# Multi-Agent Best Arm Identification in Stochastic Linear Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 49 references that are in the map.
- First posted on arXiv 20 Nov 2024.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Collaborative Learning for Deep Neural Networks](https://mlsanity.com/paper/1805.11761/) (2018)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2106.04763/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost](https://mlsanity.com/paper/2205.13170/) (2022)
- [Multi-Agent Low-Dimensional Linear Bandits](https://mlsanity.com/paper/2007.01442/) (2020)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Collaborative Multi-agent Stochastic Linear Bandits](https://mlsanity.com/paper/2205.06331/) (2022)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)

## Abstract (arXiv)

We study the problem of collaborative best-arm identification in stochastic linear bandits under a fixed-budget scenario. In our learning model, we first consider multiple agents connected through a star network, interacting with a linear bandit instance in parallel. We then extend our analysis to arbitrary network topologies. The objective of the agents is to collaboratively identify the best arm of the given bandit instance with the help of a central server while minimizing the probability of error in best arm estimation. To this end, we propose two algorithms, MaLinBAI-Star and MaLinBAI-Gen for star networks and networks with arbitrary structure, respectively. Both algorithms utilize the technique of G-optimal design along with the successive elimination based strategy where agents share their knowledge through a central server at each communication round. We demonstrate, both theoretically and empirically, that our algorithms achieve exponentially decaying probability of error in the allocated time budget. Furthermore, experimental results on both synthetic and real-world data validate the effectiveness of our algorithms over the state-of-the art existing multi-agent algorithms.