# Federated Bandit: A Gossiping Approach

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2020.

## Built on by (most cited first, 30 of 55)

- [Vertical Federated Learning: Concepts, Advances and Challenges](https://mlsanity.com/paper/2211.12814/) (2022)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Detecting Corrupted Labels Without Training a Model to Predict](https://mlsanity.com/paper/2110.06283/) (2021)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Differentially Private Federated Bayesian Optimization with Distributed Exploration](https://mlsanity.com/paper/2110.14153/) (2021)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [Pervasive AI for IoT applications: A Survey on Resource-efficient Distributed Artificial Intelligence](https://mlsanity.com/paper/2105.01798/) (2021)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Federated Neural Bandits](https://mlsanity.com/paper/2205.14309/) (2022)
- [Federated Graph Machine Learning: A Survey of Concepts, Techniques, and Applications](https://mlsanity.com/paper/2207.11812/) (2022)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Privacy-Preserving Communication-Efficient Federated Multi-Armed Bandits](https://mlsanity.com/paper/2111.01570/) (2021)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [Federated Online Clustering of Bandits](https://mlsanity.com/paper/2208.14865/) (2022)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Differentially Private Linear Bandits with Partial Distributed Feedback](https://mlsanity.com/paper/2207.05827/) (2022)
- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Distributed Linear Bandits under Communication Constraints](https://mlsanity.com/paper/2211.02212/) (2022)
- [Doubly Adversarial Federated Bandits](https://mlsanity.com/paper/2301.09223/) (2023)
- [Federated Multi-Armed Bandits Under Byzantine Attacks](https://mlsanity.com/paper/2205.04134/) (2022)
- [Distributional Reward Estimation for Effective Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/2210.07636/) (2022)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users](https://mlsanity.com/paper/2402.16312/) (2024)
- [Federated X-Armed Bandit](https://mlsanity.com/paper/2205.15268/) (2022)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits](https://mlsanity.com/paper/2305.18784/) (2023)
- [(Almost) Free Incentivized Exploration from Decentralized Learning Agents](https://mlsanity.com/paper/2110.14628/) (2021)

## Abstract (arXiv)

In this paper, we study Federated Bandit, a decentralized Multi-Armed Bandit problem with a set of N agents, who can only communicate their local data with neighbors described by a connected graph G. Each agent makes a sequence of decisions on selecting an arm from M candidates, yet they only have access to local and potentially biased feedback/evaluation of the true reward for each action taken. Learning only locally will lead agents to sub-optimal actions while converging to a no-regret strategy requires a collection of distributed data. Motivated by the proposal of federated learning, we aim for a solution with which agents will never share their local observations with a central entity, and will be allowed to only share a private copy of his/her own information with their neighbors. We first propose a decentralized bandit algorithm GossipUCB, which is a coupling of variants of both the classical gossiping algorithm and the celebrated Upper Confidence Bound (UCB) bandit algorithm. We show that GossipUCB successfully adapts local bandit learning into a global gossiping process for sharing information among connected agents, and achieves guaranteed regret at the order of O(max textttpoly(N,M) log T, textttpoly(N,M)log_λ2-1 N) for all N agents, where λ2∈(0,1) is the second largest eigenvalue of the expected gossip matrix, which is a function of G. We then propose FedUCB, a differentially private version of GossipUCB, in which the agents preserve ε-differential privacy of their local data while achieving O(max fractextttpoly(N,M)εlog2.5 T, textttpoly(N,M) (log_λ2-1 N + log T) ) regret.