提出新算法，逼近1-识别问题最优样本复杂度。
Near Optimal Non-asymptotic Sample Complexity of 1-Identification
- 设计序列探索-利用算法SEE，从非渐近角度分析。
- 上下界差距仅差多项式对数因子，接近最优。
- 适合关注纯探索问题的强化学习研究者。
针对现有文献中未解决的开放问题，本文研究1-识别问题——一种基础的纯探索多臂赌博机模型。目标是判断是否存在某个动作的期望回报不低于已知阈值μ₀，若不存在则输出None，且要求输出正确的概率至少为1−δ。Degenne & Koolen（2019）已给出该问题的渐近最优样本复杂度，但其非渐近分析仍不清晰。本文提出新的算法Sequential-Exploration-Exploitation（SEE），并从非渐近视角进行理论分析。首次在文献中实现近似最优性：上界与下界仅相差多项式对数因子。数值实验表明，该算法优于现有基准方法。
原文摘要 · Abstract (English)
Motivated by an open direction in existing literature, we study the 1-identification problem, a fundamental multi-armed bandit formulation on pure exploration. The goal is to determine whether there exists an arm whose mean reward is at least a known threshold $μ_0$, or to output None if it believes such an arm does not exist. The agent needs to guarantee its output is correct with probability at least $1-δ$. Degenne & Koolen 2019 has established the asymptotically tight sample complexity for the 1-identification problem, but they commented that the non-asymptotic analysis remains unclear. We design a new algorithm Sequential-Exploration-Exploitation (SEE), and conduct theoretical analysis from the non-asymptotic perspective. Novel to the literature, we achieve near optimality, in the sense of matching upper and lower bounds on the pulling complexity. The gap between the upper and lower bounds is up to a polynomial logarithmic factor. The numerical result also indicates the effectiveness of our algorithm, compared to existing benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。