Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set

arXiv:2607.23679v1 Announce Type: new Abstract: 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 = sum_{t=1}^T sigma_t^2, where sigma_t^2 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 ilde{al{O}}(d sqrt{Lambda / T^2}) 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 exttt{VAEE} (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 exttt{VAEE} 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 sqrt{Lambda} barrier for stochastic linear bandits with heteroscedastic noise.

Source: arXiv cs.LG | 2026-07-28

Related