提出自适应协方差的半多臂老虎机算法，解决稀疏奖励场景下的学习效率问题。
Covariance-adapting algorithm for semi-bandits with application to sparse rewards
- 采用子指数分布族建模，无需预先知道高斯性参数
- 新下界以未知协方差矩阵为参数，比传统子高斯界更紧致
- 算法动态估计协方差，在推荐系统等稀疏奖励场景表现优异
我们研究随机组合半多臂老虎机问题，其中结果的联合分布直接影响问题复杂度（不同于标准多臂老虎机）。以往方法依赖特定参数分布（如子高斯分布），需先验知识，实践中难以估计。本文改用新的子指数分布族，包含有界分布和高斯分布。证明了该族上期望遗憾的新下界，其参数为未知的结果协方差矩阵，比子高斯矩阵更紧。随后设计一种利用协方差估计的算法，并给出紧致渐近分析。最后将结果扩展至稀疏结果情形，适用于众多推荐系统场景。
原文摘要 · Abstract (English)
We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits). Typical distributions considered depend on specific parameter values, whose prior knowledge is required in theory but quite difficult to estimate in practice; an example is the commonly assumed sub-Gaussian family. We alleviate this issue by instead considering a new general family of sub-exponential distributions, which contains bounded and Gaussian ones. We prove a new lower bound on the expected regret on this family, that is parameterized by the unknown covariance matrix of outcomes, a tighter quantity than the sub-Gaussian matrix. We then construct an algorithm that uses covariance estimates, and provide a tight asymptotic analysis of the regret. Finally, we apply and extend our results to the family of sparse outcomes, which has applications in many recommender systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。