New Algorithm Optimizes Top-k Item Selection from Pairwise Data.

The problem of identifying the top-$k$ items from a larger set, based on noisy pairwise comparisons, is a fundamental challenge in active learning. This scenario often arises in contexts like product ranking, A/B testing, or preference elicitation, where an algorithm sequentially selects pairs of items for comparison and observes the outcomes. The goal is to determine the top-$k$ items with a specified error probability, while minimizing the total number of comparisons, known as sample complexity. While asymptotically optimal procedures exist for various fixed-confidence pure exploration bandit problems, a solution for top-$k$ identification from pairwise comparisons under latent utility models has been elusive. This research fills that gap by developing such an algorithm. The proposed method characterizes the information-theoretic lower bound for this problem, formulating it as a saddle-point optimization. This structure enables a computationally efficient primal-dual procedure that learns the optimal comparison allocation online. The algorithm then adaptively tracks this allocation, proving its asymptotic optimality as the desired error probability approaches zero.