# Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 55 references that are in the map.
- First posted on arXiv 22 Nov 2021.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Multi-Armed Bandit Based Client Scheduling for Federated Learning](https://mlsanity.com/paper/2007.02315/) (2020)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Federated Recommendation System via Differential Privacy](https://mlsanity.com/paper/2005.06670/) (2020)
- [Concurrent bandits and cognitive radio networks](https://mlsanity.com/paper/1404.5421/) (2014)
- [Kernel Methods for Cooperative Multi-Agent Contextual Bandits](https://mlsanity.com/paper/2008.06220/) (2020)
- [On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits](https://mlsanity.com/paper/1505.00553/) (2015)
- [A Dynamic Observation Strategy for Multi-agent Multi-armed Bandit Problem](https://mlsanity.com/paper/2004.03793/) (2020)
- [Heterogeneous Explore-Exploit Strategies on Multi-Star Networks](https://mlsanity.com/paper/2009.01339/) (2020)

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

- [Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints](https://mlsanity.com/paper/2401.11563/) (2024)
- [Distributed Multi-Agent Bandits Over ErdHos-R'enyi Random Networks](https://mlsanity.com/paper/2510.22811/) (2025)
- [Pay to Learn, Share to Earn: Incentivized Federated Multi-Player Bandits](https://mlsanity.com/paper/2610.06062/) (2026)

## Abstract (arXiv)

This paper studies a decentralized homogeneous multi-armed bandit problem in a multi-agent network. The problem is simultaneously solved by N agents assuming they face a common set of M arms and share the same arms' reward distributions. Each agent can receive information only from its neighbors, where the neighbor relationships among the agents are described by a fixed graph. Two fully decentralized upper confidence bound (UCB) algorithms are proposed for undirected graphs, respectively based on the classic algorithm and the state-of-the-art Kullback-Leibler upper confidence bound (KL-UCB) algorithm. The proposed decentralized UCB1 and KL-UCB algorithms permit each agent in the network to achieve a better logarithmic asymptotic regret than their single-agent counterparts, provided that the agent has at least one neighbor, and the more neighbors an agent has, the better regret it will have, meaning that the sum is more than its component parts. The same algorithm design framework is also extended to directed graphs through the design of a variant of the decentralized UCB1 algorithm, which outperforms the single-agent UCB1 algorithm.