SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
复制标题
SIC-MMAB：同步涉及多人多臂强盗中的通信
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Vianney Perchet
中科院分区：
文献类型：
--
作者：
Etienne Boursier;Vianney Perchet
在认知无线电网络的激励下，我们考虑了随机多人多臂强盗问题，即多个玩家同时拉动手臂，如果其中一个手臂在同一阶段被多个玩家拉动，则会发生碰撞。我们提出了一种去中心化算法，它实现了与中心化算法相同的性能，这与该问题的现有下界相矛盾。这可以通过“破解”标准模型来实现，即在玩家之间构建一个通信协议，故意强制冲突，允许他们以微不足道的成本共享信息。这促使引入不需要感应的更适当的动态设置，在这种情况下，类似的通信协议不再可能存在。然而，我们证明了使用新算法仍然可以实现该模型的后悔率的对数增长。
Motivated by cognitive radio networks, we consider the stochastic multiplayer multi-armed bandit problem, where several players pull arms simultaneously and collisions occur if one of them is pulled by several players at the same stage. We present a decentralized algorithm that achieves the same performance as a centralized one, contradicting the existing lower bounds for that problem. This is possible by "hacking" the standard model by constructing a communication protocol between players that deliberately enforces collisions, allowing them to share their information at a negligible cost. This motivates the introduction of a more appropriate dynamic setting without sensing, where similar communication protocols are no longer possible. However, we show that the logarithmic growth of the regret is still achievable for this model with a new algorithm.