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

Abstract

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 $\sqrt{t^{-1}\log \log 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.

35 pages, 8 figures

References in corpus (5)

• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Concentration inequalities for order statistics
• X-Armed Bandits: Optimizing Quantiles, CVaR and Other Risks
• Large-Scale Online Experimentation with Quantile Metrics
• A nonasymptotic law of iterated logarithm for general M-estimators

Cited by in corpus (16)

• Universal Inference
• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Hypothesis testing with e-values
• Martingale Methods for Sequential Estimation of Convex Functionals and Divergences
• Comparing Sequential Forecasters
• Confidence sequences for sampling without replacement
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Uncertainty quantification using martingales for misspecified Gaussian processes
• Estimating the number and effect sizes of non-null hypotheses
• Rapid Regression Detection in Software Deployments through Sequential Testing
• Quantile Bandits for Best Arms Identification
• ALL-IN meta-analysis: breathing life into living systematic reviews and prospective meta-analyses
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism
• CONQ: CONtinuous Quantile Treatment Effects for Large-Scale Online Controlled Experiments
• On the Problem of Best Arm Retention
• Robust Online Convex Optimization in the Presence of Outliers