# Optimal Top-k Identification from Pairwise Comparisons

arXiv: https://arxiv.org/abs/2607.08979 · HTML: https://mlsanity.com/paper/2607.08979/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 9 Jul 2026.

## Builds on (most cited first, 22 of 22)

- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [PAC Battling Bandits in the Plackett-Luce Model](https://mlsanity.com/paper/1808.04008/) (2018)
- [Minimax-optimal Inference from Partial Rankings](https://mlsanity.com/paper/1406.5638/) (2014)
- [PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds](https://mlsanity.com/paper/1806.02970/) (2018)
- [A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model](https://mlsanity.com/paper/1707.08238/) (2017)
- [Data-driven Rank Breaking for Efficient Rank Aggregation](https://mlsanity.com/paper/1601.05495/) (2016)
- [Top-K Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal](https://mlsanity.com/paper/1603.04153/) (2016)
- [Crowdsourcing subjective annotations using pairwise comparisons reduces bias and error compared to the majority-vote method](https://mlsanity.com/paper/2305.20042/) (2023)
- [From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model](https://mlsanity.com/paper/1903.00558/) (2019)
- [The Sample Complexity of Best-k Items Selection from Pairwise Comparisons](https://mlsanity.com/paper/2007.03133/) (2020)
- [Sorted Top-k in Rounds](https://mlsanity.com/paper/1906.05208/) (2019)
- [Dueling Bandits with Qualitative Feedback](https://mlsanity.com/paper/1809.05274/) (2018)

## Abstract (arXiv)

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 δ. The objective is to design such a δ-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 δ → 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.