mlsanityData to 14 Oct 2026

Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection

arXiv 2110.14798 ↗First posted 27 Oct 2021cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

We study the role of the representation of state-action value functions in regret minimization in finite-horizon Markov Decision Processes (MDPs) with linear structure. We first derive a necessary condition on the representation, called universally spanning optimal features (UNISOFT), to achieve constant regret in any MDP with linear reward function. This result encompasses the well-known settings of low-rank MDPs and, more generally, zero inherent Bellman error (also known as the Bellman closure assumption). We then demonstrate that this condition is also sufficient for these classes of problems by deriving a constant regret bound for two optimistic algorithms (LSVI-UCB and ELEANOR). Finally, we propose an algorithm for representation selection and we prove that it achieves constant regret when one of the given representations, or a suitable combination of them, satisfies the UNISOFT condition.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 27 of its 43 references that are in the map. First posted on arXiv 27 Oct 2021.

Builds on

27 of 43 references.

References · 27

  1. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  10. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
15 more
  1. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  2. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  3. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  4. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  5. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  6. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  7. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 49
  8. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  9. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  10. 2021On the Power of Multitask Representation Learning in Linear MDPcited by 30
  11. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  12. 2020Online Model Selection for Reinforcement Learning with Function Approximationcited by 28
  13. 2020An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Banditscited by 26
  14. 2020Online Sparse Reinforcement Learningcited by 25
  15. 2014Selecting Near-Optimal Approximate State Representations in Reinforcement Learningcited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

18 papers.

Sort:

By area:

  1. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  2. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  3. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  4. 2023Structure in Deep Reinforcement Learning: A Survey and Open Problemscited by 16
  5. 2022Provable General Function Class Representation Learning in Multitask Bandits and MDPscited by 12
  6. 2024Adaptive Regularization of Representation Rank as an Implicit Constraint of Bellman Equationcited by 7
  7. 2022Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guaranteescited by 5
  8. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  9. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?cited by 4
  10. 2023Context-lumpable stochastic banditscited by 4
  11. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4
  12. 2022Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regretcited by 3
6 more
  1. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  2. 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Controlcited by 1
  3. 2025Towards Understanding the Benefit of Multitask Representation Learning in Decision Processcited by 1
  4. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  5. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
  6. 2026Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPscited by 0