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:
- 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.
- 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.
- 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:
- Each player picks an arm based on their own internal MAB strategy.
- The learner duels these two arms.
- 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.
- 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