Anytime Valid Confidence Bands for Distribution Functions

Bror Hultberg; Dave Zachariah; Antônio H. Ribeiro

stat.MLOct 26, 2026

Anytime Valid Confidence Bands for Distribution Functions

Authors: Bror Hultberg, Dave Zachariah, Antônio H. Ribeiro

Organizations: Uppsala University, Sweden · Uppsala University & SciLifeLab, Sweden

Abstract

Nonparametric inference often requires characterizing an unknown function, such as a cumulative distribution function (CDF), across its entire domain rather than a specific point. We develop confidence bands for distribution functions of a data stream that are valid simultaneously over all times and all points, even when each observation may depend arbitrarily on the past. We begin by deriving such bands for the time-averaged conditional CDF and show how their widths are determined by the depth of a binary search tree. We then show that this result is an instance of a framework through which one can construct valid confidence bands uniformly over time and over an arbitrary index set for any indexed family of time-averaged distribution functions. We illustrate the framework on importance-weighted and right-censored CDFs, as well as multivariate CDFs.

Figures & tables

Panel of Figure 1 — Figure 1: Example in which we observe the sequence $\{X_{1},X_{2},X_{3}\}=\{3,1,5\}$ and use ( 6 ) to successively construct cells $C_{s}(v)$ in $\mathcal{V}=\mathbb{R}$ . Each cell is identified by the string of moves on its path, with ${\star}$ for a step without a split. The final row shows the cells $C_{4}(v)$ used for a new observation $X_{4}$ . The highlighted cell belongs to probe $v=4$ and includes $N_{3}(v)=2$ splits, corresponding to $N^{\mathsf{R}}_{3}(v)=N^{\mathsf{L}}_{3}(v)=1$ .

Figure 2: Bands for

\overline{F}_{t}

. (a) Width at

t=10^{4}

against the quantile level, for i.i.d. Beta

(6,b)

data obtained from the same uniforms. (b) Sup-width at

t=10^{4}

for i.i.d. Unif

(0,x_{\max})

data. (c) Bands at

t=10^{3}

for two runs of the Pólya urn (ours shaded). (d) Sup-width against

t

for i.i.d. Beta

(6,3)

data.

Figure 3: (a) Bands at

t=10^{4}

for the counterfactual

\overline{F}^{W}_{t}

in the importance-weighted Pólya urn (ours shaded), with the factual running-average CDF. (b) Bands at

t=10^{4}

for

\overline{S}_{t}

with 40% of the subjects censored (ours shaded), and the band that ignores the censoring.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Dependencies of the proofs. An arrow from one result to another means that the proof of the second uses the first. Shaded boxes are results stated or announced in the main text. Panel (a) shows the shared machinery, namely the master band and the two charge templates, with Template A for bounded families in the upper row and Template B for nonnegative families in the lower row. Panels (b) to (f) start from these templates.

Panel of Figure 5 — Figure 5: Cutting a box $B$ (solid) at an observation $X_{s}$ (dot) in $d=2$ . The shaded part is $B\cap O_{s}=\{v\in B:v\geq X_{s}\}$ , where $f_{s}=1$ . The box is cut only when the shaded part is neither empty nor all of $B$ , as in (a) and (b), and only along the coordinates in which $X_{s}$ lies strictly inside $B$ (dashed).

Confidence Estimation

See all 43 papers

Online Inference in Distributional Temporal-Difference Learning
Aug 14, 2026Yang Peng, Liangyu ZhangDistributional RL Temporal-Difference Learning
Yau Mathematical Sciences Center, Tsinghua University. · School of Statistics and Data Science, Shanghai University of Finance and Economics.
Distribution-free inference on the number of changepoints
Sep 8, 2026Rohan Hore, Aaditya RamdasChange-Point Detection
Department of Statistics, Stanford University
MiNCE: Nonparametric, Strongly Consistent Confidence Envelopes for Band-Limited Functions and their Smoothed Spectra
Sep 8, 2026Balázs Csanád Csáji, Bálint HorváthConfidence Region Estimation Nonparametric Regression
HUN-REN SZTAKI: Institute for Computer Science and Control, Budapest, Hungary · Institute of Mathematics, Eötvös Loránd University (ELTE), Budapest, Hungary

Aug 14, 2026J/K move · Enter open · S save

Online Inference in Distributional Temporal-Difference Learning

Yang Peng, Liangyu Zhang

Yau Mathematical Sciences Center, Tsinghua University. · School of Statistics and Data Science, Shanghai University of Finance and Economics.

Distributional RL Temporal-Difference Learning

Open paper AskPDF arXiv

We study online statistical inference for functionals of the return distribution under a fixed policy. The return distribution is estimated by nonparametric distributional temporal-difference learning from a single Markov trajectory. For the Polyak--Ruppert averaged estimator, we prove that its root-

T

error converges weakly to a centered Gaussian random element in Cramér space. We also prove that, conditionally on the observed trajectory, the root-

T

difference between the bootstrap and original averages converges weakly to the same Gaussian limit. These results justify bootstrap inference for smooth statistical functionals, including variance, CVaR, expected shortfall, and expectiles. For nonsmooth statistical functionals, we develop a local asymptotic theory for the estimated return CDF over

T^{-1/2}

-neighborhoods of finitely many thresholds, together with its bootstrap analogue. This theory allows us to conduct inference for nonsmooth statistical functionals characterized by CDF equations, including return quantiles.

Abstract

Confidence Estimation

Explore similar work

Online Inference in Distributional Temporal-Difference Learning

Distribution-free inference on the number of changepoints

MiNCE: Nonparametric, Strongly Consistent Confidence Envelopes for Band-Limited Functions and their Smoothed Spectra