mlsanityData to 7 Oct 2026

Approximate Ranking from Pairwise Comparisons

arXiv 1801.01253 ↗First posted 4 Jan 2018cs.LG cs.AI cs.ITcited by 21

Not on the map. Why?

Abstract (arXiv)

A common problem in machine learning is to rank a set of n items based on pairwise comparisons. Here ranking refers to partitioning the items into sets of pre-specified sizes according to their scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defined as the probability that it beats a randomly chosen other item. Finding an exact ranking typically requires a prohibitively large number of comparisons, but in practice, approximate rankings are often adequate. Accordingly, we study the problem of finding approximate rankings from pairwise comparisons. We analyze an active ranking algorithm that counts the number of comparisons won, and decides whether to stop or which pair of items to compare next, based on confidence intervals computed from the data collected in previous steps. We show that this algorithm succeeds in recovering approximate rankings using a number of comparisons that is close to optimal up to logarithmic factors. We also present numerical results, showing that in practice, approximation can drastically reduce the number of comparisons required to estimate a ranking.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Jan 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 6; 2025: 7; 2026: 3.

21 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 244
  2. 2023Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHFcited by 125
  3. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  4. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  5. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  6. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  7. 2024Learning-Augmented Priority Queuescited by 7
  8. 2024Active Preference Learning for Ordering Items In- and Out-of-samplecited by 6
  9. 2022Neural Improvement Heuristics for Graph Combinatorial Optimization Problemscited by 4
  10. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  11. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  12. 2025PITA: Preference-Guided Inference-Time Alignment for LLM Post-Trainingcited by 2
9 more
  1. 2025Efficient Bayesian Inference from Noisy Pairwise Comparisonscited by 2
  2. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  3. 2026What Does Preference Learning Recover from Pairwise Comparison Data?cited by 2
  4. 2024Efficient Pointwise-Pairwise Learning-to-Rank for News Recommendationcited by 1
  5. 2025Interestingness First Classifierscited by 1
  6. 2025Top-k Feature Importance Rankingcited by 0
  7. 2025Ranking Items from Discrete Ratings: The Cost of Unknown User Thresholdscited by 0
  8. 2026Bradley-Terry Rankings for Recommender Systems Across Dataset Taxonomiescited by 0
  9. 2026Cost-Aware Best-LLM Identification using Dueling Feedbackcited by 0