# PAC Battling Bandits in the Plackett-Luce Model

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2018.

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

- [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)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [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)
- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback](https://mlsanity.com/paper/2302.03805/) (2023)
- [Neural Dueling Bandits: Preference-Based Optimization with Human Feedback](https://mlsanity.com/paper/2407.17112/) (2024)
- [Dueling Bandits with Adversarial Sleeping](https://mlsanity.com/paper/2107.02274/) (2021)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [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)
- [Active Human Feedback Collection via Neural Contextual Dueling Bandits](https://mlsanity.com/paper/2504.12016/) (2025)
- [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)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Federated Linear Dueling Bandits](https://mlsanity.com/paper/2502.01085/) (2025)
- [Multi-Armed Bandits With Best-Action Queries](https://mlsanity.com/paper/2605.08287/) (2026)
- [Pure Exploration with Structured Preference Feedback](https://mlsanity.com/paper/2104.05294/) (2021)
- [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)
- [Adversarial Multi-dueling Bandits](https://mlsanity.com/paper/2406.12475/) (2024)
- [BlitzRank: Principled Zero-shot Ranking Agents with Tournament Graphs](https://mlsanity.com/paper/2602.05448/) (2026)
- [Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives](https://mlsanity.com/paper/2603.18972/) (2026)
- [Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries](https://mlsanity.com/paper/2606.08410/) (2026)
- [Optimal Top-k Identification from Pairwise Comparisons](https://mlsanity.com/paper/2607.08979/) (2026)

## Abstract (arXiv)

We introduce the probably approximately correct (PAC) Battling-Bandit problem with the Plackett-Luce (PL) subset choice model--an online learning framework where at each trial the learner chooses a subset of k arms from a fixed set of n arms, and subsequently observes a stochastic feedback indicating preference information of the items in the chosen subset, e.g., the most preferred item or ranking of the top m most preferred items etc. The objective is to identify a near-best item in the underlying PL model with high confidence. This generalizes the well-studied PAC Dueling-Bandit problem over n arms, which aims to recover the best-arm from pairwise preference information, and is known to require O(fracnε2 ln frac1δ) sample complexity citepBusapl,Busatop. We study the sample complexity of this problem under various feedback models: (1) Winner of the subset (WI), and (2) Ranking of top-m items (TR) for 2≤ m ≤ k. We show, surprisingly, that with winner information (WI) feedback over subsets of size 2 ≤ k ≤ n, the best achievable sample complexity is still Oleft( fracnε2 ln frac1δright), independent of k, and the same as that in the Dueling Bandit setting (k=2). For the more general top-m ranking (TR) feedback model, we show a significantly smaller lower bound on sample complexity of Omegabigg( fracnmε2 ln frac1δbigg), which suggests a multiplicative reduction by a factor m owing to the additional information revealed from preferences among m items instead of just 1. We also propose two algorithms for the PAC problem with the TR feedback model with optimal (upto logarithmic factors) sample complexity guarantees, establishing the increase in statistical efficiency from exploiting rank-ordered feedback.