mlsanityData to 14 Oct 2026

PAC Battling Bandits in the Plackett-Luce Model

arXiv 1808.04008 ↗First posted 12 Aug 2018cs.LG stat.MLcited by 27

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 4; 2023: 4; 2024: 6; 2025: 3; 2026: 5.

27 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  2. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  3. 2023Is RLHF More Difficult than Standard RL?cited by 96
  4. 2024Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHFcited by 57
  5. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  6. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  7. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  8. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  9. 2023Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedbackcited by 7
  10. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
  11. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  12. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
15 more
  1. 2024Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimizationcited by 4
  2. 2025Active Human Feedback Collection via Neural Contextual Dueling Banditscited by 4
  3. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3
  4. 2023Faster Convergence with Multiway Preferencescited by 3
  5. 2025Online Clustering of Dueling Banditscited by 3
  6. 2025Federated Linear Dueling Banditscited by 2
  7. 2026Multi-Armed Bandits With Best-Action Queriescited by 2
  8. 2021Pure Exploration with Structured Preference Feedbackcited by 1
  9. 2024DP-Dueling: Learning from Preference Feedback without Compromising User Privacycited by 1
  10. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedbackcited by 1
  11. 2024Adversarial Multi-dueling Banditscited by 1
  12. 2026BlitzRank: Principled Zero-shot Ranking Agents with Tournament Graphscited by 0
  13. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0
  14. 2026Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queriescited by 0
  15. 2026Optimal Top-k Identification from Pairwise Comparisonscited by 0