mlsanityData to 7 Oct 2026

Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency

arXiv 2302.10371 ↗First posted 21 Feb 2023cs.LG math.OC stat.MLcited by 39

Not on the map. Why?

Abstract (arXiv)

Recently, several studies (Zhou et al., 2021a; Zhang et al., 2021b; Kim et al., 2021; Zhou and Gu, 2022) have provided variance-dependent regret bounds for linear contextual bandits, which interpolates the regret for the worst-case regime and the deterministic reward regime. However, these algorithms are either computationally intractable or unable to handle unknown variance of the noise. In this paper, we present a novel solution to this open problem by proposing the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an tildeO(d √sumk = 1K σk2 + d) regret, where σk2 is the variance of the noise at the round k, d is the dimension of the contexts and K is the total number of rounds. Our results are based on an adaptive variance-aware confidence set enabled by a new Freedman-type concentration inequality for self-normalized martingales and a multi-layer structure to stratify the context vectors into different layers with different uniform upper bounds on the uncertainty. Furthermore, our approach can be extended to linear mixture Markov decision processes (MDPs) in reinforcement learning. We propose a variance-adaptive algorithm for linear mixture MDPs, which achieves a problem-dependent horizon-free regret bound that can gracefully reduce to a nearly constant regret for deterministic MDPs. Unlike existing nearly minimax optimal algorithms for linear mixture MDPs, our algorithm does not require explicit variance estimation of the transitional probabilities or the use of high-order moment estimators to attain horizon-free regret. We believe the techniques developed in this paper can have independent value for general online decision making problems.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). Builds on 37 of its 66 references that are in the map. First posted on arXiv 21 Feb 2023.

Builds on

37 of 66 references.

References · 37

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  10. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 113
  11. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  12. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
25 more
  1. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  2. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  3. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  4. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  5. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  6. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  7. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  8. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  9. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  10. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  11. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  12. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  13. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  14. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  15. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  16. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  17. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  18. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  19. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  20. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  21. 2020The Elliptical Potential Lemma Revisitedcited by 23
  22. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  23. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  24. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  25. 2022Variance-Aware Sparse Linear Banditscited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 8; 2024: 13; 2025: 12; 2026: 6.

39 papers.

Sort:

By area:

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  2. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  3. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  4. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  5. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  6. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  7. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  8. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  9. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 13
  10. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  11. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  12. 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
27 more
  1. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  2. 2024Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimizationcited by 6
  3. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  4. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  5. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  6. 2024Allocation Stability and Wald Inference under Variance-Aware UCBcited by 4
  7. 2025Variance-Dependent Regret Lower Bounds for Contextual Banditscited by 4
  8. 2025Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Boundscited by 4
  9. 2025Vector-valued self-normalized concentration inequalities beyond sub-Gaussianitycited by 4
  10. 2023Only Pay for What Is Uncertain: Variance-Adaptive Thompson Samplingcited by 3
  11. 2024Variance-Aware Linear UCB with Deep Representation for Neural Contextual Banditscited by 3
  12. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  13. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  14. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  15. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  16. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  17. 2025Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learningcited by 1
  18. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  19. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 1
  20. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  21. 2026Self-Normalized Martingales and Uniform Regret Bounds for Linear Regressioncited by 1
  22. 2024State-free Reinforcement Learningcited by 0
  23. 2025Second-Order Bounds for [0,1]-Valued Regression via Betting Losscited by 0
  24. 2026Stochastic Linear Bandits with Parameter Noisecited by 0
  25. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0
  26. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0
  27. 2026Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivitycited by 0