Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance
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.
Gives a tighter uniform upper bound on maximum posterior variance for GP models with small noise, and uses it to improve regret bounds for MVR/PE in noiseless, RKHS-norm-dependent, and non-stationary-variance GP bandits.
Problem
Regret analysis of near-optimal GP bandit algorithms (MVR, phased elimination) relies on the maximum posterior variance bound, which is loose when noise variance is small; optimality in noiseless settings, RKHS-norm dependence, and non-stationary noise is not established.
Approach
A new upper bound on the maximum posterior variance that improves noise-variance dependence (via an elliptical potential count lemma and MIG arguments), applied to MVR and PE to get near-optimal noiseless regret, optimal RKHS-norm dependence, and variance-aware regret for non-stationary noise.
Key results
- For the SE kernel in the noiseless setting, PE achieves cumulative regret O(ln T), and for Matérn with nu > d it achieves O(ln T), matching the conjectured lower bound.
- MVR achieves noiseless simple regret exp(-(1/2) T^{1/(d+1)} ln^{-alpha} T) for SE and Õ(T^{-nu/d}) for Matérn kernels.
- In the non-stationary variance setting, VA-PE and VA-MVR achieve regret bounds that match the derived lower bounds up to log factors, except one exceptional Matérn case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the new maximum-posterior-variance bound in PE for noiseless Matérn problems with ν < d | PE · Noiseless GP bandit, Matérn kernel, ν < d | cumulative regret: \widetilde{O}\rbr{T^{\frac{d - \nu}{d}}} vs. conjectured lower bound \Omega\rbr{T^{\frac{d - \nu}{d}}} | Helped |
| use the new maximum-posterior-variance bound in MVR | MVR · Noiseless GP bandit, Matérn kernel, simple regret | simple regret: \widetilde{O}\rbr{T^{-\frac{\nu}{d}}} | Helped |
| use λ² = Θ(B⁻²) in MVR analysis | MVR · Noisy GP bandit, Matérn kernel, simple regret | simple regret: \widetilde{O}\rbr{B^{\frac{d}{2\nu+d}} T^{-\frac{\nu}{2\nu + d}}} | Helped |
| use variance-aware PE with known time-varying variance proxies | VA-PE · Non-stationary variance GP bandit, Matérn kernel, d ≤ 2ν or V_T = Ω(T^{(d−2ν)/d}) | cumulative regret: \widetilde{O}\rbr{V_T^{\frac{\nu}{2\nu+d}} T^{\frac{d}{2\nu+d}}} | Helped |
| use variance-aware MVR with known time-varying variance proxies | VA-MVR · Non-stationary variance GP bandit, Matérn kernel, d > 2ν and V_T = O(T^{(d−2ν)/d}) | simple regret: \widetilde{O}\rbr{T^{-\frac{\nu}{d}}} | Helped |
| use VA-PE instead of VA-GP-UCB | VA-PE · Non-stationary variance GP bandit | cumulative regret | Helped |
Surprising findings
- The noiseless simple regret for SE kernels is worse in the polynomial exponent than the best existing algorithm (GP-UCB+/EXPLOIT+).
Limitations
- Simple regret for SE kernel has a worse exponent than best known result due to MIG bound exponent.
- PE analysis for RKHS norm B cannot use the same max-variance corollary and requires more restrictive growth conditions on B.
- Assumes true variance proxies are observed by the learner in the non-stationary setting.
Experimental setup
Metrics: cumulative regret simple regret
Baselines: GP-UCB SupKernelUCB Kernel-AMM-UCB REDS GP-UCB+ EXPLOIT+ GP-EI Explore-then-Commit VA-GP-UCB
Builds on: GP-UCB phased elimination maximum variance reduction weighted OFUL+
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.94)
- Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization (NeurIPS 2025 · similarity 0.93)
- 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.91)
- Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling (ICLR 2024 · similarity 0.91)
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.