Kernel $ε$-Greedy for Contextual Bandits
Sakshi Arya Bharath K. Sriperumbudur
We consider a kernelized version of the $\epsilon$-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, $\{\epsilon_t\}_t$, and choice of the regularization parameter,
$\{\lambda_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 $\sqrt{T}$ under a margin
condition for finite-dimensional RKHS.