# A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 7 Jul 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning](https://mlsanity.com/paper/2008.03606/) (2020)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [Federated Recommendation System via Differential Privacy](https://mlsanity.com/paper/2005.06670/) (2020)
- [Communication Efficient Federated Learning for Generalized Linear Bandits](https://mlsanity.com/paper/2202.01087/) (2022)
- [Unifying Clustered and Non-stationary Bandits](https://mlsanity.com/paper/2009.02463/) (2020)

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

- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Online Experimental Design With Estimation-Regret Trade-off Under Network Interference](https://mlsanity.com/paper/2412.03727/) (2024)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)
- [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)
- [FedConPE: Efficient Federated Conversational Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2405.02881/) (2024)
- [Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learning](https://mlsanity.com/paper/2303.04833/) (2023)
- [Federated Linear Contextual Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2403.00116/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?](https://mlsanity.com/paper/2507.11891/) (2025)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)
- [Incentivized Communication for Federated Bandits](https://mlsanity.com/paper/2309.11702/) (2023)
- [Federated Linear Bandits with Finite Adversarial Actions](https://mlsanity.com/paper/2311.00973/) (2023)
- [Incentivized Truthful Communication for Federated Bandits](https://mlsanity.com/paper/2402.04485/) (2024)
- [Communication-Efficient Federated Non-Linear Bandit Optimization](https://mlsanity.com/paper/2311.01695/) (2023)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Fairness and Privacy Guarantees in Federated Contextual Bandits](https://mlsanity.com/paper/2402.03531/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference](https://mlsanity.com/paper/2509.15515/) (2025)
- [Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference](https://mlsanity.com/paper/2510.07646/) (2025)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)
- [Multi-Agent Best Arm Identification in Stochastic Linear Bandits](https://mlsanity.com/paper/2411.13690/) (2024)
- [Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2506.22480/) (2025)
- [Scaling Federated Linear Contextual Bandits via Sketching](https://mlsanity.com/paper/2605.00500/) (2026)

## Abstract (arXiv)

We study federated contextual linear bandits, where M agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We propose a simple algorithm named textttFedLinUCB based on the principle of optimism. We prove that the regret of textttFedLinUCB is bounded by tildeO(d√summ=1M Tm) and the communication complexity is tildeO(dM2), where d is the dimension of the contextual vector and Tm is the total number of interactions with the environment by m-th agent. To the best of our knowledge, this is the first provably efficient algorithm that allows fully asynchronous communication for federated contextual linear bandits, while achieving the same regret guarantee as in the single-agent setting.