# Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions

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

## Key facts

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

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

- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [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)
- [Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings](https://mlsanity.com/paper/1807.00491/) (2018)
- [Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without](https://mlsanity.com/paper/1904.12233/) (2019)
- [Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions](https://mlsanity.com/paper/2011.03896/) (2020)
- [Multi-Player Bandits: The Adversarial Case](https://mlsanity.com/paper/1902.08036/) (2019)
- [Coordination without communication: optimal regret in two players multi-armed bandits](https://mlsanity.com/paper/2002.07596/) (2020)
- [Multi-User MABs with User Dependent Rewards for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1910.09091/) (2019)
- [Multi-User Multi-Armed Bandits for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1807.00867/) (2018)
- [On No-Sensing Adversarial Multi-player Multi-armed Bandits with Collision Communications](https://mlsanity.com/paper/2011.01090/) (2020)

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

- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Fast Change Identification in Multi-Play Bandits and its Applications in Wireless Networks](https://mlsanity.com/paper/2205.10366/) (2022)
- [Decentralized Online Learning in Task Assignment Games for Mobile Crowdsensing](https://mlsanity.com/paper/2309.10594/) (2023)
- [Randomness is sometimes necessary for coordination](https://mlsanity.com/paper/2605.06825/) (2026)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)
- [PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators](https://mlsanity.com/paper/2403.15524/) (2024)
- [Decentralized Asynchronous Multi-player Bandits](https://mlsanity.com/paper/2509.25824/) (2025)
- [Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry](https://mlsanity.com/paper/2608.10529/) (2026)

## Abstract (arXiv)

We study a new stochastic multi-player multi-armed bandits (MP-MAB) problem, where the reward distribution changes if a collision occurs on the arm. Existing literature always assumes a zero reward for involved players if collision happens, but for applications such as cognitive radio, the more realistic scenario is that collision reduces the mean reward but not necessarily to zero. We focus on the more practical no-sensing setting where players do not perceive collisions directly, and propose the Error-Correction Collision Communication (EC3) algorithm that models implicit communication as a reliable communication over noisy channel problem, for which random coding error exponent is used to establish the optimal regret that no communication protocol can beat. Finally, optimizing the tradeoff between code length and decoding error rate leads to a regret that approaches the centralized MP-MAB regret, which represents a natural lower bound. Experiments with practical error-correction codes on both synthetic and real-world datasets demonstrate the superiority of EC3. In particular, the results show that the choice of coding schemes has a profound impact on the regret performance.