A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players

Abstract

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.

arXiv commentAISTATS2020

References in corpus (8)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Combinatorial Bandits Revisited
• What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
• Thompson Sampling for Combinatorial Semi-Bandits
• Game of Thrones: Fully Distributed Learning for Multi-Player Bandits
• Combinatorial semi-bandit with known covariance
• Multi-Player Bandits Revisited
• Multiplayer Multi-armed Bandits for Optimal Assignment in Heterogeneous Networks

Cited by in corpus (10)

• Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions
• SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
• Selfish Robustness and Equilibria in Multi-Player Bandits
• Multiplayer Multi-armed Bandits for Optimal Assignment in Heterogeneous Networks
• Decentralized Learning in Online Queuing Systems
• Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information
• Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks
• My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits
• Distributed learning in congested environments with partial information
• Constant or logarithmic regret in asynchronous multiplayer bandits