提出可保证指数尾部停止时间的最优臂识别算法,提升决策效率与可靠性。
Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification
- 基于序列减半与加倍技巧设计新算法,确保停止时间分布更优。
- 证明部分现有算法存在永不停止的风险,暴露其理论缺陷。
- 适用于需高置信度快速决策的场景,如医疗试验、推荐系统优化。
最优臂识别问题旨在以最少实验次数(即臂抽取次数)确定最佳选项,对成本高效和及时决策至关重要。在固定置信度设置下,算法需依赖数据自适应停止,并保证返回结果的正确性。由于停止时间是随机的,我们期望其分布具有轻尾特性。然而,许多现有研究仅关注停止时间的高概率或期望值界,允许重尾分布,甚至可能导致永不停止。本文首次证明,某些流行算法确实存在永不停止的情况。为此,我们提出了两类能保证指数尾部停止时间的算法:第一类基于固定预算算法序列减半结合加倍技巧;第二类为元算法,可将任意具有高概率停止保证的固定置信度算法转化为具备指数尾部停止时间的版本。结果表明,当前主流固定置信度算法仍有显著改进空间。
原文摘要 · Abstract (English)
The best arm identification problem requires identifying the best alternative (i.e., arm) in active experimentation using the smallest number of experiments (i.e., arm pulls), which is crucial for cost-efficient and timely decision-making processes. In the fixed confidence setting, an algorithm must stop data-dependently and return the estimated best arm with a correctness guarantee. Since this stopping time is random, we desire its distribution to have light tails. Unfortunately, many existing studies focus on high probability or in expectation bounds on the stopping time, which allow heavy tails and, for high probability bounds, even not stopping at all. We first prove that this never-stopping event can indeed happen for some popular algorithms. Motivated by this, we propose algorithms that provably enjoy an exponential-tailed stopping time, which improves upon the polynomial tail bound reported by Kalyanakrishnan et al. (2012). The first algorithm is based on a fixed budget algorithm called Sequential Halving along with a doubling trick. The second algorithm is a meta algorithm that takes in any fixed confidence algorithm with a high probability stopping guarantee and turns it into one that enjoys an exponential-tailed stopping time. Our results imply that there is much more to be desired for contemporary fixed confidence algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。