We consider a stochastic sparse linear bandit problem where only a sparse
subset of context features affects the expected reward function, i.e., the
unknown reward parameter has sparse structure. In the existing Lasso bandit
literature, the compatibility conditions together with additional diversity
conditions on the context features are imposed to achieve regret bounds that
only depend logarithmically on the ambient dimension $d$. In this paper, we
demonstrate that even without the additional diversity assumptions, the
compatibility condition only on the optimal arm is sufficient to derive a
regret bound that depends logarithmically on $d$, and our assumption is
strictly weaker than those used in the lasso bandit literature under the single
parameter setting. We propose an algorithm that adapts the forced-sampling
technique and prove that the proposed algorithm achieves $O(\text{poly}\log
dT)$ regret under the margin condition. To our knowledge, the proposed
algorithm requires the weakest assumptions among Lasso bandit algorithms under
a single parameter setting that achieve $O(\text{poly}\log dT)$ regret. Through
the numerical experiments, we confirm the superior performance of our proposed
algorithm.

这篇论文研究了一种稀疏线性的随机赌博问题，其中只有稀疏的上下文特征子集影响预期的回报函数。作者提出了一个算法，借助强制抽样技术，在单参数设置下表现出 polylog 的 dT 遗憾，相较于 Lasso 赌博算法，该算法假设更弱且性能更好。