Publications
カンファレンス (国際) Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
Shogo Iwazaki
Fourty-Third International Conference on Machine Learning (ICML 2026)
2026.7.8
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 bounded norm in the known reproducing kernel Hilbert space. Specifically, we focus on the squared exponential kernel, which is one of the most widely used kernel functions for GP bandits. One of the remaining open questions for this problem is the gap of the dimension-dependent logarithmic factor between upper and lower bounds. This paper partially resolves this open question under the hyperspherical input domain. We show that any algorithm suffers from Ω(√(T (ln T)ᵈ (ln ln T)⁻ᵈ)) cumulative regret, where T and d represent the total step size and the dimension of the hypersphere, respectively. Regarding the simple regret, we show that any algorithm requires Ω(ε⁻² (ln(1/ε))ᵈ (ln ln(1/ε))⁻ᵈ) time steps to find ε-optimal point. We also provide the improved O((ln T)ᵈ⁺¹ (ln ln T)⁻ᵈ) upper bound of 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.
Paper :
Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
（外部サイト）