mlsanityData to 7 Oct 2026

Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning

arXiv 2111.00633 ↗First posted 1 Nov 2021cs.LG cs.AI cs.DScited by 17

Not on the map. Why?

Abstract (arXiv)

Recently there is a surge of interest in understanding the horizon-dependence of the sample complexity in reinforcement learning (RL). Notably, for an RL environment with horizon length H, previous work have shown that there is a probably approximately correct (PAC) algorithm that learns an O(1)-optimal policy using polylog(H) episodes of environment interactions when the number of states and actions is fixed. It is yet unknown whether the polylog(H) dependence is necessary or not. In this work, we resolve this question by developing an algorithm that achieves the same PAC guarantee while using only O(1) episodes of environment interactions, completely settling the horizon-dependence of the sample complexity in RL. We achieve this bound by (i) establishing a connection between value functions in discounted and finite-horizon Markov decision processes (MDPs) and (ii) a novel perturbation analysis in MDPs. We believe our new techniques are of independent interest and could be applied in related questions in RL.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 24 of its 45 references that are in the map. First posted on arXiv 1 Nov 2021.

Builds on

24 of 45 references.

References · 24

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  8. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  9. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  10. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  11. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  12. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
12 more
  1. 2020Q-learning with Logarithmic Regretcited by 59
  2. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  3. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  4. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  5. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  6. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  7. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  8. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  9. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  10. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  11. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  12. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 5; 2024: 4; 2025: 1; 2026: 2.

17 papers.

Sort:

By area:

  1. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  2. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  3. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  4. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  5. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  6. 2025Rapidly Adapting Policies to the Real World via Simulation-Guided Fine-Tuningcited by 15
  7. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  8. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  9. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  10. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  11. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  12. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
5 more
  1. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  2. 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Reviewcited by 3
  3. 2024Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learningcited by 1
  4. 2026Adaptive Estimation and Optimal Control in Offline Contextual MDPs without Stationaritycited by 1
  5. 2026Optimal Multi-Reward Reinforcement Learningcited by 0