Research map / Reinforcement learning / MDPs and planning

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: Average-reward and regularized MDPs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes an inexact augmented Lagrangian framework with projected Q-ascent (and projected PQA with log-linear policies) as the subproblem oracle, giving last-iterate convergence guarantees for CMDPs in tabular and log-linear settings and empirical results on Safety-Gymnasium.

Problem

Policy optimization for constrained MDPs usually guarantees only mixture policies, while practice deploys last iterates, which primal-dual methods do not guarantee; existing last-iterate methods are either impractical or restricted to simplified settings.

Approach

Uses the classic inexact augmented Lagrangian method, solving each non-concave AL subproblem with projected Q-ascent (PQA) over the occupancy-measure view, and extends to function approximation via a surrogate forward-KL projection so any PG method (PPO, SPMA) can solve the subproblem.

Key results

• Tabular PQA-ALM attains O(1/epsilon^6) total policy gradient evaluations for last-iterate epsilon-optimal stochastic policy.
• PPQA-ALM with log-linear policies (d=60) reliably converges to the optimal policy while Lin-RPG-PD and ReLOAD perform poorly.
• On Safety-Gymnasium continuous control, the framework performs comparably to PPO-Lag and CPO.

Surprising findings

• Lin-RPG-PD and ReLOAD perform poorly on the log-linear tabular-style experiment, while PPQA-ALM converges reliably.

Limitations

• Strong dependence on rho_min in the tabular setting.
• Strong dependence on the projection bias epsilon_bias for log-linear policies.
• Actor-critic and off-policy variants are not covered by the theory.

Experimental setup

Datasets: Safety-Gymnasium

Benchmarks: Safety-Gymnasium tabular CMDP environment

Metrics: optimality gap constraint violation return cost

Baselines: NPG-PD Lin-RPG-PD ReLOAD PPO-Lag CPO

Builds on: augmented Lagrangian method primal-dual policy optimization projected policy gradient PPO-Lag CPO

Closest papers by meaning

• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.90)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.90)
• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 2025 · similarity 0.90)
• On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.89)
• Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.89)
• Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.88)