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.

提出了一种新的算法：Doubly-Robust Lasso Bandit algorithm，它利用线性回归参数的稀疏结构，融合在缺失数据文献中使用的双重稳健技术，解决了高维稀疏环境下多臂赌博机算法的问题，大大减少了调参数量和算法复杂度。