论文标题
稀疏性不足的拉索匪
Sparsity-Agnostic Lasso Bandit
论文作者
论文摘要
我们考虑了一个随机上下文的强盗问题，其中特征向量的尺寸$ d $可能很大，但是，只有稀疏的基数特征$ s_0 \ ll d $影响奖励功能。本质上，所有现有的稀疏匪徒都需要先验了解稀疏指数$ s_0 $的价值。实际上，这些知识几乎从未获得，并且此参数的错误指定会导致现有方法的性能严重恶化。本文的主要贡献是提出一种算法，该算法不需要先验了解稀疏指数$ s_0 $，并在轻度条件下对其性能建立狭窄的遗憾界限。我们还通过数字上全面评估了我们提出的算法，并表明它始终优于现有方法，即使向它们揭示了正确的稀疏索引，但仍将其隐藏在我们的算法中。
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.
