  A central problem in sequential decision making is to develop algorithms that
are practical and computationally efficient, yet support the use of flexible,
general-purpose models. Focusing on the contextual bandit problem, recent
progress provides provably efficient algorithms with strong empirical
performance when the number of possible alternatives ("actions") is small, but
guarantees for decision making in large, continuous action spaces have remained
elusive, leading to a significant gap between theory and practice. We present
the first efficient, general-purpose algorithm for contextual bandits with
continuous, linearly structured action spaces. Our algorithm makes use of
computational oracles for (i) supervised learning, and (ii) optimization over
the action space, and achieves sample complexity, runtime, and memory
independent of the size of the action space. In addition, it is simple and
practical. We perform a large-scale empirical evaluation, and show that our
approach typically enjoys superior performance and efficiency compared to
standard baselines.
