# From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2019.

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

- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget](https://mlsanity.com/paper/2202.04487/) (2022)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits](https://mlsanity.com/paper/2210.14998/) (2022)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [When the Universe is Too Big: Bounding Consideration Probabilities for Plackett-Luce Rankings](https://mlsanity.com/paper/2401.11016/) (2024)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [Identifying Copeland Winners in Dueling Bandits with Indifferences](https://mlsanity.com/paper/2310.00750/) (2023)
- [Optimal Top-k Identification from Pairwise Comparisons](https://mlsanity.com/paper/2607.08979/) (2026)

## Abstract (arXiv)

We consider PAC-learning a good item from k-subsetwise feedback information sampled from a Plackett-Luce probability model, with instance-dependent sample complexity performance. In the setting where subsets of a fixed size can be tested and top-ranked feedback is made available to the learner, we give an algorithm with optimal instance-dependent sample complexity, for PAC best arm identification, of Obigg(fracθ[k]ksumi = 2nmaxBig(1,frac1Deltai2Big) lnfrackδBig(ln frac1DeltaiBig)bigg), Deltai being the Plackett-Luce parameter gap between the best and the ith best item, and θ[k] is the sum of the pl, parameters for the top-k items. The algorithm is based on a wrapper around a PAC winner-finding algorithm with weaker performance guarantees to adapt to the hardness of the input instance. The sample complexity is also shown to be multiplicatively better depending on the length of rank-ordered feedback available in each subset-wise play. We show optimality of our algorithms with matching sample complexity lower bounds. We next address the winner-finding problem in Plackett-Luce models in the fixed-budget setting with instance dependent upper and lower bounds on the misidentification probability, of Omegaleft(exp(-2 tilde Delta Q) right) for a given budget Q, where tilde Delta is an explicit instance-dependent problem complexity parameter. Numerical performance results are also reported.