mlsanityData to 7 Oct 2026

Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes

arXiv 2310.11677 ↗First posted 18 Oct 2023cs.LG cs.AIcited by 24

Not on the map. Why?

Abstract (arXiv)

We consider the problem of designing sample efficient learning algorithms for infinite horizon discounted reward Markov Decision Process. Specifically, we propose the Accelerated Natural Policy Gradient (ANPG) algorithm that utilizes an accelerated stochastic gradient descent process to obtain the natural policy gradient. ANPG achieves O(ε-2) sample complexity and O(ε-1) iteration complexity with general parameterization where ε defines the optimality error. This improves the state-of-the-art sample complexity by a log(frac1ε) factor. ANPG is a first-order algorithm and unlike some existing literature, does not require the unverifiable assumption that the variance of importance sampling (IS) weights is upper bounded. In the class of Hessian-free and IS-free algorithms, ANPG beats the best-known sample complexity by a factor of O(ε^-frac12) and simultaneously matches their state-of-the-art iteration complexity.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 36 of its 54 references that are in the map. First posted on arXiv 18 Oct 2023.

Builds on

36 of 54 references.

References · 36

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  6. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  7. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  8. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  9. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  10. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  11. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  12. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
24 more
  1. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  2. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  3. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  4. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  5. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  6. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  7. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  8. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  9. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  10. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  11. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  12. 2020Momentum-Based Policy Gradient Methodscited by 28
  13. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  14. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  15. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 22
  16. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  17. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  18. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
  19. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  20. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 17
  21. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 15
  22. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 11
  23. 2023Cooperating Graph Neural Networks with Deep Reinforcement Learning for Vaccine Prioritizationcited by 9
  24. 2023Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global Statecited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 9; 2025: 8; 2026: 7.

24 papers.

Sort:

By area:

  1. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  2. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  3. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  4. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  5. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  6. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  7. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  8. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  9. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  10. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 4
  11. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  12. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
12 more
  1. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  2. 2025Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Accesscited by 2
  3. 2025Non-Asymptotic Global Convergence of PPO-Clipcited by 2
  4. 2026Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learningcited by 2
  5. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  6. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  7. 2026Refined Analysis of Entropy-Regularized Actor-Criticcited by 1
  8. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  9. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  10. 2025Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexitycited by 0
  11. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Rewardcited by 0
  12. 2026Match or Replay: Self Imitating Proximal Policy Optimizationcited by 0