mlsanityData to 14 Oct 2026

Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes

arXiv 2110.11383 ↗First posted 21 Oct 2021math.OC cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

We consider a discounted cost constrained Markov decision process (CMDP) policy optimization problem, in which an agent seeks to maximize a discounted cumulative reward subject to a number of constraints on discounted cumulative utilities. To solve this constrained optimization program, we study an online actor-critic variant of a classic primal-dual method where the gradients of both the primal and dual functions are estimated using samples from a single trajectory generated by the underlying time-varying Markov processes. This online primal-dual natural actor-critic algorithm maintains and iteratively updates three variables: a dual variable (or Lagrangian multiplier), a primal variable (or actor), and a critic variable used to estimate the gradients of both primal and dual variables. These variables are updated simultaneously but on different time scales (using different step sizes) and they are all intertwined with each other. Our main contribution is to derive a finite-time analysis for the convergence of this algorithm to the global optimum of a CMDP problem. Specifically, we show that with a proper choice of step sizes the optimality gap and constraint violation converge to zero in expectation at a rate O(1/K1/6), where K is the number of iterations. To our knowledge, this paper is the first to study the finite-time complexity of an online primal-dual actor-critic method for solving a CMDP problem. We also validate the effectiveness of this algorithm through numerical simulations.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 33 of its 56 references that are in the map. First posted on arXiv 21 Oct 2021.

Builds on

33 of 56 references.

References · 33

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2017Robust Adversarial Reinforcement Learningcited by 451
  3. 2018Reward Constrained Policy Optimizationcited by 417
  4. 2021Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learningcited by 371
  5. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
  6. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  8. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  9. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  10. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  11. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  12. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
21 more
  1. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  2. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
  3. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  4. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  5. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  6. 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 62
  7. 2019Convergent Policy Optimization for Safe Reinforcement Learningcited by 57
  8. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  9. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  10. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  11. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  12. 2020A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learningcited by 25
  13. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
  14. 2019Autonomous Navigation via Deep Reinforcement Learning for Resource Constraint Edge Nodes using Transfer Learningcited by 19
  15. 2019Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximationcited by 18
  16. 2020Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomnesscited by 18
  17. 2021Safe Learning and Optimization Techniques: Towards a Survey of the State of the Artcited by 16
  18. 2019On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Costcited by 12
  19. 2020Improving Generalization of Reinforcement Learning with Minimax Distributional Soft Actor-Criticcited by 12
  20. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  21. 2020A Natural Actor-Critic Algorithm with Downside Risk Constraintscited by 2

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 3; 2023: 3; 2024: 7; 2025: 3.

17 papers.

Sort:

By area:

  1. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 181
  2. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  3. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  4. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
  5. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  6. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  7. 2023A safe exploration approach to constrained Markov decision processescited by 10
  8. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  9. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 6
  10. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 6
  11. 2024Learning in Herding Mean Field Games: Single-Loop Algorithm with Finite-Time Convergence Analysiscited by 3
  12. 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2
5 more
  1. 2024Federated Reinforcement Learning with Constraint Heterogeneitycited by 2
  2. 2025Anytime Safe Reinforcement Learningcited by 2
  3. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 1
  4. 2024Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learningcited by 0
  5. 2025Off-Policy Reinforcement Learning with Anytime Safety Guarantees via Robust Safe Gradient Flowcited by 0