  Quantum computers can offer dramatic improvements over classical devices for
data analysis tasks such as prediction and classification. However, less is
known about the advantages that quantum computers may bring in the setting of
reinforcement learning, where learning is achieved via interaction with a task
environment. Here, we consider a special case of reinforcement learning, where
the task environment allows quantum access. In addition, we impose certain
"naturalness" conditions on the task environment, which rule out the kinds of
oracle problems that are studied in quantum query complexity (and for which
quantum speedups are well-known). Within this framework of quantum-accessible
reinforcement learning environments, we demonstrate that quantum agents can
achieve exponential improvements in learning efficiency, surpassing previous
results that showed only quadratic improvements. A key step in the proof is to
construct task environments that encode well-known oracle problems, such as
Simon's problem and Recursive Fourier Sampling, while satisfying the above
"naturalness" conditions for reinforcement learning. Our results suggest that
quantum agents may perform well in certain game-playing scenarios, where the
game has recursive structure, and the agent can learn by playing against
itself.
