We consider a variant of the stochastic multi-armed bandit problem, where multiple players simultaneously choose from the same set of arms and may collide, receiving no reward. This setting has been motivated by problems arising in cognitive radio networks, and is especially challenging under the realistic assumption that communication between players is limited. We provide a communication-free algorithm (Musical Chairs) which attains constant regret with high probability, as well as a sublinear-regret, communication-free algorithm (Dynamic Musical Chairs) for the more difficult setting of players dynamically entering and leaving throughout the game. Moreover, both algorithms do not require prior knowledge of the number of players. To the best of our knowledge, these are the first communication-free algorithms with these types of formal guarantees. We also rigorously compare our algorithms to previous works, and complement our theoretical findings with experiments.

本研究提出了两种无需通信的算法Musical Chairs和Dynamic Musical Chairs来解决多人博弈中的多臂赌博机问题，其中玩家可能发生碰撞，但不会获得奖励。这些算法有着恒定和次线性的遗憾率，且不需要先验知识，为这类问题解决提供了理论保证。

多人博弈 -- 音乐椅子方法