这篇论文提出了VAEE算法，首次在异方差线性Bandit中打破了总方差屏障，实现了更紧的遗憾界，适合对Bandit理论感兴趣的研究者。
这篇论文针对固定动作集的异方差噪声线性Bandit问题，提出了方差自适应算法VAEE。VAEE通过主动探索未淘汰动作集中信息增益最大的动作，实现了简单遗憾界接近谐波均值依赖，打破了此前依赖总方差Λ的界限。对于有限动作集，论文还提出了基于G-optimal设计的方差感知变体，并证明了近乎匹配的下界。这是首个在异方差线性Bandit中突破√Λ屏障的工作。
Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning. In these works, the cumulative variance of the noise $Λ= \sum_{t=1}^T σ_t^2$, where $σ_t^2$ is the variance of the noise at round $t$, is used to characterize the statistical complexity of the problem, yielding \emph{simple regret} bounds of order $\tilde{\cal{O}}(d \sqrt{Λ/ T^2})$ for $d$-dimensional linear bandits with heteroscedastic noise. However, with a closer look, $Λ$ remains the same order even if the noise is close to zero at half of the rounds, which indicates that the $Λ$-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 \texttt{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 \texttt{VAEE} achieves a \emph{simple regret} with a nearly \emph{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 \emph{harmonic-mean} dependent rate is unavoidable. To the best of our knowledge, this is the first work that breaks the $\sqrtΛ$ barrier for stochastic linear bandits with heteroscedastic noise.