We study best-arm identification in stochastic dueling bandits under the sole assumption that a Condorcet winner exists, i.e., an arm that wins each noisy pairwise comparison with probability at least 1/2. We introduce a new identification procedure that exploits the full gap matrix Δ𝑖,𝑗=𝑞𝑖,𝑗−12 (where 𝑞𝑖,𝑗 is the probability that arm 𝑖 beats arm 𝑗), rather than only the gaps between the Condorcet winner and the other arms. We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones by leveraging informative comparisons beyond those involving the winner. We complement these results with new lower bounds which, to our knowledge, are the first for Condorcet-winner identification in stochastic dueling bandits. Our lower-bound analysis isolates the intrinsic cost of locating informative entries in the gap matrix and estimating them to the required confidence, establishing the optimality of our non-asymptotic bounds. Overall, our results reveal new regimes and trade-offs in the sample complexity that are not captured by asymptotic analyses based only on the expected budget.
@inproceedings{saad:hal-05551276,title={{The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits}},author={Saad, El Mehdi and Thuot, Victor and Verzelen, Nicolas},url={https://hal.science/hal-05551276},year={2026},month=mar,keywords={Best arm identification ; Dueling bandits ; Query complexity ; Condorcet winner. ; Best arm identification Dueling bandits Query complexity Condorcet winner ; Condorcet winner},}