mlsanityData to 7 Oct 2026

Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs

arXiv 2306.11700 ↗First posted 20 Jun 2023math.OC cs.LG cs.SYcited by 27

Not on the map. Why?

Abstract (arXiv)

We study the problem of computing an optimal policy of an infinite-horizon discounted constrained Markov decision process (constrained MDP). Despite the popularity of Lagrangian-based policy search methods used in practice, the oscillation of policy iterates in these methods has not been fully understood, bringing out issues such as violation of constraints and sensitivity to hyper-parameters. To fill this gap, we employ the Lagrangian method to cast a constrained MDP into a constrained saddle-point problem in which max/min players correspond to primal/dual variables, respectively, and develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. Specifically, we first propose a regularized policy gradient primal-dual (RPG-PD) method that updates the policy using an entropy-regularized policy gradient, and the dual variable via a quadratic-regularized gradient ascent, simultaneously. We prove that the policy primal-dual iterates of RPG-PD converge to a regularized saddle point with a sublinear rate, while the policy iterates converge sublinearly to an optimal constrained policy. We further instantiate RPG-PD in large state or action spaces by including function approximation in policy parametrization, and establish similar sublinear last-iterate policy convergence. Second, we propose an optimistic policy gradient primal-dual (OPG-PD) method that employs the optimistic gradient method to update primal/dual variables, simultaneously. We prove that the policy primal-dual iterates of OPG-PD converge to a saddle point that contains an optimal constrained policy, with a linear rate. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 78 of its 126 references that are in the map. First posted on arXiv 20 Jun 2023.

Builds on

78 of 126 references.

References · 78

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2018Reward Constrained Policy Optimizationcited by 397
  3. 2021Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learningcited by 337
  4. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 320
  5. 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 302
  6. 2020Projection-Based Constrained Policy Optimizationcited by 195
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  8. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  9. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  10. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  11. 2020Exploration-Exploitation in Constrained MDPscited by 146
  12. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
38 more
  1. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  2. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  5. 2019IPO: Interior-point Policy Optimization under Constraintscited by 119
  6. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  7. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  8. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  9. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  10. 2021Reward is enough for convex MDPscited by 82
  11. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  12. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  13. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  14. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  15. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  16. 2018Two-Player Games for Efficient Non-Convex Constrained Optimizationcited by 55
  17. 2019Convergent Policy Optimization for Safe Reinforcement Learningcited by 55
  18. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  19. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  20. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  21. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  22. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  23. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  24. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  25. 2021State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewardscited by 37
  26. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  27. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  28. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  29. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  30. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  31. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  32. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  33. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  34. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  35. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  36. 2022MuZero with Self-competition for Rate Control in VP9 Video Compressioncited by 27
  37. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  38. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25

50 most cited of 78 All 78 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 11; 2025: 9; 2026: 5.

27 papers.

Sort:

By area:

  1. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  2. 2024Stepwise Alignment for Constrained Language Model Policy Optimizationcited by 30
  3. 2024One-Shot Safety Alignment for Large Language Models via Optimal Dualizationcited by 24
  4. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  5. 2023A safe exploration approach to constrained Markov decision processescited by 10
  6. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  7. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  8. 2024Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learningcited by 5
  9. 2025Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spacescited by 5
  10. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  11. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  12. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
15 more
  1. 2025Auto-exploration for online reinforcement learningcited by 2
  2. 2023Resilient Constrained Reinforcement Learningcited by 1
  3. 2025Policy Testing in Markov Decision Processescited by 1
  4. 2024Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPscited by 0
  5. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  6. 2025Digital Twin Calibration with Model-Based Reinforcement Learningcited by 0
  7. 2025Context-aware Constrained Reinforcement Learning Based Energy-Efficient Power Scheduling for Non-stationary XR Data Trafficcited by 0
  8. 2025Towards a Practical Understanding of Lagrangian Methods in Safe Reinforcement Learningcited by 0
  9. 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learningcited by 0
  10. 2025Constrained Language Model Policy Optimization via Risk-aware Stepwise Alignmentcited by 0
  11. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Marginscited by 0
  12. 2026Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guaranteescited by 0
  13. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  14. 2026Computationally efficient safe exploration in reinforcement learningcited by 0
  15. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0