Pith. sign in

REVIEW 2 major objections 6 minor 1 cited by

Sequential Change Detection for Learning in Piecewise Stationary Bandit Environments

T0 review · 2 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Finite-horizon change detection with unknown pre- and post-change distributions is solved by GLR/GSR tests with $O(\log T)$ latency and controlled false alarms.

desk verdict Solid building-block paper: finite-horizon latency bounds for GLR/GSR with unknown distributions are credible and useful; needs minor statement fixes and an explicit assumption about knowing Delta and sigma^2. read the letter →

arxiv 2501.10974 v3 pith:PNJN44DF submitted 2025-01-19 cs.IT cs.SYeess.SYmath.ITstat.OT

Yu-Han Huang , Venugopal V. Veeravalli This is my paper · ORCID
classification cs.ITcs.SYeess.SYmath.ITstat.OT MSC 62L1062L1594A13
keywords quickestchangedetectionpiecewisestationarybanditsgeneralizedlikelihoodratiotestShiryaev-Robertsfinite-horizonlatencysub-Gaussianconcentrationfalsealarmcontrol
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Sequential change detection in a finite horizon is the bottleneck problem for piecewise-stationary bandits: the agent must notice when a payoff distribution changes, without knowing the distributions in advance. This paper targets a finite-horizon latency guarantee, namely the smallest window $d$ such that for every possible change point the probability the detector is more than $d$ steps late is at most $\delta_D$, while the probability of a false alarm over the whole horizon is at most $\delta_F$. The authors propose a generalized likelihood ratio test and a generalized Shiryaev-Roberts test that use Gaussian likelihoods of known variance in place of the unknown densities, and stop on logarithmically growing thresholds. They prove that both tests meet the two probability guarantees with latency $O(\log T + \log(1/\delta_F) + \log(1/\delta_D))$, matching the known-distribution lower bound in its dependence on the horizon; when the pre-change distribution is also unknown, the same guarantee holds given a pre-change window of samples whose length depends on the noise variance and the mean shift. If correct, this is exactly the property that keeps change-detection latency from dominating the regret of piecewise-stationary bandit algorithms.

What carries the argument

The carrying object is the GLR statistic built by replacing unknown densities with Gaussian densities of known variance $\sigma^2$: $G_n$ in (8) when only the post-change distribution is unknown, and $\tilde G_n$ in (17) when both are unknown; the GSR statistics $W_n$ and $\tilde W_n$ are the summed analogues. Lemmas 1 and 4 rewrite these log-statistics as KL divergences between empirical means of blocks, turning detection into a repeated two-sample mean problem. False-alarm control comes from mixture-martingale concentration inequalities applied through a maximal inequality for nonnegative supermartingales, yielding the logarithmic thresholds in (10), (15), (19), and (22). Late-detection control uses a two-sample sub-Gaussian concentration inequality comparing the pre-window mean with the post-change block mean; the pre-change window of length $m$ supplies enough clean samples for that comparison when the pre-change distribution is unknown.

What would settle it

Run the fully unknown GLR test (18) for pre-change $N(0,1)$ and post-change $N(1,1)$, set $T=10^5$, $\delta_F=\delta_D=0.01$, and choose $m$ exactly equal to $8\sigma^2\beta(T,\delta_F)/\Delta^2$ as allowed by (23); compute the latency $d$ from (24) and simulate enough trials to check whether $P_\nu(\tau\ge\nu+d)\le\delta_D$ holds. At equality the denominator $\Delta^2m-8\sigma^2\beta(T,\delta_F)$ is zero, so the bound (24) is not finite and the theorem as stated fails to give a usable latency at its own boundary condition.

Watch

Extended reading notes

Core claim

