Kernel $ε$-Greedy for Multi-Armed Bandits with Covariates
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_ | 1866909630605557760 |
|---|---|
| author | Arya, Sakshi Sriperumbudur, Bharath K. |
| author_facet | Arya, Sakshi Sriperumbudur, Bharath K. |
| contents | We consider the $ε$-greedy strategy for the multi-arm bandit with covariates (MABC) problem, where the mean reward functions are assumed to lie in a reproducing kernel Hilbert space (RKHS). We propose to estimate the unknown mean reward functions using an online weighted kernel ridge regression estimator, and show the resultant estimator to be consistent under appropriate decay rates of the exploration probability sequence, $\{ε_t\}_t$, and regularization parameter, $\{λ_t\}_t$. Moreover, we show that for any choice of kernel and the corresponding RKHS, we achieve a sub-linear regret rate depending on the intrinsic dimensionality of the RKHS. Furthermore, we achieve the optimal regret rate of $\sqrt{T}$ under a margin condition for finite-dimensional RKHS. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_17329 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Kernel $ε$-Greedy for Multi-Armed Bandits with Covariates Arya, Sakshi Sriperumbudur, Bharath K. Machine Learning Statistics Theory 62L10, 62G05, 68T05 We consider the $ε$-greedy strategy for the multi-arm bandit with covariates (MABC) problem, where the mean reward functions are assumed to lie in a reproducing kernel Hilbert space (RKHS). We propose to estimate the unknown mean reward functions using an online weighted kernel ridge regression estimator, and show the resultant estimator to be consistent under appropriate decay rates of the exploration probability sequence, $\{ε_t\}_t$, and regularization parameter, $\{λ_t\}_t$. Moreover, we show that for any choice of kernel and the corresponding RKHS, we achieve a sub-linear regret rate depending on the intrinsic dimensionality of the RKHS. Furthermore, we achieve the optimal regret rate of $\sqrt{T}$ under a margin condition for finite-dimensional RKHS. |
| title | Kernel $ε$-Greedy for Multi-Armed Bandits with Covariates |
| topic | Machine Learning Statistics Theory 62L10, 62G05, 68T05 |
| url | https://arxiv.org/abs/2306.17329 |