Closing the Regret Gap for Gaussian Process Bandits with Squared Exponential Kernel

We study minimax lower bounds for Gaussian process bandits with the squared exponential (SE) kernel over compact domains $\mathcal{X}\subset {\mathbb{R}}^d$ with non-empty interior, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). A fundamental open question in this setting has been the dimension-dependent $(\ln T{)}^{d/4}$ gap between existing upper and lower regret bounds. Although recently resolved on the hypersphere, closing this gap on general compact domains has remained open. In this work, we completely resolve this problem. By establishing a norm embedding from the bandlimited Sinc RKHS into the SE RKHS and utilizing the Prolate Spheroidal Wave Functions (PSWFs), we construct a hypothesis class yielding an $\Omega (\sqrt{T(\ln T{)}^d(\ln \ln T{)}^{-d}})$ cumulative regret lower bound and an $\Omega ({ϵ}^{-2}(\ln \frac{1}{ϵ}{)}^d(\ln \ln \frac{1}{ϵ}{)}^{-d})$ sample complexity lower bound for $ϵ$-optimal point identification. These results match known upper bounds up to dimension-independent logarithmic factors.