Pith. sign in

REVIEW 5 major objections 6 minor 15 references

Early Stopping in Contextual Bandits and Inferences

T0 review · 5 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read A batched inverse-variance-weighted estimator lets bandit experiments stop early and still support post-hoc inference.

desk verdict Interesting setup and a genuinely new combination, but Corollary 3's CLT is off by a factor of n and the variance estimator is off by n, so the online stopping and post-stopping inference claims do not hold as written. read the letter →

arxiv 2502.02793 v1 pith:WPCLEJKH submitted 2025-02-05 math.ST math.OCmath.PRstat.MLstat.TH

Zihan Cui (University of Michigan) This is my paper · ORCID
classification math.STmath.OCmath.PRstat.MLstat.TH MSC 62L0562F12
keywords contextualbanditsearlystoppingbatchedOLSinverse-varianceweightingconditionalinferenceregretboundssequentialsamplingasymptoticnormality
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

In linear contextual bandits where each observation costs money, this paper asks when an experiment can stop sampling early without losing the ability to draw conclusions. It proposes pre-determined stopping rules that use tail bounds on online least-squares estimators to bound regret as a function of batch index, and online stopping rules that stop when the estimated variance of an inverse-variance-weighted batched estimator falls below a threshold or stops improving. The paper's central claim is that this symmetric combination of batched OLS estimators is asymptotically normal, and that conditional on the realized stopping time it behaves like a truncated Gaussian. That makes it possible, in principle, to construct confidence intervals and tests after early stopping, using a Markov-chain Monte Carlo sampling procedure under the stopping constraint. If the claims hold, experimenters could reduce sampling cost while retaining statistically valid conclusions.

What carries the argument

The load-bearing object is the inverse-variance-weighted batched OLS estimator $\hat{\beta}^{\mathrm{IVW}}_{t,1}=(\sum_{j=1}^t X_{j,1})^{-1}\sum_{j=1}^t X_{j,1}\hat{\beta}^{\mathrm{OLS}}_{j,1}$ (one for each arm), together with its consistent variance estimator $\hat{\Sigma}_{t,1}=n(\sum_{j=1}^t X_{j,1})^{-1}\sigma^2$. Theorem 4 supplies the asymptotic normality of the batched score sequence via a martingale central limit theorem; Corollary 3 rescales that into the estimator's convergence. The stopping rules are then deterministic functions of $\|\hat{\Sigma}_{t,1}\|$ (threshold and opportunity cost), which is what makes the conditional distribution of the estimator a truncated Gaussian. On the regret side, Theorem 1 converts estimation-error bounds into a regret bound through a margin condition, and Theorem 2 routes the online stopping threshold through that same bound.

What would settle it

Simulate a two-arm batched contextual bandit with known parameters and known error variance, stop at a fixed threshold on the estimated variance norm, and check whether the empirical coverage of the nominal 95% confidence region conditional on the stopping time approaches 95% as the batch size grows; a systematic shortfall would indicate that the variance scaling on which the stopping thresholds and the truncated-Gaussian approximation rely is wrong.

Watch

Extended reading notes

Core claim

The paper's core claim is that early stopping can be made rigorous in batched linear contextual bandits without sacrificing post-experiment inference. The key object is the inverse-variance-weighted estimator $\hat{\beta}^{\mathrm{IVW}}_{t,1}$ that combines the per-batch OLS estimates; Corollary 3 asserts that $\sqrt{t}(\hat{\beta}^{\mathrm{IVW}}_{t,1}-\beta_1)$ converges to $N(0, n(\Sigma^*_1)^{-1}\sigma^2)$, and that $n(\sum_{j=1}^t X_{j,1})^{-1}\sigma^2$ consistently estimates its variance. The online stopping rules are built directly on this: stop when the norm of the estimated variance is below a threshold, or when one batch's variance improvement falls below an opportunity cost. The paper further argues that because the stopping event is a function of these estimators and their variances, the selected estimator is truncated Gaussian conditionally on the stopping time, permitting sampling-based conditional tests and confidence sets. Regret control is then obtained by Theorem 2, which converts a bound on the covariance norm into a high-probability bound on the regret of the learned policy.

