mlsanityData to 14 Oct 2026

Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation

arXiv 2105.12540 ↗First posted 26 May 2021cs.LG math.OCcited by 22

Not on the map. Why?

Abstract (arXiv)

In this paper, we develop a novel variant of off-policy natural actor-critic algorithm with linear function approximation and we establish a sample complexity of O(ε-3), outperforming all the previously known convergence bounds of such algorithms. In order to overcome the divergence due to deadly triad in off-policy policy evaluation under function approximation, we develop a critic that employs n-step TD-learning algorithm with a properly chosen n. We present finite-sample convergence bounds on this critic under both constant and diminishing step sizes, which are of independent interest. Furthermore, we develop a variant of natural policy gradient under function approximation, with an improved convergence rate of O(1/T) after T iterations. Combining the finite sample error bounds of actor and the critic, we obtain the O(ε-3) sample complexity. We derive our sample complexity bounds solely based on the assumption that the behavior policy sufficiently explores all the states and actions, which is a much lighter assumption compared to the related literature.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 40 of its 100 references that are in the map. First posted on arXiv 26 May 2021.

Builds on

40 of 100 references.

References · 40

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  4. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 883
  5. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  6. 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 379
  7. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  8. 2019A Theory of Regularized Markov Decision Processescited by 286
  9. 2016Safe and Efficient Off-Policy Reinforcement Learningcited by 264
  10. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  11. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  12. 2016Sample Efficient Actor-Critic with Experience Replaycited by 188
28 more
  1. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  4. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  5. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  6. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  7. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  8. 2018Learning to Navigate in Cities Without a Mapcited by 104
  9. 2015An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learningcited by 103
  10. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  11. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  12. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  13. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  14. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  15. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  16. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  17. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  18. 2019Off-Policy Policy Gradient with State Distribution Correctioncited by 43
  19. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 43
  20. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  21. 2020Interpretable Off-Policy Evaluation in Reinforcement Learning by Highlighting Influential Transitionscited by 41
  22. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  23. 2018An Off-policy Policy Gradient Theorem Using Emphatic Weightingscited by 34
  24. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  25. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 21
  26. 2018Representation Balancing MDPs for Off-Policy Policy Evaluationcited by 20
  27. 2019Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theorycited by 17
  28. 2018Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximationcited by 12

Built on by

Cited by year

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

22 papers.

Sort:

By area:

  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  2. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  3. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
  4. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  5. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  6. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  7. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  8. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  9. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  10. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysiscited by 9
  11. 2023Inverse Reinforcement Learning with the Average Reward Criterioncited by 8
  12. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
10 more
  1. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  2. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3
  3. 2023Multi-Bellman operator for convergence of Q-learning with linear function approximationcited by 3
  4. 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2
  5. 2024Dual Approximation Policy Optimizationcited by 2
  6. 2022Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximationcited by 1
  7. 2022Coordinate Ascent for Off-Policy RL with Global Convergence Guaranteescited by 1
  8. 2025Ordering-based Conditions for Global Convergence of Policy Gradient Methodscited by 1
  9. 2024Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learningcited by 0
  10. 2025Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexitycited by 0