NeurIPS

2026

1. NeurIPS

   The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits

   El Mehdi Saad, Victor Thuot, and Nicolas Verzelen

   In Advances in Neural Information Processing Systems , Dec 2026

   To appear

   Abs Bib URL Poster

   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 Δ(i,j) = q(i,j) − 1/2 (where q(i,j) is the probability that arm i beats arm j), 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},
     booktitle = {Advances in Neural Information Processing Systems},
     year = {2026},
     month = dec,
     note = {To appear},
     url = {https://hal.science/hal-05551276},
   }