Softmax Policy Gradient Methods Can Take Exponential Time to Converge

Abstract

The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For $\gamma$-discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space $\mathcal{S}$ and the effective horizon $\frac{1}{1-\gamma }$, both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize $\eta$ can take \[ \frac{1}η |\mathcal{S}|^{2^{Ω\big(\frac{1}{1-γ}\big)}} ~\text{iterations} \] to converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods.

arXiv commentaccepted to Mathematical Programming (Series A); also presented in part in Conference on Learning Theory (COLT) 2021

References in corpus (17)

• Trust Region Policy Optimization
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Robust Policy Gradient against Strong Data Corruption
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Provable Fictitious Play for General Mean-Field Games
• Leveraging Non-uniformity in First-order Non-convex Optimization
• Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPs

Cited by in corpus (4)

• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Leveraging Non-uniformity in First-order Non-convex Optimization
• Improper Reinforcement Learning with Gradient-based Policy Optimization
• Understanding the Effect of Stochasticity in Policy Optimization