# Distributed Bandits with Heterogeneous Agents

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 23 Jan 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Multi-Armed Bandit Based Client Scheduling for Federated Learning](https://mlsanity.com/paper/2007.02315/) (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)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Cooperative Online Learning: Keeping your Neighbors Updated](https://mlsanity.com/paper/1901.08082/) (2019)
- [Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings](https://mlsanity.com/paper/1807.00491/) (2018)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without](https://mlsanity.com/paper/1904.12233/) (2019)
- [Regret Guarantees for Item-Item Collaborative Filtering](https://mlsanity.com/paper/1507.05371/) (2015)
- [Decentralized Heterogeneous Multi-Player Multi-Armed Bandits with Non-Zero Rewards on Collisions](https://mlsanity.com/paper/1910.09089/) (2019)
- [Multi-User MABs with User Dependent Rewards for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1910.09091/) (2019)
- [Stochastic Online Shortest Path Routing: The Value of Feedback](https://mlsanity.com/paper/1309.7367/) (2013)
- [Resource Allocation in NOMA-based Self-Organizing Networks using Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2101.06340/) (2021)
- [Dynamic Spectrum Access using Stochastic Multi-User Bandits](https://mlsanity.com/paper/2101.04388/) (2021)

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

- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [Human-in-the-loop Learning for Dynamic Congestion Games](https://mlsanity.com/paper/2404.15599/) (2024)
- [Combining Diverse Information for Coordinated Action: Stochastic Bandit Algorithms for Heterogeneous Agents](https://mlsanity.com/paper/2408.03405/) (2024)
- [Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks](https://mlsanity.com/paper/2303.05445/) (2023)
- [Federated Linear Bandit Learning via Over-the-Air Computation](https://mlsanity.com/paper/2308.13298/) (2023)
- [Adversarial Attacks on Cooperative Multi-agent Bandits](https://mlsanity.com/paper/2311.01698/) (2023)
- [Competitive Multi-armed Bandit Games for Resource Sharing](https://mlsanity.com/paper/2503.20975/) (2025)

## Abstract (arXiv)

This paper tackles a multi-agent bandit setting where M agents cooperate together to solve the same instance of a K-armed stochastic bandit problem. The agents are textitheterogeneous: each agent has limited access to a local subset of arms and the agents are asynchronous with different gaps between decision-making rounds. The goal for each agent is to find its optimal local arm, and agents can cooperate by sharing their observations with others. While cooperation between agents improves the performance of learning, it comes with an additional complexity of communication between agents. For this heterogeneous multi-agent setting, we propose two learning algorithms, ucbo and AAE. We prove that both algorithms achieve order-optimal regret, which is Oleft(sum_i:tildeDeltai>0 log T/tildeDeltairight), where tildeDeltai is the minimum suboptimality gap between the reward mean of arm i and any local optimal arm. In addition, a careful selection of the valuable information for cooperation, AAE achieves a low communication complexity of O(log T). Last, numerical experiments verify the efficiency of both algorithms.