Adaptation to Misspecified Kernel Regularity in Kernelised Bandits
This work addresses a key open problem in continuum-armed bandits for researchers in machine learning and statistics, providing foundational insights into adaptivity across function spaces, though it is incremental as it builds on existing algorithms and theory.
The paper tackles the problem of adaptivity to unknown kernel regularity in kernelised bandit problems, proving an impossibility lower bound for achieving optimal cumulative regret across RKHSs with different regularities and showing that an existing algorithm matches this bound up to logarithmic factors.
In continuum-armed bandit problems where the underlying function resides in a reproducing kernel Hilbert space (RKHS), namely, the kernelised bandit problems, an important open problem remains of how well learning algorithms can adapt if the regularity of the associated kernel function is unknown. In this work, we study adaptivity to the regularity of translation-invariant kernels, which is characterized by the decay rate of the Fourier transformation of the kernel, in the bandit setting. We derive an adaptivity lower bound, proving that it is impossible to simultaneously achieve optimal cumulative regret in a pair of RKHSs with different regularities. To verify the tightness of this lower bound, we show that an existing bandit model selection algorithm applied with minimax non-adaptive kernelised bandit algorithms matches the lower bound in dependence of $T$, the total number of steps, except for log factors. By filling in the regret bounds for adaptivity between RKHSs, we connect the statistical difficulty for adaptivity in continuum-armed bandits in three fundamental types of function spaces: RKHS, Sobolev space, and Hölder space.