Pollak's Minimax Quickest Change Detection: Non-Asymptotic Optimality
Abstract
Although Pollak's minimax formulation is one of the central frameworks in quickest change detection (QCD), the strongest general optimality results available for it are predominantly \emph{asymptotic}, applying as the average run-length-to-false-alarm constraint, γ, tends to infinity. Exact results for finite γ have previously been available only for special models or restricted regimes. This paper addresses the general finite-γ problem over the complete class of randomized, history-dependent stopping rules for i.i.d. change models. The key technical development is a \emph{survival-process representation} that recasts the optimization of Pollak's minimax criterion over stopping times as an equivalent linear variational optimization over admissible survival processes. Although this formulation is infinite-dimensional, it establishes the existence of an optimizer and provides an exact characterization of the finite-γ Pollak minimax value. This characterization, in turn, provides a principled basis for constructing computable stopping rules whose performance can be made arbitrarily close to the optimum. The resulting rules are driven by a recursively updated weighted likelihood-ratio statistic with generally time-varying injections and boundaries. Importantly, this structure is not imposed a priori: the optimization is carried out over the full class of randomized, history-dependent stopping rules, and the Shiryaev--Roberts form emerges naturally from the solution. In particular, the classical Shiryaev--Roberts recursion arises as the time-homogeneous special case. Finally, under a likelihood-ratio floor condition, the framework yields closed-form exact minimax solutions for a nontrivial class of change models.
Related
- Robust Local Fréchet Regression: Nonasymptotic Theory and Minimax Optimality
- Minimax-Optimality of Posterior Sampling for Reinforcement Learning
- Minimax Optimality of the NPMLE for Gaussian Mixtures in Hellinger Distance
- On Minimax Optimality and Uniqueness of Fixed-Step First-Order Methods for Smooth Convex Optimization
- Online Individualized Treatment Selection under Partial Feedback: False Discovery Control and Minimax Optimality
BibTeX
@misc{tajer2026pollaks,
title = {{Pollak's Minimax Quickest Change Detection: Non-Asymptotic Optimality}},
author = {Ali Tajer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.29491},
eprint = {2608.29491},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29491},
}
RIS
TY - UNPB
TI - Pollak's Minimax Quickest Change Detection: Non-Asymptotic Optimality
AU - Ali Tajer
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2608.29491
UR - https://arxiv.org/abs/2608.29491
AB - Although Pollak's minimax formulation is one of the central frameworks in quickest change detection (QCD), the strongest general optimality results available for it are predominantly \emph{asymptotic}, applying as the average run-length-to-false-alarm constraint, γ, tends to infinity. Exact results for finite γ have previously been available only for special models or restricted regimes. This paper addresses the general finite-γ problem over the complete class of randomized, history-dependent stopping rules for i.i.d. change models. The key technical development is a \emph{survival-process representation} that recasts the optimization of Pollak's minimax criterion over stopping times as an equivalent linear variational optimization over admissible survival processes. Although this formulation is infinite-dimensional, it establishes the existence of an optimizer and provides an exact characterization of the finite-γ Pollak minimax value. This characterization, in turn, provides a principled basis for constructing computable stopping rules whose performance can be made arbitrarily close to the optimum. The resulting rules are driven by a recursively updated weighted likelihood-ratio statistic with generally time-varying injections and boundaries. Importantly, this structure is not imposed a priori: the optimization is carried out over the full class of randomized, history-dependent stopping rules, and the Shiryaev--Roberts form emerges naturally from the solution. In particular, the classical Shiryaev--Roberts recursion arises as the time-homogeneous special case. Finally, under a likelihood-ratio floor condition, the framework yields closed-form exact minimax solutions for a nontrivial class of change models.
ER -