# Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 34 references that are in the map.
- First posted on arXiv 4 Jun 2021.

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

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks](https://mlsanity.com/paper/1903.08792/) (2019)
- [Projection-Based Constrained Policy Optimization](https://mlsanity.com/paper/2010.03152/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [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)
- [Learning-based Model Predictive Control for Safe Exploration](https://mlsanity.com/paper/1803.08287/) (2018)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1802.06480/) (2018)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [Improved Algorithms for Conservative Exploration in Bandits](https://mlsanity.com/paper/2002.03221/) (2020)

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

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (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)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://mlsanity.com/paper/2302.01275/) (2023)
- [Concave Utility Reinforcement Learning with Zero-Constraint Violations](https://mlsanity.com/paper/2109.05439/) (2021)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Learning Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2403.03672/) (2024)
- [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)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games](https://mlsanity.com/paper/2206.01588/) (2022)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Probabilistic Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2503.07671/) (2025)
- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Provably Safe Reinforcement Learning with Step-wise Violation Constraints](https://mlsanity.com/paper/2302.06064/) (2023)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL](https://mlsanity.com/paper/2206.14057/) (2022)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learning](https://mlsanity.com/paper/2306.07818/) (2023)

## Abstract (arXiv)

We address the issue of safety in reinforcement learning. We pose the problem in an episodic framework of a constrained Markov decision process. Existing results have shown that it is possible to achieve a reward regret of tildeO(√K) while allowing an tildeO(√K) constraint violation in K episodes. A critical question that arises is whether it is possible to keep the constraint violation even smaller. We show that when a strictly safe policy is known, then one can confine the system to zero constraint violation with arbitrarily high probability while keeping the reward regret of order tildeO(√K). The algorithm which does so employs the principle of optimistic pessimism in the face of uncertainty to achieve safe exploration. When no strictly safe policy is known, though one is known to exist, then it is possible to restrict the system to bounded constraint violation with arbitrarily high probability. This is shown to be realized by a primal-dual algorithm with an optimistic primal estimate and a pessimistic dual update.