Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Bayesian Analysis of Combinatorial Gaussian Process Bandits
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.
Derives Bayesian cumulative regret bounds for GP-UCB, GP-BayesUCB (GP-BUCB) and GP-TS in the infinite, volatile, combinatorial semi-bandit setting and applies a contextual combinatorial GP bandit to energy-efficient EV navigation on Luxembourg and Monaco road networks.
Problem
Combinatorial volatile Gaussian process semi-bandits with infinite base-arm sets lack Bayesian regret guarantees, and no regret bound existed for GP-BayesUCB; energy-efficient navigation with negative-energy edges (regenerative braking) needs online learning.
Approach
Extends Bayesian regret analysis of GP-UCB and GP-TS to infinite, volatile and combinatorial arms via a finer discretization that bounds the discretization error of the super-arm UCB, and gives the first regret bound for GP-BUCB by reparametrizing beta_t through an inverse-erf quantile bound; applies the framework to navigation with rectified Gaussian edge weights fed to Dijkstra.
Key results
- GP-TS yields the lowest cumulative regret among the compared methods on the Luxembourg and Monaco routes with T=500 and 5 repetitions.
- The theoretical Bayesian regret for GP-UCB, GP-BUCB and GP-TS in the finite case is O(sqrt(lambda*_K T K beta_T gamma_TK)), sublinear in T for RBF and Matern kernels.
- Lower-beta GP-BUCB parametrizations (xi=0.5) achieve lower cumulative regret than GP-UCB while keeping theoretical guarantees.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Thompson sampling instead of UCB or BUCB | Navigation bandit algorithms · Luxembourg and Monaco evaluation routes | cumulative regret | Helped |
| use a GP model instead of Bayesian inference | Navigation bandit algorithms · Luxembourg and Monaco evaluation routes | cumulative regret | Helped |
| use GP-TS instead of the other evaluated algorithms | Navigation bandit algorithms · Luxembourg and Monaco evaluation routes | cumulative regret | Helped |
| use GP-BUCB instead of GP-UCB | GP-based navigation bandits · Luxembourg and Monaco evaluation routes | cumulative regret | Helped |
| lower the confidence parameter β_t through the tested parametrization (ablation) | GP-UCB and GP-BUCB · Luxembourg and Monaco evaluation routes | cumulative regret | Helped |
| increase the kernel lengthscale (ablation) | GP-based methods · Luxembourg and Monaco evaluation routes | cumulative regret | Hurt |
| vary the kernel lengthscale (ablation) | BI-based methods · Luxembourg and Monaco evaluation routes | cumulative regret | No clear effect |
Surprising findings
- The theoretically valid beta_t for GP-BUCB are smaller than for GP-UCB, and the lower-beta setting yields lower empirical regret, suggesting theoretical beta choices overexplore.
Limitations
- Regret bounds for the infinite case require strong regularity assumptions (Lipschitz mean and kernel, derivative tail bounds) and very fine discretization.
- Experiments are limited to a single horizon T=500 with 5 repetitions on four routes.
- No known lower bounds for GP bandit Bayesian regret make tightness claims only heuristic.
Experimental setup
Datasets: Luxembourg road network Monaco road network elevation data
Benchmarks: Luxembourg road network routes Monaco road network routes
Metrics: cumulative regret
Baselines: GP-UCB GP-TS BI-UCB BI-BUCB BI-TS
Builds on: GP-UCB Bayes-UCB GP-TS Russo and Van Roy posterior sampling regret analysis SVGP
Closest papers by meaning
- Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.91)
- Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization (NeurIPS 2025 · similarity 0.91)
- Improved Regret Analysis For Parallel Gaussian Process Bandit Optimization (NeurIPS 2026 · similarity 0.90)
- Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits (NeurIPS 2025 · similarity 0.90)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.89)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.88)
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.