pith. sign in

arxiv: 2605.31465 · v1 · pith:2REHWAXLnew · submitted 2026-05-29 · 🧮 math.ST · cs.IT· math.IT· stat.TH

The Nonparametric Kiefer-Weiss Problem

Michael Fauss , H. Vincent Poor , Abdelhak M. Zoubir This is my paper

Pith reviewed 2026-06-28 20:21 UTC · model grok-4.3

classification 🧮 math.ST cs.ITmath.ITstat.TH
keywords nonparametric sequential testingKiefer-Weiss problemoptimal stoppinglikelihood ratiorandomized stopping rulesBellman equationsample size constraintsequential hypothesis testing
0
0 comments X

The pith

The nonparametric Kiefer-Weiss problem reduces to an optimal stopping problem whose solution is recovered in the limit of unbounded randomizations and yields a two-dimensional stopping policy.

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

The paper sets out to solve a nonparametric version of the Kiefer-Weiss problem, whose goal is to minimize a weighted sum of the two error probabilities for a sequential binary test while keeping the expected sample size below a fixed threshold no matter which distribution is true. This is accomplished by showing that the problem is equivalent to an optimal stopping problem that can be solved exactly when the number of randomizations is bounded, with the general solution recovered by letting that bound tend to infinity. The resulting policy uses a two-dimensional statistic to decide stopping and employs randomization in a specific way to manage the remaining expected sample size. Readers interested in sequential analysis would care because this provides an explicit characterization of the optimal rule in a distribution-free setting.

Core claim

The nonparametric Kiefer-Weiss problem reduces to an optimal stopping problem. Its solution is obtained from the nonlinear Bellman equation that arises when at most k randomizations are permitted; the original problem is recovered in the limit as k tends to infinity. The optimal stopping policy is based on a two-dimensional test statistic with one component given by the likelihood ratio and the other by the expected remaining sample size. The optimal randomization rule is determined by a function that maps the likelihood ratio to an integer-valued sample size, for which two practical approximations are given.

What carries the argument

The two-dimensional test statistic that tracks the likelihood ratio together with the expected remaining sample size, and the associated randomization function mapping the likelihood ratio to a target sample size.

If this is right

  • The optimal cost function satisfies a nonlinear Bellman equation.
  • The stopping policy uses randomization both to increase the remaining expected sample size in some cases and to stop early in others.
  • Two approximations to the randomization function can be evaluated easily for practical tests.
  • The method applies to tests for shifts in Bernoulli success probability and normal distribution means.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The two-dimensional structure may generalize to other nonparametric sequential problems that enforce a worst-case sample size bound.
  • The rate at which finite-k solutions converge to the limit could supply useful error bounds for numerical implementation.
  • The explicit form of the randomization function opens the possibility of replacing the approximations with exact closed-form expressions in low-dimensional cases.

Load-bearing premise

The nonparametric Kiefer-Weiss problem can be reduced to an optimal stopping problem whose solution under a finite-randomization constraint yields the original problem in the limit as the number of allowed randomizations tends to infinity.

What would settle it

An explicit example of a probability distribution and error weights for which the proposed two-dimensional policy fails to achieve the minimal weighted error sum while satisfying the maximum expected sample size constraint would disprove the optimality of the derived policy.

Figures

Figures reproduced from arXiv: 2605.31465 by Abdelhak M. Zoubir, H. Vincent Poor, Michael Fauss.

