mlsanityData to 14 Oct 2026

Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework

arXiv 2605.10671 ↗First posted 11 May 2026cs.LG math.OC stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In this work, we show that natural policy gradient, a core algorithm in reinforcement learning, admits an exact formulation as a smoothed and averaged form of policy iteration. Specifically, we introduce doubly smoothed policy iteration (DSPI), a Bellman-operator framework in which each policy is obtained by applying a regularized greedy step to a weighted average of past Q-functions. DSPI includes policy iteration, dual-averaged policy iteration, natural policy gradient, and more general policy dual averaging methods as special cases. Using only monotonicity and contraction of smoothed Bellman operators, we prove distribution-free global geometric convergence of DSPI. Consequently, standard natural policy gradient and policy dual averaging achieve an iteration complexity of O((1-γ)-1log((1-γ)-1ε-1)) for computing an ε-optimal policy, without modifying the MDP, adding regularization beyond the mirror map inherent in the update, or using adaptive, trajectory-dependent stepsizes. For the unregularized greedy case, corresponding to dual-averaged policy iteration, we also prove finite termination. The same Bellman-operator framework further extends to discounted MDPs with linear function approximation and stochastic shortest path problems.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 30 of its 50 references that are in the map. First posted on arXiv 11 May 2026.

Builds on

30 of 50 references.

Closest ancestors · 3

Same direction, newest first

  1. 2026Operator-Theoretic Foundations and Policy Gradient Methods for General MDPs with Unbounded Costs18 Mar
  2. 2025Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs21 Oct
  3. 2024Strongly-polynomial time and validation analysis of policy gradient methods28 Sep

Other references · 27

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2015Trust Region Policy Optimizationcited by 2,580
  4. 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 379
  5. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  6. 2019A Theory of Regularized Markov Decision Processescited by 286
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  8. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  9. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  10. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  11. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  12. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
15 more
  1. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  2. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  3. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  4. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 52
  5. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  6. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  7. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
  8. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  9. 2022Policy Optimization over General State and Action Spacescited by 23
  10. 2013Improved and Generalized Upper Bounds on the Complexity of Policy Iterationcited by 21
  11. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  12. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  13. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  14. 2022Block Policy Mirror Descentcited by 11
  15. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Mathematical methods of reinforcement learning
  2. 2026Robust Regularized Policy Iteration under Transition Uncertainty
  3. 2026Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
  4. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction
  5. 2024The Definitive Guide to Policy Gradients in Deep Reinforcement Learning: Theory, Algorithms and Implementations
  6. 2024Elementary Analysis of Policy Gradient Methods
  7. 2025Policy Gradient with Second Order Momentum
  8. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics