利用已知分组结构，设计高效算法提升多臂赌博机性能
Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits
- 基于已知分组信息设计新索引，实现组内臂之间的信息共享
- 渐近最优，理论后悔上界优于经典方法
- 适合具有相似奖励结构的多臂场景，如推荐系统
我们研究一种随机多臂赌博机设置，其中臂被划分为已知的簇，同一簇内臂的均值差异不超过已知阈值。尽管簇结构已知，但臂的均值未知。我们推导出一个改进于经典Lai & Robbins（1985）下界的渐近后悔下界。随后提出Clus-UCB算法，该算法能渐近逼近此下界。该算法利用簇结构，引入依赖同簇其他臂的新索引机制，使臂间可共享信息。通过仿真验证其性能，并与KL-UCB及其他依赖臂的算法进行对比。最后讨论了本工作的局限性，并提出未来可能的研究方向。
原文摘要 · Abstract (English)
We study a stochastic multi-armed bandit setting where arms are partitioned into known clusters, such that the mean rewards of arms within a cluster differ by at most a known threshold. While the clustering structure is known a priori, the arm means are unknown. We derive an asymptotic lower bound on the regret that improves upon the classical bound of Lai & Robbins (1985). We then propose Clus-UCB, an efficient algorithm that closely matches this lower bound asymptotically. Clus-UCB is designed to exploit the clustering structure and introduces a new index to evaluate an arm, which depends on other arms within the cluster. In this way, arms share information among each other. We present simulation results of our algorithm and compare its performance against KL-UCB and other wellknown algorithms for bandits with dependent arms. Finally, we address some limitations of this work and conclude by mentioning some possible future research.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。