Sequential estimation of quantiles with applications to A/B testing and best-arm identification
Sequential estimation of quantiles with applications to A/B testing and best-arm identification
复制标题
DOI：
10.3150/21-bej1388
复制
发表时间：
2019-06
期刊：
影响因子：
1.5
通讯作者：
Steven R. Howard;Aaditya Ramdas
中科院分区：
文献类型：
--
作者：
Steven R. Howard;Aaditya Ramdas
考虑基于i.i.d.流，在一个完全的、全序的集合上顺序估计任何分布的分位数的问题。意见。我们提出了新的，理论上健全的和实际上紧的分位数，即序列的置信区间是有效的，随着时间的推移一致的置信序列。我们给出了两种方法跟踪一个固定的分位数和两种方法同时跟踪所有的分位数。具体来说，我们提供了显式表达式，其宽度以最快的速度缩小的区间的小常数，由迭代对数定律（LIL）确定。作为一个副产品，我们给出了一个非渐近浓度不等式的经验分布函数，它随着时间的推移与LIL率保持一致，从而加强了Smirnov的渐近经验过程LIL，并扩展了著名的Dvoretzky-Kiefer-Wolfowitz（DKW）不等式，在所有样本大小上保持一致，而在实践中只有大约两倍的宽度。这个不等式直接产生了单样本和双样本Kolmogorov-Smirnov检验的序列类似物，以及随机优势检验。我们将我们的研究结果的问题，选择一个手臂与一个近似最好的分位数在一个多臂的强盗框架，证明了一个国家的最先进的样本复杂性约束的一种新的分配策略。仿真结果表明，我们的方法停止与更少的样本比现有的方法的一个因素的五到五十。最后，我们展示了如何计算A/B检验中两个臂的分位数之间的差异的置信序列，沿着相应的始终有效的$p$值。
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.