A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916307952205824 |
|---|---|
| author | Kitamura, Toshinori Kozuno, Tadashi Kato, Masahiro Ichihara, Yuki Nishimori, Soichiro Sannai, Akiyoshi Sonoda, Sho Kumagai, Wataru Matsuo, Yutaka |
| author_facet | Kitamura, Toshinori Kozuno, Tadashi Kato, Masahiro Ichihara, Yuki Nishimori, Soichiro Sannai, Akiyoshi Sonoda, Sho Kumagai, Wataru Matsuo, Yutaka |
| contents | We study a primal-dual (PD) reinforcement learning (RL) algorithm for online constrained Markov decision processes (CMDPs). Despite its widespread practical use, the existing theoretical literature on PD-RL algorithms for this problem only provides sublinear regret guarantees and fails to ensure convergence to optimal policies. In this paper, we introduce a novel policy gradient PD algorithm with uniform probably approximate correctness (Uniform-PAC) guarantees, simultaneously ensuring convergence to optimal policies, sublinear regret, and polynomial sample complexity for any target accuracy. Notably, this represents the first Uniform-PAC algorithm for the online CMDP problem. In addition to the theoretical guarantees, we empirically demonstrate in a simple CMDP that our algorithm converges to optimal policies, while baseline algorithms exhibit oscillatory performance and constraint violation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_17780 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees Kitamura, Toshinori Kozuno, Tadashi Kato, Masahiro Ichihara, Yuki Nishimori, Soichiro Sannai, Akiyoshi Sonoda, Sho Kumagai, Wataru Matsuo, Yutaka Machine Learning We study a primal-dual (PD) reinforcement learning (RL) algorithm for online constrained Markov decision processes (CMDPs). Despite its widespread practical use, the existing theoretical literature on PD-RL algorithms for this problem only provides sublinear regret guarantees and fails to ensure convergence to optimal policies. In this paper, we introduce a novel policy gradient PD algorithm with uniform probably approximate correctness (Uniform-PAC) guarantees, simultaneously ensuring convergence to optimal policies, sublinear regret, and polynomial sample complexity for any target accuracy. Notably, this represents the first Uniform-PAC algorithm for the online CMDP problem. In addition to the theoretical guarantees, we empirically demonstrate in a simple CMDP that our algorithm converges to optimal policies, while baseline algorithms exhibit oscillatory performance and constraint violation. |
| title | A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2401.17780 |