Multiplayer bandits without observing collision information

Understand

We study multiplayer stochastic multi-armed bandit problems in which the players cannot communicate and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward.

• We consider two feedback models: a model in which the players can observe whether a collision has occurred and a more difficult setup when no collision information is available.
• We give the first theoretical guarantees for the second model: an algorithm with a logarithmic regret, and an algorithm with a square-root regret type that does not depend on the gaps between the means.
• For the first model, we give the first square-root regret bounds that do not depend on the gaps.