The paper's central claim is that the finite-horizon quickest change detection problem with unknown pre- and post-change distributions has explicit, order-optimal tests. In the model where the post-change density is unknown but the pre-change density is known, Theorem 1 gives $d=\left\lceil \frac{2\sigma^2}{\Delta^2}\left(\sqrt{\beta(T,\delta_F)}+\sqrt{\log(2/\delta_D)}\right)^2\right\rceil$ and shows that for the GLR test (9) and GSR test (14), $P_\infty(\tau\le T)\le\delta_F$ and $P_\nu(\tau\ge\nu+d)\le\delta_D$ for every $\nu\le T-d$. When both densities are unknown but $\sigma^2$-sub-Gaussian, Theorem 2 provides the same two guarantees with a pre-change window $m\ge\frac{8\sigma^2}{\Delta^2}\beta(T,\delta_F)$ and a latency $d$ given by (24) for the GLR test (18) and GSR test (21). Corollary 1 then proves that if $\delta_F\le\delta_D$, the choice $m=\left\lceil\frac{16\sigma^2}{\Delta^2}\beta(T,\delta_F)+\log(1/\delta_D)\right\rceil$ yields $d=O(\log T+\log(1/\delta_F)+\log(1/\delta_D))$, which is exactly Property 1. Thus the main discovery is that unknown reward distributions cost only constant and log-log factors, not a worse order of latency, relative to the known-distribution CuSum benchmark.

Load-bearing premise

The detector must know the noise level and a usable lower bound on the size of the mean shift it is trying to catch; without such a bound the required pre-change window cannot be certified, and the boundary case of Theorem 2 needs a strict inequality for its latency formula to stay finite.

Editorial extensions

If this is right

  • Plugging the GLR or GSR test into a piecewise-stationary bandit contributes only $O(\log T)$ latency to the regret, because the test achieves the known-distribution lower bound in its dependence on the horizon.
  • Setting $\delta_F=\delta_D=T^{-\gamma}$ with $\gamma>1$, as regret analyses do, makes the latency $O(\log T)$, so the detection module is not the bottleneck.
  • When the post-change distribution is unknown but the pre-change distribution is known, no pre-change window is needed, and the finite-horizon guarantee holds from the first observation.
  • The simulations with $N(0,1)$ pre-change and $N(1,1)$ post-change data show empirical latencies growing logarithmically with $T$ and $1/\delta$, matching the theorem's rates, while the fully unknown upper bound is looser than the partially unknown one.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A practical bandit designer must treat the unknown gap $\Delta$ as an input: the detector's window and thresholds are chosen from the smallest mean shift the algorithm promises to detect, so a mismatch with the true gap voids the certificate.
  • The implemented down-sampled GLR in the experiments, which restricts the supremum to the last 700 observations, has no separate proof; the theory covers the full supremum, so using the down-sampled version in a deployed algorithm is an unsupported approximation.
  • The looseness of Theorem 2's bound relative to simulation suggests the true fully-unknown latency is closer to the known-distribution rate; a sharper analysis of the pre-change window or a better threshold could close the gap.
  • Because the window guarantee applies only to change points after $m$, a bandit algorithm that restarts after each detected change should treat the first $m$ samples of each segment as unprotectable exploration.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. This paper studies a finite-horizon formulation of quickest change detection with a latency metric, defined as the smallest n such that the probability that the detection delay exceeds n is at most δ_D, while the false-alarm probability over the horizon is at most δ_F. The pre- and post-change observations are assumed σ²-sub-Gaussian. Section III treats the case where the pre-change distribution is known and the post-change distribution is unknown, proposing GLR and GSR tests with time-varying thresholds and proving in Theorem 1 explicit bounds on false-alarm probability and delay of order O((σ²/Δ²)(log T + log(1/δ_F) + log(1/δ_D))). Section IV treats the case where both distributions are unknown, assuming a pre-change window of length m, and proves in Theorem 2 a similar finite-horizon guarantee under condition (23); Corollary 1 gives a specific choice of m and claims Property 1. Section V reports simulations for downsampled versions of the GLR tests and compares their empirical latencies with the theorem bounds.

