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

arXiv: https://arxiv.org/abs/1906.09712 · HTML: https://mlsanity.com/paper/1906.09712/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2019.

## Built on by (most cited first, 27 of 27)

- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Time-uniform central limit theory and asymptotic confidence sequences](https://mlsanity.com/paper/2103.06476/) (2021)
- [Martingale Methods for Sequential Estimation of Convex Functionals and Divergences](https://mlsanity.com/paper/2103.09267/) (2021)
- [How Generalizable Is My Behavior Cloning Policy? A Statistical Approach to Trustworthy Performance Evaluation](https://mlsanity.com/paper/2405.05439/) (2024)
- [Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations](https://mlsanity.com/paper/2212.14411/) (2022)
- [An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits](https://mlsanity.com/paper/2311.05794/) (2023)
- [Comparing Sequential Forecasters](https://mlsanity.com/paper/2110.00115/) (2021)
- [Huber-Robust Confidence Sequences](https://mlsanity.com/paper/2301.09573/) (2023)
- [Taming False Positives in Out-of-Distribution Detection with Human Feedback](https://mlsanity.com/paper/2404.16954/) (2024)
- [Risk-limiting Financial Audits via Weighted Sampling without Replacement](https://mlsanity.com/paper/2305.06884/) (2023)
- [Quantile Learn-Then-Test: Quantile-Based Risk Control for Hyperparameter Optimization](https://mlsanity.com/paper/2407.17358/) (2024)
- [Anytime-Valid Conformal Risk Control](https://mlsanity.com/paper/2602.04364/) (2026)
- [Robust Online Convex Optimization in the Presence of Outliers](https://mlsanity.com/paper/2107.01881/) (2021)
- [Sequential change detection via backward confidence sequences](https://mlsanity.com/paper/2302.02544/) (2023)
- [Distribution-Free Model-Agnostic Regression Calibration via Nonparametric Methods](https://mlsanity.com/paper/2305.12283/) (2023)
- [Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation](https://mlsanity.com/paper/2410.15057/) (2024)
- [Conditionally Risk-Averse Contextual Bandits](https://mlsanity.com/paper/2210.13573/) (2022)
- [Time-uniform confidence bands for the CDF under nonstationarity](https://mlsanity.com/paper/2302.14248/) (2023)
- [Anytime-valid t-tests and confidence sequences for Gaussian means with unknown variance](https://mlsanity.com/paper/2310.03722/) (2023)
- [ASAT: Adaptive Scoring and Thresholding with Human Feedback for Robust Out-of-Distribution Detection](https://mlsanity.com/paper/2505.02299/) (2025)
- [Time-uniform conformal and PAC prediction](https://mlsanity.com/paper/2602.06297/) (2026)
- [Learning to Decide with AI Assistance under Human-Alignment](https://mlsanity.com/paper/2605.12646/) (2026)
- [Sequential inductive prediction intervals](https://mlsanity.com/paper/2312.04950/) (2023)
- [Limits of Approximating the Median Treatment Effect](https://mlsanity.com/paper/2403.10618/) (2024)
- [On the Problem of Best Arm Retention](https://mlsanity.com/paper/2504.11866/) (2025)
- [Online Learning of Optimal Sequential Testing Policies](https://mlsanity.com/paper/2509.03707/) (2025)
- [Bet on Features: Anytime-Valid and Feature-Aware Auditing of Conditional Quantile Forecasters](https://mlsanity.com/paper/2607.11653/) (2026)

## Abstract (arXiv)

We propose confidence sequences -- sequences of confidence intervals which are valid uniformly over time -- for quantiles of any distribution over a complete, fully-ordered set, based on a stream of i.i.d. observations. We give methods both for tracking a fixed quantile and for tracking all quantiles simultaneously. Specifically, we provide explicit expressions with small constants for intervals whose widths shrink at the fastest possible √t-1 loglog t rate, along with a non-asymptotic concentration inequality for the empirical distribution function which holds uniformly over time with the same rate. The latter strengthens Smirnov's empirical process law of the iterated logarithm and extends the Dvoretzky-Kiefer-Wolfowitz inequality to hold uniformly over time. We give a new algorithm and sample complexity bound for selecting an arm with an approximately best quantile in a multi-armed bandit framework. In simulations, our method requires fewer samples than existing methods by a factor of five to fifty.