# Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits

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

## Key facts

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

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

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Private and Byzantine-Proof Cooperative Decision-Making](https://mlsanity.com/paper/2205.14174/) (2022)
- [When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits](https://mlsanity.com/paper/2110.04396/) (2021)
- [Doubly Adversarial Federated Bandits](https://mlsanity.com/paper/2301.09223/) (2023)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2106.04207/) (2021)
- [Cooperative Online Learning with Feedback Graphs](https://mlsanity.com/paper/2106.04982/) (2021)
- [Cooperative Online Learning in Stochastic and Adversarial MDPs](https://mlsanity.com/paper/2201.13170/) (2022)
- [On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.17154/) (2022)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [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)
- [Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks](https://mlsanity.com/paper/2111.12581/) (2021)
- [Multitask Online Learning: Listen to the Neighborhood Buzz](https://mlsanity.com/paper/2310.17385/) (2023)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Bandits](https://mlsanity.com/paper/2410.23867/) (2024)
- [Robust Multi-Agent Bandits Over Undirected Graphs](https://mlsanity.com/paper/2203.00076/) (2022)
- [Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits](https://mlsanity.com/paper/2306.04498/) (2023)
- [Simple Opinion Dynamics for No-Regret Learning](https://mlsanity.com/paper/2306.08670/) (2023)
- [Collaborating in Multi-Armed Bandits with Strategic Agents](https://mlsanity.com/paper/2605.13145/) (2026)

## Abstract (arXiv)

We study agents communicating over an underlying network by exchanging messages, in order to optimize their individual regret in a common nonstochastic multi-armed bandit problem. We derive regret minimization algorithms that guarantee for each agent v an individual expected regret of widetildeOleft(√left(1+fracKleft|Nleft(vright)right|right)Tright), where T is the number of time steps, K is the number of actions and Nleft(vright) is the set of neighbors of agent v in the communication graph. We present algorithms both for the case that the communication graph is known to all the agents, and for the case that the graph is unknown. When the graph is unknown, each agent knows only the set of its neighbors and an upper bound on the total number of agents. The individual regret between the models differs only by a logarithmic factor. Our work resolves an open problem from [Cesa-Bianchi et al., 2019b].