Understanding the Effect of Stochasticity in Policy Optimization

Jincheng Mei, Bo Dai, Chenjun Xiao, Csaba Szepesvári, Dale Schuurmans

Abstract

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.

Introduction

Policy optimization is the bedrock of modern reinforcement learning (RL), powering popular algorithms like PPO and TRPO. Recent theoretical work has established that standard softmax Policy Gradient (PG) is guaranteed to converge to the global optimum, albeit at a slow rate of $O(1/t)$. To improve efficiency, researchers have turned to methods that exploit the geometric landscape of the objective function, such as Natural Policy Gradient (NPG). Under the assumption of exact, true gradients, NPG achieves exponentially faster convergence ($O(e^{-ct})$).

However, a significant gap exists between theory and practice. Real-world RL relies on stochastic on-policy sampling to estimate gradients. This work investigates a critical anomaly: while standard PG remains reliable under stochasticity, "fast" geometry-aware methods like NPG can fail catastrophically, converging to sub-optimal policies. This paper seeks to understand why this happens and whether it is possible to design an algorithm that is both fast and perfectly reliable in stochastic settings.

The Committal Rate and Geometry-Convergence Trade-off

To analyze this phenomenon, we introduce the committal rate. This metric quantifies how aggressively an algorithm increases the probability of an action when it is repeatedly sampled. By mathematically decoupling the sampling and updating phases, we can measure an algorithm's inherent aggressiveness and use it to predict whether the algorithm will survive the noise of stochastic sampling.

Our analysis reveals that standard PG has a low committal rate ($≤ 1$), allowing it to react slowly enough to bad samples that it eventually recovers and explores the optimal action. In contrast, NPG and Geometry-aware Normalized PG (GNPG) possess an infinite committal rate. If these algorithms sample a sub-optimal action early on, they commit so aggressively that the probability of exploring other actions vanishes, trapping the policy in a vicious cycle of sub-optimal behavior.

Results: The Stochastic Anomaly

Our theoretical analysis of three representative algorithms—standard PG, NPG, and GNPG—highlights a fundamental trade-off between speed and reliability.

Comparison of convergence properties under true vs. stochastic gradients.

As shown in the table above, algorithms that are provably superior with exact gradients (NPG, GNPG) are precisely those that fail when forced to rely on on-policy stochastic gradients. We prove that an uninformed algorithm must choose: either converge to the global optimum with probability 1 at a slow $O(1/t)$ rate, or achieve faster convergence while accepting a strictly positive probability of failure. Specifically, a committal rate of $≤ 1$ for sub-optimal actions is a necessary condition for an algorithm to almost surely converge to the global optimum.

Implications for Practice

This theory explains the "random seed lottery" observed in practical RL. Algorithms like TRPO and PPO, which are based on NPG-like updates, are highly sensitive to initialization because their aggressive updates can lead to early, irreversible commitment to sub-optimal policies based on initial random samples.

To mitigate this, we propose the use of ensembles. Since fast algorithms either fail or converge very quickly based on early samples, running an ensemble of $O(\log(1/\delta))$ independent runs and selecting the best one can guarantee convergence to the global optimum at the fast $O(e^{-ct})$ rate with high probability ($1-\delta$).

Conclusion

We have identified a fundamental limitation in on-policy optimization: the inherent trade-off between exploiting geometry for speed and maintaining reliability under stochasticity. While geometry-aware methods offer exponential speedups in ideal settings, their high committal rates make them vulnerable to noise. Future work will explore breaking this trade-off in on-policy settings and refining the conditions for almost sure global convergence in more complex, noisy environments.

Summary updated

Abstract

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.
BibTeX
@inproceedings{mei2021understanding,
  author = {Jincheng Mei and Bo Dai and Chenjun Xiao and Csaba Szepesvári 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},
}

Loading related content...

Figure