mlsanityData to 14 Oct 2026

A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits

arXiv 1601.03855 ↗First posted 15 Jan 2016cs.LGcited by 31

Not on the map. Why?

Abstract (arXiv)

We study the K-armed dueling bandit problem which is a variation of the classical Multi-Armed Bandit (MAB) problem in which the learner receives only relative feedback about the selected pairs of arms. We propose a new algorithm called Relative Exponential-weight algorithm for Exploration and Exploitation (REX3) to handle the adversarial utility-based formulation of this problem. This algorithm is a non-trivial extension of the Exponential-weight algorithm for Exploration and Exploitation (EXP3) algorithm. We prove a finite time expected regret upper bound of order O(sqrt(K ln(K)T)) for this algorithm and a general lower bound of order omega(sqrt(KT)). At the end, we provide experimental results using real data from information retrieval applications.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). First posted on arXiv 15 Jan 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

31 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  2. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  3. 2024Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHFcited by 57
  4. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  5. 2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferencescited by 27
  6. 2024Principled Preferential Bayesian Optimizationcited by 16
  7. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 13
  8. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  9. 2025ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignmentcited by 10
  10. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  11. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  12. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
19 more
  1. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
  2. 2022Dueling Convex Optimization with General Preferencescited by 6
  3. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  4. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  5. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  6. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  7. 2025Active Human Feedback Collection via Neural Contextual Dueling Banditscited by 4
  8. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  9. 2024Biased Dueling Bandits with Stochastic Delayed Feedbackcited by 3
  10. 2025Online Clustering of Dueling Banditscited by 3
  11. 2025Heterogeneous Adversarial Play in Interactive Environmentscited by 3
  12. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  13. 2025Federated Linear Dueling Banditscited by 2
  14. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  15. 2024DP-Dueling: Learning from Preference Feedback without Compromising User Privacycited by 1
  16. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedbackcited by 1
  17. 2024Adversarial Multi-dueling Banditscited by 1
  18. 2026Efficient Preference Poisoning Attack on Offline RLHFcited by 1
  19. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0