Load-bearing premise

The whole online stopping and post-experiment inference depends on the assumption that the variance estimate computed from the data is exactly proportional to the true variance of the estimator being monitored, so that a small estimated variance really means a small regret bound.

Editorial extensions

If this is right

  • In a batched two-arm linear contextual bandit, an experimenter can stop as soon as the estimated variance of the inverse-variance-weighted estimator falls below a threshold and still have a formal regret bound from Theorem 2.
  • Conditional on the realized stopping time, the chosen online estimator approximately follows a truncated Gaussian law, so confidence regions can be built by Monte Carlo sampling under the stopping constraint.
  • Pre-determined stopping rules make the stopping time a known function of batch index and clipping probabilities, allowing cost-regret trade-offs to be planned before data collection.
  • The same variance-based threshold and opportunity-cost rules transfer to any policy whose update depends only on the batched sufficient statistics, such as epsilon-greedy, upper confidence bound, and Thompson sampling.
  • When the error variance is unknown or heteroskedastic, plugging the residual-based variance estimate into the same stopping rules preserves the procedure in form.

Reading between the lines

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

  • The same variance-based stopping logic could be applied to other low-dimensional online estimators, not just the inverse-variance-weighted combination, whenever their asymptotic covariance can be estimated online.
  • The framework suggests a testable extension to K-arm contextual bandits by treating each arm's estimator separately and stopping only when every arm's variance bound is satisfied.
  • The paper's assumption of i.i.d. contexts could be relaxed to non-stationary contexts as long as a martingale central limit theorem for the batched score process still holds, with time-varying thresholds in the stopping rules.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 6 minor

Summary. The paper studies early stopping in batched linear contextual bandits with two arms. It proposes pre-determined stopping rules based on concentration inequalities and online stopping rules based on the estimated variance of an inverse-variance-weighted estimator. It further proposes a conditional inference procedure after the realized stopping time, based on an asymptotic truncated-Gaussian distribution. The theoretical core is Theorem 1, which converts estimation-error bounds into regret bounds via a margin condition, and Corollary 3, which claims asymptotic normality of the inverse-variance-weighted batched OLS estimator.

Significance. If correct, the paper would offer a useful framework for stopping adaptive experiments early while still providing valid post-experiment inference. The connection between the covariance of an online estimator and the regret of the learned policy is appealing, and the use of batched sufficient statistics is a sensible way to make the problem tractable. The proof of Theorem 1 is clean, and the martingale-CLT route in Theorem 4 is promising. However, the central asymptotic statement in Corollary 3 contains a scaling error that propagates into the online stopping rules and the conditional inference procedure. The error appears repairable, but the current manuscript does not support the claimed online-stopping and post-selection-inference results.

