Time-uniform confidence bands for the CDF under nonstationarity
Authors: Paul Mineiro
Steven R Howard
Venue: NeurIPS 2023 poster (2023)
Keywords: off-policy evaluation
anytime-valid
TL;DR: CDF estimation when DKW doesn't apply, e.g., controlled experiments in nonstationary settings

Abstract: Estimation of a complete univariate distribution from a sequence of observations is a useful primitive for both manual and automated decision making. This problem has received extensive attention in the i.i.d. setting, but the arbitrary data dependent setting remains largely unaddressed. We present computationally felicitous time-uniform and value-uniform bounds on the CDF of the running averaged conditional distribution of a sequence of real-valued random variables. Consistent with known impossibility results, our CDF bounds are always valid but sometimes trivial when the instance is too hard, and we give an instance-dependent convergence guarantee.  The importance-weighted extension is appropriate for estimating complete counterfactual distributions of rewards given data from a randomized experiment, e.g., from an A/B test or a contextual bandit.

Time-uniform confidence bands for the CDF under nonstationarity
Paul Mineiro
Steve Howard The Voleon Group
Microsoft Research
crwsoft.ccmm
steve@steevehwwadd.o org
Abstract
Estimation of a complete univariate distribution from a sequence of observations is useful primitive for both manual and automated decision making. This problem has received extensive attention in the i.i.d. setting, but the arbitrary data dependent setting remains largely unaddressed. We present computationally felicitous time- uniform and value-uniform bounds on the CDF of the running averaged conditional distribution of sequence of real-valued random variables. Consistent with known impossibility results, our CDF bounds are always valid but sometimes trivial when the instance is too hard, and we give an instance-dependent convergence guarantee. The importance-weightee extension is appropriate for estimating complete coun- terfactual distributions of rewards given data from a randomized experiment, e.g..
from an A/B test or contextual bandit.
Introduction
What would have happened if I had acted differently? Although old time itself, successful companies have recently embraced this question via offline estimation of counterfactual outcomes using data from existing randomized experiments contextual bandits. The problem is important in diverse domains such as software testing [Lindon et al. 2022 Wang and Chapman [022), portfolio
management [Liu 202T]. and medicine (Shen et al.] 2022 These experiments are in the real (digital) world, which is rich enough to demand non -symmtttitoicc statistical techniques under non- parametric and non-stationary (i.e., not i.i.d.) models. Although existing methods apply for estimating average outcomes in this general setting (either under the observed distribution or counterfactual ones), estimating complete distribution of outcomes heretofore only possible with additional assumptions: see Table for summary and Section S for complete discussion of related work.
To fix ideas, briefly describe an application from Lindon al.) [2022] in the context of canary testing: rolling out changes in an online service to a small, random subset of users in order to detect accidental performance regressions while minimizing effect overall user experience. The metric of interest measures latency for fetching content from the service. is common to look beyond the mean of the latency distribution and especially check for regressions in upper quantiles. As such, the authors choose to estimate bounds on the entire CDF of this latency metric under both the control and treatment arms and check for statistically significant differences at any point in the CDF. The hope is to detect regressions as soon as possible, often within seconds or minutes, so the authors employ a sequential method which allows an automated system to continuously update the CDF bounds as data accumulates and to stop as soon as a significant regression is detected. Statistically, this translates into the requirement of confidence bands for the CDF which are both uniform over time (valid after every update) and uniform over values (so we can check for regressions at any quantile). We seek such bounds whose statistical validity is guaranteed under a minimum of assumptions.
Intriguingly, this problem is provably impossible in the general data dependent setting [Rakhlin et al. 2015). Consequently, our bounds always achieve momtasympto coverage, but may converge to zero width slowly or not at all, depending on the hardness of the instance. We call this design principle AVAST (Always Valid And Sometimes Trivial).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison prior art for quantile-unffom CDF estimation. Time-uniform: sequence of confidence bands whose coverage holds uniformly over time with high probability. Nonstationary: does not require i.i.d. assumption. Non-asymptotic: guarantees hold at all sample sizes. Non- parametric: guarantees apply over an infiniteddimensional class of distributions. Counterfactual: method applies to estimating distribution other than the one which generated the observed data, via importance weighting. Wmax-ffre: guarantee applies without a bound on the maximum importance weight. See Section
5 for details.
REFERENCE
TIME- UNIFORM?
NON- STATIONARY?
NON- ASYMPTOTIC?
NON- PARAMETRIC?
COUNTER- FACTUAL?
Wmax FREE?
HR22
N/A
HLLA21
UNO2T
[ID]
V
/
UNO2T
[NS]
WS22
$41
/
/
THIS PAPER
V
Contributions
1. In Section 3.2 we provide time- and value-uniform upper bound on the CDF of the averaged historical conditional distribution discrete-timg real-values random process. Consistent with the lack of sequential uniform convergence of linear threshold functions [Rakhlin et al.) [015), the bounds are Always Valid (see Theorem 3.1 And Sometimes Trivial, i.e., the width guarantee is instance-dependen (see Theorem 3.3) and may not converge to zero width in the infinite data limit. When the data generating process is smooth with respect to the uniform distribution on the unit interval, the bound width adapts to the unknown smoothness parameter, following the framework of smoothed online learning [Rakhlin et al. Block al., 2022
2011 Haghtalab et al., 2020 2022b
2. In Section 3.3 we extend the previous technique to distributions with support over the entire real line, and further distributions with known countably infinite unknown nowhere dense set of discrete jumps; with analogous instance-dependee guarantees.
3. In Section 3.4 we extend the previous techniques to importance-weighted random variables, achieving our ultimate goal of estimating complete counterfactual distribution of outcomes.
We exhibit our techniques various simulations in Section 4 have comparable cost to point estimation of the empirical CDF, as the empirical CDF is a sufficient statistic.
Computationally our procedures
Problem Setting
Let (2, (Fe)ien IP)) be probability space equipped with discrete-time filtration, on which let X, be an adapted, real-valued random process. Let E, [-] = E [.].J.. The quantity of interest the (random) map CDF, R [0, 1]. the CDF of the averaged historical conditional distribution at time
CDF (D)
- [xx
We desire simultaneously time- and value-uniform bounds which hold with high probability, i.e.. adapted sequences of maps L,, U2 R - [0, 1] satisfying
(())) CDF < U,(x)) > 2a. VPER
YteN
(2)
Note that the estimand CDF is changing at each time step as we incorporate the conditional distribution of the latest observation into our historical average. The maps L,, U, provide sequence of confidence bands which contain this sequence of changing CDFs uniformly over time with high probability.
In the i.i.d. setting, Equation T is deterministic and independent of reducing to the CDF of the (unknown) generating distribution. In this setting, the classic results of Glivenko [933 and

---

Testing thresholds p
Algorithm Unit Interval Upper Bound. <(d) is an increasing function specifying the resolution of discretization at level d. E, (p: ô, d, Vx) is an upper confidence sequence for fixed value p with coverage at least (1 - 8).
%/2
1/2
spend per level
4
4/4
3/4
Input: value v, confidence a; sufficient statis- tic V,-
%/8
1/8
%
7/3
e.g. V, X1x+ or v, (Wi X Output: (v) satisfying Equation if then return end if
Figure 1: Visualization of Algorithm|] The val- ues interest are uncountably infinite; the al- gorithm allocates probability to maintain upper bounds on a countably infinite set of points p at different resolution levels via the monotonicity of cDF, (v). As resolution increases, the value better approximates v, but the allocated probabil- ity decreases; the algorithm chooses the tightest of available bounds. Shaded nodes would con- sulted for an upper bound for 5/17.
u - 1
max (0, v) for d to 00 do
Pd ((d) [((d)u]
8 (/d(d+ ()((d)
U min (u, E. (pd; 8d, Vz))
if 0 Σx -x,evval then
return
end if
end for
established uniform convergence of linear threshold functions; subsequently the Konetzky-Kiefeer Wolfowitz (DKW) inequality characterized fixed-time and value-uniform conver- gence rates (Dvoretzky et al.] [956, Massart] [990]] extended later to simultaneously time- and value- uniform bounds (Howard and Ramdas 2022]. The latter result guarantees an O(t (l))))))) confidence interval width, matching the limit imposed by the Law of the Iterated Logarithm.
Cantelli 1933
AVAST principle In contrast, under arbitrary data dependence. linear threshold functions are not sequentially uniformly convergent, i.e., the averaged historical empirical CDF does not necessarily converge uniformly to the CDF the averaged historical conditional distribution [Rakhlin et al.. 2013]. Consequently, additional assumptions required to provide guarantee that the confidence width decays to zero. In this paper we design bounds that are Always Valid And Sometimes Trivial, Fortunately bounds are also equipped with an instance-dependen width guarantee based upon the smoothness of the distribution to reference measure qua Definition 3.2
ie., under worst-case data generation, (u,,) [v)v ((1)
Additional Notation Let Xa.b {X.) == denote a contiguous subsequence of random process. Let F, denote the average historical conditional distribution, defined as a (random) distribution over the sample space R by Pe(A) = t- E.st E [1x,eA] for Borel subset A (note P, represents the entire historical average while E, corresponds single conditional distribution).
Derivations
3.1 High Level Design
Our approaches work as reductions, achieving the value- and time-uniform guarantee of Equation 2 by combining bounds A,, E. that satisfy time-uniform guarantee any fixed value p,
P E Ac(p) & CDF,()) E.(p)) > 8(p)-
The bounds A,, E, tools for estimating sequence of scalars, in this (p)((p)) for a fixed value We show how to extend such tools to the more difficult problem of estimating a sequence of (cumulative distribution) functions.
There are multiple existing approaches to obtaining the guarantee of Equation we provide self- contained introduction in Appendix A For case of exposition, will only discuss how to construct

