# Byzantine-Resilient Decentralized Multi-Armed Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 87 references that are in the map.
- First posted on arXiv 11 Oct 2023.

## Builds on (most cited first, 30 of 39)

- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [BRIDGE: Byzantine-resilient Decentralized Gradient Descent](https://mlsanity.com/paper/1908.08098/) (2019)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning](https://mlsanity.com/paper/1708.08155/) (2017)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [Federated Recommendation System via Differential Privacy](https://mlsanity.com/paper/2005.06670/) (2020)
- [Byzantine-Resilient Decentralized Stochastic Optimization with Robust Aggregation Rules](https://mlsanity.com/paper/2206.04568/) (2022)
- [On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits](https://mlsanity.com/paper/1505.00553/) (2015)
- [Distributed Optimization Under Adversarial Nodes](https://mlsanity.com/paper/1606.08939/) (2016)
- [Robust Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.03812/) (2020)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack](https://mlsanity.com/paper/2002.07214/) (2020)
- [Byzantine-Robust Online and Offline Distributed Reinforcement Learning](https://mlsanity.com/paper/2206.00165/) (2022)
- [A Dynamic Observation Strategy for Multi-agent Multi-armed Bandit Problem](https://mlsanity.com/paper/2004.03793/) (2020)
- [When Are Linear Stochastic Bandits Attackable?](https://mlsanity.com/paper/2110.09008/) (2021)
- [Private and Byzantine-Proof Cooperative Decision-Making](https://mlsanity.com/paper/2205.14174/) (2022)

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

- [Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints](https://mlsanity.com/paper/2401.11563/) (2024)
- [Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2402.04417/) (2024)
- [Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits](https://mlsanity.com/paper/2601.11924/) (2026)

## Abstract (arXiv)

In decentralized cooperative multi-armed bandits (MAB), each agent observes a distinct stream of rewards, and seeks to exchange information with others to select a sequence of arms so as to minimize its regret. Agents in the cooperative setting can outperform a single agent running a MAB method such as Upper-Confidence Bound (UCB) independently. In this work, we study how to recover such salient behavior when an unknown fraction of the agents can be Byzantine, that is, communicate arbitrarily wrong information in the form of reward mean-estimates or confidence sets. This framework can be used to model attackers in computer networks, instigators of offensive content into recommender systems, or manipulators of financial markets. Our key contribution is the development of a fully decentralized resilient upper confidence bound (UCB) algorithm that fuses an information mixing step among agents with a truncation of inconsistent and extreme values. This truncation step enables us to establish that the performance of each normal agent is no worse than the classic single-agent UCB1 algorithm in terms of regret, and more importantly, the cumulative regret of all normal agents is strictly better than the non-cooperative case, provided that each agent has at least 3f+1 neighbors where f is the maximum possible Byzantine agents in each agent's neighborhood. Extensions to time-varying neighbor graphs, and minimax lower bounds are further established on the achievable regret. Experiments corroborate the merits of this framework in practice.