Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Optimal Batched Linear 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.
Proposes E^4, a batched linear bandit algorithm (Explore-Estimate-Eliminate-Exploit) that achieves minimax-optimal regret with O(log log T) batches and asymptotic optimality with 3 batches, plus a lower bound showing asymptotically optimal algorithms need at least 3 batches.
Problem
Batched linear bandits with a fixed finite arm set need regret that is simultaneously minimax optimal and asymptotically optimal while using few batches (batch complexity).
Approach
Combines a D-optimal design first batch, a second batch that uses a gap-based optimal allocation with a Chernoff stopping rule to identify the best arm and skip further exploration, and phased elimination with D-optimal design as a fallback, so the algorithm needs only 3 batches asymptotically while keeping minimax guarantees.
Key results
- E^4 uses 3 batches on End of Optimism instances (d=5, K=9, T=100000) while IDS needs more than 10^5 batches, with regret similar to IDS and lower than rs-OFUL, EndOA and PhaElimD.
- E^4 runtime is 5x to 1000x faster than baselines across End of Optimism instances (e.g., 0.25 s vs 178.31 s for IDS at d=5, epsilon=0.01).
- Theory: regret O(log log T * sqrt(dT log(KT))) with O(log log T) batches, and limsup R_T/log T <= c* with 3 batches in expectation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use E^4 instead of the tested baselines | End of Optimism instances · End of Optimism instances | regret | Helped |
| Use E^4 instead of PhaElimD | End of Optimism instances · End of Optimism instances | batch complexity: 3 batches vs around 4 batches | Helped |
| Use E^4 instead of PhaElimD | End of Optimism instances · End of Optimism instances | regret | Helped |
| Use E^4 instead of the baselines | End of Optimism instances · End of Optimism instances | runtime: 5-fold to 1000-fold | Helped |
| Increase the instance parameter ε (ablation) | E^4 and the tested algorithms · End of Optimism instances | regret | Hurt |
| Increase the instance parameter ε (ablation) | Optimism-based algorithms relative to E^4 · End of Optimism instances | regret | Mixed |
Surprising findings
- PhaElimD-style optimistic baselines and rs-OFUL show regret that grows as epsilon shrinks, while E^4 stays near-optimal, consistent with optimism failing asymptotically on End of Optimism instances.
Limitations
- Asymptotic optimality and the 3-batch result hold only as T goes to infinity, with finite-T guarantees depending on log factors.
- Theory assumes a fixed arm set that spans R^d and unique best arm; the instance-dependent optimal regret with optimal batch complexity is left open.
Experimental setup
Datasets: synthetic End of Optimism instances randomly generated linear bandit instances
Benchmarks: End of Optimism instances random linear bandit instances
Metrics: cumulative regret batch complexity runtime (seconds)
Baselines: rs-OFUL EndOA IDS PhaElimD
Builds on: phased elimination with D-optimal design Chernoff stopping rule for best arm identification rarely switching OFUL IDS (frequentist information-directed sampling) End of Optimism instances
Closest papers by meaning
- Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits (ICLR 2025 · similarity 0.94)
- Optimal and Practical Batched Linear Bandit Algorithm (ICML 2025 · similarity 0.93)
- Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · similarity 0.92)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.90)
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.89)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (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.