On Representation Complexity of Model-based and Model-free Reinforcement Learning

Hanlin Zhu, Baihe Huang, Stuart Russell

We study the representation complexity of model-based and model-free reinforcement learning (RL) in the context of circuit complexity. We prove theoretically that there exists a br…