  A major challenge in contextual bandits is to design general-purpose
algorithms that are both practically useful and theoretically well-founded. We
present a new technique that has the empirical and computational advantages of
realizability-based approaches combined with the flexibility of agnostic
methods. Our algorithms leverage the availability of a regression oracle for
the value-function class, a more realistic and reasonable oracle than the
classification oracles over policies typically assumed by agnostic methods. Our
approach generalizes both UCB and LinUCB to far more expressive possible model
classes and achieves low regret under certain distributional assumptions. In an
extensive empirical evaluation, compared to both realizability-based and
agnostic baselines, we find that our approach typically gives comparable or
superior results.
