Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality

Kwang-Sung Jun, Chicheng Zhang

This paper introduces a novel approach to structured multi-armed bandits that challenges the traditional dominance of "optimistic" algorithms. By strategically incorporating "pessimism," the authors develop an algorithm that achieves optimal long-term performance without sacrificing efficiency in "easy" problem instances.

Introduction

In the world of multi-armed bandits, a learner tries to maximize rewards by choosing between different "arms." In structured bandits, the rewards of these arms are related (e.g., through a linear model or a shared set of hypotheses).

There are two main ways to measure success:

  1. Optimism (UCB-style): These algorithms perform well in the short term but often fail to reach "asymptotic optimality" (AO)—the theoretical limit of how well an algorithm can perform as time goes to infinity.
  2. Asymptotic Optimality: Existing AO algorithms usually rely on "forced sampling," where they occasionally pull every single arm to gather information.

The problem with forced sampling is that it acts as a blunt instrument. While it ensures the algorithm eventually finds the truth, it prevents achieving bounded regret—cases where the problem is "easy" enough that exploration should cease entirely. Furthermore, forced sampling often makes regret scale linearly with the number of arms ($K$), which is disastrous when $K$ is very large.

The CROP Algorithm

To address these limitations, the authors propose CROP (CRush Optimism with Pessimism). The core innovation lies in how it decides which arms to pull to gather information without relying on forced exploration.

Illustration of hypotheses and confidence sets used in CROP.
  • Confidence Sets: Like many bandit algorithms, CROP maintains a set of hypotheses that are consistent with the data seen so far.
  • The Pessimistic Twist: Instead of just looking at the "optimistic" hypothesis (the one with the highest reward), CROP identifies a pessimistic hypothesis—the one in the confidence set with the lowest maximum reward that isn't the current leader.
  • Informative Arm Pulls: CROP pulls arms that are "informative" according to this pessimistic hypothesis. The logic is: if we pull arms that the pessimistic hypothesis says are important, we will either confirm our current leader or quickly eliminate the pessimistic hypothesis from our confidence set.
  • Four-Branch Logic: The algorithm operates in four modes:
  • Exploit: If only one best arm is plausible, pull it.
  • Conflict: If different hypotheses suggest wildly different sampling strategies, it uses a refined confidence set to resolve the tie.
  • Feasible: If the pessimistic sampling plan covers the optimistic ones, it follows that plan.
  • Fallback: A safety net for cases that don't fit the above.

Crucially, CROP is forced-exploration-free. It only explores when the current data isn't sufficient to distinguish between competing hypotheses.

Key Insights and Results

CROP's design yields several significant theoretical and practical advantages:

  • Pessimism as a Filter: By focusing on the "pessimistic" hypothesis, the algorithm identifies the most efficient way to prune the hypothesis space. It "crushes" the optimistic view by testing the most difficult-to-disprove alternatives.
  • K-Free Regret: Because CROP avoids forced sampling, its regret doesn't necessarily depend on the total number of arms ($K$). Instead, it depends on an "effective" number of arms ($K_\psi$) required to distinguish the true hypothesis from others.
  • Asymptotic Optimality and Bounded Regret: CROP achieves a constant-factor asymptotic optimality, meaning its long-term regret matches theoretical lower bounds. Simultaneously, in "easy" instances (where the best arm is sufficiently informative), CROP's regret is $O(1)$—it eventually stops making mistakes entirely.
  • Non-Asymptotic Superiority: The authors introduce a "Cheating Code" synthetic problem class where some arms provide massive amounts of information about which other arm is the best. In this benchmark, CROP's regret scales with $\ln^2(K)$, while forced-sampling methods scale with $K$. For large $K$, this demonstrates an exponential improvement in learning speed.
  • The Oracle's Curse: A surprising insight revealed by the paper is that a "clairvoyant oracle"—an algorithm that knows the optimal long-term sampling strategy from day one—can actually suffer linear regret in the short term. This suggests that pure asymptotic optimality isn't always the best goal for practical, finite-time applications.

Limitations and Future Work

While CROP presents a significant step forward, it has limitations. The current analysis is restricted to cases where the number of possible hypotheses is finite. Extending this to infinite or continuous spaces (like general linear bandits) remains an open challenge. Additionally, finding the pessimistic hypothesis and the optimal sampling allocation can be computationally expensive, as the paper focuses primarily on statistical limits rather than algorithmic efficiency. Finally, guaranteeing that CROP will always perform at least as well as a standard UCB algorithm in every single instance (a property called "sub-UCB" performance) remains an open problem in the field.

Summary updated

Abstract

We study stochastic structured bandits for minimizing regret. The fact that the popular optimistic algorithms do not achieve the asymptotic instance-dependent regret optimality (asymptotic optimality for short) has recently alluded researchers. On the other hand, it is known that one can achieve bounded regret (i.e., does not grow indefinitely with $n$) in certain instances. Unfortunately, existing asymptotically optimal algorithms rely on forced sampling that introduces an $\omega(1)$ term w.r.t. the time horizon $n$ in their regret, failing to adapt to the ``easiness'' of the instance. In this paper, we focus on the finite hypothesis case and ask if one can achieve the asymptotic optimality while enjoying bounded regret whenever possible. We provide a positive answer by introducing a new algorithm called CRush Optimism with Pessimism (CROP) that eliminates optimistic hypotheses by pulling the informative arms indicated by a pessimistic hypothesis. Our finite-time analysis shows that CROP $(i)$ achieves a constant-factor asymptotic optimality and, thanks to the forced-exploration-free design, $(ii)$ adapts to bounded regret, and $(iii)$ its regret bound scales not with $K$ but with an effective number of arms $K_\psi$ that we introduce. We also discuss a problem class where CROP can be exponentially better than existing algorithms in \textit{nonasymptotic} regimes. This problem class also reveals a surprising fact that even a clairvoyant oracle who plays according to the asymptotically optimal arm pull scheme may suffer a linear worst-case regret.
BibTeX
@inproceedings{jun2020crush,
  author = {Kwang-Sung Jun and Chicheng Zhang},
  title = {{Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=S_b-TgyugWq},
}
Figure