# Coordination without communication: optimal regret in two players multi-armed bandits

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

## Key facts

- Cited by 11 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 14 Feb 2020.

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

- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit](https://mlsanity.com/paper/2111.04873/) (2021)
- [A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information](https://mlsanity.com/paper/2102.10200/) (2021)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)
- [The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication](https://mlsanity.com/paper/2202.09653/) (2022)
- [Simple Opinion Dynamics for No-Regret Learning](https://mlsanity.com/paper/2306.08670/) (2023)
- [Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities](https://mlsanity.com/paper/2408.10865/) (2024)
- [Collaborative Min-Max Regret in Grouped Multi-Armed Bandits](https://mlsanity.com/paper/2506.10313/) (2025)

## Abstract (arXiv)

We consider two agents playing simultaneously the same stochastic three-armed bandit problem. The two agents are cooperating but they cannot communicate. We propose a strategy with no collisions at all between the players (with very high probability), and with near-optimal regret O(√T log(T)). We also argue that the extra logarithmic term √log(T) should be necessary by proving a lower bound for a full information variant of the problem.