Last-Iterate Convergence for Constrained MDPs: From Dual Descent to Primal-Dual

Michael Lu; Max Qiushi Lin; Mo Chen; Sharan Vaswani

cs.LGOct 29, 2026

Last-Iterate Convergence for Constrained MDPs: From Dual Descent to Primal-Dual

Authors: Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani

Organizations: Simon Fraser University · Canada CIFAR AI Chair, Amii, Simon Fraser University

Abstract

We study policy optimization for infinite-horizon, discounted constrained Markov decision processes. While primal-dual ( $\texttt{PD}$ ) methods are widely used in practice, their theoretical guarantees typically hold for an impractical mixture policy. In contrast, dual descent ( $\texttt{DD}$ ) methods output a single policy ("last iterate") with guarantees on its performance. However, such methods require iteratively solving entropy-regularized MDPs in an inner-loop, limiting their practical effectiveness. Moreover, existing analyses rely on strong coverage assumptions that are difficult to satisfy in practice. Consequently, we first provide a new analysis of $\texttt{DD}$ methods that does not require coverage assumptions. We then employ entropy-regularized natural policy gradient and dual regularization to eliminate the inner loop, resulting in an efficient $\texttt{PD}$ algorithm. We develop a novel tracking analysis which shows that, compared to existing methods, the proposed algorithm achieves improved last-iterate convergence guarantees. Furthermore, our theoretical framework allows us to analyze a truncated bilevel method that interpolates between $\texttt{DD}$ and $\texttt{PD}$ methods. Finally, we generalize our analysis to handle linear function approximation. Compared to prior last-iterate methods, we prove stronger guarantees under less restrictive assumptions.

Figures & tables

Figure 1: Comparing a PD approach ( NPG-PD ) ( Ding et al., 2020 ) to the proposed DD method ( DD(K=1) ) on a 2-armed constrained bandit problem. While the iterates of NPG-PD oscillate, DD(K=1) converges to zero optimality gap and constraint violation. See Section J.1 for details.

Figure 2: Comparing our regularized inexact DD method DD (K=1) when $K=1$ , $\mu>0$ and warm-starting the initial policy with $50$ iterations. We compare against the following practical last-iterate methods from prior work: RPG-PD ( Ding et al., 2023 ) , PQA-ALM ( Lu et al., 2026 ) , NPG-NRL ( Müller et al., 2024 ) , ReLoad ( Moskovitz et al., 2023 ) , and the related DD method of Ying et al. (2022) ( DD (Nesterov) ) For all methods, the hyper-parameters were selected via a grid-search (see Section J.2 for details) We select the best variant such that the final policy satisfies $b-V^{\pi}_{c}(\rho)\leq 0.001$ . Our method converges towards zero optimality gap and constraint violation the fastest without any oscillations.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	Number of Inner-Iterations Using NPG
Dual Objective	$K={\mathcal{O}}(\ln(\nicefrac{{1}}{{{\epsilon}}}))$	$K=1$	$K\geq 1^{\dagger}$
Smooth	$\tilde{{\mathcal{O}}}(\frac{1}{{\epsilon}^{4}})$ [ Theorem 1 ]	$\tilde{{\mathcal{O}}}(\frac{1}{{\epsilon}^{7}})$ [ Theorem 5 ]	$\tilde{{\mathcal{O}}}\left\lparen\frac{1}{{\epsilon}^{4+\frac{3}{2^{K}}}}\right\rparen$ [ Theorem 6 ]
Smooth + $\ell_{2}$ -regularized	$\tilde{{\mathcal{O}}}(\frac{1}{{\epsilon}^{2}})$ [ Theorem 2 ]	$\tilde{{\mathcal{O}}}(\frac{1}{{\epsilon}^{5}})$ [ Theorem 3 ]	$\tilde{{\mathcal{O}}}\left\lparen\frac{1}{{\epsilon}^{2+\frac{3}{2^{K}}}}\right\rparen$ [ Theorem 4 ]

Appendix

Table 2: Total number of gradient evaluations required to obtain an

{\mathcal{O}}({\epsilon})

-optimal policy to Problem 1 . The columns correspond to different numbers of NPG steps

K

