# Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 13 Oct 2026.

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

- [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)
- [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)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings](https://mlsanity.com/paper/1807.00491/) (2018)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Multi-user Communication Networks: A Coordinated Multi-armed Bandit Approach](https://mlsanity.com/paper/1808.04875/) (2018)

## Abstract (arXiv)

Motivated by applications to cognitive radio networks, multi-player multi-armed bandits (MMAB) have attracted considerable attention in recent years. The asynchronous variant, in which players are active only at a fraction of timesteps, better reflects real-world decentralized networks, where devices are not permanently active. Despite its practical relevance, this setting remains relatively understudied. Existing work on asynchronous MMAB has focused on homogeneous players, who share the same activation probability, a setting in which the optimal centralized allocation can be easily characterized. In contrast, efficiently computing the optimal allocation in the heterogeneous setting, where players have different activation probabilities, has remained an open problem. In this work, we investigate this problem and first establish its NP-hardness. We then turn to the greedy algorithm, which runs in polynomial time, and prove that it achieves a frac1e-approximation of the optimal allocation. Furthermore, when players are processed in decreasing order of their activation probabilities, the approximation guarantee improves to frac1√e. Overall, our results establish the greedy algorithm as an efficient approximation to the optimal allocation, providing a practical oracle baseline for the design of online algorithms for heterogeneous asynchronous multi-player bandits.