Near-Optimal Regret in Adversarial Kernel Bandits

arXiv:2605.26585v1 Announce Type: new Abstract: 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}}ig(sqrt{T, d_(lambda),log|{X}|}ig), where d_(lambda) 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 Matern(nu,d) kernel with smoothness parameter nu on R^d, for which our bound specializes to widetilde{{O}}ig(T^{(nu+d)/(2nu+d)}ig), 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.

Source: arXiv cs.LG | 2026-05-27