Research map / Bandits and online learning / Multi-armed bandits

The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Pure exploration algorithms · 0 citations (OpenAlex)

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 LocalizeChangePoints, an adaptive bandit algorithm that detects candidate intervals via multiscale dyadic tests, then localizes change points by sequential halving with backtracking, showing sample complexity depends jointly on jumps and local spacings for general delta and eta.

Problem

Identifying N of m change points of a piecewise-constant function on [0,1] under bandit (noisy point-query) feedback to precision eta and confidence 1-delta with minimal samples; prior asymptotic results depend only on jump magnitudes and discrete-arm methods scale linearly in 1/eta.

Approach

Decompose the task into multiscale detection of intervals containing change points (governed by energies s_i*Delta_i^2) and per-interval binary-search localization with budget allocated by inverse squared jumps, yielding non-asymptotic bounds with log(1/eta) dependence and matching lower bounds when N=m.

Key results

• For two change points with jumps ±1 and spacing s, LCP's sample complexity decreases roughly as 1/s, while MCPI is insensitive to s due to its 1/eta term.
• LCP's budget grows only slightly as eta decreases from 2^-5 to 2^-11, whereas MCPI's grows nearly proportionally to 1/eta.
• For moderate delta, LCP outperforms MCPI; MCPI only becomes cheaper for very small delta (around e^-110 in Experiment 2).

Surprising findings

• Detection cost does not vanish as delta goes to zero: it enters additively and independently of delta in expectation, so the jump-only asymptotic rate is overly optimistic in moderate-confidence regimes.

Limitations

• Lower bounds only cover the case N=m; optimal rate for N<m is open.
• Doubling schedule is not fully adaptive and is not always practical.
• Upper bounds contain logarithmic factors not matching exactly in all regimes.

Experimental setup

Benchmarks: synthetic piecewise-constant functions

Metrics: average sample budget 0.05/0.95 quantiles of budget

Baselines: MCPI SCPI

Builds on: MCPI Sequential Halving with Backtracking Track-and-Stop

Closest papers by meaning

• Fixed-Confidence Multiple Change Point Identification under Bandit Feedback (ICML 2025 · similarity 0.94)
• The Cost of Learning Under Multiple Change Points (ICML 2026 · similarity 0.87)
• Near Optimal Non-asymptotic Sample Complexity of 1-Identification (ICML 2025 · similarity 0.86)
• The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.85)
• Sample-Adaptivity Tradeoff in On-Demand Sampling (NeurIPS 2025 · similarity 0.84)
• Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.84)