Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere

We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the *dimension-dependent* logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers $\Omega(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}})$ cumulative regret, where $T$ and $d$ represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires $\Omega(\epsilon^{-2}(\ln \frac{1}{\epsilon})^d (\ln \ln \frac{1}{\epsilon})^{-d})$ time steps to find an $\epsilon$-optimal point. We also provide the improved $O((\ln T)^{d+1}(\ln \ln T)^{-d})$ upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to *dimension-independent* logarithmic factors under a hyperspherical input domain.

In the field of machine learning, we often use “Gaussian process” to help computers make decisions under uncertainty. While we have many algorithms that work well in practice, our theoretical understanding of their fundamental limits is still incomplete. Specifically, there has been a persistent mathematical gap between the best-case performance we can prove and the worst-case errors we expect an algorithm to make. Understanding this gap is important for determining whether our current methods can truly be improved or if they are already reaching a natural limit. Our study focuses on narrowing this gap for one of the most common mathematical models, the “squared exponential kernel.” By carefully analyzing how this model behaves in a multi-dimensional, spherical space, we have derived a new mathematical "lower bound." This provides a more precise estimate of the minimum amount of error—or "regret"—that any such decision-making process must inevitably encounter. We also provided an updated analysis of how much information these models can capture, which helps align the theory more closely with what we observe in practice. This research does not claim to create a new, faster algorithm; rather, it helps clarify the mathematical landscape in which existing algorithms operate. By showing that the current methods are already quite close to the theoretical limit, our findings suggest that future progress may lie in areas other than just seeking faster learning speeds. We hope that providing these clearer boundaries will help the research community develop a more grounded and realistic understanding of what is possible in automated decision-making.