Significance. If the condition in Theorem 2 is corrected and the dependence on the unknown change gap is stated explicitly, the paper gives useful explicit finite-horizon false-alarm and latency bounds for GLR/GSR change detectors in the unknown-distribution setting relevant to piecewise-stationary bandits. The latency order O(log T) matches the lower bound from the authors' prior work [12]. The proof machinery is largely sound and internally consistent: the GLR statistic is reduced to empirical-mean KL divergences in Lemmas 1 and 4, concentration is handled by Lemma 2 (borrowed from mixture-martingale arguments) and Lemma 5 (from [7]), and the GSR false-alarm bound is elegantly reduced to the GLR bound. The paper is open about the looseness of the Theorem 2 bound. However, the main unknown-distribution guarantee depends on quantities that the tests do not know or estimate, which currently weakens the claim that Property 1 is achieved in an implementable sense.

major comments (2)
  1. [Section IV, Eqs. (23)-(24) and Appendix B, Eq. (48)] Theorem 2 is stated with the condition m ≥ 8σ²β(T,δ_F)/Δ², but the first term of d in (24) has denominator Δ²m − 8σ²β(T,δ_F), which is zero at equality; at equality the bound is undefined/infinite. The proof in Appendix B, specifically the chain leading to the empty intersection in (48), requires the strict inequality m > 8σ²β(T,δ_F)/Δ². The theorem statement should be corrected to use the strict inequality, and the text should note that Corollary 1's choice of m satisfies this strict condition.
  2. [Section IV, Eq. (23) and Corollary 1; also Theorem 1, Eq. (16)] The window length m that certifies the finite-horizon guarantee depends on the unknown change gap Δ, and the delay d in both Theorem 1 and Theorem 2 also depends on Δ; for example, Corollary 1 chooses m = ceil(16σ²β(T,δ_F)/Δ² + log(1/δ_D)). The stated assumptions only give σ²-sub-Gaussianity and Δ>0, and the proposed tests do not estimate Δ or σ². Consequently, from the stated assumptions alone no finite m can be selected that is guaranteed to satisfy (23): for any fixed m, an environment with a smaller Δ violates (23). The paper should either explicitly assume that a lower bound on Δ is known to the system designer (and similarly that σ² is known), or reformulate Theorem 2 and Corollary 1 as conditional results with the caveat that m is not computable from the observations alone.
minor comments (6)
  1. [Section II, Eq. (2)] The definition of latency contains a typo: "inf{n:∈ {1, . . . , T}" should read "inf{n ∈ {1, . . . , T}:".
  2. [Appendix A, Eq. (40)] In the split of the absolute-value probability, the second term is printed identically to the first: both read "Pν( ˆµν:ν+d−1 − µ1 ≥ sqrt(...))" in the manuscript. The second term should be the complement event with "≤ −sqrt(...)", since the correct bound follows from the two-sided Chernoff bound.
  3. [Section V, Eqs. (26)-(29)] The simulated tests τ'_GLR and \tilde τ'_GLR use the downsampled statistics G'_n and \tilde G'_n, which are pointwise smaller than the exact GLR statistics G_n and \tilde G_n analyzed in Theorems 1 and 2. Since downsampling delays detection, the empirical latencies are not direct realizations of the analyzed stopping times, and the comparison with the theorem bounds in Figures 1 and 2 is not a direct validation of those bounds. The text should state this explicitly and, if feasible, compare with the exact statistics or with an adjusted bound.
  4. [Section V, Figure 2 caption] The caption says "varying δ ∈ {5000,10000,20000,50000,100000} where δ_F = δ_D = δ", but δ is a probability in (0,1); the listed values are inconsistent. This appears to be a typo, likely for reciprocal values such as 1/5000, 1/10000, etc.
  5. [Section I, Introduction] The sentence "the closest variant of the QCD problem to our work appears in [?]" contains an unresolved citation placeholder; a reference should be supplied.
  6. [Section V, simulation setup] The set of change-points N is defined as {m+1+nT/10: n∈N, m+1+nT/10≤T} without also requiring ν≤T−d. For Theorem 2 the guarantee is stated only for ν∈{m+1,...,T−d}, so some simulated change-points may lie outside the range where the bound applies; the set should be restricted, or the authors should explain why the unrestricted set does not affect the comparison.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the GLR/GSR latency bounds are derived from concentration inequalities, and the only self-cited lower bound is independent support rather than a circular input.

