The Pareto Frontier of model selection for general Contextual Bandits
  Recent progress in model selection raises the question of the fundamental
limits of these techniques. Under specific scrutiny has been model selection
for general contextual bandits with nested policy classes, resulting in a
COLT2020 open problem. It asks whether it is possible to obtain simultaneously
the optimal single algorithm guarantees over all policies in a nested sequence
of policy classes, or if otherwise this is possible for a trade-off
$\alpha\in[\frac{1}{2},1)$ between complexity term and time:
$\ln(|\Pi_m|)^{1-\alpha}T^\alpha$. We give a disappointing answer to this
question. Even in the purely stochastic regime, the desired results are
unobtainable. We present a Pareto frontier of up to logarithmic factors
matching upper and lower bounds, thereby proving that an increase in the
complexity term $\ln(|\Pi_m|)$ independent of $T$ is unavoidable for general
policy classes. As a side result, we also resolve a COLT2016 open problem
concerning second-order bounds in full-information games.
