  This paper investigates methods for estimating the optimal stochastic control
policy for a Markov Decision Process with unknown transition dynamics and an
unknown reward function. This form of model-free reinforcement learning
comprises many real world systems such as playing video games, simulated
control tasks, and real robot locomotion. Existing methods for estimating the
optimal stochastic control policy rely on high variance estimates of the policy
descent. However, these methods are not guaranteed to find the optimal
stochastic policy, and the high variance gradient estimates make convergence
unstable. In order to resolve these problems, we propose a technique using
Markov Chain Monte Carlo to generate samples from the posterior distribution of
the parameters conditioned on being optimal. Our method provably converges to
the globally optimal stochastic policy, and empirically similar variance
compared to the policy gradient.
