# Understanding the Effect of Stochasticity in Policy Optimization

arXiv: https://arxiv.org/abs/2110.15572 · HTML: https://mlsanity.com/paper/2110.15572/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 29 Oct 2021.

## Builds on (most cited first, 21 of 21)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Learning Dexterous In-Hand Manipulation](https://mlsanity.com/paper/1808.00177/) (2018)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Effective Diversity in Population Based Reinforcement Learning](https://mlsanity.com/paper/2002.00632/) (2020)
- [Sample Efficient Reinforcement Learning with REINFORCE](https://mlsanity.com/paper/2010.11364/) (2020)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [The Mirage of Action-Dependent Baselines in Reinforcement Learning](https://mlsanity.com/paper/1802.10031/) (2018)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Beyond variance reduction: Understanding the true impact of baselines on policy optimization](https://mlsanity.com/paper/2008.13773/) (2020)
- [Population-Guided Parallel Policy Search for Reinforcement Learning](https://mlsanity.com/paper/2001.02907/) (2020)
- [Optimization Issues in KL-Constrained Approximate Policy Iteration](https://mlsanity.com/paper/2102.06234/) (2021)
- [Regret Analysis of a Markov Policy Gradient Algorithm for Multi-arm Bandits](https://mlsanity.com/paper/2007.10229/) (2020)

## Built on by (most cited first, 18 of 18)

- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [The Role of Baselines in Policy Gradient Optimization](https://mlsanity.com/paper/2301.06276/) (2023)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [An Alternate Policy Gradient Estimator for Softmax Policies](https://mlsanity.com/paper/2112.11622/) (2021)
- [Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs](https://mlsanity.com/paper/2405.13136/) (2024)
- [When EOS Tokens Disagree: Understanding Length Inflation in On-Policy Distillation](https://mlsanity.com/paper/2609.20511/) (2026)
- [Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning](https://mlsanity.com/paper/2310.11897/) (2023)
- [Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates](https://mlsanity.com/paper/2502.07141/) (2025)
- [Behind the Myth of Exploration in Policy Gradients](https://mlsanity.com/paper/2402.00162/) (2024)
- [Functional Acceleration for Policy Mirror Descent](https://mlsanity.com/paper/2407.16602/) (2024)
- [Policy Optimization finds Nash Equilibrium in Regularized General-Sum LQ Games](https://mlsanity.com/paper/2404.00045/) (2024)
- [Fast Convergence of Softmax Policy Mirror Ascent](https://mlsanity.com/paper/2411.12042/) (2024)
- [Coordinate Ascent for Off-Policy RL with Global Convergence Guarantees](https://mlsanity.com/paper/2212.05237/) (2022)
- [How Log-Barrier Helps Exploration in Policy Optimization](https://mlsanity.com/paper/2603.15001/) (2026)
- [Acceleration in Policy Optimization](https://mlsanity.com/paper/2306.10587/) (2023)
- [Demonstrating Generalization Failures via Mixtures of Conditional Policies](https://mlsanity.com/paper/2607.03478/) (2026)
- [Shared Actors Need Not Share Critics: Effects of Value Mismatch in Parallel Reinforcement Learning](https://mlsanity.com/paper/2608.26481/) (2026)

## Abstract (arXiv)

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.