Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization
Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Chengshuai Shi;Wei Xiong;Cong Shen;Jing Yang
中科院分区：
文献类型：
--
作者：
Chengshuai Shi;Wei Xiong;Cong Shen;Jing Yang
尽管近年来分散式多玩家多武装土匪（MP-MAB）问题的重大利益和许多进展，在异构MP-MAB设置的自然集中下界的遗憾差距仍然是开放的。在本文中，我们提出了BEACON --具有自适应通信的批处理探索--来缩小这一差距。BEACON在隐式通信和有效探索方面做出了新的贡献，实现了这一目标。对于前者，我们提出了一种新的自适应差分通信（ADC）的设计，显着提高了隐式通信效率。对于后者，一个精心制作的批量勘探计划的开发，使合并的组合置信上限（CUCB）的原则。然后，我们将现有的线性奖励MP-MAB问题，其中系统奖励总是单独收集的奖励的总和，一个新的MP-MAB问题，其中系统奖励是一个一般的（非线性）功能的个人奖励。我们扩展了BEACON来解决这个问题，并证明了一个对数遗憾。BEACON桥梁组合MAB（CMAB）和MP-MAB，在MAB的两个很大程度上脱节的领域的算法设计和遗憾分析，本文的结果表明，这种以前被忽视的连接是值得进一步研究。
Despite the significant interests and many progresses in decentralized multi-player multi-armed bandits (MP-MAB) problems in recent years, the regret gap to the natural centralized lower bound in the heterogeneous MP-MAB setting remains open. In this paper, we propose BEACON -- Batched Exploration with Adaptive COmmunicatioN -- that closes this gap. BEACON accomplishes this goal with novel contributions in implicit communication and efficient exploration. For the former, we propose a novel adaptive differential communication (ADC) design that significantly improves the implicit communication efficiency. For the latter, a carefully crafted batched exploration scheme is developed to enable incorporation of the combinatorial upper confidence bound (CUCB) principle. We then generalize the existing linear-reward MP-MAB problems, where the system reward is always the sum of individually collected rewards, to a new MP-MAB problem where the system reward is a general (nonlinear) function of individual rewards. We extend BEACON to solve this problem and prove a logarithmic regret. BEACON bridges the algorithm design and regret analysis of combinatorial MAB (CMAB) and MP-MAB, two largely disjointed areas in MAB, and the results in this paper suggest that this previously ignored connection is worth further investigation.