# Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback

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

## Key facts

- Cited by 9 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 65 references that are in the map.
- First posted on arXiv 16 Apr 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)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning](https://mlsanity.com/paper/1910.10897/) (2019)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [The Ingredients of Real-World Robotic Reinforcement Learning](https://mlsanity.com/paper/2004.12570/) (2020)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [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)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2106.02978/) (2021)
- [Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes](https://mlsanity.com/paper/2212.05949/) (2022)
- [A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits](https://mlsanity.com/paper/1601.03855/) (2016)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)

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

- [Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Dueling](https://mlsanity.com/paper/2405.11204/) (2024)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [On the Exponential Convergence for Offline RLHF with Pairwise Comparisons](https://mlsanity.com/paper/2406.12205/) (2024)
- [Contextual bandits with entropy-based human feedback](https://mlsanity.com/paper/2502.08759/) (2025)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions](https://mlsanity.com/paper/2605.01752/) (2026)
- [Linear and Neural Dueling Bandits with Delayed Feedback](https://mlsanity.com/paper/2605.26554/) (2026)
- [CUPID in the Model Zoo: Online Matchmaking for Selecting Your Dream LLM](https://mlsanity.com/paper/2606.00846/) (2026)
- [Robust Risk-Sensitive Reinforcement Learning from Corrupted Human Feedback](https://mlsanity.com/paper/2609.38938/) (2026)

## Abstract (arXiv)

Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM). However, the effectiveness of this approach can be influenced by adversaries, who may intentionally provide misleading preferences to manipulate the output in an undesirable or harmful direction. To tackle this challenge, we study a specific model within this problem domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose an algorithm, namely robust contextual dueling bandits, which is based on uncertainty-weighted maximum likelihood estimation. Our algorithm achieves an tilde O(d√T/kappa+dC/kappa) regret bound, where T is the number of rounds, d is the dimension of the context, kappa is the lower bound of the derivative of the link function, and  0 ≤ C ≤ T is the total number of adversarial feedback. We also prove a lower bound to show that our regret bound is nearly optimal, both in scenarios with and without (C=0) adversarial feedback. Our work is the first to achieve nearly minimax optimal regret for dueling bandits in the presence of adversarial preference feedback. Additionally, for the sigmoid link function, we develop a novel algorithm that takes into account the effect of local derivatives in maximum likelihood estimation (MLE) analysis through a refined method for estimating the link function's derivative. This method helps us to eliminate the kappa dependence in the leading term with respect to T, which reduces the exponential dependence on the parameter radius B to a polynomial dependence. We conduct experiments to evaluate our proposed algorithm against various types of adversarial feedback. Experimental results demonstrate its superiority over the state-of-the-art dueling bandit algorithms in the presence of adversarial feedback.