# Contextual Dueling Bandits

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

## Key facts

- Cited by 101 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2015.

## Built on by (most cited first, 30 of 101)

- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Using Human Feedback to Fine-tune Diffusion Models without Any Reward Model](https://mlsanity.com/paper/2311.13231/) (2023)
- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)
- [A Minimaximalist Approach to Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2401.04056/) (2024)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [REBEL: Reinforcement Learning via Regressing Relative Rewards](https://mlsanity.com/paper/2404.16767/) (2024)
- [Pairwise Proximal Policy Optimization: Harnessing Relative Feedback for LLM Alignment](https://mlsanity.com/paper/2310.00212/) (2023)
- [Online Iterative Reinforcement Learning from Human Feedback with General Preference Model](https://mlsanity.com/paper/2402.07314/) (2024)
- [Efficient Exploration for LLMs](https://mlsanity.com/paper/2402.00396/) (2024)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Dataset Reset Policy Optimization for RLHF](https://mlsanity.com/paper/2404.08495/) (2024)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHF](https://mlsanity.com/paper/2410.04612/) (2024)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Beyond Bradley-Terry Models: A General Preference Model for Language Model Alignment](https://mlsanity.com/paper/2410.02197/) (2024)
- [Provable Reward-Agnostic Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.18505/) (2023)
- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [Sample Efficient Preference Alignment in LLMs via Active Exploration](https://mlsanity.com/paper/2312.00267/) (2023)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Adaptive Batch-Wise Sample Scheduling for Direct Preference Optimization](https://mlsanity.com/paper/2506.17252/) (2025)
- [Principled Preferential Bayesian Optimization](https://mlsanity.com/paper/2402.05367/) (2024)
- [Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Models](https://mlsanity.com/paper/2406.04274/) (2024)
- [Sample-Efficient Alignment for LLMs](https://mlsanity.com/paper/2411.01493/) (2024)
- [Inverse-Q*: Token Level Reinforcement Learning for Aligning Large Language Models Without Preference Data](https://mlsanity.com/paper/2408.14874/) (2024)

## Abstract (arXiv)

We consider the problem of learning to choose actions using contextual information when provided with limited feedback in the form of relative pairwise comparisons. We study this problem in the dueling-bandits framework of Yue et al. (2009), which we extend to incorporate context. Roughly, the learner's goal is to find the best policy, or way of behaving, in some space of policies, although "best" is not always so clearly defined. Here, we propose a new and natural solution concept, rooted in game theory, called a von Neumann winner, a randomized policy that beats or ties every other policy. We show that this notion overcomes important limitations of existing solutions, particularly the Condorcet winner which has typically been used in the past, but which requires strong and often unrealistic assumptions. We then present three efficient algorithms for online learning in our setting, and for approximating a von Neumann winner from batch-like data. The first of these algorithms achieves particularly low regret, even when data is adversarial, although its time and space requirements are linear in the size of the policy space. The other two algorithms require time and space only logarithmic in the size of the policy space when provided access to an oracle for solving classification problems on the space.