We consider the problem of probably approximately correct (PAC) ranking n items by adaptively eliciting subset-wise preference feedback. At each round, the learner chooses a subset of k items and observes stochastic feedback indicating preference information of the winner (most preferred) item of the chosen subset drawn according to a Plackett-Luce (PL) subset choice model unknown a priori. The objective is to identify an -optimal ranking of the n items with probability at least 1 − δ. When the feedback in each subset round is a single Plackett-Luce-sampled item, we show ( , δ)-PAC algorithms with a sample complexity of O n 2 ln n δ rounds, which we establish as being order-optimal by exhibiting a matching sample complexity lower bound of Ω n 2 ln n δ -this shows that there is essentially no improvement possible from the pairwise comparisons setting (k = 2). When, however, it is possible to elicit top-m (≤ k) ranking feedback according to the PL model from each adaptively chosen subset of size k, we show that an ( , δ)-PAC ranking sample complexity of O n m 2 ln n δ is achievable with explicit algorithms, which represents an m-wise reduction in sample complexity compared to the pairwise case. This again turns out to be order-wise unimprovable across the class of symmetric ranking algorithms. Our algorithms rely on a novel pivot trick to maintain only n itemwise score estimates, unlike O(n 2 ) pairwise score estimates that has been used in prior work. We report results of numerical experiments that corroborate our findings. idea in our algorithms to efficiently estimate a global ordering using only local comparisons with a pivot or probe element: split the entire pool into playable subsets all containing one common element, learn local orderings relative to this element and then merge. Here again, the IIA structure of the PL model helps to ensure consistency among preferences aggregated across disparate subsets but with a common reference pivot. Our sample complexity lower bounds are information-theoretic in nature and rely on a generic change-of-measure argument but with carefully crafted confusing instances. Related Work. Over the years, ranking from pairwise preferences (k = 2) has been studied in both the batch or non-adaptive setting Gleich and Lim [2011], Rajkumar and Agarwal [2016], Wauthier et al. [2013], Negahban et al. [2012] and the active or adaptive setting Braverman and Mossel [2008], Jamieson and Nowak [2011], Ailon [2012]. In particular, prior work has addressed the problem of statistical parameter estimation given preference observations from the Plackett-Luce model in the offline setting Rajkumar and Agarwal [2014], Negahban et al. [2012], Chen and Suh [2015], Khetan and Oh [2016], Hajek et al. [2014]. There also have been recent developments on the PAC objective for different pairwise preference models, such as those satisfying stochastic triangle inequalities and strong stochastic transitivity [Yue and Joachims, 2011], general utility-based preference models [Urvoy et al., 2013], the Plackett-Luce model [Szörényi et al., 2015] and the Mallows model [Busa-Fekete et al., 2014a]]. Recent work has studied PAC-learning objectives other than identifying the single (near) best arm, e.g. recovering a few of the top arms [Busa-Fekete et al., 2013, Mohajer et al., 2017, Chen et al., 2017], or the true ranking of the items [Busa-Fekete et al., 2014b, Falahatgar et al., 2017]. There is also work on the problem of Plackett-Luce parameter estimation in the subset-wise feedback setting Jang et al. [2017], Khetan and Oh [2016], but for the batch (offline) setup where the sampling is not adaptive. Recent work by Chen et al. [2018] analyzes an active learning problem in the Plackett-Luce model with subset-wise feedback; however, the objective there is to recover the top-(unordered) items of the model, unlike full-rank recovery considered in this work. Moreover, they give instance-dependent sample complexity bounds, whereas we allow a tolerance ( ) in defining good rankings, natural in many settings Szörényi et al. [2015], Yue and Joachims [2011], Busa-Fekete et al. [2014a]. Notation. We denote the set [n] = {1, 2, ..., n}. When there is no confusion about the context, we often represent (an unordered) subset S as a vector, or ordered subset, S of size |S| (according to, say, the order induced by the natural global ordering [n] of all the items). In this case, S(i) denotes the item (member) at the ith position in subset S. Σ S = {σ | σ is a permutation over items of S}. where for any permutation σ ∈ Σ S , σ(i) denotes the position of element i ∈ S in the ranking σ. 1(ϕ) denote an indicator variable that takes the value 1 if the predicate ϕ is true, and 0 otherwise. P r(A) is used to denote the probability of event A, in a probability space that is clear from the context. Ber(p) and Geo(p) respectively denote
REF examine the ranking problem under the PL model in the PAC setting.
Active Ranking with Subset-wise Preferences
ArXiv
ArXiv
Mathematics Computer Science