# Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 9 Jun 2023.

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

- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits](https://mlsanity.com/paper/1505.00553/) (2015)
- [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](https://mlsanity.com/paper/1907.05632/) (2019)
- [On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems](https://mlsanity.com/paper/1802.08380/) (2018)
- [Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits](https://mlsanity.com/paper/1902.01575/) (2019)
- [Bayesian Algorithms for Decentralized Stochastic Bandits](https://mlsanity.com/paper/2010.10569/) (2020)
- [A Dynamic Observation Strategy for Multi-agent Multi-armed Bandit Problem](https://mlsanity.com/paper/2004.03793/) (2020)
- [Multi-Player Bandits: A Trekking Approach](https://mlsanity.com/paper/1809.06040/) (2018)
- [Joint Channel Selection and Power Control in Infrastructureless Wireless Networks: A Multi-Player Multi-Armed Bandit Framework](https://mlsanity.com/paper/1407.5447/) (2014)
- [Heterogeneous Stochastic Interactions for Multiple Agents in a Multi-armed Bandit Problem](https://mlsanity.com/paper/1905.08731/) (2019)
- [A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits](https://mlsanity.com/paper/1908.10402/) (2019)
- [A Non-Stationary Bandit-Learning Approach to Energy-Efficient Femto-Caching with Rateless-Coded Transmission](https://mlsanity.com/paper/2005.04154/) (2020)
- [Heterogeneous Explore-Exploit Strategies on Multi-Star Networks](https://mlsanity.com/paper/2009.01339/) (2020)
- [Reliable Crowdsourcing for Multi-Class Labeling using Coding Theory](https://mlsanity.com/paper/1309.3330/) (2013)

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

- [Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.14138/) (2023)
- [The Nah Bandit: Modeling User Non-compliance in Recommendation Systems](https://mlsanity.com/paper/2408.07897/) (2024)

## Abstract (arXiv)

We study a structured multi-agent multi-armed bandit (MAMAB) problem in a dynamic environment. A graph reflects the information-sharing structure among agents, and the arms' reward distributions are piecewise-stationary with several unknown change points. The agents face the identical piecewise-stationary MAB problem. The goal is to develop a decision-making policy for the agents that minimizes the regret, which is the expected total loss of not playing the optimal arm at each time step. Our proposed solution, Restarted Bayesian Online Change Point Detection in Cooperative Upper Confidence Bound Algorithm (RBO-Coop-UCB), involves an efficient multi-agent UCB algorithm as its core enhanced with a Bayesian change point detector. We also develop a simple restart decision cooperation that improves decision-making. Theoretically, we establish that the expected group regret of RBO-Coop-UCB is upper bounded by O(KNMlog T + K√MTlog T), where K is the number of agents, M is the number of arms, and T is the number of time steps. Numerical experiments on synthetic and real-world datasets demonstrate that our proposed method outperforms the state-of-the-art algorithms.