A Unified Lower Bound for Noisy Kernelized Bandit Optimization

Kernelized bandit optimization models the maximization of an unknown function that is expensive to evaluate and can only be observed under noise. Performance is measured by regret, the amount by which the points an algorithm chooses fall below the true maximum. Characterizing such a problem requires bounding regret from two directions: an upper bound says what a particular algorithm achieves, a lower bound says what no algorithm can beat, and an algorithm is known to be optimal only when the two meet. Upper bounds rest on a single quantity, the maximum information gain, and bounding it for a new kernel is enough for a regret guarantee to follow from a general analysis. Lower bounds have no such quantity and are proved one kernel at a time, from families of hard functions tuned to the spectrum of a particular kernel, so a kernel for which no such construction exists has no lower bound. We introduce the missing quantity, the localized packing number, which counts how many functions can be selected from a class so that each peaks in a region of its own while the selected functions stay collectively close to a common reference. We show that these two properties are sufficient: minimax simple and cumulative regret are governed by the resolution at which the packing number balances the sampling budget. We then verify the two conditions in one construction for every kernel whose RKHS is a Sobolev space on a torus or a sphere, using tight frames in place of a construction tailored to one kernel. This yields new lower bounds for the ReLU neural tangent kernel that match the T-dependence of SupNTK-UCB up to logarithmic factors.