On the representation complexity of model-based and model-free reinforcement learning

We study the representation complexity of model-based and model-free reinforcement learning (RL) via circuit complexity. We prove that there exists a broad class of Markov decision processes whose underlying transition and reward functions can be represented by polynomial-sized constant-depth circuits, whereas the optimal Q-function suffers an exponential complexity in constant-depth circuits. By drawing attention to the approximation errors and building connections to complexity theory, our theory provides unique insights into why model-based algorithms usually enjoy better sample complexity than model-free algorithms from a novel representation complexity perspective: in some cases, the ground-truth rule (model) of the environment is simple to represent, while other quantities, such as Q-function, appear complex. This also emphasizes the importance and advantage of the underlying world model when building and learning artificial intelligence models. We empirically corroborate our theory by comparing the approximation errors of the transition kernel, reward function and optimal Q-function in various MuJoCo environments, which demonstrates that the approximation errors of the transition kernel and reward function are consistently lower than those of the optimal Q-function. To the best of our knowledge, this work is the first to study the circuit complexity of RL and also provides a rigorous framework for future research. This article is part of the theme issue 'World models in natural and artificial intelligence'.