Doubly-Robust Lasso Bandit
This addresses the challenge of efficient sequential decision-making in high-dimensional settings like recommendation systems, offering a method with reduced tuning and improved performance under correlated contexts, though it is incremental as it builds on existing Lasso and doubly-robust techniques.
The authors tackled the problem of high-dimensional contextual bandits where only a sparse subset of features is relevant, proposing the Doubly-Robust Lasso Bandit algorithm to achieve regret scaling logarithmically with context dimension instead of polynomially, with a high-probability upper bound independent of the number of arms.
Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, $d$. In many applications however, it is often the case that contexts are high-dimensional with only a sparse subset of size $s_0 (\ll d)$ being correlated with the reward. We consider the stochastic linear contextual bandit problem and propose a novel algorithm, namely the Doubly-Robust Lasso Bandit algorithm, which exploits the sparse structure of the regression parameter as in Lasso, while blending the doubly-robust technique used in missing data literature. The high-probability upper bound of the regret incurred by the proposed algorithm does not depend on the number of arms and scales with $\mathrm{log}(d)$ instead of a polynomial function of $d$. The proposed algorithm shows good performance when contexts of different arms are correlated and requires less tuning parameters than existing methods.