mlsanityData to 14 Oct 2026

Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP

arXiv 2101.12745 ↗First posted 29 Jan 2021cs.LGcited by 45

Not on the map. Why?

Abstract (arXiv)

This paper presents new variance-aware confidence sets for linear bandits and linear mixture Markov Decision Processes (MDPs). With the new confidence sets, we obtain the follow regret bounds: For linear bandits, we obtain an tildeO(poly(d)√1 + sumk=1Kσk2) data-dependent regret bound, where d is the feature dimension, K is the number of rounds, and σk2 is the unknown variance of the reward at the k-th round. This is the first regret bound that only scales with the variance and the dimension but no explicit polynomial dependency on K. When variances are small, this bound can be significantly smaller than the tildeThetaleft(d√Kright) worst-case regret bound. For linear mixture MDPs, we obtain an tildeO(poly(d, log H)√K) regret bound, where d is the number of base models, K is the number of episodes, and H is the planning horizon. This is the first regret bound that only scales logarithmically with H in the reinforcement learning with linear function approximation setting, thus exponentially improving existing results, and resolving an open problem in citepzhou2020nearly. We develop three technical ideas that may be of independent interest: 1) applications of the peeling technique to both the input norm and the variance magnitude, 2) a recursion-based estimator for the variance, and 3) a new convex potential lemma that generalizes the seminal elliptical potential lemma.

Key facts. Cited by 45 papers in the map (data through 14 Oct 2026). Builds on 37 of its 70 references that are in the map. First posted on arXiv 29 Jan 2021.

Builds on

37 of 70 references.

References · 37

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  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. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  11. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  12. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
25 more
  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  3. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  4. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  5. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  6. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  7. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  8. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  9. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  10. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  11. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  12. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  13. 2020Optimal Best-arm Identification in Linear Banditscited by 71
  14. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  15. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 57
  16. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  17. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  18. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
  19. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 35
  20. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  21. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  22. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  23. 2019Tight Regret Bounds for Infinite-armed Linear Contextual Banditscited by 17
  24. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  25. 2020Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learningcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 6; 2023: 13; 2024: 11; 2025: 9; 2026: 5.

45 papers.

Sort:

By area:

  1. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  2. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  3. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  4. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  5. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  6. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  7. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
  8. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
  9. 2022Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Armscited by 15
  10. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  11. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 14
  12. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 14
33 more
  1. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  2. 2022Variance-Aware Sparse Linear Banditscited by 11
  3. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  4. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  5. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  6. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  7. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  8. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
  9. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  10. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 4
  11. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  12. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  13. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  14. 2024Allocation Stability and Wald Inference under Variance-Aware UCBcited by 4
  15. 2025Variance-Dependent Regret Lower Bounds for Contextual Banditscited by 4
  16. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4
  17. 2025Vector-valued self-normalized concentration inequalities beyond sub-Gaussianitycited by 4
  18. 2023SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Banditscited by 3
  19. 2023Only Pay for What Is Uncertain: Variance-Adaptive Thompson Samplingcited by 3
  20. 2024Variance-Aware Linear UCB with Deep Representation for Neural Contextual Banditscited by 3
  21. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  22. 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 3
  23. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  24. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  25. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 2
  26. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  27. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  28. 2026Prior Diffusiveness and Regret in the Linear-Gaussian Banditcited by 1
  29. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  30. 2024Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancementcited by 0
  31. 2026Stochastic Linear Bandits with Parameter Noisecited by 0
  32. 2026Learning to Attack: A Bandit Approach to Adversarial Context Poisoningcited by 0
  33. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0