Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

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

Read Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs by Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani (2026) 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-2605-11694.txt.

Introduction

Michael Lu and three colleagues close a practical gap in constrained reinforcement learning. Theory usually guarantees only a mixture policy, yet deployment needs one single policy. Their framework adapts the classic augmented Lagrangian method to constrained Markov decision processes and proves that the last policy in the sequence converges. It works first for tabular settings, then for log-linear and complex nonlinear policies, and it scales to continuous control tasks.

Catalog record

CREATORMichael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE157586
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11694

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani Abstract 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 ( 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 AL sub-problem with projected Q-ascent ( PQA ). Combining the theoretical guarantees of PQA and the standard 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 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. 1 Introduction Reinforcement Learning (RL) has found success in a variety of applications such as video games ( Mnih et al. 2015 ) , robotics ( Kober et al. 2013 ) and fine-tuning large language models ( Uc-Cetina et al. 2023 ) . While standard RL algorithms are typically designed to optimize a single performance objective, real-world systems must also operate under operational and safety constraints. For instance, in a wireless communication system, a network controller aims to maximize the bitrate delivered to users while ensuring that total energy consumption does not exceed a given budget ( Julian et al. 2002 ; Buratti et al. 2009 ) . A common approach is to model such problems as a constrained Markov decision process (CMDP) ( Altman 2021 ) . In this setting, an agent must maximize a cumulative reward (e.g. bitrate), while ensuring that the cumulative constraint reward (e.g. energy consumption) satisfies a prescribed threshold. Unlike standard MDPs, the optimal policies for CMDPs are stochastic, making it challenging to design algorithms that reliably recover a near-optimal policy. A typical algorithmic template ( Jain et al. 2022 ; Liu et al. 2025b ; Ding et al. 2020 ; Bura et al. 2022 ) to solve CMDPs is to form the Lagrangian and iteratively perform alternating updates of the policy (primal variable) and the associated Lagrange multipliers (dual variable). While such primal–dual ( PD ) methods are guaranteed to output a policy that maximizes the reward while satisfying the constraints, such guarantees only hold for the mixture policy . In particular, PD methods iteratively generate a sequence of policies, and maintaining a mixture policy requires storing all intermediate policies, making this approach memory intensive. Moreover, in order to deploy a mixture policy, a policy is randomly sampled from the set of intermediate policies, and the theoretical guarantees hold in expectation over this random selection. From a safety perspective, relying on such a mixture policy can be dangerous, because an individual sampled policy may significantly violate the constraints. Consequently, practitioners use PD methods and deploy the final policy, trading theoretical guarantees for ease of implementation. Unfortunately, this practical variant is typically sensitive to hyper-parameters and the final policy can exhibit oscillatory behavior (for example, see Fig. 1 ). This concern has motivated recent works ( Ding et al. 2023 ; Mondal and Aggarwal 2024b ; Müller et al. 2024 ; Moskovitz et al. 2023 ; Ying et al. 2022 ; Montenegro et al. 2024 ) that aim to design iterative approaches that have theoretical guarantees for the final stochastic policy. Such last-iterate convergence is desirable from both a theoretical and empirical perspective. All such recent works rely on adding additional regularization to both the primal and dual variables. Despite their theoretical appeal, these last-iterate algorithms are either difficult to implement in practice, or are designed for simplified settings, limiting their applicability. In fact, to the best of our knowledge, there is no last-iterate algorithm that is both principled (has guarantees in simplified settings) and practical (can be efficiently implemented for large problems). Motivated by this gap, and in contrast to the previous work on last-iterate convergence, we employ the augmented Lagrangian ( AL ) method . Such methods are a classic approach in the constrained optimization literature, and are widely used in practice (see Deng et al. 2025 for a recent survey). Under suitable assumptions, AL methods enjoy strong theoretical guarantees, including last-iterate global convergence ( Xu 2021 ; Liu et al. 2019 ) . Empirically, AL methods tend to be stable and more robust when compared to common PD approaches ( Birgin and Martínez 2014 ) . For example, Fig. 1 shows that the final policy produced by our proposed AL -based approach attains convergence to the optimal policy (the optimality gap is small) and satisfies the constraints more reliably when compared to the PD approach in Ding et al. 2020 . Figure 1 : Comparing the proposed AL method ( PPG-ALM ) to the primal-dual approach ( NPG-PD ) ( Ding et al. 2020 ) on a tabular environment. While the iterates of NPG-PD oscillate, PPG-ALM results in smooth convergence to zero optimality gap and constraint violation. We note that such AL methods have been previously used for solving CMDPs. However, prior work either uses the AL method only as inspiration, without providing theoretical guarantees ( Dai et al. 2023 ; Li et al. 2021 ) , or is restricted to simplistic settings and relies on computationally expensive procedures that do not scale in practice ( Müller et al. 2023 ) . Consequently, our objective is to develop a general, practical and theoretically principled AL framework for last-iterate convergence in CMDPs . To this end, we make the following contributions. Contribution 1 : In Section 3 , we introduce a generic inexact AL framework for solving CMDPs. Each iteration of the algorithm requires computing an approximate solution to a non-concave AL subproblem . Assuming access to an inexact solver for the subproblem, we prove that this framework requires {\mathcal{O}}(\nicefrac{{1}}{{\varepsilon^{2}}}) iterations to output an \varepsilon -optimal policy (which simultaneously achieves an \varepsilon optimality-gap and constraint violation) for the CMDP. This modular design separates the AL analysis from the choice of the subproblem solver, enabling flexibility across a range of settings. Contribution 2 : We first consider the tabular setting where the number of parameters scales with the size of the state-action space, and propose to solve the AL subproblem using policy optimization. In Section 4.1 , we show the policy gradient of the AL subproblem involves policy-dependent, non-stationary pseudo-rewards . We use projected Q-ascent ( PQA ) ( Xiao 2022 ; Liu et al. 2025a ) which yields last-iterate convergence guarantees for the AL subproblem. In Section 4.2 , we combine these results with the standard AL analysis ( Liu et al. 2019 ) , resulting in last-iterate guarantees for the CMDP. Specifically, for a target \varepsilon>0 , the proposed algorithm requires {\mathcal{O}}(\nicefrac{{1}}{{\varepsilon^{6})}} policy gradient evaluations to obtain an \varepsilon

Read the complete text