Research map / Optimization / Nonconvex and smooth optimization
Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows natural policy gradient equals a doubly smoothed (averaged and entropy-regularized) policy iteration, yielding distribution-free geometric convergence of NPG/PDA and finite termination of dual-averaged PI.
Problem
Existing NPG analyses lack distribution-free global geometric convergence without extra regularization or adaptive stepsizes, and there is no unified view connecting policy iteration with NPG and policy dual averaging.
Approach
Introduces doubly smoothed policy iteration (DSPI): the policy is a regularized greedy step on a weighted running average of past Q-functions; NPG with entropy and geometric stepsizes is exactly DSPI, so smoothed Bellman operator contraction and monotonicity give global geometric rates.
Key results
- DSPI converges with ||V*-V^{pi_k}||_inf <= (1-(1-gamma)beta)^{k-1}(gamma||V*-V^{pi_0}||_inf+1), giving NPG iteration complexity O((1-gamma)^{-1} log((1-gamma)^{-1} eps^{-1})) without extra regularization or adaptive stepsizes.
- Dual-averaged policy iteration terminates finitely, in at most n(m-1)ceil(beta^{-1}(1-gamma)^{-1} log(2(1-gamma)^{-1})) iterations.
- NPG with geometric stepsizes alpha_k = beta alpha_0/(1-beta)^k is exactly DSPI with beta_k = beta, giving distribution-free geometric convergence.
Surprising findings
- Vector-valued (componentwise) monotone improvement of Q-functions holds for NPG, stronger than scalar objective monotonicity in prior work.
Limitations
- Analysis assumes exact Q-function evaluation for each policy iterate; model-free sample complexity not established.
- Finite termination result is for the unregularized greedy case (dual-averaged PI) only.
- Linear function approximation result carries an approximation error term.
Experimental setup
Metrics: l-infinity value function gap iteration complexity
Baselines: policy iteration natural policy gradient policy dual averaging incremental policy iteration
Builds on: policy iteration natural policy gradient policy dual averaging policy mirror ascent incremental policy iteration
Closest papers by meaning
- SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation (ICML 2018 · similarity 0.90)
- A Theory of Regularized Markov Decision Processes (ICML 2019 · similarity 0.90)
- Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics (ICLR 2025 · similarity 0.89)
- Enhancing Value Function Estimation through First-Order State-Action Dynamics in Offline Reinforcement Learning (ICML 2024 · similarity 0.88)
- Sample-Efficient Constrained Reinforcement Learning with General Parameterization (NeurIPS 2024 · similarity 0.88)
- Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.