Near-Optimal Regret in Adversarial Kernel Bandits

We study the adversarial kernel bandit problem, in which the loss at each time step is induced by some bounded (but otherwise arbitrary) element of an RKHS. We propose an exponential-weights algorithm with a regularized importance-weighted estimator and an explicit correction term that controls the estimator's regularization bias. Our main result bounds the regret in terms of a widely-adopted notion of effective dimension that captures the complexity of the kernel. Notably, when the kernel satisfies a polynomial eigendecay condition with exponent $\beta >1$, our regret scales as $T^{(\beta +1)/(2\beta )}$ up to logarithmic factors. This matches a lower bound from existing work (Chatterji, Pacchiano, and Bartlett, ICML 2019) and strictly improves on the upper bound derived in that work (with dependence $T^{\beta /(2(\beta -1))}$), while also having the benefit of dropping their rank-one adversary assumption and instead allowing arbitrary RKHS elements at each step.