# Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without

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

## Key facts

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

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

- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (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)
- [Distributed Bandits with Heterogeneous Agents](https://mlsanity.com/paper/2201.09353/) (2022)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit](https://mlsanity.com/paper/2111.04873/) (2021)
- [The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication](https://mlsanity.com/paper/2202.09653/) (2022)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Multi-Player Bandits Robust to Adversarial Collisions](https://mlsanity.com/paper/2211.07817/) (2022)
- [Communication Bounds for the Distributed Experts Problem](https://mlsanity.com/paper/2501.03132/) (2025)
- [Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliability](https://mlsanity.com/paper/2201.12482/) (2022)
- [Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits](https://mlsanity.com/paper/2306.04498/) (2023)

## Abstract (arXiv)

We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication at all between the players, and furthermore when two (or more) players select the same action this results in a maximal loss. We prove the first √T-type regret guarantee for this problem, under the feedback model where collisions are announced to the colliding players. Such a bound was not known even for the simpler stochastic version. We also prove the first sublinear guarantee for the feedback model where collision information is not available, namely T^1-frac12m where m is the number of players.