Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
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 GP-UCB in the Bayesian setting attains Õ(√T) cumulative regret under Matérn kernels with 2ν+d ≤ ν² and O(√(T ln² T)) under SE kernels, by refining information-gain bounds using concentration of the GP-UCB input sequence near the maximizer.
Problem
Existing regret bounds for GP-UCB in the Bayesian setting (GP-distributed objective) are loose: Õ(T^{(ν+d)/(2ν+d)}) for Matérn and O(√(T ln^{d+2} T)) for SE, while the best known bound is O(√(T ln T)) from a successive-elimination algorithm.
Approach
Decompose regret into a lenient-regret term and a near-maximizer term; show that GP-UCB's inputs concentrate near the maximizer under sample path regularity (quadratic growth around x*), so the information gain is evaluated on a shrinking ball around x*, tightening the MIG-based bound.
Key results
- Matérn kernel with 2ν+d ≤ ν²: GP-UCB cumulative regret Õ(√T) with high probability, improving on the prior Õ(T^{(ν+d)/(2ν+d)}) bound.
- Squared exponential kernel: O(√(T ln² T)) regret, improving on the prior O(√(T ln^{d+2} T)).
- Empirical illustration in 1D (σ²=3, Matérn ν=5/2) shows GP-UCB inputs concentrate around the maximizer and information gain grows like Case I (ln t) after t≈30.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use refined information-gain analysis that captures concentration of GP-UCB inputs around the maximizer | GP-UCB with a Matérn kernel satisfying 2ν + d ≤ ν² · Bayesian BO, Matérn kernel | cumulative regret upper bound: \widetilde{O}\rbr{T^{\frac{\nu + d}{2\nu + d}}} -> \widetilde{O}\rbr{\sqrt{T}} | Helped |
| Use refined information-gain analysis that captures concentration of GP-UCB inputs around the maximizer | GP-UCB with a squared exponential kernel · Bayesian BO, squared exponential kernel | cumulative regret upper bound: O\rbr{\sqrt{T \ln^{d+2} T}} -> O\rbr{\sqrt{T \ln^2 T}} | Helped |
Limitations
- Expected regret bound not obtained because dependence of sample-path constants on the confidence level is unknown.
- Matérn result requires additional smoothness condition 2ν+d ≤ ν²; otherwise regret is larger than Õ(√T).
- Only the dependence on T is improved; dependence on d and other parameters is not claimed to improve, and the worst-case frequentist bound is not improved.
Experimental setup
Metrics: cumulative regret
Baselines: GP-UCB (Srinivas et al.) successive elimination GP bandit (Salgia et al.)
Builds on: GP-UCB successive elimination for GP bandits (Salgia et al.) maximum information gain (Srinivas et al.) lenient regret analysis of GP-UCB partition-based GP bandit analysis (Shekhar and Javidi)
Closest papers by meaning
- Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits (NeurIPS 2025 · similarity 0.95)
- Improved Regret Analysis For Parallel Gaussian Process Bandit Optimization (NeurIPS 2026 · similarity 0.93)
- Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.93)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.92)
- Bayesian Analysis of Combinatorial Gaussian Process Bandits (ICLR 2025 · similarity 0.91)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.