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

Shogo Iwazaki

cs.LGFeb 20, 2026

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

Authors: Shogo Iwazaki

Organizations: LY Corporation, Tokyo, Japan

Abstract

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 $Ω(\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 $Ω(ε^{-2}(\ln \frac{1}ε)^d (\ln \ln \frac{1}ε)^{-d})$ time steps to find an $ε$ -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.

Figures & tables

( Scarlett et al., 2017 )	$\Omega\left(\sqrt{T(\ln T)^{d/2}}\right)$
	Cumulative regret	Simple regret
Upper bound	$O^{\ast}\left(\sqrt{T(\ln T)^{d}}\right)$	$O^{\ast}\Bigl(\frac{1}{\epsilon^{2}}\left(\ln\frac{1}{\epsilon}\right)^{d}\Bigr)$
Lower bound	$\Omega\left(\sqrt{T(\ln T)^{d/2}}\right)$	$\Omega\Bigl(\frac{1}{\epsilon^{2}}\left(\ln\frac{1}{\epsilon}\right)^{d/2}\Bigr)$
Lower bound	$\Omega\left(\sqrt{\frac{T(\ln T)^{d}}{(\ln\ln T)^{d}}}\right)$	$\Omega\Bigl(\frac{\left(\ln\frac{1}{\epsilon}\right)^{d}}{\epsilon^{2}\left(\ln\ln\frac{1}{\epsilon}\right)^{d}}\Bigr)$
( Ours )

Table 1: A comparison between best known upper bounds and lower bounds for the SE kernel on the hyperspherical input domain

\mathcal{X}=\mathbb{S}^{d}

. For the simple regret, the table below shows the upper and lower bounds on the number of time steps required for the simple regret to become smaller than

\epsilon>0

Figure 1: Illustrative example of

\mathcal{F}_{\epsilon}

in one dimension ( Scarlett et al., 2017 , adapted from Figure 1 in) .

Figure 2: Visualization of the function

f_{\epsilon,N,\bm{z}}

with

\epsilon=0.5

and

d=1

(i.e., the function on the 2D circle

\mathbb{S}^{1}

). Note that the above plot takes the geodesic distance

\rho(\bm{x},\bm{z})\coloneqq\arccos(\bm{x}^{\top}\bm{z})

from some center point

\bm{z}\in\mathbb{S}^{1}

as the horizontal axis. Intuitively, the number

N

controls the sharpness of the behavior around the peak at

\rho(\bm{x},\bm{z})=0

Explore similar work

May 11, 2026

Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves

\tilde{O}(\sqrt{T γ_T})

adversarial regret, where

T

and

γ_T

denote the number of total rounds and the maximum information gain, respectively. For squared exponential (SE) and

ν

-Matérn kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nyström approximation while maintaining nearly optimal regret guarantees.

Shogo Iwazaki

LY Corporation Tokyo, Japan

Multi-Armed Bandits Adversarial Bandits

Ask PDF

Oct 8, 2026

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain

γ_T

. In particular, the best existing upper bounds scale as

\sqrt{Tγ_T}

up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general

Ω(\sqrt{Tγ_T/\log T})

minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly

Θ(\sqrt{Tγ_T})

(i.e., within constant factors) for the Matérn-

ν

kernel with

ν\in (0,2)

γ

-exponential kernel with

γ\in (0,2)

, and certain piecewise-polynomial kernels.

Chenkai Ma, Jonathan Scarlett

National University of Singapore

Minimax Regret Multi-Armed Bandits Information-Theoretic Lower Bounds

Ask PDF

Aug 19, 2026

Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields

\tildeγ_T/T=\widetilde{\mathcal O}(ε^{1/2})

and expected average regret

\widetilde{\mathcal O}(ε^{1/4})

in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on

1/ε

Matthias Mandl, Hanne Kekkonen

Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft

Bayesian Optimization Non-Stationary Bandits Dynamic Regret Minimization UCB Algorithms Multi-Armed Bandits

Ask PDF

Abstract

Explore similar work

Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

A General Ω~(TγT)\widetildeΩ(\sqrt{T γ_T})Ω(TγT​​) Lower Bound for Kernel Bandits

Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits