Posterior Sampling-based Online Learning for Episodic POMDPs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913560295112704 |
|---|---|
| author | Tang, Dengwang Ye, Dongze Jain, Rahul Nayyar, Ashutosh Nuzzo, Pierluigi |
| author_facet | Tang, Dengwang Ye, Dongze Jain, Rahul Nayyar, Ashutosh Nuzzo, Pierluigi |
| contents | Learning in POMDPs is known to be significantly harder than in MDPs. In this paper, we consider the online learning problem for episodic POMDPs with unknown transition and observation models. We propose a Posterior Sampling-based reinforcement learning algorithm for POMDPs (PS4POMDPs), which is much simpler and more implementable compared to state-of-the-art optimism-based online learning algorithms for POMDPs. We show that the Bayesian regret of the proposed algorithm scales as the square root of the number of episodes and is polynomial in the other parameters. In a general setting, the regret scales exponentially in the horizon length $H$, and we show that this is inevitable by providing a lower bound. However, when the POMDP is undercomplete and weakly revealing (a common assumption in the recent literature), we establish a polynomial Bayesian regret bound. We finally propose a posterior sampling algorithm for multi-agent POMDPs, and show it too has sublinear regret. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_10107 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Posterior Sampling-based Online Learning for Episodic POMDPs Tang, Dengwang Ye, Dongze Jain, Rahul Nayyar, Ashutosh Nuzzo, Pierluigi Machine Learning Artificial Intelligence Systems and Control 93E35 Learning in POMDPs is known to be significantly harder than in MDPs. In this paper, we consider the online learning problem for episodic POMDPs with unknown transition and observation models. We propose a Posterior Sampling-based reinforcement learning algorithm for POMDPs (PS4POMDPs), which is much simpler and more implementable compared to state-of-the-art optimism-based online learning algorithms for POMDPs. We show that the Bayesian regret of the proposed algorithm scales as the square root of the number of episodes and is polynomial in the other parameters. In a general setting, the regret scales exponentially in the horizon length $H$, and we show that this is inevitable by providing a lower bound. However, when the POMDP is undercomplete and weakly revealing (a common assumption in the recent literature), we establish a polynomial Bayesian regret bound. We finally propose a posterior sampling algorithm for multi-agent POMDPs, and show it too has sublinear regret. |
| title | Posterior Sampling-based Online Learning for Episodic POMDPs |
| topic | Machine Learning Artificial Intelligence Systems and Control 93E35 |
| url | https://arxiv.org/abs/2310.10107 |