full rationale

The derivation chain is self-contained for the core bounds. Theorem 1 is proved from the GLR/GSR statistics, Lemma 1, Lemma 2 (via the mixture-martingale inequality of [16]), and standard sub-Gaussian Chernoff bounds; the latency expression (16) is a derived upper bound, not a fitted parameter or a restatement of the latency definition. Theorem 2 likewise follows from Lemma 4, Lemma 5 from [7], and explicit choices of m and d; Corollary 1 is an algebraic consequence of those choices, not a circular redefinition. The only self-citation is the Omega(log T) lower bound from the authors' prior work [12], used to label the O(log T) latency as order-optimal. That lower bound is a parameter-free theorem for the known-distribution case, its assumptions do not include the unknown-distribution upper-bound results of this paper, and it is independent of the new proofs, so it is real evidence rather than a circular reduction. There are non-circular caveats worth noting: Theorem 2 is stated with m >= 8 sigma^2 beta / Delta^2, while the proof uses m > 8 sigma^2 beta / Delta^2, and equality would make the denominator in (24) vanish; also, the choice of m in Corollary 1 depends on the unknown gap Delta and on sigma^2, so the implementable guarantee requires the designer to know (or have a lower bound on) Delta and to know sigma^2. These are correctness and implementability concerns, not circularity, and they do not affect the circularity score.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central results rest on two sets of inputs: standard concentration inequalities cited from Besson et al., Kaufmann and Koolen, and Ville, and problem-specific assumptions (sub-Gaussianity, known sigma^2, known or lower-bounded change gap Delta, and a long enough pre-change window). No parameters are fitted to data; the constants in the thresholds are proof-design constants inherited from the cited inequalities. The heaviest extra load is the dependence of the pre-change window requirement on the unknown Delta.

assumptions (6)
  • standard math Ville's inequality for nonnegative supermartingales is valid.
    Used in Appendix A, proof of Lemma 2, equation (35), to turn a supermartingale bound into a tail bound.
  • standard math The mixture martingale lemma from Kaufmann and Koolen (Lemma 3 in [16]) holds with constant c = 5/4 log(pi^2/3 / (log(5/4))^2).
    Used in Appendix A, Lemma 2, to associate the empirical-mean process with a nonnegative martingale Z(t).
  • standard math The two-sample sub-Gaussian concentration inequality from Besson et al. (Lemma 5 in [7]) holds.
    Used in Appendix B, equations (46) and (49), to bound the late-detection probability in Theorem 2.
  • domain assumption The observations are independent and sigma^2-sub-Gaussian, and the pre- and post-change means differ by Delta > 0.
    Stated in Section II; the whole analysis and the definitions of latency and change gap rest on this.
  • domain assumption The detector knows the variance parameter sigma^2 and uses Gaussian likelihoods with that variance in the GLR and GSR statistics.
    The statistics in equations (8), (13), (17), and (20) are not computable without sigma^2, yet the paper never states this requirement explicitly.
  • ad hoc to paper A pre-change window of length m exists (nu > m), and for Theorem 2 the window must satisfy m >= 8 sigma^2 / Delta^2 beta(T, delta_F), which depends on the unknown change gap Delta.
    Theorem 2 and Corollary 1 require this condition; without a known lower bound on Delta the agent cannot certify that enough pre-change samples are available.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sequential Change Detection for Learning in Piecewise Stationary Bandit Environments." pith.science (2026). https://pith.science/paper/PNJN44DF

@misc{pith2026250110974,
  author       = {Pith},
  title        = {Pith review of: Sequential Change Detection for Learning in Piecewise Stationary Bandit Environments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PNJN44DF}},
  note         = {Machine review of arXiv:2501.10974}
}
read the original abstract

