# Multiplayer bandits without observing collision information

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2018.

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

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets](https://mlsanity.com/paper/2206.02344/) (2022)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit](https://mlsanity.com/paper/2111.04873/) (2021)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information](https://mlsanity.com/paper/2102.10200/) (2021)
- [The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication](https://mlsanity.com/paper/2202.09653/) (2022)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Multi-Player Bandits Robust to Adversarial Collisions](https://mlsanity.com/paper/2211.07817/) (2022)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Meet Me at the Arm: The Cooperative Multi-Armed Bandits Problem with Shareable Arms](https://mlsanity.com/paper/2506.10127/) (2025)
- [Fair Distributed Cooperative Bandit Learning on Networks for Intelligent Internet of Things Systems (Technical Report)](https://mlsanity.com/paper/2403.11603/) (2024)
- [PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators](https://mlsanity.com/paper/2403.15524/) (2024)
- [Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities](https://mlsanity.com/paper/2408.10865/) (2024)
- [Collaborative Min-Max Regret in Grouped Multi-Armed Bandits](https://mlsanity.com/paper/2506.10313/) (2025)
- [Decentralized Asynchronous Multi-player Bandits](https://mlsanity.com/paper/2509.25824/) (2025)
- [DCM Bandits: Multiplayer Information Asymmetric Cascading Bandits for Multiple Clicks](https://mlsanity.com/paper/2608.11873/) (2026)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

We study multiplayer stochastic multi-armed bandit problems in which the players cannot communicate and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward. We consider two feedback models: a model in which the players can observe whether a collision has occurred and a more difficult setup when no collision information is available. We give the first theoretical guarantees for the second model: an algorithm with a logarithmic regret, and an algorithm with a square-root regret type that does not depend on the gaps between the means. For the first model, we give the first square-root regret bounds that do not depend on the gaps. Building on these ideas, we also give an algorithm for reaching approximate Nash equilibria quickly in stochastic anti-coordination games.