An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem

Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan

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:
    1. 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.

Table comparing regret bounds of fully adaptive, standard batched, and the proposed C2B algorithm.

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

Abstract

We study the $K$-armed dueling bandit problem, a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the fully adaptive setting, where the algorithm can make updates after every comparison. The "batched" dueling bandit problem is motivated by large-scale applications like web search ranking and recommendation systems, where performing sequential updates may be infeasible. In this work, we ask: is there a solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for $K$-armed dueling bandits? We answer this in the affirmative under the Condorcet condition, a standard setting of the $K$-armed dueling bandit problem. We obtain asymptotic regret of $O(K^2\log^2(K))$ + $O(K\log(T))$ in $O(\log(T))$ rounds, where $T$ is the time horizon. Our regret bounds nearly match the best regret bounds known in the fully sequential setting under the Condorcet condition. Finally, in computational experiments over a variety of real-world datasets, we observe that our algorithm using $O(\log(T))$ rounds achieves almost the same performance as fully sequential algorithms (that use $T$ rounds).
BibTeX
@inproceedings{agarwal2022asymptotically,
  author = {Arpit Agarwal and Rohan Ghuge and Viswanath Nagarajan},
  title = {{An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=u6GIDyHitzF},
}
Figure