# Identifying Copeland Winners in Dueling Bandits with Indifferences

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 81 references that are in the map.
- First posted on arXiv 1 Oct 2023.

## Builds on (most cited first, 30 of 30)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Preferential Bayesian Optimization](https://mlsanity.com/paper/1704.03651/) (2017)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Double Thompson Sampling for Dueling Bandits](https://mlsanity.com/paper/1604.07101/) (2016)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits](https://mlsanity.com/paper/1601.03855/) (2016)
- [Confidence sequences for sampling without replacement](https://mlsanity.com/paper/2006.04347/) (2020)
- [Top-k Ranking Bayesian Optimization](https://mlsanity.com/paper/2012.10688/) (2020)
- [ROIAL: Region of Interest Active Learning for Characterizing Exoskeleton Gait Preference Landscapes](https://mlsanity.com/paper/2011.04812/) (2020)
- [Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm](https://mlsanity.com/paper/1605.01677/) (2016)
- [Multi-Dueling Bandits and Their Application to Online Ranker Evaluation](https://mlsanity.com/paper/1608.06253/) (2016)
- [Human Preferences as Dueling Bandits](https://mlsanity.com/paper/2204.10362/) (2022)
- [On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons](https://mlsanity.com/paper/1909.03194/) (2019)
- [From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model](https://mlsanity.com/paper/1903.00558/) (2019)
- [The Sample Complexity of Best-k Items Selection from Pairwise Comparisons](https://mlsanity.com/paper/2007.03133/) (2020)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2202.00935/) (2022)
- [AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration](https://mlsanity.com/paper/2212.00333/) (2022)
- [Sequential Preference-Based Optimization](https://mlsanity.com/paper/1801.02788/) (2018)
- [Davidson-Luce model for multi-item choice with ties](https://mlsanity.com/paper/1909.07123/) (2019)
- [PAC Mode Estimation using PPR Martingale Confidence Sequences](https://mlsanity.com/paper/2109.05047/) (2021)
- [Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget](https://mlsanity.com/paper/2202.04487/) (2022)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)
- [Modelling and analysis of rank ordered data with ties via a generalized Plackett-Luce model](https://mlsanity.com/paper/2212.08543/) (2022)
- [Crowdsourcing Pareto-Optimal Object Finding by Pairwise Comparisons](https://mlsanity.com/paper/1409.4161/) (2014)

## Abstract (arXiv)

We consider the task of identifying the Copeland winner(s) in a dueling bandits problem with ternary feedback. This is an underexplored but practically relevant variant of the conventional dueling bandits problem, in which, in addition to strict preference between two arms, one may observe feedback in the form of an indifference. We provide a lower bound on the sample complexity for any learning algorithm finding the Copeland winner(s) with a fixed error probability. Moreover, we propose POCOWISTA, an algorithm with a sample complexity that almost matches this lower bound, and which shows excellent empirical performance, even for the conventional dueling bandits problem. For the case where the preference probabilities satisfy a specific type of stochastic transitivity, we provide a refined version with an improved worst case sample complexity.