Sharper Guarantees for Misspecified Kernelized Bandit Optimization
This paper proves that the misspecification penalty in kernelized bandit optimization — both offline (simple regret) and online (cumulative regret) — can be reduced from a square-root-of-complexity factor to a logarithmic or polylogarithmic one, by exploiting spectral localization in the offline setting and spatial domain-splitting in the online setting.