# Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 85 references that are in the map.
- First posted on arXiv 18 Feb 2021.

## Builds on (most cited first, 30 of 30)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Safe and Efficient Off-Policy Reinforcement Learning](https://mlsanity.com/paper/1606.02647/) (2016)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Sample Efficient Actor-Critic with Experience Replay](https://mlsanity.com/paper/1611.01224/) (2016)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [An Actor-Critic Algorithm for Sequence Prediction](https://mlsanity.com/paper/1607.07086/) (2016)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy](https://mlsanity.com/paper/1906.10306/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Interpretable Off-Policy Evaluation in Reinforcement Learning by Highlighting Influential Transitions](https://mlsanity.com/paper/2002.03478/) (2020)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Representation Balancing MDPs for Off-Policy Policy Evaluation](https://mlsanity.com/paper/1805.09044/) (2018)
- [Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximation](https://mlsanity.com/paper/1802.07842/) (2018)

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

- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators](https://mlsanity.com/paper/2106.12729/) (2021)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)
- [Inverse Reinforcement Learning with the Average Reward Criterion](https://mlsanity.com/paper/2305.14608/) (2023)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithms](https://mlsanity.com/paper/2208.03247/) (2022)
- [Approximate Global Convergence of Independent Learning in Multi-Agent Systems](https://mlsanity.com/paper/2405.19811/) (2024)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning](https://mlsanity.com/paper/2108.08655/) (2021)
- [Two-Timescale Stochastic Approximation for Bilevel Optimisation Problems in Continuous-Time Models](https://mlsanity.com/paper/2206.06995/) (2022)
- [Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithms](https://mlsanity.com/paper/2310.16363/) (2023)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Neural Network Compatible Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2110.10017/) (2021)
- [Coordinate Ascent for Off-Policy RL with Global Convergence Guarantees](https://mlsanity.com/paper/2212.05237/) (2022)
- [Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization](https://mlsanity.com/paper/2603.07698/) (2026)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [MoMA: Model-based Mirror Ascent for Offline Reinforcement Learning](https://mlsanity.com/paper/2401.11380/) (2024)
- [Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexity](https://mlsanity.com/paper/2510.04189/) (2025)
- [Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs](https://mlsanity.com/paper/2607.28390/) (2026)

## Abstract (arXiv)

In this paper, we provide finite-sample convergence guarantees for an off-policy variant of the natural actor-critic (NAC) algorithm based on Importance Sampling. In particular, we show that the algorithm converges to a global optimal policy with a sample complexity of O(ε-3log2(1/ε)) under an appropriate choice of stepsizes. In order to overcome the issue of large variance due to Importance Sampling, we propose the Q-trace algorithm for the critic, which is inspired by the V-trace algorithm citeespeholt2018impala. This enables us to explicitly control the bias and variance, and characterize the trade-off between them. As an advantage of off-policy sampling, a major feature of our result is that we do not need any additional assumptions, beyond the ergodicity of the Markov chain induced by the behavior policy.