Introduction
This paper introduces C2B (Catching the Condorcet winner in Batches), the first algorithm for the $K$-armed dueling bandit problem that achieves asymptotically optimal regret using only a logarithmic number of adaptive rounds. By bridging the gap between fully sequential and batched learning, the authors demonstrate that models do not need to be updated after every single user interaction to maintain state-of-the-art performance in large-scale ranking and recommendation systems.
The Batched Dueling Bandit Problem
In the traditional multi-armed bandit problem, an agent pulls an arm and receives a numerical reward. However, in many real-world scenarios—such as web search ranking or movie recommendations—it is much easier to obtain pairwise preferences (e.g., "User clicked Result A over Result B") than absolute scores. This formulation is known as the dueling bandit problem.
Most existing algorithms for this problem are "fully adaptive," meaning they update their strategy after every single duel. In massive systems, like a search engine handling thousands of queries per second, updating a model with such high frequency is computationally infeasible. Instead, these systems operate in batches: they commit to a set of comparisons, collect data in parallel, and only then update the model for the next round.
The central challenge addressed by this paper is: Can we achieve the same low "regret" (the loss incurred compared to always picking the best arm) with only a few batches as we can with full adaptivity?
The C2B Algorithm
The authors propose the C2B algorithm, which operates under the Condorcet condition. This standard assumption posits that there is one "best" arm ($a^*$) that is likely to beat any other arm in a head-to-head duel.
Key components of the C2B methodology include:
- The "Anchor" Strategy: Instead of comparing every arm against every other arm (which is computationally expensive), C2B attempts to identify a "candidate" champion in each round.
- Defeated Sets: The algorithm maintains a set of arms that a candidate has "defeated" with high statistical confidence.
- Two-Tiered Comparisons:
- If an arm is already defeated by the current candidate, it is only compared against that candidate (acting as an "anchor") to refine the estimate.
- If an arm is not yet defeated, it is compared against all active arms. This "safety net" ensures that if the current candidate isn't actually the best arm, the true Condorcet winner ($a^*$) will eventually be discovered and "trapped."
- Elimination: Arms are permanently removed from the active set once they are statistically proven to be inferior to another arm.
Key Insights
- Logarithmic Rounds are Sufficient: The most significant insight is that only $O(\log T)$ rounds (where $T$ is the total number of duels) are needed to match the performance of an algorithm that updates $T$ times. This is a massive win for system architecture and latency constraints.
- Robustness of the Condorcet Winner: The algorithm relies on the idea that once the true winner $a^*$ is "trapped" as the candidate, it stays there. The "safety net" of comparing non-defeated arms against everyone else prevents the algorithm from getting stuck with a sub-optimal "champion" for too long.
- Smooth Trade-off: The paper provides a framework where practitioners can trade off the number of batches ($B$) against the expected regret, allowing them to choose a batch size that fits their specific latency constraints.
Key Results
Theoretical Optimality
C2B achieves a regret bound of $O(K^2 \log^2 K + K \log T)$ using $O(\log T)$ rounds. This nearly matches the best-known bounds for fully sequential algorithms, proving that batched execution does not inherently sacrifice long-term performance.
Empirical Performance
The authors evaluated C2B against several real-world datasets that provide pairwise preference matrices, including retrieval functions from ArXiv.org, Sushi preferences, Irish Election data, and subsets of the Microsoft (MSLR30) and Yahoo! (Yahoo30) Learning to Rank datasets.
In simulations, C2B (using only $\log T$ batches) performed almost identically to state-of-the-art sequential algorithms like RMED and RUCB, and significantly outperformed previous batched approaches like SCOMP2. The experiments showed that adding just a few extra rounds (e.g., $\log T + 6$) allowed C2B to match the performance of fully adaptive models even on complex, large-scale datasets like Yahoo30.
Limitations and Future Work
- The Condorcet Assumption: The algorithm strictly requires a Condorcet winner to exist. In "rock-paper-scissors" scenarios (cyclic preferences), such a winner doesn't exist, and the algorithm's guarantees may not hold.
- Future Directions: The authors suggest extending this batched approach to more general winner definitions, such as the Copeland winner (the arm that beats the most other arms) or the von Neumann winner, which can naturally handle cycles in preferences.
- Parameter Tuning: Like many bandit algorithms, performance can be sensitive to the choice of confidence intervals, though the authors successfully used standard KL-divergence-based bounds in their empirical evaluations.
Summary updated