Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Regret minimization in Linear Bandits with offline data via extended D-optimal exploration.
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 OOPE, a phased elimination algorithm for linear bandits with fixed-design offline data that uses an extended D-optimal design, yielding effective-dimension regret bounds plus minimax lower bounds and a Frank-Wolfe variant (OOPE-FW).
Problem
Online regret minimization in stochastic linear bandits when the learner has prior offline observations collected by a fixed (non-adaptive) design over arms.
Approach
Phased elimination whose exploration design mixes the offline Gram matrix with online samples via an extended D-optimal design; the effective dimension f, computed from the offline eigenspectrum, governs regret, and the paper derives matching-regime minimax lower bounds that depend on offline eigenspectrum.
Key results
- Upper bound of order sqrt(f T log(|A|T)) + d^2 with f <= d, recovering online rates when offline data is poorly explored and improving when well explored.
- Minimax lower bounds depending on the offline eigenspectrum match OOPE up to log factors and additive constants in the well-explored (k=1) and under-explored (k=Omega(d)) regimes.
- OOPE-FW improves the second term to d^2/f, and experiments show it outperforms OOPE at moderate effective dimension and longer horizons, while OOPE is better at large f.
Surprising findings
- Warm-started LinUCB can be d^{1/2} worse than OOPE on a hard instance, and the paper reports that the Frank-Wolfe variant is worse than OOPE when effective dimension is near d.
Limitations
- Assumes offline data is generated by a fixed non-adaptive design and reward distributions do not drift between offline and online stages.
- Gap between upper and lower bounds in the moderately explored regime (k=o(d)).
- Requires a technical assumption on minimum offline samples per arm in the support of the offline design.
Experimental setup
Datasets: synthetic linear bandit instances (unit sphere arms and parameters)
Benchmarks: synthetic linear bandit simulations
Metrics: cumulative regret regret difference (OOPE minus OOPE-FW)
Baselines: pure online phased elimination warm-started LinUCB warm-started LinTS
Builds on: phased elimination D-optimal design OFUL LinUCB Frank-Wolfe
Closest papers by meaning
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.92)
- Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.92)
- Optimal Batched Linear Bandits (ICML 2024 · similarity 0.90)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.90)
- Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.90)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 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.