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

Nam Phuong Tran; Trinh Ha Mai Huynh; Tuyen Pham Le; Van-Truong Nguyen; Quan Nguyen; Long Tran-Thanh

cs.LGSep 26, 2026

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

Authors: Nam Phuong Tran, Trinh Ha Mai Huynh, Tuyen Pham Le, Van-Truong Nguyen, Quan Nguyen, Long Tran-Thanh

Organizations: Inria centre at the University of Lille Lille, France · Vin Motion Vietnam · Department of Computer Science University of Warwick Coventry, United Kingdom

Abstract

In safety-critical applications, deployment uses a single policy, whose performance and constraint satisfaction should hold directly rather than only for an average or mixture of training policies. This motivates last-iterate guarantees in constrained reinforcement learning. Recent progress has established such guarantees in exact-gradient or tabular online settings, yet scalable results for structured large-state problems remain open. We develop a general, statistically efficient framework for last-iterate convergence in structured Constrained MDPs (CMDPs). Our analysis separates contraction of the regularised primal-dual dynamics from actor approximation and statistical errors in policy evaluation under online exploration. This enables model-free on- and off-policy learning with structured function approximation: optimistic policy evaluation avoids explicit transition-model construction, while a compact parametric actor avoids maintaining mixtures or histories of past policies. We instantiate the framework for linear CMDPs and general function approximation, obtaining representation-dependent complexity and improved target-accuracy dependence over prior optimistic regularised primal-dual analyses. We further validate the stabilising effect predicted by our theory on a synthetic linear CMDP: the regularised method exhibits stable last-iterate behaviour, whereas its unregularised counterpart shows larger oscillations.

Figures & tables

	$\displaystyle Q_{j,h}^{k}$	$\displaystyle=\mathrm{Truncate}_{[0,H+1-h]}\bigl(\langle\phi,\widehat{\theta}_{j,h}^{k}\rangle+b_{j,h}^{k}\bigr),$		(13)
	$\displaystyle Q_{\psi,h}^{k}(s,a)$	$\displaystyle=\psi_{k,h}(s,a)+\mathrm{Truncate}_{[0,(H-h)\log\|\mathcal{A}\|]}\bigl(\langle\phi(s,a),\widehat{\theta}_{\psi,h}^{k}\rangle+b_{\psi,h}^{k}(s,a)\bigr).$		(13)

Algorithm 2 Linear

\mathrm{OPE}(\pi^{k},\lambda_{k},\mathcal{D})

Figure 1: Online last-iterate performance in the synthetic linear CMDP over

1.5\times 10^{4}

policy updates.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	Sample complexity	Model free	Structured CMDPs
Müller et al. [2024]	$\widetilde{O}(\epsilon^{-14})$	✗	✗
Kitamura et al. [2024]	$\widetilde{O}(\epsilon^{-7})$	✗	✗
Zuo et al. [2026]	$\widetilde{O}(\epsilon^{-6})$	✗	✗
This work (off-policy)	$\widetilde{O}(\epsilon^{-6})$	✓	✓
This work (on-policy)	$\widetilde{O}(\epsilon^{-10})$	✓	✓
Lower bound Domingues et al. [2021]	$\widetilde{O}(\epsilon^{-2})$	—	—

Appendix

Table A: Comparison of online CMDP results with last-iterate guarantees for the final policy. We include only works that explicitly account for exploration through online interaction with an unknown CMDP. For a fair comparison with these prior tabular, model-based results, we report sample complexity in the tabular setting using one-hot state-action features for the actor and critic, with

\epsilon_{\rm act}=0

. Sample complexity counts the complete episodes required to obtain an

O(\epsilon)

-optimal,

O(\epsilon)

-feasible final policy. Rates suppress logarithmic factors and dependence on problem parameters other than

\epsilon

. The Structured CMDPs column identifies guarantees based on features or function classes, while Model free indicates that the method does not explicitly estimate the transition kernel.

R_{\mathcal{F}}=\sup_{x\in\mathcal{X}}\sup_{f,g\in\mathcal{F}}|f(x)-g(x)|.

Appendix

Algorithm 3

\mathrm{StableBonus}(\mathcal{F},\overline{f},Z,\alpha,M,\delta_{0})

Figure 2: On-policy last-iterate performance for one seed. Solid and dashed curves denote the regularised and unregularised methods, both trained at

c

Figure 3: Off-policy last-iterate performance for one seed, using the same panels, visual encoding, and axis limits as Figure 2 .

Sampling mode	Regularised	Unregularised
On-policy	$0.0027\,[0.0023,\,0.0037]$	$0.2234\,[0.2199,\,0.2247]$
Off-policy	$0.0068\,[0.0052,\,0.0084]$	$0.1790\,[0.0794,\,0.3122]$

Appendix

Table B: Late-training fluctuations of the signed constraint gap. For each run, we sort the recorded gaps during updates

13{,}000

–

15{,}000

, discard the lowest and highest

10\%

, and measure the width of the remaining values. Each entry gives the median width across

30

seeds, with the [25th, 75th] percentiles in brackets.

Function Approximation in RL

See all 22 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
Near-Optimal Sample Complexity for Online Constrained MDPs
Feb 16, 2026Chang Liu, Yunfan Li, Lin F. YangConstrained RL Safe RL
University of California, Los Angeles
Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
Sep 24, 2025Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni +2Markov Decision Processes Constrained RL
Politecnico di Milano

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

Function Approximation in RL

Explore similar work

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

Near-Optimal Sample Complexity for Online Constrained MDPs

Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints