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

Wenbo Ren, Jia Liu, Ness B. Shroff

Published 2018-06-08Version 1

This paper explores the adaptively (active) PAC (probably approximately correct) top-$k$ ranking and total ranking from $l$-wise ($l\geq 2$) comparisons under the popular multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output about 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 prove a lower bound on the sample complexity (aka number of queries), and propose an algorithm that is sample complexity optimal up to a $O(\log(k+l)/\log{k})$ factor. When $l=2$ (i.e., pairwise) or $l=O(poly(k))$, the algorithm matches the lower bound. For the PAC total ranking problem, we prove a lower bound, and propose an algorithm that matches the lower bound. When $l=2$, this model reduces to the popular Plackett-Luce (PL) model, and our results still outperform the state-of-the-art theoretically and numerically. We also run comparisons of our algorithms with the state-of-the-art on synthesized data as well as real-world data, and demonstrate the improvement on sample complexity numerically.