Multi-Player Bandits -- a Musical Chairs Approach
This addresses resource allocation in decentralized systems like cognitive radio networks, offering a novel solution to a known bottleneck with practical implications.
The paper tackles the stochastic multi-armed bandit problem with multiple players and collisions, motivated by cognitive radio networks, and presents communication-free algorithms (Musical Chairs and Dynamic Musical Chairs) that achieve constant regret with high probability and sublinear regret for dynamic player settings, without prior knowledge of player numbers.
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.