mlsanityData to 7 Oct 2026

Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm

arXiv 2402.02042 ↗First posted 3 Feb 2024cs.LG cs.AIcited by 9

Not on the map. Why?

Abstract (arXiv)

This paper explores the realm of infinite horizon average reward Constrained Markov Decision Processes (CMDPs). To the best of our knowledge, this work is the first to delve into the regret and constraint violation analysis of average reward CMDPs with a general policy parametrization. To address this challenge, we propose a primal dual-based policy gradient algorithm that adeptly manages the constraints while ensuring a low regret guarantee toward achieving a global optimal policy. In particular, our proposed algorithm achieves tildeO(T4/5) objective regret and tildeO(T4/5) constraint violation bounds.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 24 of its 39 references that are in the map. First posted on arXiv 3 Feb 2024.

Builds on

24 of 39 references.

References · 24

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  4. 2020Exploration-Exploitation in Constrained MDPscited by 146
  5. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  6. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  7. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  8. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  9. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  10. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
  11. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  12. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
12 more
  1. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  2. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  3. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  4. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  5. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  6. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  7. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  8. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  9. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  10. 2023Cooperating Graph Neural Networks with Deep Reinforcement Learning for Vaccine Prioritizationcited by 9
  11. 2023Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global Statecited by 8
  12. 2020Provably Efficient Model-Free Algorithm for MDPs with Peak Constraintscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 5.

9 papers.

  1. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  2. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  3. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  4. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 3
  5. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  6. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  7. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  8. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  9. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0