mlsanityData to 7 Oct 2026

Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies

arXiv 2203.12922 ↗First posted 24 Mar 2022cs.LGcited by 27

Not on the map. Why?

Abstract (arXiv)

This paper gives the first polynomial-time algorithm for tabular Markov Decision Processes (MDP) that enjoys a regret bound independent on the planning horizon. Specifically, we consider tabular MDP with S states, A actions, a planning horizon H, total reward bounded by 1, and the agent plays for K episodes. We design an algorithm that achieves an Oleft(poly(S,A,log K)√Kright) regret in contrast to existing bounds which either has an additional polylog(H) dependency~citepzhang2020reinforcement or has an exponential dependency on S~citepli2021settling. Our result relies on a sequence of new structural lemmas establishing the approximation power, stability, and concentration property of stationary policies, which can have applications in other problems related to Markov chains.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 29 of its 51 references that are in the map. First posted on arXiv 24 Mar 2022.

Builds on

29 of 51 references.

References · 29

  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. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  7. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  8. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  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
17 more
  1. 2020Q-learning with Logarithmic Regretcited by 59
  2. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  3. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  4. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  5. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  6. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  7. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  8. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  9. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  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. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  13. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  14. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  15. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  16. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  17. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 9; 2024: 4; 2025: 7; 2026: 1.

27 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. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  5. 2023Optimal Multi-Distribution Learningcited by 13
  6. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  7. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  8. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  9. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  10. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  11. 2024VC Theory for Inventory Policiescited by 7
  12. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
15 more
  1. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  2. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  3. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  4. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  5. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  6. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  7. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  8. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  9. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  10. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  11. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  12. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  13. 2024Utilizing Maximum Mean Discrepancy Barycenter for Propagating the Uncertainty of Value Functions in Reinforcement Learningcited by 0
  14. 2025The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportabilitycited by 0
  15. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0