Finite-Horizon Quickest Change Detection Balancing Latency with False Alarm Probability

Basic Information

• Paper ID: 2511.12803
• Title: Finite-Horizon Quickest Change Detection Balancing Latency with False Alarm Probability
• Authors: Yu-Han Huang and Venugopal V. Veeravalli (University of Illinois Urbana-Champaign)
• Classification: cs.IT, math.IT, stat.ML
• Compilation Date: November 18, 2025
• Paper Link: https://arxiv.org/abs/2511.12803

Abstract

This paper investigates a variant of the finite-horizon quickest change detection (QCD) problem related to learning in non-stationary environments. The paper employs false alarm probability as the false alarm metric and latency (the minimum value such that the probability of detection delay exceeding this value is bounded to a predetermined level) as the detection delay metric. The objective is to minimize latency while maintaining low false alarm probability. Under preset latency and false alarm levels, the paper derives a universal lower bound on latency that any change detection procedure must satisfy, and develops change detectors that are order-optimal in the time domain. The analysis first considers the case where pre- and post-change distributions are known, then generalizes to the non-parametric case where distributions are only known to be sub-Gaussian with different means. Simulation results validate the theoretical findings.

Research Background and Motivation

1. Core Problem to Be Addressed

This paper studies the finite-horizon quickest change detection problem, balancing detection performance under the following new metric system:

• False Alarm Metric: Probability of false alarm within the time domain P∞(τ ≤ T)
• Latency Metric: Latency ℓ, defined as the minimum value such that the probability of detection delay exceeding this value does not exceed a preset level δD

2. Problem Importance

Traditional QCD problems typically assume:

• Infinite Time Horizon: Inconsistent with finite-horizon scenarios in practical applications
• Expected Delay Minimization: Rather than controlling the probability of delay exceeding a threshold
• Average Time Between False Alarms: Rather than false alarm probability

The new problem formulation is more critical in the following applications:

• Online Learning in Piecewise-Stationary Environments: Such as piecewise-stationary bandit problems and finite-horizon episodic Markov decision processes
• Algorithms Requiring Restart: After detecting environmental changes, algorithms must restart, necessitating simultaneous control of false alarm probability and detection delay probability

3. Limitations of Existing Methods

• Classical CuSum and SR Tests: Use constant thresholds; false alarm probability approaches 1 over large time horizons
• Lai (1998) Work: Only partially addresses the false alarm probability problem; window size does not cover the entire time domain and depends on false alarm level
• Lack of Theoretical Bounds: For problems simultaneously controlling false alarm probability and delay probability, performance lower bounds and order-optimal algorithms are lacking

4. Research Motivation

• Provide theoretical foundations for learning in piecewise-stationary environments
• Establish performance benchmarks (lower bounds) under the new problem formulation
• Develop practical order-optimal detection algorithms

Core Contributions

1. New Problem Formulation: Proposes a finite-horizon QCD problem balancing false alarm probability and latency (Equation 3), where latency is defined as the minimum value such that the probability of detection delay exceeding this value does not exceed δD
2. Universal Lower Bound: Derives a universal lower bound on latency that any change detector must satisfy (Theorem 1): $\ell \geq \left(\frac{1}{K} + o(1)\right)\left[\log(T) + \log\left(\frac{1}{\delta_F}\right) + \log(1-\delta_F-\delta_D) + o(1)\right]$ where $K = \log\left(\mathbb{E}_{f_1}\left[\frac{f_1(X)}{f_0(X)}\right]\right)$
3. Order-Optimal Detector for Known Distributions: Proposes Time-Varying Threshold CuSum (TVT-CuSum) and Time-Varying Threshold SR (TVT-SR) tests, proving their latency is O(log T), matching the order of the lower bound (Theorem 2)
4. Non-parametric Detector: Generalizes the approach to unknown distribution settings, proposing Generalized Likelihood Ratio (GLR) and Generalized Shiryaev-Roberts (GSR) tests, achieving O(log T) latency under sub-Gaussian assumptions (Theorem 3, Corollary 1)
5. Experimental Validation: Validates theoretical results through simulation, demonstrating the order-optimality of the algorithms

