  Variational quantum circuits have recently gained popularity as quantum
machine learning models. While considerable effort has been invested to train
them in supervised and unsupervised learning settings, relatively little
attention has been given to their potential use in reinforcement learning. In
this work, we leverage the understanding of quantum policy gradient algorithms
in a number of ways. First, we investigate how to construct and train
reinforcement learning policies based on variational quantum circuits. We
propose several designs for quantum policies, provide their learning
algorithms, and test their performance on classical benchmarking environments.
Second, we show the existence of task environments with a provable separation
in performance between quantum learning agents and any polynomial-time
classical learner, conditioned on the widely-believed classical hardness of the
discrete logarithm problem. We also consider more natural settings, in which we
show an empirical quantum advantage of our quantum policies over standard
neural-network policies. Our results constitute a first step towards
establishing a practical near-term quantum advantage in a reinforcement
learning setting. Additionally, we believe that some of our design choices for
variational quantum policies may also be beneficial to other models based on
variational quantum circuits, such as quantum classifiers and quantum
regression models.
