# Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 3 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach](https://mlsanity.com/paper/2407.18878/) (2024)
- [Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach](https://mlsanity.com/paper/2505.19986/) (2025)
- [Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization](https://mlsanity.com/paper/2602.08000/) (2026)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis](https://mlsanity.com/paper/2509.15392/) (2025)
- [Stabilizing Policy Gradient Methods via Reward Profiling](https://mlsanity.com/paper/2511.16629/) (2025)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL](https://mlsanity.com/paper/2606.25012/) (2026)
- [Schrödinger--Föllmer Actor--Critic: Diffusion Policy Improvement with Finite-Sample Analysis](https://mlsanity.com/paper/2609.33239/) (2026)

## Abstract (arXiv)

Actor-critic (AC) is a powerful method for learning an optimal policy in reinforcement learning, where the critic uses algorithms, e.g., temporal difference (TD) learning with function approximation, to evaluate the current policy and the actor updates the policy along an approximate gradient direction using information from the critic. This paper provides the textittightest non-asymptotic convergence bounds for both the AC and natural AC (NAC) algorithms. Specifically, existing studies show that AC converges to an ε+varepsiloncritic neighborhood of stationary points with the best known sample complexity of O(ε-2) (up to a log factor), and NAC converges to an ε+varepsiloncritic+√varepsilonactor neighborhood of the global optimum with the best known sample complexity of O(ε-3), where varepsiloncritic is the approximation error of the critic and varepsilonactor is the approximation error induced by the insufficient expressive power of the parameterized policy class. This paper analyzes the convergence of both AC and NAC algorithms with compatible function approximation. Our analysis eliminates the term varepsiloncritic from the error bounds while still achieving the best known sample complexities. Moreover, we focus on the challenging single-loop setting with a single Markovian sample trajectory. Our major technical novelty lies in analyzing the stochastic bias due to policy-dependent and time-varying compatible function approximation in the critic, and handling the non-ergodicity of the MDP due to the single Markovian sample trajectory. Numerical results are also provided in the appendix.