# Safe Reinforcement Learning in Constrained Markov Decision Processes

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

## Key facts

- Cited by 115 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2020.

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

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Safe Offline Reinforcement Learning with Feasibility-Guided Diffusion Model](https://mlsanity.com/paper/2401.10700/) (2024)
- [State-wise Safe Reinforcement Learning: A Survey](https://mlsanity.com/paper/2302.03122/) (2023)
- [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)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [Context-Aware Safe Reinforcement Learning for Non-Stationary Environments](https://mlsanity.com/paper/2101.00531/) (2021)
- [Verifying Learning-Based Robotic Navigation Systems](https://mlsanity.com/paper/2205.13536/) (2022)
- [Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithms](https://mlsanity.com/paper/2310.03225/) (2023)
- [Safe Pontryagin Differentiable Programming](https://mlsanity.com/paper/2105.14937/) (2021)
- [ActSafe: Active Exploration with Safety Constraints for Reinforcement Learning](https://mlsanity.com/paper/2410.09486/) (2024)
- [Evaluating Model-free Reinforcement Learning toward Safety-critical Tasks](https://mlsanity.com/paper/2212.05727/) (2022)
- [Survival Instinct in Offline Reinforcement Learning](https://mlsanity.com/paper/2306.03286/) (2023)
- [Reinforced Refinement with Self-Aware Expansion for End-to-End Autonomous Driving](https://mlsanity.com/paper/2506.09800/) (2025)
- [Safe Exploration by Solving Early Terminated MDP](https://mlsanity.com/paper/2107.04200/) (2021)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Distributionally Robust Constrained Reinforcement Learning under Strong Duality](https://mlsanity.com/paper/2406.15788/) (2024)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [BAGEN: Are LLM Agents Budget-Aware?](https://mlsanity.com/paper/2606.00198/) (2026)
- [Lyapunov Barrier Policy Optimization](https://mlsanity.com/paper/2103.09230/) (2021)
- [Near-Optimal Multi-Agent Learning for Safe Coverage Control](https://mlsanity.com/paper/2210.06380/) (2022)
- [Provably Safe Reinforcement Learning with Step-wise Violation Constraints](https://mlsanity.com/paper/2302.06064/) (2023)
- [Model-based Dynamic Shielding for Safe and Efficient Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2304.06281/) (2023)
- [Safe Policy Optimization with Local Generalized Linear Function Approximations](https://mlsanity.com/paper/2111.04894/) (2021)
- [Gradient Shaping for Multi-Constraint Safe Reinforcement Learning](https://mlsanity.com/paper/2312.15127/) (2023)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Thresholded Lexicographic Ordered Multiobjective Reinforcement Learning](https://mlsanity.com/paper/2408.13493/) (2024)
- [Provable Safe Reinforcement Learning with Binary Feedback](https://mlsanity.com/paper/2210.14492/) (2022)
- [SAFER: Data-Efficient and Safe Reinforcement Learning via Skill Acquisition](https://mlsanity.com/paper/2202.04849/) (2022)

## Abstract (arXiv)

Safe reinforcement learning has been a promising approach for optimizing the policy of an agent that operates in safety-critical applications. In this paper, we propose an algorithm, SNO-MDP, that explores and optimizes Markov decision processes under unknown safety constraints. Specifically, we take a stepwise approach for optimizing safety and cumulative reward. In our method, the agent first learns safety constraints by expanding the safe region, and then optimizes the cumulative reward in the certified safe region. We provide theoretical guarantees on both the satisfaction of the safety constraint and the near-optimality of the cumulative reward under proper regularity assumptions. In our experiments, we demonstrate the effectiveness of SNO-MDP through two experiments: one uses a synthetic data in a new, openly-available environment named GP-SAFETY-GYM, and the other simulates Mars surface exploration by using real observation data.