Near-Optimal Regret in Adversarial Kernel Bandits

We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose an exponential-weights algorithm built on a regularized importance-weighted loss estimator, together with an explicit correction term that cancels the bias introduced by the regularization. Our main result bounds the regret by \widetilde{O}\big(\sqrt{T, d_(λ),\log|{X}|}\big), where d_(λ) is a widely-adopted notion of effective dimension that captures the complexity of the kernel. Up to logarithmic factors, this matches the known rate achieved in the related stochastic kernel bandit problem. A notable application is the Matérn(ν,d) kernel with smoothness parameter ν on \mathbb{R}^d, for which our bound specializes to \widetilde{O}\big(T^{(ν+d)/(2ν+d)}\big), improving over the best-known prior rate of Chatterji et al. [2019] while simultaneously removing the rank-one adversary assumption required by their analysis. Moreover, this rate is the same as the known optimal rate for stochastic kernel bandits, and also matches a lower bound from concurrent work up to a \log T factor.