mlsanityData to 7 Oct 2026

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

arXiv 1605.01677 ↗First posted 5 May 2016stat.ML cs.LGcited by 16

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 5; 2024: 5; 2025: 1; 2026: 1.

16 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. 2022Batched Dueling Banditscited by 10
  6. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  7. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  8. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  9. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  10. 2024Biased Dueling Bandits with Stochastic Delayed Feedbackcited by 3
  11. 2022An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problemcited by 2
  12. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
4 more
  1. 2024Multi-Player Approaches for Dueling Banditscited by 2
  2. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  3. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0
  4. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0