# Near Optimal Best Arm Identification for Clustered Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 45 references that are in the map.
- First posted on arXiv 15 May 2025.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [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)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Local Clustering in Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2103.00063/) (2021)
- [Collaborative Top Distribution Identifications with Limited Interaction](https://mlsanity.com/paper/2004.09454/) (2020)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1901.08386/) (2019)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [On the Complexity of A/B Testing](https://mlsanity.com/paper/1405.3224/) (2014)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Privacy-Preserving Communication-Efficient Federated Multi-Armed Bandits](https://mlsanity.com/paper/2111.01570/) (2021)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [Federated Multi-Armed Bandits Under Byzantine Attacks](https://mlsanity.com/paper/2205.04134/) (2022)
- [Parallel Best Arm Identification in Heterogeneous Environments](https://mlsanity.com/paper/2207.08015/) (2022)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Communication-Efficient Collaborative Best Arm Identification](https://mlsanity.com/paper/2208.09029/) (2022)
- [Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits](https://mlsanity.com/paper/2305.18784/) (2023)
- [Representative Arm Identification: A fixed confidence approach to identify cluster representatives](https://mlsanity.com/paper/2408.14195/) (2024)
- [Adaptive Sample Sharing for Multi Agent Linear Bandits](https://mlsanity.com/paper/2309.08710/) (2023)

## Abstract (arXiv)

This work investigates the problem of best arm identification for multi-agent multi-armed bandits. We consider N agents grouped into M clusters, where each cluster solves a stochastic bandit problem. The mapping between agents and bandits is a priori unknown. Each bandit is associated with K arms, and the goal is to identify the best arm for each agent under a δ-probably correct (δ-PC) framework, while minimizing sample complexity and communication overhead. We propose two novel algorithms: Clustering then Best Arm Identification (Cl-BAI) and Best Arm Identification then Clustering (BAI-Cl). Cl-BAI uses a two-phase approach that first clusters agents based on the bandit problems they are learning, followed by identifying the best arm for each cluster. BAI-Cl reverses the sequence by identifying the best arms first and then clustering agents accordingly. Both algorithms leverage the successive elimination framework to ensure computational efficiency and high accuracy. We establish δ-PC guarantees for both methods, derive bounds on their sample complexity, and provide a lower bound for this problem class. Moreover, when M is small (a constant), we show that the sample complexity of a variant of BAI-Cl is minimax optimal in an order-wise sense. Experiments on synthetic and real-world datasets (MovieLens, Yelp) demonstrate the superior performance of the proposed algorithms in terms of sample and communication efficiency, particularly in settings where M ll N.