When and why randomised exploration works (in linear bandits)
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929713246633984 |
|---|---|
| author | Abeille, Marc Janz, David Pike-Burke, Ciara |
| author_facet | Abeille, Marc Janz, David Pike-Burke, Ciara |
| contents | We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation. With this, we demonstrate that in the $d$-dimensional linear bandit setting, when the action space is smooth and strongly convex, randomised exploration algorithms enjoy an $n$-step regret bound of the order $O(d\sqrt{n} \log(n))$. Notably, this shows for the first time that there exist non-trivial linear bandit settings where Thompson sampling can achieve optimal dimension dependence in the regret. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08870 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When and why randomised exploration works (in linear bandits) Abeille, Marc Janz, David Pike-Burke, Ciara Machine Learning We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation. With this, we demonstrate that in the $d$-dimensional linear bandit setting, when the action space is smooth and strongly convex, randomised exploration algorithms enjoy an $n$-step regret bound of the order $O(d\sqrt{n} \log(n))$. Notably, this shows for the first time that there exist non-trivial linear bandit settings where Thompson sampling can achieve optimal dimension dependence in the regret. |
| title | When and why randomised exploration works (in linear bandits) |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.08870 |