# Cooperative Multi-Agent Bandits with Heavy Tails

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

## Key facts

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

## Built on by (most cited first, 30 of 31)

- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Trustworthy Distributed AI Systems: Robustness, Privacy, and Governance](https://mlsanity.com/paper/2402.01096/) (2024)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [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)
- [Differentially Private Linear Bandits with Partial Distributed Feedback](https://mlsanity.com/paper/2207.05827/) (2022)
- [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)
- [Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication](https://mlsanity.com/paper/2110.07392/) (2021)
- [Robust Online and Distributed Mean Estimation Under Adversarial Data Corruption](https://mlsanity.com/paper/2209.09624/) (2022)
- [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)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [Asymptotic Optimality for Decentralised Bandits](https://mlsanity.com/paper/2109.09427/) (2021)
- [Evolutionary Multi-Armed Bandits with Genetic Thompson Sampling](https://mlsanity.com/paper/2205.10113/) (2022)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Multi-Agent Bandit Learning through Heterogeneous Action Erasure Channels](https://mlsanity.com/paper/2312.14259/) (2023)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics](https://mlsanity.com/paper/2501.19239/) (2025)
- [QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Bandits](https://mlsanity.com/paper/2410.23867/) (2024)
- [Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds](https://mlsanity.com/paper/2411.12154/) (2024)
- [Amplifying Human Creativity and Problem Solving with AI Through Generative Collective Intelligence](https://mlsanity.com/paper/2505.19167/) (2025)
- [Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks](https://mlsanity.com/paper/2303.05445/) (2023)
- [Cooperative Thresholded Lasso for Sparse Linear Bandit](https://mlsanity.com/paper/2305.19161/) (2023)
- [Distributed Optimization via Kernelized Multi-armed Bandits](https://mlsanity.com/paper/2312.04719/) (2023)
- [Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities](https://mlsanity.com/paper/2408.10865/) (2024)
- [Estimating Causal Effects in Networks with Cluster-Based Bandits](https://mlsanity.com/paper/2505.04200/) (2025)
- [Collaborating in Multi-Armed Bandits with Strategic Agents](https://mlsanity.com/paper/2605.13145/) (2026)

## Abstract (arXiv)

We study the heavy-tailed stochastic bandit problem in the cooperative multi-agent setting, where a group of agents interact with a common bandit problem, while communicating on a network with delays. Existing algorithms for the stochastic bandit in this setting utilize confidence intervals arising from an averaging-based communication protocol known as~textitrunning consensus, that does not lend itself to robust estimation for heavy-tailed settings. We propose textscMP-UCB, a decentralized multi-agent algorithm for the cooperative stochastic bandit that incorporates robust estimation with a message-passing protocol. We prove optimal regret bounds for textscMP-UCB for several problem settings, and also demonstrate its superiority to existing methods. Furthermore, we establish the first lower bounds for the cooperative bandit problem, in addition to providing efficient algorithms for robust bandit estimation of location.