Obviously not that fast because then they wouldn't be useful.

But fairly fast, actually — the pale green food caddy liners we use in the UK break down pretty fast in our wet environment and warm wet food starts working on them within a week. They are very likely entirely gone within six months in the open air, and much faster in the bioreactor conditions that the food waste itself goes into.

Though if you bury them it takes a lot longer, like with newspaper.

I don't think you could make a carrier bag out of that material anyway; it's potato starch and some other polymer, basically, and it is not strong.

AFAIK they are not toxic and digest in stomachs, but are not safe for ruminant animals. But then neither are waxed and printed paper bags, particularly?

There are now some PHA bags being trialled by food delivery services (though why they can't use paper I don't know): that is a stronger material that does break down fully in ordinary outdoor environments without needing "bioreactor" conditions, but again I suppose the same issues for ruminants.

The best strategy is obviously to eliminate plastic bags wherever possible and use as untreated paper as possible. I don't really understand the whining about the inconvenience of reusable shopping bags.

I can only recount my experience with them. A quick search on the topic suggests it was probably starch/cellulose based and degradation can happen within days in ideal conditions - which generally means some sort of moisture. It was stored in an enclosed but outdoor type kitchen environment, so humidity was probably elevated relative to a normal indoor scenario.