# Adversarial Dueling Bandits

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2020.

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

- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2202.00935/) (2022)
- [Dueling Convex Optimization with General Preferences](https://mlsanity.com/paper/2210.02562/) (2022)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [Active Learning with Label Comparisons](https://mlsanity.com/paper/2204.04670/) (2022)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits](https://mlsanity.com/paper/2210.14998/) (2022)
- [Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources](https://mlsanity.com/paper/2312.17229/) (2023)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Biased Dueling Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2408.14603/) (2024)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2506.01250/) (2025)
- [Reinforcement Learning from Adversarial Preferences in Tabular MDPs](https://mlsanity.com/paper/2507.11706/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Online Learning and Equilibrium Computation with Ranking Feedback](https://mlsanity.com/paper/2603.19221/) (2026)
- [Online Convex Optimization with Dueling Feedback](https://mlsanity.com/paper/2608.15050/) (2026)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [Adversarial Multi-dueling Bandits](https://mlsanity.com/paper/2406.12475/) (2024)
- [Fusing Reward and Dueling Feedback in Stochastic Bandits](https://mlsanity.com/paper/2504.15812/) (2025)
- [Efficient Preference Poisoning Attack on Offline RLHF](https://mlsanity.com/paper/2605.02495/) (2026)
- [Set2Seq Transformer: Temporal and Position-Aware Set Representations for Sequential Multiple-Instance Learning](https://mlsanity.com/paper/2408.03404/) (2024)

## Abstract (arXiv)

We introduce the problem of regret minimization in Adversarial Dueling Bandits. As in classic Dueling Bandits, the learner has to repeatedly choose a pair of items and observe only a relative binary `win-loss' feedback for this pair, but here this feedback is generated from an arbitrary preference matrix, possibly chosen adversarially. Our main result is an algorithm whose T-round regret compared to the Borda-winner from a set of K items is tildeO(K1/3T2/3), as well as a matching Omega(K1/3T2/3) lower bound. We also prove a similar high probability regret bound. We further consider a simpler fixed-gap adversarial setup, which bridges between two extreme preference feedback models for dueling bandits: stationary preferences and an arbitrary sequence of preferences. For the fixed-gap adversarial setup we give an smash tildeO((K/Delta2)logT)  regret algorithm, where Delta is the gap in Borda scores between the best item and all other items, and show a lower bound of Omega(K/Delta2) indicating that our dependence on the main problem parameters K and Delta is tight (up to logarithmic factors).