On the Global Convergence Rates of Softmax Policy Gradient Methods
arXiv:2005.06392
Abstract
We make three contributions toward better understanding policy gradient methods in the tabular setting. First, we show that with the true gradient, policy gradient with a softmax parametrization converges at a rate, with constants depending on the problem and initialization. This result significantly expands the recent asymptotic convergence results. The analysis relies on two findings: that the softmax policy gradient satisfies a Łojasiewicz inequality, and the minimum probability of an optimal action during optimization can be bounded in terms of its initial value. Second, we analyze entropy regularized policy gradient and show that it enjoys a significantly faster linear convergence rate toward softmax optimal policy . This result resolves an open question in the recent literature. Finally, combining the above two results and additional new lower bound results, we explain how entropy regularization improves policy optimization, even with the true gradient, from the perspective of convergence rate. The separation of rates is further explained using the notion of non-uniform Łojasiewicz degree. These results provide a theoretical understanding of the impact of entropy and corroborate existing empirical studies.
64 pages, 5 figures. Published in ICML 2020
References in corpus (1)
Cited by in corpus (30)
- Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
- Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
- On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
- Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
- Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergences
- Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
- A general sample complexity analysis of vanilla policy gradient
- Reinforcement Learning for Load-balanced Parallel Particle Tracing
- Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
- Softmax Policy Gradient Methods Can Take Exponential Time to Converge
- Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
- Leveraging Non-uniformity in First-order Non-convex Optimization
- Meta-Learning Bandit Policies by Gradient Ascent
- Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
- Beyond variance reduction: Understanding the true impact of baselines on policy optimization
- Gradient play in stochastic games: stationary points, convergence, and sample complexity
- A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization
- On Linear Convergence of Policy Gradient Methods for Finite MDPs
- Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
- Approximate Newton policy gradient algorithms
- Improper Reinforcement Learning with Gradient-based Policy Optimization
- On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
- Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning
- Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
- Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
- Off-Policy Actor-Critic with Emphatic Weightings
- On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
- Cautious Policy Programming: Exploiting KL Regularization in Monotonic Policy Improvement for Reinforcement Learning
- Global optimality of softmax policy gradient with single hidden layer neural networks in the mean-field regime
- Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch