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

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

## Key facts

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

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

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHF](https://mlsanity.com/paper/2401.16335/) (2024)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences](https://mlsanity.com/paper/2403.01857/) (2024)
- [Principled Preferential Bayesian Optimization](https://mlsanity.com/paper/2402.05367/) (2024)
- [Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems](https://mlsanity.com/paper/2307.12975/) (2023)
- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignment](https://mlsanity.com/paper/2505.19241/) (2025)
- [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)
- [Neural Dueling Bandits: Preference-Based Optimization with Human Feedback](https://mlsanity.com/paper/2407.17112/) (2024)
- [Dueling Convex Optimization with General Preferences](https://mlsanity.com/paper/2210.02562/) (2022)
- [Dueling Bandits with Adversarial Sleeping](https://mlsanity.com/paper/2107.02274/) (2021)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (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)
- [Active Human Feedback Collection via Neural Contextual Dueling Bandits](https://mlsanity.com/paper/2504.12016/) (2025)
- [Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources](https://mlsanity.com/paper/2312.17229/) (2023)
- [Biased Dueling Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2408.14603/) (2024)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Heterogeneous Adversarial Play in Interactive Environments](https://mlsanity.com/paper/2510.18407/) (2025)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [Federated Linear Dueling Bandits](https://mlsanity.com/paper/2502.01085/) (2025)
- [Reinforcement Learning from Adversarial Preferences in Tabular MDPs](https://mlsanity.com/paper/2507.11706/) (2025)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2405.11226/) (2024)
- [Adversarial Multi-dueling Bandits](https://mlsanity.com/paper/2406.12475/) (2024)
- [Efficient Preference Poisoning Attack on Offline RLHF](https://mlsanity.com/paper/2605.02495/) (2026)

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