We consider online learning in non-stationary environments, where the goal is to track an unknown parameter that switches abruptly between a finite set of recurring values. Recurrence opens the possibility of judiciously reusing past observations to improve algorithm performance. However, the changing nature of the underlying signal and lack of information on these dynamics may limit the ability to "safely" reuse data. In this paper we quantify some of the fundamental tradeoffs in this class of problems, and show that they bear a certain resemblance to the classical bias-variance dilemma. Specifically, we propose a class of anytime algorithms, dubbed Exposure-Capped Reuse (ECR), that combine online change detection, compatibility testing, and "contamination" control. We characterize the regime in which ECR's regret scales with the number of distinct values rather than the number of changes, and derive a novel information-theoretic lower bound that establishes the near-minimax optimality of ECR. This provides rigorous quantification of the statistical "value" of data reuse.
Figures & tables
Figure 1
Figure 3: A recurrent environment. The mean undergoes S=5 changes across M=3 classes. Returns to previously visited classes create opportunities for data reuse. However, if the short segment I1 goes undetected, its observations can become mixed with those from the surrounding θ(1) segments. Reusing this mixed history when θ(1) returns can introduce bias.
Figure 4: Schematic ECR segmentation. Red dashed lines delimit blocks created by detector alarms. Missed changes and detection delays introduce contamination, yet block B0 remains anchored at class 1 .
Figure 5: Numerical results. (a) Synthetic regret on log–log axes. (b) Exposure-budget tradeoff at different levels of source contamination. (c) Electronic-nose readouts and reference levels for the first 12 segments. (d) Regret over the full replay, normalized by t . Error bars in (a) and (b) show 95% Monte Carlo intervals.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Exposure capping under persistent contamination. (a) Terminal cumulative L1 regret as the subsequent recurrent sequence grows. (b) Cumulative regret at T=33,168 . Results average 100 paired paths.
Figure 7: Trace-driven NAB replay. (a) The first 12 segments of one irregular, noncyclic replay. (b) Mean cumulative L1 regret over 100 randomized replays.
Figure 8: (a) Vector-valued recurrence. Euclidean regret relative to the recurrent benchmark for d=5 , M=4 , and S+1=T , averaged over 40 paired paths. (b) Online benefit under Lp loss. Relative regret reduction of ECR over no reuse at T=262,144 , averaged over 30 paired paths.
Figure 9: Geometric-grid ECR. (a) Regret relative to the recurrent benchmark’s Monte Carlo mean. (b) Total split evaluations. Results average 40 paired paths.
Figure 10: Environment illustration. Each cell represents two rounds. Each source interval is followed by a q -cell A -segment and produces an unanchored source block. Each reuse interval is followed by an L -cell A -segment and produces an unsafe block anchored at 0 ; the constant- A segments produce class- A blocks. During the latter half of each reuse interval, the same source blocks are accepted and reused, while all other completed blocks are rejected. The illustration is schematic and not to scale; alarm delays are suppressed.