# The Cost of Learning Under Multiple Change Points

arXiv: https://arxiv.org/abs/2602.11406 · HTML: https://mlsanity.com/paper/2602.11406/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 11 Feb 2026.

## Builds on (most cited first, 16 of 16)

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Evaluating Real-time Anomaly Detection Algorithms - the Numenta Anomaly Benchmark](https://mlsanity.com/paper/1510.03336/) (2015)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [An Adaptive Deep RL Method for Non-Stationary Environments with Piecewise Stable Context](https://mlsanity.com/paper/2212.12735/) (2022)
- [Minimal Expected Regret in Linear Quadratic Control](https://mlsanity.com/paper/2109.14429/) (2021)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [Window-Limited CUSUM for Sequential Change Detection](https://mlsanity.com/paper/2206.06777/) (2022)
- [Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits](https://mlsanity.com/paper/2410.07638/) (2024)
- [Sequential Change Detection for Learning in Piecewise Stationary Bandit Environments](https://mlsanity.com/paper/2501.10974/) (2025)
- [Short term prediction of demand for ride hailing services: A deep learning approach](https://mlsanity.com/paper/2212.03956/) (2022)
- [Non-Parametric Quickest Mean Change Detection](https://mlsanity.com/paper/2108.11348/) (2021)

## Abstract (arXiv)

We consider an online learning problem in environments with multiple change points. In contrast to the single change point problem that is widely studied using classical "high confidence" detection schemes, the multiple change point environment presents new learning-theoretic and algorithmic challenges. Specifically, we show that classical methods may exhibit catastrophic failure (high regret) due to a phenomenon we refer to as endogenous confounding. To overcome this, we propose a new class of learning algorithms dubbed Anytime Tracking CUSUM (ATC). These are horizon-free online algorithms that implement a selective detection principle, balancing the need to ignore "small" (hard-to-detect) shifts, while reacting "quickly" to significant ones. We prove that the performance of a properly tuned ATC algorithm is nearly minimax-optimal; its regret is guaranteed to closely match a novel information-theoretic lower bound on the achievable performance of any learning algorithm in the multiple change point problem. Experiments on synthetic as well as real-world data validate the aforementioned theoretical findings.