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

arXiv: https://arxiv.org/abs/1902.01239 · HTML: https://mlsanity.com/paper/1902.01239/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2019.

## Built on by (most cited first, 25 of 25)

- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms: Learning Algorithms & Applications](https://mlsanity.com/paper/2204.13502/) (2022)
- [Distributed Bandits with Heterogeneous Agents](https://mlsanity.com/paper/2201.09353/) (2022)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [Dynamic Spectrum Access using Stochastic Multi-User Bandits](https://mlsanity.com/paper/2101.04388/) (2021)
- [Collaborative Algorithms for Online Personalized Mean Estimation](https://mlsanity.com/paper/2208.11530/) (2022)
- [Learning to Control Unknown Strongly Monotone Games](https://mlsanity.com/paper/2407.00575/) (2024)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks](https://mlsanity.com/paper/2111.12581/) (2021)
- [Multi-Player Bandits Robust to Adversarial Collisions](https://mlsanity.com/paper/2211.07817/) (2022)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Constant or logarithmic regret in asynchronous multiplayer bandits](https://mlsanity.com/paper/2305.19691/) (2023)
- [Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits](https://mlsanity.com/paper/2306.04498/) (2023)
- [Distributed Optimization via Kernelized Multi-armed Bandits](https://mlsanity.com/paper/2312.04719/) (2023)
- [Optimal Regret Bounds for Collaborative Learning in Bandits](https://mlsanity.com/paper/2312.09674/) (2023)
- [Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities](https://mlsanity.com/paper/2408.10865/) (2024)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

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.