Methodology Details

Task Definition

Problem Setting:

• Observation Sequence: {Xn : n ∈ T}, sequentially observed within finite time horizon T
• Change Point: ν ∈ m+1, T, where m is the pre-change window (used to estimate pre-change distribution)
• Distribution Change: $X_n \sim \begin{cases} f_0, & n \in [\nu-1] \\ f_1, & n \in [\nu, T] \end{cases}$

Performance Metrics:

• Latency (Equation 2): $\ell := \min\{d \in [T] : P_\nu(\tau \geq \nu+d) \leq \delta_D, \forall \nu \in [m+1, T-d]\}$
• False Alarm Probability: P∞(τ ≤ T)

Optimization Objective (Equation 3): $\min_\tau \ell \quad \text{s.t.} \quad P_\infty(\tau \leq T) \leq \delta_F$

Model Architecture

1. TVT-CuSum Test (Known Distributions)

CuSum Statistic (Recursive Form): $C_n = \max\{C_{n-1}, 0\} + \log\left(\frac{f_1(X_n)}{f_0(X_n)}\right), \quad C_0 = 0$

Time-Varying Threshold: $\beta_C(n, \delta_F, r) := \log\left(\frac{\zeta(r)}{n^r\delta_F}\right), \quad \zeta(r) = \sum_{i=1}^\infty i^{-r}$

Stopping Time (Equation 12): $\tau_{C,r} := \inf\{n \in \mathbb{N} : C_n \geq \beta_C(n, \delta_F, r)\}$

Key Characteristics:

• Computational Complexity: O(1) per time step
• Threshold grows logarithmically with time, controlling false alarm probability

2. TVT-SR Test (Known Distributions)

SR Statistic (Recursive Form): $S_n = (S_{n-1} + 1)\frac{f_1(X_n)}{f_0(X_n)}, \quad S_0 = 0$

Time-Varying Threshold: $\beta_S(n, \delta_F, r) := \beta_C(n, \delta_F, r) + \log n$

Stopping Time (Equation 14): $\tau_{S,r} := \inf\{n \in \mathbb{N} : \log S_n \geq \beta_S(n, \delta_F, r)\}$

3. GLR Test (Unknown Distributions)

GLR Statistic (Equation 21): $G_n = \sup_{k \in [n]} kD(\hat{\mu}_{1:k}; \hat{\mu}_{1:n}) + (n-k)D(\hat{\mu}_{k+1:n}; \hat{\mu}_{1:n})$

where $D(x;y) := (x-y)^2/(2\sigma^2)$ is the KL divergence for Gaussian distributions, and $\hat{\mu}_{m:n}$ is the empirical mean.

Threshold Function (Equation 23): $\beta_{GLR}(n, \delta_F) := 6\log(1+\log(n)) + \frac{5}{2}\log\left(\frac{4n^{3/2}}{\delta_F}\right) + 11$

Stopping Time: $\tau_{GLR} := \inf\{n \in \mathbb{N} : G_n \geq \beta_{GLR}(n, \delta_F)\}$

Pre-change Window Length Requirement (Equation 29): $m \geq \frac{8\sigma^2}{\Delta^2}\beta(T, \delta_F)$

4. GSR Test (Unknown Distributions)

GSR Statistic (Equation 25): $W_n = \sum_{k=1}^n \exp(kD(\hat{\mu}_{1:k}; \hat{\mu}_{1:n}) + (n-k)D(\hat{\mu}_{k+1:n}; \hat{\mu}_{1:n}))$

Threshold: $\beta_{GSR}(n, \delta_F) := \beta_{GLR}(n, \delta_F) + \log n$

Technical Innovations

1. Time-Varying Threshold Design

Innovation: Threshold grows logarithmically with time, rather than being constant