---

time- and value- unttrrrm upper bound by combining fixed-value, time-uniform upper bounds, and defer the analogous lower bound construction to Appendix Our approach is to compose these fixed-value bounds into value-uniform bound by taking union bound over a particular collection of values, leveraging monotonicity of the CDF.
Quantile vs Value Space In the i..d. setting, a value-uniform guarantee can be obtained by taking a careful union bound over the unique value associated with each quantile [Howard and Ramdas 2022]. This "quantile space" approach has advantages, e.g., variance based discretization and covariance to monotonic transformations. However, under arbitrary data dependence, the value associated with each quantile can change. Therefore we proceed in "value space". See Appendix A.1 for more details.
3.2 On the Unit Interval
Algorithm [ visualized in Figure D constructs upper bound on Equation ( which, while valid for all values, is designed for random variables ranging over the unit interval. For given value v, it searches over upper bounds on the CDF evaluated at decreasing sequence of values P1 P2 2 ... > and exploits monotonicity of CDF, That is, at each level d = 1, ........ we construct a discretizing grid of size e(d) over the unit interval, and construct a time-uniform upper bound on (p) for each grid point p using the value confidence sequence oracle E, Then, for given value v, at each level d we make use of the fixed-value confidence sequence for smallest grid point Pa e v, and we search for the level d which yields the minimal upper confidence bound. A union bound over the (countably infinite) possible choices for Pa controls the coverage of the overall procedure. Because the error probability dy decreases with d (and the fixed-value confidence radius E, increases 5 decreases), the procedure can terminate whenever observations remain between the desired value v and the current upper bound Pd: as all subsequent bounds are dominated.
The lower bound is derived analogously in Algorithm (which we have left to Appendix B.2 for the sake of brevity) and leverages lower confidence sequence A, (p; 6, w)) (instead an upper confidence sequence) evaluated at an increasingly refined lower bound on the value p (e(d)_)
Theorem 3.1. If E(d) 1 d 1 oc, then Algorithms 7 and terminate with probability one. Furthermore, for all p. 6, and the algorithms Ae(p; V.) and Er(p; ō, M.) satisfy
P(VL: : CDF, > O, v.)) > 1 1 5,
(4)
P(VL: (pF & 5, v.)) 1 5.
(5)
then guarantee ② holds with Ue, Le given by the outputs of Algorithms Aand? respectively.
Proof. See Appendix B.3
Theorem 3.1 ensures Algorithms 1 and 2 yield the desired time- and value-uniform coverage, essentially due to the union bound and the coverage guarantees of the oracles E,, Aç. However, coverage also guaranteed by the trivial bounds & CDF((v) < 1. The critical question is: what is the bound width?
Smoothed Regret Guarantee Even assuming X is entirely supported on the unit interval, on what distributions will P
non-trivial bound? Because each [Ar(p; 6, U,),, Ex(p; 8, V,)] confidence sequence for the mean of the bounded random variable 1 1x, we enjoy width guarantees at each of the (countably infinite) p which are covered by the union bound, but the guarantee degrades as the depth d increases. If the data generating process focuses on an increasingly small part of the unit interval over time, the width guarantees to determine the distribution. Indeed, explicit constructions demonstrating the lack of sequential uniform convergence of linear threshold functions increasingly focus in this manner [Block et al. 2022].
discretization will be insufficient
Conversely, if Vt: CDF((2) was Lipschitz continuous in v, then our increasingly granular discretiza- tion would eventually overwhelm any fixed Lipschitz constant and guarantee uniform convergence. Theorem 3.3 expresses this intuition, but using the concept of smoothness rather than Lipschitz, as smoothness will allow us to generalize further [Rakhlin et al. 2011 Haghtalab et al. 2020 2022b
Block et al. 2022

---

Continarux Polya Um,, y
the EM you Kudd
Ldd. Betef6, 3)
bourds 1200, K,-
the ETP
bour AL00130G.
52
10
9.0
022
0.5 28
09
02
Figure 2: CDF bounds approaching the true CDF
Figure 3: Nonstationary Pólya simulation for two seeds approaching different average conditional CDFs. Bounds successfully track the true CDFs
when sampling i.i.d. from Beta(6,3) distribution. Note these bounds are simultaneously valid for all times and values.
in both cases. See Section 4.2
Definition 3.2. A distribution D is {-smooth wrt reference measure M D M and ess supM (dD/aM) < g-
When the reference measure is the uniform distribution on the unit interval, f-smoothness implies an g L--Liischitz CDF. However, when the reference measure has its own curvature, or charges points, the concepts diverge. When reading Theorem 3.3 note 1 (since the reference measure a probability distribution) and as & - the smoothness constraint increasingly relaxed. Thus states "for less smooth distributions, convergence is slowed."
Theorem 3.3
Theorem 3.3. Let UV(v) and L((v) be the upper and lower bounds returned by Algorithm and
Algorithum 2 respectively, when evaluated with c(d) 2 and the confidence sequences Dt and E, of
Equation
1. 1fVt: IP's is Es-smooth wrt the uniform distribution on the unit interval then
Vt,Yo Vo Us(v) - -L(()) <
VE + δ
(V log ( (a-1)/22)
(/V
(6)
where q: = CDF,(t); V, + (g+ 1/21///g////// 1///////1////////////// aa); and Ō() elides polylog factors.
Proof. See Appendix
Theorem 3.3 matches our empirical results in two important aspects: (i) logarithmic dependence upon
smoothness (e.g.,. Figure/4); (ii) tighter intervals for more extreme quantiles (e.g., Figure 2). Note choice (d) 2d ensures the loop in Algorithm ] terminates after most log, (A) iterations, where the minimum difference between two distinct realized values.
Worked Example synthetic data set.
To build intiution, in Appendix B.I we explicitly calculate Algorithm ! for
3.3 Extensions
Arbitrary Support In Appendix D.I we describe a variant Algorithm which uses a countable dense subset of the entire real line. It enjoys similar guarantee to Theorem 3.3 but with additional
width which is logarithmic in the probe value Ô
( Vi log ((2 + f/// 2a 163/2
Note in this case & is defined relative to (unnormalized) Lebesgue measure and can therefore exceed 1.
Discrete Jumps Pf is smooth wrt a reference measure which charges countably infinite number of known discrete points, their density the reference measure. In this case we preserve the above malue-uniform guarantees. See Appendix [D22 for more details.
explicitly union bound over these additional points proportional to
For distributions which charge unknown discrete points, we note the proof Theorem 3.3 only exploits smoothness local to v. Therefore if the set of discrete points is nowhere dense, we eventually recover the guarantee Equation (6) after a "burn-in" time which is logarithmic in the minimum distance from charged discrete point.
5

---

Un DGN
lAd.x Betals. Pardb(
2.0
10
2010 15 10 10" 20" 10 15-7
Figure 4: As smoothness decreases, we require more time to reach the same maximum confidence width. For low smoothness, DKW dominates our method. The logarithmic dependence matches our theory. See Section 4.1
Figure 5: CDF bounds' approaching the true counterfactual CDF when sampling i.i.d from Beta(6,3) with ffinite-variance importance weights, using DDRM for the oracle confidence sequence.
3.4 Importance- Weighted Variant
An important case is estimating distribution based upon observations produced from another distribution with known shift, e.g., arising in transfer learning [Pan and Yang [0100] or off- off-policy evaluation (Waudby-Smitt et al. 2022 In this case the observations are tuples (W X2), where the importance weight We is a Badon-Nikodym derivative, implying Vt. E, [W.] = and a.s.
W. > 0; and the goal is to estimate CDF, (u) = t-- = E. E, [W, 1x, The basic approach in Algorithm and Algorithm iss still applicable in this setting, but different A, and E, required. In Appendix we present details on two possible choices for A, and E,: the first is based upon the empirical Bernstein construction Howard al. [2021), and the second based upon the DDRM construction of Mineiro 2022]. Both constructions leverage the I,* Adagrad bound of Orabonal 2019] enable lazy evaluation. The empirical Bernstein version is amenable analysis and computationally lightweight, but requires finite importance weight variance to converge (the variance bound need not be known, as the construction adapts to the unknown variance). The DDRM version requires more computation but produces tighter intervals. See Section for a comparison.
Inspired by the empirical Bernstein variant, the following analog of Theorem 3.3 holds. Note F. the target impporaace--eeihtee. distribution, not the observation moo-importance-weighee distribution.
Theorem 3.4. Let (V) and Lu( be the upper and lower bounds returned by Algorithm and Algorithm 2 respectively with <(d) = 2 and the confidence sequences D₃ and E, of Equation Vl. P. is Emsoohth wrt the uniform distribution on the unit interval then
If
Vl U((v) - L.(v) &
( + Vo)/t
B₁ +
(7)
(T Vi)it
log (Et 2-11)
Ō(t (EE 2 "a)
where qe = (DF, K(ge) = (a. (n-11/2/oog(n/i
Ve 0 (K(a) W?). B. =
--E E. (W 1), and Ö() elides polylog Vi factors.
Proof. See Appendix
E.2
Theorem 3.4 exhibits the following key properties: (i) logarithmic dependence upon smoothness; (ii) tighter intervals for extreme quantiles and importance weights with smaller quadratic variation; (iii) no explicit dependence upon importance weight range; (iv) asymptotic zero width for importance weights with sub-linear quadratic variation.
Additional Remarks First, the importance- weighted average CDF a well-defined mathematical
quantity, but the interpretation as counterfactual distribution of outcomes given different actions in the controlled experimentation setting involves subtleties: we refer the interested reader to Waudby
Smith et al. 2022) for complete discussion. Second, the need for nonstationarity techniques for

---

L-d. Lnglemalll,
unitam DOY
50.0
importance hidd Continouus Potya um
y
0.04
52
0.22
-1000
5.0
0.00
12F 12F 1.0 365
Figure 6: A nonstationary. importance- weighted simulation in which the factual distribution (red) diverges dramatically from the counterfactual dis- tribution (green). The bound correctly covers the counterfactual CDF.
Figure 7: Demonstration the variant described
in Section 3.3 and Appendix [.I] for distributions with arbitrary support, based on i.i.d. sampling from variety of lognormal distributions, Loga- rithmic range dependence is evident.
estimating the sepportance-wiighte CDF is driven by the outcomes (X₂) and not the importance- weights (W,). For example with off-policy contextual bandits, a changing historical policy does not induce nonstationarity, but a changing conditional reward distribution does.
4 Simulations
These simulations explore the empirical behaviour of Algorithm [ Algorithm when instantiated with (d) 2d and curved boundary oracles A and E. To save space, precise details on the experiments well additional figures are elided to Appendix Reference implementations which reproduce the figures are available at htttps://githhi /ggbhbb..bb.. com wttm//ccoooooftccoooooooooo
4.1 The i.idd setting
These simulations exhibit our techniques on i.i.d. data. Although the i.i.d. setting does not fully exercise the technique, it convenient for visualizing convergence to the unique true CDF. In this setting the DKW inequality applies, so to build intuition about our statistical efficiency, we compare our bounds with naive time-uniform version of DKW resulting from (%/2222 union bound over time.
Beta distribution In this case the data is smooth wrt the uniform distribution on [0. 1] so we can directly apply Algorithm| [ and Algorithm| [ Figure[sshows shows the bounds converging to the true CDF as increases for an i.i.d. Beta(6, (6, 3) realization. Figure 8 compares the bound width to time-uniform DKW at = 10000 for Beta distributions that are increasingly less smooth with respect to the uniform distribution. The DKW bound is identical for all, but our bound width increases as the smoothness decreases.
The additional figures in Appendix Felearly indicate tighter bounds at extreme quantiles, in corre- spondence with Theorem 3.3
Beyond the unit interval In Figure (main text) and Appendix we present further simulations i.... lognormal and Gaussian random variables, ranging over I and R respectively, and using Algorithm The logarithmic dependence of the bound width upon the probe value is evident.
An Exhibition of Failure Figure 4 shows the (empirical) relative convergence when the data is simulated i.idd uniform over [0, e] for decreasing (hence decreasing smoothness). The reference width the maximum bound width obtained with Algorithm and Algorithm a tąes 10000 and c= =1/16, and shown is the multiplicative factor of time required for the maximum bound width to match the reference width as smoothness varies. The trend is consistent with arbitrarily poor convergence with arbitrarily small e. Because this is i.i.d. data, DKW applies and uniform bound (independent of e) is available. Thus while our instance-dependent guarantees are valuable in practice, they can be dominated by stronger guarantees leveraging additional assumptions. On positive note, a logarithmic dependence on smoothness evident over many orders of magnitude, confirming the analysis of Theorem 3.3

---

Importance-
In these simulations, in addition to being i..d.. X, and W are drawn independently of each other, the importance weights merely merease the difficulty of ultimately estimating the same quantity.
In the importance-weighter case, additional aspect is whether the importance-weights have finite or infinite variance. Figures and 13 demonstrate convergence in both conditions when using DDRM for pointwise bounds. Figures and 15 show the results using empirical Bernstein pointwise bounds. In theory, with enough samples and infinite precision, the infinite variance Pareto simulation would eventually cause the empirical Bernstein variant reset to trivial bounds, but in practice this is not observed. Instead, DDRM is consistently tighter but also consistently more expensive to compute, as exemplified Table Thus either choice potentially preferable.
Table 2: Comparison of DDRM and Empirical Bernstein on i.i.d X2 ~ Beta(6, 3), for different Wr- Width denotes the maximum bound width sup, Uz(u) Le(v). Time for computing the bound 1000 equally spaced points.
W
WHAT
WIDTH
TIME (SEC)
DDRM
0.09
24.8
EXP(1)
EMP. BERN
0.10
1.0
DDRM
0.052
59.4
PARETO(%/2)
EMP. BERN
0.125
2.4
4.2 Nonstationary
Continuous Polya Urn In this case
X, Beta
2 " Σ 1x % Σ 1x e5t
i... X, Beta distributed with parameters becoming more extreme over time: each realization will ta. In the most extreme case that (t -. 1 1x,= the conditional distribution time is Beta (x; 2 + t7t, 2) O(t hence dP./au 0(1++9), which is smooth enough for our bounds to converge. Figure 3 shows the bounds covering the true CDF for two realizations with different limits. Figure shows (for one realization) the maximum bound width, scaled by / ///log(t) to remove the primary trend, as function of t for different y schedules.
increasingly concentrate either towards O or 1. Suppose
Importance- Weighted Continuous Polya Urn In this case W. is drawn i.i.d. either W, 0 or W, = Wmax. such as might occur during off off-policy evaluation with an epsilon- greedy logging policy. Given Wt, the distribution of X, is given by
X, W, Beta
+ n Σ 1x,=1/21w.--0g
act
2 + 7 Σ s<t
1x
ie.. each importance weight runs an independent Continuous Polya Urn. Because of this, it is possible for the unweighted CDF mostly concentrate at one limit (e.g.. 1) but the weighted CDF to concentrate another limit (e.g., 0). Figure this phenomenon.
5 Related Work
Constructing nonasymptotic confidence bands for the cumulative distribution function of i.i.d. ran- dom variables classical problem of statistical inference dating back to DDooetzky al. (1956) and Massart [990]. While these bounds are quantilc-unffomm, they are ultimately fixed-time bounds

---

(i.e. not time-umiien tine-uniform). In other words, given sample of i..dd random variables X,...., Xn F. these fixed time bounds (f..(x)) Un(x)) satisfy guarantee of the form:
P(Vx IR, In( & F(x) & (x)))) 2 a,
(8)
for any desired error level a (0,1). 1). Howard and Ramdas 2022] developed confidence bands (T.()))U (=)))REER that are both quantile- and time-uniform, meaning that they satisfy the stronger guarantee:
P(V2 e R,LEN, N, L,(x) F()) < U.(x)) > 1 1
However, the bounds presented in Howard and Ramdas [022] ultimately focused on the classical i..d. on-policy setup, meaning the CDF for which confidence bands are derived is the same CDF as those of the observations (X,) This is in contrast to off- off-policy evaluation problems such as in randomized controlled trials, adaptive A/B tests, or contextual bandits, where the goal is to estimate a distribution different from that which collected (e.g. collecting data based on a Bernoulli experiment with the goal of estimating the counterfactual distribution under treatment or control). Chandak et al.] [2021) and Huang et al. (202I) both introduced fixed-time (i.e. non-time-uniform) confidence bands for the off-policy CDF in contextual bandit problems, though their procedures are quite different, rely on different proof techniques, and have different properties from one another. |Waudby-Smite et al.
2022, Section 4] later developed time-uniform confidence bands in the off- off-policy setting, using technique akin to Howard and Ramdas [2022] Theorem 5] and has several desirable properties in comparison to Chandak et al. [2021] and Huang et al. [021 as outlined in Waudby-Smill et al.
2022 Table 2].
Nevertheless, regardless of time-uniformity or on/off-policy estimation, all of the aforementioned prior works assume that the distribution to be estimated is fixed and unchanging over time. The present paper takes significant departure from the existing literature by deriving confidence bands that allow the distribution to change over time in a data-dependent manner, all while remaining time-uniform and applicable to off-policy problems in contextual bandits. Moreover, we achieve this by way of novel stitching technique which is closely related to those of Howard and Ramdas 2022
and Waudby- Smith et al. 2002
6 Discussion
This work constructs bounds by tracking specific values, in contrast with i.idd. techniques which track specific quantiles. The value-based approach is amenable to proving correctness qua Theorem 3.1 but has the disadvantage of sensitivity to monotonic transformations. We speculate it is possible to be covariant to a fixed (wrt time) but unknown monotonic transformation without violating known impossibility results. A technique with this property would have increased practical utility.
Acknowledgments and Disclosure of Funding
The authors thank Ian Waudby-Smint for insightful discussion and review.
References
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. arXiv preprint arXiv:2202.04699) 2022.
Francesco Paolo Cantelli. Sulla determinazione empirica delle leggi di probabilita. Giorn. Ist. Ital. Attuari, 4(421-424) 1933.
Yash Chandak, Scott Niekum, Bruno da Silva, Erik Leamed-Miller Emma Brunskill, and Philip Thomas. Universal ooo-py evaluation. Advances in Neural Information Processing Systems, 34: 27475-27490, 2021.
Joannis Chatzigeorgiou. Bounds on the lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters. 100-11555-5588. 2013.

---

Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator, The Annals of Mathematical Statistics, pages 642-669, 1956.
Xiequan Fan, lon Grama, and Quansheng Liu. Exponential inequalities for martingales with applica- tions. Electronic Journal of Probability, 20:1-22, 2015.
William Feller. An introduction to probability theory and its applications, 3rd edition. Wiley series in probability and mathematical statistics, 1958.
Valery Glivenko. Sulla determinazione empirica delle leggi di probabilita. Gion. Ist. Ital. Attauri., 92-99, 1933.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed Analysis of Online and Dif- ferentially Private Learning. In Advances in Neural Information Processing Systems, volume 33, pages 9203-9215, 2020.
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries, November 2022a. arXiv:2202.08549 [cs, stat].
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed Analysis with Adaptive Adversaries. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022b.
pages
Steven R Howard and Aaditya Ramdas. Sequential estimation of quantiles with applications to A/B testing and best-arm identification. Bernoulli, 1804)177 2022.
Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparamet- ric, nonasymptotic confidence sequences. The Annals of Statistics, 4902):1055-1000, 2021.
Audrey Huang, Liu Leqi, Zachary Lipton, and Kamyar Azizzadeneshelii Off-policy risk assessment in contextual bandits. Advances in Neural Information Processing Systems, 34:23714-23726, 2021.
Michael Kearns and Lawrence Saul. Large deviation methods for approximate probabilistic inference. In Proceedings of the Fourteenth conference Uncertainty in artificial intelligence, pages 31 319, 1998.
Michael Lindon, Chris Sanden, and Vaché Shirikian. Rapid regression detection in software de- ployments through sequential testing. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3336-3346, 2022.
Wentao Liu. Risk-Aware Financial Portfolio Management with Distributional Deep Deterministic Policy Gradient. PhD thesis, University of Toronto (Canada), 2021.
Pascal Massart. The tight constant in the Cooretzky-Kiefeee Wolfowitz Probability, pages 1269-1283, 1990.
Wifffr--wwieeefw-ootittz inequality. The annals of Paul Mineiro. A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean. arXiv preprint arXiv:2210.1 1/133, 2022.
Frank WJ Olver, Daniel W Lozier, Ronald F Boisvert, and Charles W Clark. NIST handbook of mathematical functions functtoo hardback and CD-ROM. Cambridge university press, 2010.
Francesco Orabona. A modern introduction online learning, arXiv preprint 13X2v:1912.13213. 2019.
Sinno Jialin Pan and Qiang Yang. survey on transfer learning. IEEE Transactions on knowledge and data engineering, 13150)1334-1355 2010.
Iosif Pinelis. Exact lower and upper bounds on the incomplete gamma function. arXiv preprint 20050:2000506384. 2020.
10

---

Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online Learning: Stochastic, Constrained, and Smoothed Adversaries. In Advances in Neural Information Processing Systems, volume 24, 2011.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161(1)1111-53, 2015.
Glenn Shafer, Alexander Shen, Nikolai Vereshchagin, and Vladimir Vovk. Test martingales, Bayes factors and p-values. Statistical Science, 201, 2011.
Yi Shen, Jessilyn Dunn, and Michael M Zavlanos. Risk-averse multi-armed bandits with unobserved confounders: A case study in emotion regulation in mobile health. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 144-149. IEEE, 2022.
Yuheng Wang and Margaret Chapman. Risk-averse autonomous systems: brief history and recent developments from the perspective of optimal control. Artificial Intelligence, page 103743, 2022.
lan Waudby-Smith, Lili Wu, Aaditya Ramdas, Nikos Karampatziakis, and Paul Mineiro. Anytime- valid off- oof-colicy inference for contextual bandits. arXiv preprint arXiv:2210.10668, 2022.

---

A Confidence Sequences for Fixed V
Since our algorithm operates via reduction pointwise confidence sequences, provide brief self-contained review here, We refer the interested reader to Howard et al. [2021] for more thorough treatment.
confidence sequence for a random process X₃ is a time-indexed collection confidence sets CI2 with time-uniform coverage property P (V' N: X2 E C4² the concept lower confidence sequence can be defined via I (vt E N. X, > L,) > 1 - a, and analogously for upper confidence sequences, and lower and upper confidence sequence can be combined to form a confidence sequence CI₃ { L & x & Uz} with coverage (1 2ox) via a union bound.
For real random variables,
One method for constructing a lower confidence sequence for real valued parameter 2 is to exhibit a real-valued random process (z) which, when evaluated at the true value 2* of the parameter of interest, is a non-negative supermartingale with initial value 1, in which case Ville's inequality If the process E2(2) is monotonically increasing in 2, then the supremum of the lower contour L, sup, {2| (2)) & a-13 } is suitable lower confidence sequence; an upper confidence sequence can be analogously defined.
ensures P (vt N. Ex(=*) & +
We use the above strategy follows. We bound these deviations using the following nonnegative martingale,
Ex(A) exp
AS, Σ log (h(2,
Elog
(10)
where À E is fixed and ((A, = (1- -1-2)e= + (1-=) the moment- -eenenttgenerrting function of centered Bernoulli::) random variable. Equation (10) is test martingale qua Shafer et al. [201]] ie., it can be used to construct time-uniform bounds on d: - q: via Ville's inequality.
qua/Shafer
Next we lower bound Equation 10
(A) = exp
XS Σ
log (M(A,0.))
10
seet
and eliminate the explicit dependence upon tz by noting log h(,,) :) is concave and therefore Ex(A) > exp (At (q: âc) - -t log h (X, q:))
(11)
because (ef(g) max o/1 I 0- E.se f(0)) for any concave Equation 11 monotonically
increasing in and therefore defines lower confidence sequence. For an upper confidence sequence we use q:
(1 q:) and a lower confidence sequence on (1 (1-4: -a))
Regarding the choice of X, in practice many À are (implicitly) used via stitching (i.c., using different in different time epochs and majorizing the resulting bound in closed form) mixing (i.e., using a particular fixed mixture of Equation (1T) via discrete sum or continuous integral over A); our designing for tight asymptotic rates low computational
choices will depend upon whether footprint. We provide specific details associated with each theorem or experiment.
Note Equation [ is invariant to permutations of X and hence the empirical CDF at time is sufficient statistic for calculating Equation at any v.
A.1 Challenge with quantile space
In this section assume all CDFs are invertible for ease of exposition.
In the i..dd setting, Equation 100 can be evaluated at the (unknown) fixed v(g) which corresponds to quantile Without knowledge of the values, one can assert the existence of such values for a countably infinite collection of quantiles and careful union bound of Ville's 's inequality a particular discretization can yield an LIL rate: this the approach of Howard and Ramdas (2022). A key advantage of this approach is covariance monotonic transformations.
Beyond the i.i.d setting, one might hope to analogously evaluate Equation (10 at an unknown fixed value (g(g) which for each & corresponds to quantile q. Unfortunately, vz(g) is not just unknown,
12

---

but also unpredictable with respect to the initial filtration, and the derivation that Equation (TO) is martingale depends upon being predictable. In the case that X, independent but not identically distributed, (g(g) is initially predictable and therefore this approach could work, but would only be valid under this assumption.
The above argument does not completely foreclose the possibility of a quantile space approach, but merely serves to explain why the authors pursued value space approach in this work. We encourage the interested reader to innovate.
B
Unit Interval Bounds
B.1 Worked Example
Our (synthetic) data set consists of five values, each of which has occurred 1000 times:
D {10000 0), (1000, 1/r), (1000, 2/7), (1000, 1/7), (1000, 9/r))
We use resolution c(d) = 2d and coverage error a = 1/20.
Upper bound for e 4/7 The upper bound algorithm starts with the trivial upper bound of 1. The first evaluated point P1 = 2 12 o| = 1 again yields the trivial bound of There are still empirical counts between the probe value (v 4/7) and the bound value (pi 1) so the algorithm continues. The second evaluated point P2 = 2 2-2[22u] = 3/4, for which there are 4000 empirical counts below P2 out of 5000 total. The pointwise confidence sequence is evaluated with counts (4000, 5000) and coverage error 62 = 0/24, resulting in improved bound x 0.825. Now, there are no empirical counts between the probe value (v = 4/7) and the bound value (02 3/4) the algorithm terminates. To all subsequent bounds are dominated, note that a tighter upper bound Pa>2 will result in the same empirical counts (4000 out of 5000) but looser coverage error and hence worse bound.
Upper bound for = 13/28 The upper bound algorithm starts with the trivial upper bound of 1. The first evaluated point A1 2- ul 1/2, for which there are 4000 empirical counts below P2 out of 5000 total. The pointwise confidence sequence is evaluated with counts (4000, 5000) and coverage error 5, a/4, resulting in improved bound 0.822. There are no empirical counts between the probe value (u = 13/2s) and the bound value (p) = 1/2) so the algorithm terminates. Relative to the previous example, the bound is slightly tighter the discretization worked better for this v.
Upper bound for v = 5/14 The upper bound algorithm starts with the trivial upper bound of 1. The first evaluated point P1 = 2- u] 1/2, for which there are 4000 empirical counts below P2 out of 5000 total. The pointwise confidence sequence is evaluated with counts (4000, 5000) and coverage error 8, 4/4, resulting in improved bound v 0.822. There empirical counts between the probe value (r 5/14) and the bound value (p) = 1/2) so the algorithm continues. The second 1/2, which has the same empirical counts but worse coverage error at this level, and hence does not improve the bound. There are empirical counts between the probe value (v 5/14) and the bound value (p2 = 1/2) so the algorithm continues. The third evaluated point P3 = 2 [2 1/8, for which there are 3000 empirical counts below P3 out of 5000 total. The pointwise confidence sequence is evaluated with counts (3000, 5000) and coverage error 8z- = a/9s, resulting in improved bound x 0.633. There are empirical counts between the probe value (u 5/14) and the bound value (ps 3/s) so the algorithm terminates.
evaluated point P2 2-2[22x]
B.2 Lower Bound
Algorithm is extremely similar to Algorithm 1 the differences are indicated in comments. Careful inspection reveals the output of Algorithm Ue(e), can be obtained from the output of Algorithm 2 L.(,, via U+) = 1 - [1 - v); but only if the sufficient statistics are adjusted such that E.(pa; 6, V.)
A,(1 Pa; 8, V.). The reference implementation uses this strategy.
B.3 Proof of Theorem 3.1
We prove the results for the upper bound Algorithm T the argument for the lower bound Algorithm similar.
13

---

Algorithm 2 Unit Interval Lower Bound, <(d) is an increasing function specifying the resolution of discretization at level d. A, (p; d, V.) lower confidence sequence for fixed value p with coverage at least (1 8).
Input: value confidence a; sufficient statistic v. // comments below indicate differences from upper bound
v. = X or = (Wet.
Output: (v) satisfying Equation
if then return 0 end if
II check for underflow range rather than overflow
I ---00
// initialize with 0 instead of 1 I/ project onto [0, using min instead of max
min (1 for = to 30 do
Pd - c() ((d))'((d)d))
I/ floor instead ceiling use lower bound instead of upper bound
8g ((2
max (1, Ar (pa; 6, vr))
if 0 = En x.e(aae) then
return
end if end for
The algorithm terminates when we find d such that Mise X,,evvppa-- Since c(d) 1 oo as d æc, we have Ps = <(d)[e(d)~ 'bl J u, so that E.sr 1 [xe(v,nd 1 0. So the algorithm must terminate. At level d, we have c(d) confidence sequences. The 5th confidence sequence at level d satisfies
CDF, > (i/e(d))); v.)) & 2dc(d)
(12)
Taking union bound over all confidence sequences at all levels, we have
P PAde (1, (I, d,, CDF (D/(((/(()) dd v.)) a.
(13)
Thus we are assured that, for any E R.
P(Yt, d: (DF,(U) & CDF & Ec(pa da, d, v.))
(14)
Algorithm will return Epap: 8a, d, V,) for some d unless all such values larger than one, in which case it returns the trivial upper bound of one. This proves the upper-bound half of guarantee 2 A similar argument proves the lower-bound half, and union bound over the upper and lower bounds finishes the argument.
C Proof of Theorem 3.3
Theorem 3.3. Let Ug(v) and L.(v) be the upper and lower bounds returned by Algorithm and Algorithmm 2 respectively, when evaluated with e(d) 2nd and the confidence sequences Ar and E, of Equation 15 If P. is & smooth wrt the uniform distribution on the unit interval then
Vt, Vo: Uz(v) - Lo(v) <
VE t
+ Ô (V log 25
(6)
where d CDF((v): V, 1/2 + (a. //) and Ö() elides polylog V, factors.
Note is fixed for the entire argument below, and denotes the unknown smoothness parameter time t.
We will argue that the upper confidence radius (1()) 1-1 Σ Se 1x, has the desired rate. An anal- ogous argument applies the lower confidence radius --1 E.st Lx,s0 L((v), and the confidence width Uz(z) Le(v) is the sum of these two.
14

---

For the proof we introduce an integer parameter > 2 which controls both the grid spacing (e(d) = 17") and the allocation of error probabilities levels (6ą = a/ e(d))(())) In the main paper we set 1 2.
At level d we construct 17 confidence sequences evenly-spaced grid of values 1/1/, 2/n ..... 1. We divide total error probability a/1/" at level d among these 17 confidence sequences, that each individual confidence sequence has error probability a//12d.
For fixed bet and value p, St defined in Section 3.2 is sub-Bernoulli qua Howard et al. 2021
Definition 1] and therefore sub-Gaussian with variance process V, LK (g)). where (p)
12p-1)/2 (1/ is from Kearns and Saul [1998]; from Howard et al. 2021 Proposition 5] follows
that there exists an explicit mixture distribution over such that
M(t: (). = (tt + r) log
1/2d
[K(
+T
+ +1)
(15)
2a
7
a (curved) uniform crossing boundary, i.e., satisfies
a
M(ti(,,))
2
3t 1: S
172d
t
where S. - E.gt Ix,en is from Equation 10). and T is hyperparameter to be determined further below.
Because the values at level are 1/m apart, the worst-case discretization error in the estimated average CDF value is
CDF CDF,(e(d)(e(d)~-v) CDF < 1/(Ean"),
and the total worst-case confidence radius including discretization error
2 (K(4) + T/U) log
1,20 (K((g)) +
ra(t)
ELTP +
+
2a
Now evaluate at d such that Vile < EnT & n/ where the = =((((q)) +T/t)
K(qd + T/t
(K (q)) + T/t)
212
tK(g) + +1)
ra(t)= &
log
t
2a
K(qt) + T/t
The final result not very sensitive to the choice of r, and we use t = in practice.
D Extensions
D.1 Arbitrary Support
Algorithm is variation on Algorithm which does not assume bounded range, and instead uses a countably discrete dense subset of the entire real line. Using the same argument of Theorem 3.3 with the modified probability from the modified union bound, have
[hal - 1 4el & [kal.
E// V Wi 17 = nj -T V.
= 1 + 1kal < 2 Ec/ul/
ra(t) & Ô (V
Vi
log ((2 Edultt E/lutt-1/2) 2-- 183/2)
demonstrating logarithmic penalty in the probe value (c.g., Figure 7
15

---

Algorithm 3 Entire Real Line Upper Bound, (dd) is an increasing function specifying the resolution of discretization at level d. Ex (p: 6, d, v,) an upper confidence sequence for fixed value p with coverage at least (1 6). 8).
Input: value confidence a; sufficient statistic V.
e.g. V. X1a or Vr (Wi,, X1.4)
Output: (z( satisfying Equation (
u --1
for to do
ki [e(d)=tvl
// Sub-optimal: see text for details
pa e(d)ka
8g - (0/2*)
// Union bound over d E N and ka 6 Z
u min (u, (pa: dd, v.))
if 0 = Eese (x,e then
return
end if
end for
Sub-optimality of ka The choice of ka in Algorithm 3 is amenable analysis, but unlike in Algorithm[] [ it is not optimal. In Algorithm the probability is allocated uniformly at each depth, and therefore the closest grid point provides the tightest estimate. However in Algorithm probability budget decreases with [kia] and because ka can be negative, is possible that a different ka produce tighter upper bound. Since every k is covered by the union bound, in principle could optimize over all ka but it is unclear how to do this efficiently. In our implementation we do search over all kig but do adjust ka be closest to the origin with the same empirical counts.
the
D.2 Discrete Jumps
Known Countably Infinite Suppose D is smooth wrt a reference measure M, where M is of the form
M M + Σ Gil.
iel
with 7 countable index set, 1 > sir Si and M sub-probabilityy measure normalizing to (1
Eger G.). Then we can allocate (1 Eier Gi) of our overall coverage probability bounding M
using Algorithm [ [nd Algorithm 2 For the remaining {urker we can run explicit pointwise bounds each with coverage probability fraction G.
Computationally. early termination of the infinite search over the discrete bounds is possible. Suppose (wlog) I indexes Ç in non-increasing order, i.e., j S & Sj: then remaining empirical counts between the desired value v and the most recent discrete value v; the search over discrete bounds can terminate.
there are
E Importance- Variant
E.1 Modified Bounds
Algorithm| and Algorithm 2 are unmodified, with the caveat that the oracles A, and E, must
operate on an importance-weighter realization (Wia, X1æ),, rather then directly on the realization
X Lit.
E.1.1 DDRM Variant
For simplicity we describe the lower bound A, only. The upper bound derived analogously via the equality Y, W. (W, Y.) and lower bound (W, Y.): see Waudby- al. 2022 Remark 3] for more details.
This is the Heavy NSM from Mineiro 2022 combined with the _ bound of Orabona 2019 $4.2.3].
The Heavy NSM allow us to handle importance weights with unbounded variance, while the Adagrad L bound facilitates lazy evaluation.
16

---

For fixed v, let Y = Wilx,vv be non-negative real-valued discrete-time random process, let Y E [0, 1J be predictable sequence, and let X [0, 1) be fixed scalar bet. Then
Bx(A) = exp A
Σ S
Y. E. [Y3]
log (1 A (Yy-YY.))
#
is a test supermartingale [Minciro 2022 $33. Manipulating,
E((A) exp
A
Σ Y, E, [X:]
[Y2]] -
- Σ a (Y, -P.) log + (Y, (Y, -P,
=n(A(s,-
exp
A
Σ Y, E.-1 [YA]
Σ () (ax. -11))
185t
35t
Σ h () (Y, (/ )イ)) -Reg(t)
Σ Y, Ey-1 [Y.]
Reg(t)
exp
exp
Σ E. [X.] #5E
+
Σ SEt
log (1 a (r. px)) Reg(()
where for (f) we use no-regret learner h() with regret Reg(t) to any constant prediction
Y: [0, 1]. The function h() is M-smooth with M
X² (1- so we can get an I,* bound Orabona
2019
$4.2.3] of
12 (1
Reg(t)
+
Σ > (v. v7+))
2)2
X
( (117 + Σ Y - Σ log (1+ 11+A(Y-- (Y+)) 1,+)). S5t
2
4
+
(1 - X)2
1 1
thus essentially our variance process is inflated by square-root. In exchange do not have to actually run the no-regret algorithm, which eases the computational burden. We can compete with any in in-hindsight prediction: if we choose to compete with the clipped running mean Y, then we end up with
( min t, EY #Et
E((A) > exp
[Y.1 Yg - E. 11.1
+ Σ log A - Y,) - -Reg(t) #
(16)
which is DogApprox:getLowerBBee www.geeeweeoodwwwtteeeeeeeeeeeee (lam). The X-s are mixed using DDRM from Mineiro [2022] Thm. 4), implemented via the DDRM class and the getDDRMcSLLowerBonnd method in the reference implementation. getDDRNcSLowerBound provably correctly early terminates the infinite sum by leveraging
implemented in the reference
implementation
as
log (1+A(Y.-A0)) - & S
A
Σv, ESt
tY
as seen in the termination criterion of the inner method logweal th (mu).
To minimize computational overhead, can lower bound log( + b) for b > 0 using strong concavity
qua Mineiro (2022] Thm. 3), resulting in the following geometrically spaced collection sufficient statistics:
k1 = & 2 2n (1 k) k))
along with distinct statistics for discretization (tighter lower bound vs. more space overhead): we use k 1/4 exclusively in our
hyperparameter controlling the granularity of the
17

---

Note the coverage guarantee is preserved for any choice of l since we are lower bounding the wealth.
experiments.
Given these statistics, the wealth can be lower bounded given any bet À and any in-hindsight prediction Y via
f(z) log (1 [1+ (=-x(=1;))
f(2) 3 af(z1) + (1 oz) + a(1 a)m(zz),
2
a Zu
Zu
21
2
kzd
m(²) k2p X
Thus when accumulating the statisties, for each Y, W.1x,ze- value of a must be accumulated at key (=:). a value of (1 a:) accumulated at key f(zu), and a value of ax11 - a) accumulated at key m(x)). The LogApprox: update method from the reference implementation implements this.
Because these sufficient statistics are data linear, further computational trick to accumulate the suf- ficient statistics with equality only, i.e., for Y, W. Welx,=vi and when the CDF curve is desired, com- bine these point statistics into cumulative statistics. In this manner only O(1) incremental work done per datapoint; while additional O(t (tg(t)) work is done to accumulate all the sufficient statistics only when the bounds need be computed. The method Str ierremigDDDRM : Frozen: :__init. from the reference implementation contains this logic.
E.1.2 Empirical Bernstein Variant
For simplicity we describe the lower bound A, only. The upper bound derived analogously via the equality Y, = W, (W, - Y,) and a lower bound on (W, Y.): see Waudby-Smith et al. (002 Remark 3] for more details.
This is the empirical Bernstein NSM from Howard et al. 2021 combined with the L bound of Orabona 2019) $4.2.3). Relative DDRM is faster compute, has concise sufficient statistic, and is easier to analyze; but it is wider empirically, and theoretically requires finite importance weight variance to converge.
For fixed v, let Y, = W,lx,a0 be a non-negative real-valued discrete-time random process, let Y, E [0, 1] be a predictable sequence, and let À E [0, 1) be fixed scalar bet. Then
E,(A) = exp (x (>
E.- 1Y.1
Σ log (1 a (Y. (Y%-8.)) #5
is a test supermartingale [Minciro 2022 $3). Manipulating,
Fa(A) exp X
Σ Y, E. [8,]
- Σ
\ Y, - 8.) - log (1 + x Y, Y
=A(A(X)-8.))
exp
Σ Y. E.-1 [Y6]
- -h(- Σ
Y. \Y)=
Fan
Lemma 4.1]
25t
exp
Σ Yg -E-1 [Y6]
- -( Reg(t)
Σ (Y, y:m)² 155
(t).
exp (AS: h(->)V:).
where S. = E.s,
and for (f) we use no-regret learner on squared loss on feasible set [0, 1] with regret Reg(t) to any constant in-hindsight prediction Ý,* [0, 1]. Since Y, is unbounded
[Y,] Y
18

---

above, the loss is not Lipschitz and we can't get fast rates for squared loss, but we can run Adagrad and get an L* bound,
Reg(t)
2
Σ
9
4v2
E V2,2
(Y,
4v2 Regg()) 1
Σ(Y, 82022
ast
Reg(t) 16 4v2
8+
Σ(,, -
#51
Thus basically our variance process is inflated by an additive square root. We will compete with Y,* = min E, Y,).
A key advantage of the empirical Bernstein over DDRM is the availability of both conjugate (closed- form) mixture over and a closed-form majorized stitched boundary. This yields both computational speedup and analytical tractability.
For conjugate mixture, 2] which yields mixture wealth
the truncated gamma prior from Waudby-Smith al. 2022
Theorem
I(T)- (++v) F (
TTe
MEB
7),
(17)
where :...... is Kummer's confluent hypergeometric function and [(,.)) is the upper incomplete gamma function. For the hyperparameter, use
E.2 Proof of Theorem 3.4
Theorem 3.4. Let UV) and (v) be the upper and lower bounds returned by Algorithm and
Algorithm 2 respectively with e(d) 2d and the confidence sequences Ds and E, of Equation 18 Vt: Pt is E--mooth wrt the uniform distribution on the unit interval then
Vl U.(v) - L.(v)
( + Vo)/t
B₁ +
(7)
(T Vi)tt
log a
Ö(t O(t (Er aG==)-1));;
where qt (D), K(ge) (n (2/g1////og/n///-n)) Ve O (K(())) E W?), B =
E.s(WW (W, 1). and Ō() elides polylog Vi factooss.
Note is fixed for the entire argument below, and & denotes the unknown smoothness parameter time l.
We will argue that the upper confidence radius Uz(v) 'x Lest W.lx has the desired rate. An analogous argument applies to the lower contidence radius. One difference from the non- importance-weighted case is that, to be sub-exponential, the lower bound is constructed from an upper bound on (v) = W.(1 1x, via (v) B, tー Eesc (W, 1) term to the width. (Note, because Vi E,[W, 1] O, this term will concentrate, but we will simply use the realized value here.)
U.(.), which introduces an additional
For the proof we introduce an integer parameter > 2 which controls both the grid spacing (e(d) = 17d) and the allocation of error probabilities to levels (6. = (d()e(()) In the main paper set 17 2.
19

---

At level d we construct r7 confidence sequences on an evenly-spaced grid of values 1/11,21 ./.,...., We divide total error probability a/ at level d among these 17 confidence sequences, so that each individual confidence sequence has error probability a/1)""
For fixed bet À and value p. St defined in Appendix E.1.2 is sub-exponential qua Howard et al. [021]] Definition 1] and therefore from Lemma E. there exists an explicit mixture distribution over inducing (curved) boundary
3t 3 1: S: 3 max
C((T)
VEiT, mpd mpa )))
2
I
122d
(r + Vilst
T + Vi
1 11
VeiTo 1p2d
2
log
12(++()))11
2T
C(T)
(
T+ Ve
+ 1p C(T)
+ t
log
(18)
2
where S, = cDF - +- - W.lx and is a hyperparameter be determined further below.
Because the values at level d are 1/1d apart, the worst-case discretization error in the estimated average CDF value is
CDF CDF(((())((()>>)) (v) & 1/((an"),
and the total worst-case confidence radius including discretization error is
ra(t) ELT + max (C(T),
a )) " Vi: T, (2d
Now evaluate at d such that vol < Ein & my th where the t(( V1)/8)
C(T) u (ViiT, 1,25
a (
ra(t)= & V
+ max
(T + Vi)/t
+ +
( Vi)/t log (5r (G=2)-1) + Ö(t llog 1));
t
t
where Ō() clides polylog Ve factors. The final result is not very sensitive the choice of T, and use 7 in practice.
Lemma E.1. Suppose
exp (AS, - (ee())
the (A) -X -- 1--A--lghh log(1 - A);
is sub-iha qual Howard et al. (2021 Definition I]; then there exists an explicit mixture distribution over X with hyperparameter such that
]1 1: S
max (C(T) ( (V.o.oV)))))
a> P
( Vi)st
V1 V1
T+
(1ta-))
u u(ViT,
= -1
log
2T
C(r)
r V
( ((7) ))
(1+001))
log
2T
-T
C(r)= = I(T) T(T,T)
is a (curved) uniform crossing boundary.
20

---

Proof. We can form the conjugate mixture using truncated gamma prior from Howard et al. [2021 Proposition 9I. in the form from Waudby-Smine -mithhh et al. 2022 Theorem 21, which our Equation (7].
TTe=
M ((7)-
++
where (F((..) . is Kummer's 's confluent hypergeometric function. Using Olver et al. 20100 identity 13.6.5).
a1, + 1,x) e²ar (T(a) - -((,
where [( .²) is the (unregularized) upper incomplete gamma function. From Pinelis 2020 1.2] we have
Theorem
I(a, x) < x=E² x
T a
F 1, > E" oz TT(a)
a
I
Applying this to the mixture yields
V/+ + [ + Vi) C(T)
C(r)ertVi+ss,
MER EB
S
C(T)
(T + S,)T+K. I (T + Vi) - 1,
(f)
where (f) follows from the self imposed constraint S. 2 C(T)). This yields crossing boundary
C( (T+ Vz + S.)
( Vi) -1
e7
(T + Vz)
(T+V)) 1.)tt di(T,a),
C(T)
T+V
[ Vi)
[ Vi)
1
r+V.
(r 1o) न|.
++Ve
@e(T,a)=iv 21
1
S. TtV
[ Vi)
S = (T Vi) (-1 1-1-W116
W- (-1
Chatzigeorgiou 2013
Theorem 1] states
2
W w- E -1 V2u +
U,
2
-1 W W-1--e E V2u +
U,
Substituting yields
(T + Vi) (-1- W-1 (-11--11-271) -) & (T Vi) (V (2210g
(tt
log (2)
(19)
(ll
From Feller 1958,
Equation (9.8)] we have
n
r(1+ n)) v 22n
e 12nn+1 glon
el
( + Vi) v1)
Tiv
T Ve
+((+
E
2m
12(++
12(++1)
Therefore
21 (r+ Vi) v 2log (e))
< (T (1)) 2log
( + V,
B (T, FiVE
2T
T Vi (
- 2 (T Vo)
n pe(Tra))
(20)
2x
21

---

and
24 (T+ Vo) log
(r
Vi) log
Vi
a(++(()
12 V2) 12) 161161 12) (T((T ()) TT
2x
T Vi
log
(21)
2
Combining Equations
19
to
21
yields the crossing boundary
Se
(T + vo)/t
T V
1 a- C(T)
2
log
2T
1
T V
+ a (1 C(T)
+ log
(1
t
2m
Simulations
F.1 i.i.d. setting
For non-importance-weigheee simulations, we use the Beta-Binomial boundary of Howard et al. 2021 for A, and E.. The curved boundary is induced by the test NSM
(2:) the 1-p 0(1-6))
Sh dBeta (p; bqc. b(1 9))
1--
W,(b; de, qr)
S dBeta (p: bqc. b(1 4:))
Beta( 1, 1, + 1he, b(1 9t) + 1(1 (c))
(1 qt [(1 ((1-4))) 4.)gg.
Beta 1, by: b(1 4t)
with prior parameter csnsquantile.ippnn
1. Further documentation and details are in the reference implementation
The importannce-eiighee simulations the constructions from Appendix E the reference implemen- tation is in csnsopquantile ipynb for the DDRM variant and wwwpoppuunnnnteaeeeoeoeeee ipynb for the empirical Bernstein variant.
22

---

1.0
10000
0.7
2.8
0.06
5.6
Beteis, 3)
0.04
24
0.03
02
ReENS, BRONS, D6300)
001
8.0
50283
DAY
0.2
0.5 25 23
0. 03
20 Figure 8: Comparison naive time-uniform DKW (which is only valid in the i.i.d. setting) for Beta distributions of varying smoothness. De- creasing smoothness degrades our bound.
30
20 25
Figure CDF bounds approaching true CDF
when sampling i.i.d. from Beta(6,3) distribution. Note these bounds are simultancously valid for all times and values.
L-d LogMermals,
10000
Log Normak20.
Time unitium ho!
Laghermell
2.8
0.00
1-15
120
0.02
8.9
00 25
15
25.0
0.00
12
12"
10" 30"
sol
Figure 9: CDF bounds approaching the true CDF when sampling i.i.d. from lognormal(O, 1) dis- tribution. Recall these bounds are simultaneously valid for all times and values.
Figure Demonstration the variant described in Section 3.3 and Appendix [D. for distributions with arbitrary support, based on i.i.d. sampling from variety of lognormal distributions, Loga- rithmic range dependence is evident.
1.0
1-4 Caumdaniz
8.5
0.05
Time vellien DEW
2.6
0.03
Gaussiant0.
0.03
02
1300
13000
0.00
12"
100 107 10" 10
Figure 10: CDF bounds approaching the true CDF when sampling i.i.d. from a Gaussian(O, 1) distri- bution. Recall these bounds are simultaneously valid for all times and values.
Figure 11: Demonstration of the variant described in Section 3.3 and Appendix D.I for distributions with arbitrary support, based on i.i.d. sampling from variety of Gaussian distributions. Loga- rithmic range dependence is evident.
Continuuus Polya Um. 2-10
2.6
bounees af 1365, A. true CDR
bourds dit Syrik
l0f
Figure Nonstationary Polya simulation for two seeds approaching different average conditional CDFs. Bounds successfully track the true CDFs in both cases. See Section 4.2
Maximum bound width, scaled by //og((t) to remove the primary trend, as func- tion of for nonstationary Polya simulations with different 7/ schedules. See Section 4.2
Figure 12:
23

---

1.0
9.8
9.8
4.6
0.66
led. Betate, P
114.X- Bctale, 3. EXpiL)
2.4
8.
0.2
033 04 0.5
55
03
02
0.3 046 0.5 55 0.5 00
Figure 13: CDF bounds approaching the true
Figure CDF bounds" approaching the true
counterfactual CDF when sampling i.i.d. from Beta(6,3) with finite-variance importance weights, using DDRM for the oracle confidence sequence.
counterfactual CDF when sampling i.i.d. from Beta(6,3) with infinite-variance importance weights, using DDRM for the oracle confidence sequence.
2.6
U.4.x
10
221
Figure 14: CDF bounds approaching the true counterfactual CDF when sampling i.i.d. from a Beta(6.3) with finite-variance importance weights, using Empirical Bernstein for the oracle confi- dence sequence.
Figure 15: CDF bounds approaching the true counterfactual CDF when sampling i.i.d. from Beta(6,3) with infinite-variance importance weights, using Empirical Bernstein for the oracle confidence sequence. Despite apparent conver- gence, eventually this simulation would reset the Empirical Bernstein oracle confidence sequence to trivial bounds.
24


Reviews:
[{"review_id": "w0fMHBcE9O", "reviewer": "Reviewer_hk3u", "summary": "The paper presents the time and value uniform bounds on the CDF of the running averaged conditional distribution of a real valued random variable. The new bounds do not require iid setting and always achieve non-asymptotic coverage. The converge speed depends on the smoothness of distribution against the reference distribution, which it is the uniform distribution. Following Howard et al (2021), a confidence sequence of a discrete time random process was employed, and a time uniform coverage property was a key to construct the uniform bounds.\nAuthors established the bounds for unit interval random variables, extended to real random variables then extended to importance weighted random variables. Algorithms for lower/upper bounds and theoretical properties are presented and simulation studies are provided. \n", "questions": "Please see the weakness section. ", "limitations": "Authors addressed the limitation of the new bounds. ", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Reliable bounds on the CDF for dependent data setting is valuable as iid setting does not always hold. In order to deal with dependent data, the smoothness of distribution to a reference measure is assumed and the time-value uniform bounds are presented. It is examined numerically for both iid samples and nonstationary data.", "weaknesses": "This is not my research area and, I found the paper was hard to read and follow. I have an impression that this paper is written assuming that readers have some knowledge and, detailed explanation would be helpful.\n\n\ni) Confidence sequences Lambda and Xi have very important roles but I can’t grab what they are from the Algorithms 1 and 2 and the justification. Although the confidence sequence review is given in Appendix A, it is not straight forward to make connections to Alg 1 and the rest of paper.\n\nii) Consequently, it was difficult to follow proofs without fully understanding the confidence sequences and their theoretical properties. Where are the Eqn 12 from? Could authors derive this from the assumptions and properties of the confidence sequence? \n\niii) Authors did extensive simulation studies with iid samples although the highlight of result is dropping iid assumption. \n\niv) Some abbreviations were not defined. For example, NSM, DKW and DDRM.\n\nv) Careful edit seems to be needed. For example, there are Eqn (10)s, S_t is not defined in Appendix A. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> This is not my research area and, I found the paper was hard to read and follow.\n\nThanks for the honest feedback.  We are trying to promote confidence sequences within the machine learning community (they are better known within the statistics literature) and it is challenging to properly calibrate the exposition, but we feel the effort is worthwhile.\n\n> i) Confidence sequences Lambda and Xi have very important roles but I can’t grab what they are from the Algorithms 1 and 2 and the justification. Although the confidence sequence review is given in Appendix A, it is not straight forward to make connections to Alg 1 and the rest of paper.\n\nWe will expand Appendix A to better introduce confidence sequences. We will state the definition of a fixed-sample confidence interval and then make the extension to a confidence sequence as a sequence of confidence intervals satisfying a coverage guarantee which holds uniformly over time. We hope this will make the paper more self-contained.\n\n> iv) Some abbreviations were not defined. For example, NSM, DKW and DDRM.\n\nThanks for pointing this out.\n* We'll drop the usage of the acronym NSM entirely and use \"construction\" instead (NSM is a term of art from the stats community which is not helpful here.)\n* DKW is defined on line 55.\n* DDRM is itself the name of a technique; when first mentioned in the text a reference is provided, but the potential first encounter for the reader is in the caption of a figure 5, so we'll put a reference on that usage.\n\n> v) Careful edit seems to be needed. For example, there are Eqn (10)s, S_t is not defined in Appendix A.\n\nThanks for pointing that out, when we moved some material to the appendix we lost some definitions, which we will restore.\n"}, {"review_id": "E3hMGOxWoW", "reviewer": "Reviewer_gT4m", "summary": "This paper proposes a new construction of time-uniform confidence bands for CDF, where the standard toolkit such as Glivenko—Cantelli cannot be applied due to nonstationarity.\nAt a high level, the proposed method combines confidence sequence for a certain subset of values via a union bound.\nDespite the impossibility result from the adversarial online learning scenario, the proposed construction of confidence bands is shown to have vanishing width for a class of smooth distributions (Theorem 3.3).\nThis result holds for unbounded random variables (Section 3.3) as well as under a known distribution shift case (Section 3.4).\nThe simulations demonstrate that the proposed algorithms can be effective.\n", "questions": "Most of my questions are around Algorithm 1, which seems to contain the key idea of the proposed method. The authors should revise the manuscript so that the key ideas become clear.\n- Is i.i.d.ness is assumed throughout Section 3? It is never explicit except in line 80 before Section 3.4.\n- In Algorithm 1, aren’t the functions $\\epsilon(d)$ and $\\Xi_t$ also “inputs” (or “hyperparameters”) to the algorithm? If so, I think it’d better to put it in the algorithm, not in the caption. Further, I think that making Algorithm 1 illustrative by giving a concrete example of $\\epsilon$ and $\\Xi_t$ may improve readability. Since the paper is extremely notation-heavy, it is not very clear how to parse the algorithm at that abstract level.\n- In Algorithm 1, most of the readers will be confused with $W_{1:t}$, as it hasn’t been defined by then. I can search over the text and find it in Section 3.4 that it means the importance weight, but it only distracts a reader if it’s put in Algorithm 1. \n- In the caption of Figure 1, it is stated that “The algorithm searches over all d to optimize the overall bound via a provably correct early termination criterion”. What do you mean by the “provably correct early termination criterion”? In Algorithm 1, where is this corresponded? And where do you provide a provably correctness?\n\nAs the resulting estimator seems new and interesting, I am inclined to vote for accept, but only provided that the writing is greatly improved in the revision. \n", "limitations": "Limitations are not discussed. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The considered problem of constructing confidence bands for CDFs under nonstationarity is of great practical importance.\nThe proposed technique seems to be new and interesting. The theoretical guarantee in Theorem 3.3 is insightful as it characterizes the adaptivity.\n", "weaknesses": "- While I believe that the proposed method is new and novel, the writing is hard to follow, which can be much improved.\n- The paper is not very self-contained. For example, Table 1 needs to be elaborated further. For example, there is no description on “$w_{\\max}$-free” in the main text or in the caption.\n- The figures can be revised further. Legends and labels are too small and not very visible. And it might be better to put Figures 2-5 after Section 4 as these are never referred before the experimental section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper is not very self-contained. For example, Table 1 needs to be elaborated further. For example, there is no description on &ldquo;$w_{\\max}$-free&rdquo; in the main text or in the caption.\n\nWe will expand section 5 to explicitly define the six properties we identify in the columns of Table 1, including what \"unbounded importance weights\" refers to.\n\n> The figures can be revised further. Legends and labels are too small and not very visible.\n\nThanks for pointing this out.  We will increase the sizes of all fonts.\n\n> Is i.i.d.ness is assumed throughout Section 3? It is never explicit except in line 80 before Section 3.4.\n\nThe goal of our paper is to dispense with the i.i.d. assumption, so we do not assume it for any of our results. We will be more explicit about this in the introduction. The goal of line 80 was only to point out that a previous proof method used in the i.i.d. setting appears to break down, which is why we use a different technique.\n\n> If so, I think it’d better to put it in the algorithm, not in the caption.\n\nGood suggestion, we'll make this change.\n\n> In Algorithm 1, most of the readers will be confused with, as it hasn’t been defined by then.\n\nWe will remove it.\n\n> In the caption of Figure 1, it is stated that “The algorithm searches over all d to optimize the overall bound via a provably correct early termination criterion”. What do you mean by the “provably correct early termination criterion”? In Algorithm 1, where is this corresponded? And where do you provide a provably correctness?\n\nThanks for pointing this out.  We will include an explicit proof.  The proof sketch is as follows: once the termination criterion is met, any subsequent (deeper in the tree) bounds are evaluated on the same statistics but with a worse confidence level, and hence are dominated.\n"}, {"review_id": "TVvnfaitnI", "reviewer": "Reviewer_jBxN", "summary": "The paper considers the problem of estimating the CDF of a sequence of random variables obtained sequentially according to some distributions.\nMany classical results are known for this problem when the random variable sequence is obtained in an i.i.d. manner following a certain distribution, along with its confidence bands.\nOn the other hand, some impossibility results are known for the case where the random variables are dependent on each other, and their confidence bands are not sufficiently known.\nTo address this issue, the paper constructs confidence bands for CDFs with running averaged conditional distributions that are uniform in time and value.\nThe extension to importance-weighted random variables is also discussed.", "questions": "- As noted in Weaknesses, there are few specific descriptions of technical difficulties, and reviewers expect authors to address them.\n", "limitations": "NA", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper shows how to construct confidence bands in the setting where there is dependence in the sequence of random variables obtained, an important problem in practical applications. This result is further extended to the importance-weighted setting, which is frequently encountered in many online decision making problems.\n- Through a number of experimental results, the paper shows that results that are consistent with the theoretical results are obtained.", "weaknesses": "- The contents of the Introduction seem to be insufficient, because it is not clear what kind of problem is being solved just by following line 12 to line 27, and then the explanation of contirbutions is given immediately after that.\nSection 5 (Related Work) seems to be useful for understanding the problem the authors are trying to solve, so it would be desirable to include it earlier. Even after adding it, the explanation of background knowledge still seems insufficient, so it seems desirable to use the remaining pages to provide more explanation in the current Introduction.\n\n- Although the comparison with existing results is clearly stated, the reviewer could not tell from the text what the major technical difficulties of the problems are. Many of the proofs and contributions are included in the appendix, and it would be desirable to have an explanation of what technical difficulties were solved to obtain the main results, even if they are only sketches.\n\nMinor issues and typos:\n- The horizontal line labels in Figures 1 to 7 are too small to see.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The contents of the Introduction seem to be insufficient\n\nGreat point, the current introduction is abstract and a concrete example will be helpful.  We will discuss the scenario of continuous monitoring for software regression detection, which combines the desire to do inference beyond the mean (hence the entire CDF) with a desire to detect changes as rapidly as possible in a nonstationary environment.[[1]](https://arxiv.org/abs/2205.14762)\n\n> Many of the proofs and contributions are included in the appendix, and it would be desirable to have an explanation of what technical difficulties were solved to obtain the main results, even if they are only sketches.\n\nThanks for pointing this out.  We'll provide short sketches of the proofs within the main text.  For example, for the first two theorems:\n* Theorem 3.1 follows from the guarantees of the confidence sequences at each fixed value, the monotonicity of the CDF, and a union bound.\n* Theorem 3.3 follows by noting the bias of the discretization is bounded by the smoothness, and then propagating that through a closed-form confidence boundary.\n\n> The horizontal line labels in Figures 1 to 7 are too small to see.\n\nThanks for pointing this out.  We will increase all font sizes.\n"}, {"review_id": "dQK1kT6I3Y", "reviewer": "Reviewer_gyN9", "summary": "The authors propose a method for constructing time-uniform and value-uniform bounds on the CDF of the averaged historical distribution of a real valued random process. They propose a design principle AVAST (always valid and sometimes trivial), implying that their bounds always have coverage, but may converge to 0 slowly. The authors build upon the work of [Howard and Ramdas 2022], extending those results to non-stationary processes, and allowing for counterfactual estimation.", "questions": "See weaknesses, the instance-adaptivity of Theorem 3.3 is unclear. This work seems polished and well-written aside from this, but this result seems like a critical part of the paper. I am leaving a score of weak reject, but if this point is clarified I would be happy to see this paper accepted.", "limitations": "Line 79: leveraging *the* monotonicity\nline 137: two commas after e.g.\nLine 427: For a fixed \"bet\" $\\lambda$. It is not explained why $\\lambda$ should be treated as a bet.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "1. The authors provide a new algorithm for constructing time and value uniform bounds on the CDF of the averaged historical distribution of a real valued random process in the non-stationary case. The theoretical guarantees are cleanly provided, and the proofs appear to be correct.\n2. The authors extend these results to importance-weighted random variables.\n3. The authors simulate their algorithm on several synthetic examples, showcasing its adaptive performance.", "weaknesses": "The one point that is not clear to me is the instance-adaptivity of Theorem 3.3. Is this a constant bound $\\xi_t$ constant for all $t$, i.e. $\\xi_t \\le \\xi$ for all $t$? If not, how is it that the bound is time-uniform while having no dependence on previous $\\xi_t$? It seems as though if $X_1,\\dots,X_{100}$ were i.i.d. $U[0,\\epsilon]$, and $X_{101}$ is independent $U[0,1]$, then the confidence interval width $U_{101}(\\epsilon/2)-L_{101}(\\epsilon/2)$ would depend critically on $\\epsilon$. Simulations would also be helpful to clarify this point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The one point that is not clear to me is the instance-adaptivity of Theorem 3.3.\n\nThanks for pointing this out, we'll add more commentary, since this is an important and desirable property of the technique which should be highlighted.\n\nThe width guarantee is dependent upon the smoothness of the averaged historical distribution up to time t, which can vary with t (as the technique adapts to the [unknown] smoothness at each timestep).  In particular the distributions can become polynomial (in t) less smooth over time and we still enjoy a 1/sqrt(t) shrinking width up to log(t) factors.  It is only when distributions are exponentially less smooth with time that our width becomes constant, which (not coincidentally) is what the impossibility construction of Block et. al. does.\n\n> For a fixed \"bet\" $\\lambda$. It is not explained why $\\lambda$ should be treated as a bet.\n\nThanks for pointing this out.  When we moved material from the main text to the appendix, we lost the definition of $S_t$ (as another reviewer pointed out).  Defining that will clarify.  Furthermore the word \"bet\" is a term of art from the confidence sequence literature which is not helpful here, so we'll switch to using the word \"parameter\".\n"}]

Author rebuttal:
We thank for reviewers for helping to improve the paper.

To improve the intelligibility of Algorithm 1, we propose adding the attached figure. Further, in the appendix, we will manually describe the execution of Algorithm 1 step-by-step until termination on a simple dataset of five items.

Meta-review: This paper is a a non-trivial extension of the Howard and Ramdas 2022 paper, to time-varying processes. This is a useful extension from the applicability perspective, and the proof techniques differ in a few important ways in order to handle non-stationarity. The most critical feedback from reviewers is on presentation. While the material may be accessible to those who have a background in the relevant literature, the authors are advised to take more care in explaining their notation, particularly by elaborating the time-averaged nature of the quantities and by making sure each concept used is defined ahead of time. The authors are also advised to provide brief proof sketches that highlight the methodology employed, to give a roadmap to the detailed proofs in the supplemental material. Please also elaborate the introduction as far as the relationship with other works goes, e.g., by making the comparisons and contrasts of Table 1 more explicit in the text and including the differences in tools used to achieve the results. The technical contributions of this work do warrant being shared with the community, however it is critical that all the clarity concerns of the reviewers and their other comments are taken into account.
Decision: Accept (poster)