major comments (5)
  1. [§4.2.3, Corollary 3 and Eq. (4.2.2)] The scaling of the CLT is incorrect. Since X_{j,1} = Σ_{i=1}^n 1_{A_{j,i}=1} x_{j,i} x_{j,i}^T is a sum of n terms, S_t = Σ_{j=1}^t X_{j,1} satisfies S_t/(nt) → Σ*_1, and therefore (1/√(nt)) S_t β_1 → √(tn) Σ*_1 β_1, not √(t/n) Σ*_1 β_1 as claimed in the proof. Carrying the correct limit through the Slutsky step gives √(tn)(β̂^IVW_{t,1} − β_1) → N(0, (Σ*_1)^{-1}σ²); equivalently, for fixed n and t → ∞, √t(β̂^IVW_{t,1} − β_1) → N(0, (1/n)(Σ*_1)^{-1}σ²). The claimed limiting covariance n(Σ*_1)^{-1}σ² is therefore n² times too large, and the proposed variance estimator n(Σ_{j=1}^t X_{j,1})^{-1}σ² is n times too large as an estimate of the variance of β̂^IVW_{t,1}. This invalidates the calibration of the online stopping rules in §4.2.3 and the sampling step in §4.2.4.
  2. [§4.2.3, Corollary 3] The statement of Corollary 3 is not a well-defined two-index limit: the right-hand side contains n, which is also tending to infinity. If n is fixed, the theorem should be stated with t → ∞ only; if both n and t diverge, the normalization √t with an n-dependent limiting covariance is not meaningful without a rate condition such as t/n → c. The proof implicitly assumes such a condition, but it is not stated. Please specify the intended asymptotic regime and provide the corresponding CLT and variance estimator.
  3. [§4.2.4, Step 1] Because Corollary 3 is mis-scaled, the conditional inference procedure samples β̃₁ and β̃₀ from the wrong asymptotic distribution. In addition, the claim that conditioning on π_{1:T} can be ignored because the asymptotic covariance in Corollary 3 does not depend on the policies is not justified: unconditional asymptotic normality does not automatically imply asymptotic normality conditional on the data-dependent event {T = t}. The truncation constraint '‖Σ̂_{t,1}‖ ≤ p iff t = T' must be re-derived from the corrected distribution and variance estimator, and the resulting conditional sampling procedure should be stated explicitly.
  4. [§4.1, Online Stopping-Threshold] Lemma 2 and Theorem 2 require the actual covariance V of the estimator to be bounded by k, but the proposed stopping rules use an estimated covariance S_t. If S_t is only a consistent estimator, the event {‖S_t‖ ≤ k} does not by itself imply ‖Cov(β̂_t)‖ ≤ k with high probability at the stopping time. A uniform-in-t confidence bound or an upper-confidence version of the variance estimator is needed to support the claimed regret guarantee.
  5. [Introduction, last paragraph; §4.2.4] The Introduction states that the conditional inference procedure is 'demonstrate[d] on both simulated and real data,' but the manuscript contains no experiments or data-analysis section after §4.2.4. This promised empirical support is missing and should either be added or the claim should be removed.
minor comments (6)
  1. [Abstract] There is a typo: 'devolopment' should be 'development'.
  2. [§4.2.3, Corollary 3] In the display defining β̂^IVW_{t,1}, the sums use X_{t,1} and β̂^OLS_{t,1} as indices rather than X_{j,1} and β̂^OLS_{j,1}.
  3. [§4.2.4, Eq. (4.2.4)] The residual in the estimator Σ̂_{t,0} uses β̂^IVW_{t,1}; it should use β̂^IVW_{t,0}.
  4. [§4.1, Lemma 2 proof] In the proof of Lemma 2, the intermediate display writes 'sqrt(d‖V‖₂/(1−δ))' where the final statement and the argument require 'δ' in the denominator.
  5. [§4.2.4, Step 1] The stopping condition '‖X^{-1}_{t,0}‖ ≤ p' should read '‖Σ̂_{t,0}‖ ≤ p'.
  6. [§4.2.2, Theorem 4 proof] The proof says the error terms are 'uniformly bounded,' but only sub-Gaussianity is assumed; please state the boundedness assumption explicitly or adapt the Lindeberg verification.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivation chain is self-contained and the cited asymptotic results are external, not self-referential.

full rationale

