# An Optimal Algorithm for Multiplayer Multi-Armed Bandits

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

## Key facts

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

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

- [Multiplayer Information Asymmetric Bandits in Metric Spaces](https://mlsanity.com/paper/2503.08004/) (2025)
- [Multiplayer Information Asymmetric Contextual Bandits](https://mlsanity.com/paper/2503.08961/) (2025)

## Abstract (arXiv)

The paper addresses the Multiplayer Multi-Armed Bandit (MMAB) problem, where M decision makers or players collaborate to maximize their cumulative reward. When several players select the same arm, a collision occurs and no reward is collected on this arm. Players involved in a collision are informed about this collision. We present DPE (Decentralized Parsimonious Exploration), a decentralized algorithm that achieves the same regret as that obtained by an optimal centralized algorithm. Our algorithm has better regret guarantees than the state-of-the-art algorithm SIC-MMAB citeboursier2019. As in SIC-MMAB, players communicate through collisions only. An additional important advantage of DPE is that it requires very little communication. Specifically, the expected number of rounds where players use collisions to communicate is finite.