# Decentralized Heterogeneous Multi-Player Multi-Armed Bandits with Non-Zero Rewards on Collisions

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2019.

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

- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms: Learning Algorithms & Applications](https://mlsanity.com/paper/2204.13502/) (2022)
- [Distributed Bandits with Heterogeneous Agents](https://mlsanity.com/paper/2201.09353/) (2022)
- [Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms](https://mlsanity.com/paper/2206.08776/) (2022)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approach](https://mlsanity.com/paper/2112.11818/) (2021)
- [Decentralized Adversarial Training over Graphs](https://mlsanity.com/paper/2303.13326/) (2023)
- [Decentralized Online Learning in Task Assignment Games for Mobile Crowdsensing](https://mlsanity.com/paper/2309.10594/) (2023)
- [PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators](https://mlsanity.com/paper/2403.15524/) (2024)
- [Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approach](https://mlsanity.com/paper/2605.27076/) (2026)

## Abstract (arXiv)

We consider a fully decentralized multi-player stochastic multi-armed bandit setting where the players cannot communicate with each other and can observe only their own actions and rewards. The environment may appear differently to different players, textiti.e., the reward distributions for a given arm are heterogeneous across players. In the case of a collision (when more than one player plays the same arm), we allow for the colliding players to receive non-zero rewards. The time-horizon T for which the arms are played is not known to the players. Within this setup, where the number of players is allowed to be greater than the number of arms, we present a policy that achieves near order-optimal expected regret of order O(log1 + δ T) for some 0 < δ < 1 over a time-horizon of duration T. This paper is accepted at IEEE Transactions on Information Theory.