Kernel ϵ-greedy for multi-armed bandits with covariates
Electronic Journal of Statistics · 2026-01-01 · 20 (2) · 5618-5668
DOI: 10.1214/26-ejs2610 ↗At a glance
Journal article in Electronic Journal of Statistics, published on 2026-01-01. Written by Sakshi Arya and 1 co-authors. 53 references.
Abstract (original language)
We consider the ϵ-greedy strategy for the multi-armed 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. In particular, for finite-dimensional RKHSs, we recover the standard O(T2∕3) regret rate for ϵ-greedy strategies without a margin condition and establish an improved rate of O(T4∕7+ε), for any ε>0, under a margin condition, while requiring only finite variance of the reward noise.
Cite
APA
Arya, S., & Sriperumbudur, B. K. (2026). Kernel ϵ-greedy for multi-armed bandits with covariates. Electronic Journal of Statistics, 20(2), 5618-5668. https://doi.org/10.1214/26-ejs2610
Vancouver
Arya S, Sriperumbudur BK. Kernel ϵ-greedy for multi-armed bandits with covariates. Electronic Journal of Statistics. 2026;20(2):5618-5668. doi:10.1214/26-ejs2610
BibTeX
@article{Arya2026,
author = {Arya, Sakshi and Sriperumbudur, Bharath K.},
title = {Kernel ϵ-greedy for multi-armed bandits with covariates},
journal = {Electronic Journal of Statistics},
year = {2026},
volume = {20},
number = {2},
pages = {5618--5668},
doi = {10.1214/26-ejs2610}
}
EUVIMED