mlsanityData to 14 Oct 2026

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

arXiv 2309.16291 ↗First posted 28 Sep 2023cs.LG cs.AIcited by 0

Not on the map. Why?

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.

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

17 of 32 references.

References · 17

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  3. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,546
  4. 2017Hindsight Experience Replaycited by 1,136
  5. 2022Planning with Diffusion for Flexible Behavior Synthesiscited by 1,061
  6. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  7. 2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 252
  8. 2021RvS: What is Essential for Offline RL via Supervised Learning?cited by 185
  9. 2015Learning Continuous Control Policies by Stochastic Value Gradientscited by 162
  10. 2018Model-Based Value Estimation for Efficient Model-Free Reinforcement Learningcited by 156
  11. 2019Reinforcement Learning Upside Down: Don't Predict Rewards -- Just Map Them to Actionscited by 125
  12. 2019Reward-Conditioned Policiescited by 102
5 more
  1. 2022You Can't Count on Luck: Why Decision Transformers and RvS Fail in Stochastic Environmentscited by 63
  2. 2022Dichotomy of Control: Separating What You Can Control from What You Cannotcited by 47
  3. 2018The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpointcited by 40
  4. 2022Imitating Past Successes can be Very Suboptimalcited by 23
  5. 2022Addressing Optimism Bias in Sequence Modeling for Reinforcement Learningcited by 22

Built on by

Not cited yet.