Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909219862609920 |
|---|---|
| author | Tamás, Ambrus Szentpéteri, Szabolcs Csáji, Balázs Csanád |
| author_facet | Tamás, Ambrus Szentpéteri, Szabolcs Csáji, Balázs Csanád |
| contents | Stochastic multi-armed bandits (MABs) provide a fundamental reinforcement learning model to study sequential decision making in uncertain environments. The upper confidence bounds (UCB) algorithm gave birth to the renaissance of bandit algorithms, as it achieves near-optimal regret rates under various moment assumptions. Up until recently most UCB methods relied on concentration inequalities leading to confidence bounds which depend on moment parameters, such as the variance proxy, that are usually unknown in practice. In this paper, we propose a new distribution-free, data-driven UCB algorithm for symmetric reward distributions, which needs no moment information. The key idea is to combine a refined, one-sided version of the recently developed resampled median-of-means (RMM) method with UCB. We prove a near-optimal regret bound for the proposed anytime, parameter-free RMM-UCB method, even for heavy-tailed distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05710 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits Tamás, Ambrus Szentpéteri, Szabolcs Csáji, Balázs Csanád Machine Learning Stochastic multi-armed bandits (MABs) provide a fundamental reinforcement learning model to study sequential decision making in uncertain environments. The upper confidence bounds (UCB) algorithm gave birth to the renaissance of bandit algorithms, as it achieves near-optimal regret rates under various moment assumptions. Up until recently most UCB methods relied on concentration inequalities leading to confidence bounds which depend on moment parameters, such as the variance proxy, that are usually unknown in practice. In this paper, we propose a new distribution-free, data-driven UCB algorithm for symmetric reward distributions, which needs no moment information. The key idea is to combine a refined, one-sided version of the recently developed resampled median-of-means (RMM) method with UCB. We prove a near-optimal regret bound for the proposed anytime, parameter-free RMM-UCB method, even for heavy-tailed distributions. |
| title | Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2406.05710 |