Research map / Bandits and online learning / Multi-armed bandits

The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Best-arm identification in linear bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies Condorcet winner identification in dueling bandits using the full gap matrix, giving elimination-based fixed-budget and fixed-confidence algorithms with instance-dependent upper bounds and new high-probability and expected lower bounds.

Problem

Identifying the Condorcet winner in stochastic dueling bandits under only the existence of a CW; the optimal instance-dependent sample complexity (especially high-probability budget) is poorly understood.

Approach

Exploit the full skew-symmetric gap matrix rather than only the CW row: for each arm, search (via sequential halving) for a strong negative opponent and estimate a lower-tail quantile of its row via a new adaptive Range-Quantile routine; eliminate a constant fraction of arms per round, with a certification step. Yields an exploration/certification trade-off bound and matching-type lower bounds.

Key results

• Upper bound: with probability at least 1-delta, FC-CWI budget is at most min of H_cw(delta) and min over s of [H_certify + H_explore^(1)] log(1/delta) + H_explore^(0), up to log factors.
• Expected-budget lower bound: E[N_delta] >= (1/4) sum_{i!=i*} log(1/(4delta))/Delta_{i,(1)}^2 for any delta-correct algorithm, matching the asymptotic upper bound of prior verification approach.
• Lower bound on (1-delta)-quantile of budget reduces to exploration plus certification cost, shown to be unavoidable in a local minimax sense.

Surprising findings

• The expected budget can be much smaller than the (1-delta)-quantile of the budget when gaps are heterogeneous, so expectation-based analyses are overly optimistic.
• Under the fixed-probability regime, an additive term of order K^2 can dominate the sample complexity when effective sparsities are small.

Limitations

• Upper bounds hide logarithmic factors and numerical constants (c_0 not made explicit).
• Upper and lower bounds do not match in hybrid regimes where the CW is strongest for some arms and nearly tied with others.
• Fully instance-dependent lower bound for the (1-delta)-quantile of the budget remains open.

Experimental setup

Metrics: sample complexity (budget) error probability

Baselines: verification-based CW identification H_cw direct-search algorithm

Builds on: Sequential Halving Condorcet winner identification verification approach testification

Closest papers by meaning

• On Weak Regret Analysis for Dueling Bandits (NeurIPS 2024 · similarity 0.90)
• Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.89)
• Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.89)
• Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.89)
• Near Optimal Best Arm Identification for Clustered Bandits (ICML 2025 · similarity 0.89)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.89)