REVIEW 4 major objections 5 minor 31 references
Online Learning of Optimal Sequential Testing Policies
T0 review · 4 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read This paper proves that the Online Testing Problem has minimax regret Ω(T^(2/3)) because skipped tests hide both outcomes and rewards, and it matches this bound with an Explore-Then-Commit algorithm.
desk verdict Plausible and interesting Ω(T^{2/3}) result for online testing with missing decision rewards, but the proofs have several real gaps—most seriously a false claim about the number of posterior distributions—so treat the rates as conditional pending a rewrite. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the masking state: a subject's test outcomes are a vector x, and any state s marks unperformed tests as NA, so the reward f(x,y) of a final decision is a function of the full concealed vector and is observable only when every test has been run. This creates a Missing-At-Random mechanism because termination depends on observed entries. The matching algorithm is Explore-Then-Commit: fully observe N subjects, form an unbiased plug-in estimate of the distribution, run the clairvoyant dynamic program on that estimate, and then reuse the derived policy. The proof machinery is an error-propagation argument showing that estimation error in posterior distributions, bounded
What would settle it
Run the paper's single-test lower-bound instance (test cost 3/4, p0 = (1 ± ε)/2 with ε = T^(-1/3)) but after every episode reveal to the learner the true skipped outcome and the true reward f(x,y); if cumulative regret still must scale as T^(2/3), the permanent absence of that feedback is not the source of hardness, whereas a drop to Θ(√T) confirms it is.
Extended reading notes
Core claim
The central claim is that missing data from skipped tests is not a nuisance but a hardness amplifier: in the Online Testing Problem, any algorithm must incur minimax regret at least Ω(T^(2/3)), and with discrete support size |P| at least Ω(|P|^(1/3) T^(2/3)), in contrast to the Θ(√T) regret of episodic MDPs. The cause is that exploitation and exploration never align—when a policy skips a test to exploit, it learns nothing about that test or about the reward of its final decision. The paper matches this lower bound with a two-phase algorithm: fully test N = |P|^(1/3) T^(2/3) (or σ²T^(2/3) for Gaussians) subjects, estimate the distribution without missingness, then commit to the optimal policy
Load-bearing premise
The entire Ω(T^(2/3)) lower bound rests on the assumption that when a policy skips a test, the skipped outcome and the true reward of the final decision are never revealed later.
Editorial extensions
If this is right
- No online testing policy can guarantee regret better than T^(2/3) in the worst case when skipped tests hide their outcomes and decision rewards.
- Explore-then-commit with a full-testing exploration phase is near-optimal for both discrete and Gaussian outcome distributions, up to log factors and support-size dependence.
- The common industry practice of collecting a fully tested dataset first and then training a policy offline is theoretically justified: the resulting regret matches the lower bound up to log factors.
- If rewards depend only on the tests actually observed, as in the maximum-entropy-sampling variant, iterative elimination breaks the T^(2/3) barrier and achieves O~(√T) regret.
- A doubling-trick version of the algorithm achieves the same rate without knowing the horizon T in advance.
Reading between the lines
- If post-hoc audits or registries ever reveal skipped outcomes or true decision rewards, the hard T^(2/3) regime should collapse to an episodic-MDP regime with √T regret; testing that feedback model would sharply delimit the paper's negative result.
- The Explore-Then-Commit algorithm requires the support size |P| or the covariance condition number σ as input; a data-driven estimator of these quantities could produce a fully parameter-free algorithm with the same rate.
- The MAR insight implies that historical datasets with premature test termination are themselves biased training signals: retraining on them as if they were complete would inherit the same exploration–exploitation conflict, not merely a statistical inefficiency.
- The posterior-support error-propagation technique may transfer to other partially observable MDPs with missing rewards, not just sequential testing, giving a general criterion for when missing feedback raises regret above √T.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Online Testing Problem (OTP), a sequential decision-making setting in which a stream of subjects arrives, and for each subject the agent chooses tests (at a cost) and eventually makes a final decision. The full vector of test outcomes x is never observed unless all tests are run, and the final-decision reward f(x,y) is claimed to be unobserved when x is incomplete. The paper proves an Ω(T^{2/3}) minimax regret lower bound for OTP, presents an Explore-Then-Commit algorithm whose regret is O~(d|P|^{1/3} T^{2/3}) for discrete distributions and O~(dσ^2 T^{2/3}) for Gaussians, and identifies a special case, Online Cost-sensitive Maximum Entropy Sampling Problem (OCMESP), for which an iterative-elimination algorithm achieves O~(d^3 σ √T) regret. The theoretical results are supplemented by small numerical simulations. The main contribution is the claimed separation from episodic MDPs, where the minimax rate is Θ(√T).
Significance. The conceptual claim that missingness-dependent rewards make OTP fundamentally harder than episodic MDPs is interesting and, if established rigorously, would be a meaningful contribution to online learning under partial monitoring. The ETC upper bound and the OCMESP contrast are also constructive. However, the significance currently rests on a formal model that is internally inconsistent (the MDP reward definition in §2.1 implies observed rewards, while the lower bound in §2.4 requires unobserved rewards) and on lower-bound/upper-bound proofs that contain specific gaps (Jensen in the wrong direction in Theorem 2, and an unsupported claim that only |P|^2 posteriors need estimation in Lemma 4). These issues are load-bearing, and the paper's central conclusions should be considered unproven until they are resolved. If repaired, the results would be noteworthy.
major comments (4)
- [§2.1 vs §2.3] The formal MDP definition in Section 2.1 states that for a final decision y in state s, 'r(s, y) ∼ f(x, y) | s' and in an MDP the reward realization is observed by the agent. In the lower-bound example of §2.4, f(x,y)=1{x=y}; therefore, skipping the test and predicting 0 yields an observed reward of 1 iff x=0, i.e., the reward reveals the hidden x. Under this definition the problem is a standard episodic MDP with observed rewards, and the Ω(T^{2/3}) lower bound contradicts known Θ(√T) rates. Section 2.3 later asserts that 'the reward for the final decision f(x,y) is typically unobserved', but the formal model is never amended. Please clarify the feedback model explicitly (e.g., state that r(s,y) is not revealed to the agent, or model it as a partial-monitoring problem) and adjust the definitions in Section 2.1 so that the lower bound is internally consistent.
- [Appendix A.2 (Theorem 2)] The proof uses Jensen's inequality to claim E[T_i^{2/3}] = Ω((E[T_i])^{2/3}). Since x ↦ x^{2/3} is concave, Jensen gives E[T_i^{2/3}] ≤ (E[T_i])^{2/3}, the opposite direction. The proof needs a concentration argument (e.g., Chernoff bounds for T_i ~ Bin(T, 2/|P|)) to show that T_i is close to its expectation with high probability, so that E[T_i^{2/3}] is indeed Ω((T/|P|)^{2/3}). As written, the |P| dependence in Theorem 2 is not established.
- [Lemma 4 / §2.5] The proof claims there are at most |P|^2 posterior distributions to estimate, arguing that collecting one state for every pair x', x'' covers all states that must be estimated. This is not true in general: a cylinder event (a set of support points consistent with a partial assignment) can require more than two points to identify. For example, with P = {000, 011, 101, 110} (even-parity strings in 3 bits), the state with all coordinates NA has a posterior supported on all four points, but no pair of points in that set has exactly the same common-coordinate state; the pair construction misses this posterior. In a one-hot embedding with |P| points, every subset of P is a cylinder, giving 2^{|P|} distinct non-singleton posteriors, far more than |P|^2. The union bound over posterior deviations (and hence the |P| dependence in Theorem 3) therefore lacks a valid state-count bound. Please provide
- [Theorem 1 proof, §2.4 and Appendix A.1] The lower-bound example's action costs are mislabeled: §2.4 calls E[f(x1,0)] = 1-p0 the 'expected cost' of predicting 0, but it is actually the expected reward; the subsequent regret computation in Theorem 1 uses the loss interpretation (p0 and 1-p0 as costs of misclassification), which is correct. This is a presentation error rather than a numerical one, but it obscures the argument. Please rewrite the action list in a consistent loss/reward formulation.
minor comments (5)
- [Section 4 (Conclusion)] The conclusion states the discrete ETC regret as O~(d|P|^{2/3} T^{2/3}), but Theorem 3 and Section 1.4 correctly state O~(d|P|^{1/3} T^{2/3}). Please correct the exponent.
- [Appendix A.1] 'Pinker's inequality' should be 'Pinsker's inequality'.
- [Appendix A.4 (Theorem 4)] In the proof, the exploitation-phase regret is written as O~(dσ^3 / √N) without the factor T; it should be O~(dσ^3 T / √N). The final bound is unaffected after substituting N = σ^2 T^{2/3}, but the displayed expression is misleading.
- [Section 2.5] The sentence 'we claim that ... the number of non-trivial P^s is at most |P|^2' appears before the formal proof; given the issue raised in Major Comment 3, please ensure the proof is sufficiently detailed and correct before asserting this claim in the main text.
- [Section 3.3] Algorithm 4 takes the condition number σ as input. The paper says this is an upper bound on the condition number, but it is not explained how a practitioner would obtain such an upper bound in the unknown-Σ setting. Please add a remark on this assumption.
Circularity Check
No significant circularity: the regret bounds are derived from stated distributional assumptions and standard concentration inequalities; the reward-observability inconsistency is a modeling caveat, not a circular reduction.
full rationale
The paper's core derivation chain is self-contained rather than circular. Algorithm 2 (ETC) estimates the full distribution P during a pure exploration phase and then commits to a policy by solving the clairvoyant DP (Algorithm 1). The regret bound in Theorem 3 is obtained by standard L1 deviation bounds for empirical distributions (Weissman et al. 2003) and a dynamic-programming error-propagation induction; the exploration length N is chosen to balance exploration regret O(dN) against exploitation regret O(dT sqrt(|P|/N)), yielding N = |P|^{1/3} T^{2/3}. This is a genuine tradeoff, not a parameter fitted to force the target rate. The lower bound (Theorem 1) is a worst-case two-instance hypothesis test with epsilon = T^{-1/3} used as a proof device; the bound follows from KL/Pinsker inequalities, not from an equation that already contains the conclusion. There are no load-bearing self-citations: the cited external results (Weissman, Vershynin, Little & Rubin) are standard, and the authors' own prior work is not used to justify any premise. The only notable issue is an internal tension: Section 2.1 defines r(s,y) as a realization of f(x,y)|s, which in an MDP would be observed, while Section 2.3 asserts that f(x,y) is typically unobserved when x is incomplete. If the Section 2.1 definition were taken literally, the lower-bound example's skipped decisions would reveal x and the T^{2/3} separation would collapse. However, this is a formal-consistency caveat about the model, not circularity: the T^{2/3} theorem is explicitly conditional on the unobserved-reward premise stated in Section 2.3, and it is not derived by defining the conclusion into the inputs. Thus the paper's central derivations are independent of their own outputs and receive a circularity score of 0.
Assumptions & free parameters
free parameters (1)
- ETC exploration length N =
|P|^(1/3) T^(2/3) for discrete, σ^2 T^(2/3) for Gaussian
assumptions (8)
- domain assumption The outcome vectors x(t) of subjects are i.i.d. from a fixed, stationary distribution P.
- domain assumption Test observations are noiseless and each test has a known, fixed, additive cost c_i.
- domain assumption When a subject is not fully tested, the reward f(x,y) is unobserved and never revealed.
- domain assumption The optimal decision for a subject is identifiable if all tests are performed.
- domain assumption For discrete results the support size |P| is finite and known; for Gaussian results the covariance has a known condition-number bound σ.
- standard math Standard concentration tools are valid: Hoeffding, Bernstein, Weissman's L1 deviation bound, Pinsker's inequality.
- ad hoc to paper There are at most |P|^2 non-trivial posterior distributions P^s that need estimation.
- domain assumption For OCMESP, a non-adaptive policy is as good as any adaptive policy.
Cite this review
Pith. "Pith review of Online Learning of Optimal Sequential Testing Policies." pith.science (2026). https://pith.science/paper/CDYRNMKS
@misc{pith2026250903707,
author = {Pith},
title = {Pith review of: Online Learning of Optimal Sequential Testing Policies},
year = {2026},
howpublished = {\url{https://pith.science/paper/CDYRNMKS}},
note = {Machine review of arXiv:2509.03707}
}
abstract
This paper studies an online learning problem that seeks optimal testing policies for a stream of subjects, each of whom can be evaluated through a sequence of candidate tests drawn from a common pool. We refer to this problem as the Online Testing Problem (OTP). Although conducting every candidate test for a subject provides more information, it is often preferable to select only a subset when tests are correlated and costly, and make decisions with partial information. If the joint distribution of test outcomes were known, the problem could be cast as a Markov Decision Process (MDP) and solved exactly. In practice, this distribution is unknown and must be learned online as subjects are tested. When a subject is not fully tested, the resulting missing data can bias estimates, making the problem fundamentally harder than standard episodic MDPs. We prove that the minimax regret must scale at least as $\Omega(T^{\frac{2}{3}})$, in contrast to the $\Theta(\sqrt{T})$ rate in episodic MDPs, revealing the difficulty introduced by missingness. This elevated lower bound is then matched by an Explore-Then-Commit algorithm whose cumulative regret is $\tilde{O}(T^{\frac{2}{3}})$ for both discrete and Gaussian distributions. To highlight the consequence of missingness-dependent rewards in OTP, we study a variant called the Online Cost-sensitive Maximum Entropy Sampling Problem, where rewards are independent of missing data. This structure enables an iterative-elimination algorithm that achieves $\tilde{O}(\sqrt{T})$ regret, breaking the $\Omega(T^{\frac{2}{3}})$ lower bound for OTP. Numerical results confirm our theory in both settings. Overall, this work deepens the understanding of the exploration--exploitation trade-off under missing data and guides the design of efficient sequential testing policies.
Reference graph
Works this paper leans on
-
[1]
Journal of the ACM (JACM) 67(6):1--42
Ashtiani H, Ben-David S, Harvey NJ, Liaw C, Mehrabian A, Plan Y (2020) Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM (JACM) 67(6):1--42
work page 2020
-
[2]
International conference on machine learning, 263--272 (PMLR)
Azar MG, Osband I, Munos R (2017) Minimax regret bounds for reinforcement learning. International conference on machine learning, 263--272 (PMLR)
work page 2017
-
[3]
arXiv preprint arXiv:2212.14411
Bibaut A, Kallus N, Lindon M (2022) Near-optimal non-parametric sequential tests and confidence sequences with possibly dependent observations. arXiv preprint arXiv:2212.14411
arXiv 2022
-
[4]
(2011) Shigley's mechanical engineering design, volume 9 (McGraw-Hill New York)
Budynas RG, Nisbett JK, et al. (2011) Shigley's mechanical engineering design, volume 9 (McGraw-Hill New York)
work page 2011
-
[5]
Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge, UK: Cambridge University Press), ISBN 978-0-521-85128-4
work page 2006
-
[6]
Mathematics of Operations Research 31(3):562--580
Cesa-Bianchi N, Lugosi G, Stoltz G (2006) Regret minimization under partial monitoring. Mathematics of Operations Research 31(3):562--580
work page 2006
-
[7]
The Annals of Mathematical Statistics 30(3):755--770
Chernoff H (1959) Sequential design of experiments. The Annals of Mathematical Statistics 30(3):755--770
work page 1959
-
[8]
ACM Transactions on Algorithms (TALG) 5(2):1--34
Condon A, Deshpande A, Hellerstein L, Wu N (2009) Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Transactions on Algorithms (TALG) 5(2):1--34
work page 2009
Show all 31 references
-
[9]
Cover TM, Thomas JA (2006) Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing) (USA: Wiley-Interscience), ISBN 0471241954
2006
-
[10]
Algorithmic Learning Theory, 578--598 (PMLR)
Domingues OD, M \'e nard P, Kaufmann E, Valko M (2021) Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. Algorithmic Learning Theory, 578--598 (PMLR)
2021
-
[11]
Fampa M, Lee J (2022) Maximum-entropy sampling: algorithms and application (Springer Nature)
2022
-
[12]
Clinical Rheumatology 37:1879--1884
Gamala M, Linn-Rasker S, Nix M, Heggelman B, Van Laar J, Pasker-de Jong P, Jacobs J, Klaasen R (2018) Gouty arthritis: decision-making following dual-energy ct scan in clinical practice, a retrospective analysis. Clinical Rheumatology 37:1879--1884
2018
-
[13]
Advances in Neural Information Processing Systems 34:5012--5024
Gan K, Jia S, Li A (2021) Greedy approximation algorithms for active sequential hypothesis testing. Advances in Neural Information Processing Systems 34:5012--5024
2021
-
[14]
O zkan \
Hellerstein L, \"O zkan \"O , Sellie L (2017) Max-throughput for (conservative) k-of-n testing. Algorithmica 77(2):595--618
2017
-
[15]
Bernoulli 28(3):1704 -- 1728, ://dx.doi.org/10.3150/21-BEJ1388
Howard SR, Ramdas A (2022) Sequential estimation of quantiles with applications to A/B testing and best-arm identification . Bernoulli 28(3):1704 -- 1728, ://dx.doi.org/10.3150/21-BEJ1388
2022 doi
-
[16]
The Annals of Statistics 49(2):1055 -- 1080, ://dx.doi.org/10.1214/20-AOS1991
Howard SR, Ramdas A, McAuliffe J, Sekhon J (2021) Time-uniform, nonparametric, nonasymptotic confidence sequences . The Annals of Statistics 49(2):1055 -- 1080, ://dx.doi.org/10.1214/20-AOS1991
2021 doi
-
[17]
SIAM Journal on Matrix Analysis and Applications 30(2):762--776
Ipsen IC, Rehman R (2008) Perturbation bounds for determinants and characteristic polynomials. SIAM Journal on Matrix Analysis and Applications 30(2):762--776
2008
-
[18]
Khuri AI (2009) Linear model methodology (Chapman and Hall/CRC)
2009
-
[19]
International Conference on Integer Programming and Combinatorial Optimization, 280--292 (Springer)
Kodialam MS (2001) The throughput of sequential testing. International Conference on Integer Programming and Combinatorial Optimization, 280--292 (Springer)
2001
-
[20]
Lattimore T, Szepesv \'a ri C (2020) Bandit algorithms (Cambridge University Press)
2020
-
[21]
Little RJA, Rubin DB (2019) Statistical Analysis with Missing Data (Hoboken, NJ: John Wiley & Sons), 3 edition, ISBN 978-1-119-45724-2
2019
-
[22]
The Annals of Statistics 41(6):2703 -- 2738, ://dx.doi.org/10.1214/13-AOS1144
Naghshvar M, Javidi T (2013) Active sequential hypothesis testing . The Annals of Statistics 41(6):2703 -- 2738, ://dx.doi.org/10.1214/13-AOS1144
2013 doi
-
[23]
Advances in Neural Information Processing Systems, volume 31 (Curran Associates, Inc.)
Peng YS, Tang KF, Lin HT, Chang E (2018) Refuel: Exploring sparse features in deep reinforcement learning for fast disease diagnosis. Advances in Neural Information Processing Systems, volume 31 (Curran Associates, Inc.)
2018
-
[24]
Operations Research 70(2):1153--1165, ://dx.doi.org/10.1287/opre.2019.1967
Segev D, Shaposhnik Y (2022) A polynomial-time approximation scheme for sequential batch testing of series systems. Operations Research 70(2):1153--1165, ://dx.doi.org/10.1287/opre.2019.1967
2022
-
[25]
Vershynin R (2018) High-dimensional probability: An introduction with applications in data science, volume 47 (Cambridge university press)
2018
-
[26]
The Annals of Mathematical Statistics 326--339
Wald A, Wolfowitz J (1948) Optimum character of the sequential probability ratio test. The Annals of Mathematical Statistics 326--339
1948
-
[27]
Hewlett-Packard Labs, Tech
Weissman T, Ordentlich E, Seroussi G, Verdu S, Weinberger MJ (2003) Inequalities for the l1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep 125
2003
-
[28]
The Eleventh International Conference on Learning Representations
Yu Z, Li Y, Kim JC, Huang K, Luo Y, Wang M (2023) Deep reinforcement learning for cost-effective medical diagnosis. The Eleventh International Conference on Learning Representations
2023
-
[29]
International Conference on Machine Learning, 7304--7312 (PMLR)
Zanette A, Brunskill E (2019) Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. International Conference on Machine Learning, 7304--7312 (PMLR)
2019
-
[30]
(2006) Eular evidence based recommendations for gout
Zhang W, Doherty M, Bardin T, Pascual E, Barskova V, Conaghan P, Gerster J, Jacobs J, Leeb B, Liot \'e F, et al. (2006) Eular evidence based recommendations for gout. part ii: Management. report of a task force of the eular standing committee for international clinical studies...
2006
-
[31]
Journal of the Royal Statistical Society Series C: Applied Statistics 49(1):63--79, ISSN 0035-9254, ://dx.doi.org/10.1111/1467-9876.00179
Zidek JV, Sun W, Le ND (2002) Designing and integrating composite networks for monitoring multivariate gaussian pollution fields. Journal of the Royal Statistical Society Series C: Applied Statistics 49(1):63--79, ISSN 0035-9254, ://dx.doi.org/10.1111/1467-9876.00179
2002
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.