Exact and Approximate Condorcet Winner Identification in Dueling Bandits

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 $1-\delta$ using $O({\sum }_{k\ne k^{\star }}{\Delta }_k^{-2}(\ln \frac{K}{\delta }+\ln \ln \frac{1}{{\Delta }_k}))$ comparisons, where ${\Delta }_k$ is the Condorcet gap of arm $k$. 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 ${ϵ}^{\prime }$-approximate Condorcet winner with $\tilde{O}((1+N){\sum }_k\max ({\Delta }_k,{ϵ}^{\prime }{)}^{-2})$ comparisons, where $N$ is the number of arms near-tied with the winner. This is optimal up to logarithmic factors when $N=0$, and a second lower bound shows that without transitivity the factor $N$ cannot be removed: unlike in $ϵ$-best-arm identification, ${\sum }_k\max ({\Delta }_k,{ϵ}^{\prime }{)}^{-2}$ 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 $\tilde{O}\left(\frac{1}{\rho \eta {ϵ}^2}\right)$ does not depend on the number of arms and improves with the proportion $\rho$ of good arms.