Research map / Reinforcement learning / MDPs and planning
Structure Matters: Dynamic Policy Gradient
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.
Introduces Dynamic Policy Gradient (DynPG), which combines dynamic programming with any policy gradient method by growing the horizon and solving a sequence of contextual bandits, and proves polynomial-in-effective-horizon convergence for tabular softmax parametrization.
Problem
Vanilla policy gradient can take exponential time in the effective horizon (1-γ)^{-1} to converge on discounted infinite-horizon tabular MDPs, because it does not exploit the Markov structure of the environment.
Approach
Extend the horizon one epoch at a time by prepending a new decision epoch, train only the first-action policy of that epoch with policy gradient (a contextual bandit), and freeze previously learned policies for future steps, so that the Bellman structure is used directly within PG.
Key results
- Exact-gradient softmax DynPG achieves overall-error complexity O((1-γ)^{-4} ε^{-1} log((1-γ)^{-2} ε^{-1})) gradient steps, versus the vanilla softmax PG bound with factor C(γ) that can be exponential in (1-γ)^{-1}.
- On a numerical example with γ=0.9 and 0.99, sample-based vanilla PG plateaus at about 0.8 success probability while DynPG converges to the optimal policy (success probability approaching 1).
- Sample-based DynPG gives a high-probability sample complexity polynomial in (1-γ)^{-1}, scaling as (1-γ)^{-17} times ε^{-8} and other factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use dynamic policy gradient instead of vanilla policy gradient | Tabular softmax policy optimization · Exact-gradient discounted MDPs | gradient-step complexity dependence on effective horizon: O\big( (1-\gamma)^{-6}\epsilon^{-1}\big) upper bound for softmax PG; O\big( (1-\gamma)^{-4} \epsilon^{-1} \log((1-\gamma | Helped |
| Use DynPG instead of softmax PG | Lower-bound MDP · Lower-bound MDP, ε=0.15 | gradient-step complexity: |\cS|^{2^{\Omega((1-\gamma)^{-1})}} gradient steps for softmax PG; O\big( (1-\gamma)^{-4} \epsilon^{-1} \log((1-\gamma)^ | Helped |
| Use DynPG instead of vanilla PG | Tabular softmax policies · Committal-behavior MDP, γ=0.9 and γ=0.99 | success probability of reaching overall error ε=0.01: vanilla PG ... can only reach the success probability of around 0.8 | Helped |
| Use DynPG instead of vanilla PG | Tabular softmax policies · Committal-behavior MDP | success probability | No clear effect |
| Use DynPG instead of vanilla PG | Simpler environments where vanilla PG performs well · Simpler environments | efficiency | No clear effect |
Surprising findings
- The last trained non-stationary epoch policy can be used as a stationary policy only with additional training; the stationary policy error term introduces an extra (1-γ)^{-1} factor.
- Vanilla PG is reported to stall on the numerical example at about 0.8 success probability, showing committal behavior.
Limitations
- Theoretical guarantees are for tabular softmax parametrization with exact or sampled gradients; function approximation is not analyzed.
- Stored policies grow linearly with the number of training iterations, creating memory costs; DynAC variant lacks convergence guarantees.
- Complexity bounds include an extra log(ε^{-1}) factor and are likely not tight; the numerical example is artificial.
Experimental setup
Benchmarks: custom tabular MDP derived from Q-learning overestimation example
Metrics: success probability of reaching suboptimality 0.01 value function error total gradient steps / sample complexity
Baselines: vanilla softmax policy gradient REINFORCE
Builds on: policy search by dynamic programming vanilla softmax policy gradient REINFORCE performance difference lemma
Closest papers by meaning
- Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods (ICLR 2024 · similarity 0.92)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.89)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.88)
- Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (NeurIPS 2026 · similarity 0.88)
- Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs (NeurIPS 2026 · similarity 0.88)
- Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 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.