Research map / Bandits and online learning / Multi-armed bandits
Individual Regret in Cooperative Stochastic Multi-Armed Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes a cooperative successive elimination algorithm (Coop-SE) for multi-agent stochastic bandits on arbitrary connected graphs, proving a diameter-free individual regret bound O(R/m + A^2 + A√log T) with a near-matching lower bound, plus CONGEST and low-communication variants.
Problem
Individual regret in cooperative stochastic multi-armed bandits where agents communicate over an arbitrary connected graph, without an additive dependence on graph diameter.
Approach
Shows that Coop-SE (successive elimination with message passing of rewards and eliminations) makes neighborhoods implicitly synchronize over stage intervals, so each agent accumulates roughly sum over stages of (tau_j/A_j)*|N_{<=tau_j/4}| samples; with |N| >= min(m, tau/4) this yields a diameter-free bound.
Key results
- Coop-SE achieves individual regret O(sum_i log(T)/(m Delta_i) + A^2 + A sqrt(log T)), independent of graph diameter.
- Lower bound Omega(sqrt(AT/m) + sqrt(A)) on individual minimax regret, nearly matching the upper bound.
- Coop-SE-CONGEST keeps the same regret bound with O(log(mA))-bit messages; Coop-SE-Comm-Cost uses O(log T) communication rounds with regret O(log(A) R/m + A log(A) log(T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cooperative successive elimination with message passing and round-robin action selection | Coop-SE · Cooperative stochastic MAB | individual regret | Helped |
| Use random action choices instead of round-robin selection (ablation) | Coop-SE · Cooperative stochastic MAB | individual regret | Mixed |
| Restrict message size to O(\log(Am)) bits using Coop-SE-CONGEST | Coop-SE · Cooperative stochastic MAB | individual regret | Helped |
| Limit communication to O(\log(T)) rounds using Coop-SE-Comm-Cost | Coop-SE · Cooperative stochastic MAB | individual regret | Mixed |
Surprising findings
- With enough agents the individual regret is independent of the sub-optimality gaps, scaling only with A^2 and A sqrt(log T).
- Lower bound shows individual regret still scales with the number of actions even as m goes to infinity.
Limitations
- Additive term A^2 + A sqrt(log T) has suboptimal dependence on A and log T; exact dependence left open.
- Analysis restricted to Successive Elimination; extension to UCB and Thompson sampling is open.
- Communication-cost variant has a worse regret factor log(A) on the gap term and does not satisfy the CONGEST constraint simultaneously.
Experimental setup
Metrics: individual pseudo-regret
Baselines: Coop-UCB2 DDUCB UCB-TCOM Sus-Act
Builds on: Successive Elimination UCB Coop-UCB2 DDUCB UCB-TCOM
Closest papers by meaning
- Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits (NeurIPS 2019 · similarity 0.95)
- Decentralized Cooperative Stochastic Bandits (NeurIPS 2019 · similarity 0.93)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.90)
- Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits (AAAI 2024 · similarity 0.90)
- Delay as Payoff in MAB (AAAI 2025 · similarity 0.89)
- Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.