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\"older space.

研究了在核化赌博机问题中，在未知正则性的情况下学习算法是否能够自适应于相关核函数的正则性。通过研究转化不变核的正则性自适应性，我们推导出自适应性的下限，证明不可能在具有不同规则性的RKHS对中同时实现最优累计遗憾。通过连接在不同功能空间中自适应的统计困难性，我们展示了这一下限的紧密性。

核化赌博机中适应误差核正则性