# On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2015.

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

- [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)
- [Online Learning for Cooperative Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2109.03818/) (2021)
- [Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication](https://mlsanity.com/paper/2311.06210/) (2023)
- [Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approach](https://mlsanity.com/paper/2112.11818/) (2021)
- [SINR-Aware Deep Reinforcement Learning for Distributed Dynamic Channel Allocation in Cognitive Interference Networks](https://mlsanity.com/paper/2402.17773/) (2024)
- [Learning to Control Unknown Strongly Monotone Games](https://mlsanity.com/paper/2407.00575/) (2024)
- [Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2111.10933/) (2021)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Distributed Stochastic Bandit Learning with Delayed Context Observation](https://mlsanity.com/paper/2207.14391/) (2022)
- [Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2306.05998/) (2023)
- [Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks](https://mlsanity.com/paper/2111.12581/) (2021)
- [Deterministic Sequencing of Exploration and Exploitation for Reinforcement Learning](https://mlsanity.com/paper/2209.05408/) (2022)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliability](https://mlsanity.com/paper/2201.12482/) (2022)
- [Exploiting Side Information for Improved Online Learning Algorithms in Wireless Networks](https://mlsanity.com/paper/2202.11699/) (2022)
- [Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits](https://mlsanity.com/paper/2306.04498/) (2023)
- [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)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

We consider the problem of learning in single-player and multiplayer multiarmed bandit models. Bandit problems are classes of online learning problems that capture exploration versus exploitation tradeoffs. In a multiarmed bandit model, players can pick among many arms, and each play of an arm generates an i.i.d. reward from an unknown distribution. The objective is to design a policy that maximizes the expected reward over a time horizon for a single player setting and the sum of expected rewards for the multiplayer setting. In the multiplayer setting, arms may give different rewards to different players. There is no separate channel for coordination among the players. Any attempt at communication is costly and adds to regret. We propose two decentralizable policies, tt E3 (tt E-tt cubed) and tt E3-tt TS, that can be used in both single player and multiplayer settings. These policies are shown to yield expected regret that grows at most as O(log1+ε T). It is well known that log T is the lower bound on the rate of growth of regret even in a centralized case. The proposed algorithms improve on prior work where regret grew at O(log2 T). More fundamentally, these policies address the question of additional cost incurred in decentralized online learning, suggesting that there is at most an ε-factor cost in terms of order of regret. This solves a problem of relevance in many domains and had been open for a while.