On the representation complexity of model-based and model-free reinforcement learning
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · 14.05.2026 · 384 (2320)
DOI: 10.1098/rsta.2024.0532 ↗Kurz gefasst
Fachartikel in der Zeitschrift Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, online erschienen am 14.05.2026. Verfasst von Hanlin Zhu und 2 weiteren Autor:innen. Beteiligte Einrichtung: EECS, University of California, Berkeley, Berkeley, CA, USA. Die Arbeit nennt 75 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: A gift from Open Philanthropy to the Center for Human-Compatible AI (CHAI) at UC Berkeley.
Abstract (Originalsprache)
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’.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- EECS, University of California, Berkeley, Berkeley, CA, USA.
ORCID-Profile: Hanlin Zhu
Förderung
- A gift from Open Philanthropy to the Center for Human-Compatible AI (CHAI) at UC Berkeley
Zitieren
APA
Zhu, H., Huang, B., & Russell, S. (2026). On the representation complexity of model-based and model-free reinforcement learning. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 384(2320). https://doi.org/10.1098/rsta.2024.0532
Vancouver
Zhu H, Huang B, Russell S. On the representation complexity of model-based and model-free reinforcement learning. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2026;384(2320). doi:10.1098/rsta.2024.0532
BibTeX
@article{Zhu2026,
author = {Zhu, Hanlin and Huang, Baihe and Russell, Stuart},
title = {On the representation complexity of model-based and model-free reinforcement learning},
journal = {Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences},
year = {2026},
volume = {384},
number = {2320},
doi = {10.1098/rsta.2024.0532}
}
EUVIMED