mlsanityData to 14 Oct 2026

Horizon-Free Regret for Linear Markov Decision Processes

arXiv 2403.10738 ↗First posted 15 Mar 2024cs.LGcited by 6

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

A recent line of works showed regret bounds in reinforcement learning (RL) can be (nearly) independent of planning horizon, a.k.a.~the horizon-free bounds. However, these regret bounds only apply to settings where a polynomial dependency on the size of transition model is allowed, such as tabular Markov Decision Process (MDP) and linear mixture MDP. We give the first horizon-free bound for the popular linear MDP setting where the size of the transition model can be exponentially large or even uncountable. In contrast to prior works which explicitly estimate the transition model and compute the inhomogeneous value functions at different time steps, we directly estimate the value functions and confidence sets. We obtain the horizon-free bound by: (1) maintaining multiple weighted least square estimators for the value functions; and (2) a structural lemma which shows the maximal total variation of the inhomogeneous value functions is bounded by a polynomial factor of the feature dimension.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 27 of its 40 references that are in the map. First posted on arXiv 15 Mar 2024.

Builds on

27 of 40 references.

References · 27

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  10. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  11. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  12. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
15 more
  1. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  2. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  3. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  4. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  5. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  6. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  7. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  8. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  9. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  10. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 35
  11. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  12. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  13. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  14. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  15. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 0; 2026: 3.

6 papers.

  1. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  2. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  3. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  4. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  5. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1
  6. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  3. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
  4. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  5. 2024Achieving Constant Regret in Linear Markov Decision Processes
  6. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  7. 2024No-Regret Reinforcement Learning in Smooth MDPs
  8. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation