提出新算法与下界，解决单合格臂识别的样本复杂度问题
Closing the Gap on the Sample Complexity of 1-Identification
- 基于优化建模推导新下界，更精准刻画最少需抽多少次
- 新算法在所有情形下达到理论最优，误差不超过对数因子
- 适合研究强化学习探索效率或需高置信度判断的场景
1-识别问题是多臂赌博机中的基础纯探索问题。智能体需判断是否存在某臂的期望奖励超过已知阈值μ₀，若无则输出 extsf{None}。要求以至少1−δ的概率保证正确性，同时最小化期望抽取次数𝔼[τ]。本文研究该问题，做出两项主要贡献：首先，对于至少存在一个合格臂的情形，通过新颖的优化公式推导出𝔼[τ]的新下界；其次，提出一种新算法，并建立上界，该上界在所有实例中均与下界匹配，仅差多项式对数因子。本结果补充了多个合格臂情形下𝔼[τ]分析的空白，是文献中的开放问题。
原文摘要 · Abstract (English)
The 1-identification problem is a fundamental pure-exploration problem in multi-armed bandits. An agent aims to determine whether there exists an arm whose mean reward exceeds a known threshold $μ_0$, or to output \textsf{None} otherwise. The agent must guarantee correctness with probability at least $1-δ$, while minimizing the expected number of arm pulls $\mathbb{E}[τ]$. We study the 1-identification problem and make two main contributions. First, for instances with at least one qualified arm, we derive a new lower bound on $\mathbb{E}[τ]$ via a novel optimization formulation. Second, we propose a new algorithm and establish upper bounds that match the lower bounds up to polynomial logarithmic factors uniformly over all instances. Our result complements the analysis of $\mathbb{E}τ$ when there are multiple qualified arms, which is an open problem in the literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。