# A Large Deviations Perspective on Policy Gradient Algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 36 references that are in the map.
- First posted on arXiv 13 Nov 2023.

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

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [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)
- [Bridging the Gap Between Value and Policy Based Reinforcement Learning](https://mlsanity.com/paper/1702.08892/) (2017)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [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 Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)
- [An Exploration of Softmax Alternatives Belonging to the Spherical Loss Family](https://mlsanity.com/paper/1511.05042/) (2015)
- [Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2110.10117/) (2021)
- [Large deviations rates for stochastic gradient descent with strongly convex functions](https://mlsanity.com/paper/2211.00969/) (2022)
- [Importance Sampling for Stochastic Gradient Descent in Deep Neural Networks](https://mlsanity.com/paper/2303.16529/) (2023)

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

- [Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry](https://mlsanity.com/paper/2410.15637/) (2024)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)

## Abstract (arXiv)

Motivated by policy gradient methods in the context of reinforcement learning, we identify a large deviation rate function for the iterates generated by stochastic gradient descent for possibly non-convex objectives satisfying a Polyak-Lojasiewicz condition. Leveraging the contraction principle from large deviations theory, we illustrate the potential of this result by showing how convergence properties of policy gradient with a softmax parametrization and an entropy regularized objective can be naturally extended to a wide spectrum of other policy parametrizations.