# Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 16 references that are in the map.
- First posted on arXiv 24 Mar 2021.

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

- [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)
- [Multiplayer bandits without observing collision information](https://mlsanity.com/paper/1808.08416/) (2018)
- [Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions](https://mlsanity.com/paper/2011.03896/) (2020)
- [Decentralized Heterogeneous Multi-Player Multi-Armed Bandits with Non-Zero Rewards on Collisions](https://mlsanity.com/paper/1910.09089/) (2019)

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

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [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)
- [The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication](https://mlsanity.com/paper/2202.09653/) (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)
- [Constant or logarithmic regret in asynchronous multiplayer bandits](https://mlsanity.com/paper/2305.19691/) (2023)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (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)

## Abstract (arXiv)

We propose a novel algorithm for multi-player multi-armed bandits without collision sensing information. Our algorithm circumvents two problems shared by all state-of-the-art algorithms: it does not need as an input a lower bound on the minimal expected reward of an arm, and its performance does not scale inversely proportionally to the minimal expected reward. We prove a theoretical regret upper bound to justify these claims. We complement our theoretical results with numerical experiments, showing that the proposed algorithm outperforms state-of-the-art in practice as well.