Knowledge Gradient Procedure to Select the Best System Under Pairwise Comparisons
本文针对只能通过成对比较评估备选方案性能的固定预算排名与选择问题，将知识梯度方法扩展到自适应分配采样预算，以识别最优或前k个设计，并推导了渐近最优分配比例。
ABSTRACT This article considers fixed‐budget ranking and selection (R&S) problems where the performance of alternative designs can only be assessed through pairwise comparisons, a setting encountered in many applications, including player ranking in games, sports tournaments, recommender systems, image‐based search, public choice models such as voting schemes or decision rules in committees, and market research. Assuming Gaussian sampling noise, we successfully extend the knowledge gradient (KG) procedure to adaptively allocate the sampling budget for identifying the best design or the top‐ designs. The proposed algorithms inherit several attractive features of KG such as enabling exact computation and achieving asymptotic mean‐variance trade‐offs. Additionally, we investigate the asymptotically optimal sampling budget allocation ratio for the pairwise R&S problem within a large deviations framework. The derived balance conditions for the optimal ratio resemble those of traditional R&S but include specific features pertinent to pairwise comparisons. Lastly, we perform extensive numerical experiments to demonstrate that the proposed algorithms deliver competitive and robust finite‐budget performance compared with several other state‐of‐the‐art procedures.