The paper's central claims do not reduce to their inputs by construction. In Section 3, the pre-determined stopping rules are obtained by combining the external tail bound Lemma 1 (cited from Chen et al. [4]) with Theorem 1, which converts the bound into a regret upper bound; the resulting Opportunity Cost and Threshold rules are decision rules that minimize an explicit cost, not predictions reconstructed from fitted values. In Section 4.2.2, Theorem 4 is derived as a martingale central limit theorem with the conditional-variance and Lindeberg conditions checked in the text, and Lemmas 3 and 4 are explicitly imported from Zhang, Janson, and Murphy [14], an external source with no author overlap; this is independent support rather than a self-citation chain. Corollary 3 then follows by a Slutsky argument from Theorem 4, and the online stopping rules in Section 4.2.3 use the estimated variance of the inverse-variance-weighted estimator only as a stopping statistic. The conditional inference procedure in Section 4.2.4 conditions on the realized stopping time by sampling from the claimed asymptotic distribution subject to the stopping constraint; this constraint is the conditioning event itself, not a hidden reuse of the conclusion. There are no fitted parameters renamed as predictions, no uniqueness theorem imported from the authors' prior work, and no ansatz smuggled in through a self-citation. A real mathematical concern exists in the proof of Corollary 3: the displayed limit of (1/sqrt(nt)) times the sum of the weighted contexts appears to be incorrect by a factor of n, so the stated variance n(Sigma*_1)^{-1}sigma^2 and the online threshold calibration may be wrong; however, that is a soundness or scaling error, not a circularity, because the claimed result is not true by definition or by equivalence with its inputs.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The central claim rests on domain assumptions about contexts, margins, and errors, plus the unstated premise that the policy and stopping time are measurable with respect to the sufficient statistics. Two user-chosen constants enter the stopping rules. No new physical or statistical entities are postulated.

free parameters (2)
  • K' (composite tail-bound constant) = not specified
    Pre-determined stopping rules use U(Rπ_t)=K'(1/(n t p_t^2))^{1+λ}; K' aggregates L, M, λ, C1, C2 from Lemma 1 and Theorem 1, none of which are given numerical values or estimable from pre-experiment information, so the threshold and opportunity-cost rules are not directly implementable.
  • threshold k = user-specified
    Both pre-determined and online threshold stopping rules stop when an upper bound on regret or an estimated variance norm falls below k. The paper gives only heuristic guidance for choosing k, and the correct value depends on the unknown scaling of the variance estimator.
assumptions (7)
  • domain assumption Bounded contexts: ||x||∞ ≤ L for all x in the support.
    Used in Theorem 1 and Lemma 1 to control ||x|| in the regret bound and concentration.
  • domain assumption Positive minimum eigenvalue: λ_min(E[xx^T]) > q.
    Ensures OLS matrices are invertible and do not blow up.
  • domain assumption Margin condition: P(|(β1-β0)^T x| ≤ h) ≤ M h^λ.
    Used in Theorem 1 to convert the probability of sign disagreement into the regret bound (2B_tL)^{1+λ}M.
  • domain assumption Sub-Gaussian and bounded reward errors.
    Invoked in Lemma 1 (via Chen et al.) and in the Lindeberg condition in Theorem 4's proof; not stated as a formal assumption in Section 2.
  • domain assumption Clipping condition: p_t ≤ P(a_t=i|π_t,x) ≤ 1-p_t.
    The paper forces exploration in each batch; Theorem 4's limit Σ*_1 depends on whether p_t→0 or p_t→p>0.
  • domain assumption The adaptive policy is totally determined by the sufficient statistics T_{1:t}.
    Section 4.2.2 uses this to justify conditional inference based on T_{1:t}; the claim is that epsilon-greedy, UCB, and Thompson sampling satisfy it because their policies depend only on batched OLS estimates and covariance matrices.
  • domain assumption The stopping time is a function of batched OLS estimators and their variances.
    Section 4.2.4 relies on this to assert the estimator's distribution conditional on the stopping time is a truncated Gaussian.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Early Stopping in Contextual Bandits and Inferences." pith.science (2026). https://pith.science/paper/WPCLEJKH

@misc{pith2026250202793,
  author       = {Pith},
  title        = {Pith review of: Early Stopping in Contextual Bandits and Inferences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WPCLEJKH}},
  note         = {Machine review of arXiv:2502.02793}
}
read the original abstract

