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

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

## Key facts

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

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

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [A Primal-Dual Approach to Constrained Markov Decision Processes](https://mlsanity.com/paper/2101.10895/) (2021)
- [Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization](https://mlsanity.com/paper/2003.01303/) (2020)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [Cautious Reinforcement Learning via Distributional Risk in the Dual Domain](https://mlsanity.com/paper/2002.12475/) (2020)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Conservative Stochastic Optimization with Expectation Constraints](https://mlsanity.com/paper/2008.05758/) (2020)
- [Joint Latency and Cost Optimization for Erasure-coded Data Center Storage](https://mlsanity.com/paper/1404.4975/) (2014)

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

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments](https://mlsanity.com/paper/2209.15090/) (2022)
- [A Survey of Constraint Formulations in Safe Reinforcement Learning](https://mlsanity.com/paper/2402.02025/) (2024)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Long-Term Fairness with Unknown Dynamics](https://mlsanity.com/paper/2304.09362/) (2023)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Trust Region-Based Safe Distributional Reinforcement Learning for Multiple Constraints](https://mlsanity.com/paper/2301.10923/) (2023)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach](https://mlsanity.com/paper/2407.18878/) (2024)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (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)
- [A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learning](https://mlsanity.com/paper/2306.07818/) (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)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration](https://mlsanity.com/paper/2312.14470/) (2023)
- [Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces](https://mlsanity.com/paper/2502.18655/) (2025)
- [Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation](https://mlsanity.com/paper/2301.11547/) (2023)
- [Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries](https://mlsanity.com/paper/2403.09940/) (2024)
- [An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints](https://mlsanity.com/paper/2505.21841/) (2025)
- [A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP](https://mlsanity.com/paper/2207.06147/) (2022)
- [Conflict-Averse Gradient Aggregation for Constrained Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2403.00282/) (2024)

## 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.