# Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2016.

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

- [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)
- [Batched Dueling Bandits](https://mlsanity.com/paper/2202.10660/) (2022)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [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)
- [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)
- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (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)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Identifying Copeland Winners in Dueling Bandits with Indifferences](https://mlsanity.com/paper/2310.00750/) (2023)
- [Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives](https://mlsanity.com/paper/2603.18972/) (2026)

## Abstract (arXiv)

We study the K-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. The hardness of recommending Copeland winners, the arms that beat the greatest number of other arms, is characterized by deriving an asymptotic regret bound. We propose Copeland Winners Relative Minimum Empirical Divergence (CW-RMED) and derive an asymptotically optimal regret bound for it. However, it is not known whether the algorithm can be efficiently computed or not. To address this issue, we devise an efficient version (ECW-RMED) and derive its asymptotic regret bound. Experimental comparisons of dueling bandit algorithms show that ECW-RMED significantly outperforms existing ones.