Introduction
In sequential decision-making, a "bandit" learner faces two major sources of uncertainty. First, the environment type: is the world stochastic (where rewards follow a fixed distribution) or adversarial (where rewards are chosen by an opponent)? Stochastic environments allow for fast, logarithmic regret, while adversarial ones require cautious $\sqrt{T}$ strategies. Second, the model complexity: what is the right hypothesis class? Choosing a model that is too simple leads to bias and mis-specification, while choosing one that is too complex leads to high variance and slow learning.
While previous research has addressed these problems individually through "Best of Both Worlds" (BoBW) algorithms for environment adaptation and model selection for complexity adaptation, combining them has proven notoriously difficult. This paper bridges that gap by introducing Arbe (Adversarial Regret Balancing and Elimination), the first model selection framework for contextual bandits that provides BoBW guarantees with high probability.
The Challenge of Simultaneous Adaptation
Standard model selection tools designed for adversarial settings, such as the CORRAL algorithm, often fail to achieve the fast learning rates needed for stochastic settings. A major hurdle is that in adversarial environments, an algorithm can occasionally achieve "negative regret"—performing better than the best fixed policy for a short stretch. This anomaly causes standard elimination tests to fail, as a complex model might temporarily appear superior to a well-specified simple model purely by chance. Furthermore, most existing meta-algorithms only offer guarantees "in expectation," leaving them vulnerable to worst-case random realizations.
Methodology: The Arbe Framework
To overcome these challenges, the authors propose a meta-algorithm built on several innovative mechanisms:
Regret Balancing
The meta-learner maintains a pool of $M$ base learners, each assigned to a different nested policy class (e.g., linear models of increasing dimensions $d_1 < d_2 < \dots < d_M$). It plays each base learner according to a specific probability schedule designed to keep their "candidate" regret bounds balanced. If a learner is theoretically sound, its regret is constrained from growing faster than a specific rate.
Elimination and "Linking"
Arbe continuously monitors the performance of these learners. If a low-complexity learner performs significantly worse than a high-complexity one, it is eliminated as mis-specified. To solve the "negative regret" problem, the authors introduce a novel Linking mechanism. Lower-level learners are given the option to follow the actions of higher-level learners. This prevents the meta-algorithm from accidentally discarding a perfectly good, simple model just because a complex model had a lucky streak in an adversarial setting.
Arbe-Gap for Stochastic Exploitation
To achieve BoBW guarantees, the framework incorporates a gap-detection subroutine. If the algorithm detects a clear "winner" policy with a performance gap ($\Delta$), it seamlessly switches to an exploitation phase, allowing it to achieve logarithmic regret in benign environments.
Key Insights and Theoretical Results
This is a purely theoretical work focused on proving regret bounds and algorithmic convergence. The authors establish several foundational insights for the field:
- The Inevitable Cost of Stochastic Model Selection: The authors prove a lower bound demonstrating that in stochastic environments, it is impossible to achieve a regret bound that depends only on the complexity of the optimal class ($d_{i^*}$). The learner must pay a penalty related to the largest class in the pool ($d_M$). This clarifies why perfect model selection is fundamentally harder in the stochastic BoBW setting.
- High-Probability Stability (h-stability): Arbe moves beyond "in expectation" guarantees by defining a stricter requirement for base learners called h-stability, ensuring the algorithm remains robust even under worst-case random realizations.
Performance Guarantees
The Arbe framework achieves simultaneous guarantees without requiring the user to specify the environment type:
- Adversarial Performance: Arbe recovers the performance of state-of-the-art adversarial model selection but with high-probability guarantees. For linear bandits, the regret scales roughly as $\tilde{O}(d_i^2 \sqrt{T})$, where $d_i$ is the dimension of the best-fitting model.
- Stochastic Performance: When the environment is stochastic with a gap $\Delta$, the algorithm achieves logarithmic regret scaling as $\tilde{O}(\frac{R(\Pi_M)^2}{\Delta} \log T)$.
Limitations and Future Directions
While Arbe represents a significant theoretical leap, the current regret bounds exhibit a polynomial dependence on the number of base learners ($M$) and complexity terms, which the authors suggest could be optimized. Additionally, running $M$ base learners in parallel with complex importance-sampling updates can be computationally expensive for very large policy classes. A promising future direction is adapting the Arbe framework to handle "adversarially corrupted" stochastic rewards, providing a robust middle ground between the two extremes studied in this work.
Summary updated