Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914704843079680 |
|---|---|
| author | Gouverneur, Amaury Rodríguez-Gálvez, Borja Oechtering, Tobias J. Skoglund, Mikael |
| author_facet | Gouverneur, Amaury Rodríguez-Gálvez, Borja Oechtering, Tobias J. Skoglund, Mikael |
| contents | This paper studies the Bayesian regret of a variant of the Thompson-Sampling algorithm for bandit problems. It builds upon the information-theoretic framework of [Russo and Van Roy, 2015] and, more specifically, on the rate-distortion analysis from [Dong and Van Roy, 2020], where they proved a bound with regret rate of $O(d\sqrt{T \log(T)})$ for the $d$-dimensional linear bandit setting. We focus on bandit problems with a metric action space and, using a chaining argument, we establish new bounds that depend on the metric entropy of the action space for a variant of Thompson-Sampling.
Under suitable continuity assumption of the rewards, our bound offers a tight rate of $O(d\sqrt{T})$ for $d$-dimensional linear bandit problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03361 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems Gouverneur, Amaury Rodríguez-Gálvez, Borja Oechtering, Tobias J. Skoglund, Mikael Machine Learning This paper studies the Bayesian regret of a variant of the Thompson-Sampling algorithm for bandit problems. It builds upon the information-theoretic framework of [Russo and Van Roy, 2015] and, more specifically, on the rate-distortion analysis from [Dong and Van Roy, 2020], where they proved a bound with regret rate of $O(d\sqrt{T \log(T)})$ for the $d$-dimensional linear bandit setting. We focus on bandit problems with a metric action space and, using a chaining argument, we establish new bounds that depend on the metric entropy of the action space for a variant of Thompson-Sampling. Under suitable continuity assumption of the rewards, our bound offers a tight rate of $O(d\sqrt{T})$ for $d$-dimensional linear bandit problems. |
| title | Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2403.03361 |