Structure Matters: Dynamic Policy Gradient
Sara Klein, Xiangyuan Zhang, Tamer Basar, Simon Weissmann, Leif Döring
Abstract
In this work, we study γ-discounted infinite-horizon tabular Markov decision processes (MDPs) and introduce a framework called dynamic policy gradient (DynPG). The framework directly integrates dynamic programming with (any) policy gradient method, explicitly leveraging the Markovian property of the environment. DynPG dynamically adjusts the problem horizon during training, decomposing the original infinite-horizon MDP into a sequence of contextual bandit problems. By iteratively solving these contextual bandits, DynPG converges to the stationary optimal policy of the infinite-horizon MDP. To demonstrate the power of DynPG, we establish its non-asymptotic global convergence rate under the tabular softmax parametrization, focusing on the dependencies on salient but essential parameters of the MDP. By combining classical arguments from dynamic programming with more recent convergence arguments of policy gradient schemes, we prove that softmax DynPG scales polynomially in the effective horizon (1 -γ) -1 . Our findings contrast recent exponential lower bound examples for vanilla policy gradient.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Does Stochastic Gradient really succeed for bandits? cites Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods
- Does Stochastic Gradient really succeed for bandits? cites On the Global Convergence Rates of Softmax Policy Gradient Methods
- Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods cites On the Global Convergence Rates of Softmax Policy Gradient Methods
- ϕ-Update: A Class of Policy Update Methods with Policy Convergence Guarantee cites On the Global Convergence Rates of Softmax Policy Gradient Methods
Cited by top-tier papers2
Builds on2
- On the Global Convergence Rates of Softmax Policy Gradient MethodsJincheng Mei, Chenjun Xiao, Csaba Szepesvári, Dale SchuurmansICML 2020 · 349 citations
- Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient MethodsSara Klein, Simon Weissmann, Leif DöringICLR 2024 · 12 citations
Related papers
- Global Convergence of Policy Gradient in Average Reward MDPsNavdeep Kumar, Yashaswini Murthy, Itai Shufaro, Kfir Yehuda Levy et al.ICLR 2025
- Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision ProcessesDongsheng Ding, Kaiqing Zhang, Tamer Basar, Mihailo R. JovanovicNeurIPS 2020 · 252 citations
- REINFORCE Converges to Optimal Policies with Any Learning RateSamuel Robertson, Thang Chu, Bo Dai, Dale Schuurmans et al.NeurIPS 2025 · 2 citations
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision ProcessesQinbo Bai, Washim Uddin Mondal, Vaneet AggarwalAAAI 2024 · 23 citations
- Ordering-based Conditions for Global Convergence of Policy Gradient MethodsJincheng Mei, Bo Dai, Alekh Agarwal, Mohammad Ghavamzadeh et al.NeurIPS 2023 · 4 citations
