# Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

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

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2015.

## Built on by (most cited first, 30 of 61)

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF](https://mlsanity.com/paper/2312.08358/) (2023)
- [ReviewerGPT? An Exploratory Study on Using Large Language Models for Paper Reviewing](https://mlsanity.com/paper/2306.00622/) (2023)
- [Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism](https://mlsanity.com/paper/2305.18438/) (2023)
- [Active Preference Optimization for Sample Efficient RLHF](https://mlsanity.com/paper/2402.10500/) (2024)
- [Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHF](https://mlsanity.com/paper/2401.16335/) (2024)
- [Direct Judgement Preference Optimization](https://mlsanity.com/paper/2409.14664/) (2024)
- [Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences](https://mlsanity.com/paper/2403.01857/) (2024)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [A Tale of HodgeRank and Spectral Method: Target Attack Against Rank Aggregation Is the Fixed Point of Adversarial Game](https://mlsanity.com/paper/2209.05742/) (2022)
- [Poisoning Attack against Estimating from Pairwise Comparisons](https://mlsanity.com/paper/2107.01854/) (2021)
- [Towards User-level Private Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2502.17515/) (2025)
- [Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems](https://mlsanity.com/paper/2307.12975/) (2023)
- [Differentially Private Reward Estimation with Preference Feedback](https://mlsanity.com/paper/2310.19733/) (2023)
- [Spectral Ranking Inferences based on General Multiway Comparisons](https://mlsanity.com/paper/2308.02918/) (2023)
- [Understanding the Performance Gap in Preference Learning: A Dichotomy of RLHF and DPO](https://mlsanity.com/paper/2505.19770/) (2025)
- [ℓ∞-Bounds of the MLE in the BTL Model under General Comparison Graphs](https://mlsanity.com/paper/2110.10825/) (2021)
- [J4R: Learning to Judge with Equivalent Initial State Group Relative Policy Optimization](https://mlsanity.com/paper/2505.13346/) (2025)
- [Learning Rich Rankings](https://mlsanity.com/paper/2312.15081/) (2023)
- [Learning Linear Utility Functions From Pairwise Comparison Queries](https://mlsanity.com/paper/2405.02612/) (2024)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [On Sinkhorn's Algorithm and Choice Modeling](https://mlsanity.com/paper/2310.00260/) (2023)
- [Statistical ranking with dynamic covariates](https://mlsanity.com/paper/2406.16507/) (2024)
- [A Perceptually Optimized and Self-Calibrated Tone Mapping Operator](https://mlsanity.com/paper/2206.09146/) (2022)
- [Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning](https://mlsanity.com/paper/2309.04626/) (2023)
- [Statistical inference for pairwise comparison models](https://mlsanity.com/paper/2401.08463/) (2024)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting](https://mlsanity.com/paper/2402.18697/) (2024)

## Abstract (arXiv)

Data in the form of pairwise comparisons arises in many domains, including preference elicitation, sporting competitions, and peer grading among others. We consider parametric ordinal models for such pairwise comparison data involving a latent vector w^* ∈ ℝd that represents the "qualities" of the d items being compared; this class of models includes the two most widely used parametric models--the Bradley-Terry-Luce (BTL) and the Thurstone models. Working within a standard minimax framework, we provide tight upper and lower bounds on the optimal error in estimating the quality score vector w^* under this class of models. The bounds depend on the topology of the comparison graph induced by the subset of pairs being compared via its Laplacian spectrum. Thus, in settings where the subset of pairs may be chosen, our results provide principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors.