  We consider black box optimization of an unknown function in the
nonparametric Gaussian process setting when the noise in the observed function
values can be heavy tailed. This is in contrast to existing literature that
typically assumes sub-Gaussian noise distributions for queries. Under the
assumption that the unknown function belongs to the Reproducing Kernel Hilbert
Space (RKHS) induced by a kernel, we first show that an adaptation of the
well-known GP-UCB algorithm with reward truncation enjoys sublinear
$\tilde{O}(T^{\frac{2 + \alpha}{2(1+\alpha)}})$ regret even with only the
$(1+\alpha)$-th moments, $\alpha \in (0,1]$, of the reward distribution being
bounded ($\tilde{O}$ hides logarithmic factors). However, for the common
squared exponential (SE) and Mat\'{e}rn kernels, this is seen to be
significantly larger than a fundamental $\Omega(T^{\frac{1}{1+\alpha}})$ lower
bound on regret. We resolve this gap by developing novel Bayesian optimization
algorithms, based on kernel approximation techniques, with regret bounds
matching the lower bound in order for the SE kernel. We numerically benchmark
the algorithms on environments based on both synthetic models and real-world
data sets.
