# Constrained Markov Decision Processes via Backward Value Functions

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

## Key facts

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

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

- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Constraints Penalized Q-learning for Safe Offline Reinforcement Learning](https://mlsanity.com/paper/2107.09003/) (2021)
- [COptiDICE: Offline Constrained Reinforcement Learning via Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2204.08957/) (2022)
- [Constrained Update Projection Approach to Safe Policy Optimization](https://mlsanity.com/paper/2209.07089/) (2022)
- [Offline Reinforcement Learning with Soft Behavior Regularization](https://mlsanity.com/paper/2110.07395/) (2021)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [CUP: A Conservative Update Policy Algorithm for Safe Reinforcement Learning](https://mlsanity.com/paper/2202.07565/) (2022)
- [Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimization](https://mlsanity.com/paper/2102.11055/) (2021)
- [Dynamic Model Predictive Shielding for Provably Safe Reinforcement Learning](https://mlsanity.com/paper/2405.13863/) (2024)
- [Mitigating the Safety Alignment Tax with Null-Space Constrained Policy Optimization](https://mlsanity.com/paper/2512.11391/) (2025)
- [Safe Policy Optimization with Local Generalized Linear Function Approximations](https://mlsanity.com/paper/2111.04894/) (2021)
- [Robust Imitation of a Few Demonstrations with a Backwards Model](https://mlsanity.com/paper/2210.09337/) (2022)
- [Imitate the Good and Avoid the Bad: An Incremental Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/2312.10385/) (2023)
- [Adapting Static Fairness to Sequential Decision-Making: Bias Mitigation Strategies towards Equal Long-term Benefit Rate](https://mlsanity.com/paper/2309.03426/) (2023)
- [Solving Multi-Agent Safe Optimal Control with Distributed Epigraph Form MARL](https://mlsanity.com/paper/2504.15425/) (2025)
- [Successive Convex Approximation Based Off-Policy Optimization for Constrained Reinforcement Learning](https://mlsanity.com/paper/2105.12545/) (2021)
- [Learning Expected Emphatic Traces for Deep RL](https://mlsanity.com/paper/2107.05405/) (2021)
- [Ablation Study of How Run Time Assurance Impacts the Training and Performance of Reinforcement Learning Agents](https://mlsanity.com/paper/2207.04117/) (2022)
- [Solving Richly Constrained Reinforcement Learning through State Augmentation and Reward Penalties](https://mlsanity.com/paper/2301.11592/) (2023)
- [ACPO: A Policy Optimization Algorithm for Average MDPs with Constraints](https://mlsanity.com/paper/2302.00808/) (2023)
- [Guiding Safe Exploration with Weakest Preconditions](https://mlsanity.com/paper/2209.14148/) (2022)
- [Human-AI Collaboration in Real-World Complex Environment with Reinforcement Learning](https://mlsanity.com/paper/2312.15160/) (2023)
- [Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves](https://mlsanity.com/paper/2412.13962/) (2024)
- [DeCOM: Decomposed Policy for Constrained Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2111.05670/) (2021)
- [Handling Long and Richly Constrained Tasks through Constrained Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2302.10639/) (2023)
- [COIN: Chance-Constrained Imitation Learning for Uncertainty-aware Adaptive Resource Oversubscription Policy](https://mlsanity.com/paper/2401.07051/) (2024)
- [Imitating Cost-Constrained Behaviors in Reinforcement Learning](https://mlsanity.com/paper/2403.17456/) (2024)
- [ProSh: Probabilistic Shielding for Model-free Reinforcement Learning](https://mlsanity.com/paper/2510.15720/) (2025)
- [Safe But Not Sorry: Reducing Over-Conservatism in Safety Critics via Uncertainty-Aware Modulation](https://mlsanity.com/paper/2510.18478/) (2025)

## Abstract (arXiv)

Although Reinforcement Learning (RL) algorithms have found tremendous success in simulated domains, they often cannot directly be applied to physical systems, especially in cases where there are hard constraints to satisfy (e.g. on safety or resources). In standard RL, the agent is incentivized to explore any behavior as long as it maximizes rewards, but in the real world, undesired behavior can damage either the system or the agent in a way that breaks the learning process itself. In this work, we model the problem of learning with constraints as a Constrained Markov Decision Process and provide a new on-policy formulation for solving it. A key contribution of our approach is to translate cumulative cost constraints into state-based constraints. Through this, we define a safe policy improvement method which maximizes returns while ensuring that the constraints are satisfied at every step. We provide theoretical guarantees under which the agent converges while ensuring safety over the course of training. We also highlight the computational advantages of this approach. The effectiveness of our approach is demonstrated on safe navigation tasks and in safety-constrained versions of MuJoCo environments, with deep neural networks.