I think govt subsidy on compostable biodegradable plastics would be good too. Especially if the subsidy was not just on the bags themselves, but the research and process engineering to make them more cost-competitive.

In the US at least, cities can also get creative, such as exempting compostable items from sales taxes.