mlsanityData to 7 Oct 2026

Policy Optimization for Constrained MDPs with Provable Fast Global Convergence

arXiv 2111.00552 ↗First posted 31 Oct 2021cs.LG cs.AI math.OCcited by 22

Not on the map. Why?

Abstract (arXiv)

We address the problem of finding the optimal policy of a constrained Markov decision process (CMDP) using a gradient descent-based algorithm. Previous results have shown that a primal-dual approach can achieve an O(1/√T) global convergence rate for both the optimality gap and the constraint violation. We propose a new algorithm called policy mirror descent-primal dual (PMD-PD) algorithm that can provably achieve a faster O(log(T)/T) convergence rate for both the optimality gap and the constraint violation. For the primal (policy) update, the PMD-PD algorithm utilizes a modified value function and performs natural policy gradient steps, which is equivalent to a mirror descent step with appropriate regularization. For the dual update, the PMD-PD algorithm uses modified Lagrange multipliers to ensure a faster convergence rate. We also present two extensions of this approach to the settings with zero constraint violation and sample-based estimation. Experimental results demonstrate the faster convergence rate and the better performance of the PMD-PD algorithm compared with existing policy gradient-based algorithms.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 25 of its 37 references that are in the map. First posted on arXiv 31 Oct 2021.

Builds on

25 of 37 references.

References · 25

  1. 2015Trust Region Policy Optimizationcited by 2,503
  2. 2016Concrete Problems in AI Safetycited by 1,582
  3. 2017Constrained Policy Optimizationcited by 928
  4. 2014Convex Optimization: Algorithms and Complexitycited by 569
  5. 2018Reward Constrained Policy Optimizationcited by 397
  6. 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 302
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  8. 2020Projection-Based Constrained Policy Optimizationcited by 195
  9. 2017A unified view of entropy-regularized Markov decision processescited by 174
  10. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  11. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  12. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
13 more
  1. 2020Exploration-Exploitation in Constrained MDPscited by 146
  2. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  3. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  4. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  5. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  6. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  7. 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 61
  8. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  9. 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
  10. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  11. 2015A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programscited by 6
  12. 2020First-order methods for problems with O(1) functional constraints can have almost the same convergence rate as for unconstrained problemscited by 4
  13. 2017A Primal-Dual Parallel Method with O(1/ε) Convergence for Constrained Composite Convex Programscited by 3

Built on by

Cited by year (2026 to 7 Oct)

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

22 papers.

Sort:

  1. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  2. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  3. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  4. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  5. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  6. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  7. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  8. 2023A safe exploration approach to constrained Markov decision processescited by 10
  9. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  10. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  11. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  12. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
10 more
  1. 2022Algorithm for Constrained Markov Decision Process with Linear Convergencecited by 3
  2. 2024Federated Reinforcement Learning with Constraint Heterogeneitycited by 2
  3. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  4. 2025Session-Level Dynamic Ad Load Optimization using Offline Robust Reinforcement Learningcited by 2
  5. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  6. 2026Safe Continual Reinforcement Learning Methods for Nonstationary Environments. Towards a Survey of the State of the Artcited by 1
  7. 2024Constraint-Generation Policy Optimization (CGPO): Nonlinear Programming for Policy Optimization in Mixed Discrete-Continuous MDPscited by 0
  8. 2024Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learningcited by 0
  9. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  10. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0