Instance-Dependent Regret Analysis of Kernelized Bandits
  We study the kernelized bandit problem, that involves designing an adaptive
strategy for querying a noisy zeroth-order-oracle to efficiently learn about
the optimizer of an unknown function $f$ with a norm bounded by $M<\infty$ in a
Reproducing Kernel Hilbert Space~(RKHS) associated with a positive definite
kernel $K$. Prior results, working in a \emph{minimax framework}, have
characterized the worst-case~(over all functions in the problem class) limits
on regret achievable by \emph{any} algorithm, and have constructed algorithms
with matching~(modulo polylogarithmic factors) worst-case performance for the
\matern family of kernels. These results suffer from two drawbacks. First, the
minimax lower bound gives no information about the limits of regret achievable
by the commonly used algorithms on specific problem instances. Second, due to
their worst-case nature, the existing upper bound analysis fails to adapt to
easier problem instances within the function class. Our work takes steps to
address both these issues. First, we derive \emph{instance-dependent} regret
lower bounds for algorithms with uniformly~(over the function class) vanishing
normalized cumulative regret. Our result, valid for all the practically
relevant kernelized bandits algorithms, such as, GP-UCB, GP-TS and
SupKernelUCB, identifies a fundamental complexity measure associated with every
problem instance. We then address the second issue, by proposing a new minimax
near-optimal algorithm which also adapts to easier problem instances.
