# Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 59 references that are in the map.
- First posted on arXiv 24 Dec 2023.

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

- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [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)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [Multi-Agent Multi-Armed Bandits with Limited Communication](https://mlsanity.com/paper/2102.08462/) (2021)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Decentralized Multi-player Multi-armed Bandits with No Collision Information](https://mlsanity.com/paper/2003.00162/) (2020)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits](https://mlsanity.com/paper/1505.00553/) (2015)
- [Multiplayer bandits without observing collision information](https://mlsanity.com/paper/1808.08416/) (2018)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](https://mlsanity.com/paper/1907.05632/) (2019)
- [Selfish Robustness and Equilibria in Multi-Player Bandits](https://mlsanity.com/paper/2002.01197/) (2020)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Best Arm Identification in Spectral Bandits](https://mlsanity.com/paper/2005.09841/) (2020)
- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Multi-User MABs with User Dependent Rewards for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1910.09091/) (2019)
- [Scalable Optimization for Wind Farm Control using Coordination Graphs](https://mlsanity.com/paper/2101.07844/) (2021)
- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [Solving Transition-Independent Multi-agent MDPs with Sparse Interactions (Extended version)](https://mlsanity.com/paper/1511.09047/) (2015)
- [Fleetwide data-enabled reliability improvement of wind turbines](https://mlsanity.com/paper/1903.11518/) (2019)
- [Multi-Objective Coordination Graphs for the Expected Scalarised Returns with Generative Flow Models](https://mlsanity.com/paper/2207.00368/) (2022)
- [On Distributed Multi-player Multiarmed Bandit Problems in Abruptly Changing Environment](https://mlsanity.com/paper/1812.05165/) (2018)

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

- [ε-Neural Thompson Sampling of Deep Brain Stimulation for Parkinson Disease Treatment](https://mlsanity.com/paper/2403.06814/) (2024)

## Abstract (arXiv)

We study the multi-agent multi-armed bandit (MAMAB) problem, where m agents are factored into ρ overlapping groups. Each group represents a hyperedge, forming a hypergraph over the agents. At each round of interaction, the learner pulls a joint arm (composed of individual arms for each agent) and receives a reward according to the hypergraph structure. Specifically, we assume there is a local reward for each hyperedge, and the reward of the joint arm is the sum of these local rewards. Previous work introduced the multi-agent Thompson sampling (MATS) algorithm citepverstraeten2020multiagent and derived a Bayesian regret bound. However, it remains an open problem how to derive a frequentist regret bound for Thompson sampling in this multi-agent setting. To address these issues, we propose an efficient variant of MATS, the ε-exploring Multi-Agent Thompson Sampling (ε-MATS) algorithm, which performs MATS exploration with probability ε while adopts a greedy policy otherwise. We prove that ε-MATS achieves a worst-case frequentist regret bound that is sublinear in both the time horizon and the local arm size. We also derive a lower bound for this setting, which implies our frequentist regret upper bound is optimal up to constant and logarithm terms, when the hypergraph is sufficiently sparse. Thorough experiments on standard MAMAB problems demonstrate the superior performance and the improved computational efficiency of ε-MATS compared with existing algorithms in the same setting.