used for each dual update. The dagger (

\dagger

) indicates result rate requires an additional

{\mathcal{O}}(\ln(\nicefrac{{1}}{{{\epsilon}}}))

gradient evaluations.

Figure 3: Visualization of the optimal policy for the cliff world environment. A longer arrows indicates a higher the probability of taking a particular action.

Figure 4: Visualization of the optimal policy for the deep sea treasure environment. A longer arrows indicates a higher the probability of taking a particular action.

Panel of Figure 5 — Figure 5: Comparing our regularized inexact DD method DD (K=1) when $K=1$ , $\mu>0$ and warm-starting the initial policy with $50$ iterations. We compare against the following practical last-iterate methods from prior work: RPG-PD Ding et al. [2023] , PQA-ALM Lu et al. [2026] , NPG-NRL Müller et al. [2024] , ReLoad Moskovitz et al. [2023] , and the related DD method of Ying et al. Ying et al. [2022] ( DD (Nesterov) ). Our method converges steadily to zero optimality gap and constraint violations without any oscillations

Method	Fixed Params.	Grid Search Space
DD (K=1)	$T=950$ , $K=1$ , $J=50$ , $\tau=\mu=0.0001$	Dual step-size ( $\beta)$ : $\{0.0001,0.001,0.01,0.1\}$
	Warm-up iterations=50
PQA-ALM	$T=10$ , $K=100$ , $\beta=10$	Primal step-size: $\{0.1,1,10\}$
RPG-PD [ Ding et al., 2023 ]	$T=1000$	Entropy Coefficient $\{10^{-4},10^{-2},10^{-1}\}$
		Primal step-size: $\{0.01,0.1,1,10,100\}$
		Dual step-size: $\{0.01,0.1,1,10,100\}$

Appendix

Table 3: Grid search ranges for the tabular experiments

Last-Iterate Convergence

Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.

See all 43 papers

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
May 12, 2026Michael Lu, Max Qiushi Lin, Mo Chen +1Markov Decision Processes Last-Iterate Convergence
Simon Fraser University
Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs
Sep 26, 2026Nam Phuong Tran, Trinh Ha Mai Huynh, Tuyen Pham Le +3Function Approximation in RL Reinforcement Learning
Inria centre at the University of Lille Lille, France · Vin Motion Vietnam · Department of Computer Science University of Warwick Coventry, United Kingdom
Fast Regularized Policy Mirror Descent with One-Step TD Updates
Sep 30, 2026Qipei Chen, Wenye Li, Yule Sun +1Markov Decision Processes Policy Optimization
School of Mathematical Sciences, Fudan University · School of Data Science, Fudan University

May 12, 2026J/K move · Enter open · S save

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani

Simon Fraser University

Markov Decision Processes Last-Iterate Convergence Policy Optimization Constrained RL Convergence Analysis Augmented Lagrangian Method+1

Open paper AskPDF arXiv

We study policy optimization for infinite-horizon, discounted constrained Markov decision processes (CMDPs). While existing theoretical guarantees typically hold for the mixture policy, deploying such a policy is computationally and memory intensive. This leads to a practical mismatch where a single (last-iterate) policy must be deployed. Recent theoretical works have thus focused on proving last-iterate convergence, but are largely limited to the tabular setting or to algorithmic variants that are rarely used in practice. To address this, we use the classic inexact augmented Lagrangian (

\texttt{AL}

) method from constrained optimization, and propose a general framework with provable last-iterate convergence for CMDPs. We first focus on the tabular setting and propose to solve the

\texttt{AL}

sub-problem with projected Q-ascent (

\texttt{PQA}

). Combining the theoretical guarantees of

\texttt{PQA}

and the standard

\texttt{AL}

analysis enables us to establish global last-iterate convergence. We generalize these results to handle log-linear policies, and demonstrate that an efficient, projected variant of

\texttt{PQA}

can achieve last-iterate convergence with comparable guarantees as prior work. Finally, we demonstrate that our framework scales to complex non-linear policies, and evaluate it on continuous control tasks.

Abstract

Last-Iterate Convergence

Explore similar work

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs

Fast Regularized Policy Mirror Descent with One-Step TD Updates