提出可随时停止的最优算法，高效识别最佳选项
Rate-optimal Design for Anytime Best Arm Identification
- 基于可证明最优的框架设计新算法，支持任意时刻停止
- 在常见风险度量下达到理论最优性能，实验优于现有方法
- 无需提前知道总预算，适合实际应用中的动态场景
我们研究最佳臂识别问题，目标是在有限采样预算下从K个臂中找出均值最高的臂，该问题广泛应用于A/B测试等场景。本文提出一类算法框架，其在最坏情况下的表现可证明接近最优（仅差常数因子），并推广了以往固定预算方法对特定风险度量的局限性。基于此框架，我们提出Almost Tracking算法，该算法具有针对流行风险度量H₁的可证明保证。与现有方法不同，该算法无需预先设定总采样预算，也无需舍弃大量样本，具备显著实用性。在合成数据和真实数据集上的实验表明，该算法在性能上优于现有的任意时间算法以及固定预算算法。
原文摘要 · Abstract (English)
We consider the best arm identification problem, where the goal is to identify the arm with the highest mean reward from a set of $K$ arms under a limited sampling budget. This problem models many practical scenarios such as A/B testing. We consider a class of algorithms for this problem, which is provably minimax optimal up to a constant factor. This idea is a generalization of existing works in fixed-budget best arm identification, which are limited to a particular choice of risk measures. Based on the framework, we propose Almost Tracking, a closed-form algorithm that has a provable guarantee on the popular risk measure $H_1$. Unlike existing algorithms, Almost Tracking does not require the total budget in advance nor does it need to discard a significant part of samples, which gives a practical advantage. Through experiments on synthetic and real-world datasets, we show that our algorithm outperforms existing anytime algorithms as well as fixed-budget algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。