Thresholded Lasso Bandit
This work addresses the challenge of efficient decision-making in high-dimensional bandit settings for applications like recommendation systems, though it is incremental as it builds on existing Lasso and bandit frameworks.
The paper tackles the regret minimization problem in sparse stochastic contextual linear bandits by proposing the Thresholded Lasso bandit algorithm, which achieves non-asymptotic regret bounds of O(log d + sqrt(T)) in general and O(log d + log T) under a margin condition, outperforming previous methods with bounds like O(log d + sqrt(T log(dT))).
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.