The Cost of Learning Under Multiple Change Points

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.

Many real-world systems change over time. Customer demand can shift after a major event, computer workloads can change following a software update, and user behavior on online platforms can evolve unexpectedly. To make good decisions, learning algorithms must continuously adapt to these changes. Our work studies the fundamental limits of learning in environments that experience multiple abrupt changes. A key challenge is that if an algorithm misses an earlier change, outdated information can contaminate future estimates, making subsequent changes harder to detect. We show that this effect, which we call endogenous confounding, can accumulate over time and lead to severe performance degradation if not properly controlled. To address this challenge, we develop a new online learning algorithm that selectively reacts to meaningful changes while ignoring changes that are too small or too short-lived to significantly affect performance. We prove that this approach achieves near-optimal performance in a worst-case sense and validate the theory on both synthetic and real-world datasets. Our results provide new insights into how learning systems can remain reliable in dynamic and changing environments.