# Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2020.

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

- [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)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets](https://mlsanity.com/paper/2206.02344/) (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)
- [Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility](https://mlsanity.com/paper/2401.01528/) (2024)
- [An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit](https://mlsanity.com/paper/2111.04873/) (2021)
- [Cooperative Online Learning in Stochastic and Adversarial MDPs](https://mlsanity.com/paper/2201.13170/) (2022)
- [The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication](https://mlsanity.com/paper/2202.09653/) (2022)
- [Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds](https://mlsanity.com/paper/2301.11802/) (2023)

## Abstract (arXiv)

We consider the cooperative multi-player version of the stochastic multi-armed bandit problem. We study the regime where the players cannot communicate but have access to shared randomness. In prior work by the first two authors, a strategy for this regime was constructed for two players and three arms, with regret tildeO(√T), and with no collisions at all between the players (with very high probability). In this paper we show that these properties (near-optimal regret and no collisions at all) are achievable for any number of players and arms. At a high level, the previous strategy heavily relied on a 2-dimensional geometric intuition that was difficult to generalize in higher dimensions, while here we take a more combinatorial route to build the new strategy.