• Problem Solved: Constant thresholds result in false alarm probability approaching 1 over large time horizons
• Theoretical Basis: Utilizes Ville's inequality and supermartingale properties

Key Lemma 2 (Appendix A): The sequence $\left\{\frac{1}{(j+k)^r}\prod_{i=j}^{j+k}\frac{f_1(X_i)}{f_0(X_i)}\right\}_{k=0}^\infty$ is a non-negative supermartingale under P∞

2. Non-parametric Generalization Strategy

Innovation: Replaces likelihood ratio with generalized likelihood ratio

• GLR Statistic: Estimates unknown parameters through maximum likelihood
• Lemma 1: Expresses GLR statistic as a function of empirical means, facilitating exploitation of sub-Gaussian properties

3. Concentration Inequality Application

Innovation: Combines mixed martingale techniques (Kaufmann & Koolen, 2021)

• Lemma 5: For i.i.d. sub-Gaussian sequences, establishes concentration inequality for empirical KL divergence
• Lemma 6: Constructs non-negative mixed martingale enabling rare events to be bounded by martingale values

4. Latency Analysis Technique

Innovation: Decomposes latency events into three disjoint events

• Event A: Early detection but large log-likelihood ratio
• Event B: Early detection but small log-likelihood ratio
• Separately bounds each using measure transformation and Markov inequality

Experimental Setup

Dataset

Synthetic Data:

• Pre-change Distribution: N(0, 1) (Gaussian with mean 0, variance 1)
• Post-change Distribution: N(1, 1) (Gaussian with mean 1, variance 1)
• Change Magnitude: Δ = 1
• Time Horizon Range: T ∈ {5000, 10000, 20000, 50000, 100000}

Evaluation Metrics

Empirical Latency Calculation:

• For each change point in candidate set M ⊆ m+1, T-ℓ
• Conduct 2×10⁵ trials
• Record detection delay τ - ν
• Take maximum of 100(1-δD) percentile across all change points
• Candidate set: M = {m+1+nT/10 : n ∈ ℕ, m+1+nT/10 ≤ T}

Comparison Methods

• TVT-CuSum Test (with parameter r settings)
• TVT-SR Test (with parameter r settings)
• GLR Test (with downsampling implementation)
• Theoretical Lower Bound (Theorem 1)
• Theoretical Upper Bounds (Theorems 2 and 3)

Implementation Details

