Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Optimal and Practical Batched Linear Bandit Algorithm
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 BLAE, a batched linear bandit algorithm combining arm elimination with regularized G-optimal design that claims minimax-optimal regret (up to log T) in both large-K and small-K regimes using O(log log T) batches, with empirical superiority over E^4, RS-OFUL and PhaElimD.
Problem
Batched linear bandits must achieve near-optimal regret with limited policy updates (few batches) while remaining computationally cheap and performing well in practice; prior methods either are computationally heavy, eliminate arms prematurely, or update too often.
Approach
Arm elimination across batches where each batch's sampling distribution solves a regularized G-optimal design over remaining arms, mixed with a greedy exploitation arm, plus a batched regularized least-squares estimator and an arm-difference concentration bound that keeps the optimal arm while removing suboptimal ones.
Key results
- Theory: worst-case regret O(sqrt(dT)(sqrt(log(KT)) ∧ sqrt(d+log T)) log log T) using O(log log T) batches, claimed to match lower bounds up to log factors.
- Experiments (10 runs, T=100,000): BLAE reports lower cumulative regret than E^4, RS-OFUL and PhaElimD across all tested (K,d) pairs, including RS-OFUL which uses over 100 updates.
- E^4 has minimal batch complexity but the highest regret and instability in the reported experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BLAE instead of existing batched linear bandit algorithms | Batched linear bandits with fixed arms · Synthetic experiments across the tested (K,d) settings | cumulative regret | Helped |
| Use BLAE instead of RS-OFUL | Batched linear bandits with fixed arms · Synthetic experiments | policy updates | Helped |
| Use E⁴ instead of BLAE | Batched linear bandits with fixed arms · Synthetic experiments | cumulative regret | Hurt |
Surprising findings
- RS-OFUL with over 100 parameter updates is outperformed by BLAE, which uses far fewer batches.
- BatchLinUCB-DG often fails to double the determinant of its information matrix and settles on degenerate exploration distributions in the authors' experiments.
Limitations
- Theorem requires horizon condition T >= Omega(max{K^2/((d∧log K)d), K^{4/5}}) and d>=2.
- Regret bounds hold up to log factors; hyperparameter choices (lambda, c_l) are set heuristically in experiments, and theory uses only O(1) constants.
- Experiments are limited to synthetic uniform instances with small d and K up to 400, and only four baselines.
Experimental setup
Datasets: synthetic linear bandit instances (uniform arms and theta)
Benchmarks: synthetic linear bandit with K in {50,100,200,400}, d in {5,10}, T=100000
Metrics: cumulative regret batch complexity runtime
Baselines: E^4 RS-OFUL PhaElimD BatchLinUCB-DG
Builds on: phased elimination rarely switching OFUL Explore-Estimate-Eliminate-Exploit
Closest papers by meaning
- Optimal Batched Linear Bandits (ICML 2024 · similarity 0.93)
- Regret Bounds for Batched Bandits (AAAI 2021 · similarity 0.92)
- Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · similarity 0.92)
- Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.88)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.88)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.88)
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.