# Active Ranking with Subset-wise Preferences

arXiv: https://arxiv.org/abs/1810.10321 · HTML: https://mlsanity.com/paper/1810.10321/

## Key facts

- Cited by 21 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 23 Oct 2018.

## Built on by (most cited first, 21 of 21)

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHF](https://mlsanity.com/paper/2401.16335/) (2024)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences](https://mlsanity.com/paper/2403.01857/) (2024)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [Neural Dueling Bandits: Preference-Based Optimization with Human Feedback](https://mlsanity.com/paper/2407.17112/) (2024)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [Active Human Feedback Collection via Neural Contextual Dueling Bandits](https://mlsanity.com/paper/2504.12016/) (2025)
- [Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources](https://mlsanity.com/paper/2312.17229/) (2023)
- [Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization](https://mlsanity.com/paper/2402.18917/) (2024)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [Federated Linear Dueling Bandits](https://mlsanity.com/paper/2502.01085/) (2025)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Learning an Optimal Assortment Policy under Observational Data](https://mlsanity.com/paper/2502.06777/) (2025)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2405.11226/) (2024)
- [Fair Active Ranking from Pairwise Preferences](https://mlsanity.com/paper/2402.03252/) (2024)
- [Cold-Start Active Preference Learning in Socio-Economic Domains](https://mlsanity.com/paper/2508.05090/) (2025)
- [Learning Distributions from Multiple Data Providers](https://mlsanity.com/paper/2607.24732/) (2026)
- [Beyond Pairwise Feedback: Listwise Vision-Language Supervision for Preference-Based Reward Learning](https://mlsanity.com/paper/2608.25350/) (2026)

## Abstract (arXiv)

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 Oleft(fracnε2 ln fracnδ right) rounds, which we establish as being order-optimal by exhibiting a matching sample complexity lower bound of Omegaleft(fracnε2 ln fracnδ 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 (≤ 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 Oleft(fracnm ε2 ln fracnδ 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(n2) pairwise score estimates that has been used in prior work. We report results of numerical experiments that corroborate our findings.