Active ranking from pairwise comparisons and when parametric assumptions do not help
The paper deals with the problem of finding a partial or complete ranking of a set of \(n\) items based on active pairwise comparisons in a sequential fashion. The outcomes of comparisons are stochastic, i.e. item \(i\) beats item \(j\) with an unknown probability \(M_{ij}\in (0,~1).\) The outcomes of pairwise comparisons are assumed to be stochastically mutually independent, and moreover the probabilities \(M_{ij}\) are separated away from zero and one. The ordering of the items is defined in terms of their (unknown) scores, where the score \(\tau_i\) of item \(i\) is the probability that item \(i\) beats an item chosen uniformly at random from all other items. An algorithm is presented that counts the number of comparisons won, and uses these counts to decide whether to stop, or to compare another pair of items, chosen based on confidence intervals specified by the data collected up to that point. It is shown that the algorithm succeeds in recovering the ranking using a number of comparisons (which is called the sample complexity) that is optimal up to logarithmic factors. Moreover it is proven that the algorithm remains optimal when imposing common parametric assumptions on the probabilities \(M_{ij}\) such as the Bradley-Terry-Luce model (see [\textit{R. D. Luce}, Individual choice behavior. A theoretical analysis. New York: John Wiley \& Sons, Inc.; London: Chapman \& Hall, Ltd. (1959; Zbl 0093.31708)]) or Thurstone model (see [\textit{L. Thurstone}, ``A law of comparative judgment, Psychol. Rev. 34, No. 4, 273--286 (1927; \url{doi:10.1037/h0070288})]). This shows, quite surprisingly, that popular parametric modeling choices offer at most a logarithmic gain in the sample complexity; this gain needs to be weighed against the potential lack of robustness incurred by using a parametric mode, as shown in the numerical results section. The discussion in the paper notices that for essentially deterministic comparison models (meaning that the probabilities \(M_{ij}\) may be arbitrarily close to zero ore one), there indeed can be significant gains in the sample complexity if to use the parametric assumptions.
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- A nearly instance optimal algorithm for top-k ranking under the multinomial logit model
- Rank Centrality: Ranking from Pairwise Comparisons
- Top-\(\kappa\) selection with pairwise comparisons
- An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity
- A Sequential Procedure for Selecting the Population with the Largest Mean from k Normal Populations
- Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
- Active ranking from pairwise comparisons and when parametric assumptions do not help
- Competitive analysis of the top-K ranking problem
- Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
- scientific article; zbMATH DE number 3152611 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 3073477 (Why is no real title available?)
- Majorization, entropy and paired comparisons
- MM algorithms for generalized Bradley-Terry models.
- On the complexity of best-arm identification in multi-armed bandit models
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
- The \(K\)-armed dueling bandits problem
- Top-\(\kappa\) selection with pairwise comparisons
- Towards optimal estimation of bivariate isotonic matrices with unknown permutations
- Optimal full ranking from pairwise comparisons
- Active ranking from pairwise comparisons and when parametric assumptions do not help
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- Competitive analysis of the top-K ranking problem
- A nearly instance optimal algorithm for top-k ranking under the multinomial logit model
- A new and flexible approach to the analysis of paired comparison data
- Minimax rates and efficient algorithms for noisy sorting
- Preference-based online learning with dueling bandits: a survey
- Robust Learning of Consumer Preferences
- Low permutation-rank matrices: structural properties and noisy completion
- Time-homogeneous top-\(K\) ranking using tensor decompositions
- Asymptotically Optimal Sequential Design for Rank Aggregation
- Ranking and selection for pairwise comparison
- A General Pairwise Comparison Model for Extremely Sparse Networks
- Pair-matching: link prediction with adaptive queries
- Knowledge gradient procedure to select the best system under pairwise comparisons
- Extreme score distributions in countable-outcome round-robin tournaments of equally strong players
This page was built for publication: Active ranking from pairwise comparisons and when parametric assumptions do not help
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2284367)
