Identifying Copeland Winners in Dueling Bandits with Indifferences
Viktor Bengs Björn Haddenhorst Eyke Hüllermeier
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.