  We study a multiplayer stochastic multi-armed bandit problem in which 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 the
challenging heterogeneous setting, in which different arms may have different
means for different players, and propose a new and efficient algorithm that
combines the idea of leveraging forced collisions for implicit communication
and that of performing matching eliminations. We present a finite-time analysis
of our algorithm, giving the first sublinear minimax regret bound for this
problem, and prove that if the optimal assignment of players to arms is unique,
our algorithm attains the optimal $O(\ln(T))$ regret, solving an open question
raised at NeurIPS 2018.

Machine Learning;Machine Learning