Knowledge Gradient Procedure to Select the Best System Under Pairwise Comparisons

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, the authors 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, they 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, they 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.