# Softmax Policy Gradient Methods Can Take Exponential Time to Converge

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 22 Feb 2021.

## Builds on (most cited first, 23 of 23)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Sample Efficient Reinforcement Learning with REINFORCE](https://mlsanity.com/paper/2010.11364/) (2020)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Policy Optimization for H2 Linear Control with H_∞ Robustness Guarantee: Implicit Regularization and Global Convergence](https://mlsanity.com/paper/1910.09496/) (2019)
- [Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem](https://mlsanity.com/paper/1912.11899/) (2019)
- [Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy](https://mlsanity.com/paper/1906.10306/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Global optimality of softmax policy gradient with single hidden layer neural networks in the mean-field regime](https://mlsanity.com/paper/2010.11858/) (2020)
- [Convergence Guarantees of Policy Optimization Methods for Markovian Jump Linear Systems](https://mlsanity.com/paper/2002.04090/) (2020)
- [Provable Fictitious Play for General Mean-Field Games](https://mlsanity.com/paper/2010.04211/) (2020)
- [Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPs](https://mlsanity.com/paper/2011.00213/) (2020)

## Built on by (most cited first, 30 of 48)

- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Vanishing Gradients in Reinforcement Finetuning of Language Models](https://mlsanity.com/paper/2310.20703/) (2023)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2110.10117/) (2021)
- [The Role of Baselines in Policy Gradient Optimization](https://mlsanity.com/paper/2301.06276/) (2023)
- [Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regime](https://mlsanity.com/paper/2201.07296/) (2022)
- [Understanding the Effect of Stochasticity in Policy Optimization](https://mlsanity.com/paper/2110.15572/) (2021)
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024)
- [Understanding the Complexity Gains of Single-Task RL with a Curriculum](https://mlsanity.com/paper/2212.12809/) (2022)
- [Robust Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.06866/) (2022)
- [Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games](https://mlsanity.com/paper/2310.09727/) (2023)
- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Learning Optimal Deterministic Policies with Stochastic Policy Gradients](https://mlsanity.com/paper/2405.02235/) (2024)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [An Alternate Policy Gradient Estimator for Softmax Policies](https://mlsanity.com/paper/2112.11622/) (2021)
- [Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods](https://mlsanity.com/paper/2109.06362/) (2021)
- [Convergence and Price of Anarchy Guarantees of the Softmax Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2206.07642/) (2022)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates](https://mlsanity.com/paper/2502.07141/) (2025)
- [Approximate Newton policy gradient algorithms](https://mlsanity.com/paper/2110.02398/) (2021)
- [Actor-Critic based Improper Reinforcement Learning](https://mlsanity.com/paper/2207.09090/) (2022)
- [Policy Gradient with Tree Expansion](https://mlsanity.com/paper/2301.13236/) (2023)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Breaking the Safety-Capability Tradeoff: Reinforcement Learning with Verifiable Rewards Maintains Safety Guardrails in LLMs](https://mlsanity.com/paper/2511.21050/) (2025)
- [Accelerating Primal-dual Methods for Regularized Markov Decision Processes](https://mlsanity.com/paper/2202.10506/) (2022)
- [Matryoshka Policy Gradient for Entropy-Regularized RL: Convergence and Global Optimality](https://mlsanity.com/paper/2303.12785/) (2023)

## Abstract (arXiv)

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 γ-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 S and the effective horizon frac11-γ, 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 η can take [ frac1η |S|^2^Omegabig(frac11-γbig) ~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.