# Bandits with Preference Feedback: A Stackelberg Game Perspective

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

## Key facts

- Cited by 7 papers in the map (data through 14 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.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 30 of 38)

- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2307.15217/) (2023)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications](https://mlsanity.com/paper/1705.06270/) (2017)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [A Literature Survey of Benchmark Functions For Global Optimization Problems](https://mlsanity.com/paper/1308.4008/) (2013)
- [Preferential Bayesian Optimization](https://mlsanity.com/paper/1704.03651/) (2017)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Double Thompson Sampling for Dueling Bandits](https://mlsanity.com/paper/1604.07101/) (2016)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Multi-dueling Bandits with Dependent Arms](https://mlsanity.com/paper/1705.00253/) (2017)
- [Preference-Based Learning for Exoskeleton Gait Optimization](https://mlsanity.com/paper/1909.12316/) (2019)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Regret Analysis for Continuous Dueling Bandit](https://mlsanity.com/paper/1711.07693/) (2017)
- [Projective Preferential Bayesian Optimization](https://mlsanity.com/paper/2002.03113/) (2020)
- [Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processes](https://mlsanity.com/paper/2302.01513/) (2023)
- [Maximum Selection and Ranking under Noisy Comparisons](https://mlsanity.com/paper/1705.05366/) (2017)
- [Principled Preferential Bayesian Optimization](https://mlsanity.com/paper/2402.05367/) (2024)

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

- [Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2505.23673/) (2025)
- [Active Flow Expansion for Out-of-Distribution Discovery: from Theory to Molecules](https://mlsanity.com/paper/2606.08802/) (2026)
- [Adversarial Policy Optimization for Offline Preference-based Reinforcement Learning](https://mlsanity.com/paper/2503.05306/) (2025)
- [ActiveUltraFeedback: Efficient Preference Data Generation using Active Learning](https://mlsanity.com/paper/2603.09692/) (2026)
- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback](https://mlsanity.com/paper/2604.25025/) (2026)
- [On the Complexity of Preference-Based Bandits](https://mlsanity.com/paper/2609.39351/) (2026)

## 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.