Structure Matters: Dynamic Policy Gradient
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929582207139840 |
|---|---|
| author | Klein, Sara Zhang, Xiangyuan Başar, Tamer Weissmann, Simon Döring, Leif |
| author_facet | Klein, Sara Zhang, Xiangyuan Başar, Tamer Weissmann, Simon Döring, Leif |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04913 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Structure Matters: Dynamic Policy Gradient Klein, Sara Zhang, Xiangyuan Başar, Tamer Weissmann, Simon Döring, Leif Machine Learning Optimization and Control Probability 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. |
| title | Structure Matters: Dynamic Policy Gradient |
| topic | Machine Learning Optimization and Control Probability |
| url | https://arxiv.org/abs/2411.04913 |