{"id":"dfa6c227-6d11-44be-a85a-e348935e986e","arxiv_id":"2501.10974","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New GLR and GSR tests for unknown pre- and post-change reward distributions achieve order-optimal logarithmic latency in piecewise stationary bandits.","lead":"This paper builds change-detection tests that spot when a bandit arm's reward distribution changes even when the new distribution is unknown. The tests provably detect changes with delay that grows only logarithmically with time and error levels, which is the best possible order.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The finite-horizon guarantee for the unknown-distribution tests is conditional on knowing σ² and on a pre-change window m that depends on the unknown gap Δ; Theorem 2 also needs a strict inequality to keep d finite.","rationale":"The central claim is that the GLR/GSR tests attain O(log T + log(1/δF) + log(1/δD)) latency with only σ²-sub-Gaussianity assumed. What must be true for this claim to hold is that the theorem's condition on m can be met without knowing the distributions. The paper does not establish this: m in (23) and Corollary 1 depends on Δ, which is part of the unknown post-change mean. For any fixed m, one can choose Δ small enough to violate (23), so the guarantee is not uniform over the assumed class. This is a genuine gap between the theorem and the stated PS-bandit motivation, not merely a tightness issue. The strict ≥ in Theorem 2 is a related concrete defect: at equality the d formula is undefined, and Appendix B explicitly assumes m > 8σ²β/Δ². I checked the main concentration arguments in Appendices A and B; apart from typographical slips (duplicated term in (40), a 25/32 constant in (52), unresolved '[?]' citation), the inequalities are consistent, so the theorems are likely repairable by adding an explicit lower-bound assumption on Δ and requiring strict inequality. The reader's CONDITIONAL verdict already captures this; my stress test does not move it.","tokens_in":18643,"tokens_out":23621,"duration_ms":240293,"concrete_test":"Analytical check: attempt to instantiate Theorem 2 and Corollary 1 using only the assumptions in Section II (σ²-sub-Gaussian, Δ>0, no lower bound on Δ). Show that for every finite m there exists a σ²-sub-Gaussian pair with Δ < sqrt(8σ²β(T,δF)/m), so (23) fails and the guaranteed d in (24) is not available. Also evaluate d at m = 8σ²β(T,δF)/Δ²: the denominator is zero, so the theorem statement must require strict inequality. If the authors confirm that a lower bound on Δ is assumed, the practical guarantee is restricted accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 1 and Theorem 2 claim a finite-horizon false-alarm/latency guarantee when pre- and post-change distributions are unknown. The guarantee is stated for a pre-change window m satisfying (23), i.e. m ≥ 8σ²β(T,δF)/Δ², and Corollary 1 chooses m = ceil(16σ²β(T,δF)/Δ² + log(1/δD)). But Δ = |μ0−μ1| is the unknown change gap, and σ² is also assumed known; the tests themselves do not estimate either. Thus, from only the stated assumptions (σ²-sub-Gaussian, Δ>0), no finite m can be selected that certifies the latency: for any chosen m, a smaller Δ can violate (23). The paper needs to state explicitly that Δ (or a lower bound) and σ² are known to the system designer, otherwise Property 1 is not an implementable guarantee. Additionally, Theorem 2 states m ≥ in (23), but d in (24) has denominator Δ²m−8σ²β(T,δF), which vanishes at equality; the proof in Appendix B uses m > 8σ²β/Δ². This is an internal inconsistency in the theorem statement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18824,"tokens_out":9848,"duration_ms":109041,"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":[{"comment":"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.","section":"Section IV, Eqs. (23)-(24) and Appendix B, Eq. (48)"},{"comment":"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.","section":"Section IV, Eq. (23) and Corollary 1; also Theorem 1, Eq. (16)"}],"minor_comments":[{"comment":"The definition of latency contains a typo: \"inf{n:∈ {1, . . . , T}\" should read \"inf{n ∈ {1, . . . , T}:\".","section":"Section II, Eq. (2)"},{"comment":"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.","section":"Appendix A, Eq. (40)"},{"comment":"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.","section":"Section V, Eqs. (26)-(29)"},{"comment":"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.","section":"Section V, Figure 2 caption"},{"comment":"The sentence \"the closest variant of the QCD problem to our work appears in [?]\" contains an unresolved citation placeholder; a reference should be supplied.","section":"Section I, Introduction"},{"comment":"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.","section":"Section V, simulation setup"}],"recommendation":"major_revision","confidential_remarks":"The paper is on a sound track and the core proof strategy is credible. The main issues are local but load-bearing: the strict-inequality mismatch in Theorem 2 and the unstated dependence of m and d on the unknown gap Δ. Both can be fixed within the manuscript's scope by an explicit assumption (e.g., a known lower bound on Δ) and a corrected theorem statement. The simulation section is better described as an illustration than as a direct validation of the exact tests. The reliance on the authors' prior work [12] for the latency definition and lower bound is appropriate and does not raise a circularity concern. The missing reference placeholder should be resolved before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid, narrowly scoped theory paper. It gives finite-horizon high-probability latency bounds for GLR and GSR change detectors when pre- and post-change distributions are unknown, matching the O(log T) lower bound from the authors' earlier ISIT paper. That result is genuinely new as far as I can tell: [12] assumed known distributions and [13] used expected-delay metrics. The main proof chains in Appendices A and B check out, and the false-alarm argument via mixture martingales is clean.\n\nWhat deserves credit: the paper is honest about being a building block rather than a complete bandit algorithm, the threshold design follows Besson et al. and Kaufmann-Koolen, and the finite-horizon treatment is theirs. The delay bound in Theorem 2 is derived rather than fitted, and the simulations, though downsampled, do track the predicted logarithmic growth.\n\nSoft spots, in order of importance. First, Theorem 2 states m >= 8 sigma^2 beta / Delta^2, but the proof and the denominator in d require strict >; at equality the first term in d blows up. That is a minor statement fix but should be corrected. Second, and more substantive, the guarantee is conditional on knowing sigma^2 and on choosing m proportional to beta / Delta^2, where Delta is the unknown change gap. The paper assumes Delta > 0 but never says the designer needs a lower bound on Delta to choose m. Without that, Property 1 is not implementable. This is not a flaw in the math, but it is a missing caveat in the interpretation. Third, the closest-work citation is an unresolved '[?]', which makes the novelty claim hard to verify; the authors should fix that before publication. The experiments use a downsampled GLR statistic, so they validate the qualitative trend but not the exact constants; the paper acknowledges this, but readers should not over-read Figures 1 and 2.\n\nThe self-citation to [12] is appropriate because the lower bound genuinely comes from there. There are no fitted parameters and no circularity.\n\nWho this is for: people designing change-detection-based PS bandit algorithms, and QCD theorists interested in finite-horizon metrics. It deserves a serious referee: the core result is credible and useful, and the issues are fixable. I would send it to review and ask for the strict inequality, a discussion of the Delta/sigma^2 assumptions, and the reference cleanup.","headline":"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.","tokens_in":19384,"tokens_out":1501,"would_cite":true,"duration_ms":16767,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L10","62L15","94A13"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["quickest change detection","piecewise stationary bandits","generalized likelihood ratio test","Shiryaev-Roberts","finite-horizon latency","sub-Gaussian concentration","false alarm control"],"falsifier":"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.","tokens_in":18341,"feed_emoji":"🎰","tokens_out":11361,"duration_ms":106457,"temperature":0.7,"pith_summary":"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.","feed_headline":"Unknown reward shifts detected in provably log-time latency","feed_subtitle":"GLR and GSR tests keep false alarms and late detections in check even when reward distributions are unknown.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the finite-horizon latency metric and the TVT-CuSum test; its known-distribution lower bound is the benchmark the new tests must match.","marker":"[12]"},{"why":"Introduces the pre-change window of length m for unknown pre-change parameters, used in Section IV.","marker":"[13]"},{"why":"Provides the change-detection approach for piecewise-stationary bandits and the two-sample sub-Gaussian concentration inequality (Lemma 5) used to bound late detection.","marker":"[7]"},{"why":"Casts GLR as the standard tool for detecting unknown post-change parameters; the GLR statistics generalize this method.","marker":"[15]"},{"why":"Supplies the mixture-martingale construction whose concentration inequality controls the false-alarm probability in Theorem 1 and Theorem 2.","marker":"[16]"},{"why":"Provides the CuSum and Shiryaev-Roberts statistics and the QCD framework that the GLR and GSR tests generalize.","marker":"[3]"},{"why":"Introduces the Shiryaev-Roberts statistic, the basis of the GSR tests in (14) and (21).","marker":"[17]"},{"why":"Provides the maximal inequality for nonnegative supermartingales used with the mixture martingale to turn concentration bounds into false-alarm control.","marker":"[18]"},{"why":"Uses change-detection latency in piecewise-stationary bandit regret analysis with $\\delta_F$ and $\\delta_D$ set to $T^{-\\gamma}$, motivating Property 1.","marker":"[14]"}],"fun_headline_variants":["Unknown reward shifts? GLR/GSR tests hit log-time","Order-optimal latency for unknown-distribution bandit shifts","Quickest change detection with unknown pre/post distributions","GLR/GSR tests: unknown rewards, provably minimal latency","Order-optimal change detection for piecewise stationary bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Unknown reward shifts? GLR/GSR tests hit log-time","Order-optimal latency for unknown-distribution bandit shifts","Quickest change detection with unknown pre/post distributions","GLR/GSR tests: unknown rewards, provably minimal latency","Order-optimal change detection for piecewise stationary bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000957,"raw_usage":{"total_tokens":4117,"prompt_tokens":1019,"completion_tokens":3098,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":3014}},"tokens_in":635,"tokens_out":3098,"duration_ms":22683,"temperature":1.0,"reasoning_tokens":3014,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:47:41.372113+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"High probability latency quickest change detection over a finite horizon,","cited_arxiv_id":null,"evidence_quote":"Defines the finite-horizon latency metric and the TVT-CuSum test; its known-distribution lower bound is the benchmark the new tests must match."},{"cited_title":"Sequential change-point detection when the pre- and post-change parameters are unknown,","cited_arxiv_id":null,"evidence_quote":"Introduces the pre-change window of length m for unknown pre-change parameters, used in Section IV."},{"cited_title":"Efficient change-point detection for tackling piecewise-stationary bandits,","cited_arxiv_id":null,"evidence_quote":"Provides the change-detection approach for piecewise-stationary bandits and the two-sample sub-Gaussian concentration inequality (Lemma 5) used to bound late detection."},{"cited_title":"Mixture martingales revisited with applications to sequential tests and confidence intervals,","cited_arxiv_id":null,"evidence_quote":"Supplies the mixture-martingale construction whose concentration inequality controls the false-alarm probability in Theorem 1 and Theorem 2."},{"cited_title":"Quickest change detection,","cited_arxiv_id":null,"evidence_quote":"Provides the CuSum and Shiryaev-Roberts statistics and the QCD framework that the GLR and GSR tests generalize."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Shiryaev-Roberts statistic, the basis of the GSR tests in (14) and (21)."},{"cited_title":"Ville,Etude critique de la notion de collectif","cited_arxiv_id":null,"evidence_quote":"Provides the maximal inequality for nonnegative supermartingales used with the mixture martingale to turn concentration bounds into false-alarm control."},{"cited_title":"Change detection-based procedures for piecewise stationary mabs: A modular approach,","cited_arxiv_id":null,"evidence_quote":"Uses change-detection latency in piecewise-stationary bandit regret analysis with $\\delta_F$ and $\\delta_D$ set to $T^{-\\gamma}$, motivating Property 1."}],"review_version":1}