# Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

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

## Key facts

- Cited by 1 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 12 of its 62 references that are in the map.
- First posted on arXiv 12 May 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, 12 of 12)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Benchmarking Batch Deep Reinforcement Learning Algorithms](https://mlsanity.com/paper/1910.01708/) (2019)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Gymnasium: A Standard Interface for Reinforcement Learning Environments](https://mlsanity.com/paper/2407.17032/) (2024)
- [A general class of surrogate functions for stable and efficient reinforcement learning](https://mlsanity.com/paper/2108.05828/) (2021)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model](https://mlsanity.com/paper/2507.02089/) (2025)
- [Dissecting Discrete Soft Actor-Critic: Limitations and Principled Alternatives](https://mlsanity.com/paper/2509.09838/) (2025)
- [The Augmented Lagrangian Methods: Overview and Recent Advances](https://mlsanity.com/paper/2510.16827/) (2025)
- [Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs](https://mlsanity.com/paper/2408.11513/) (2024)
- [Smoothness of the Augmented Lagrangian Dual in Convex Optimization](https://mlsanity.com/paper/2505.01824/) (2025)

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

- [Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs](https://mlsanity.com/paper/2609.32933/) (2026)

## Abstract (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 (textttAL) 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 textttAL sub-problem with projected Q-ascent (textttPQA). Combining the theoretical guarantees of textttPQA and the standard textttAL 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 textttPQA 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.