mlsanityData to 7 Oct 2026

Contextual Dueling Bandits

arXiv 1502.06362 ↗First posted 23 Feb 2015cs.LGcited by 101

Not on the map. Why?

Cited by 47 in LLM alignment / RLHF / preference optimisation, but placed by its own abstract, which didn’t fit.

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 10; 2023: 12; 2024: 32; 2025: 22; 2026: 20.

101 papers.

Sort:

By area:

  1. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  2. 2023Using Human Feedback to Fine-tune Diffusion Models without Any Reward Modelcited by 246
  3. 2024Self-Play Preference Optimization for Language Model Alignmentcited by 228
  4. 2024Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferencescited by 176
  5. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 141
  6. 2023Is RLHF More Difficult than Standard RL?cited by 96
  7. 2024REBEL: Reinforcement Learning via Regressing Relative Rewardscited by 66
  8. 2023Pairwise Proximal Policy Optimization: Harnessing Relative Feedback for LLM Alignmentcited by 57
  9. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  10. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  11. 2024Efficient Exploration for LLMscited by 44
  12. 2024Dataset Reset Policy Optimization for RLHFcited by 41
38 more
  1. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  2. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  3. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  4. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  5. 2024Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHFcited by 29
  6. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  7. 2024Beyond Bradley-Terry Models: A General Preference Model for Language Model Alignmentcited by 24
  8. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  9. 2024Optimal Design for Reward Modeling in RLHFcited by 23
  10. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  11. 2023Sample Efficient Preference Alignment in LLMs via Active Explorationcited by 18
  12. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  13. 2024Principled Preferential Bayesian Optimizationcited by 16
  14. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  15. 2024Sample-Efficient Alignment for LLMscited by 16
  16. 2025Adaptive Batch-Wise Sample Scheduling for Direct Preference Optimizationcited by 16
  17. 2025Toward Efficient Exploration by Large Language Model Agentscited by 15
  18. 2024Inverse-Q*: Token Level Reinforcement Learning for Aligning Large Language Models Without Preference Datacited by 12
  19. 2022Batched Dueling Banditscited by 10
  20. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  21. 2021Preference learning along multiple criteria: A game-theoretic perspectivecited by 9
  22. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  23. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  24. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  25. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  26. 2025Doctor Approved: Generating Medically Accurate Skin Disease Images through AI-Expert Feedbackcited by 9
  27. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  28. 2025VARP: Reinforcement Learning from Vision-Language Model Feedback with Agent Regularized Preferencescited by 8
  29. 2024Bandits with Preference Feedback: A Stackelberg Game Perspectivecited by 7
  30. 2025Addressing Concept Mislabeling in Concept Bottleneck Models Through Preference Optimizationcited by 7
  31. 2024Active Preference Learning for Ordering Items In- and Out-of-samplecited by 6
  32. 2024Online Bandit Learning with Offline Preference Data for Improved RLHFcited by 6
  33. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  34. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  35. 2022Active Learning with Label Comparisonscited by 5
  36. 2022Dueling Convex Optimization with General Preferencescited by 5
  37. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  38. 2024Conversational Dueling Bandits in Generalized Linear Modelscited by 5

50 most cited of 101 All 101 (JSON)