There are biodegradable bags [1], but not sure if they are completely plastic-free ("38% vegetable-based").

1. http://amzn.com/dp/B01LXVVH1I