Research map / Bandits and online learning / Multi-armed bandits
Communication-Efficient Collaborative Regret Minimization in 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.
Gives the first round-regret tradeoff for multi-agent (collaborative learning) multi-armed bandits: a lower bound via hard two-arm instances showing regret must scale as (KT)^{1/R} for R rounds, plus a matching batched successive-elimination algorithm.
Problem
Regret minimization in multi-armed bandits under the collaborative learning model, where K agents must trade off parallelism against the number of communication rounds.
Approach
A round lower bound for CL-model regret via a new proof strategy using a chain of hard two-arm Bernoulli instances with geometrically decreasing gaps and indistinguishability of short transcripts (projection onto single agents), since round elimination does not work for two-arm instances; paired with a batched successive elimination algorithm whose round count adapts to the instance gap.
Key results
- Lower bound: any R-round T-time K-agent CL algorithm incurs regret Omega(min{K,(KT)^{1/R}}/(log(KT) logloglog(KT)) * 1/Delta) on some input, for R up to log(KT)/(2 logloglog(KT)).
- Batched successive elimination algorithm uses O(log_lambda(1/Delta)) rounds w.h.p. and regret O(lambda log(KT)/Delta), matching the lower bound up to logarithmic factors for constant R.
- With lambda = Theta(1), the CL algorithm uses O(log(KT)) rounds and achieves asymptotically optimal regret O(sum log(KT)/Delta_a).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict collaborative learning to R communication rounds | Collaborative MAB algorithms · Collaborative MAB | expected regret: \Omega\left(\frac{1}{{\log(KT)\log\log\log(KT)}} \cdot \min\left\{K, (KT)^{\frac{1}{R}}\right\}\cdot \frac{1}{\Delta(I)} | Hurt |
| Use the proposed batched successive-elimination algorithm | Batched MAB · Batched MAB | expected regret: O\left(\sum_{a \neq \star} \frac{\lambda \log T}{\Delta_a}\right) | Helped |
| Use the collaborative reduction of the batched algorithm | Collaborative MAB · Collaborative MAB | expected regret: O\left(\sum_{a \neq \star} \frac{\lambda \log(KT)}{\Delta_a}\right) | Helped |
| Set λ = (KT)^{\frac{1}{R}} | BatchedMAB via collaborative reduction · Two-arm collaborative MAB | expected regret: O\left((KT)^{\frac{1}{R}} \cdot \log(KT) \cdot \frac{1}{\Delta(I)} \right); \Omega\left((KT)^{\frac{1}{R}} \cdot \frac{1 | Mixed |
| Set λ = Θ(1) | BatchedMAB via collaborative reduction · Collaborative MAB | expected regret: O\left(\sum_{a \neq \star} \frac{\log(KT)}{\Delta_a}\right) | Helped |
| Add early stopping when only one arm remains | BatchedMAB · Batched MAB | rounds: \eta = O\left(\log_\lambda \frac{1}{\Delta(I)}\right) | Helped |
| Add a preliminary exploration step | BatchedMAB · Batched MAB | rounds | Helped |
Surprising findings
- Round elimination, the standard technique for BAI round lower bounds, only yields a round lower bound of two for two-arm regret instances.
Limitations
- Poly-logarithmic gap remains between upper and lower bounds.
- Results are for IID environments; non-IID setting not addressed.
- Round lengths are fixed in the algorithm, while the lower bound allows adaptive round lengths.
Experimental setup
Metrics: expected regret number of communication rounds
Baselines: BPR two-arm batched algorithm centralized UCB/successive elimination regret bound
Builds on: successive elimination generalized round elimination batched bandit algorithms
Closest papers by meaning
- Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication (ICLR 2020 · similarity 0.93)
- Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits (ICML 2023 · similarity 0.92)
- Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits (NeurIPS 2019 · similarity 0.91)
- Distributed Linear Bandits under Communication Constraints (ICML 2023 · similarity 0.91)
- Individual Regret in Cooperative Stochastic Multi-Armed Bandits (NeurIPS 2025 · similarity 0.90)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · 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.