# Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 21 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (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)
- [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)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon](https://mlsanity.com/paper/2011.10300/) (2020)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes](https://mlsanity.com/paper/2309.01922/) (2023)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [Steady State Analysis of Episodic Reinforcement Learning](https://mlsanity.com/paper/2011.06631/) (2020)
- [Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods](https://mlsanity.com/paper/2310.02671/) (2023)
- [On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2403.06806/) (2024)
- [Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods](https://mlsanity.com/paper/2109.06362/) (2021)
- [Reinforcement Learning with Random Time Horizons](https://mlsanity.com/paper/2506.00962/) (2025)

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

- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework](https://mlsanity.com/paper/2605.10671/) (2026)
- [Policy Gradient for Continuous-Time Robust Markov Decision Processes](https://mlsanity.com/paper/2606.04335/) (2026)

## Abstract (arXiv)

The classical policy gradient method is the theoretical and conceptual foundation of modern policy-based reinforcement learning (RL) algorithms. Most rigorous analyses of such methods, particularly those establishing convergence guarantees, assume a discount factor γ < 1. In contrast, however, a recent line of work on policy-based RL for large language models uses the undiscounted total-reward setting with γ = 1, rendering much of the existing theory inapplicable. In this paper, we provide analyses of the policy gradient method for undiscounted expected total-reward infinite-horizon MDPs based on two key insights: (i) the classification of the MDP states into recurrent and transient states is invariant over the set of policies that assign strictly positive probability to every action (as is typical in deep RL models employing a softmax output layer) and (ii) the classical state visitation measure (which may be ill-defined when γ = 1) can be replaced with a new object that we call the transient visitation measure.