mlsanityData to 7 Oct 2026

Bandits with Preference Feedback: A Stackelberg Game Perspective

arXiv 2406.16745 ↗First posted 24 Jun 2024cs.LG cs.AI cs.GTcited by 7

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

Abstract (arXiv)

Bandits with preference feedback present a powerful tool for optimizing unknown target functions when only pairwise comparisons are allowed instead of direct value queries. This model allows for incorporating human feedback into online inference and optimization and has been employed in systems for fine-tuning large language models. The problem is well understood in simplified settings with linear target functions or over finite small domains that limit practical interest. Taking the next step, we consider infinite domains and nonlinear (kernelized) rewards. In this setting, selecting a pair of actions is quite challenging and requires balancing exploration and exploitation at two levels: within the pair, and along the iterations of the algorithm. We propose MAXMINLCB, which emulates this trade-off as a zero-sum Stackelberg game, and chooses action pairs that are informative and yield favorable rewards. MAXMINLCB consistently outperforms existing algorithms and satisfies an anytime-valid rate-optimal regret guarantee. This is due to our novel preference-based confidence sequences for kernelized logistic estimators.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 38 of its 69 references that are in the map. First posted on arXiv 24 Jun 2024.

Builds on

38 of 69 references.

Closest ancestors · 5

Same direction, newest first

  1. 2023Nash Learning from Human Feedback1 Dec
  2. 2023Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback27 Jul
  3. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems24 Jul
  4. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons26 Jan
  5. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 33

  1. 2017On Kernelized Multi-armed Banditscited by 348
  2. 2018Approximation Methods for Bilevel Programmingcited by 231
  3. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  5. 2017A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applicationscited by 126
  6. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  7. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  8. 2015Contextual Dueling Banditscited by 101
  9. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  10. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  11. 2013A Literature Survey of Benchmark Functions For Global Optimization Problemscited by 75
  12. 2017Preferential Bayesian Optimizationcited by 72
21 more
  1. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  2. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  3. 2016Double Thompson Sampling for Dueling Banditscited by 42
  4. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  5. 2020Information Directed Sampling for Linear Partial Monitoringcited by 39
  6. 2015Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Playscited by 38
  7. 2017Multi-dueling Bandits with Dependent Armscited by 35
  8. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  9. 2019Preference-Based Learning for Exoskeleton Gait Optimizationcited by 23
  10. 2017Regret Analysis for Continuous Dueling Banditcited by 21
  11. 2020Projective Preferential Bayesian Optimizationcited by 21
  12. 2023Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processescited by 19
  13. 2017Maximum Selection and Ranking under Noisy Comparisonscited by 18
  14. 2024Principled Preferential Bayesian Optimizationcited by 16
  15. 2017Dueling Bandits With Weak Regretcited by 15
  16. 2019Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Casecited by 11
  17. 2019Zeroth Order Non-convex optimization with Dueling-Choice Banditscited by 11
  18. 2021Bias-Robust Bayesian Optimization via Dueling Banditscited by 11
  19. 2018Contextual bandits with surrogate losses: Margin bounds and efficient algorithmscited by 10
  20. 2018Factored Banditscited by 7
  21. 2023Kernelized Offline Contextual Dueling Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 5.

7 papers.

  1. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  2. 2025Adversarial Policy Optimization for Offline Preference-based Reinforcement Learningcited by 2
  3. 2026ActiveUltraFeedback: Efficient Preference Data Generation using Active Learningcited by 1
  4. 2026Active Flow Expansion for Out-of-Distribution Discovery: from Theory to Moleculescited by 1
  5. 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 0
  6. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  7. 2026On the Complexity of Preference-Based Banditscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Stackelberg Learning from Human Feedback: Preference Optimization as a Sequential Game
  2. 2025Greedy Sampling Is Provably Efficient for RLHF
  3. 2023Sample Efficient Preference Alignment in LLMs via Active Exploration
  4. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint
  5. 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
  6. 2026A Regret Minimization Framework on Preference Learning in Large Language Models
  7. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  8. 2026Efficient Exploration for Iterative Nash Preference Optimization