Research map / Reinforcement learning / MDPs and planning
Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods
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.
Analyzes convergence of softmax policy gradient for finite-horizon MDPs, comparing simultaneous training with a new backward-in-time "dynamic policy gradient", under exact and sampled (REINFORCE-style) gradients without regularisation.
Problem
Global convergence of policy gradient for finite-time-horizon MDPs, where optimal policies are non-stationary and are typically trained simultaneously across epochs, ignoring the dynamic programming structure.
Approach
Dynamic policy gradient trains epoch-dependent softmax parameters sequentially backwards in time (backward induction, each epoch a contextual bandit with fixed future policies), giving convergence bounds scaling as H^3 instead of H^5 for simultaneous PG, plus a stochastic analysis using stopping times to control the lower bound on the probability of optimal actions.
Key results
- Simultaneous PG yields training-step bound scaling as H^5 (N = 10 H^5 R|S| / (c^2 eps) ...), while dynamic PG yields sum of N_h scaling as H^3 for exact gradients.
- Under uniform initialisation the dynamic PG constant c_h equals 1/|A| explicitly, whereas the simultaneous constant c is not explicitly known.
- Stochastic analysis gives high-probability (1-delta) epsilon-optimality for both schemes; the number of training steps scales as H^10 (simultaneous) vs H^7 (dynamic), and batch sizes as H^30 vs H^20.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train policies backwards in time instead of training all epochs simultaneously | Policy gradient for finite-time MDPs with exact gradients · Finite-time MDPs | training-step horizon dependence: H^5 -> H^3 | Helped |
| Train policies backwards in time instead of training all epochs simultaneously | Stochastic policy gradient for finite-time MDPs · Finite-time MDPs | training-step horizon dependence: H^{10} -> H^7 | Helped |
| Train policies backwards in time instead of training all epochs simultaneously | Stochastic policy gradient for finite-time MDPs · Finite-time MDPs | batch-size horizon dependence: H^{30} -> H^{20} | Helped |
| Use uniform initialization | Dynamic PG · Finite-time MDPs | lower bound on c_h: c_h = \frac{1}{|\mathcal A|} | Helped |
Limitations
- Analysis restricted to tabular softmax parametrisation
- Bounds are loose and impractical; batch sizes are very large
- The constant c for simultaneous PG cannot be shown independent of H
Experimental setup
Metrics: convergence bound on suboptimality V*-V number of training steps batch size
Baselines: simultaneous policy gradient
Builds on: Mei et al. 2020 softmax policy gradient convergence Agarwal et al. 2021 PG global convergence Policy gradient theorem Performance difference lemma
Closest papers by meaning
- Structure Matters: Dynamic Policy Gradient (NeurIPS 2025 · similarity 0.92)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.88)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.88)
- Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs (NeurIPS 2026 · similarity 0.88)
- Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity (ICML 2025 · similarity 0.88)
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 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.