Research map / Bandits and online learning / Multi-armed bandits
Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DEMAB's staged elimination and limited communication instead of immediate sharing | Distributed MAB · Distributed MAB | communication cost: O(M^2T) -> O\left(M\log(MK)\right) | Helped |
| Use DEMAB instead of immediate sharing | Distributed MAB · Distributed MAB | regret: O\left(\sqrt{MKT\log T}\right) -> O\left(\sqrt{MTK\log T}\right) | No clear effect |
| Use DELB's elimination protocol instead of immediate sharing | Distributed linear bandits · Fixed action set | communication cost: O(M^2dT) -> O\left((Md+d\log\log d)\log T\right) | Helped |
| Use DELB instead of immediate sharing | Distributed linear bandits · Fixed action set | regret: O\left(d\sqrt{MT\log T}\right) -> O\left(d\sqrt{TM\log T}\right) | No clear effect |
| Use DisLinUCB for a time-varying action set | Distributed linear bandits · Time-varying action set | communication cost: O\left(M^{1.5}d^3\right) | Mixed |
| Set burn-in duration D and starting phase l₀ to 0 (ablation) | DEMAB · Distributed MAB | instance-dependent regret: O\left(\sum_{k: \Delta_k > 0} \Delta_k^{-1} \log T + M\log M\right) | Helped |
| Set burn-in duration D and starting phase l₀ to 0 (ablation) | DEMAB · Distributed MAB | communication cost (expected): O\left(M\log(MK)\right) -> O\left(M\log T\right) | Mixed |
| Replace public randomness with a finite preselected set of strings and a server-selected string (ablation) | DEMAB · Distributed MAB without public randomness | regret: O(\sqrt{MKT\log T}) | No clear effect |
| Replace public randomness with a finite preselected set of strings and a server-selected string (ablation) | DEMAB · Distributed MAB without public randomness | communication cost (expected): O(M\log(MK)) | No clear effect |
Closest papers by meaning
- Distributed Linear Bandits under Communication Constraints (ICML 2023 · similarity 0.95)
- Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits (AAAI 2024 · similarity 0.93)
- Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost (ICML 2023 · similarity 0.93)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.92)
- Individual Regret in Cooperative Stochastic Multi-Armed Bandits (NeurIPS 2025 · similarity 0.90)
- 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.