$(ε, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929240098734080 |
|---|---|
| author | Genalti, Gianmarco Marsigli, Lupo Gatti, Nicola Metelli, Alberto Maria |
| author_facet | Genalti, Gianmarco Marsigli, Lupo Gatti, Nicola Metelli, Alberto Maria |
| contents | Heavy-tailed distributions naturally arise in several settings, from finance to telecommunications. While regret minimization under subgaussian or bounded rewards has been widely studied, learning with heavy-tailed distributions only gained popularity over the last decade. In this paper, we consider the setting in which the reward distributions have finite absolute raw moments of maximum order $1+ε$, uniformly bounded by a constant $u<+\infty$, for some $ε\in (0,1]$. In this setting, we study the regret minimization problem when $ε$ and $u$ are unknown to the learner and it has to adapt. First, we show that adaptation comes at a cost and derive two negative results proving that the same regret guarantees of the non-adaptive case cannot be achieved with no further assumptions. Then, we devise and analyze a fully data-driven trimmed mean estimator and propose a novel adaptive regret minimization algorithm, AdaR-UCB, that leverages such an estimator. Finally, we show that AdaR-UCB is the first algorithm that, under a known distributional assumption, enjoys regret guarantees nearly matching those of the non-adaptive heavy-tailed case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02975 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | $(ε, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits Genalti, Gianmarco Marsigli, Lupo Gatti, Nicola Metelli, Alberto Maria Machine Learning Artificial Intelligence Heavy-tailed distributions naturally arise in several settings, from finance to telecommunications. While regret minimization under subgaussian or bounded rewards has been widely studied, learning with heavy-tailed distributions only gained popularity over the last decade. In this paper, we consider the setting in which the reward distributions have finite absolute raw moments of maximum order $1+ε$, uniformly bounded by a constant $u<+\infty$, for some $ε\in (0,1]$. In this setting, we study the regret minimization problem when $ε$ and $u$ are unknown to the learner and it has to adapt. First, we show that adaptation comes at a cost and derive two negative results proving that the same regret guarantees of the non-adaptive case cannot be achieved with no further assumptions. Then, we devise and analyze a fully data-driven trimmed mean estimator and propose a novel adaptive regret minimization algorithm, AdaR-UCB, that leverages such an estimator. Finally, we show that AdaR-UCB is the first algorithm that, under a known distributional assumption, enjoys regret guarantees nearly matching those of the non-adaptive heavy-tailed case. |
| title | $(ε, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2310.02975 |