  Since its introduction a decade ago, \emph{relative entropy policy search}
(REPS) has demonstrated successful policy learning on a number of simulated and
real-world robotic domains, not to mention providing algorithmic components
used by many recently proposed reinforcement learning (RL) algorithms. While
REPS is commonly known in the community, there exist no guarantees on its
performance when using stochastic and gradient-based solvers. In this paper we
aim to fill this gap by providing guarantees and convergence rates for the
sub-optimality of a policy learned using first-order optimization methods
applied to the REPS objective. We first consider the setting in which we are
given access to exact gradients and demonstrate how near-optimality of the
objective translates to near-optimality of the policy. We then consider the
practical setting of stochastic gradients, and introduce a technique that uses
\emph{generative} access to the underlying Markov decision process to compute
parameter updates that maintain favorable convergence to the optimal
regularized policy.
