Research map / Optimization / Nonconvex and smooth optimization
Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning
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.
Proposes Accelerated Policy Gradient (APG), applying Nesterov momentum to softmax policy gradient in tabular MDPs, proving Õ(1/t²) convergence with near-constant step sizes and linear convergence with time-varying steps, plus Atari validation.
Problem
Policy gradient converges at O(1/t) under tabular softmax parameterization; whether Nesterov momentum can accelerate policy optimization with provable rates is unknown because RL objectives are non-concave.
Approach
Adapts Nesterov's accelerated gradient (with monotone restart) to policy optimization; shows that after finite time iterates enter a locally nearly-concave region around the optimal policy that is absorbing, enabling O(1/t^2) rates via surrogate optimal parameters with bounded norm.
Key results
- APG achieves an Õ(1/t^2) convergence rate with nearly constant step sizes under tabular softmax, versus O(1/t) for PG; log-log slope of about 2 for APG vs about 1 for PG and HBPG on a 5x5 MDP.
- With exponentially growing step sizes and element-wise clipping, APG achieves linear convergence O(e^{-ct}).
- On four Atari 2600 games (Pong, Carnival, Riverraid, Seaquest), APG shows faster or comparable convergence to PG and HBPG, averaged over 5 seeds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Nesterov momentum in place of standard PG | Policy optimization with tabular softmax policies · Tabular softmax MDP, nearly constant step sizes | suboptimality gap convergence rate: O({1} / {t}) -> \tilde{O}(1/t^2) | Helped |
| Use time-varying step sizes with element-wise clipping | APG · Tabular softmax MDP | suboptimality gap convergence rate: O({1} / {t}) -> O(e^{-ct}) | Helped |
| Use Nesterov momentum instead of standard PG or heavy-ball momentum | Policy optimization · 5-state, 5-action MDP, uniform initialization | log-log suboptimality gap slope: approximately 1 -> 2 | Helped |
| Use APG instead of PG and HBPG | Policy optimization · 5-state, 5-action MDP, hard initialization | suboptimality gap | Helped |
| Use APG instead of PG or HBPG | Atari policy optimization · Pong, Carnival, Riverraid, and Seaquest | convergence | Mixed |
Surprising findings
- Non-monotonic policy improvement can occur under naively applied Nesterov momentum to PG, requiring a restart mechanism.
Limitations
- Analysis is restricted to exact (true) gradients with tabular softmax parameterization; stochastic gradient extension is open.
- Convergence rate constants and the finite time T are problem-dependent and not explicit.
- Atari experiments are limited to four games with only 5 seeds.
Experimental setup
Datasets: Atari 2600 games (Pong, Carnival, Riverraid, Seaquest) via ALE 5-state 5-action tabular MDP
Benchmarks: Atari 2600 Pong Atari 2600 Carnival Atari 2600 Riverraid Atari 2600 Seaquest 5-state 5-action tabular MDP
Metrics: sub-optimality gap log-log convergence slope episode return
Baselines: Policy Gradient (PG) Heavy-Ball PG (HBPG)
Builds on: Nesterov's accelerated gradient policy gradient convergence under softmax parameterization (Mei et al.) monotone NAG with restart (O'Donoghue and Candès / Li and Lin)
Closest papers by meaning
- Marginal Policy Gradients: A Unified Family of Estimators for Bounded Action Spaces with Applications (ICLR 2019 · similarity 0.89)
- Reusing Trajectories in Policy Gradients Enables Fast Convergence (ICML 2026 · similarity 0.89)
- Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity (ICML 2025 · similarity 0.89)
- Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework (NeurIPS 2026 · similarity 0.88)
- SAPG: Split and Aggregate Policy Gradients (ICML 2024 · similarity 0.87)
- Nesterov acceleration in benignly non-convex landscapes (ICLR 2025 · similarity 0.87)
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.