Bandit algorithms sequentially accumulate data using adaptive sampling policies, offering flexibility for real-world applications. However, excessive sampling can be costly, motivating the devolopment of early stopping methods and reliable post-experiment conditional inferences. This paper studies early stopping methods in linear contextual bandits, including both pre-determined and online stopping rules, to minimize in-experiment regrets while accounting for sampling costs. We propose stopping rules based on the Opportunity Cost and Threshold Method, utilizing the variances of unbiased or consistent online estimators to quantify the upper regret bounds of learned optimal policy. The study focuses on batched settings for stability, selecting a weighed combination of batched estimators as the online estimator and deriving its asymptotic distribution. Online statistical inferences are performed based on the selected estimator, conditional on the realized stopping time. Our proposed method provides a systematic approach to minimize in-experiment regret and conduct robust post-experiment inferences, facilitating decision-making in future applications.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

  1. [1]

    How to sample and when to stop sampling: The gene ralized wald problem and minimax policies

    Karun Adusumilli. How to sample and when to stop sampling: The gene ralized wald problem and minimax policies. arXiv preprint arXiv:2210.15841 , 2022

    arXiv 2022

  2. [2]

    Thompson sampling for contextu al bandits with linear payoffs

    Shipra Agrawal and Navin Goyal. Thompson sampling for contextu al bandits with linear payoffs. In International conference on machine learning , pages 127–135. PMLR, 2013

    work page 2013

  3. [3]

    Just-in-time contextual advertising

    Aris Anagnostopoulos, Andrei Z Broder, Evgeniy Gabrilovich, Va nja Josifovski, and Lance Riedel. Just-in-time contextual advertising. In Proceedings of the sixteenth ACM conference on Conference on information and knowledge management , pages 331–340, 2007

    work page 2007

  4. [4]

    Statistical inference for online decision making: In a contextual bandit setting

    Haoyu Chen, Wenbin Lu, and Rui Song. Statistical inference for online decision making: In a contextual bandit setting. Journal of the American Statistical Association , 116(533):240–255, 2021

    work page 2021

  5. [5]

    Optimal conditional inference in adaptive experiments

    Jiafeng Chen and Isaiah Andrews. Optimal conditional inference in adaptive experiments. arXiv preprint arXiv:2309.12162, 2023

    arXiv 2023

  6. [6]

    Contextua l bandits with linear payoff functions

    Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextua l bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2 011

    work page

  7. [7]

    Action elimination and stopping conditions for the multi-armed bandit and reinforcement le arning problems

    Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Maha devan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement le arning problems. Journal of machine learning research , 7(6), 2006

    work page 2006

  8. [8]

    Confidence intervals for policy evaluation in adaptive experiments

    Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, an d Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the national academy of sciences, 118(15):e2014602118, 2021

    work page 2021

Show all 15 references
  1. [9]

    A con textual-bandit approach to personalized news article recommendation

    Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A con textual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web , pages 661–670, 2010

    2010

  2. [10]

    Randomized stratified observer-blind placebo-contr olled study to evaluate the efficacy safety immunogenicity of mrna-1273 sars-cov-2 vaccine in adults a ged 18 years older.(2020), 3

    A Phase. Randomized stratified observer-blind placebo-contr olled study to evaluate the efficacy safety immunogenicity of mrna-1273 sars-cov-2 vaccine in adults a ged 18 years older.(2020), 3

    2020

  3. [11]

    Doubly robust interval es timation for optimal policy evaluation in online learning

    Ye Shen, Hengrui Cai, and Rui Song. Doubly robust interval es timation for optimal policy evaluation in online learning. Journal of the American Statistical Association , pages 1–20, 2024

    2024

  4. [12]

    Reinforcement learning: An introduction

    Richard S Sutton. Reinforcement learning: An introduction. A Bradford Book , 2018

    2018

  5. [13]

    Bandits with costly reward observations

    Aaron D Tucker, Caleb Biddulph, Claire Wang, and Thorsten Joac hims. Bandits with costly reward observations. In Uncertainty in Artificial Intelligence , pages 2147–2156. PMLR, 2023

    2023

  6. [14]

    Inference for batched bandits

    Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances in neural information processing systems , 33:9818–9829, 2020. 12

    2020

  7. [15]

    Statistical infe rence with m-estimators on adaptively collected data

    Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical infe rence with m-estimators on adaptively collected data. Advances in neural information processing systems , 34:7460–7471, 2021. 13

    2021

Pith tools

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