Research map / Bandits and online learning / Multi-armed bandits
Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
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.
Introduces fixed-confidence piecewise constant bandits for identifying N change points under bandit feedback, derives instance-dependent lower bounds, and proposes the MCPI Track-and-Stop variant shown asymptotically optimal.
Problem
Identifying the locations of abrupt changes (change points) in a piecewise constant mean-reward function over an action space with confidence and minimal sequential samples, under bandit feedback.
Approach
Derives explicit optimal sampling proportions concentrated on the arms adjacent to each change point (inversely proportional to squared jump size), and builds a computationally cheap Track-and-Stop variant (MCPI) with a closed-form stopping rule and sequential binary-segmentation-style search for multiple change points.
Key results
- MCPI's expected stopping time increases parallel to the instance-dependent lower bound across confidence levels in synthetic environments, consistent with asymptotic optimality.
- MCPI is asymptotically optimal for the Any-(N,delta) objective and within a factor of 2 of the Exact-(N,delta) lower bound.
- BOC with oracle weights and true cluster count has a much faster-growing stopping time than MCPI, as it ignores piecewise constant structure.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MCPI instead of BOC with oracle weights | Fixed-confidence piecewise constant bandits · Synthetic environments v1, v2, and v3 | expected stopping time | Helped |
| Use MCPI to identify one change point despite additional changes | MCPI with N=1 · Synthetic environment v4 | expected stopping time | Helped |
Limitations
- Analysis restricted to discrete arms with Gaussian noise of known variance
- Exact-(N,delta) optimality only up to a factor of 2
- Experiments limited to small synthetic environments
Experimental setup
Datasets: synthetic piecewise constant bandit environments
Benchmarks: synthetic piecewise constant environments v1-v4
Metrics: expected stopping time (sample complexity) comparison to instance-dependent lower bound
Baselines: Bandit Online Clustering (BOC)
Builds on: Track-and-Stop D-Tracking Binary Segmentation
Closest papers by meaning
- The Sample Complexity of Multiple Change Point Identification under Bandit Feedback (NeurIPS 2026 · similarity 0.94)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.85)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.85)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.85)
- On the Asymptotic Optimality of Confidence Interval Based Algorithms for Fixed Confidence MABs (AAAI 2025 · similarity 0.84)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.84)
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.