Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost
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 batch elimination with a server and communicate only reward-feature vectors at batch boundaries | Distributed contextual linear bandits · Stochastic contexts | communication cost: $\mathcal{O}(dN\log\log(NT))$ versus the lower bound $\Omega(dN)$ | Helped |
| Use DisBE-LUCB batch elimination instead of DisLinUCB | Distributed contextual linear bandits · Synthetic stochastic contexts | communication cost | Helped |
| Use DisBE-LUCB batch elimination instead of DisLinUCB | Distributed contextual linear bandits · Synthetic stochastic contexts | regret | No clear effect |
| Replace standard confidence intervals with the paper's distribution-based confidence intervals (ablation) | DisBE-LUCB · Stochastic contexts | communication cost: $\tilde{\mathcal{O}}(d^2N)$ to $\tilde{\mathcal{O}}(dN)$ | Helped |
| Estimate the context-distribution matrix rather than use its exact value (ablation) | DisBE-LUCB · Stochastic contexts, estimated context distribution | regret: $(1-\max_{m\in[M]}\epsilon_m)^{-1}$ | Hurt |
| Round communicated vector entries to precision $\epsilon_0$ (ablation) | DisBE-LUCB · Stochastic contexts, rounded messages | regret: its regret is same as DisBE-LUCB's | No clear effect |
| Replace the central server with neighbor-only communication and consensus (ablation) | DisBE-LUCB · Stochastic contexts on a communication graph | communication cost: extra multiplication factor $\log(dN)\delta_{\rm max}/\sqrt{1/\abs{\lambda_2}}$ | Hurt |
| Replace the central server with neighbor-only communication and consensus (ablation) | DisBE-LUCB · Stochastic contexts on a communication graph | regret: $\log(dN)NM/\sqrt{1/\abs{\lambda_2}}$ | Hurt |
Closest papers by meaning
- Distributed Linear Bandits under Communication Constraints (ICML 2023 · similarity 0.93)
- Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication (ICLR 2020 · similarity 0.93)
- Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · 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.90)
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · 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.