mlsanityData to 7 Oct 2026

Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options

arXiv 2510.18713 ↗First posted 21 Oct 2025cs.LG cs.AI stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

We study online preference-based reinforcement learning (PbRL) with the goal of improving sample efficiency. While a growing body of theoretical work has emerged-motivated by PbRL's recent empirical success, particularly in aligning large language models (LLMs)-most existing studies focus only on pairwise comparisons. A few recent works (Zhu et al., 2023, Mukherjee et al., 2024, Thekumparampil et al., 2024) have explored using multiple comparisons and ranking feedback, but their performance guarantees fail to improve-and can even deteriorate-as the feedback length increases, despite the richer information available. To address this gap, we adopt the Plackett-Luce (PL) model for ranking feedback over action subsets and propose M-AUPO, an algorithm that selects multiple actions by maximizing the average uncertainty within the offered subset. We prove that M-AUPO achieves a suboptimality gap of tildeOleft( fracdT √ sumt=1T frac1|St| right), where T is the total number of rounds, d is the feature dimension, and |St| is the size of the subset at round t. This result shows that larger subsets directly lead to improved performance and, notably, the bound avoids the exponential dependence on the unknown parameter's norm, which was a fundamental limitation in most previous works. Moreover, we establish a near-matching lower bound of Omega left( fracdK √T right), where K is the maximum subset size. To the best of our knowledge, this is the first theoretical result in PbRL with ranking feedback that explicitly shows improved sample efficiency as a function of the subset size.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 68 of its 99 references that are in the map. First posted on arXiv 21 Oct 2025.

Builds on

68 of 99 references.

References · 68

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  3. 2017Deep reinforcement learning from human preferencescited by 3,846
  4. 2020Learning to summarize from human feedbackcited by 2,562
  5. 2024Gemma: Open Models Based on Gemini Research and Technologycited by 889
  6. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  7. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  8. 2024RLHF Workflow: From Reward Modeling to Online RLHFcited by 265
  9. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 244
  10. 2023Nash Learning from Human Feedbackcited by 220
  11. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 141
  12. 2024Provably Robust DPO: Aligning Language Models with Noisy Feedbackcited by 133
38 more
  1. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  2. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  3. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  4. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  5. 2015Contextual Dueling Banditscited by 101
  6. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  7. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  8. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
  9. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  10. 2024Active Preference Optimization for Sample Efficient RLHFcited by 61
  11. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  12. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
  13. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  14. 2024Active Preference Learning for Large Language Modelscited by 55
  15. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  16. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 51
  17. 2017MNL-Bandit: A Dynamic Learning Approach to Assortment Selectioncited by 50
  18. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  19. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  20. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  21. 2016Double Thompson Sampling for Dueling Banditscited by 42
  22. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  23. 2015Copeland Dueling Banditscited by 36
  24. 2019Lipschitz Adaptivity with Multiple Learning Rates in Online Learningcited by 36
  25. 2017Thompson Sampling for the MNL-Banditcited by 35
  26. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  27. 2020Adversarial Dueling Banditscited by 33
  28. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
  29. 2013Learning Trajectory Preferences for Manipulators via Iterative Improvementcited by 31
  30. 2015Sparse Dueling Banditscited by 29
  31. 2018Dynamic Assortment Optimization with Changing Contextual Informationcited by 28
  32. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
  33. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  34. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  35. 2024Optimal Design for Reward Modeling in RLHFcited by 23
  36. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  37. 2018Approximate Ranking from Pairwise Comparisonscited by 21
  38. 2021Multinomial Logit Contextual Bandits: Provable Optimality and Practicalitycited by 21

50 most cited of 68 All 68 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0
  2. 2026Beyond Pairwise Feedback: Listwise Vision-Language Supervision for Preference-Based Reward Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  2. 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
  3. 2026Data-dependent Exploration for Online Reinforcement Learning from Human Feedback
  4. 2023Query-Policy Misalignment in Preference-Based Reinforcement Learning
  5. 2025Direct Preference Optimization with Unobserved Preference Heterogeneity: The Necessity of Ternary Preferences
  6. 2024Direct Preference Optimization With Unobserved Preference Heterogeneity: The Necessity of Ternary Preferences
  7. 2025Best Policy Learning from Trajectory Preference Feedback
  8. 2025Greedy Sampling Is Provably Efficient for RLHF