# A Primal-Dual Approach to Constrained Markov Decision Processes

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2021.

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

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Constrained Decision Transformer for Offline Safe Reinforcement Learning](https://mlsanity.com/paper/2302.07351/) (2023)
- [Datasets and Benchmarks for Offline Safe Reinforcement Learning](https://mlsanity.com/paper/2306.09303/) (2023)
- [Constrained Update Projection Approach to Safe Policy Optimization](https://mlsanity.com/paper/2209.07089/) (2022)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [Enhancing LLM Safety via Constrained Direct Preference Optimization](https://mlsanity.com/paper/2403.02475/) (2024)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (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)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [CUP: A Conservative Update Policy Algorithm for Safe Reinforcement Learning](https://mlsanity.com/paper/2202.07565/) (2022)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [AutoCost: Evolving Intrinsic Cost for Zero-violation Reinforcement Learning](https://mlsanity.com/paper/2301.10339/) (2023)
- [Efficient Gradient Approximation Method for Constrained Bilevel Optimization](https://mlsanity.com/paper/2302.01970/) (2023)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [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)
- [Offline Safe Reinforcement Learning Using Trajectory Classification](https://mlsanity.com/paper/2412.15429/) (2024)
- [Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chains](https://mlsanity.com/paper/2201.12224/) (2022)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPs](https://mlsanity.com/paper/2406.18529/) (2024)
- [Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learning](https://mlsanity.com/paper/2303.04833/) (2023)
- [Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamics](https://mlsanity.com/paper/2212.01505/) (2022)
- [Marketing Budget Allocation with Offline Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/2309.02669/) (2023)
- [RL-MPCA: A Reinforcement Learning Based Multi-Phase Computation Allocation Approach for Recommender Systems](https://mlsanity.com/paper/2401.01369/) (2023)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Dual-Objective Reinforcement Learning with Novel Hamilton-Jacobi-Bellman Formulations](https://mlsanity.com/paper/2506.16016/) (2025)
- [Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling](https://mlsanity.com/paper/2405.19017/) (2024)
- [Scalable and Independent Learning of Nash Equilibrium Policies in n-Player Stochastic Games with Unknown Independent Chains](https://mlsanity.com/paper/2312.01587/) (2023)

## Abstract (arXiv)

In many operations management problems, we need to make decisions sequentially to minimize the cost while satisfying certain constraints. One modeling approach to study such problems is constrained Markov decision process (CMDP). When solving the CMDP to derive good operational policies, there are two key challenges: one is the prohibitively large state space and action space; the other is the hard-to-compute transition kernel. In this work, we develop a sampling-based primal-dual algorithm to solve CMDPs. Our approach alternatively applies regularized policy iteration to improve the policy and subgradient ascent to maintain the constraints. Under mild regularity conditions, we show that the algorithm converges at rate  O(log(T)/√T), where T is the number of iterations. When the CMDP has a weakly coupled structure, our approach can substantially reduce the dimension of the problem through an embedded decomposition. We apply the algorithm to two important applications with weakly coupled structures: multi-product inventory management and multi-class queue scheduling, and show that it generates controls that outperform state-of-art heuristics.