mlsanityData to 7 Oct 2026

First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach

arXiv 2112.03432 ↗First posted 7 Dec 2021cs.LG stat.MLcited by 38

Not on the map. Why?

Abstract (arXiv)

Obtaining first-order regret bounds -- regret bounds scaling not as the worst-case but with some measure of the performance of the optimal policy on a given instance -- is a core question in sequential decision-making. While such bounds exist in many settings, they have proven elusive in reinforcement learning with large state spaces. In this work we address this gap, and show that it is possible to obtain regret scaling as widetildeO(√d3 H3 · V1^star · K + d3.5H3log K ) in reinforcement learning with large state spaces, namely the linear MDP setting. Here V1^star is the value of the optimal policy and K is the number of episodes. We demonstrate that existing techniques based on least squares estimation are insufficient to obtain this result, and instead develop a novel robust self-normalized concentration bound based on the robust Catoni mean estimator, which may be of independent interest.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). Builds on 40 of its 64 references that are in the map. First posted on arXiv 7 Dec 2021.

Builds on

40 of 64 references.

References · 40

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  10. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  12. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
28 more
  1. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  2. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  5. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  6. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  7. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  8. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  9. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  10. 2018Near optimal finite time identification of arbitrary linear dynamical systemscited by 89
  11. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  12. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  13. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  14. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  15. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  16. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  17. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  18. 2015Second-order Quantile Methods for Experts and Combinatorial Gamescited by 47
  19. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  20. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  21. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  22. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  23. 2015First-order regret bounds for combinatorial semi-banditscited by 25
  24. 2015Adaptive Online Learningcited by 23
  25. 2020Taking a hint: How to leverage loss predictors in contextual bandits?cited by 20
  26. 2017Small-loss bounds for online learning with partial informationcited by 18
  27. 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
  28. 2019First-Order Bayesian Regret Analysis of Thompson Samplingcited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 9; 2023: 12; 2024: 7; 2025: 8; 2026: 2.

38 papers.

Sort:

By area:

  1. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  2. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  3. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  4. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  5. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  6. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  7. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  8. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  9. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  10. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  11. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  12. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
26 more
  1. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  2. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  3. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  4. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  5. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  6. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learningcited by 8
  7. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  8. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  9. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  10. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  11. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  12. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  13. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  14. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  15. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  16. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  17. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  18. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  19. 2026Eluder dimension: localise it!cited by 2
  20. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  21. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  22. 2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1
  23. 2023Robust Offline Reinforcement Learning -- Certify the Confidence Intervalcited by 0
  24. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
  25. 2025Second-Order Bounds for [0,1]-Valued Regression via Betting Losscited by 0
  26. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0