# Robust Multi-Agent Bandits Over Undirected Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 12 references that are in the map.
- First posted on arXiv 28 Feb 2022.

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

- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [Robust Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.03812/) (2020)

## Abstract (arXiv)

We consider a multi-agent multi-armed bandit setting in which n honest agents collaborate over a network to minimize regret but m malicious agents can disrupt learning arbitrarily. Assuming the network is the complete graph, existing algorithms incur O( (m + K/n) log (T) / Delta ) regret in this setting, where K is the number of arms and Delta is the arm gap. For m ll K, this improves over the single-agent baseline regret of O(Klog(T)/Delta). In this work, we show the situation is murkier beyond the case of a complete graph. In particular, we prove that if the state-of-the-art algorithm is used on the undirected line graph, honest agents can suffer (nearly) linear regret until time is doubly exponential in K and n. In light of this negative result, we propose a new algorithm for which the i-th agent has regret O( ( dmal(i) + K/n) log(T)/Delta) on any connected and undirected graph, where dmal(i) is the number of i's neighbors who are malicious. Thus, we generalize existing regret bounds beyond the complete graph (where dmal(i) = m), and show the effect of malicious agents is entirely local (in the sense that only the dmal(i) malicious agents directly connected to i affect its long-term regret).