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

Improved Regret Analysis For Parallel Gaussian Process Bandit Optimization

NeurIPS 2026 · 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.

Gives an improved regret analysis for GP batched Thompson sampling (GP-BTS) that replaces the multiplicative Q factor with an additive one without an initial uncertainty-sampling phase, and derives much tighter noiseless regret bounds.

Problem

Parallel/delayed GP bandit optimization: known regret bounds for GP-BUCB and GP-BTS degrade multiplicatively with batch size Q, and prior fixes need an impractical initial uncertainty-sampling phase.

Approach

A new elliptical-potential-style count lemma over the set of iterations with inflated posterior variance >= lambda^2/Q, which decouples Q as an additive term; combined with a modified instantaneous regret bound for GP-TS, yielding additive-in-Q regret for GP-BTS with no initial US phase, and tighter noiseless bounds.

Key results

• Noisy setting: GP-BTS cumulative regret O(Q ln^{d+1} Q + sqrt(T ln^{2d+3} T)) for SE kernels, replacing the multiplicative sqrt(Q) factor of prior analysis with an additive term.
• Noiseless setting: GP-BTS cumulative regret O(Q ln^{1/2} T) for SE kernels and O(Q ln^{1/2} T) for Matern with d < nu, versus O(sqrt(QT ...)) for prior batched bounds.
• Experiments on synthetic GP functions show regret dependence on Q is mild for Q <= 4.

Surprising findings

• Experimental dependence on Q appears milder than the theoretical upper bound suggests, particularly for Q <= 4.

Limitations

• Expected (not high-probability) regret bounds; noiseless high-probability bound open.
• Discretization error for GP-TS incurs extra ln T factor in noisy setting.
• Analysis is for deterministic delay/batch setting; GP-BUCB not covered by the technique.

Experimental setup

Datasets: synthetic GP sample paths on a discrete grid {0,0.1,...,0.9}^3

Benchmarks: synthetic GP objective on discrete domain (d=3)

Metrics: cumulative regret simple regret (theory)

Baselines: GP-BTS (prior analysis) GP-UCB-batch sequential GP-UCB sequential GP-TS

Builds on: GP-BTS GP-BUCB GP-TS elliptical potential count lemma maximum information gain bounds

Closest papers by meaning

• Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits (NeurIPS 2025 · similarity 0.94)
• Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · 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.90)
• Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.89)
• Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.89)