Figure 1
Figure 1. Figure 1: Optimal cost ρk(z, c) as a function of z for fixed c Both examples are simple, but well-suited to illustrate the NPKWT. For the unlimited randomness case, k → ∞, the results presented in this section were obtained by numerically solving (21) and in turn (19). For the two examples above, (21) simplifies to g(2λ ) − ϱ(λ, n) n = sup m≥n g(2λ ) − 2 3 ϱ [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Optimal cost ρk(z, c) as a function of c for fixed z k = 1. In light of the discussion in Section 5, this indicates that a single randomization is sufficient to overcome the bottleneck of the test statistic “getting stuck” on the wrong side of the decision threshold. Allowing for an unlimited number of randomization uses, k → ∞, further reduces the cost, but the effects are less significant. In [PITH_FULL… view at source ↗
Figure 3
Figure 3. Figure 3: Optimal expected remaining sample size m∗ as a function of z sample size, b ∗ 1 (z, 1), and the two approximations proposed in Section 6. Since the approximation in (25) is exact in the Gaussian example, the approximate upper bound coincides with b ∗ 1 (z, 1) in the plot on the right. In the Bernoulli example, the approximation is no longer exact but slightly differs from b ∗ 1 (z, 1). In general, the appr… view at source ↗
Figure 4
Figure 4. Figure 4: Sum error probability as a function of k [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Histograms of the stopping times of the NPKWTs under the respective null hypotheses [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Histograms of the number of randomization uses of the NPKWTs under the respective [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
read the original abstract

A nonparametric variant of the Kiefer-Weiss problem is proposed and solved. The objective is to minimize a weighted sum of the error probabilities of a binary sequential test subject to a constraint on its maximum expected sample size. This maximum is taken over all possible probability distributions on the given sequence space. First, it is shown that the nonparametric Kiefer-Weiss problem can be reduced to an optimal stopping problem. Then, the optimal stopping policy is derived under the assumption that at most k uses of randomization are permitted during any run of the test. The solution to the original problem is then obtained by letting k go to infinity. The optimal cost function is shown to be the solution of a nonlinear Bellman equation. The corresponding optimal stopping policy is shown to be based on a two-dimensional test statistic, with one component tracking the likelihood ratio and the other one tracking the expected remaining sample size. Critically, the stopping policy uses randomization to increase the remaining expected sample size for some runs, while stopping early for others. The optimal randomization rule is shown to be determined by a function that maps the likelihood ratio to an integer-valued sample size. Two approximations of this function are proposed that can be evaluated easily in practice. The results are illustrated with two numerical examples of nonparametric Kiefer-Weiss tests, one for a shift in the success probability of a Bernoulli distribution, and one for a shift in the mean of a normal distribution.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a nonparametric variant of the Kiefer-Weiss problem: minimize a weighted sum of type-I and type-II error probabilities for a binary sequential test subject to a constraint on the supremum (over all distributions P) of the expected sample size. It reduces the problem to an optimal stopping problem, solves the version with at most k randomizations via a nonlinear Bellman equation, and recovers the original solution by sending k to infinity. The resulting optimal policy is characterized by a two-dimensional statistic (likelihood ratio together with expected remaining sample size); randomization is governed by a function that maps the likelihood ratio to an integer-valued sample size, for which two practical approximations are given. The results are illustrated on Bernoulli and Gaussian shift examples.

Significance. If the reduction and the k-to-infinity limit are rigorously justified, the work supplies the first explicit solution method for a nonparametric Kiefer-Weiss problem and yields implementable policies together with easily computable randomization approximations. This would constitute a substantive advance in robust sequential analysis.

major comments (2)
  1. [argument recovering the original problem by k→∞ (after the finite-k Bellman equation)] The central claim that the original nonparametric value is recovered by letting k→∞ after solving the finite-randomization Bellman equation rests on an unstated convergence argument. In the nonparametric setting the state space (likelihood ratio × expected remaining sample size) is typically non-compact; without an explicit uniform-integrability, tightness, or monotone-convergence justification for V_k → V (and preservation of the sup_P E_P[N] constraint), the passage to the limit may fail to yield a feasible or optimal policy for the original problem.
  2. [reduction to optimal stopping and derivation of the nonlinear Bellman equation] The reduction of the nonparametric Kiefer-Weiss problem to an optimal stopping problem is asserted, but the precise manner in which the supremum over all P is folded into the Bellman operator (or into the two-dimensional state process) is not shown to commute with the dynamic-programming recursion; this step is load-bearing for the claim that the finite-k solution converges to the desired nonparametric optimum.
minor comments (2)
  1. [numerical examples] The two numerical examples would benefit from a brief statement of the discretization or approximation scheme used to solve the Bellman equation on the continuous state space.
  2. [characterization of the optimal policy] Notation for the likelihood-ratio process and the expected-remaining-sample-size process should be introduced once and used consistently; currently the same symbols appear to be overloaded between the finite-k and limiting regimes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying two points where the manuscript's arguments would benefit from expanded justification. We address each major comment below and will make the indicated revisions.

read point-by-point responses

  1. Referee: The central claim that the original nonparametric value is recovered by letting k→∞ after solving the finite-randomization Bellman equation rests on an unstated convergence argument. In the nonparametric setting the state space (likelihood ratio × expected remaining sample size) is typically non-compact; without an explicit uniform-integrability, tightness, or monotone-convergence justification for V_k → V (and preservation of the sup_P E_P[N] constraint), the passage to the limit may fail to yield a feasible or optimal policy for the original problem.

    Authors: We agree that the convergence V_k → V requires a more explicit treatment than the sketch currently given in Section 5. In the revised version we will insert a new subsection establishing monotone convergence of the finite-k value functions to the nonparametric value via the monotone convergence theorem applied to the Bellman operators. Non-compactness will be handled by a truncation argument on the likelihood-ratio coordinate together with a uniform-integrability bound derived from the fact that the worst-case expected sample size remains bounded by the constraint; preservation of the sup_P E_P[N] constraint in the limit will follow from Fatou's lemma. These additions will appear in the next revision. revision: yes

  2. Referee: The reduction of the nonparametric Kiefer-Weiss problem to an optimal stopping problem is asserted, but the precise manner in which the supremum over all P is folded into the Bellman operator (or into the two-dimensional state process) is not shown to commute with the dynamic-programming recursion; this step is load-bearing for the claim that the finite-k solution converges to the desired nonparametric optimum.

    Authors: The reduction is carried out in Section 3 by augmenting the state with the worst-case expected remaining sample size, so that the supremum over P is absorbed into the definition of the state process before the dynamic-programming recursion begins. The nonlinear Bellman equation is then obtained by applying the optimality principle to this augmented Markov decision process. While the manuscript indicates this construction, it does not supply a separate lemma verifying that the sup and the recursion commute. In the revision we will add such a lemma (new Lemma 3.2) that shows the value function of the reduced optimal-stopping problem satisfies the nonlinear Bellman equation without interchanging the order of sup and inf. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is a standard optimal-stopping reduction.

full rationale

The paper reduces the nonparametric Kiefer-Weiss problem to an optimal stopping problem whose value function satisfies a nonlinear Bellman equation, solves the finite-k randomization version explicitly, and recovers the original problem by taking k to infinity. This chain relies on dynamic programming and limiting arguments rather than any self-definitional mapping, fitted parameters renamed as predictions, or load-bearing self-citations. No equation is shown to equal its own input by construction, and the two-dimensional test statistic (likelihood ratio plus expected remaining sample size) emerges from the Bellman recursion rather than being presupposed. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard results from optimal stopping theory and dynamic programming; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption The nonparametric Kiefer-Weiss problem reduces to an optimal stopping problem under the given max-expected-sample-size constraint.
    Stated as the first step of the solution in the abstract.
  • standard math The optimal cost function satisfies a nonlinear Bellman equation.
    Invoked as the characterization of the value function.

pith-pipeline@v0.9.1-grok · 5790 in / 1281 out tokens · 22684 ms · 2026-06-28T20:21:16.118931+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 24 canonical work pages

  1. [1]

    , year 1948

    A. Wald and J. Wolfowitz. “Optimum Character of the Sequential Probability Ratio Test”. In: Annals of Mathematical Statistics19.3 (1948), pp. 326–339.doi:10.1214/aoms/1177730197

    work page doi:10.1214/aoms/1177730197 1948

  2. [2]

    Tartakovsky, I

    A. Tartakovsky, I. Nikiforov, and M. Basseville.Sequential Analysis: Hypothesis Testing and Changepoint Detection. Boca Raton, FL, USA: Chapman and Hall/CRC, 2014.doi:10.1201/ b17279

    2014

  3. [3]

    Some Properties of Generalized Sequential Probability Ratio Tests

    J. Kiefer and L. Weiss. “Some Properties of Generalized Sequential Probability Ratio Tests”. In:Annals of Mathematical Statistics28.1 (1957), pp. 57–74.doi:10.1214/aoms/1177707037

    work page doi:10.1214/aoms/1177707037 1957

  4. [4]

    On Sequential Tests which Minimize the Maximum Expected Sample Size

    L. Weiss. “On Sequential Tests which Minimize the Maximum Expected Sample Size”. In: Journal of the American Statistical Association57.299 (1962), pp. 551–566.doi:10.2307/ 2282392

    1962

  5. [5]

    On information and sufficiency,

    A. Dvoretzky, J. Kiefer, and J. Wolfowitz. “Sequential Decision Problems for Processes with Continuous Time Parameter. Testing Hypotheses”. In:Annals of Mathematical Statistics24.2 (1953), pp. 254–264.doi:10.1214/aoms/1177729031

    work page doi:10.1214/aoms/1177729031 1953

  6. [6]

    A Modification of the Sequential Probability Ratio Test to Reduce the Sample Size

    T. W. Anderson. “A Modification of the Sequential Probability Ratio Test to Reduce the Sample Size”. In:Annals of Mathematical Statistics31.1 (1960), pp. 165–197.doi:10.1214/ aoms/1177705996

    work page arXiv 1960

  7. [7]

    A Class of Stopping Rules for Testing Parametric Hypothe- ses

    H. Robbins and D. Siegmund. “A Class of Stopping Rules for Testing Parametric Hypothe- ses”. In:Proc. of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 4: Biology and Health. University of California Press, 1972, pp. 37–41.doi:10.1525/ 9780520422001-006

    1972

  8. [8]

    Optimal Stopping and Sequential Tests which Minimize the Maximum Expected Sample Size

    T. L. Lai. “Optimal Stopping and Sequential Tests which Minimize the Maximum Expected Sample Size”. In:Annals of Statistics1.4 (1973), pp. 659–673.doi:10.1214/aos/1176342461

    work page doi:10.1214/aos/1176342461 1973

  9. [9]

    On confidence sequences

    G. Lorden. “2-SPRT’S and The Modified Kiefer-Weiss Problem of Minimizing an Expected Sample Size”. In:Annals of Statistics4.2 (1976), pp. 281–291.doi:10.1214/aos/1176343407

    work page doi:10.1214/aos/1176343407 1976

  10. [10]

    The Asymptotic Solution of the Kiefer–Weiss Problem

    B. Eisenberg. “The Asymptotic Solution of the Kiefer–Weiss Problem”. In:Communications in Statistics. Part C: Sequential Analysis1.1 (1982), pp. 81–88.doi:10.1080/07474948208836005

    work page doi:10.1080/07474948208836005 1982

  11. [11]

    A Universal Prior for Integers and Estimation by Minimum Description Length

    M. D. Huffman. “An Efficient Approximate Solution to the Kiefer–Weiss Problem”. In:Annals of Statistics11.1 (1983), pp. 306–316.doi:10.1214/aos/1176346081

    work page doi:10.1214/aos/1176346081 1983

  12. [12]

    Asymptotic Solution of the Kiefer–Weiss Problem for Pro- cesses with Independent Increments

    V. P. Dragalin and A. Novikov. “Asymptotic Solution of the Kiefer–Weiss Problem for Pro- cesses with Independent Increments”. In:Theory of Probability & Its Applications32.4 (1988), pp. 617–627.doi:10.1137/1132094

    work page doi:10.1137/1132094 1988

  13. [13]

    T. L. Lai.Asymptotic Optimality of Generalized Sequential Likelihood Ratio Tests in Some Classical Sequential Testing Problems. Tech. rep. Department of Statistics, Stanford Univer- sity, 1988.doi:10.1081/SQA-120016301

    work page doi:10.1081/sqa-120016301 1988

  14. [14]

    Sequential Procedure of Testing Composite Hypotheses with Applications to the Kiefer–Weiss Problem

    I. V. Pavlov. “Sequential Procedure of Testing Composite Hypotheses with Applications to the Kiefer–Weiss Problem”. In:Theory of Probability & Its Applications35.2 (1991), pp. 280– 292.doi:10.1137/1135036

    work page doi:10.1137/1135036 1991

  15. [15]

    Augustin and S

    T. Augustin and S. P¨ ohlmann.On Robust Sequential Analysis – Kiefer–Weiss Optimal Test- ing under Interval Probability. 2001.doi:10.5282/ubm/epub.1641. 30

    work page doi:10.5282/ubm/epub.1641 2001

  16. [16]

    The Optimal Decision Rule in the Kiefer–Weiss Problem for a Brownian Motion

    M. V. Zhitlukhin, A. A. Muravlev, and A. N. Shiryaev. “The Optimal Decision Rule in the Kiefer–Weiss Problem for a Brownian Motion”. In:Russian Mathematical Surveys68.2 (2013), pp. 389–391.doi:10.1070/RM2013v068n02ABEH004834

    work page doi:10.1070/rm2013v068n02abeh004834 2013

  17. [17]

    A Computational Approach to the Kiefer–Weiss Problem for Sampling from a Bernoulli Population

    Andrey Novikov, Andrei Novikov, and Fahil Farkhshatov. “A Computational Approach to the Kiefer–Weiss Problem for Sampling from a Bernoulli Population”. In:Sequential Analysis 41.2 (2022), pp. 198–219.doi:10.1080/07474946.2022.2070212

    work page doi:10.1080/07474946.2022.2070212 2022

  18. [18]

    A Computational Approach to the Kiefer–Weiss Problem for Sampling from a Bernoulli Population

    Andrey Novikov and Fahil Farkhshatov. “Design and Performance Evaluation in Kiefer–Weiss Problems When Sampling from Discrete Exponential Families”. In:Sequential Analysis41.4 (2022), pp. 417–434.doi:10.1080/07474946.2022.2109673

    work page doi:10.1080/07474946.2022.2109673 2022

  19. [19]

    Numerical Solution of Kiefer– Weiss Problems When Sampling from Continuous Exponential Families

    Andrey Novikov, Andrei Novikov, and Fahil Farkhshatov. “Numerical Solution of Kiefer– Weiss Problems When Sampling from Continuous Exponential Families”. In:Sequential Anal- ysis42.2 (2023), pp. 189–209.doi:10.1080/07474946.2023.2193602

    work page doi:10.1080/07474946.2023.2193602 2023

  20. [20]

    Choudhary, J

    Michael Fauß and H. Vincent Poor. “Fading Boundaries: On a Nonparametric Variant of the Kiefer–Weiss Problem”. In:arXiv: Statistics Theory(2020).doi:10.48550/arXiv.2010. 12094

    work page doi:10.48550/arxiv.2010 2020

  21. [21]

    C. D. Aliprantis and K. C. Border.Infinite Dimensional Analysis: A Hitchhiker’s Guide. 3rd. Berlin: Springer, 2007.doi:10.1007/3-540-29587-9

    work page doi:10.1007/3-540-29587-9 2007

  22. [22]

    Lehmann and George Casella.Theory of Point Estimation

    Erich L. Lehmann and George Casella.Theory of Point Estimation. 2nd ed. Springer Texts in Statistics. New York: Springer, 1998.doi:10.2307/1270597

    work page doi:10.2307/1270597 1998

  23. [23]

    Wald.Sequential Analysis

    A. Wald.Sequential Analysis. Hoboken, NJ, USA: Wiley, 1947.doi:10.2307/2280027

    work page doi:10.2307/2280027 1947

  24. [24]

    Siegmund.Sequential Analysis

    D. Siegmund.Sequential Analysis. New York City, NY, USA: Springer, 1985.doi:10.1007/ 978-1-4757-1862-1. [25]Code Repository.https://github.com/mifauss/Nonparametric_Kiefer_Weiss_Test

    1985

  25. [25]

    G. B. Folland.Real Analysis: Modern Techniques and Their Applications. 2nd. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. New York: Wiley, 1999

    1999

  26. [26]

    Compactness of Stopping Times

    J. R. Baxter and Rafael V. Chacon. “Compactness of Stopping Times”. In:Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete40 (1977), pp. 169–181.doi:10.1007/ bf00736045

    1977

  27. [27]

    On Compactness and Optimality of Stopping Times

    G. A. Edgar, A. Millet, and L. Sucheston. “On Compactness and Optimality of Stopping Times”. In:Martingale Theory in Harmonic Analysis and Banach Spaces. Ed. by Jia-Arng Chao and Wojbor A. Woyczy´ nski. Berlin, Heidelberg: Springer, 1982, pp. 36–61.doi:10. 1007/bfb0096258

    1982

  28. [28]

    J. B. Conway.A Course in Functional Analysis. Graduate Texts in Mathematics. Springer New York, 1994.doi:10.1007/978-1-4757-4383-8

    work page doi:10.1007/978-1-4757-4383-8 1994

  29. [29]

    Rudin.Real and Complex Analysis

    W. Rudin.Real and Complex Analysis. Mathematics series. McGraw-Hill, 1987.doi:10 . 2307/2348852

    1987

  30. [30]

    J. R. Munkres.Topology: A First Course. 1st. Englewood Cliffs, NJ: Prentice-Hall, 1974

    1974

  31. [31]

    Rudin.Principles of Mathematical Analysis

    W. Rudin.Principles of Mathematical Analysis. 3rd. International Series in Pure and Applied Mathematics. New York: McGraw-Hill, 1976. 31

    1976

  32. [32]

    R. T. Rockafellar and R. J. B. Wets.Variational Analysis. Vol. 317. Grundlehren der math- ematischen Wissenschaften. Berlin, Heidelberg: Springer, 2009.doi:10.1007/978- 3- 642- 02431-3

    work page doi:10.1007/978- 2009

  33. [33]

    R. T. Rockafellar.Convex Analysis. Princeton, NJ, USA: Princeton University Press, 1970. doi:10.1515/9781400873173

    work page doi:10.1515/9781400873173 1970

  34. [34]

    Feller.An Introduction to Probability Theory and Its Applications, Volume 1

    W. Feller.An Introduction to Probability Theory and Its Applications, Volume 1. An Intro- duction to Probability Theory and Its Applications. Wiley, 1968.doi:10.2307/2286108. 32

    work page doi:10.2307/2286108 1968