A Limitation on Black-Box Dynamics Approaches to Reinforcement Learning
Abstract
We prove a fundamental limitation on the computational efficiency of a large class of Reinforcement Learning (RL) methods. This limitation applies to model-free RL methods as well as some model-based methods, such as AlphaZero. We provide a formalism that describes this class and present a family of RL problems provably intractable for these methods. Conversely, the problems in the family can be efficiently solved by toy methods. We identify several types of algorithms proposed in the literature that can avoid our limitation, including algorithms that construct an inverse dynamics model, and planning algorithms that leverage an explicit model of the dynamics.
Cite
Text
Pinon et al. "A Limitation on Black-Box Dynamics Approaches to Reinforcement Learning." Transactions on Machine Learning Research, 2025.Markdown
[Pinon et al. "A Limitation on Black-Box Dynamics Approaches to Reinforcement Learning." Transactions on Machine Learning Research, 2025.](https://mlanthology.org/tmlr/2025/pinon2025tmlr-limitation/)BibTeX
@article{pinon2025tmlr-limitation,
title = {{A Limitation on Black-Box Dynamics Approaches to Reinforcement Learning}},
author = {Pinon, Brieuc and Jungers, Raphael and Delvenne, Jean-Charles},
journal = {Transactions on Machine Learning Research},
year = {2025},
url = {https://mlanthology.org/tmlr/2025/pinon2025tmlr-limitation/}
}