mlsanityData to 7 Oct 2026

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

arXiv 2206.05850 ↗First posted 12 Jun 2022cs.LG cs.AI cs.SYcited by 19

Not on the map. Why?

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.

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

Builds on

20 of 33 references.

References · 20

  1. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2017A Brief Survey of Deep Reinforcement Learningcited by 466
  5. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  6. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  7. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  8. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  9. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  10. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  11. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  12. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
8 more
  1. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  2. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  3. 2020Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimizationcited by 34
  4. 2020A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learningcited by 24
  5. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  6. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  7. 2020Conservative Stochastic Optimization with Expectation Constraintscited by 10
  8. 2020Provably Efficient Model-Free Algorithm for MDPs with Peak Constraintscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 7; 2025: 5; 2026: 3.

19 papers.

Sort:

  1. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  2. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  3. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  4. 2023A safe exploration approach to constrained Markov decision processescited by 10
  5. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  6. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  7. 2022Mean-Field Approximation of Cooperative Constrained Multi-Agent Reinforcement Learning (CMARL)cited by 5
  8. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Timecited by 5
  9. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  10. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  11. 2025Adaptive Shielding for Safe Reinforcement Learning under Hidden-Parameter Dynamics Shiftscited by 2
  12. 2023Enhancing Infrared Small Target Detection Robustness with Bi-Level Adversarial Frameworkcited by 1
7 more
  1. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  2. 2025Polynomial-Time Approximability of Constrained Reinforcement Learningcited by 1
  3. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  4. 2026Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizescited by 1
  5. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  6. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  7. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0