mlsanityData to 14 Oct 2026

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

arXiv 2207.03106 ↗First posted 7 Jul 2022cs.LG stat.MLcited by 28

Not on the map. Why?

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.

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

19 of 48 references.

References · 19

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2020Mime: Mimicking Centralized Stochastic Algorithms in Federated Learningcited by 154
  3. 2014Online Clustering of Banditscited by 102
  4. 2020Differentially-Private Federated Linear Banditscited by 83
  5. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 64
  6. 2021Federated Linear Contextual Banditscited by 61
  7. 2020Federated Bandit: A Gossiping Approachcited by 55
  8. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  9. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  10. 2016Distributed Clustering of Linear Bandits in Peer to Peer Networkscited by 50
  11. 2013A Gang of Banditscited by 49
  12. 2019Social Learning in Multi Agent Multi Armed Banditscited by 48
7 more
  1. 2013Bandits with Switching Costs: T^{2/3} Regretcited by 39
  2. 2021Learning Equilibria in Matching Markets from Bandit Feedbackcited by 34
  3. 2015On Distributed Cooperative Decision-Making in Multiarmed Banditscited by 33
  4. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  5. 2020Federated Recommendation System via Differential Privacycited by 26
  6. 2022Communication Efficient Federated Learning for Generalized Linear Banditscited by 13
  7. 2020Unifying Clustered and Non-stationary Banditscited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 12; 2024: 9; 2025: 5; 2026: 2.

28 papers.

Sort:

  1. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  2. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  3. 2024Federated Combinatorial Multi-Agent Multi-Armed Banditscited by 11
  4. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  5. 2024Online Experimental Design With Estimation-Regret Trade-off Under Network Interferencecited by 9
  6. 2023On-Demand Communication for Asynchronous Multi-Agent Banditscited by 7
  7. 2023Federated Online and Bandit Convex Optimizationcited by 7
  8. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  9. 2024Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Userscited by 6
  10. 2024FedConPE: Efficient Federated Conversational Bandits with Heterogeneous Clientscited by 6
  11. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  12. 2024Federated Linear Contextual Bandits with Heterogeneous Clientscited by 4
16 more
  1. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  2. 2025Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?cited by 4
  3. 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Banditscited by 3
  4. 2023Incentivized Communication for Federated Banditscited by 3
  5. 2023Federated Linear Bandits with Finite Adversarial Actionscited by 3
  6. 2024Incentivized Truthful Communication for Federated Banditscited by 2
  7. 2023Communication-Efficient Federated Non-Linear Bandit Optimizationcited by 1
  8. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  9. 2024Fairness and Privacy Guarantees in Federated Contextual Banditscited by 1
  10. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  11. 2025LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inferencecited by 1
  12. 2025Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inferencecited by 1
  13. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1
  14. 2024Multi-Agent Best Arm Identification in Stochastic Linear Banditscited by 0
  15. 2025Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Banditscited by 0
  16. 2026Scaling Federated Linear Contextual Bandits via Sketchingcited by 0