A finite-horizon variant of the quickest change detection problem is investigated, which is motivated by a change detection problem that arises in piecewise stationary bandits. The goal is to minimize the \emph{latency}, which is smallest threshold such that the probability that the detection delay exceeds the threshold is below a desired low level, while controlling the false alarm probability to a desired low level. When the pre- and post-change distributions are unknown, two tests are proposed as candidate solutions. These tests are shown to attain order optimality in terms of the horizon. Furthermore, the growth in their latencies with respect to the false alarm probability and late detection probability satisfies a property that is desirable in regret analysis for piecewise stationary bandits. Numerical results are provided to validate the theoretical performance results.

Figures

Figures reproduced from arXiv: 2501.10974 by the authors.

Figure 1
Figure 1. Latencies of τ ′ GLR and τ˜ ′ GLR with fixed δF = δD = 0.01 and varying T ∈ {5000, 10000, 20000, 50000, 100000}. 100 (1 − δD) th percentile of the recorded detection delays over all change-points in N . The collection of change-points N is set to {m + 1 + nT /10 : n ∈ N, m + 1 + nT /10 ≤ T}, as conducting 200000 trials over all possible change-points is cumbersome. To implement the GLR tests in (9) and (18), we need… view at source ↗
Figure 2
Figure 2. Latencies of τ ′ GLR and τ˜ ′ GLR with fixed T = 10000 and varying δ ∈ {5000, 10000, 20000, 50000, 100000} where δF = δD = δ. Nevertheless, the upper bound in Theorem 2 is loose compared to that in Theorem 1, as the gap between the simulated value and the upper bound is wider when the pre- and post￾change distributions are unknown. We can also see that the gap between the latency of the TVT-CuSum test and that of th… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Cost of Learning Under Multiple Change Points

    stat.ML 2026-02 conditional novelty 6.0 of 10

    An anytime CUSUM tracker with a logarithmically growing threshold achieves O(σ²(S+1) log T) dynamic regret for piecewise-constant mean tracking and nearly matches a new Ω(σ²(S+1) log(T/(S+1))) minimax lower bound.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages · cited by 1 Pith paper

  1. [12]

    High probability latency quickest change detection over a finite horizon,

    Y .-H. Huang and V . V . Veeravalli, “High probability latency quickest change detection over a finite horizon,” in2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 2024, pp. 1047–1052

    work page 2024

  2. [13]

    Sequential change-point detection when the pre- and post-change parameters are unknown,

    T. L. Lai and H. Xing, “Sequential change-point detection when the pre- and post-change parameters are unknown,”Sequential analysis, vol. 29, no. 2, pp. 162–175, 2010

    work page 2010

  3. [7]

    Efficient change-point detection for tackling piecewise-stationary bandits,

    L. Besson, E. Kaufmann, O.-A. Maillard, and J. Seznec, “Efficient change-point detection for tackling piecewise-stationary bandits,”The Journal of Machine Learning Research, vol. 23, no. 1, pp. 3337–3376, 2022

    work page 2022

  4. [1]

    H. V . Poor and O. Hadjiliadis,Quickest detection. Cambridge Univer- sity Press, 2009

    work page 2009

  5. [2]

    A. G. Tartakovsky, I. V . Nikiforov, and M. Basseville,Sequential Analysis: Hypothesis Testing and Change-Point Detection, ser. Statistics. CRC Press, 2014

    work page 2014

  6. [3]

    Quickest change detection,

    V . V . Veeravalli and T. Banerjee, “Quickest change detection,” in Academic press library in signal processing: Array and statistical signal processing. Cambridge, MA: Academic Press, 2013

    work page 2013

  7. [4]

    Sequential (quickest) change detection: Classical results and new directions,

    L. Xie, S. Zou, Y . Xie, and V . V . Veeravalli, “Sequential (quickest) change detection: Classical results and new directions,”IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 2, pp. 494–514, 2021

    2021

  8. [5]

    A change-detection based framework for piecewise-stationary multi-armed bandit problem,

    F. Liu, J. Lee, and N. Shroff, “A change-detection based framework for piecewise-stationary multi-armed bandit problem,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1, 2018

    work page 2018

