# ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 57 of its 94 references that are in the map.
- First posted on arXiv 2 Feb 2023.

## Builds on (most cited first, 30 of 57)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Maximum a Posteriori Policy Optimisation](https://mlsanity.com/paper/1806.06920/) (2018)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Safe Exploration in Continuous Action Spaces](https://mlsanity.com/paper/1801.08757/) (2018)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Distributed Distributional Deterministic Policy Gradients](https://mlsanity.com/paper/1804.08617/) (2018)
- [Meta-Gradient Reinforcement Learning](https://mlsanity.com/paper/1805.09801/) (2018)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Mirror Descent Policy Optimization](https://mlsanity.com/paper/2005.09814/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)

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

- [Confronting Reward Model Overoptimization with Constrained RLHF](https://mlsanity.com/paper/2310.04373/) (2023)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [One-Shot Safety Alignment for Large Language Models via Optimal Dualization](https://mlsanity.com/paper/2405.19544/) (2024)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Learning Shared Safety Constraints from Multi-task Demonstrations](https://mlsanity.com/paper/2309.00711/) (2023)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [Alignment of large language models with constrained learning](https://mlsanity.com/paper/2505.19387/) (2025)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning](https://mlsanity.com/paper/2402.12711/) (2024)
- [Operator Splitting for Convex Constrained Markov Decision Processes](https://mlsanity.com/paper/2412.14002/) (2024)
- [A State Representation for Diminishing Rewards](https://mlsanity.com/paper/2309.03710/) (2023)
- [Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning](https://mlsanity.com/paper/2407.10775/) (2024)
- [Provably Efficient Exploration in Inverse Constrained Reinforcement Learning](https://mlsanity.com/paper/2409.15963/) (2024)
- [Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise](https://mlsanity.com/paper/2509.22500/) (2025)
- [Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins](https://mlsanity.com/paper/2602.10917/) (2026)
- [Acceleration in Policy Optimization](https://mlsanity.com/paper/2306.10587/) (2023)
- [Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs](https://mlsanity.com/paper/2309.15395/) (2023)
- [Handling Cost and Constraints with Off-Policy Deep Reinforcement Learning](https://mlsanity.com/paper/2311.18684/) (2023)
- [Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs](https://mlsanity.com/paper/2408.10015/) (2024)

## Abstract (arXiv)

In recent years, Reinforcement Learning (RL) has been applied to real-world problems with increasing success. Such applications often require to put constraints on the agent's behavior. Existing algorithms for constrained RL (CRL) rely on gradient descent-ascent, but this approach comes with a caveat. While these algorithms are guaranteed to converge on average, they do not guarantee last-iterate convergence, i.e., the current policy of the agent may never converge to the optimal solution. In practice, it is often observed that the policy alternates between satisfying the constraints and maximizing the reward, rarely accomplishing both objectives simultaneously. Here, we address this problem by introducing Reinforcement Learning with Optimistic Ascent-Descent (ReLOAD), a principled CRL method with guaranteed last-iterate convergence. We demonstrate its empirical effectiveness on a wide variety of CRL problems including discrete MDPs and continuous control. In the process we establish a benchmark of challenging CRL problems.