Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences

Aadirupa Saha, Pierre GaillardICML 2022 · OpenReview

In the world of online learning, algorithms often have to choose between two extremes: a stable, predictable environment (stochastic) or a chaotic, ever-changing one (adversarial). For years, researchers in the Dueling Bandits (DB) subfield—where a learner chooses pairs of items and only observes which one is preferred—had to pick a side. Algorithms designed for one world usually failed miserably in the other.

A recent paper by Aadirupa Saha and Pierre Gaillard introduces a "best-of-both-worlds" framework that performs optimally regardless of the environment, finally closing a decade-long gap in dueling bandit theory.

The Core Challenge: Absolute Rewards vs. Relative Preferences

Standard Multi-Armed Bandits (MAB) deal with absolute rewards (e.g., "Item A yielded a reward of 0.7"). Dueling Bandits, however, deal with relative preferences (e.g., "Item A is preferred over Item B"). This type of feedback is often much easier to collect in the real world—think of a streaming service asking "Which of these two movies would you rather watch?" instead of asking for a precise star rating.

The authors tackle three primary challenges in this domain:

  1. The Environment Gap: Most DB algorithms are highly specialized. Stochastic algorithms assume fixed preference probabilities but fail if preferences change over time. Adversarial algorithms handle change but fail to exploit the structure of stable environments to achieve faster learning.
  2. Suboptimal Regret: Even in the well-studied stochastic setting, existing algorithms for finding the Condorcet winner (an arm that beats every other arm) had suboptimal dependencies on the number of arms ($K$) or the "gap" between the best and second-best arms.
  3. Corruption Sensitivity: Real-world feedback is often noisy or maliciously tampered with. Most DB algorithms are not designed to handle such "adversarial corruptions."

A Novel Reduction: From DB to MAB

The paper's breakthrough is a surprisingly elegant reduction from Dueling Bandits to Multi-Armed Bandits.

Instead of treating the dueling bandit as a single complex problem, the authors split it into two independent MAB "players." In each round:

  1. Each player picks an arm based on their own internal MAB strategy.
  2. The learner duels these two arms.
  3. The outcome (which arm won) is fed back to both players as a "loss."

By using Online Mirror Descent (OMD) with a Tsallis regularizer (specifically the Tsallis-INF algorithm) as the underlying MAB engine for these players, they create Versatile-DB (VDB). This specific MAB algorithm is known for its "best-of-both-worlds" properties, and the authors prove that their reduction allows VDB to inherit these exact properties for the dueling bandit setting.

Key Insights and Theoretical Milestones

  • Simplicity is Power: The reduction demonstrates that we do not necessarily need specialized, complex dueling bandit algorithms. We can effectively "piggyback" on decades of progress made in the standard MAB field.
  • Closing the Condorcet Gap: Their analysis yields an instance-optimal regret bound of $O(\sum_{i=1}^K \frac{\log T}{\Delta_i})$. This is a major theoretical milestone, as it matches known lower bounds and removes the suboptimal $K^2$ or $\Delta^{-2}$ dependencies found in previous state-of-the-art methods.
  • Self-Bounding Property: The mathematical mechanism that allows the algorithm to adapt to the environment is a self-bounding constraint. In stochastic settings, the algorithm's regret naturally bounds itself more tightly, leading to logarithmic regret instead of the square-root regret seen in adversarial settings.

Empirical Results

The authors evaluated their algorithms using several synthetic and real-world preference benchmarks, including synthetic BTL models of varying difficulty (Trivial, Easy, Medium, Hard) and real-world matrices (Car and Hurdy).

The empirical results strongly support the theory. VDB consistently outperforms existing state-of-the-art algorithms like RUCB, RMED, and Double Thompson Sampling (DTS) across all tested scenarios.

Averaged cumulative regret over time for various stochastic environments. VDB (magenta line) consistently achieves the lowest regret across synthetic and real-world datasets.
  • Adversarial Performance: VDB achieves the optimal $O(\sqrt{KT})$ regret.
  • Stochastic Performance: It achieves the optimal $O(\sum_{i=1}^K \frac{\log T}{\Delta_i})$ regret, converging faster than competitors in stable environments.
  • Robustness: In experiments with corrupted feedback, VDB's performance decayed the least, maintaining its lead over other baselines.

Limitations and Future Directions

While the paper provides a major leap forward, there are a few areas for further exploration. The current "best-of-both-worlds" analysis applies to pseudo-regret (expected regret). Achieving similar high-probability bounds for both worlds simultaneously remains a difficult open problem. Additionally, while theoretically efficient, running two MAB instances and performing OMD updates might be slightly more computationally intensive than simpler heuristic-based DB algorithms in very large-scale applications.

Ultimately, this reduction idea could be extended to more complex scenarios like dueling bandits with "sleeping" arms, delayed feedback, or even full reinforcement learning settings, opening exciting new avenues for preference-based learning.

Summary updated

Abstract

We study the problem of $K$-armed dueling bandit for both stochastic and adversarial environments, where the goal of the learner is to aggregate information through relative preferences of pair of decision points queried in an online sequential manner. We first propose a novel reduction from any (general) dueling bandits to multi-armed bandits which allows us to improve many existing results in dueling bandits. In particular, we give the first best-of-both world result for the dueling bandits regret minimization problem—a unified framework that is guaranteed to perform optimally for both stochastic and adversarial preferences simultaneously. Moreover, our algorithm is also the first to achieve an optimal $O(\sum_{i = 1}^K \frac{\log T}{\Delta_i})$ regret bound against the Condorcet-winner benchmark, which scales optimally both in terms of the arm-size $K$ and the instance-specific suboptimality gaps $\{\Delta_i\}_{i = 1}^K$. This resolves the long standing problem of designing an instancewise gap-dependent order optimal regret algorithm for dueling bandits (with matching lower bounds up to small constant factors). We further justify the robustness of our proposed algorithm by proving its optimal regret rate under adversarially corrupted preferences—this outperforms the existing state-of-the-art corrupted dueling results by a large margin. In summary, we believe our reduction idea will find a broader scope in solving a diverse class of dueling bandits setting, which are otherwise studied separately from multi-armed bandits with often more complex solutions and worse guarantees. The efficacy of our proposed algorithms are empirically corroborated against state-of-the art dueling bandit methods.
BibTeX
@inproceedings{saha2022versatile,
  author = {Aadirupa Saha and Pierre Gaillard},
  title = {{Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=VkERxWG0Ik},
}
Figure