Kernel ε-Greedy for Contextual Bandits
share
We consider a kernelized version of the ϵ-greedy strategy for contextual bandits. More precisely, in a setting with finitely many arms, we consider that the mean reward functions lie in a reproducing kernel Hilbert space (RKHS). We propose an online weighted kernel ridge regression estimator for the reward functions. Under some conditions on the exploration probability sequence, {ϵ_t}_t, and choice of the regularization parameter, {λ_t}_t, we show that the proposed estimator is consistent. We also 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 √(T) under a margin condition for finite-dimensional RKHS.
READ FULL TEXT