Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds
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 tighter Bayesian cumulative regret bounds for Thompson sampling and for PIMS, a hyperparameter-free randomized PI-from-sample-path acquisition function, with experiments against GP-UCB variants, TS, EI, MES and JES.
Problem
Bayesian optimization acquisition functions suffer from manual confidence-parameter tuning (GP-UCB) or over-exploration (TS), and PI-type AFs lack sub-linear cumulative regret bounds.
Approach
Proves the tighter BCR bound (removing sqrt(log T) factor) for TS and introduces PIMS, a probability-of-improvement over the maximum of a posterior sample path, which is equivalent to GP-UCB with a data-driven randomized confidence parameter and achieves the same tighter bound without hyperparameters.
Key results
- PIMS achieves BCR bound O(sqrt(T gamma_T log T)) for continuous domains without discretization in the algorithm, matching TS and IRGP-UCB rates.
- TS is shown to achieve BCR bound sqrt(C1 C2 T gamma_T) for finite domains, removing the sqrt(log T) factor from prior analysis.
- In synthetic experiments PIMS shows best or comparable simple regret versus GP-UCB, IRGP-UCB, TS, EI, MES and JES; TS evaluates higher-variance points (over-exploration).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PIMS instead of GP-UCB | Bayesian optimization · Finite input domain | BCR upper-bound rate | Helped |
| Use TS instead of GP-UCB | Bayesian optimization · Finite input domain | BCR upper-bound rate | Helped |
| Use PIMS without discretizing the algorithm's input domain | PIMS · Continuous input domain | BCR upper-bound rate | Helped |
| Use PIMS instead of TS | Bayesian optimization · Synthetic functions, small length scale | simple regret | Helped |
| Use PIMS instead of GP-UCB-based methods | Bayesian optimization · Synthetic functions, large input domain | simple regret | Helped |
| Use PIMS instead of TS | Bayesian optimization · Ackley and Shekel functions | simple regret | Helped |
| Use PIMS instead of GP-UCB-based methods | Bayesian optimization · Shekel function | simple regret | Helped |
| Use PIMS instead of TS | Bayesian optimization · Real-world emulators: alkox and Fullerenes | best observed value | Helped |
| Use PIMS instead of GP-UCB-based methods | Bayesian optimization · Real-world emulators: alkox and Fullerenes | best observed value | No clear effect |
| Use posterior-sampled maximum as the PI reference instead of the current best observation | PI · Synthetic function experiments | simple regret | Helped |
Surprising findings
- The usual PI with best observation is over-exploitative, while PIMS with sample-path maximum explores appropriately.
Limitations
- Posterior sampling for continuous domains must be approximated by random Fourier features, whose approximation error is not analyzed.
- Regret analysis assumes Bayesian setting; frequentist/RKHS setting left open.
- GP hyperparameter tuning remains necessary and is not covered by the regret analysis.
Experimental setup
Datasets: synthetic GP-sampled functions Ackley function Shekel function alkox emulator dataset Fullerenes emulator dataset
Benchmarks: synthetic GP functions Ackley Shekel alkox emulator Fullerenes emulator
Metrics: simple regret best observed value average posterior standard deviation of evaluated points
Baselines: GP-UCB IRGP-UCB TS EI MES JES PI
Builds on: GP-UCB IRGP-UCB Thompson sampling max-value entropy search random Fourier features
Closest papers by meaning
- Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization (NeurIPS 2025 · similarity 0.92)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · similarity 0.90)
- Principled Preferential Bayesian Optimization (ICML 2024 · similarity 0.90)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.90)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.90)
- Improved Regret Analysis For Parallel Gaussian Process Bandit Optimization (NeurIPS 2026 · similarity 0.89)
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.