Optimal Top-$k$ Identification from Pairwise Comparisons

We study the active learning problem of fixed-confidence top-$k$ identification from noisy pairwise comparisons. In this problem, an algorithm sequentially chooses pairs of items to compare, observes the outcomes, and stops when it can return the set of top-$k$ items with error probability at most $\delta$. The objective is to design such a *$\delta$-correct* procedure that minimizes the expected number of comparisons (the sample complexity). This problem falls within the broader literature on fixed-confidence pure exploration in bandit models, where a common target is asymptotic optimality: the algorithm's expected sample complexity matches the information theoretic lower bound as $\delta \to 0$. Asymptotically optimal procedures have been developed for a range of fixed-confidence pure-exploration problems, however to the best of our knowledge, for top-$1$, or more generally top-$k$ identification from pairwise comparisons under latent utility models an asymptotically optimal algorithm has not been established. In this setting, we develop such an algorithm. We characterize the structure of the lower bound and formulate it as a saddle-point problem. This structure enables a computationally efficient primal--dual procedure that learns the asymptotically optimal comparison allocation online. We then construct an adaptive comparison-allocation algorithm that tracks the allocation learned by the primal--dual procedure and prove it is asymptotically optimal.

Many applications use pairwise comparisons to identify the best few items from a large set of candidates. For instance, using human pairwise preferences to identify which LLMs are best at certain tasks. However, human attention costs time and/or money, so we would like to learn as much as possible from each comparison we ask to be conducted. This paper develops an adaptive algorithm for choosing which pair to compare next, using all the information we have learned so far. This allows us to ``hone in'' on the items near the best few, so that with fewer comparisons we can identify with high confidence which items are best. We prove that the algorithm is especially well-suited for high-stakes settings, where a wrong choice is costly.