# Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 4 Oct 2023.

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

- [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)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Model-Based Reinforcement Learning via Meta-Policy Optimization](https://mlsanity.com/paper/1809.05214/) (2018)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020)
- [Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon](https://mlsanity.com/paper/2011.10300/) (2020)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games](https://mlsanity.com/paper/2107.13090/) (2021)
- [Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2110.10117/) (2021)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022)
- [Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity](https://mlsanity.com/paper/2101.01041/) (2021)
- [A policy gradient approach for Finite Horizon Constrained Markov Decision Processes](https://mlsanity.com/paper/2210.04527/) (2022)
- [Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods](https://mlsanity.com/paper/2109.06362/) (2021)

## Built on by (most cited first, 9 of 9)

- [On Entropy Control in LLM-RL Algorithms](https://mlsanity.com/paper/2509.03493/) (2025)
- [EPO: Entropy-regularized Policy Optimization for LLM Agents Reinforcement Learning](https://mlsanity.com/paper/2509.22576/) (2025)
- [ARES: Multimodal Adaptive Reasoning via Difficulty-Aware Token-Level Entropy Shaping](https://mlsanity.com/paper/2510.08457/) (2025)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs](https://mlsanity.com/paper/2510.18340/) (2025)
- [A learning-based approach to stochastic optimal control under reach-avoid constraint](https://mlsanity.com/paper/2412.16561/) (2024)
- [Causal Invariance Learning via Efficient Nonconvex Optimization](https://mlsanity.com/paper/2412.11850/) (2024)
- [Structure Matters: Dynamic Policy Gradient](https://mlsanity.com/paper/2411.04913/) (2024)
- [Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes](https://mlsanity.com/paper/2607.22982/) (2026)

## Abstract (arXiv)

Markov Decision Processes (MDPs) are a formal framework for modeling and solving sequential decision-making problems. In finite-time horizons such problems are relevant for instance for optimal stopping or specific supply chain problems, but also in the training of large language models. In contrast to infinite horizon MDPs optimal policies are not stationary, policies must be learned for every single epoch. In practice all parameters are often trained simultaneously, ignoring the inherent structure suggested by dynamic programming. This paper introduces a combination of dynamic programming and policy gradient called dynamic policy gradient, where the parameters are trained backwards in time. For the tabular softmax parametrisation we carry out the convergence analysis for simultaneous and dynamic policy gradient towards global optima, both in the exact and sampled gradient settings without regularisation. It turns out that the use of dynamic policy gradient training much better exploits the structure of finite- time problems which is reflected in improved convergence bounds.