为追踪停止算法提供非渐近性能保证，解决多正确答案场景下的探索效率问题。
Non-Asymptotic Analysis of (Sticky) Track-and-Stop
- 基于动态采样策略，结合跟踪与停止机制优化查询次数
- 首次给出两类算法在有限δ下的严格样本复杂度上界
- 适用于ε-最优臂识别等多解场景，适合高可靠性要求的决策系统
在纯探索问题中，统计学家需通过顺序采样来回答关于未知随机环境的问题，且错误率不得超过给定风险参数δ。优秀的算法应尽可能减少对环境的查询次数。Track-and-Stop算法是解决此类问题的开创性方法，已知其在δ→0时具有渐近最优的样本复杂度，前提是环境到正确答案的映射是单值的（如存在唯一最优臂）。而Sticky Track-and-Stop算法将该结论推广至可能存在多个正确答案的情形（如ε-最优臂识别）。尽管两者在渐近意义上最优，但其非渐近性能仍未明确。本文填补该空白，首次为这两类算法提供了非渐近意义上的样本复杂度保证。
原文摘要 · Abstract (English)
In pure exploration problems, a statistician sequentially collects information to answer a question about some stochastic and unknown environment. The probability of returning a wrong answer should not exceed a maximum risk parameter $δ$ and good algorithms make as few queries to the environment as possible. The Track-and-Stop algorithm is a pioneering method to solve these problems. Specifically, it is well-known that it enjoys asymptotic optimality sample complexity guarantees for $δ\to 0$ whenever the map from the environment to its correct answers is single-valued (e.g., best-arm identification with a unique optimal arm). The Sticky Track-and-Stop algorithm extends these results to settings where, for each environment, there might exist multiple correct answers (e.g., $ε$-optimal arm identification). Although both methods are optimal in the asymptotic regime, their non-asymptotic guarantees remain unknown. In this work, we fill this gap and provide non-asymptotic guarantees for both algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。