mlsanityData to 13 Oct 2026

Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs

arXiv 2408.11513 ↗First posted 21 Aug 2024cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

This paper focuses on learning a Constrained Markov Decision Process (CMDP) via general parameterized policies. We propose a Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) algorithm that uses entropy and quadratic regularizers to reach this goal. For parameterized policy classes with a transferred compatibility approximation error, εbias, PDR-ANPG achieves a last-iterate ε optimality gap and ε constraint violation with a sample complexity of tildeO(ε-2minε-2,εbias^-frac13). If the class is incomplete (εbias>0), then the sample complexity reduces to tildeO(ε-2) for ε<(εbias)^frac16. Moreover, for complete policies with εbias=0, our algorithm achieves a last-iterate ε optimality gap and ε constraint violation with tildeO(ε-4) sample complexity. It is a significant improvement over the state-of-the-art last-iterate guarantees of general parameterized CMDPs.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 32 of its 40 references that are in the map. First posted on arXiv 21 Aug 2024.

Builds on

32 of 40 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning15 Jul
  2. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterization17 May

Other references · 30

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 515
  2. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 171
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 158
  4. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 151
  5. 2020Exploration-Exploitation in Constrained MDPscited by 147
  6. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 132
  7. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  8. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  9. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 79
  10. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 68
  11. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 64
  12. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
18 more
  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 54
  2. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  3. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  5. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  6. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  7. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  8. 2020Momentum-Based Policy Gradient Methodscited by 29
  9. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  10. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  11. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 23
  12. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  13. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
  14. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  15. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 16
  16. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  17. 2023Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global Statecited by 8
  18. 2022Algorithm for Constrained Markov Decision Process with Linear Convergencecited by 3

Built on by

Not cited yet.