Regret Bounds for Noise-Free Kernel-Based Bandits
This work tackles a theoretical gap in black-box optimization for researchers, but it is incremental as it builds on existing noisy setting results without presenting new empirical gains.
The paper addresses the noise-free kernel-based bandit problem, where exact function values are accessible without observation noise, and discusses several upper bounds on regret, conjecturing an order optimal bound but without providing concrete numerical results.
Kernel-based bandit is an extensively studied black-box optimization problem, in which the objective function is assumed to live in a known reproducing kernel Hilbert space. While nearly optimal regret bounds (up to logarithmic factors) are established in the noisy setting, surprisingly, less is known about the noise-free setting (when the exact values of the underlying function is accessible without observation noise). We discuss several upper bounds on regret; none of which seem order optimal, and provide a conjecture on the order optimal regret bound.