Best of Both Worlds Model Selection

Aldo Pacchiano, Christoph Dann, Claudio Gentile

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, specifically in the case of nested adversarial linear bandits. 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 (linear) bandit scenarios.

Introduction

In sequential decision-making, the linear bandit framework is a powerful tool for balancing exploration and exploitation. However, practitioners often face two distinct uncertainties: the complexity of the model (model selection) and the nature of the environment (stochastic vs. adversarial). Traditionally, algorithms are optimized for one or the other. This paper presents a unified meta-algorithm that achieves "Best of Both Worlds" (BOBW) performance while simultaneously performing model selection across nested policy classes.

The Dual Challenge: Model Selection and BOBW

Model selection in bandits involves identifying the optimal complexity—such as the true dimensionality of a feature vector—without prior knowledge. If an algorithm assumes a model that is too simple (underfitting), it suffers from bias; if it assumes one that is too complex (overfitting), it suffers from excessive variance.

Simultaneously, the environment may be stochastic (rewards follow a fixed distribution) or adversarial (rewards are chosen by an opponent). While stochastic environments allow for logarithmic regret, adversarial environments typically necessitate square-root regret. A BOBW algorithm adapts to whichever reality it encounters. Combining these two challenges with high-probability guarantees (rather than just expected values) is a significant theoretical hurdle.

The Arbe Framework

The authors introduce Arbe (Adversarial Regret Balancing and Elimination), a meta-algorithm designed to manage a suite of $M$ base learners, each corresponding to a nested policy class (e.g., increasing dimensions $d_1 \subset d_2 \subset \dots \subset d_M$).

1. Regret Balancing and Elimination

Arbe does not simply pick a single base learner. Instead, it employs a scheduling mechanism that balances the candidate regret bounds of all active learners. This ensures that no model is discarded prematurely. The algorithm continuously runs mis-specification tests; if a base learner's observed performance violates its theoretical regret guarantee, it is eliminated from the pool.

2. Linking Nested Learners

A key innovation is the "linking" of learners. Because the policy classes are nested, a lower-complexity learner can "follow" the actions of a higher-complexity one. This prevents simpler models from being unfairly penalized or eliminated due to the superior exploratory actions of more complex models.

3. Arbe-Gap for Stochastic Environments

To achieve optimal performance in stochastic settings, the authors extend the framework into Arbe-Gap. This version includes a two-phase strategy:

  • Identification Phase: The algorithm monitors the rewards to identify a candidate optimal policy and estimate the suboptimality gap ($\Delta$).
  • Exploitation Phase: Once the gap is sufficiently estimated, the algorithm transitions to an exploitation-heavy mode to achieve the logarithmic regret characteristic of stochastic environments.

Key Theoretical Insights

The Price of Ignorance

A significant contribution of this work is the "no-free-lunch" result established in Theorem 6. The authors prove that any algorithm performing model selection in both stochastic and adversarial worlds must pay a price: the stochastic regret will inevitably depend on the complexity of the largest possible model ($d_M$), even if the environment actually conforms to a much smaller model ($d_{i^*}$).

High-Probability Guarantees

Unlike many existing BOBW results that hold only in expectation, Arbe provides high-probability bounds. This requires ensuring "h-stability"—a property that keeps the algorithm stable even when it receives feedback only intermittently due to the meta-algorithm's scheduling.

Results and Performance

The proposed framework achieves the following:

  • Adversarial Regret: In adversarial settings, the regret scales with $poly(d_{i^*}) \sqrt{T}$, where $d_{i^*}$ is the true complexity. This demonstrates successful model selection, as the regret does not scale with the maximum complexity $d_M$.
  • Stochastic Regret: In stochastic settings with a gap $\Delta$, the pseudo-regret scales as $poly(d_M) \frac{\log T}{\Delta}$, matching the optimal logarithmic rate.

Limitations and Future Directions

While this work represents the first simultaneous BOBW and model selection guarantee for linear bandits, several areas for improvement remain:

  • Dependency on M: The current bounds have a polynomial dependence on the number of base learners ($M$). Reducing this to a logarithmic dependence is a key goal for future research.
  • Computational Complexity: Running multiple base learners and mis-specification tests in parallel increases the computational burden.
  • Action Space Constraints: The current theory applies to specific "extendable" action spaces; generalizing these results to arbitrary action sets is an open problem.

Conclusion

By blending adversarial regret balancing with sophisticated mis-specification testing, the Arbe framework bridges the gap between model selection and environment adaptation. It provides a robust theoretical foundation for deploying bandit algorithms in unpredictable, real-world scenarios where neither the model complexity nor the environment type is known in advance.

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, specifically in the case of nested adversarial linear bandits. 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 (linear) 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