We consider the sparse contextual bandit problem where arm feature affects reward through the inner product of sparse parameters. Recent studies have developed sparsity-agnostic algorithms based on the greedy arm selection policy. However, the analysis of these algorithms requires strong assumptions on the arm feature distribution to ensure that the greedily selected samples are sufficiently diverse; One of the most common assumptions, relaxed symmetry, imposes approximate origin-symmetry on the distribution, which cannot allow distributions that has origin-asymmetric support. In this paper, we show that the greedy algorithm is applicable to a wider range of the arm feature distributions from two aspects. Firstly, we show that a mixture distribution that has a greedy-applicable component is also greedy-applicable. Second, we propose new distribution classes, related to Gaussian mixture, discrete, and radial distribution, for which the sample diversity is guaranteed. The proposed classes can describe distributions with origin-asymmetric support and, in conjunction with the first claim, provide theoretical guarantees of the greedy policy for a very wide range of the arm feature distributions.

在这篇论文中，我们考虑了稀疏背景下的上下文强化学习问题，其中臂特征通过稀疏参数的内积影响奖励。我们证明了贪心算法适用于更广泛的臂特征分布，提出了与高斯混合、离散和径向分布相关的新分布类，确保样本的多样性，从而为贪心策略在非常广泛的臂特征分布上提供了理论保证。

稀疏线性强化学习问题中，用于贪婪算法的新类臂特征分布