Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits

NeurIPS 2025 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Gaussian process bandit regret · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that noise-free GP-UCB achieves nearly-optimal cumulative and simple regret bounds (constant regret for SE and Matérn with d<ν) by bounding noise-free posterior standard deviations via maximum information gain.

Problem

Noise-free GP bandits: GP-UCB has only suboptimal regret guarantees, while nearly-optimal noise-free algorithms are non-adaptive despite GP-UCB's better empirical performance.

Approach

Derives algorithm-independent upper bounds on noise-free posterior standard deviations (both minimum and cumulative sums over any input sequence) by comparing to a noisy GP posterior with a tuned noise level and applying the elliptical potential count lemma with the MIG bound; this yields tight regret for GP-UCB.

Key results

• GP-UCB attains constant O(1) cumulative regret under the SE kernel and Matérn kernel with d < ν, matching the conjectured lower bound up to polylog factors.
• Simple regret of noise-free GP-UCB is O(sqrt(T) exp(-C T^{1/(d+1)})) for SE and Õ(T^{-ν/d}) for Matérn, nearly matching lower bounds.
• Empirically, GP-UCB outperforms REDS and PE in average cumulative regret over 3000 runs in d=2 synthetic experiments, but is worse than EI in simple regret.

Measured effects reported in the paper

Surprising findings

• In the Bayesian setting, the analysis yields O(sqrt(ln T)) regret for d<ν, unlike the constant regret in the frequentist setting, which the authors call counterintuitive.
• GP-UCB empirically performs consistently worse than EI in simple regret minimization despite its near-optimal worst-case guarantee.

Limitations

• Results rely on the MIG upper bound from prior work that assumes uniform boundedness of kernel eigenfunctions, which is doubted for general compact domains.
• The SE kernel simple regret rate is conjectured but not shown to be optimal.
• Analysis is limited to SE and Matérn kernels (extension to NTK only sketched).

Experimental setup

Benchmarks: synthetic RKHS objective functions (SE and Matérn kernels, d=2)

Metrics: cumulative regret simple regret

Baselines: GP-UCB REDS PE MVR GP-EI Kernel-AMM-UCB GP-UCB+ EXPLOIT+

Builds on: GP-UCB maximum information gain bounds elliptical potential count lemma phased elimination maximum variance reduction

Closest papers by meaning

• Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization (NeurIPS 2025 · similarity 0.95)
• Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.95)
• Improved Regret Analysis For Parallel Gaussian Process Bandit Optimization (NeurIPS 2026 · similarity 0.94)
• Bayesian Analysis of Combinatorial Gaussian Process Bandits (ICLR 2025 · similarity 0.90)
• Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.90)
• Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.89)