Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914674360975360 |
|---|---|
| author | Dorn, Yuriy Katrutsa, Aleksandr Latypov, Ilgam Pudovikov, Andrey |
| author_facet | Dorn, Yuriy Katrutsa, Aleksandr Latypov, Ilgam Pudovikov, Andrey |
| contents | In this study, we propose a new method for constructing UCB-type algorithms for stochastic multi-armed bandits based on general convex optimization methods with an inexact oracle. We derive the regret bounds corresponding to the convergence rates of the optimization methods. We propose a new algorithm Clipped-SGD-UCB and show, both theoretically and empirically, that in the case of symmetric noise in the reward, we can achieve an $O(\log T\sqrt{KT\log T})$ regret bound instead of $O\left (T^{\frac{1}{1+α}} K^{\fracα{1+α}} \right)$ for the case when the reward distribution satisfies $\mathbb{E}_{X \in D}[|X|^{1+α}] \leq σ^{1+α}$ ($α\in (0, 1])$, i.e. perform better than it is assumed by the general lower bound for bandits with heavy-tails. Moreover, the same bound holds even when the reward distribution does not have the expectation, that is, when $α<0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07062 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise Dorn, Yuriy Katrutsa, Aleksandr Latypov, Ilgam Pudovikov, Andrey Machine Learning Optimization and Control In this study, we propose a new method for constructing UCB-type algorithms for stochastic multi-armed bandits based on general convex optimization methods with an inexact oracle. We derive the regret bounds corresponding to the convergence rates of the optimization methods. We propose a new algorithm Clipped-SGD-UCB and show, both theoretically and empirically, that in the case of symmetric noise in the reward, we can achieve an $O(\log T\sqrt{KT\log T})$ regret bound instead of $O\left (T^{\frac{1}{1+α}} K^{\fracα{1+α}} \right)$ for the case when the reward distribution satisfies $\mathbb{E}_{X \in D}[|X|^{1+α}] \leq σ^{1+α}$ ($α\in (0, 1])$, i.e. perform better than it is assumed by the general lower bound for bandits with heavy-tails. Moreover, the same bound holds even when the reward distribution does not have the expectation, that is, when $α<0$. |
| title | Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2402.07062 |