mlsanityData to 7 Oct 2026

Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits

arXiv 1904.03293 ↗First posted 5 Apr 2019cs.LG cs.IT math.ITcited by 40

Not on the map. Why?

Abstract (arXiv)

Best arm identification (or, pure exploration) in multi-armed bandits is a fundamental problem in machine learning. In this paper we study the distributed version of this problem where we have multiple agents, and they want to learn the best arm collaboratively. We want to quantify the power of collaboration under limited interaction (or, communication steps), as interaction is expensive in many settings. We measure the running time of a distributed algorithm as the speedup over the best centralized algorithm where there is only one agent. We give almost tight round-speedup tradeoffs for this problem, along which we develop several new techniques for proving lower bounds on the number of communication steps under time or confidence constraints.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 6; 2022: 9; 2023: 12; 2024: 5; 2025: 8.

40 papers.

Sort:

  1. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  2. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  3. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  4. 2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
  5. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  6. 2021Online Learning for Cooperative Multi-Player Multi-Armed Banditscited by 12
  7. 2023The sample complexity of multi-distribution learningcited by 12
  8. 2022Almost Cost-Free Communication in Federated Best Arm Identificationcited by 11
  9. 2023A Lipschitz Bandits Approach for Continuous Hyperparameter Optimizationcited by 9
  10. 2023Tight Regret Bounds for Single-pass Streaming Multi-armed Banditscited by 9
  11. 2022Federated Best Arm Identification with Heterogeneous Clientscited by 8
  12. 2022Distributed Linear Bandits under Communication Constraintscited by 8
28 more
  1. 2023Optimal Batched Best Arm Identificationcited by 8
  2. 2023Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communicationcited by 8
  3. 2021When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Banditscited by 7
  4. 2022Parallel Best Arm Identification in Heterogeneous Environmentscited by 6
  5. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  6. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  7. 2022Communication-Efficient Collaborative Best Arm Identificationcited by 5
  8. 2022Collaborative Algorithms for Online Personalized Mean Estimationcited by 5
  9. 2023The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Banditscited by 5
  10. 2024Optimal Streaming Algorithms for Multi-Armed Banditscited by 5
  11. 2023Incentivized Communication for Federated Banditscited by 3
  12. 2024Batched Nonparametric Contextual Banditscited by 3
  13. 2025Multiplayer Information Asymmetric Contextual Banditscited by 3
  14. 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Banditscited by 2
  15. 2024Batched Stochastic Bandit for Nondegenerate Functionscited by 2
  16. 2025The Batch Complexity of Bandit Pure Explorationcited by 2
  17. 2023Federated Learning for Heterogeneous Bandits with Unobserved Contextscited by 1
  18. 2023Communication-Efficient Federated Non-Linear Bandit Optimizationcited by 1
  19. 2024Differentially-Private Collaborative Online Personalized Mean Estimationcited by 1
  20. 2022Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliabilitycited by 0
  21. 2023Optimal Regret Bounds for Collaborative Learning in Banditscited by 0
  22. 2024Fair Distributed Cooperative Bandit Learning on Networks for Intelligent Internet of Things Systems (Technical Report)cited by 0
  23. 2025Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Gridscited by 0
  24. 2025Near Optimal Best Arm Identification for Clustered Banditscited by 0
  25. 2025Collaborative Min-Max Regret in Grouped Multi-Armed Banditscited by 0
  26. 2025Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Banditscited by 0
  27. 2025Batched Bandits with Heavy-Tailed Rewardscited by 0
  28. 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margincited by 0