PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds

Wenbo Ren, Jia Liu, Ness B. ShroffarXiv 2018 · OpenReview

Abstract

This paper explores the adaptive (active) PAC (probably approximately correct) top-$k$ ranking (i.e., top-$k$ item selection) and total ranking problems from $l$-wise ($l\geq 2$) comparisons under the multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output of the most favored item of each query, we design ranking algorithms that recover the top-$k$ or total ranking using as few queries as possible. For the PAC top-$k$ ranking problem, we derive a lower bound on the sample complexity (aka number of queries), and propose an algorithm that is sample-complexity-optimal up to an $O(\log(k+l)/\log{k})$ factor. For the PAC total ranking problem, we derive a tight lower bound and propose an algorithm that matches it. When $l=2$, the MNL model reduces to the popular Plackett-Luce (PL) model. In this setting, our results still outperform the state-of-the-art both theoretically and numerically. We also compare our algorithms with the state-of-the-art using synthetic data as well as real-world data to verify the efficiency of our algorithms.

Introduction

In modern information retrieval and e-commerce, users are frequently presented with lists of items rather than simple pairs. While traditional active ranking research has focused on pairwise comparisons ($l=2$), this work addresses the more general and practical scenario of listwise queries ($l > 2$). We operate within the PAC (Probably Approximately Correct) framework, aiming to identify an $\epsilon$-accurate ranking with high probability ($1-\delta$) while minimizing the number of queries, known as sample complexity.

Theoretical Foundations

Lower Bound Analysis

We establish theoretical lower bounds for the number of queries required for any algorithm to achieve PAC accuracy. For total ranking, the complexity is $\Omega(\frac{n}{\epsilon^2} \log \frac{n}{\delta})$, and for top-$k$ selection, it is $\Omega(\frac{n}{\epsilon^2} \log \frac{k}{\delta})$. These bounds indicate that while listwise queries increase information throughput, they primarily offer constant-factor improvements over pairwise queries in worst-case scenarios.

The RBC Condition

A critical assumption in our analysis is the Ratios Bounded by a Constant (RBC) condition. This condition ensures that the preference scores of items are within a reasonable range, preventing scenarios where one item is infinitely preferred over others (making the problem trivial) or where noise levels make ranking impossible.

Proposed Algorithms

PairwiseDefeatingTotalRanking (PDTR)

For the total ranking task, we introduce PDTR. Unlike traditional methods that rely on simple mean-reward estimation, PDTR tracks the win ratios between pairs of items within the listwise query results. It utilizes an Upper Confidence Bound (UCB) mechanism to statistically "defeat" and remove items once their relative rank is established with sufficient confidence.

TournamentKSelection (TNKS)

For top-$k$ selection, we propose TNKS, a tournament-style algorithm. It recursively divides items into groups and applies a modified version of the PDTR logic (PDKS) to promote the best items to subsequent rounds. This filtering process efficiently narrows the search space to the top $k$ items.

Experimental Evaluation

We evaluated the proposed algorithms using both synthetic data and real-world movie preference datasets from PreFLib (specifically the 'ED-00004' datasets). Synthetic tests varied parameters such as $n, k, \epsilon,$ and $l$ to test robustness.

Performance comparison of TNKS against baselines for various list sizes ($l$) and top-$k$ targets.

As shown in the figure above, TNKS consistently achieves a higher correct rate with fewer queries compared to state-of-the-art baselines like Spectral MLE, Halving, and AlgPairwise/AlgMultiwise. Notably, the efficiency gains of TNKS are maintained across different list sizes ($l$) and selection targets ($k$), confirming its near-optimality and superiority over existing methods.

Conclusion

This work provides a comprehensive theoretical and empirical treatment of PAC ranking with listwise queries. While TNKS and PDTR offer significant performance improvements, future work could address the remaining logarithmic gap in the top-$k$ lower bound for very large $l$, the dependence on the RBC constant $C$, and explore settings with non-stationary user preferences.

Summary updated

Abstract

This paper explores the adaptive (active) PAC (probably approximately correct) top-$k$ ranking (i.e., top-$k$ item selection) and total ranking problems from $l$-wise ($l\geq 2$) comparisons under the multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output of the most favored item of each query, we want to design ranking algorithms that recover the top-$k$ or total ranking using as few queries as possible. For the PAC top-$k$ ranking problem, we derive a lower bound on the sample complexity (aka number of queries), and propose an algorithm that is sample-complexity-optimal up to an $O(\log(k+l)/\log{k})$ factor. When $l=2$ (i.e., pairwise comparisons) or $l=O(poly(k))$, this algorithm matches the lower bound. For the PAC total ranking problem, we derive a tight lower bound, and propose an algorithm that matches the lower bound. When $l=2$, the MNL model reduces to the popular Plackett-Luce (PL) model. In this setting, our results still outperform the state-of-the-art both theoretically and numerically. We also compare our algorithms with the state-of-the-art using synthetic data as well as real-world data to verify the efficiency of our algorithms.
BibTeX
@misc{ren2018pac,
  author = {Wenbo Ren and Jia Liu and Ness B. Shroff},
  title = {{PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds}},
  year = {2018},
  eprint = {1806.02970},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.02970},
}
Figure