mlsanityData to 14 Oct 2026

Pure Exploration in Asynchronous Federated Bandits

arXiv 2310.11015 ↗First posted 17 Oct 2023cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the federated pure exploration problem of multi-armed bandits and linear bandits, where M agents cooperatively identify the best arm via communicating with the central server. To enhance the robustness against latency and unavailability of agents that are common in practice, we propose the first federated asynchronous multi-armed bandit and linear bandit algorithms for pure exploration with fixed confidence. Our theoretical analysis shows the proposed algorithms achieve near-optimal sample complexities and efficient communication costs in a fully asynchronous environment. Moreover, experimental results based on synthetic and real-world data empirically elucidate the effectiveness and communication cost-efficiency of the proposed algorithms.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 41 of its 66 references that are in the map. First posted on arXiv 17 Oct 2023.

Builds on

41 of 66 references.

References · 41

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  3. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  4. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 149
  5. 2014Best-Arm Identification in Linear Banditscited by 100
  6. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
  7. 2020Differentially-Private Federated Linear Banditscited by 83
  8. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  9. 2020Optimal Best-arm Identification in Linear Banditscited by 71
  10. 2020Gamification of Pure Exploration for Linear Banditscited by 63
  11. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  12. 2021Federated Linear Contextual Banditscited by 61
29 more
  1. 2021Federated Multi-Armed Banditscited by 59
  2. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  3. 2020Federated Bandit: A Gossiping Approachcited by 55
  4. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  5. 2016Distributed Clustering of Linear Bandits in Peer to Peer Networkscited by 50
  6. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  7. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43
  8. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  9. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  10. 2016Towards Instance Optimal Bounds for Best Arm Identificationcited by 30
  11. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  12. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  13. 2020Collaborative Top Distribution Identifications with Limited Interactioncited by 21
  14. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  15. 2019Best Arm Identification in Generalized Linear Banditscited by 18
  16. 2020Fast Distributed Bandits for Online Recommendation Systemscited by 18
  17. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  18. 2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
  19. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  20. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  21. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  22. 2022Communication Efficient Federated Learning for Generalized Linear Banditscited by 13
  23. 2022Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcited by 13
  24. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  25. 2022Almost Cost-Free Communication in Federated Best Arm Identificationcited by 11
  26. 2022Distributed Bandits with Heterogeneous Agentscited by 9
  27. 2022Federated Best Arm Identification with Heterogeneous Clientscited by 8
  28. 2023On-Demand Communication for Asynchronous Multi-Agent Banditscited by 7
  29. 2023Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costscited by 3

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 4.

6 papers.

  1. 2024Online Experimental Design With Estimation-Regret Trade-off Under Network Interferencecited by 9
  2. 2025AGFT: An Adaptive GPU Frequency Tuner for Real-Time LLM Inference Optimizationcited by 2
  3. 2025Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inferencecited by 1
  4. 2024Multi-Agent Best Arm Identification in Stochastic Linear Banditscited by 0
  5. 2025Near Optimal Best Arm Identification for Clustered Banditscited by 0
  6. 2025Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisitioncited by 0