Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards
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_ | 1866913310857756672 |
|---|---|
| author | Qin, Hao Jun, Kwang-Sung Zhang, Chicheng |
| author_facet | Qin, Hao Jun, Kwang-Sung Zhang, Chicheng |
| contents | We study $K$-armed bandit problems where the reward distributions of the arms are all supported on the $[0,1]$ interval. It has been a challenge to design regret-efficient randomized exploration algorithms in this setting. Maillard sampling \cite{maillard13apprentissage}, an attractive alternative to Thompson sampling, has recently been shown to achieve competitive regret guarantees in the sub-Gaussian reward setting \cite{bian2022maillard} while maintaining closed-form action probabilities, which is useful for offline policy evaluation. In this work, we propose the Kullback-Leibler Maillard Sampling (KL-MS) algorithm, a natural extension of Maillard sampling for achieving KL-style gap-dependent regret bound. We show that KL-MS enjoys the asymptotic optimality when the rewards are Bernoulli and has a worst-case regret bound of the form $O(\sqrt{μ^*(1-μ^*) K T \ln K} + K \ln T)$, where $μ^*$ is the expected reward of the optimal arm, and $T$ is the time horizon length. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_14989 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards Qin, Hao Jun, Kwang-Sung Zhang, Chicheng Machine Learning We study $K$-armed bandit problems where the reward distributions of the arms are all supported on the $[0,1]$ interval. It has been a challenge to design regret-efficient randomized exploration algorithms in this setting. Maillard sampling \cite{maillard13apprentissage}, an attractive alternative to Thompson sampling, has recently been shown to achieve competitive regret guarantees in the sub-Gaussian reward setting \cite{bian2022maillard} while maintaining closed-form action probabilities, which is useful for offline policy evaluation. In this work, we propose the Kullback-Leibler Maillard Sampling (KL-MS) algorithm, a natural extension of Maillard sampling for achieving KL-style gap-dependent regret bound. We show that KL-MS enjoys the asymptotic optimality when the rewards are Bernoulli and has a worst-case regret bound of the form $O(\sqrt{μ^*(1-μ^*) K T \ln K} + K \ln T)$, where $μ^*$ is the expected reward of the optimal arm, and $T$ is the time horizon length. |
| title | Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2304.14989 |