Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs
Jongmin Lee, Ernest K. Ryu · 2025
Read Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs by Jongmin Lee, Ernest K. Ryu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18340.txt.
Introduction
Jongmin Lee and Ernest K Ryu explain policy gradient methods in a 2025 reinforcement learning paper. Reinforcement learning trains agents by reward, and policy gradient methods adjust the action policy directly. Most proofs assume a discount factor below one, meaning future rewards count for less than present ones.
Modern language model training often uses no discounting, so those proofs do not apply. The authors show that state types, recurrent versus transient, stay fixed across common softmax policies. Softmax here means the policy gives every action some positive chance. They define a transient visitation measure to replace the classic one, restoring convergence analysis for the undiscounted case.
Catalog record
| CREATOR | Jongmin Lee, Ernest K. Ryu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-18340
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs Jongmin Lee, Ernest K. Ryu Abstract 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 \gamma<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 \gamma=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 \gamma=1 ) can be replaced with a new object that we call the transient visitation measure. 1 Introduction Since the seminal Policy Gradient Theorem ( Sutton et al. 1999 ) , policy gradient algorithms have been a cornerstone of modern reinforcement learning (RL). Unlike classical dynamic programming approaches, policy gradient methods directly optimize the policy using the gradient of the expected total-reward. These methods, along with their deep learning variants, have achieved remarkable practical success, and their convergence properties have been extensively studied for Markov decision processes (MDP) with discount factor \gamma<1 . More recently, however, a large body of work has emerged on training large language models within the RL framework without discounting ( \gamma=1 ) and arbitrarily long horizons, as in reinforcement learning from human feedback (RLHF) ( Christiano et al. 2017 ) and reinforcement learning with verifiable rewards (RLVR) ( Guo et al. 2025 ) . Yet, the convergence of policy gradient methods in this undiscounted total-reward setup remains largely unexplored, and even the policy gradient theorem itself has not been rigorously established in this setup. Contribution In this work, we study the convergence of policy gradient methods for undiscounted expected total-reward infinite-horizon MDPs. Our analysis is 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 ill-defined when \gamma=1 ) can be replaced with a new object that we call the transient visitation measure . Leveraging these insights, we establish convergence guarantees for projected policy gradient and natural policy gradient algorithms in the tabular setting. 1.1 related works Undiscounted total-reward infinite horizon MDP. The setup of undiscounted total-reward MDP was first introduced by Savage 1965 . For the well-definedness of the value function, Schäl 1983 considered the finiteness of V^{\pi}_{+} and V^{\pi}_{-} (defined in the next section) and the existence of an optimal policy was first proved by Van Der Wal 1981 . With different additional assumptions, three models of total-reward setup have been proposed and studied: stochastic shortest path model ( Eaton & Zadeh 1962 ) , positive model ( Blackwell 1967 ) , and negative model ( Strauch 1966 ) . The stochastic shortest path model assumes single absorbing terminal state and the existence of a policy that reaches the terminal state with probability 1 from any initial state ( Bertsekas & Tsitsiklis 1991 ) . The positive model assumed V_{+}^{\pi} is finite, and for each s , there exist a with r(s,a)\geq 0 ( Puterman 2014 , Section 7.2) . The negative model assumed V_{+}^{\pi}=0 and there exist \pi for which V_{-}^{\pi}(s)>\infty for all s ( Puterman 2014 , Section 7.3) . In this work, the undiscounted total-reward model with the assumption that V^{\pi} is finite, motivated by modern reinforcement learning frameworks and needed to establish the transient policy gradient, does not fall into previous categories. Policy gradient method. Policy gradient methods ( Williams 1992 ; Sutton et al. 1999 ; Konda & Tsitsiklis 1999 ; Kakade 2001 ) are foundational reinforcement learning algorithms, commonly implemented with deep neural networks for policy parameterization ( Schulman et al. 2015 ; Schulman et al. 2017 ) . In line with their practical success, convergence of policy gradient variants has been extensively studied across settings. In discounted total-reward infinite horizon MDP, Agarwal et al. 2021 ; Xiao 2022 ; Bhandari & Russo 2024 ; Mei et al. 2020 analyzed convergence of projected policy gradient and naive policy gradient with softmax parametrization. The natural policy gradient, introduced by Kakade 2001 and viewable as a special case of mirror descent ( Shani et al. 2020 ) , has been analyzed by Agarwal et al. 2021 ; Cen et al. 2022 ; Xiao 2022 ; Lan 2023 . In the average reward MDP, convergence results have been established by Even-Dar et al. 2009 ; Murthy & Srikant 2023 ; Bai et al. 2024 ; Kumar et al. 2024 , and related analyses exist for the finite horizon setup as well ( Hambly et al. 2021 ; Guo et al. 2022 ; Klein et al. 2023 ) . In undiscounted total-reward infinite-horizon MDP, however, there are few results on policy gradient methods. Since Sutton et al. 1999 established the policy gradient theorem only for the discounted total-reward and average reward MDPs, Bojun 2020 ; Ribera Borrell et al. 2025 analyze policy gradients for the undiscounted total-reward random time horizon MDP. Specifically, Bojun 2020 consider an episodic learning process that can be viewed as an ergodic Markov chain with finite episode length , and establish a policy gradient theorem via the steady state distribution. Ribera Borrell et al. 2025 consider trajectory dependent random termination times and prove a policy gradient theorem with an almost surely finite termination time. We note that neither work further analyzes the convergence of policy gradient methods, and their setups and assumptions differ from ours, as shown in next section. 2 Undiscounted expected total-reward infinite-horizon MDPs In this work, we consider undiscounted total-reward infinite-horizon Markov decision processes (MDPs). We review basic definitions and assumptions of undiscounted MDPs and reinforcement learning (RL). For further details, we refer the readers to references such as ( Puterman 2014 , Section 7) or ( Sutton & Barto 2018 ) . Undiscounted Markov decision processes. Let \mathcal{M}(\mathcal{X}) be the space of probability distributions over a set \mathcal{X} . Write (\mathcal{S},\mathcal{A},P,r,\mu) to denote the infinite-horizon undiscounted MDP with finite state space \mathcal{S} , finite action space \mathcal{A} , transition matrix P\colon\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{M}(\mathcal{S}) , bounded reward r\colon\mathcal{S}\times\mathcal{A}\rightarrow[-R,R] with some R<\infty , and initial state distribution \mu\in\mathcal{M}(\mathcal{S}) . We say the reward is nonnegative if r(s,a)\geq 0 for all s\in\mathcal{S},a\in\mathcal{A} . Denote \pi\colon\mathcal{S}\rightarrow\mathcal{M}(\mathcal{A}) for a policy. Define \displaystyle\Pi \displaystyle=\text{set of all policies}=\mathcal{M}(\mathcal{A})^{\mathcal{S}}, \displaystyle\Pi_{+} \displaystyle=\{\pi\in\Pi\,|\,\pi(s\,|\,a)>0\text{ for all }s,a\}. So, \Pi_{+} is the (relative) interior of \Pi . Let \displaystyle V_{\raisebox{1.35623pt}{$\mkern 1.0mu\scriptscriptstyle+$}}^{\pi}(s) \displaystyle=\lim_{T\rightarrow\infty}\mathbb{E}_{\pi}\bigg[\sum^{T-1}_{i=0}\max\{r(s_{i},a_{i}),0\}\,\Big|\,s_{0}=s\bigg] \displaystyle V_{\raisebox{1.35623pt}{$\mkern 1.0mu\scriptscriptstyle-$}}^{\pi}(s) \displaystyle=\lim_{T\rightarrow\infty}\mathbb{E}_{\pi}\bigg[\sum^{T-1}_{i=0}\max\{-r(s_{i},a_{i}),0\}\,\Big|\,s_{0}=s\bigg], where \mathbb{E}_{\pi} denotes expectation over trajectories (s_{0},a_{0},s_{1},a_{1},\dots,s_{T-1},a_{T-1}) induced by the policy \pi . Since both summands are nonnegative, the monotone convergence theorem guarantees that each limit exists (possibly infinite). To ensure the well-definedness of the value