Efficiency Separation between RL Methods: Model-Free, Model-Based and
  Goal-Conditioned
Brieuc Pinon Raphaël Jungers Jean-Charles Delvenne
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.