An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929698260385792 |
|---|---|
| author | Gouverneur, Amaury Gálvez, Borja Rodriguez Oechtering, Tobias Skoglund, Mikael |
| author_facet | Gouverneur, Amaury Gálvez, Borja Rodriguez Oechtering, Tobias Skoglund, Mikael |
| contents | This paper studies the Bayesian regret of the Thompson Sampling algorithm for bandit problems, building on the information-theoretic framework introduced by Russo and Van Roy (2015). Specifically, it extends the rate-distortion analysis of Dong and Van Roy (2018), which provides near-optimal bounds for linear bandits. A limitation of these results is the assumption of a finite action space. We address this by extending the analysis to settings with infinite and continuous action spaces. Additionally, we specialize our results to bandit problems with expected rewards that are Lipschitz continuous with respect to the action space, deriving a regret bound that explicitly accounts for the complexity of the action space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02140 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces Gouverneur, Amaury Gálvez, Borja Rodriguez Oechtering, Tobias Skoglund, Mikael Machine Learning This paper studies the Bayesian regret of the Thompson Sampling algorithm for bandit problems, building on the information-theoretic framework introduced by Russo and Van Roy (2015). Specifically, it extends the rate-distortion analysis of Dong and Van Roy (2018), which provides near-optimal bounds for linear bandits. A limitation of these results is the assumption of a finite action space. We address this by extending the analysis to settings with infinite and continuous action spaces. Additionally, we specialize our results to bandit problems with expected rewards that are Lipschitz continuous with respect to the action space, deriving a regret bound that explicitly accounts for the complexity of the action space. |
| title | An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.02140 |