mlsanityData to 7 Oct 2026

Maximum Selection and Ranking under Noisy Comparisons

arXiv 1705.05366 ↗First posted 15 May 2017cs.LGcited by 18

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 5; 2024: 5; 2025: 1; 2026: 4.

18 papers.

Sort:

By area:

  1. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  2. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  3. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  4. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  5. 2022Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisonscited by 10
  6. 2024Bandits with Preference Feedback: A Stackelberg Game Perspectivecited by 7
  7. 2024Advances in Preference-based Reinforcement Learning: A Reviewcited by 6
  8. 2021Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisonscited by 3
  9. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  10. 2023On the Optimal Bounds for Noisy Computingcited by 2
  11. 2023Noisy Computing of the mathsfOR and mathsfMAX Functionscited by 1
  12. 2026Active Seriation: Efficient Ordering Recovery with Statistical Guaranteescited by 1
6 more
  1. 2023Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problemcited by 0
  2. 2023Eliciting Kemeny Rankingscited by 0
  3. 2024Automatic design optimization of preference-based subjective evaluation with online learning in crowdsourcing environmentcited by 0
  4. 2026Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Banditscited by 0
  5. 2026Revisiting scaling laws for reward optimizationcited by 0
  6. 2026On the Complexity of Preference-Based Banditscited by 0