mlsanityData to 14 Oct 2026

Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model

arXiv 2005.12900 ↗First posted 26 May 2020cs.LG cs.IT math.ITcited by 109

Not on the map. Why?

Cited by 24 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator). We first consider γ-discounted infinite-horizon Markov decision processes (MDPs) with state space S and action space A. Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is yet to be determined. In particular, all prior results suffer from a severe sample size barrier, in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least frac|S||A|(1-γ)2. The current paper overcomes this barrier by certifying the minimax optimality of two algorithms -- a perturbed model-based algorithm and a conservative model-based algorithm -- as soon as the sample size exceeds the order of frac|S||A|1-γ (modulo some log factor). Moving beyond infinite-horizon MDPs, we further study time-inhomogeneous finite-horizon MDPs, and prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level. To the best of our knowledge, this work delivers the first minimax-optimal guarantees that accommodate the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically infeasible).

Key facts. Cited by 109 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 26; 2022: 20; 2023: 25; 2024: 10; 2025: 15; 2026: 13.

109 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  2. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  3. 2023Synthetic Experience Replaycited by 101
  4. 2022Robust Reinforcement Learning using Offline Datacited by 96
  5. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  6. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  7. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  8. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  9. 2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 60
  10. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  11. 2022A Survey on Quantum Reinforcement Learningcited by 53
  12. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
38 more
  1. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  2. 2022On the Principles of Parsimony and Self-Consistency for the Emergence of Intelligencecited by 50
  3. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  4. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  5. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  6. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  7. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  8. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  9. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  10. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  11. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  12. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  13. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  14. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  15. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  16. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  17. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  18. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  19. 2025Exploration vs Exploitation: Rethinking RLVR through Clipping, Entropy, and Spurious Rewardcited by 27
  20. 2022Scalable Multi-Agent Model-Based Reinforcement Learningcited by 25
  21. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  22. 2021Efficient Local Planning with Linear Function Approximationcited by 23
  23. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  24. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
  25. 2023Replicability in Reinforcement Learningcited by 21
  26. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  27. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  28. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  29. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  30. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  31. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  32. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  33. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  34. 2021An Experimental Design Perspective on Model-Based Reinforcement Learningcited by 16
  35. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  36. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  37. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  38. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15

50 most cited of 109 All 109 (JSON)