A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
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_ | 1866915273960849408 |
|---|---|
| author | Ganesh, Swetha Mondal, Washim Uddin Aggarwal, Vaneet |
| author_facet | Ganesh, Swetha Mondal, Washim Uddin Aggarwal, Vaneet |
| contents | This work examines average-reward reinforcement learning with general policy parametrization. Existing state-of-the-art (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and dependence on knowledge of mixing times and hitting times. To address these limitations, we propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve a global convergence rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$ for average-reward Markov Decision Processes (MDPs) (where $T$ is the horizon length), without requiring the knowledge of mixing and hitting times. Moreover, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18878 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach Ganesh, Swetha Mondal, Washim Uddin Aggarwal, Vaneet Machine Learning This work examines average-reward reinforcement learning with general policy parametrization. Existing state-of-the-art (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and dependence on knowledge of mixing times and hitting times. To address these limitations, we propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve a global convergence rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$ for average-reward Markov Decision Processes (MDPs) (where $T$ is the horizon length), without requiring the knowledge of mixing and hitting times. Moreover, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces. |
| title | A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2407.18878 |