Collaborative Learning with Limited Interaction: Tight Bounds for
  Distributed Exploration in Multi-Armed Bandits
  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.
