Understanding the Effect of Stochasticity in Policy Optimization

Jincheng Mei, Bo Dai, Chenjun Xiao, Csaba Szepesvari, Dale Schuurmans

Reinforcement learning (RL) practitioners often observe a frustrating phenomenon: "advanced" policy optimization methods frequently fail or exhibit extreme sensitivity to random seeds, while simpler methods remain robust. This paper provides a rigorous theoretical foundation for this behavior, proving a fundamental trade-off in stochastic policy optimization. An algorithm can either be "stable" (guaranteed to find the global optimum but at a slow rate) or "aggressive" (converging at a fast exponential rate but with a non-zero probability of failing entirely).

The Exact vs. Stochastic Gradient Gap

In the "exact gradient" setting—where the agent has perfect knowledge of the environment's rewards—advanced techniques like Natural Policy Gradient (NPG) and Mirror Descent strictly outperform standard Softmax Policy Gradient (PG). They exploit the geometry of the optimization landscape to achieve exponential convergence ($O(e^{-ct})$) compared to the standard $O(1/t)$ rate.

However, real-world RL relies on stochastic on-policy samples. Agents do not have access to the true gradient; they must rely on noisy estimates based on recent actions. The authors address a critical gap: why do geometrically superior methods often converge to sub-optimal policies or become highly sensitive to initialization when moving from exact gradients to stochastic samples?

The Committal Rate

To explain these differences, the authors analyze three representative algorithms: Softmax PG, NPG, and Geometry-aware Normalized PG (GNPG). They introduce a novel metric called the committal rate ($\kappa$), which measures how aggressively an algorithm "commits" to an action based on its samples.

  • High $\kappa$: The algorithm quickly increases the probability of an action it evaluates as good.
  • Low $\kappa$: The algorithm updates its policy more cautiously.

The authors prove that for an algorithm to guarantee convergence to the global optimum almost surely, its committal rate for sub-optimal actions must be $\leq 1$.

The Geometry-Convergence Trade-off

The core finding is an inherent "Geometry-Convergence Trade-off." Without an external oracle providing extra information about the reward gap, an algorithm cannot be both faster than $O(1/t)$ and guaranteed to be globally optimal. You can have speed, or you can have certainty, but not both.

Convergence comparison of Softmax PG, NPG, and GNPG

As summarized in the table above:

  • Softmax PG is Robust: It converges in probability to the global optimum even with stochastic samples, but it is stuck at the slower $\Theta(1/t)$ rate. Its committal rate is exactly 1.
  • NPG and GNPG Risk Failure: In the exact gradient setting, NPG's speed is a feature. In the stochastic setting, it becomes a flaw. NPG has an infinite committal rate ($\kappa = \infty$), meaning it can "lock in" on a sub-optimal action before gathering enough evidence to realize its mistake. Consequently, these methods fail (converge to sub-optimal policies) with positive probability.

This theory elegantly explains why RL is so sensitive to random seeds. Because fast algorithms have a positive probability of failure, a "bad" random initialization might lead the agent down a path where it commits to a sub-optimal policy almost immediately.

Proposed Solution and Limitations

To bridge this gap, the authors propose an ensemble method. By running $O(\log(1/\delta))$ independent trials of a fast but "risky" algorithm (like NPG) and selecting the best one, practitioners can achieve fast exponential convergence with high probability ($1-\delta$).

While these insights are powerful, the current analysis assumes rewards are observed without noise (only the sampling of actions is stochastic). Extending this to noisy reward observations is a key next step. Furthermore, the detailed analysis is centered on the tabular (one-state) setting. Extending the committal rate theory to function approximation in deep RL remains an open and exciting challenge.

Summary updated

Abstract

We study the effect of stochasticity in on-policy policy optimization, and make the following four contributions. \emph{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. \emph{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. \emph{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. \emph{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.
BibTeX
@inproceedings{mei2021understanding,
  author = {Jincheng Mei and Bo Dai and Chenjun Xiao and Csaba Szepesvari and Dale Schuurmans},
  title = {{Understanding the Effect of Stochasticity in Policy Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=oAog3W9w6R},
}
Figure