Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929235539525632 |
|---|---|
| author | Moradipari, Ahmadreza Pedramfar, Mohammad Zini, Modjtaba Shokrian Aggarwal, Vaneet |
| author_facet | Moradipari, Ahmadreza Pedramfar, Mohammad Zini, Modjtaba Shokrian Aggarwal, Vaneet |
| contents | In this paper, we prove the first Bayesian regret bounds for Thompson Sampling in reinforcement learning in a multitude of settings. We simplify the learning problem using a discrete set of surrogate environments, and present a refined analysis of the information ratio using posterior consistency. This leads to an upper bound of order $\widetilde{O}(H\sqrt{d_{l_1}T})$ in the time inhomogeneous reinforcement learning problem where $H$ is the episode length and $d_{l_1}$ is the Kolmogorov $l_1-$dimension of the space of environments. We then find concrete bounds of $d_{l_1}$ in a variety of settings, such as tabular, linear and finite mixtures, and discuss how how our results are either the first of their kind or improve the state-of-the-art. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_20007 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning Moradipari, Ahmadreza Pedramfar, Mohammad Zini, Modjtaba Shokrian Aggarwal, Vaneet Machine Learning Artificial Intelligence In this paper, we prove the first Bayesian regret bounds for Thompson Sampling in reinforcement learning in a multitude of settings. We simplify the learning problem using a discrete set of surrogate environments, and present a refined analysis of the information ratio using posterior consistency. This leads to an upper bound of order $\widetilde{O}(H\sqrt{d_{l_1}T})$ in the time inhomogeneous reinforcement learning problem where $H$ is the episode length and $d_{l_1}$ is the Kolmogorov $l_1-$dimension of the space of environments. We then find concrete bounds of $d_{l_1}$ in a variety of settings, such as tabular, linear and finite mixtures, and discuss how how our results are either the first of their kind or improve the state-of-the-art. |
| title | Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2310.20007 |