# A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 14 references that are in the map.
- First posted on arXiv 19 Feb 2021.

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

- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [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)
- [Coordination without communication: optimal regret in two players multi-armed bandits](https://mlsanity.com/paper/2002.07596/) (2020)

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

- [Decentralized Asynchronous Multi-player Bandits](https://mlsanity.com/paper/2509.25824/) (2025)
- [Bandit Learning in General Open Multi-agent Systems](https://mlsanity.com/paper/2605.06202/) (2026)

## Abstract (arXiv)

Motivated by applications in cognitive radio networks, we consider the decentralized multi-player multi-armed bandit problem, without collision nor sensing information. We propose Randomized Selfish KL-UCB, an algorithm with very low computational complexity, inspired by the Selfish KL-UCB algorithm, which has been abandoned as it provably performs sub-optimally in some cases. We subject Randomized Selfish KL-UCB to extensive numerical experiments showing that it far outperforms state-of-the-art algorithms in almost all environments, sometimes by several orders of magnitude, and without the additional knowledge required by state-of-the-art algorithms. We also emphasize the potential of this algorithm for the more realistic dynamic setting, and support our claims with further experiments. We believe that the low complexity and high performance of Randomized Selfish KL-UCB makes it the most suitable for implementation in practical systems amongst known algorithms.