  We consider the problem of optimizing a black-box function based on noisy
bandit feedback. Kernelized bandit algorithms have shown strong empirical and
theoretical performance for this problem. They heavily rely on the assumption
that the model is well-specified, however, and can fail without it. Instead, we
introduce a \emph{misspecified} kernelized bandit setting where the unknown
function can be $\epsilon$--uniformly approximated by a function with a bounded
norm in some Reproducing Kernel Hilbert Space (RKHS). We design efficient and
practical algorithms whose performance degrades minimally in the presence of
model misspecification. Specifically, we present two algorithms based on
Gaussian process (GP) methods: an optimistic EC-GP-UCB algorithm that requires
knowing the misspecification error, and Phased GP Uncertainty Sampling, an
elimination-type algorithm that can adapt to unknown model misspecification. We
provide upper bounds on their cumulative regret in terms of $\epsilon$, the
time horizon, and the underlying kernel, and we show that our algorithm
achieves optimal dependence on $\epsilon$ with no prior knowledge of
misspecification. In addition, in a stochastic contextual setting, we show that
EC-GP-UCB can be effectively combined with the regret bound balancing strategy
and attain similar regret bounds despite not knowing $\epsilon$.
