Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality

Kwang-Sung Jun, Chicheng Zhang

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 nonasymptotic regimes.

Introduction

In structured multi-armed bandit problems, the rewards of different arms are linked through a shared structure (e.g., linear relationships or shared parameters). The objective is to minimize cumulative regret—the difference between the rewards obtained and those of the optimal arm. Traditional approaches generally fall into two categories: optimistic algorithms (like UCB), which are robust but often fail to reach the theoretical limit of efficiency (asymptotic optimality), and asymptotically optimal (AO) algorithms, which hit these limits but typically rely on "forced sampling."

Forced sampling requires occasionally pulling every arm to ensure no sub-optimal arm is overlooked. However, this approach is inefficient in "easy" problems where an intelligent algorithm should eventually stop making errors, achieving bounded regret. Furthermore, forced sampling causes regret to scale linearly with the number of arms ($K$), a significant drawback for large-scale applications with thousands or millions of options.

The CROP Algorithm

To address these limitations, we propose CROP (CRush Optimism with Pessimism). Instead of uniform forced sampling, CROP utilizes a pessimistic hypothesis to guide exploration surgically.

Mechanism

  1. Confidence Set Maintenance: The algorithm maintains a set of hypotheses $\mathcal{F}$ consistent with observed data.
  2. Identifying Optimism and Pessimism: It identifies the "optimistic" hypothesis (promising the highest reward) and a "pessimistic" hypothesis (a plausible hypothesis suggesting the lowest reward for the current best arm).
  3. Informative Arm Pulls: CROP pulls "informative arms" identified by the pessimistic hypothesis to either invalidate the optimistic hypothesis or confirm the pessimistic one as the truth.
  4. Elimination of Forced Sampling: By pulling only statistically informative arms, CROP avoids the $\omega(1)$ regret term associated with forced sampling, allowing it to adapt to the instance's difficulty.
Figure 1: (a) Mean reward curves for various hypotheses. (b) Relationship between hypothesis sets: optimistic ($\mathcal{O}^*$), pessimistic ($\mathcal{P}^*$), consistent ($\mathcal{C}^*$), and the true hypothesis $f^*$.

Problem Classes and Evaluation

We evaluate CROP using specific mathematical problem classes designed to test adaptability and efficiency.

  • The "Staircase" Example: Demonstrates scenarios where standard Empirical Risk Minimization (ERM) fails by getting trapped in sub-optimal arm pulls indefinitely.
  • The "Cheating Code" Example: A scenario where specific arms provide disproportionate information about the optimal arm. In this class, CROP can be exponentially more efficient than forced-sampling algorithms.
Table 1: A structured reward matrix where arm rewards (A1-A5) are correlated across hypotheses ($f_1-f_4$), allowing for efficient information gathering.

Theoretical Contributions and Results

CROP provides several key theoretical advantages over state-of-the-art methods:

  • Asymptotic Optimality: It achieves the theoretical lower bound of regret within a constant factor.
  • Bounded Regret: In "easy" instances where the optimal arm is sufficiently informative, CROP’s regret stops growing entirely, whereas forced-sampling algorithms continue to accumulate regret linearly with time.
  • $K$-free Regret Bound: Regret scales with an "effective number of arms" ($K_\psi$) rather than the total number of arms ($K$). In the "Cheating Code" scenario, this results in a scale of $(\ln K)^2$ versus the linear $K$ scaling of traditional AO algorithms.
  • The $\ln \ln n$ Necessity: We prove that a $\ln \ln n$ term in the regret bound is a mathematical requirement for any algorithm that achieves bounded regret without forced sampling while remaining "uniformly good."

Conclusion

CROP bridges the gap between optimism and asymptotic optimality by replacing blind exploration with targeted, pessimistic-guided sampling. While currently focused on finite hypothesis classes, CROP demonstrates that it is possible to achieve asymptotic optimality while adapting to the inherent "easiness" of a problem. Future work includes extending this framework to infinite or continuous hypothesis classes and optimizing the computational overhead of finding the pessimistic hypothesis.

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