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

arXiv: https://arxiv.org/abs/2110.11383 · HTML: https://mlsanity.com/paper/2110.11383/

## 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 (most cited first, 30 of 33)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1802.06480/) (2018)
- [Convergent Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1910.12156/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning](https://mlsanity.com/paper/2006.04338/) (2020)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Autonomous Navigation via Deep Reinforcement Learning for Resource Constraint Edge Nodes using Transfer Learning](https://mlsanity.com/paper/1910.05547/) (2019)
- [Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10583/) (2019)
- [Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness](https://mlsanity.com/paper/2003.10973/) (2020)
- [Safe Learning and Optimization Techniques: Towards a Survey of the State of the Art](https://mlsanity.com/paper/2101.09505/) (2021)
- [On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost](https://mlsanity.com/paper/1907.06246/) (2019)

## Built on by (most cited first, 17 of 17)

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm](https://mlsanity.com/paper/2206.05850/) (2022)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Learning in Herding Mean Field Games: Single-Loop Algorithm with Finite-Time Convergence Analysis](https://mlsanity.com/paper/2408.04780/) (2024)
- [Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithms](https://mlsanity.com/paper/2310.16363/) (2023)
- [Federated Reinforcement Learning with Constraint Heterogeneity](https://mlsanity.com/paper/2405.03236/) (2024)
- [Anytime Safe Reinforcement Learning](https://mlsanity.com/paper/2504.16417/) (2025)
- [Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs](https://mlsanity.com/paper/2408.11513/) (2024)
- [Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2405.02456/) (2024)
- [Off-Policy Reinforcement Learning with Anytime Safety Guarantees via Robust Safe Gradient Flow](https://mlsanity.com/paper/2510.01492/) (2025)

## 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.