# Operator Splitting for Convex Constrained Markov Decision Processes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 36 of its 72 references that are in the map.
- First posted on arXiv 18 Dec 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Projection-Based Constrained Policy Optimization](https://mlsanity.com/paper/2010.03152/) (2020)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [IPO: Interior-point Policy Optimization under Constraints](https://mlsanity.com/paper/1910.09615/) (2019)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Scalable First-Order Methods for Robust MDPs](https://mlsanity.com/paper/2005.05434/) (2020)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [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)
- [Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process](https://mlsanity.com/paper/2110.10351/) (2021)
- [Convergence Rates with Inexact Non-expansive Operators](https://mlsanity.com/paper/1404.4837/) (2014)
- [Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations](https://mlsanity.com/paper/2112.14004/) (2021)
- [Dynamic Programming Through the Lens of Semismooth Newton-Type Methods (Extended Version)](https://mlsanity.com/paper/2203.08678/) (2022)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions](https://mlsanity.com/paper/1407.5210/) (2014)
- [Algorithm for Constrained Markov Decision Process with Linear Convergence](https://mlsanity.com/paper/2206.01666/) (2022)
- [From Optimization to Control: Quasi Policy Iteration](https://mlsanity.com/paper/2311.11166/) (2023)

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

- [Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers](https://mlsanity.com/paper/2508.10480/) (2025)
- [Stochastic Dimension Implicit Functional Projections for Global Integral Conservation in High-Dimensional PINNs](https://mlsanity.com/paper/2603.29237/) (2026)
- [NLPOpt-Net: A Learning Method for Nonlinear Optimization with Feasibility Guarantees](https://mlsanity.com/paper/2605.00260/) (2026)
- [Joint Chance Constrained Safe-Optimal Control](https://mlsanity.com/paper/2606.30829/) (2026)

## Abstract (arXiv)

We consider finite Markov decision processes (MDPs) with convex constraints and known dynamics. In principle, this problem is amenable to off-the-shelf convex optimization solvers, but typically this approach suffers from poor scalability. In this work, we develop a first-order algorithm, based on the Douglas-Rachford splitting, that allows us to decompose the dynamics and constraints. Thanks to this decoupling, we can incorporate a wide variety of convex constraints. Our scheme consists of simple and easy-to-implement updates that alternate between solving a regularized MDP and a projection. The inherent presence of regularized updates ensures last-iterate convergence, numerical stability, and, contrary to existing approaches, does not require us to regularize the problem explicitly. If the constraints are not attainable, we exploit salient properties of the Douglas-Rachord algorithm to detect infeasibility and compute a policy that minimally violates the constraints. We demonstrate the performance of our algorithm on two benchmark problems and show that it compares favorably to competing approaches.