  We study the effect of stochasticity in on-policy policy optimization, and
make the following four contributions. First, we show that the preferability of
optimization methods depends critically on whether stochastic versus exact
gradients are used. In particular, unlike the true gradient setting, geometric
information cannot be easily exploited in the stochastic case for accelerating
policy optimization without detrimental consequences or impractical
assumptions. Second, to explain these findings we introduce the concept of
committal rate for stochastic policy optimization, and show that this can serve
as a criterion for determining almost sure convergence to global optimality.
Third, we show that in the absence of external oracle information, which allows
an algorithm to determine the difference between optimal and sub-optimal
actions given only on-policy samples, there is an inherent trade-off between
exploiting geometry to accelerate convergence versus achieving optimality
almost surely. That is, an uninformed algorithm either converges to a globally
optimal policy with probability $1$ but at a rate no better than $O(1/t)$, or
it achieves faster than $O(1/t)$ convergence but then must fail to converge to
the globally optimal policy with some positive probability. Finally, we use the
committal rate theory to explain why practical policy optimization methods are
sensitive to random initialization, then develop an ensemble method that can be
guaranteed to achieve near-optimal solutions with high probability.
