  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.
Building on these ideas, we also give an algorithm for reaching approximate
Nash equilibria quickly in stochastic anti-coordination games.