Show all 19 references
  1. [6]

    Nearly optimal adaptive procedure for piecewise-stationary bandit: a change-point detection approach,

    Y . Cao, W. Zheng, B. Kveton, and Y . Xie, “Nearly optimal adaptive procedure for piecewise-stationary bandit: a change-point detection approach,”AISTATS, Okinawa, Japan, 2019

    2019

  2. [8]

    Controlling a Markov decision process with an abrupt change in the transition kernel,

    N. Dahlin, S. Bose, and V . V . Veeravalli, “Controlling a Markov decision process with an abrupt change in the transition kernel,” in2023 American Control Conference (ACC). IEEE, 2023, pp. 3401–3408

    2023

  3. [9]

    Near-optimal algorithms for piecewise-stationary cascading bandits,

    L. Wang, H. Zhou, B. Li, L. R. Varshney, and Z. Zhao, “Near-optimal algorithms for piecewise-stationary cascading bandits,” inICASSP 2021- 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021, pp. 3365–3369

    2021

  4. [10]

    A near-optimal change-detection based algorithm for piecewise-stationary combinatorial semi-bandits,

    H. Zhou, L. Wang, L. Varshney, and E.-P. Lim, “A near-optimal change-detection based algorithm for piecewise-stationary combinatorial semi-bandits,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, 2020, pp. 6933–6940

    2020

  5. [11]

    Nonstationary re- inforcement learning with linear function approximation,

    H. Zhou, J. Chen, L. R. Varshney, and A. Jagmohan, “Nonstationary re- inforcement learning with linear function approximation,”arXiv preprint arXiv:2010.04244, 2020

    2010 arXiv

  6. [14]

    Change detection-based procedures for piecewise stationary mabs: A modular approach,

    Y .-H. Huang, A. Gerogiannis, S. Bose, and V . V . Veeravalli, “Change detection-based procedures for piecewise stationary mabs: A modular approach,”arXiv preprint arXiv:2501.01291, 2025

    2025

  7. [15]

    Information bounds and quick detection of parameter changes in stochastic systems,

    T. L. Lai, “Information bounds and quick detection of parameter changes in stochastic systems,”IEEE Transactions on Information theory, vol. 44, no. 7, pp. 2917–2929, 1998

    1998

  8. [16]

    Mixture martingales revisited with applications to sequential tests and confidence intervals,

    E. Kaufmann and W. M. Koolen, “Mixture martingales revisited with applications to sequential tests and confidence intervals,”The Journal of Machine Learning Research, vol. 22, no. 1, pp. 11 140–11 183, 2021

    2021

  9. [17]

    A. N. Shiryaev,Optimal stopping rules. Springer Science & Business Media, 2007, vol. 8

    2007

  10. [18]

    Ville,Etude critique de la notion de collectif

    J. Ville,Etude critique de la notion de collectif. Gauthier-Villars Paris, 1939. APPENDIXA PROOF OFTHEOREM1 There are two change detectors to consider: the GLR and GSR tests. For each test, there are two parts to prove: the false alarm probabilityP ∞ (τ≤T)and the late detectio...

    1939

  11. [19]

    Lemma 3(Lemma 13 from [16]).Letc := 5 4 log π2/3 (log(5/4))2

    to construct the associated supermartingale. Lemma 3(Lemma 13 from [16]).Letc := 5 4 log π2/3 (log(5/4))2 . For anyx >0, there exists a nonnegative (mixture) martingale Z(t)such thatZ(0) = 1and for anyx >0andn∈N, {Y(n)−c≥x} ⊆ n Z(n)≥e 4x 5 o .(33) Continuing with the proof of ...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.