# Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 8 Aug 2023.

## Builds on (most cited first, 18 of 18)

- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Distributed Bandits with Heterogeneous Agents](https://mlsanity.com/paper/2201.09353/) (2022)
- [When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits](https://mlsanity.com/paper/2110.04396/) (2021)
- [Decentralized Exploration in Multi-Armed Bandits -- Extended version](https://mlsanity.com/paper/1811.07763/) (2018)

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

- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [Distributed Algorithms for Multi-Agent Multi-Armed Bandits with Collision](https://mlsanity.com/paper/2510.06683/) (2025)

## Abstract (arXiv)

Recently, there has been extensive study of cooperative multi-agent multi-armed bandits where a set of distributed agents cooperatively play the same multi-armed bandit game. The goal is to develop bandit algorithms with the optimal group and individual regrets and low communication between agents. The prior work tackled this problem using two paradigms: leader-follower and fully distributed algorithms. Prior algorithms in both paradigms achieve the optimal group regret. The leader-follower algorithms achieve constant communication costs but fail to achieve optimal individual regrets. The state-of-the-art fully distributed algorithms achieve optimal individual regrets but fail to achieve constant communication costs. This paper presents a simple yet effective communication policy and integrates it into a learning algorithm for cooperative bandits. Our algorithm achieves the best of both paradigms: optimal individual regret and constant communication costs.