Beat the Mean Bandit

Yisong Yue, Thorsten JoachimsICML 2011 · OpenReview

TL;DR

This paper introduces Beat-the-Mean (BtM), a robust algorithm for the "Dueling Bandits" problem—a scenario where a learner must find the best option using only noisy pairwise comparisons rather than absolute scores. Unlike previous methods, BtM works even when human preferences violate "strong transitivity" (e.g., if you prefer A over B and B over C, you don't necessarily prefer A over C by a massive margin), offering significantly lower variance and stronger theoretical guarantees.

What Problem Does This Paper Address?

In traditional Multi-Armed Bandit (MAB) problems, an algorithm pulls a lever and receives a numerical reward (like a 5-star rating). However, in many real-world applications like search engines or recommender systems, absolute rewards are hard to elicit. Users are much better at providing pairwise preferences: "I like Result A better than Result B."

The Dueling Bandits Problem formalizes this setting. The challenge is that previous algorithms relied on a strict mathematical assumption called "Strong Stochastic Transitivity." In plain English, this assumes that if A is slightly better than B, and B is slightly better than C, then A must be much better than C.

Real-world data shows that humans are messy—we often violate these strict transitive rules. Previous algorithms like the "Interleaved Filter" (IF) become unstable or highly inefficient when these assumptions break down.

Pairwise preference matrix from ArXiv.org search data, illustrating real-world transitivity violations.

Methods

The authors propose the Beat-the-Mean (BtM) algorithm. Its core philosophy is a shift in how "quality" is measured:

  1. The "Mean" Benchmark: Instead of picking one "champion" bandit and pitting everyone against it (which is risky if the champion is a fluke), BtM maintains a "working set" of active candidates.
  2. Elimination Rounds: In each round, a bandit is compared against a randomly selected opponent from the current working set. This effectively compares the bandit against the average (mean) performance of the group.
  3. Confidence Intervals: The algorithm tracks how often a bandit "beats the mean." If a bandit’s empirical win rate falls significantly below the best-performing bandit (outside a calculated confidence radius), it is eliminated.
  4. Relaxed Transitivity: The authors introduce a parameter $\gamma$ to account for transitivity violations. This allows the algorithm to "degrade gracefully"—it might take longer to find the winner if the preferences are highly inconsistent, but it won't fail catastrophically.

The paper provides two versions of the algorithm: one for the Online Setting (minimizing "regret" while learning) and one for the PAC Setting (finding the best arm with high confidence using the fewest possible comparisons).

Datasets

The paper primarily uses simulated environments grounded in real-world data:

  • ArXiv.org Search Data: The authors used data from six retrieval functions on ArXiv.org to estimate real-world preference probabilities. This data explicitly showed that strong transitivity is often violated in practice (specifically, they found a relaxation factor of $\gamma = 1.5$).
  • Synthetic Transitivity Violations: They created scenarios where preferences were intentionally "noisy" or followed a logistic model to test the limits of the algorithm's robustness.

Key Insights and Ideas

  • Stability through Averaging: By comparing candidates against the "mean" of the active set rather than a single leader, the algorithm avoids the "high variance" trap. If a previous leader was just lucky, BtM won't be fooled as easily as older methods.
  • High-Probability vs. Expectation: Previous bounds for Dueling Bandits were often "in expectation," meaning they worked on average but could fail badly in individual runs. BtM provides "high-probability" bounds, ensuring consistent performance.
  • The $\gamma$ Factor: Recognizing that transitivity is a spectrum, not a binary, allows for a more realistic theoretical framework. The algorithm's complexity scales with the degree of "messiness" in the preference data.

Key Results

  • Robustness: In simulations where transitivity was violated, the previous state-of-the-art (Interleaved Filter) showed "super-linear" regret—meaning it got worse at an accelerating rate. BtM remained stable and linear.
  • Lower Variability: BtM demonstrated orders-of-magnitude lower variance than Interleaved Filter. In practical terms, this means BtM is much more predictable and reliable for production systems.
  • Theoretical Superiority: The authors proved that BtM matches the performance of previous algorithms in ideal settings but offers a $O(K \log T)$ regret bound that holds even under relaxed assumptions.
Regret comparisons showing BtM's stability and lower variance across varying numbers of bandits and relaxation parameter $\gamma$.

Limitations and Future Work

  • Dependence on $\gamma$: The theoretical regret bounds have a somewhat high dependence on the relaxation parameter (scaling with $\gamma^7$ or $\gamma^8$). The authors acknowledge this might be a loose bound and suggest that tighter analysis could improve this.
  • Computational Complexity: While the sample complexity is optimized, maintaining the working set and performing random pairings requires careful bookkeeping as the number of "bandits" ($K$) grows very large.
  • Non-Stationary Preferences: The paper assumes preferences are time-stationary (they don't change). A natural next step would be adapting BtM for environments where user tastes evolve over time.

Summary updated

Abstract

The Dueling Bandits Problem is an online learning framework in which actions are restricted to noisy comparisons between pairs of strategies (also called bandits). It models settings where absolute rewards are difficult to elicit but pairwise preferences are readily available. In this paper, we extend the Dueling Bandits Problem to a relaxed setting where preference magnitudes can violate transitivity. We present the first algorithm for this more general Dueling Bandits Problem and provide theoretical guarantees in both the online and the PAC settings. We also show that the new algorithm has stronger guarantees than existing results even in the original Dueling Bandits Problem, which we validate empirically.
BibTeX
@inproceedings{yue2011beat,
  author = {Yisong Yue and Thorsten Joachims},
  title = {{Beat the Mean Bandit}},
  booktitle = {International Conference on Machine Learning},
  year = {2011},
  url = {https://openreview.net/forum?id=HkVzjiZuWr},
}
Figure