Individual Regret in Cooperative Stochastic Multi-Armed Bandits

Idan Barnea, Tal Lancewicki, Yishay Mansour

TL;DR

This paper introduces Coop-SE, the first decentralized cooperative multi-armed bandit algorithm that achieves an individual regret bound completely independent of the communication graph's diameter. By scaling the single-agent regret down by the number of agents ($R/m$), the authors demonstrate that agents can effectively collaborate without being bottlenecked by the network's physical layout. Furthermore, they extend this framework to communication-constrained environments, offering near-optimal performance even with strict limits on message sizes or communication rounds.

What Problem Does This Paper Address?

In cooperative Multi-Armed Bandit (MAB) problems, multiple agents collaborate to discover the best action (or "arm") to maximize their cumulative rewards. When these agents are arranged across a network graph, they pass messages to share what they've learned.

Historically, theoretical guarantees for an individual agent's regret (the expected reward lost by not picking the optimal arm) heavily depended on the graph's diameter ($D$)—the maximum distance between any two agents. In large or sparse networks like cycles or grids, the diameter scales with the number of agents ($m$). If your regret bound includes an additive $+D$ term, the penalty of a large network can completely wipe out the statistical benefits of having more agents helping you sample the arms.

The authors set out to answer a fundamental question: Can agents cooperate effectively over an arbitrary network without paying a mathematical penalty for the network's physical size?

Methods

The authors base their approach on the classic Successive Elimination (SE) algorithm. In a standard single-agent SE setup, the agent samples all active arms in a round-robin fashion, calculates confidence intervals for their rewards, and permanently eliminates arms that are statistically proven to be suboptimal.

To make this cooperative, the authors analyze Coop-SE (Cooperative Successive Elimination). In this decentralized protocol, agents run SE locally but continuously broadcast two types of events to their neighbors:

  1. Reward events: New observations of an arm's reward.
  2. Elimination events: A signal that the agent has dropped a specific arm.

These messages propagate through the network at each timestep. To handle practical network constraints, the authors also introduce two specialized variants:

  • Coop-SE-CONGEST: Tailored for the classic CONGEST model, where message sizes are strictly limited to $O(\log(mA))$ bits. It routes messages along a shared spanning tree using a staggered round-robin schedule to prevent queueing delays.
  • Coop-SE-Comm-Cost: Designed for scenarios where communication is expensive, limiting agents to just $O(\log T)$ communication rounds by grouping agents into dynamically expanding clusters over time.

Datasets

This is a purely theoretical paper focused on algorithmic analysis and mathematical proofs. No empirical datasets or real-world benchmarks were used for evaluation.

Key Insights and Ideas

  • Implicit Synchronization: The core mathematical breakthrough is proving that Coop-SE forces nearby agents to implicitly synchronize their active action sets. Even without an explicit consensus protocol, agents within a certain neighborhood naturally maintain the exact same set of active arms over critical time intervals. This synchronization ensures that local sample counts boost each other efficiently.
  • Diameter-Free Scaling: By leveraging this implicit synchronization, the authors prove that the individual regret drops from the single-agent baseline $R$ to $R/m$, plus an additive term that depends only on the number of actions ($A$) and time ($T$), completely bypassing the graph diameter ($D$).
  • Clever Routing Beats Congestion: For the CONGEST variant, the authors show that by starting the round-robin message scheduling at a different action for each agent, messages can flow up and down a spanning tree without ever colliding or suffering from queueing delays, keeping message sizes minimal without sacrificing the diameter-free regret bound.

Key Results

The paper provides a comprehensive theoretical comparison of how Coop-SE stacks up against prior state-of-the-art cooperative bandit algorithms:

Table 1: Performance Comparison of Multi-Armed Bandit Algorithms in Cooperative Settings. Notation: Horizon T; Number of agents m; Actions A; Graph’s diameter D; Graph G; R = P
  • Upper Bound: Coop-SE achieves an individual regret bound of $O(R/m + A^2 + A\sqrt{\log T})$. When played with random action choices instead of round-robin, the additive term sharpens to $O(A\log T)$.
  • Lower Bound: The authors prove a minimax lower bound of $\Omega(\sqrt{TA/m} + \sqrt{A})$, demonstrating that their upper bound is near-optimal.
  • CONGEST Efficiency: Even when restricting message sizes to a logarithmic number of bits (Coop-SE-CONGEST), the algorithm maintains the exact same diameter-free regret scaling.

Limitations and Future Work

While this paper marks a significant theoretical advancement, the authors note a few open challenges:

  1. The Additive Gap: There is still a gap between the additive term in the upper bound ($A^2$ or $A\sqrt{\log T}$) and the lower bound ($\sqrt{A}$). Closing this gap remains an open question.
  2. Simultaneous Constraints: The current algorithms handle either small message sizes or a small number of communication rounds, but not both simultaneously. Designing an algorithm that achieves near-optimal regret under both constraints at once is a promising direction for future research.
  3. Extension to Other Paradigms: Successive Elimination naturally lends itself to synchronization because active arm sets change predictably. Extending diameter-free individual regret bounds to other popular bandit frameworks like Upper Confidence Bound (UCB) or Thompson Sampling will be much more challenging, as rare action selections can easily cause agents' policies to diverge.

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 analyzed a variant of Cooperative Successive Elimination algorithm, COOP-SE, and show an individual regret bound of $O(R/ m + A^2 + A \sqrt{\log T})$ and a nearly matching lower bound. Here $A$ is the number of actions, $T$ the time horizon, $m$ the number of agents, and $R = \sum_{Δ_i > 0}\log(T)/Δ_i$ is the optimal single agent regret, where $Δ_i$ is the sub-optimality gap of action $i$. Our work is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter. When considering communication networks there are additional considerations beyond regret, such as message size and number of communication rounds. First, we show that our regret bound holds even if we restrict the messages to be of logarithmic size. Second, for logarithmic number of communication rounds, we obtain a regret bound of $O(R / m+A \log T)$.
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