Last-Iterate Convergence for Constrained Reinforcement Learning

This direction is merged into another direction: Lagrangian optimization instability. Its last version stays readable and citable here.

Version 1 of 120 papers32 conceptsfrozen 2026-10-04

In standard Reinforcement Learning (RL), an agent's only goal is to maximize a reward signal. However, real-world deployment often requires satisfying strict safety or resource constraints—modeled as Constrained Markov Decision Processes (CMDPs). While researchers have long used primal-dual methods to solve these problems, a persistent gap has remained between theory and practice: most algorithms only guarantee that the agent is safe on average over the course of training, rather than ensuring the final, deployed policy is safe.

A recent wave of research has solved this "oscillation" problem by using regularized primal-dual frameworks, ensuring that the very last iteration of training produces an optimal and feasible policy.

The Problem of Policy Oscillation

To solve a CMDP, we typically use a Lagrangian approach. We turn the constrained problem into an unconstrained one by adding a penalty term: the reward minus a "cost" multiplied by a Lagrange multiplier (the dual variable). If the agent violates a constraint, the dual variable increases, making the penalty more severe.

In theory, this creates a "game" where the primal player (the policy) tries to maximize the Lagrangian and the dual player (the multiplier) tries to minimize it. However, as noted by Adrian Müller and Niao He in Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes, standard linear dual methods suffer from "error cancellations." An agent might be dangerously reckless in one episode and overly cautious in the next. Mathematically, the average is safe, but any single policy iteration might be disastrous.

This behavior occurs because the standard Lagrangian is linear with respect to the dual variables. In optimization terms, the landscape lacks the "curvature" needed to pull the iterates toward a single stable point, leading to perpetual cycles around the optimum.

Bending the Landscape with Regularization

The core insight of recent work is to "bend" this optimization landscape using regularization. By adding quadratic penalties to the dual variables—often called Ridge Regularization—researchers transform the dual objective from merely concave to strongly concave.

As explained by Dongsheng Ding and Alejandro Ribeiro in Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs, this dual regularization acts as a stabilizer. It prevents the Lagrange multipliers from over-reacting to small constraint violations, which in turn prevents the policy from oscillating wildly between feasible and infeasible regions.

When combined with primal regularization (like entropy terms that make the policy objective strongly convex), the entire problem becomes a strongly-convex-strongly-concave saddle point problem. This structural change is what enables last-iterate convergence: the current policy is guaranteed to move directly toward the optimal safe solution and stay there.

From Theory to Real-World Control

This shift from "average" to "last-iterate" convergence has profound implications for different types of systems:

Why It Works: The Intuition of Damped Feedback

Think of standard primal-dual optimization as a thermostat that only has two settings: "Full Blast" and "Off." If the room is too cold, it blasts heat until it's too hot, then shuts off until it's too cold again. The temperature oscillates, and while the average temperature might be 70 degrees, the room is rarely comfortable.

Regularized primal-dual methods, such as the PDR-ANPG algorithm proposed by Washim Uddin Mondal and Vaneet Aggarwal, act like a modern PID controller. The quadratic penalty provides continuous, proportional feedback. As the agent approaches the constraint boundary, the "pressure" from the dual variable increases smoothly rather than abruptly. This creates a damped system that settles into an equilibrium—the optimal safe policy—rather than orbiting it forever.

By transforming the underlying geometry of the CMDP objective, this research direction has turned constrained RL from a volatile balancing act into a stable, convergent numerical process.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_last_iterate_convergence_for_constrained_37080f15,
  title = {Last-Iterate Convergence for Constrained Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/last-iterate-convergence-for-constrained-reinforcement-learning/rdr_37080f15b12d4a78a17fda94b20d761f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_last_iterate_convergence_for_constrained_37080f15_v1,
  title = {Last-Iterate Convergence for Constrained Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/last-iterate-convergence-for-constrained-reinforcement-learning/rdr_37080f15b12d4a78a17fda94b20d761f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}