# Multi-Player Bandits: A Trekking Approach

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2018.

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

- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2306.05998/) (2023)
- [Representation Learning for Context-Dependent Decision-Making](https://mlsanity.com/paper/2205.05820/) (2022)
- [United We Stand: Decentralized Multi-Agent Planning With Attrition](https://mlsanity.com/paper/2407.08254/) (2024)
- [Modelling Cournot Games as Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2201.01182/) (2022)
- [Exploiting Side Information for Improved Online Learning Algorithms in Wireless Networks](https://mlsanity.com/paper/2202.11699/) (2022)
- [Sequential Decision Problems with Weak Feedback](https://mlsanity.com/paper/2212.11603/) (2022)
- [Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities](https://mlsanity.com/paper/2408.10865/) (2024)

## Abstract (arXiv)

We study stochastic multi-armed bandits with many players. The players do not know the number of players, cannot communicate with each other and if multiple players select a common arm they collide and none of them receive any reward. We consider the static scenario, where the number of players remains fixed, and the dynamic scenario, where the players enter and leave at any time. We provide algorithms based on a novel `trekking approach' that guarantees constant regret for the static case and sub-linear regret for the dynamic case with high probability. The trekking approach eliminates the need to estimate the number of players resulting in fewer collisions and improved regret performance compared to the state-of-the-art algorithms. We also develop an epoch-less algorithm that eliminates any requirement of time synchronization across the players provided each player can detect the presence of other players on an arm. We validate our theoretical guarantees using simulation based and real test-bed based experiments.