Sparsity-Agnostic Lasso Bandit
This addresses a practical limitation in sparse bandit algorithms for high-dimensional decision-making, though it is incremental as it builds on existing sparse bandit frameworks.
The paper tackles the problem of sparse contextual bandits where existing methods require prior knowledge of the sparsity index, which is often unavailable in practice. They propose a sparsity-agnostic algorithm that achieves tight regret bounds and outperforms existing methods in numerical evaluations, even when those methods are given the correct sparsity index.
We consider a stochastic contextual bandit problem where the dimension $d$ of the feature vectors is potentially large, however, only a sparse subset of features of cardinality $s_0 \ll d$ affect the reward function. Essentially all existing algorithms for sparse bandits require a priori knowledge of the value of the sparsity index $s_0$. This knowledge is almost never available in practice, and misspecification of this parameter can lead to severe deterioration in the performance of existing methods. The main contribution of this paper is to propose an algorithm that does not require prior knowledge of the sparsity index $s_0$ and establish tight regret bounds on its performance under mild conditions. We also comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms existing methods, even when the correct sparsity index is revealed to them but is kept hidden from our algorithm.