Best of Both Worlds Model Selection

Aldo Pacchiano, Christoph Dann, Claudio Gentile

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:

  1. 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.
  2. 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

Abstract

We study the problem of model selection in bandit scenarios in the presence of nested policy classes, with the goal of obtaining simultaneous adversarial and stochastic (``best of both worlds") high-probability regret guarantees. Our approach requires that each base learner comes with a candidate regret bound that may or may not hold, while our meta algorithm plays each base learner according to a schedule that keeps the base learner's candidate regret bounds balanced until they are detected to violate their guarantees. We develop careful mis-specification tests specifically designed to blend the above model selection criterion with the ability to leverage the (potentially benign) nature of the environment. We recover the model selection guarantees of the CORRAL algorithm for adversarial environments, but with the additional benefit of achieving high probability regret bounds. More importantly, our model selection results also hold simultaneously in stochastic environments under gap assumptions. These are the first theoretical results that achieve best-of-both world (stochastic and adversarial) guarantees while performing model selection in contextual bandit scenarios.
BibTeX
@inproceedings{pacchiano2022best,
  author = {Aldo Pacchiano and Christoph Dann and Claudio Gentile},
  title = {{Best of Both Worlds Model Selection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=FMgvuOeM6Kw},
}
Figure