# A safe exploration approach to constrained Markov decision processes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 82 references that are in the map.
- First posted on arXiv 1 Dec 2023.

## Builds on (most cited first, 30 of 49)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [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)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks](https://mlsanity.com/paper/1903.08792/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems](https://mlsanity.com/paper/1705.01292/) (2017)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Lyapunov-based Safe Policy Optimization for Continuous Control](https://mlsanity.com/paper/1901.10031/) (2019)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics](https://mlsanity.com/paper/1602.04450/) (2016)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [IPO: Interior-point Policy Optimization under Constraints](https://mlsanity.com/paper/1910.09615/) (2019)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1802.06480/) (2018)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)

## Built on by (most cited first, 10 of 10)

- [ActSafe: Active Exploration with Safety Constraints for Reinforcement Learning](https://mlsanity.com/paper/2410.09486/) (2024)
- [Embedding Safety into RL: A New Take on Trust Region Methods](https://mlsanity.com/paper/2411.02957/) (2024)
- [Safe Exploration via Policy Priors](https://mlsanity.com/paper/2601.19612/) (2026)
- [A learning-based approach to stochastic optimal control under reach-avoid constraint](https://mlsanity.com/paper/2412.16561/) (2024)
- [Central Path Proximal Policy Optimization](https://mlsanity.com/paper/2506.00700/) (2025)
- [Constrained Meta Reinforcement Learning with Provable Test-Time Safety](https://mlsanity.com/paper/2601.21845/) (2026)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Safety Certification is Classification](https://mlsanity.com/paper/2605.06087/) (2026)
- [Provably Safe Sim-to-Real Transfer](https://mlsanity.com/paper/2609.01418/) (2026)
- [Computationally efficient safe exploration in reinforcement learning](https://mlsanity.com/paper/2609.22919/) (2026)

## Abstract (arXiv)

We consider discounted infinite-horizon constrained Markov decision processes (CMDPs), where the goal is to find an optimal policy that maximizes the expected cumulative reward while satisfying expected cumulative constraints. Motivated by the application of CMDPs in online learning for safety-critical systems, we focus on developing a model-free and simulator-free algorithm that ensures constraint satisfaction during learning. To this end, we employ the LB-SGD algorithm proposed in citeusmanova2022log, which utilizes an interior-point approach based on the log-barrier function of the CMDP. Under the commonly assumed conditions of relaxed Fisher non-degeneracy and bounded transfer error in policy parameterization, we establish the theoretical properties of the LB-SGD algorithm. In particular, unlike existing CMDP approaches that ensure policy feasibility only upon convergence, the LB-SGD algorithm guarantees feasibility throughout the learning process and converges to the varepsilon-optimal policy with a sample complexity of tildeO(varepsilon-6). Compared to the state-of-the-art policy gradient-based algorithm, C-NPG-PDA citebai2022achieving2, the LB-SGD algorithm requires an additional O(varepsilon-2) samples to ensure policy feasibility during learning with the same Fisher non-degenerate parameterization.