Improved Regret Bounds for Gaussian Process Bandits under Heavy-Tailed Noise

We study Gaussian process bandit optimization of an unknown objective function in a reproducing kernel Hilbert space (RKHS). We assume that the observation noise has a finite $(1+ϵ)$-moment for some $ϵ\in (0,1]$. Unlike the sub-Gaussian noise assumption, this moment condition allows heavy-tailed noise and does not require finite variance when $ϵ<1$. For a horizon $T$ and maximum information gain ${\gamma }_T$, existing regret bounds in this setting scale as either $\tilde{\mathcal{O}}(T^{\frac{2+ϵ}{2(1+ϵ)}}{\gamma }_T)$ or $\tilde{\mathcal{O}}(T^{\frac{1}{1+ϵ}}{\gamma }_T)$, both linear in ${\gamma }_T$. To reduce this dependence on ${\gamma }_T$, we propose the heavy-tailed chaining phased elimination (HT-ChainPE) algorithm, which combines regularized D-optimal design with a robust chained estimator. HT-ChainPE achieves cumulative regret of order $\tilde{\mathcal{O}}(T^{\frac{1}{1+ϵ}}(1\vee {\gamma }_T{)}^{\frac{1+3ϵ}{2(1+ϵ)}})$. For $ϵ<1$, this bound retains the $T^{1/(1+ϵ)}$ dependence achieved in prior work while reducing the exponent of ${\gamma }_T$ below one. We also establish a worst-case cumulative regret lower bound on $[0,1{]}^d$ of $\Omega (T^{\frac{1}{1+ϵ}}{L}_{\delta }^{\frac{ϵ}{1+ϵ}}(\frac{\log (T/L_{\delta })}{\log \log (T/L_{\delta })}{)}^{\frac{dϵ}{1+ϵ}})$ for the squared-exponential kernel, where $L_{\delta }=(1-2\delta )\log (\frac{1-\delta }{\delta })$ and $\delta \in (0,1/3)$. For the Matérn kernel with smoothness $\nu$ on $[0,1{]}^d$, we obtain a lower bound of $\Omega (T^{\frac{\nu +dϵ}{\nu (1+ϵ)+dϵ}}{L}_{\delta }^{\frac{\nu ϵ}{\nu (1+ϵ)+dϵ}})$. Finally, experiments on synthetic and real-world benchmarks show that HT-ChainPE performs competitively against existing methods.