# Sample Complexity of Policy Gradient Finding Second-Order Stationary Points

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2020.

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

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Constrained Update Projection Approach to Safe Policy Optimization](https://mlsanity.com/paper/2209.07089/) (2022)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [CUP: A Conservative Update Policy Algorithm for Safe Reinforcement Learning](https://mlsanity.com/paper/2202.07565/) (2022)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2304.10951/) (2023)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [TinyLight: Adaptive Traffic Signal Control on Devices with Extremely Limited Resources](https://mlsanity.com/paper/2205.00427/) (2022)
- [A nearly Blackwell-optimal policy gradient method](https://mlsanity.com/paper/2105.13609/) (2021)
- [Efficiently Escaping Saddle Points for Policy Optimization](https://mlsanity.com/paper/2311.08914/) (2023)
- [DiffOP: Reinforcement Learning of Optimization-Based Control Policies via Implicit Policy Gradients](https://mlsanity.com/paper/2411.07484/) (2024)
- [A Communication-Efficient Decentralized Actor-Critic Algorithm](https://mlsanity.com/paper/2510.19199/) (2025)
- [Stochastic Dimension-reduced Second-order Methods for Policy Optimization](https://mlsanity.com/paper/2301.12174/) (2023)
- [Off-OAB: Off-Policy Policy Gradient Method with Optimal Action-Dependent Baseline](https://mlsanity.com/paper/2405.02572/) (2024)
- [A Variance-Reduced Cubic-Regularized Newton for Policy Optimization](https://mlsanity.com/paper/2507.10120/) (2025)
- [Policy Newton methods for Distortion Riskmetrics](https://mlsanity.com/paper/2508.07249/) (2025)

## Abstract (arXiv)

The goal of policy-based reinforcement learning (RL) is to search the maximal point of its objective. However, due to the inherent non-concavity of its objective, convergence to a first-order stationary point (FOSP) can not guarantee the policy gradient methods finding a maximal point. A FOSP can be a minimal or even a saddle point, which is undesirable for RL. Fortunately, if all the saddle points are strict, all the second-order stationary points (SOSP) are exactly equivalent to local maxima. Instead of FOSP, we consider SOSP as the convergence criteria to character the sample complexity of policy gradient. Our result shows that policy gradient converges to an (ε,√εchi)-SOSP with probability at least 1-widetildeO(δ) after the total cost of Oleft(dfracε^-frac92(1-γ)√chilogdfrac1δright), where γ∈(0,1). Our result improves the state-of-the-art result significantly where it requires Oleft(dfracε-9chi^frac32δlogdfrac1εchiright). Our analysis is based on the key idea that decomposes the parameter space ℝp into three non-intersected regions: non-stationary point, saddle point, and local optimal region, then making a local improvement of the objective of RL in each region. This technique can be potentially generalized to extensive policy gradient methods.