# Almost Cost-Free Communication in Federated Best Arm Identification

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 20 references that are in the map.
- First posted on arXiv 19 Aug 2022.

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

- [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)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [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)
- [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)
- [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)

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

- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [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)
- [Representative Arm Identification: A fixed confidence approach to identify cluster representatives](https://mlsanity.com/paper/2408.14195/) (2024)
- [Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences](https://mlsanity.com/paper/2411.13922/) (2024)
- [ICQ: A Quantization Scheme for Best-Arm Identification Over Bit-Constrained Channels](https://mlsanity.com/paper/2305.00528/) (2023)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)
- [Fixed-Confidence Best Arm Identification with Decreasing Variance](https://mlsanity.com/paper/2502.07199/) (2025)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)
- [Secure Best Arm Identification in the Presence of a Copycat](https://mlsanity.com/paper/2507.18975/) (2025)
- [ICMAPE: In-Context Multiagent Pure Exploration](https://mlsanity.com/paper/2609.33986/) (2026)

## Abstract (arXiv)

We study the problem of best arm identification in a federated learning multi-armed bandit setup with a central server and multiple clients. Each client is associated with a multi-armed bandit in which each arm yields em i.i.d. rewards following a Gaussian distribution with an unknown mean and known variance. The set of arms is assumed to be the same at all the clients. We define two notions of best arm -- local and global. The local best arm at a client is the arm with the largest mean among the arms local to the client, whereas the global best arm is the arm with the largest average mean across all the clients. We assume that each client can only observe the rewards from its local arms and thereby estimate its local best arm. The clients communicate with a central server on uplinks that entail a cost of C≥0 units per usage per uplink. The global best arm is estimated at the server. The goal is to identify the local best arms and the global best arm with minimal total cost, defined as the sum of the total number of arm selections at all the clients and the total communication cost, subject to an upper bound on the error probability. We propose a novel algorithm sc FedElim that is based on successive elimination and communicates only in exponential time steps and obtain a high probability instance-dependent upper bound on its total cost. The key takeaway from our paper is that for any C≥ 0 and error probabilities sufficiently small, the total number of arm selections (resp. the total cost) under sc FedElim is at most~2 (resp.~3) times the maximum total number of arm selections under its variant that communicates in every time step. Additionally, we show that the latter is optimal in expectation up to a constant factor, thereby demonstrating that communication is almost cost-free in sc FedElim. We numerically validate the efficacy of sc FedElim.