# Efficiency Separation between RL Methods: Model-Free, Model-Based and Goal-Conditioned

arXiv: https://arxiv.org/abs/2309.16291 · HTML: https://mlsanity.com/paper/2309.16291/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 28 Sep 2023.

## Builds on (most cited first, 17 of 17)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [RvS: What is Essential for Offline RL via Supervised Learning?](https://mlsanity.com/paper/2112.10751/) (2021)
- [Learning Continuous Control Policies by Stochastic Value Gradients](https://mlsanity.com/paper/1510.09142/) (2015)
- [Model-Based Value Estimation for Efficient Model-Free Reinforcement Learning](https://mlsanity.com/paper/1803.00101/) (2018)
- [Reinforcement Learning Upside Down: Don't Predict Rewards -- Just Map Them to Actions](https://mlsanity.com/paper/1912.02875/) (2019)
- [Reward-Conditioned Policies](https://mlsanity.com/paper/1912.13465/) (2019)
- [You Can't Count on Luck: Why Decision Transformers and RvS Fail in Stochastic Environments](https://mlsanity.com/paper/2205.15967/) (2022)
- [Dichotomy of Control: Separating What You Can Control from What You Cannot](https://mlsanity.com/paper/2210.13435/) (2022)
- [The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint](https://mlsanity.com/paper/1812.03565/) (2018)
- [Imitating Past Successes can be Very Suboptimal](https://mlsanity.com/paper/2206.03378/) (2022)
- [Addressing Optimism Bias in Sequence Modeling for Reinforcement Learning](https://mlsanity.com/paper/2207.10295/) (2022)

## Abstract (arXiv)

We prove a fundamental limitation on the efficiency of a wide class of Reinforcement Learning (RL) algorithms. This limitation applies to model-free RL methods as well as a broad range of model-based methods, such as planning with tree search. Under an abstract definition of this class, we provide a family of RL problems for which these methods suffer a lower bound exponential in the horizon for their interactions with the environment to find an optimal behavior. However, there exists a method, not tailored to this specific family of problems, which can efficiently solve the problems in the family. In contrast, our limitation does not apply to several types of methods proposed in the literature, for instance, goal-conditioned methods or other algorithms that construct an inverse dynamics model.