Best of Both Worlds Model Selection
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.