• False Alarm Level: δF = 0.01
• Latency Level: δD = 0.01
• Pre-change Window: m = T - 1000 (for GLR test)
• GLR Downsampling Window: 700 time steps (Equation 34) $G'_n := \sup_{k \in [n-700, n]} \log\frac{\sup_{\mu'_0}\prod_{i=1}^k f_{\mu'_0}(X_i) \sup_{\mu'_1}\prod_{i=k+1}^n f_{\mu'_1}(X_i)}{\sup_\mu \prod_{i=1}^n f_\mu(X_i)}$

Experimental Results

Main Findings

Key Observations from Figure 1:

1. Order-Optimality Verification: Empirical latencies of all tests exhibit linear relationship with log T, validating O(log T) order-optimality
2. Performance Ranking:
   • TVT-CuSum < TVT-SR < GLR (latency from smallest to largest)
   • Tests for known distributions outperform those for unknown distributions
3. Tightness of Bounds:
   • Lower Bound is Loose: Noticeable gap between theoretical lower bound and empirical values
   • GLR Upper Bound Most Loose: Theorem 3's upper bound shows largest gap from GLR empirical values
   • TVT-CuSum and TVT-SR Upper Bounds Tighter: Theorem 2's upper bounds show smaller gaps from empirical values

Specific Numerical Examples (Approximate Values from Figure 1)

For T = 100000:

• Theoretical Lower Bound: ~35
• TVT-CuSum Empirical Value: ~55
• TVT-SR Empirical Value: ~60
• GLR Empirical Value: ~75
• GLR Theoretical Upper Bound: ~200+

Experimental Findings

1. Linear Logarithmic Relationship

All tests exhibit latency of the form ℓ = a·log(T) + b, where:

• Slope a reflects algorithm efficiency
• TVT-CuSum has the smallest slope (most optimal)

2. Performance Gap: Known vs. Unknown Distributions

• GLR test's latency approximately 1.4 times that of TVT-CuSum
• Indicates acceptable performance loss from unknown distributions
• GLR test maintains O(log T) order-optimality

3. Theoretical Bounds Have Improvement Potential

Possible Reasons for Lower Bound Looseness:

1. Proof does not impose condition that test is unaware of time horizon T
2. TVT-CuSum may have room for improvement

Reasons for GLR Upper Bound Looseness:

• Proof techniques are conservative
• Concentration inequalities used may not be tight enough

4. Practical Validity

• All tests successfully control false alarm probability below δF
• Latency control within acceptable range
• Reasonable computational complexity (TVT-CuSum and TVT-SR are O(1) per step)

Related Work

1. Classical QCD Theory

• Lorden Criterion (Lorden, 1971): Worst-case expected delay
• Pollak Criterion (Pollak, 1985): Conditional expected delay
• CuSum Test (Page, 1954; Moustakides, 1986): Exactly optimal under Lorden criterion
• SR Test (Shiryaev, 1961): Asymptotically optimal under Pollak and Lorden criteria

2. Finite-Horizon QCD

• Lai (1998): Considers false alarm probability within window, but window does not cover entire time domain
• Distinction of This Work: False alarm probability covers entire time domain; latency defined via probability bound rather than expectation

3. Non-parametric QCD

• Lai & Xing (2010): Sequential change detection with unknown distributions
• GLR Method: Common generalization of generalized likelihood ratio tests
• Contribution of This Work: Non-parametric methods under finite horizon and new metric system

4. Piecewise-Stationary Learning

• Piecewise-Stationary Bandits (Auer et al., 2019; Wei & Luo, 2021; Besson et al., 2022)
• Detection and Restart Strategy (Huang et al., 2025): Requires simultaneous control of false alarm and delay probability
• Application of This Work: Provides theoretical foundation and detection tools for these algorithms

5. Concentration Inequality Techniques

• Ville's Inequality (Ville, 1939): Supermartingale maximum value inequality
• Chernoff Bound (Chernoff, 1952): Tail probability bound for sums
• Mixed Martingale (Kaufmann & Koolen, 2021): Time-uniform concentration inequality

Conclusions and Discussion

Main Conclusions

1. Theoretical Lower Bound: Establishes latency lower bound Ω(log T) for finite-horizon QCD problem, providing performance benchmark for any detector
2. Order-Optimal Algorithms:
   • Known Distributions: TVT-CuSum and TVT-SR achieve O(log T) latency
   • Unknown Distributions: GLR and GSR achieve O(log T) latency under sub-Gaussian assumption
3. Practical Value:
   • Algorithms are computationally efficient (recursive implementation)
   • Successfully control both false alarm probability and latency probability
   • Applicable to piecewise-stationary environment learning
4. Generalizability: Results can be extended to independent but non-identically distributed sub-Gaussian noise (Remark 2)

Limitations

1. Tightness of Theoretical Bounds

• Lower Bound is Loose: Gap with empirical values approximately 1.5 times
• GLR Upper Bound Very Loose: Gap with empirical values exceeds 2.5 times
• Root Causes:
  • Lower bound proof does not account for time-horizon-unaware constraint
  • GLR analysis uses conservative concentration inequalities

2. Distribution Assumptions

• Sub-Gaussian Assumption: While covering bounded distributions, excludes heavy-tailed distributions
• Known Parameters: Requires knowledge of sub-Gaussian parameter σ²
• Mean Change: Only considers mean changes, not variance or other parameter changes

3. Computational Complexity

• GLR Statistic: Lacks recursive structure; direct computation is O(n²)
• Downsampling Tradeoff: Experiments use 700-step window, potentially affecting performance
• GSR Statistic: More difficult to compute; not reported in experiments

4. Single Change Point Assumption

• Current theory addresses single change point
• Piecewise-stationary environments have multiple change points requiring repeated application

Future Directions

1. Improve Theoretical Bounds

• Tighten Lower Bound: Account for time-horizon-unaware constraint
• Tighten GLR Upper Bound: Use more refined concentration inequalities
• Possible Approaches: Information-theoretic methods, exact asymptotic analysis

2. Improve GLR Test

• Tighter Threshold Design: Reduce performance gap with TVT-CuSum
• Efficient Computation: Explore approximate recursive algorithms
• Adaptive Window: Dynamically adjust downsampling window size

3. Generalize Distribution Assumptions

• More General Distribution Families: Beyond sub-Gaussian
• Unknown Parameters: No need to know σ²
• Multi-parameter Changes: Variance, shape parameters, etc.

4. Multiple Change Points Extension

• Theoretical Analysis: Cumulative latency and false alarm under multiple change points
• Adaptive Restart: How to optimally restart after detection
• Change Point Number Estimation

5. Application Research

• Piecewise-Stationary Bandits: Integration into practical algorithms
• Reinforcement Learning: Piecewise-stationary MDPs
• Other Domains: Finance, biomedical signal processing, etc.

In-Depth Evaluation

Strengths

1. Innovation in Problem Formulation ⭐⭐⭐⭐⭐

• Novel Metric System: False alarm probability + latency probability, more suitable for practical applications than traditional expectation-based metrics
• Finite-Horizon Setting: Better aligned with real-world application scenarios
• Clear Application Motivation: Tightly connected with piecewise-stationary learning

2. Completeness of Theoretical Contributions ⭐⭐⭐⭐⭐

• Lower Bound: Provides performance benchmark
• Upper Bound: Gives achievable algorithms
• Order Matching: Proves order-optimality of algorithms
• Progression from Known to Unknown: Complete generalization pathway

3. Rigor of Proof Techniques ⭐⭐⭐⭐⭐

• Supermartingale Construction (Lemma 2): Clever exploitation of Ville's inequality
• Event Decomposition (Appendix B): Breaks complex events into manageable parts
• Mixed Martingale Technique (Lemma 6): Incorporates cutting-edge techniques
• Measure Transformation: Classical yet effective analytical tool

4. Practicality of Methods ⭐⭐⭐⭐

• Computational Efficiency: TVT-CuSum and TVT-SR are O(1) per step
• Easy Implementation: Simple recursive form
• Clear Parameter Selection: Threshold function explicitly specified, no tuning required
• Robustness: GLR method applicable to unknown distributions

5. Sufficiency of Experimental Validation ⭐⭐⭐⭐

• Multiple Time Horizons: T ranges from 5000 to 100000
• Adequate Repetitions: 2×10⁵ trials per setting
• Theoretical Comparison: Compared against theoretical bounds
• Clear Visualization: Figure 1 clearly shows logarithmic-linear relationship

Weaknesses

1. Tightness of Theoretical Bounds ⭐⭐⭐

• Gap Between Lower Bound and Empirical Values: Approximately 1.5 times
• GLR Upper Bound Overly Loose: Gap exceeds 2.5 times
• Impact: Limits guidance value of theory
• Improvement Potential: Authors acknowledge and discuss in paper

2. GLR Computational Complexity ⭐⭐⭐

• Lacks Recursive Structure: Direct computation is O(n²)
• Downsampling Scheme: Used in experiments but lacks theoretical analysis
• GSR Not Implemented: Only GLR results reported
• Practical Impact: Limits large-scale applications

3. Experimental Setup Limitations ⭐⭐⭐

• Single Distribution Family: Only Gaussian distributions tested
• Fixed Parameters: δF = δD = 0.01; parameter sensitivity not explored
• Candidate Change Point Sampling: M includes only points at T/10 intervals
• Missing Comparisons: No comparison with other finite-horizon methods (possibly because few exist)

4. Distribution Assumption Limitations ⭐⭐⭐

• Sub-Gaussian Assumption: Excludes heavy-tailed distributions
• Known σ²: May be unknown in practice
• Mean Change Only: Does not consider other parameter changes
• Generalizability: Limits application scope

5. Writing Completeness ⭐⭐⭐⭐

• Main Results Clear: But proof details relegated to appendix
• Numerous Symbols: Requires careful tracking
• Experimental Details: Downsampling implementation description insufficient
• Overall Clarity: Well-structured, logical flow

Impact

1. Theoretical Contribution to Field ⭐⭐⭐⭐⭐

• New Problem Paradigm: Establishes new theoretical framework for finite-horizon QCD
• Performance Benchmark: Provides standard for other researchers' comparisons
• Technical Tools: Proof techniques applicable to related problems
• Long-term Value: Foundational contribution

2. Practical Value for Applications ⭐⭐⭐⭐

• Piecewise-Stationary Learning: Direct application to bandits, reinforcement learning
• Plug-and-Play: Algorithms can be directly integrated
• Performance Guarantees: Theoretical guarantees reduce application risk
• Limitations: GLR's computational complexity needs resolution

3. Reproducibility ⭐⭐⭐⭐

• Algorithm Clarity: Recursive formulas are clear
• Threshold Functions: Completely specified
• Experimental Setup: Parameters and methods sufficiently described
• Code Not Available: But implementation should not be difficult

4. Value for Follow-up Research ⭐⭐⭐⭐⭐

• Improve Theoretical Bounds: Clear research directions
• Efficient GLR Algorithm: Practical need
• Generalize to Other Distributions: Natural extension
• Multiple Change Points Theory: Important future direction

Applicable Scenarios

1. Ideal Application Scenarios ✅

• Piecewise-Stationary Bandits: Need to detect environmental changes and restart
• Finite-Horizon Decision Making: Clear time constraints
• Sub-Gaussian Observations: Such as bounded rewards
• Mean Changes: Environmental changes manifest as mean drift

2. Scenarios Requiring Adjustment ⚠️

• Infinite Time Horizon: May require threshold function modification
• Heavy-Tailed Distributions: Requires different theoretical tools
• Variance Changes: Requires modified statistics
• Multiple Change Points: Requires repeated application and cumulative analysis

3. Inapplicable Scenarios ❌

• Continuous Changes: Rather than abrupt changes
• Unknown Time Horizon: Algorithm assumes T exists (though doesn't exploit it)
• Extreme Real-Time Requirements: GLR's O(n²) may be too slow
• Dependent Observations: Such as time series with correlation

Key References

1. Moustakides (1986): Exact optimality of CuSum test
2. Pollak (1985) & Lorden (1971): Classical QCD criteria
3. Lai (1998): False alarm probability control within window
4. Kaufmann & Koolen (2021): Mixed martingales and time-uniform concentration inequalities
5. Besson et al. (2022): Change detection for piecewise-stationary bandits
6. Ville (1939): Ville's inequality (supermartingale maximum bound)

Summary

This paper makes important theoretical contributions to the finite-horizon quickest change detection problem, proposing a new metric system more aligned with practical application needs (false alarm probability + latency), establishing performance lower bounds, and developing order-optimal detection algorithms. The theory is rigorous, proof techniques are sophisticated, and experimental validation is comprehensive. Main limitations are loose theoretical bounds and high GLR computational complexity, but these also provide clear directions for future research. This work provides solid theoretical foundations for piecewise-stationary environment learning with significant academic value and application potential.

Recommendation Index: ⭐⭐⭐⭐⭐ (5/5)

• Recommended for researchers interested in sequential analysis, statistical detection, and online learning
• Essential reading for scholars working on piecewise-stationary problems
• Provides theoretical guidance and practical tools for system designers