# Federated Best Arm Identification with Heterogeneous Clients

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 41 references that are in the map.
- First posted on arXiv 14 Oct 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [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)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [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)
- [Your 2 is My 1, Your 3 is My 9: Handling Arbitrary Miscalibrations in Ratings](https://mlsanity.com/paper/1806.05085/) (2018)
- [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)
- [Solving Multi-Arm Bandit Using a Few Bits of Communication](https://mlsanity.com/paper/2111.06067/) (2021)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Optimal Best Markovian Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1912.00636/) (2019)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Rate-Constrained Remote Contextual Bandits](https://mlsanity.com/paper/2204.12620/) (2022)
- [Best Arm Identification in Restless Markov Multi-Armed Bandits](https://mlsanity.com/paper/2203.15236/) (2022)

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

- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Best Arm Identification in Bandits with Limited Precision Sampling](https://mlsanity.com/paper/2305.06082/) (2023)
- [Fixed-Budget Differentially Private Best Arm Identification](https://mlsanity.com/paper/2401.09073/) (2024)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)
- [Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2506.22480/) (2025)
- [ICMAPE: In-Context Multiagent Pure Exploration](https://mlsanity.com/paper/2609.33986/) (2026)

## Abstract (arXiv)

We study best arm identification in a federated multi-armed bandit setting with a central server and multiple clients, when each client has access to a em subset of arms and each arm yields independent Gaussian observations. The goal is to identify the best arm of each client subject to an upper bound on the error probability; here, the best arm is one that has the largest em average value of the means averaged across all clients having access to the arm. Our interest is in the asymptotics as the error probability vanishes. We provide an asymptotic lower bound on the growth rate of the expected stopping time of any algorithm. Furthermore, we show that for any algorithm whose upper bound on the expected stopping time matches with the lower bound up to a multiplicative constant (em almost-optimal algorithm), the ratio of any two consecutive communication time instants must be em bounded, a result that is of independent interest. We thereby infer that an algorithm can communicate no more sparsely than at exponential time instants in order to be almost-optimal. For the class of almost-optimal algorithms, we present the first-of-its-kind asymptotic lower bound on the expected number of em communication rounds until stoppage. We propose a novel algorithm that communicates at exponential time instants, and demonstrate that it is asymptotically almost-optimal.