In this paper, we revisit the regret minimization problem in sparse
stochastic contextual linear bandits, where feature vectors may be of large
dimension $d$, but where the reward function depends on a few, say $s_0\ll d$,
of these features only. We present Thresholded Lasso bandit, an algorithm that
(i) estimates the vector defining the reward function as well as its sparse
support, i.e., significant feature elements, using the Lasso framework with
thresholding, and (ii) selects an arm greedily according to this estimate
projected on its support. The algorithm does not require prior knowledge of the
sparsity index $s_0$ and can be parameter-free under some symmetric
assumptions. For this simple algorithm, we establish non-asymptotic regret
upper bounds scaling as $\mathcal{O}( \log d + \sqrt{T} )$ in general, and as
$\mathcal{O}( \log d + \log T)$ under the so-called margin condition (a
probabilistic condition on the separation of the arm rewards). The regret of
previous algorithms scales as $\mathcal{O}( \log d + \sqrt{T \log (d T)})$ and
$\mathcal{O}( \log T \log d)$ in the two settings, respectively. Through
numerical experiments, we confirm that our algorithm outperforms existing
methods.

本文提出一种基于阈值套索算法的 regret minimization 解决方案，能够更好地应对稀疏随机上下文线性赌博机问题，且不需要对稀疏度等参数有先验知识，理论上的性能约束也有所提高。