mlsanityData to 14 Oct 2026

Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexity

arXiv 2510.04189 ↗First posted 5 Oct 2025cs.LG cs.AIcited by 0

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

Abstract (arXiv)

Recent studies have increasingly focused on non-asymptotic convergence analyses for actor-critic (AC) algorithms. One such effort introduced a two-timescale critic-actor algorithm for the discounted cost setting using a tabular representation, where the usual roles of the actor and critic are reversed. However, only asymptotic convergence was established there. Subsequently, both asymptotic and non-asymptotic analyses of the critic-actor algorithm with linear function approximation were conducted. In our work, we introduce the first natural critic-actor algorithm with function approximation for the long-run average cost setting and under inequality constraints. We provide the non-asymptotic convergence guarantees for this algorithm. Our analysis establishes optimal learning rates and we also propose a modification to enhance sample complexity. We further show the results of experiments on three different Safety-Gym environments where our algorithm is found to be competitive in comparison with other well known algorithms.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 14 of its 27 references that are in the map. First posted on arXiv 5 Oct 2025.

Builds on

14 of 27 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning15 May

Other references · 13

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  2. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  3. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  4. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  5. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  6. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  7. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 24
  8. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  9. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  10. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  11. 2022Actor-Critic or Critic-Actor? A Tale of Two Time Scalescited by 7
  12. 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
1 more
  1. 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation
  2. 2025Actor-Critics Can Achieve Optimal Sample Efficiency
  3. 2024Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization
  4. 2026A Concentration Bound for Two-Timescale Actor-Critic Algorithm
  5. 2024On the Convergence of Single-Timescale Actor-Critic
  6. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Reward
  7. 2025An Actor-Critic Algorithm with Function Approximation for Risk Sensitive Cost Markov Decision Processes
  8. 2025A Theoretical Justification for Asymmetric Actor-Critic Algorithms