text: 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, efficient algorithm that combines the idea of leveraging forced collisions for implicit communication and that of performing matching eliminations. We give a finite-time analysis of our algorithm, bounding its regret by O((log T)^ 1+ ) for any fixed >0. If the optimal assignment of players to arms is unique, we further show that it attains the optimal O(log(T)) regret, solving an open question raised at NeurIPS 2018.
  @cite_16: We consider a multi-armed bandit game where N players compete for M arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed or Markovian. When two or more players choose the same arm, they all receive zero reward. Performance is measured using the expected sum of regrets, compared to optimal assignment of arms to players. We assume that each player only knows her actions and the reward she received each turn. Players cannot observe the actions of other players, and no communication between players is possible. We present a distributed algorithm and prove that it achieves an expected sum of regrets of near-O ( T ). This is the first algorithm to achieve a near order optimal regret in this fully distributed scenario. All other works have assumed that either all players have the same vector of expected rewards or that communication between players is possible.
summary: Our problem can be viewed as a challenging extension of two complex multi-armed bandit problems. First, relaxing the need for decentralization, i.e. when a central controller is requested to jointly select @math , the problem coincides with a combinatorial bandit problem with semi-bandit feedback, as explained in , where we review the achievable regret in the centralized setting. Second, the particular case of a common utility for all players, i.e. @math for all @math , has been studied extensively, and we review in the achievable regret in this multi-player bandit problem, presenting in particular some inspiring ideas to design algorithms for our more general problem. Finally in we discuss the Game-of-Thrones algorithm of @cite_16 , which is our only competitor in the fully distributed setting considered in this paper.