# Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 8 Jun 2021.

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

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Decentralized Multi-player Multi-armed Bandits with No Collision Information](https://mlsanity.com/paper/2003.00162/) (2020)
- [Stochastic Linear Optimization with Adversarial Corruption](https://mlsanity.com/paper/1909.02109/) (2019)
- [Cooperative Online Learning: Keeping your Neighbors Updated](https://mlsanity.com/paper/1901.08082/) (2019)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits](https://mlsanity.com/paper/2002.09808/) (2020)
- [Multi-Player Bandits: The Adversarial Case](https://mlsanity.com/paper/1902.08036/) (2019)

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

- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)
- [A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond](https://mlsanity.com/paper/2502.07514/) (2025)

## Abstract (arXiv)

We study the problem of stochastic bandits with adversarial corruptions in the cooperative multi-agent setting, where V agents interact with a common K-armed bandit problem, and each pair of agents can communicate with each other to expedite the learning process. In the problem, the rewards are independently sampled from distributions across all agents and rounds, but they may be corrupted by an adversary. Our goal is to minimize both the overall regret and communication cost across all agents. We first show that an additive term of corruption is unavoidable for any algorithm in this problem. Then, we propose a new algorithm that is agnostic to the level of corruption. Our algorithm not only achieves near-optimal regret in the stochastic setting, but also obtains a regret with an additive term of corruption in the corrupted setting, while maintaining efficient communication. The algorithm is also applicable for the single-agent corruption problem, and achieves a high probability regret that removes the multiplicative dependence of K on corruption level. Our result of the single-agent case resolves an open question from Gupta et al. [2019].