Active Ranking with Subset-wise Preferences

By Aadirupa Saha, Aditya Gopalan. 2018

31 citations recorded by the source corpus.

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 $\epsilon$-optimal ranking of the $n$ items with probability at least $1 - \delta$. When the feedback in each subset round is a single Plackett-Luce-sampled item, we show $(\epsilon, \delta)$-PAC algorithms with a sample complexity of $O\left(\frac{n}{\epsilon^2} \ln \frac{n}{\delta} \right)$ rounds, which we establish as being order-optimal by exhibiting a matching sample complexity lower bound of $\Omega\left(\frac{n}{\epsilon^2} \ln \frac{n}{\delta} \right)$---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$ ($\leq k$) ranking feedback according to the PL model from each adaptively chosen subset of size $k$, we show that an $(\epsilon, \delta)$-PAC ranking sample complexity of $O\left(\frac{n}{m \epsilon^2} \ln \frac{n}{\delta} \right)$ 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.

Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Economics and Econometrics

In Management Science and Operations Research

In Evaluation & Benchmarks

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, methodology): “Yue and Joachims (2009, 2011); Saha and Krishnamurthy (2022); Ghoshal and Saha (2022); Saha and Gopalan (2018a) The setting is relevant in various realworld systems which aim to collect information from user preferences, including recommender systems, retail management, search engine optimization,…”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “…comparisons (Yue et al., 2012; Zoghi et al., 2014b; Yue and Joachims, 2009, 2011; Saha and Krishnamurthy, 2022; Ghoshal and Saha, 2022; Saha and Gopalan, 2018a; Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019; Faury et al., 2020).”
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons (2020, methodology): “We note that assumptions A1) to A3) are common in the literature (e.g., (Szörényi et al., 2015; Shah and Wainwright, 2017; Falahatgar et al., 2017a;b; 2018; Heckel et al., 2018; Katariya et al., 2018; Heckel et al., 2019; Saha and Gopalan, 2019a;b; Ren et al., 2019)).”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, unknown): “…et al., 2015; Saha et al., 2021], best-arm identiﬁcation [Saha and Gopalan, 2019b, 2020; Yue and Joachims, 2011], full-ranking [Szörényi et al., 2015; Falahatgar et al., 2017; Saha and Gopalan, 2018], top-set detection [Busa-Fekete et al., 2013; Mohajer et al., 2017; Chen et al., 2018], etc.”