# Maximum Selection and Ranking under Noisy Comparisons

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2017.

## Built on by (most cited first, 18 of 18)

- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons](https://mlsanity.com/paper/2203.06063/) (2022)
- [Advances in Preference-based Reinforcement Learning: A Review](https://mlsanity.com/paper/2408.11943/) (2024)
- [Bandits with Preference Feedback: A Stackelberg Game Perspective](https://mlsanity.com/paper/2406.16745/) (2024)
- [Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons](https://mlsanity.com/paper/2110.04136/) (2021)
- [Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2505.23673/) (2025)
- [On the Optimal Bounds for Noisy Computing](https://mlsanity.com/paper/2306.11951/) (2023)
- [Noisy Computing of the mathsfOR and mathsfMAX Functions](https://mlsanity.com/paper/2309.03986/) (2023)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)
- [Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problem](https://mlsanity.com/paper/2310.02016/) (2023)
- [Eliciting Kemeny Rankings](https://mlsanity.com/paper/2312.11663/) (2023)
- [Automatic design optimization of preference-based subjective evaluation with online learning in crowdsourcing environment](https://mlsanity.com/paper/2403.06100/) (2024)
- [Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits](https://mlsanity.com/paper/2606.01799/) (2026)
- [Revisiting scaling laws for reward optimization](https://mlsanity.com/paper/2609.38526/) (2026)
- [On the Complexity of Preference-Based Bandits](https://mlsanity.com/paper/2609.39351/) (2026)

## Abstract (arXiv)

We consider (ε,δ)-PAC maximum-selection and ranking for general probabilistic models whose comparisons probabilities satisfy strong stochastic transitivity and stochastic triangle inequality. Modifying the popular knockout tournament, we propose a maximum-selection algorithm that uses Oleft(fracnε2log frac1δright) comparisons, a number tight up to a constant factor. We then derive a general framework that improves the performance of many ranking algorithms, and combine it with merge sort and binary search to obtain a ranking algorithm that uses Oleft(fracnlog n (log log n)3ε2right) comparisons for any δ≥frac1n, a number optimal up to a (log log n)3 factor.