mlsanityData to 7 Oct 2026

Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach

arXiv 2109.06332 ↗First posted 13 Sep 2021cs.LGcited by 46

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning is widely used in applications where one needs to perform sequential decisions while interacting with the environment. The problem becomes more challenging when the decision requirement includes satisfying some safety constraints. The problem is mathematically formulated as constrained Markov decision process (CMDP). In the literature, various algorithms are available to solve CMDP problems in a model-free manner to achieve ε-optimal cumulative reward with ε feasible policies. An ε-feasible policy implies that it suffers from constraint violation. An important question here is whether we can achieve ε-optimal cumulative reward with zero constraint violations or not. To achieve that, we advocate the use of randomized primal-dual approach to solve the CMDP problems and propose a conservative stochastic primal-dual algorithm (CSPDA) which is shown to exhibit tildeOleft(1/ε2right) sample complexity to achieve ε-optimal cumulative reward with zero constraint violations. In the prior works, the best available sample complexity for the ε-optimal policy with zero constraint violation is tildeOleft(1/ε5right). Hence, the proposed algorithm provides a significant improvement as compared to the state of the art.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). Builds on 19 of its 36 references that are in the map. First posted on arXiv 13 Sep 2021.

Builds on

19 of 36 references.

References · 19

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2017A Brief Survey of Deep Reinforcement Learningcited by 466
  6. 2018Reward Constrained Policy Optimizationcited by 397
  7. 2020Exploration-Exploitation in Constrained MDPscited by 146
  8. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  9. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  10. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  12. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
7 more
  1. 2020Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimizationcited by 34
  2. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  3. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  4. 2020Cautious Reinforcement Learning via Distributional Risk in the Dual Domaincited by 18
  5. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  6. 2020Conservative Stochastic Optimization with Expectation Constraintscited by 10
  7. 2014Joint Latency and Cost Optimization for Erasure-coded Data Center Storagecited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 10; 2023: 11; 2024: 13; 2025: 10; 2026: 2.

46 papers.

Sort:

By area:

  1. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  2. 2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 54
  3. 2024A Survey of Constraint Formulations in Safe Reinforcement Learningcited by 42
  4. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  5. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  6. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  7. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  8. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  9. 2023Long-Term Fairness with Unknown Dynamicscited by 25
  10. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  11. 2023Trust Region-Based Safe Distributional Reinforcement Learning for Multiple Constraintscited by 20
  12. 2022Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learningcited by 15
34 more
  1. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  2. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  3. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  4. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  5. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  6. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  7. 2023A safe exploration approach to constrained Markov decision processescited by 10
  8. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  9. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  10. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  11. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  12. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  13. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 6
  14. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  15. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  16. 2023Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Explorationcited by 5
  17. 2024Spectral-Risk Safe Reinforcement Learning with Convergence Guaranteescited by 5
  18. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  19. 2022Learning Globally Smooth Functions on Manifoldscited by 4
  20. 2024Conflict-Averse Gradient Aggregation for Constrained Multi-Objective Reinforcement Learningcited by 4
  21. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  22. 2022Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamicscited by 3
  23. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 3
  24. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  25. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraintscited by 2
  26. 2025Constrained Sliced Wasserstein Embeddingcited by 2
  27. 2024Sampling-based Safe Reinforcement Learning for Nonlinear Dynamical Systemscited by 1
  28. 2025AL-CoLe: Augmented Lagrangian for Constrained Learningcited by 1
  29. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  30. 2026Dyna-Style Safety Augmented Reinforcement Learning: Staying Safe in the Face of Uncertaintycited by 1
  31. 2024Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learningcited by 0
  32. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  33. 2025Temporally smoothed incremental model-based heuristic dynamic programming for command-filtered cascaded online learning flight controlcited by 0
  34. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Marginscited by 0