Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
This work addresses the challenge of efficient distributed exploration for multi-agent systems where interaction is costly, offering theoretical insights with potential applications in domains like sensor networks or federated learning.
The paper tackles the problem of best arm identification in multi-armed bandits with multiple agents collaborating under limited communication, providing almost tight bounds on the tradeoff between communication rounds and speedup over centralized algorithms.
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.