mlsanityData to 14 Oct 2026

Sample-Efficient Constrained Reinforcement Learning with General Parameterization

arXiv 2405.10624 ↗First posted 17 May 2024cs.LG cs.AIcited by 11

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

Abstract (arXiv)

We consider a constrained Markov Decision Problem (CMDP) where the goal of an agent is to maximize the expected discounted sum of rewards over an infinite horizon while ensuring that the expected discounted sum of costs exceeds a certain threshold. Building on the idea of momentum-based acceleration, we develop the Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) algorithm that ensures an ε global optimality gap and ε constraint violation with tildeO((1-γ)-7ε-2) sample complexity for general parameterized policies where γ denotes the discount factor. This improves the state-of-the-art sample complexity in general parameterized CMDPs by a factor of O((1-γ)-1ε-2) and achieves the theoretical lower bound in ε-1.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 33 of its 43 references that are in the map. First posted on arXiv 17 May 2024.

Builds on

33 of 43 references.

References · 33

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  4. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  5. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  6. 2020Exploration-Exploitation in Constrained MDPscited by 149
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  8. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
  9. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  10. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  11. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  12. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
21 more
  1. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  2. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  3. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  4. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  5. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
  6. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 52
  7. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  9. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  10. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  11. 2020Momentum-Based Policy Gradient Methodscited by 30
  12. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  13. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  14. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 23
  15. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  16. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  17. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
  18. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 17
  19. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 17
  20. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 13
  21. 2023Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global Statecited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 6.

11 papers.

  1. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  2. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  3. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 1
  4. 2025Offline Constrained Reinforcement Learning under Partial Data Coveragecited by 1
  5. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  6. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  7. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  8. 2026On the Convergence of Self-Improving Online LLM Alignmentcited by 1
  9. 2026Sample Complexity Analysis for Constrained Bilevel Reinforcement Learningcited by 0
  10. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  11. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
  2. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
  3. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
  4. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  5. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees
  6. 2025Provably Efficient Sample Complexity for Robust CMDP
  7. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  8. 2025Reinforcement Learning in POMDP's via Direct Gradient Ascent