Maximum Selection and Ranking under Noisy Comparisons

Abstract

We consider $(\epsilon ,\delta )$-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 $\mathcal{O}\left(\frac{n}{{\epsilon }^2}\log \frac{1}{\delta }\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 $\mathcal{O}\left(\frac{n\log n(\log \log n{)}^3}{{\epsilon }^2}\right)$ comparisons for any $\delta \ge \frac{1}{n}$, a number optimal up to a $(\log \log n{)}^3$ factor.

References in corpus (3)

• Top-$K$ Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal
• Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
• Maximum Selection and Sorting with Adversarial Comparators and an Application to Density Estimation

Cited by in corpus (10)

• Preference-based Online Learning with Dueling Bandits: A Survey
• Human Preferences as Dueling Bandits
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• Advances in Preference-based Reinforcement Learning: A Review
• Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions
• A Bayesian Choice Model for Eliminating Feedback Loops
• Graph Resistance and Learning from Pairwise Comparisons
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations