mlsanityData to 7 Oct 2026

A Primal-Dual Approach to Constrained Markov Decision Processes

arXiv 2101.10895 ↗First posted 26 Jan 2021math.OCcited by 42

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 14; 2024: 13; 2025: 3; 2026: 3.

42 papers.

Sort:

By area:

  1. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  2. 2023Constrained Decision Transformer for Offline Safe Reinforcement Learningcited by 65
  3. 2023Datasets and Benchmarks for Offline Safe Reinforcement Learningcited by 58
  4. 2022Constrained Update Projection Approach to Safe Policy Optimizationcited by 55
  5. 2024Enhancing LLM Safety via Constrained Direct Preference Optimizationcited by 47
  6. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  7. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  8. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  9. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  10. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  11. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  12. 2022CUP: A Conservative Update Policy Algorithm for Safe Reinforcement Learningcited by 16
30 more
  1. 2023AutoCost: Evolving Intrinsic Cost for Zero-violation Reinforcement Learningcited by 16
  2. 2023Efficient Gradient Approximation Method for Constrained Bilevel Optimizationcited by 15
  3. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  4. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  5. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  6. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  7. 2024Offline Safe Reinforcement Learning Using Trajectory Classificationcited by 9
  8. 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 6
  9. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  10. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  11. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  12. 2022Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamicscited by 3
  13. 2023Marketing Budget Allocation with Offline Constrained Deep Reinforcement Learningcited by 3
  14. 2023RL-MPCA: A Reinforcement Learning Based Multi-Phase Computation Allocation Approach for Recommender Systemscited by 3
  15. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Samplingcited by 2
  16. 2025Dual-Objective Reinforcement Learning with Novel Hamilton-Jacobi-Bellman Formulationscited by 2
  17. 2023Scalable and Independent Learning of Nash Equilibrium Policies in n-Player Stochastic Games with Unknown Independent Chainscited by 1
  18. 2024A Dual Perspective of Reinforcement Learning for Imposing Policy Constraintscited by 1
  19. 2024Myopically Verifiable Probabilistic Certificates for Safe Control and Learningcited by 1
  20. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  21. 2023A Single-Loop Deep Actor-Critic Algorithm for Constrained Reinforcement Learning with Provable Convergencecited by 0
  22. 2023Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Needcited by 0
  23. 2024On the Limited Representational Power of Value Functions and its Links to Statistical (In)Efficiencycited by 0
  24. 2024Online Learning of Weakly Coupled MDP Policies for Load Balancing and Auto Scalingcited by 0
  25. 2024Adversarial Constrained Policy Optimization: Improving Constrained Reinforcement Learning by Adapting Budgetscited by 0
  26. 2025Context-aware Constrained Reinforcement Learning Based Energy-Efficient Power Scheduling for Non-stationary XR Data Trafficcited by 0
  27. 2025A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidancecited by 0
  28. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  29. 2026Q-learning Penalized Transformer for Safe Offline Reinforcement Learningcited by 0
  30. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0