Sample Complexity Of Policy Gradient Finding Second-order Stationary Points

Abstract

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 \((\epsilon,\sqrt\{\epsilon\chi\})\)-SOSP with probability at least \(1-\widetilde\{\mathcal\{O\}\}(\delta)\) after the total cost of \(\mathcal\{O\}\left(\dfrac\{\epsilon^\{-\frac\{9\}\{2\}\}\}\{(1-\gamma)\sqrt\chi\}log\dfrac\{1\}\{\delta\}\right)\), where \(\gamma\in(0,1)\). Our result improves the state-of-the-art result s

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyang2020sample

Related papers

• Efficiently Escaping Saddle Points For Policy Optimization (2023)0.00
• On The Convergence Of Policy Gradient Methods To Nash Equilibria In General Stochastic Games (2022)0.00
• Gradient Play In Stochastic Games: Stationary Points, Convergence, And Sample Complexity (2021)0.00
• On The Second-order Convergence Of Biased Policy Gradient Algorithms (2023)0.00
• Stochastic Policy Gradient Methods: Improved Sample Complexity For Fisher-non-degenerate Policies (2023)0.00
• Sample Efficient Policy Gradient Methods With Recursive Variance Reduction (2019)0.00
• Global Convergence Guarantees For Federated Policy Gradient Methods With Adversaries (2024)0.00
• Low-switching Policy Gradient With Exploration Via Online Sensitivity Sampling (2023)0.00