Multi-Player Bandits -- a Musical Chairs Approach
  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.
