The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits

• URL: http://arxiv.org/abs/2603.15189v1
• Date: Mon, 16 Mar 2026 12:27:14 GMT
• Title: The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits
• Abstract summary: We study best-arm identification in dueling bandits under the sole assumption that a Condorcet winner exists.<n>We introduce a new identification procedure that exploits the full gap matrix $_i,j=q_i,j-tfrac12$.<n>We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones.
• Score: 6.244816393907942
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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}-\tfrac12$ (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.

Related papers

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Analysis of Search Heuristics in the Multi-Armed Bandit Setting [6.730459235906337]
  We consider the classic Multi-Armed Bandit setting to understand the exploration/exploitation tradeoffs made by different searchs.<n>We show that evolutionary algorithms are rather bad at identifying the Condorcet winner.
  arXiv  Detail & Related papers  (2026-04-09T11:27:59Z)
• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback.<n>This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc.<n>Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  We consider the best arm identification problem in the $K-$armed bandit framework.<n>Agent is allowed to play a subset of arms at each time slot instead of one arm.<n>We propose an algorithm that constructs $log K$ groups and performs a likelihood ratio test to detect the presence of the best arm.
  arXiv  Detail & Related papers  (2025-02-03T15:10:08Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible.<n>We study multi-fidelity best-arm identification, in which the can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost.<n>Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm.
  arXiv  Detail & Related papers  (2024-06-05T08:02:40Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Covariance Adaptive Best Arm Identification [0.0]
  The goal is to identify the arm with the highest mean reward with a probability of at least 1 -- $delta$, while minimizing the number of arm pulls. We propose a more flexible scenario where arms can be dependent and rewards can be sampled simultaneously. This framework is relevant in various applications, such as clinical trials, where similarities between patients or drugs suggest underlying correlations.
  arXiv  Detail & Related papers  (2023-06-05T06:57:09Z)
• Top Two Algorithms Revisited [14.783452541904365]
  Top Two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models. We provide a general analysis of Top Two methods, which identifies desirable properties of the leader, the challenger, and the (possibly non-parametric) distributions of the arms. Our proof method demonstrates in particular that the sampling step used to select the leader inherited from Thompson sampling can be replaced by other choices.
  arXiv  Detail & Related papers  (2022-06-13T09:03:24Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
  We propose a novel correlated bandit framework that captures domain knowledge about correlation between arms. We show that the total samples obtained by C-LUCB are of the form $mathcalOleft(sum_k in mathcalC logleft(frac1deltaright)$ as opposed to the typical $mathcalOleft(sum_k in mathcalC logleft(frac1deltaright)$ samples required in the independent reward setting
  arXiv  Detail & Related papers  (2021-09-10T15:41:07Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.