Beyond UCB: Optimal and Efficient Contextual Bandits with Regression
  Oracles
  A fundamental challenge in contextual bandits is to develop flexible,
general-purpose algorithms with computational requirements no worse than
classical supervised learning tasks such as classification and regression.
Algorithms based on regression have shown promising empirical success, but
theoretical guarantees have remained elusive except in special cases. We
provide the first universal and optimal reduction from contextual bandits to
online regression. We show how to transform any oracle for online regression
with a given value function class into an algorithm for contextual bandits with
the induced policy class, with no overhead in runtime or memory requirements.
We characterize the minimax rates for contextual bandits with general,
potentially nonparametric function classes, and show that our algorithm is
minimax optimal whenever the oracle obtains the optimal rate for regression.
Compared to previous results, our algorithm requires no distributional
assumptions beyond realizability, and works even when contexts are chosen
adversarially.
