mlsanityData to 14 Oct 2026

Achieving Constant Regret in Linear Markov Decision Processes

arXiv 2404.10745 ↗First posted 16 Apr 2024cs.LGcited by 3

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

Abstract (arXiv)

We study the constant regret guarantees in reinforcement learning (RL). Our objective is to design an algorithm that incurs only finite regret over infinite episodes with high probability. We introduce an algorithm, Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs) where both the transition kernel and the reward function can be approximated by some linear function up to misspecification level zeta. At the core of Cert-LSVI-UCB is an innovative method, which facilitates a fine-grained concentration analysis for multi-phase value-targeted regression, enabling us to establish an instance-dependent regret bound that is constant w.r.t. the number of episodes. Specifically, we demonstrate that for a linear MDP characterized by a minimal suboptimality gap Delta, Cert-LSVI-UCB has a cumulative regret of tildeO(d3H5/Delta) with high probability, provided that the misspecification level zeta is below tildeO(Delta / (√dH2)). Here d is the dimension of the feature space and H is the horizon. Remarkably, this regret bound is independent of the number of episodes K. To the best of our knowledge, Cert-LSVI-UCB is the first algorithm to achieve a constant, instance-dependent, high-probability regret bound in RL with linear function approximation without relying on prior distribution assumptions.

Key facts. Cited by 3 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 37 references that are in the map. First posted on arXiv 16 Apr 2024.

Builds on

27 of 37 references.

References · 27

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  7. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  8. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  9. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  10. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  11. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  12. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
15 more
  1. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  2. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  3. 2020Q-learning with Logarithmic Regretcited by 60
  4. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  5. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  6. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  7. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  8. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  9. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  10. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
  11. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  12. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
  13. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  14. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  15. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025A variational approach to dimension-free self-normalized concentrationcited by 2
  2. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  3. 2026Provably Efficient Offline-to-Online Value Adaptation with General Function Approximationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
  2. 2024Horizon-Free Regret for Linear Markov Decision Processes
  3. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  4. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
  5. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  6. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  7. 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
  8. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation