We study the best-arm identification problem in sparse linear bandits under
the fixed-budget setting. In sparse linear bandits, the unknown feature vector
$\theta^*$ may be of large dimension $d$, but only a few, say $s \ll d$ of
these features have non-zero values. We design a two-phase algorithm, Lasso and
Optimal-Design- (Lasso-OD) based linear best-arm identification. The first
phase of Lasso-OD leverages the sparsity of the feature vector by applying the
thresholded Lasso introduced by Zhou (2009), which estimates the support of
$\theta^*$ correctly with high probability using rewards from the selected arms
and a judicious choice of the design matrix. The second phase of Lasso-OD
applies the OD-LinBAI algorithm by Yang and Tan (2022) on that estimated
support. We derive a non-asymptotic upper bound on the error probability of
Lasso-OD by carefully choosing hyperparameters (such as Lasso's regularization
parameter) and balancing the error probabilities of both phases. For fixed
sparsity $s$ and budget $T$, the exponent in the error probability of Lasso-OD
depends on $s$ but not on the dimension $d$, yielding a significant performance
improvement for sparse and high-dimensional linear bandits. Furthermore, we
show that Lasso-OD is almost minimax optimal in the exponent. Finally, we
provide numerical examples to demonstrate the significant performance
improvement over the existing algorithms for non-sparse linear bandits such as
OD-LinBAI, BayesGap, Peace, LinearExploration, and GSE.

稀疏线性赌博机中的最佳臂识别问题，设计了基于 Lasso-OD 算法的两阶段线性最佳臂识别算法，对于稀疏且高维的线性赌博机，在固定稀疏度和预算下，通过精心设置超参数和平衡两个阶段的错误概率，获得显著的性能改进，同时在指数上接近极小极大最优。

稀疏线性赌臂机器中的固定预算最佳臂识别

Fixed-Budget Best-Arm Identification in Sparse Linear Bandits

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 算法。