Research map / Bandits and online learning / Multi-armed bandits
Almost Minimax Optimal Best Arm Identification in Piecewise Stationary 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 a piecewise-stationary linear bandit model and the PSεBAI+ algorithm (change detection and context alignment run in parallel with a naive baseline) for fixed-confidence ε-best arm identification, with near-optimal expected sample complexity up to a log factor.
Problem
Fixed-confidence (ε,δ)-PAC best arm identification in piecewise stationary linear bandits, where contexts are drawn i.i.d. from an unknown distribution at unknown changepoints and arm quality is its average return over contexts.
Approach
Measures arms by expected return over a context distribution, actively detects changepoints via sliding-window linear change detection and aligns new segments to previously seen contexts, and runs this in parallel with a naive stopping rule so the expected sample complexity is finite, with a matching-up-to-log lower bound.
Key results
- PSεBAI+ empirical sample complexity is at most 1% of NεBAI's across tested epsilon values.
- PSεBAI+ needs roughly the same number of context samples as DεBAI and DεBAI-beta, which observe contexts and changepoints, despite having no such oracle information.
- The expected sample complexity upper bound matches a generic lower bound up to logarithmic factors on the example instance family.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add active changepoint detection and context alignment, using PSεBAI within PSεBAI+ | PSεBAI+ vs. NεBAI · PSLB synthetic instance | sample complexity: ≤1% of that of NεBAI | Helped |
| Use PSεBAI+ without observing context vectors or changepoints, compared with algorithms given that oracle information | PSεBAI+ vs. DεBAI and DBAIβ · PSLB synthetic instance | number of context samples | No clear effect |
| Misspecify Lmax slightly (ablation) | PSεBAI+ · PSLB synthetic instance | sample complexity | No clear effect |
| Vary the change-detection frequency γ, with w and b changed accordingly (ablation) | PSεBAI+ · PSLB synthetic instance | sample complexity | No clear effect |
Surprising findings
- PSεBAI+ is competitive with oracle-informed baselines that observe contexts and changepoints.
Limitations
- Requires assumptions (distinguishability, segment lengths long enough, knowledge of L_max) that may not hold in practice.
- Expected sample complexity relies on running two algorithms in parallel; the high-probability PSεBAI result needs a non-vanishing failure budget.
Experimental setup
Benchmarks: simulated PSLB instance (d=2, phi=pi/8)
Metrics: expected sample complexity number of context samples empirical error rate / PAC success
Baselines: NεBAI DεBAI D-ε-BAI variant with confidence radius (beta)
Builds on: G-optimal allocation stationary linear bandit best arm identification piecewise-stationary bandit change detection
Closest papers by meaning
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.92)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.91)
- Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.91)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.91)
- Near Optimal Best Arm Identification for Clustered Bandits (ICML 2025 · similarity 0.90)
- Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · similarity 0.90)
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.