Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning. In these works, the cumulative variance of the noise Lambda = sumt=1T σt2, where σt2 is the variance of the noise at round t, is used to characterize the statistical complexity of the problem, yielding simple regret bounds of order tildecalO(d √Lambda / T2) for d-dimensional linear bandits with heteroscedastic noise. However, with a closer look, Lambda remains the same order even if the noise is close to zero at half of the rounds, which indicates that the Lambda-dependence is not optimal. In this paper, we revisit the stochastic linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process. We propose a novel variance-adaptive algorithm textttVAEE (Variance-Aware Exploration with Elimination) for large action set, which actively explores actions that maximizes the information gain among a candidate set of actions that are not eliminated. With the active-exploration strategy, we show that textttVAEE achieves a simple regret with a nearly harmonic-mean dependent rate. For finitely many actions, we propose a variance-aware variant of G-optimal design based exploration, which achieves a simple regret with sharper dependence on d. We also establish a nearly matching lower bound for the fixed action set setting indicating that harmonic-mean dependent rate is unavoidable. To the best of our knowledge, this is the first work that breaks the √Lambda barrier for stochastic linear bandits with heteroscedastic noise.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 24 of its 39 references that are in the map. First posted on arXiv 26 Jul 2026.
Builds on
24 of 39 references.
Closest ancestors · 3
Same direction, newest first
- 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimation4 Aug
- 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds16 Aug
- 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning11 Feb
Other references · 21
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
- 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
- 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
- 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
- 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
- 2018Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffscited by 31
- 2020MOTS: Minimax Optimal Thompson Samplingcited by 28
- 2017A minimax and asymptotically optimal algorithm for stochastic banditscited by 27
- 2020Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffscited by 25
9 more
- 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
- 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 14
- 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
- 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
- 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
- 2021Do we need to estimate the variance in robust mean estimation?cited by 6
- 2022Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Banditscited by 5
- 2025Variance-Dependent Regret Lower Bounds for Contextual Banditscited by 4
- 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis
- 2025A Framework for Fair Evaluation of Variance-Aware Bandit Algorithms
- 2025Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits
- 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
- 2025Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits
- 2025An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical System
- 2024On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization
- 2024Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits