Sequential estimation of quantiles with applications to A/B testing and best-arm identification

By Steven R. Howard, Aaditya Ramdas. Bernoulli, 2019

73 citations recorded by the source corpus.

Consider the problem of sequentially estimating quantiles of any distribution over a complete, fully-ordered set, based on a stream of i.i.d. observations. We propose new, theoretically sound and practically tight confidence sequences for quantiles, that is, sequences of confidence intervals which are valid uniformly over time. We give two methods for tracking a fixed quantile and two methods for tracking all quantiles simultaneously. Specifically, we provide explicit expressions with small constants for intervals whose widths shrink at the fastest possible $\sqrt{t^{-1} \log\log t}$ rate, as determined by the law of the iterated logarithm (LIL). As a byproduct, we give a non-asymptotic concentration inequality for the empirical distribution function which holds uniformly over time with the LIL rate, thus strengthening Smirnov's asymptotic empirical process LIL, and extending the famed Dvoretzky-Kiefer-Wolfowitz (DKW) inequality to hold uniformly over all sample sizes while only being about twice as wide in practice. This inequality directly yields sequential analogues of the one- and two-sample Kolmogorov-Smirnov tests, and a test of stochastic dominance. We apply our results to the problem of selecting an arm with an approximately best quantile in a multi-armed bandit framework, proving a state-of-the-art sample complexity bound for a novel allocation strategy. Simulations demonstrate that our method stops with fewer samples than existing methods by a factor of five to fifty. Finally, we show how to compute confidence sequences for the difference between quantiles of two arms in an A/B test, along with corresponding always-valid $p$-values.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/baa6a827eb975bb622cf9444a7e224c3d20f9b61

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Time-uniform central limit theory and asymptotic confidence sequences (2021, background): “CSs are an inherently nonasymptotic notion, and thus essentially every published CS is nonasymptotic, including the recent state-of-the-art [19, 17, 65].”