The complexity of tracking a stopping time

We present a generalization of the well-known Bayesian change-point detection problem. Specifically, let {(X_i,Y_i)} _i≥1 be a sequence of pairs of random variables, and let S be a stopping time with respect to {X_i}_i≥1. We assume that the (X_i,Y_i)'s take values in the same finite alphabet X × Y. For a fixed κ ≥ 1, we consider the problem of finding a stopping time T ≤ κ, with respect to {Y_i}_i≥1 that optimally tracks S, in the sense that T minimizes the average reaction time E(T - S)⁺, while it keeps the false-alarm probability ℙ(T < S) below a given threshold α ε [0, 1]. In previous work, we presented an algorithm that computes the optimal expected reaction times for all α ε [0, 1] such that α ≥ ℙ(S > κ), and constructs the associated optimal stopping times T. In this paper, we provide a sufficient condition on {(X_i,Y_i)}_i≥1 and S under which the algorithm running time is polynomial in κ, and we illustrate this condition with two examples: a Bayesian change-point problem and a pure tracking stopping time problem.