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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 47 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## 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, 4 of 4)

- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins](https://mlsanity.com/paper/2602.10917/) (2026)
- [Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs](https://mlsanity.com/paper/2605.11694/) (2026)

## Abstract (arXiv)

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.