Sample Complexity of Policy Gradient Finding Second-Order Stationary Points

Authors

  • Long Yang Zhejiang University
  • Qian Zheng Nanyang Technological University
  • Gang Pan Zhejiang University

Keywords:

Reinforcement Learning

Abstract

The policy-based reinforcement learning (RL) can be considered as maximization of its objective. However, due to the inherent non-concavity of its objective, the policy gradient method to a first-order stationary point (FOSP) cannot guar- antee a maximal point. A FOSP can be a minimal or even a saddle point, which is undesirable for RL. It has be found that if all the saddle points are strict, all the second-order station- ary points (SOSP) are exactly equivalent to local maxima. Instead of FOSP, we consider SOSP as the convergence criteria to characterize the sample complexity of policy gradient. Our result shows that policy gradient converges to an (ε, √εχ)-SOSP with probability at least 1 − O(δ) after the total cost of O(ε−9/2)sinificantly improves the state of the art cost O(ε−9).Our analysis is based on the key idea that decomposes the parameter space Rp into three non-intersected regions: non-stationary point region, saddle point region, 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. For the complete proof, please refer to https://arxiv.org/pdf/2012.01491.pdf.

Downloads

Published

2021-05-18

How to Cite

Yang, L., Zheng, Q., & Pan, G. (2021). Sample Complexity of Policy Gradient Finding Second-Order Stationary Points. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 10630-10638. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17271

Issue

Section

AAAI Technical Track on Machine Learning V