acceptodds
Desk rejected at ICLR 2027

Exact and Approximate Condorcet Winner Identification in Dueling Bandits

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

We study fixed-confidence identification in dueling bandits under the assumption that the preference matrix admits an approximate Condorcet winner (CW). We first propose , a phased elimination algorithm whose pivot is selected through a median-of-quantiles estimator of each arm's preference column, obtained by sub-sampling a constant number of random opponents, and prove that, if it exists, it returns the CW with probability at least using comparisons, where is the Condorcet gap of arm . Our main contribution concerns approximate identification, previously studied only under transitivity or parametric assumptions. When some arm beats every other arm up to a slack , a two-stage variant returns an -approximate Condorcet winner with comparisons, where is the number of arms near-tied with the winner. This is optimal up to logarithmic factors when , and a second lower bound shows that without transitivity the factor cannot be removed: unlike in -best-arm identification, alone does not govern the sample complexity. Finally, relaxing the minimum in the definition of a Condorcet winner into a quantile yields an algorithm whose sample complexity does not depend on the number of arms and improves with the proportion of good arms.

Primary area:
learning theory
Keywords:
dueling bandits best arm identification Condorcet winner pure exploration PAC learning sample complexity pairwise comparisons

Related papers

Discussion (0)

Sign in to comment.