# Multi-Player Bandits Robust to Adversarial Collisions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 15 Nov 2022.

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

- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Decentralized Multi-player Multi-armed Bandits with No Collision Information](https://mlsanity.com/paper/2003.00162/) (2020)
- [Concurrent bandits and cognitive radio networks](https://mlsanity.com/paper/1404.5421/) (2014)
- [Multiplayer bandits without observing collision information](https://mlsanity.com/paper/1808.08416/) (2018)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without](https://mlsanity.com/paper/1904.12233/) (2019)
- [Selfish Robustness and Equilibria in Multi-Player Bandits](https://mlsanity.com/paper/2002.01197/) (2020)
- [Multi-Player Bandits: The Adversarial Case](https://mlsanity.com/paper/1902.08036/) (2019)
- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Multi-User MABs with User Dependent Rewards for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1910.09091/) (2019)
- [Learning to Coordinate in a Decentralized Cognitive Radio Network in Presence of Jammers](https://mlsanity.com/paper/1803.06810/) (2018)

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

- [Decentralized Asynchronous Multi-player Bandits](https://mlsanity.com/paper/2509.25824/) (2025)

## Abstract (arXiv)

Motivated by cognitive radios, stochastic Multi-Player Multi-Armed Bandits has been extensively studied in recent years. In this setting, each player pulls an arm, and receives a reward corresponding to the arm if there is no collision, namely the arm was selected by one single player. Otherwise, the player receives no reward if collision occurs. In this paper, we consider the presence of malicious players (or attackers) who obstruct the cooperative players (or defenders) from maximizing their rewards, by deliberately colliding with them. We provide the first decentralized and robust algorithm RESYNC for defenders whose performance deteriorates gracefully as tildeO(C) as the number of collisions C from the attackers increases. We show that this algorithm is order-optimal by proving a lower bound which scales as Omega(C). This algorithm is agnostic to the algorithm used by the attackers and agnostic to the number of collisions C faced from attackers.