# Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 12 Jun 2022.

## Builds on (most cited first, 20 of 20)

- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization](https://mlsanity.com/paper/2003.01303/) (2020)
- [A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning](https://mlsanity.com/paper/2006.04338/) (2020)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Conservative Stochastic Optimization with Expectation Constraints](https://mlsanity.com/paper/2008.05758/) (2020)
- [Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints](https://mlsanity.com/paper/2003.05555/) (2020)

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

- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs](https://mlsanity.com/paper/2404.02108/) (2024)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm](https://mlsanity.com/paper/2402.02042/) (2024)
- [Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm](https://mlsanity.com/paper/2505.15138/) (2025)
- [Mean-Field Approximation of Cooperative Constrained Multi-Agent Reinforcement Learning (CMARL)](https://mlsanity.com/paper/2209.07437/) (2022)
- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)
- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (2025)
- [Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning](https://mlsanity.com/paper/2407.10775/) (2024)
- [Anytime Safe Reinforcement Learning](https://mlsanity.com/paper/2504.16417/) (2025)
- [Adaptive Shielding for Safe Reinforcement Learning under Hidden-Parameter Dynamics Shifts](https://mlsanity.com/paper/2506.11033/) (2025)
- [Enhancing Infrared Small Target Detection Robustness with Bi-Level Adversarial Framework](https://mlsanity.com/paper/2309.01099/) (2023)
- [Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs](https://mlsanity.com/paper/2408.11513/) (2024)
- [Anytime-Constrained Equilibria in Polynomial Time](https://mlsanity.com/paper/2410.23637/) (2024)
- [Polynomial-Time Approximability of Constrained Reinforcement Learning](https://mlsanity.com/paper/2502.07764/) (2025)
- [Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs](https://mlsanity.com/paper/2511.05758/) (2025)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization](https://mlsanity.com/paper/2603.07698/) (2026)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)

## Abstract (arXiv)

We consider the problem of constrained Markov decision process (CMDP) in continuous state-actions spaces where the goal is to maximize the expected cumulative reward subject to some constraints. We propose a novel Conservative Natural Policy Gradient Primal-Dual Algorithm (C-NPG-PD) to achieve zero constraint violation while achieving state of the art convergence results for the objective value function. For general policy parametrization, we prove convergence of value function to global optimal upto an approximation error due to restricted policy class. We even improve the sample complexity of existing constrained NPG-PD algorithm citeDing2020 from O(1/ε6) to O(1/ε4). To the best of our knowledge, this is the first work to establish zero constraint violation with Natural policy gradient style algorithms for infinite horizon discounted CMDPs. We demonstrate the merits of proposed algorithm via experimental evaluations.