Landscape of Policy Optimization for Finite Horizon MDPs with General State and Action
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908872387592192 |
|---|---|
| author | Chen, Xin Hu, Yifan Zhao, Minda |
| author_facet | Chen, Xin Hu, Yifan Zhao, Minda |
| contents | Policy gradient methods are widely used in reinforcement learning. Yet, the nonconvexity of policy optimization poses significant challenges in understanding the global convergence of policy gradient methods. For a class of finite-horizon Markov Decision Processes (MDPs) with general state and action spaces, we identify a set of structural properties to establish a benign nonconvex landscape, the Polyak-Łojasiewicz-Kurdyka (PŁK) condition of the policy optimization. Leveraging the PŁK condition, policy gradient methods converge to the globally optimal policy with a non-asymptotic rate despite nonconvexity. Our results apply to various control and operations models, including entropy-regularized tabular MDPs, Linear Quadratic Regulator problems, and both stochastic inventory models and stochastic cash balance problems with strongly convex costs. In these models, stochastic policy gradient methods obtain an $ε$-optimal policy using a sample size of $\tilde{\mathcal{O}}(ε^{-1})$ and polynomial in terms of the planning horizon. To the best of our knowledge, we provide the first sample-complexity guarantees for multi-period inventory systems with Markov-modulated demand and for stochastic cash balance problems. We complement the theory with numerical experiments showing that policy gradient methods outperform several benchmark algorithms from the literature across these operations models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_17138 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Landscape of Policy Optimization for Finite Horizon MDPs with General State and Action Chen, Xin Hu, Yifan Zhao, Minda Optimization and Control Machine Learning Policy gradient methods are widely used in reinforcement learning. Yet, the nonconvexity of policy optimization poses significant challenges in understanding the global convergence of policy gradient methods. For a class of finite-horizon Markov Decision Processes (MDPs) with general state and action spaces, we identify a set of structural properties to establish a benign nonconvex landscape, the Polyak-Łojasiewicz-Kurdyka (PŁK) condition of the policy optimization. Leveraging the PŁK condition, policy gradient methods converge to the globally optimal policy with a non-asymptotic rate despite nonconvexity. Our results apply to various control and operations models, including entropy-regularized tabular MDPs, Linear Quadratic Regulator problems, and both stochastic inventory models and stochastic cash balance problems with strongly convex costs. In these models, stochastic policy gradient methods obtain an $ε$-optimal policy using a sample size of $\tilde{\mathcal{O}}(ε^{-1})$ and polynomial in terms of the planning horizon. To the best of our knowledge, we provide the first sample-complexity guarantees for multi-period inventory systems with Markov-modulated demand and for stochastic cash balance problems. We complement the theory with numerical experiments showing that policy gradient methods outperform several benchmark algorithms from the literature across these operations models. |
| title | Landscape of Policy Optimization for Finite Horizon MDPs with General State and Action |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2409.17138 |