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

Chao Tao, Qin Zhang, Yuan Zhou

Abstract

This paper investigates the fundamental limits of distributed best arm identification in multi-armed bandits under communication constraints. By analyzing both fixed-time and fixed-confidence settings, the authors establish nearly tight theoretical bounds on the number of communication rounds required to achieve a linear speedup with $K$ agents. The results reveal a significant complexity gap between the two learning scenarios and provide new mathematical tools for analyzing distributed online learning.

Introduction

The Multi-Armed Bandit (MAB) problem is a cornerstone of online learning, where a learner seeks to identify the optimal "arm" from a set of $n$ options by observing stochastic rewards. In many real-world applications—ranging from clinical trials to large-scale A/B testing—exploration is performed by multiple agents in parallel. However, communication between agents is often the primary bottleneck due to network latency, energy consumption, and protocol overhead. This research addresses a critical question: how many rounds of communication are necessary for $K$ agents to achieve a $K$-fold speedup in learning efficiency?

Problem Variants

The study focuses on two primary exploration paradigms:

  1. Fixed-time: The agents have a predefined time budget $T$ and aim to minimize the probability of failing to identify the best arm.
  2. Fixed-confidence: The agents must achieve a target error probability $\delta$ while minimizing the total time taken.

Methodology

To establish upper bounds, the authors propose a two-phase distributed algorithm. In the first phase (Elimination), arms are partitioned among agents who independently identify local candidates without communication. In the second phase (Refinement), agents use the remaining communication rounds to collectively narrow down the candidates through uniform sampling and confidence interval-based elimination.

For the lower bounds, the paper introduces two novel mathematical techniques:

  • Generalized Round-Elimination: This technique proves that if a problem cannot be solved in $R-1$ rounds, it remains intractable in $R$ rounds under specific constraints.
  • Distribution Exchange Lemma: Specifically designed for the fixed-confidence setting, this lemma tracks how information about different reward distributions propagates across communication rounds.

Key Results and the Round-Speedup Tradeoff

The core contribution of this work is the characterization of the tradeoff between the number of communication rounds and the achievable speedup. The results show that a linear speedup is not always possible without sufficient interaction.

Summary of upper and lower bounds for communication rounds in fixed-time and fixed-confidence settings.

In the fixed-time setting, achieving a near-linear speedup requires $\Omega(\ln K / \ln \ln K)$ rounds, while the proposed algorithm achieves this in $\ln K$ rounds. Conversely, in the fixed-confidence setting, the required communication scales with the problem's inherent difficulty—specifically the gap $\Delta_{min}$ between the best and second-best arm—requiring $\Omega(\ln(1/\Delta_{min}))$ rounds. This highlights a fundamental separation in the intrinsic complexity of these two common learning objectives.

Insights and Implications

The analysis reveals that "adaptivity"—the ability to adjust strategies within a round—offers diminishing returns when the number of arms is small relative to the number of agents. Furthermore, the authors utilize a "Pyramid" hard instance to demonstrate that certain arm distributions inherently resist parallelization unless frequent communication occurs.

Conclusion and Future Directions

While this work provides "almost tight" bounds, small logarithmic gaps remain between the upper and lower bounds. Future research may focus on closing these gaps, exploring the impact of message size limits, and extending the model to heterogeneous agents with varying operational costs or sampling speeds.

Summary updated

Abstract

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.
BibTeX
@inproceedings{tao2019collaborative,
  author = {Chao Tao and Qin Zhang and Yuan Zhou},
  title = {{Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits}},
  booktitle = {FOCS},
  year = {2019},
  url = {https://openreview.net/forum?id=huU_WWQw-dZ},
}
Figure