No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911228466561024 |
|---|---|
| author | Bayrooti, Jasmine Vakili, Sattar Prorok, Amanda Ek, Carl Henrik |
| author_facet | Bayrooti, Jasmine Vakili, Sattar Prorok, Amanda Ek, Carl Henrik |
| contents | Thompson sampling (TS) is a powerful and widely used strategy for sequential decision-making, with applications ranging from Bayesian optimization to reinforcement learning (RL). Despite its success, the theoretical foundations of TS remain limited, particularly in settings with complex temporal structure such as RL. We address this gap by establishing no-regret guarantees for TS using models with Gaussian marginal distributions. Specifically, we consider TS in episodic RL with joint Gaussian process (GP) priors over rewards and transitions. We prove a regret bound of $\mathcal{\tilde{O}}(\sqrt{KHΓ(KH)})$ over $K$ episodes of horizon $H$, where $Γ(\cdot)$ captures the complexity of the GP model. Our analysis addresses several challenges, including the non-Gaussian nature of value functions and the recursive structure of Bellman updates, and extends classical tools such as the elliptical potential lemma to multi-output settings. This work advances the understanding of TS in RL and highlights how structural assumptions and model uncertainty shape its performance in finite-horizon Markov Decision Processes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_20725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes Bayrooti, Jasmine Vakili, Sattar Prorok, Amanda Ek, Carl Henrik Machine Learning Thompson sampling (TS) is a powerful and widely used strategy for sequential decision-making, with applications ranging from Bayesian optimization to reinforcement learning (RL). Despite its success, the theoretical foundations of TS remain limited, particularly in settings with complex temporal structure such as RL. We address this gap by establishing no-regret guarantees for TS using models with Gaussian marginal distributions. Specifically, we consider TS in episodic RL with joint Gaussian process (GP) priors over rewards and transitions. We prove a regret bound of $\mathcal{\tilde{O}}(\sqrt{KHΓ(KH)})$ over $K$ episodes of horizon $H$, where $Γ(\cdot)$ captures the complexity of the GP model. Our analysis addresses several challenges, including the non-Gaussian nature of value functions and the recursive structure of Bellman updates, and extends classical tools such as the elliptical potential lemma to multi-output settings. This work advances the understanding of TS in RL and highlights how structural assumptions and model uncertainty shape its performance in finite-horizon Markov Decision Processes. |
| title | No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2510.20725 |