It is well-known that for sparse linear bandits, when ignoring the dependency
on sparsity which is much smaller than the ambient dimension, the worst-case
minimax regret is $\widetilde{\Theta}\left(\sqrt{dT}\right)$ where $d$ is the
ambient dimension and $T$ is the number of rounds. On the other hand, in the
benign setting where there is no noise and the action set is the unit sphere,
one can use divide-and-conquer to achieve $\widetilde{\mathcal O}(1)$ regret,
which is (nearly) independent of $d$ and $T$. In this paper, we present the
first variance-aware regret guarantee for sparse linear bandits:
$\widetilde{\mathcal O}\left(\sqrt{d\sum_{t=1}^T \sigma_t^2} + 1\right)$, where
$\sigma_t^2$ is the variance of the noise at the $t$-th round. This bound
naturally interpolates the regret bounds for the worst-case constant-variance
regime (i.e., $\sigma_t \equiv \Omega(1)$) and the benign deterministic regimes
(i.e., $\sigma_t \equiv 0$). To achieve this variance-aware regret guarantee,
we develop a general framework that converts any variance-aware linear bandit
algorithm to a variance-aware algorithm for sparse linear bandits in a
"black-box" manner. Specifically, we take two recent algorithms as black boxes
to illustrate that the claimed bounds indeed hold, where the first algorithm
can handle unknown-variance cases and the second one is more efficient.

本文发展了一种数据稀疏 (稀疏线性斯托剖斯) 的新型算法，该算法使较小的环境维度下研究致命后果的风险得以降低，实现了一种有区别的、具有人造和样本方差适应性的总体安全算法。同时，该研究还探讨了如何在一种 <黑盒> 化的方式下将任何方差算法转化为 sparce linear bandits 算法。