mlsanityData to 7 Oct 2026

Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs

arXiv 2206.02346 ↗First posted 6 Jun 2022math.OC cs.AI cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

We study the sequential decision making problem of maximizing the expected total reward while satisfying a constraint on the expected total utility. We employ the natural policy gradient method to solve the discounted infinite-horizon optimal control problem for Constrained Markov Decision Processes (constrained MDPs). Specifically, we propose a new Natural Policy Gradient Primal-Dual (NPG-PD) method that updates the primal variable via natural policy gradient ascent and the dual variable via projected subgradient descent. Although the underlying maximization involves a nonconcave objective function and a nonconvex constraint set, under the softmax policy parametrization, we prove that our method achieves global convergence with sublinear rates regarding both the optimality gap and the constraint violation. Such convergence is independent of the size of the state-action space, i.e., it is~dimension-free. Furthermore, for log-linear and general smooth policy parametrizations, we establish sublinear convergence rates up to a function approximation error caused by restricted policy parametrization. We also provide convergence and finite-sample complexity guarantees for two sample-based NPG-PD algorithms. We use a set of computational experiments to showcase the effectiveness of our approach.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 57 of its 101 references that are in the map. First posted on arXiv 6 Jun 2022.

Builds on

57 of 101 references.

References · 57

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Continuous control with deep reinforcement learningcited by 3,279
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  5. 2017Constrained Policy Optimizationcited by 928
  6. 2018Reward Constrained Policy Optimizationcited by 397
  7. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 320
  8. 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 302
  9. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 278
  10. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  11. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  12. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
38 more
  1. 2020Projection-Based Constrained Policy Optimizationcited by 195
  2. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  4. 2017A General Safety Framework for Learning-Based Control in Uncertain Robotic Systemscited by 150
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  7. 2020Exploration-Exploitation in Constrained MDPscited by 146
  8. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  9. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  10. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  11. 2019IPO: Interior-point Policy Optimization under Constraintscited by 119
  12. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  13. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  14. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  15. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  16. 2017Online Convex Optimization with Stochastic Constraintscited by 94
  17. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  18. 2018Stagewise Safe Bayesian Optimization with Gaussian Processescited by 79
  19. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  20. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  21. 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 61
  22. 2018Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systemscited by 56
  23. 2019Convergent Policy Optimization for Safe Reinforcement Learningcited by 55
  24. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  25. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  26. 2018Online convex optimization for cumulative constraintscited by 47
  27. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  28. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  29. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  30. 2019Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problemcited by 35
  31. 2020Constrained Markov Decision Processes via Backward Value Functionscited by 33
  32. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  33. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  34. 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
  35. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  36. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  37. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  38. 2020Learning in Markov Decision Processes under Constraintscited by 20

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

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

26 papers.

Sort:

By area:

  1. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  2. 2024ActSafe: Active Exploration with Safety Constraints for Reinforcement Learningcited by 22
  3. 2023Identifiability and Generalizability in Constrained Inverse Reinforcement Learningcited by 16
  4. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  5. 2022Geometry and convergence of natural policy gradient methodscited by 12
  6. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  7. 2023A safe exploration approach to constrained Markov decision processescited by 10
  8. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  9. 2024Enhancing Efficiency of Safe Reinforcement Learning via Sample Manipulationcited by 8
  10. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  11. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  12. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientscited by 5
14 more
  1. 2024Conflict-Averse Gradient Aggregation for Constrained Multi-Objective Reinforcement Learningcited by 4
  2. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  3. 2026Policy Gradient Primal-Dual Method for Safe Reinforcement Learning from Human Feedbackcited by 2
  4. 2026Reasoning Is Not Free: Robust Adaptive Cost-Efficient Routing for LLM-as-a-Judgecited by 2
  5. 2023Resilient Constrained Reinforcement Learningcited by 1
  6. 2026Robust General Utility for Reinforcement Learningcited by 1
  7. 2024Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPscited by 0
  8. 2025A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Modelscited by 0
  9. 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learningcited by 0
  10. 2026Provable Last-Iterate Convergence for Multi-Objective Safe LLM Alignment via Optimistic Primal-Dualcited by 0
  11. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  12. 2026Sampling-Based Safe Reinforcement Learningcited by 0
  13. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  14. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0