EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Hanlin Zhu iD, Baihe Huang, Stuart Russell

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

circuit complexitymodel-based reinforcement learningrepresentation complexitysample complexityworld model

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}
}
Kostenlos starten →