提出新方法，更高效识别胜者最优的成对比较问题。
The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits
- 利用完整胜负差距矩阵，不只看胜者与他人对比
- 样本复杂度比现有方法降低，理论保证更优
- 适合关注实际采样效率的研究者或应用者
我们研究在仅假设存在康多塞胜者（即每对比较中胜率不低于1/2的臂）条件下的随机成对强化学习中的最优臂识别问题。提出一种新识别方法，充分利用完整的差距矩阵 Δ_{i,j} = q_{i,j} - 1/2（其中 q_{i,j} 表示臂 i 击败臂 j 的概率），而不仅依赖胜者与其他臂的差距。推导出高概率、实例相关的样本复杂度上界，相比已有最优结果（忽略对数因子）有改进，得益于利用了除胜者相关外的更多有效比较信息。同时给出新的下界，据我们所知，这是首个针对随机成对强化学习中康多塞胜者识别的下界。分析揭示了在差距矩阵中定位并精确估计关键项的内在成本，证明了非渐近上界的最优性。总体结果揭示了渐近分析未捕捉到的新样本复杂度规律与权衡。
原文摘要 · Abstract (English)
We study best-arm identification in stochastic dueling bandits under the sole assumption that a Condorcet winner exists, i.e., an arm that wins each noisy pairwise comparison with probability at least $1/2$. We introduce a new identification procedure that exploits the full gap matrix $Δ_{i,j}=q_{i,j}-\tfrac12$ (where $q_{i,j}$ is the probability that arm $i$ beats arm $j$), rather than only the gaps between the Condorcet winner and the other arms. We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones by leveraging informative comparisons beyond those involving the winner. We complement these results with new lower bounds which, to our knowledge, are the first for Condorcet-winner identification in stochastic dueling bandits. Our lower-bound analysis isolates the intrinsic cost of locating informative entries in the gap matrix and estimating them to the required confidence, establishing the optimality of our non-asymptotic bounds. Overall, our results reveal new regimes and trade-offs in the sample complexity that are not captured by asymptotic analyses based only on the expected budget.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。