Individual Regret in Cooperative Stochastic Multi-Armed Bandits

Idan Barnea, Tal Lancewicki, Yishay Mansour

Abstract

We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We show a near-optimal individual regret bound of $\tilde{O}(\sqrt{AT/m}+A)$, where $A$ is the number of actions, $T$ the time horizon, and $m$ the number of agents. In particular, assuming a sufficient number of agents, we achieve a regret bound of $\tilde{O}(A)$, which is independent of the sub-optimality gaps and the diameter of the communication graph. To the best of our knowledge, our study is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter and applicable to non-fully-connected communication graphs.

Introduction

In the Multi-Armed Bandit (MAB) framework, an agent must repeatedly choose between several "arms" (actions) with unknown reward distributions to maximize its total reward. In a cooperative setting, multiple agents solve the same MAB problem and share information over a communication graph. The primary challenge in this domain is optimizing individual regret: the reward loss of a single agent compared to an oracle knowing the best arm from the start.

Previous research in cooperative MAB often produced bounds that included an additive term proportional to the graph's diameter ($D$). In large, sparse networks like long lines or grids, $D$ can be substantial, potentially negating the benefits of cooperation for individual agents. This work demonstrates that agents can cooperate effectively without their performance being bottlenecked by the overall size or "width" of the network.

Methodology

The study focuses on a decentralized protocol where agents interact with the environment and their neighbors in discrete rounds.

The general protocol for a stochastic MAB on a graph.

The primary algorithm introduced is Cooperative Successive Elimination (Coop-SE). It operates through three main mechanisms:

  1. Successive Elimination: Each agent maintains a set of "active" arms, sampling them in a round-robin fashion.
  2. Information Sharing: Agents broadcast observed rewards and "elimination signals" (decisions that an arm is suboptimal) to immediate neighbors.
  3. Local Processing: Agents update confidence intervals using received information. If an arm's upper confidence bound falls below another arm's lower confidence bound, it is eliminated.

To address practical constraints, the authors also propose Coop-SE-CONGEST, which limits message sizes to $O(\log(mA))$ bits using a spanning tree, and Coop-SE-Comm-Cost, which restricts communication to $O(\log T)$ rounds over the entire horizon.

Key Theoretical Insights

Diameter Independence

The core finding is that an agent does not require information from the entire graph to improve performance. Information from a local neighborhood propagates quickly enough to boost the effective sample size before the next arm elimination occurs. By dividing time into "stages" based on elimination events, the authors decouple regret from the global graph diameter.

Implicit Synchronization

Under Coop-SE, agents in a local neighborhood naturally synchronize their sets of active arms. This occurs because elimination signals travel through the graph faster than the time required for an individual agent to collect enough samples to eliminate an arm independently.

Fundamental Limits

The authors establish a lower bound using a line graph, showing that even with infinite agents, individual regret must scale with the number of actions ($A$). This highlights a fundamental limit to the benefits of cooperation.

Comparative Results

The paper provides a comprehensive comparison of Coop-SE against existing state-of-the-art algorithms, demonstrating superior performance in regret bounds and communication efficiency.

Comparison of performance across various cooperative MAB algorithms.
  • Regret Bound: Coop-SE achieves an individual regret of $O(\mathcal{R}/m + A^2 + A\sqrt{\log T})$, where $\mathcal{R}$ is the optimal single-agent regret.
  • Minimax Regret: The minimax bound is $O(\sqrt{TA \log T}/m + A^2 + A\sqrt{\log T})$.
  • Lower Bound: The established lower bound of $\Omega(\sqrt{TA}/m + \sqrt{A})$ nearly matches the upper bound in the minimax setting.

Conclusion and Future Work

While this work provides the first diameter-independent regret bounds, several open questions remain. There is a gap between the $A^2$ additive term in the upper bound and the $\sqrt{A}$ term in the lower bound. Furthermore, the current analysis is specific to Successive Elimination; extending these results to Upper Confidence Bound (UCB) or Thompson Sampling remains a challenge due to the lack of explicit "stages" in those algorithms. Future research may also explore leveraging specific graph topologies, such as expander graphs, to further optimize additive terms.

Summary updated

Abstract

We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We show a near-optimal individual regret bound of $\tilde{O}(\sqrt{AT/m}+A)$, where $A$ is the number of actions, $T$ the time horizon, and $m$ the number of agents. In particular, assuming a sufficient number of agents, we achieve a regret bound of $\tilde{O}(A)$, which is independent of the sub-optimality gaps and the diameter of the communication graph. To the best of our knowledge, our study is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter and applicable to non-fully-connected communication graphs.
BibTeX
@inproceedings{barnea2025individual,
  author = {Idan Barnea and Tal Lancewicki and Yishay Mansour},
  title = {{Individual Regret in Cooperative Stochastic Multi-Armed Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=k4wAXbEPD6},
}
Figure