# Constant or logarithmic regret in asynchronous multiplayer bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 52 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [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)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [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)
- [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)
- [Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings](https://mlsanity.com/paper/1807.00491/) (2018)
- [Selfish Robustness and Equilibria in Multi-Player Bandits](https://mlsanity.com/paper/2002.01197/) (2020)
- [An adaptive stochastic optimization algorithm for resource allocation](https://mlsanity.com/paper/1902.04376/) (2019)
- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Multi-User MABs with User Dependent Rewards for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1910.09091/) (2019)
- [Combinatorial Multi-armed Bandits for Resource Allocation](https://mlsanity.com/paper/2105.04373/) (2021)
- [Multi-User Multi-Armed Bandits for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1807.00867/) (2018)
- [Stability and Learning in Strategic Queuing Systems](https://mlsanity.com/paper/2003.07009/) (2020)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Distributed learning in congested environments with partial information](https://mlsanity.com/paper/2103.15901/) (2021)

## Abstract (arXiv)

Multiplayer bandits have recently been extensively studied because of their application to cognitive radio networks. While the literature mostly considers synchronous players, radio networks (e.g. for IoT) tend to have asynchronous devices. This motivates the harder, asynchronous multiplayer bandits problem, which was first tackled with an explore-then-commit (ETC) algorithm (see Dakdouk, 2022), with a regret upper-bound in O(T^frac23). Before even considering decentralization, understanding the centralized case was still a challenge as it was unknown whether getting a regret smaller than Omega(T^frac23) was possible. We answer positively this question, as a natural extension of UCB exhibits a O(√Tlog(T)) minimax regret. More importantly, we introduce Cautious Greedy, a centralized algorithm that yields constant instance-dependent regret if the optimal policy assigns at least one player on each arm (a situation that is proved to occur when arm means are close enough). Otherwise, its regret increases as the sum of log(T) over some sub-optimality gaps. We provide lower bounds showing that Cautious Greedy is optimal in the data-dependent terms. Therefore, we set up a strong baseline for asynchronous multiplayer bandits and suggest that learning the optimal policy in this problem might be easier than thought, at least with centralization.