Identifying Copeland Winners in Dueling Bandits with Indifferences
This work addresses an underexplored variant of dueling bandits relevant for practical scenarios with indifference feedback, offering incremental improvements in algorithm design.
The paper tackles the problem of identifying Copeland winners in dueling bandits with ternary feedback, where indifference is possible, and proposes the POCOWISTA algorithm that nearly matches a derived lower bound on sample complexity, showing strong empirical performance.
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.