mlsanityData to 7 Oct 2026

A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees

arXiv 2401.17780 ↗First posted 31 Jan 2024cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We study a primal-dual (PD) reinforcement learning (RL) algorithm for online constrained Markov decision processes (CMDPs). Despite its widespread practical use, the existing theoretical literature on PD-RL algorithms for this problem only provides sublinear regret guarantees and fails to ensure convergence to optimal policies. In this paper, we introduce a novel policy gradient PD algorithm with uniform probably approximate correctness (Uniform-PAC) guarantees, simultaneously ensuring convergence to optimal policies, sublinear regret, and polynomial sample complexity for any target accuracy. Notably, this represents the first Uniform-PAC algorithm for the online CMDP problem. In addition to the theoretical guarantees, we empirically demonstrate in a simple CMDP that our algorithm converges to optimal policies, while baseline algorithms exhibit oscillatory performance and constraint violation.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 40 of its 49 references that are in the map. First posted on arXiv 31 Jan 2024.

Builds on

40 of 49 references.

References · 40

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Reward Constrained Policy Optimizationcited by 397
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2019Batch Policy Learning under Constraintscited by 242
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  12. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
28 more
  1. 2020Exploration-Exploitation in Constrained MDPscited by 146
  2. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  3. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  4. 2021Reward is enough for convex MDPscited by 82
  5. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  6. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  7. 2019Reinforcement Learning with Convex Constraintscited by 57
  8. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  9. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  10. 2021DeepThermal: Combustion Optimization for Thermal Power Generating Units Using Offline Reinforcement Learningcited by 47
  11. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  12. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  13. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  14. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  15. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  16. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  17. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  18. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  19. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  20. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  21. 2020Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertaintycited by 23
  22. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  23. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
  24. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  25. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  26. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  27. 2022Robust Constrained Reinforcement Learningcited by 14
  28. 2022Provable Safe Reinforcement Learning with Binary Feedbackcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  2. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  3. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  4. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  5. 2026Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Marginscited by 0