mlsanityData to 7 Oct 2026

Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability

arXiv 2111.12306 ↗First posted 24 Nov 2021cs.LGcited by 44

Not on the map. Why?

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

Abstract (arXiv)

We study the K-armed contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes preference-based feedback suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class mathcal F. We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over mathcal F. This resolves an open problem of Dud'ik et al. [2015] on oracle efficient, regret-optimal algorithms for contextual dueling bandits.

Key facts. Cited by 44 papers in the map (data through 7 Oct 2026). Builds on 39 of its 70 references that are in the map. First posted on arXiv 24 Nov 2021.

Builds on

39 of 70 references.

References · 39

  1. 2019Introduction to Multi-Armed Banditscited by 475
  2. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  3. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  4. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  6. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  7. 2015Contextual Dueling Banditscited by 101
  8. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  9. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2021Adapting to Misspecification in Contextual Banditscited by 81
  11. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  12. 2017Preferential Bayesian Optimizationcited by 72
27 more
  1. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  2. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  3. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 59
  4. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 51
  5. 2016Double Thompson Sampling for Dueling Banditscited by 42
  6. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
  7. 2017Provably Optimal Algorithms for Generalized Linear Contextual Banditscited by 38
  8. 2015Copeland Dueling Banditscited by 36
  9. 2017Multi-dueling Bandits with Dependent Armscited by 35
  10. 2020Adversarial Dueling Banditscited by 33
  11. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 32
  12. 2016A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Banditscited by 31
  13. 2015Sparse Dueling Banditscited by 29
  14. 2018PAC Battling Bandits in the Plackett-Luce Modelcited by 27
  15. 2017Regret Analysis for Continuous Dueling Banditcited by 21
  16. 2018Active Ranking with Subset-wise Preferencescited by 21
  17. 2016BISTRO: An Efficient Relaxation-Based Method for Contextual Banditscited by 20
  18. 2019Combinatorial Bandits with Relative Feedbackcited by 19
  19. 2013A Generalized Online Mirror Descent with Applications to Classification and Regressioncited by 18
  20. 2018PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Boundscited by 17
  21. 2016Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithmcited by 16
  22. 2016Multi-Dueling Bandits and Their Application to Online Ranker Evaluationcited by 16
  23. 2016Improved Regret Bounds for Oracle-Based Adversarial Contextual Banditscited by 13
  24. 2017A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Modelcited by 12
  25. 2015Contextual Semibandits via Supervised Learning Oraclescited by 11
  26. 2020Best-item Learning in Random Utility Models with Subset Choicescited by 6
  27. 2020Non-stationary Online Regressioncited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 6; 2024: 19; 2025: 8; 2026: 6.

44 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 244
  2. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 141
  3. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  4. 2024Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHFcited by 57
  5. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  6. 2024Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHFcited by 29
  7. 2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferencescited by 27
  8. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  9. 2024Optimal Design for Human Preference Elicitationcited by 17
  10. 2024Principled Preferential Bayesian Optimizationcited by 16
  11. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  12. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
32 more
  1. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  2. 2024Bandits with Preference Feedback: A Stackelberg Game Perspectivecited by 7
  3. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
  4. 2024Active Preference Learning for Ordering Items In- and Out-of-samplecited by 6
  5. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  6. 2022Dueling Convex Optimization with General Preferencescited by 5
  7. 2024Conversational Dueling Bandits in Generalized Linear Modelscited by 5
  8. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  9. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4
  10. 2025Active Human Feedback Collection via Neural Contextual Dueling Banditscited by 4
  11. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3
  12. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  13. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  14. 2025Pre-Trained AI Model Assisted Online Decision-Making under Missing Covariates: A Theoretical Perspectivecited by 3
  15. 2023Faster Convergence with Multiway Preferencescited by 2
  16. 2024DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedbackcited by 2
  17. 2025Federated Linear Dueling Banditscited by 2
  18. 2025Online Clustering of Dueling Banditscited by 2
  19. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 2
  20. 2022Flexible and Efficient Contextual Bandits with Heterogeneous Treatment Effect Oraclescited by 1
  21. 2024MENTOR: Guiding Hierarchical Reinforcement Learning with Human Feedback and Dynamic Distance Constraintcited by 1
  22. 2024DP-Dueling: Learning from Preference Feedback without Compromising User Privacycited by 1
  23. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedbackcited by 1
  24. 2026Online Convex Optimization with Dueling Feedbackcited by 1
  25. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0
  26. 2023Sample Complexity of Preference-Based Nonparametric Off-Policy Evaluation with Deep Networkscited by 0
  27. 2025Thompson Sampling in Online RLHF with General Function Approximationcited by 0
  28. 2025Recycling History: Efficient Recommendations from Contextual Dueling Banditscited by 0
  29. 2025Offline Clustering of Preference Learning with Active-data Augmentationcited by 0
  30. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  31. 2026Linear and Neural Dueling Bandits with Delayed Feedbackcited by 0
  32. 2026On the Complexity of Preference-Based Banditscited by 0