# Constrained Reinforcement Learning Has Zero Duality Gap

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

## Key facts

- Cited by 151 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2019.

## Built on by (most cited first, 30 of 151)

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Confronting Reward Model Overoptimization with Constrained RLHF](https://mlsanity.com/paper/2310.04373/) (2023)
- [Penalized Proximal Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/2205.11814/) (2022)
- [Constrained Update Projection Approach to Safe Policy Optimization](https://mlsanity.com/paper/2209.07089/) (2022)
- [Constrained Learning with Non-Convex Losses](https://mlsanity.com/paper/2103.05134/) (2021)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Chasing Moving Targets with Online Self-Play Reinforcement Learning for Safer Language Models](https://mlsanity.com/paper/2506.07468/) (2025)
- [On the Robustness of Safe Reinforcement Learning under Observational Perturbations](https://mlsanity.com/paper/2205.14691/) (2022)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizability](https://mlsanity.com/paper/2209.08025/) (2022)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [A Survey on Autonomy-Induced Security Risks in Large Model-Based Agents](https://mlsanity.com/paper/2506.23844/) (2025)
- [MuZero with Self-competition for Rate Control in VP9 Video Compression](https://mlsanity.com/paper/2202.06626/) (2022)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithms](https://mlsanity.com/paper/2310.03225/) (2023)
- [DiffCPS: Diffusion Model based Constrained Policy Search for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.05333/) (2023)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Density Constrained Reinforcement Learning](https://mlsanity.com/paper/2106.12764/) (2021)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [CUP: A Conservative Update Policy Algorithm for Safe Reinforcement Learning](https://mlsanity.com/paper/2202.07565/) (2022)
- [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://mlsanity.com/paper/2302.01275/) (2023)
- [Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process](https://mlsanity.com/paper/2110.10351/) (2021)
- [Safe Model-Based Reinforcement Learning with an Uncertainty-Aware Reachability Certificate](https://mlsanity.com/paper/2210.07553/) (2022)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Lexicographic Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2212.13769/) (2022)
- [TGRL: An Algorithm for Teacher Guided Reinforcement Learning](https://mlsanity.com/paper/2307.03186/) (2023)

## Abstract (arXiv)

Autonomous agents must often deal with conflicting requirements, such as completing tasks using the least amount of time/energy, learning multiple tasks, or dealing with multiple opponents. In the context of reinforcement learning~(RL), these problems are addressed by (i)~designing a reward function that simultaneously describes all requirements or (ii)~combining modular value functions that encode them individually. Though effective, these methods have critical downsides. Designing good reward functions that balance different objectives is challenging, especially as the number of objectives grows. Moreover, implicit interference between goals may lead to performance plateaus as they compete for resources, particularly when training on-policy. Similarly, selecting parameters to combine value functions is at least as hard as designing an all-encompassing reward, given that the effect of their values on the overall policy is not straightforward. The later is generally addressed by formulating the conflicting requirements as a constrained RL problem and solved using Primal-Dual methods. These algorithms are in general not guaranteed to converge to the optimal solution since the problem is not convex. This work provides theoretical support to these approaches by establishing that despite its non-convexity, this problem has zero duality gap, i.e., it can be solved exactly in the dual domain, where it becomes convex. Finally, we show this result basically holds if the policy is described by a good parametrization~(e.g., neural networks) and we connect this result with primal-dual algorithms present in the literature and we establish the convergence to the optimal solution.