mlsanityData to 7 Oct 2026

Adversarial Dueling Bandits

arXiv 2010.14563 ↗First posted 27 Oct 2020cs.LG stat.MLcited by 33

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 4; 2024: 9; 2025: 5; 2026: 6.

33 papers.

Sort:

By area:

  1. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  2. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  3. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  4. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  5. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  6. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  7. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  8. 2022Non-Stationary Dueling Banditscited by 7
  9. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  10. 2022Active Learning with Label Comparisonscited by 5
  11. 2022Dueling Convex Optimization with General Preferencescited by 5
  12. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
21 more
  1. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  2. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3
  3. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  4. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  5. 2024Biased Dueling Bandits with Stochastic Delayed Feedbackcited by 3
  6. 2022Learning to Identify Top Elo Ratings: A Dueling Bandits Approachcited by 2
  7. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  8. 2024Multi-Player Approaches for Dueling Banditscited by 2
  9. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  10. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  11. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  12. 2024DP-Dueling: Learning from Preference Feedback without Compromising User Privacycited by 1
  13. 2024Adversarial Multi-dueling Banditscited by 1
  14. 2025Fusing Reward and Dueling Feedback in Stochastic Banditscited by 1
  15. 2026Online Learning and Equilibrium Computation with Ranking Feedbackcited by 1
  16. 2026Online Convex Optimization with Dueling Feedbackcited by 1
  17. 2024Set2Seq Transformer: Temporal and Position-Aware Set Representations for Sequential Multiple-Instance Learningcited by 0
  18. 2025Continuum-armed Bandit Optimization with Batch Pairwise Comparison Oraclescited by 0
  19. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0
  20. 2026Efficient Preference Poisoning Attack on Offline RLHFcited by 0
  21. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0