mlsanityData to 7 Oct 2026

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

arXiv 2102.09318 ↗First posted 18 Feb 2021cs.LG math.OC stat.MLcited by 26

Not on the map. Why?

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.

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

Builds on

30 of 85 references.

References · 30

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  4. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  5. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 659
  6. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
  7. 2019A Theory of Regularized Markov Decision Processescited by 279
  8. 2016Safe and Efficient Off-Policy Reinforcement Learningcited by 260
  9. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  10. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  11. 2016Sample Efficient Actor-Critic with Experience Replaycited by 185
  12. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
18 more
  1. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  2. 2016An Actor-Critic Algorithm for Sequence Predictioncited by 158
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  4. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  5. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  6. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  7. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  8. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  9. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  10. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  11. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  12. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  13. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  14. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 42
  15. 2020Interpretable Off-Policy Evaluation in Reinforcement Learning by Highlighting Influential Transitionscited by 41
  16. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  17. 2018Representation Balancing MDPs for Off-Policy Policy Evaluationcited by 20
  18. 2018Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximationcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 5; 2024: 2; 2025: 3; 2026: 3.

26 papers.

Sort:

By area:

  1. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  2. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  3. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  4. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  5. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  6. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  7. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 22
  8. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  9. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  10. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  11. 2023Inverse Reinforcement Learning with the Average Reward Criterioncited by 8
  12. 2023On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrizationcited by 5
14 more
  1. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3
  2. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  3. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  4. 2021Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learningcited by 2
  5. 2022Two-Timescale Stochastic Approximation for Bilevel Optimisation Problems in Continuous-Time Modelscited by 2
  6. 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2
  7. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  8. 2021Neural Network Compatible Off-Policy Natural Actor-Critic Algorithmcited by 1
  9. 2022Coordinate Ascent for Off-Policy RL with Global Convergence Guaranteescited by 1
  10. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  11. 2024MoMA: Model-based Mirror Ascent for Offline Reinforcement Learningcited by 0
  12. 2025Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexitycited by 0
  13. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  14. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0