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
- Confidence Set Maintenance: The algorithm maintains a set of hypotheses $\mathcal{F}$ consistent with observed data.
- 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).
- 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.
- 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.
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.
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