Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

• URL: http://arxiv.org/abs/2605.11694v1
• Date: Tue, 12 May 2026 07:51:18 GMT
• Title: Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
• Abstract summary: We study policy optimization for infinite-horizon, discounted constrained Markov decision processes (CMDPs)<n>We use the classic inexact augmented Lagrangian ($textttAL$) method from constrained optimization, and propose a general framework with provable last-iterate convergence for CMDPs.<n>We generalize these results to handle log-linear policies, and demonstrate that an efficient, projected variant of $textttPQA$ can achieve last-iterate convergence.
• Score: 7.237620866644061
• License: http://creativecommons.org/licenses/by/4.0/
• 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 ($\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.

Related papers

• Holder Policy Optimisation [26.521180498291717]
  textbfHlderPO is a generalised policy optimisation framework.<n>It unifies token-level probability aggregation via the Hlder mean.<n>It achieves a state-of-the-art average accuracy of $54.9%$ across multiple mathematical benchmarks.
  arXiv  Detail & Related papers  (2026-05-12T12:45:03Z)
• Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with $k$-step Policy Gradients [8.64427265159929]
  This work revisits standard policy gradient methods used on restricted policy classes.<n>We propose a generalized $k$-step policy gradient method that couples the randomness within a $k$-step time window.<n>We show this new method is theoretically guaranteed to converge to a solution that is exponentially close in performance to the optimal deterministic policy.
  arXiv  Detail & Related papers  (2026-05-11T17:49:09Z)
• Provably Efficient Sample Complexity for Robust CMDP [7.060086147428817]
  We study the problem of learning policies that maximize cumulative reward while satisfying safety constraints.<n>We focus on robust constrained Markov decision processes (RCMDPs), where the agent must maximize reward while ensuring cumulative utility exceeds a threshold.<n>We propose a novel Robust constrained Value iteration (RCVI) algorithm with a sample complexity of $mathcaltildeO(|S||A|H5/2)$ achieving at most $$ violations.
  arXiv  Detail & Related papers  (2025-11-10T04:40:37Z)
• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  We study reinforcement learning in the policy learning setting.<n>The goal is to find a policy whose performance is competitive with the best policy in a given class of interest.
  arXiv  Detail & Related papers  (2025-07-06T14:40:05Z)
• Mirror Descent Policy Optimisation for Robust Constrained Markov Decision Processes [12.666842349236788]
  This paper presents mirror descent policy optimisation for robust constrained Markov decision processes.<n>We make use of policy gradient techniques to optimise both the policy (as a maximiser) and the transition kernel (as an adversarial minimiser) on the Lagrangian.<n>Experiments confirm the benefits of mirror descent policy optimisation in constrained and unconstrained optimisation.
  arXiv  Detail & Related papers  (2025-06-29T09:55:52Z)
• Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation [52.772454746132276]
  We show that the approximation error in modeling problem-dependent quantities is irrelevant to the algorithm's global convergence.<n>We prove that $textttLin-SPG$ with any arbitrary constant learning rate can ensure global convergence to the optimal policy.
  arXiv  Detail & Related papers  (2025-05-06T04:03:06Z)
• Convergence of Policy Mirror Descent Beyond Compatible Function Approximation [66.4260157478436]
  We develop theoretical PMD general policy classes where we strictly assume a weaker variational dominance and obtain convergence to the best-in-class policy.<n>Our main notion leverages a novel notion induced by the local norm induced by the occupancy- gradient measure.
  arXiv  Detail & Related papers  (2025-02-16T08:05:46Z)
• Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
  The constrained Markov decision process (CMDP) framework emerges as an important reinforcement learning approach for imposing safety or other critical objectives.<n>In this paper, we address the learning problem given linear function approximation with $q_pi$-realizability.
  arXiv  Detail & Related papers  (2024-06-26T17:57:13Z)
• Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling [23.989009116398208]
  We design a low-switching sample-efficient policy optimization algorithm, LPO, with general non-linear function approximation. We show that, our algorithm obtains an $varepsilon$-optimal policy with only $widetildeO(fractextpoly(d)varepsilon3)$ samples.
  arXiv  Detail & Related papers  (2023-06-15T23:51:46Z)
• Fast Global Convergence of Policy Optimization for Constrained MDPs [17.825031573375725]
  We show that gradient-based methods can achieve an $mathcalO(log(T)/T)$ global convergence rate both for the optimality gap and the constraint violation. When Slater's condition is satisfied and known a priori, zero constraint violation can be further guaranteed for a sufficiently large $T$.
  arXiv  Detail & Related papers  (2021-10-31T17:46:26Z)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  We show that the preferability of optimization methods depends critically on whether exact gradients are used. Second, to explain these findings we introduce the concept of committal rate for policy optimization. Third, we show that in the absence of external oracle information, there is an inherent trade-off between exploiting geometry to accelerate convergence versus achieving optimality almost surely.
  arXiv  Detail & Related papers  (2021-10-29T06:35:44Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  The softmax policy gradient (PG) method is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. We demonstrate that softmax PG methods can take exponential time -- in terms of $mathcalS|$ and $frac11-gamma$ -- to converge.
  arXiv  Detail & Related papers  (2021-02-22T18:56:26Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation. We present an provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.
  arXiv  Detail & Related papers  (2020-03-01T17:47:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.