# Game of Thrones: Fully Distributed Learning for Multi-Player Bandits

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

## Key facts

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

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

- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [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)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Distributed Linear Bandits under Communication Constraints](https://mlsanity.com/paper/2211.02212/) (2022)
- [Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks](https://mlsanity.com/paper/2111.12581/) (2021)
- [Logit-Q Dynamics for Efficient Learning in Stochastic Teams](https://mlsanity.com/paper/2302.09806/) (2023)
- [Optimistic Thompson Sampling for No-Regret Learning in Unknown Games](https://mlsanity.com/paper/2402.09456/) (2024)
- [Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits](https://mlsanity.com/paper/2306.04498/) (2023)
- [PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators](https://mlsanity.com/paper/2403.15524/) (2024)
- [Distributed Algorithms for Multi-Agent Multi-Armed Bandits with Collision](https://mlsanity.com/paper/2510.06683/) (2025)
- [Distributed Learning in Markovian Restless Bandits over Interference Graphs for Stable Spectrum Sharing](https://mlsanity.com/paper/2512.17161/) (2025)

## Abstract (arXiv)

We consider an N-player multi-armed bandit game where each player chooses one out of M arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed or Markovian. When two or more players choose the same arm, they all receive zero reward. Performance is measured using the expected sum of regrets, compared with an optimal assignment of arms to players that maximizes the sum of expected rewards. We assume that each player only knows her actions and the reward she received each turn. Players cannot observe the actions of other players, and no communication between players is possible. We present a distributed algorithm and prove that it achieves an expected sum of regrets of near-Oleft(log Tright). This is the first algorithm to achieve a near order optimal regret in this fully distributed scenario. All other works have assumed that either all players have the same vector of expected rewards or that communication between players is possible.