# On Information Gain and Regret Bounds in Gaussian Process Bandits

arXiv: https://arxiv.org/abs/2009.06966 · HTML: https://mlsanity.com/paper/2009.06966/

## Key facts

- Cited by 158 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2020.

## Built on by (most cited first, 30 of 158)

- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Optimistic Active Exploration of Dynamical Systems](https://mlsanity.com/paper/2306.12371/) (2023)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximization](https://mlsanity.com/paper/2412.12098/) (2024)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Efficient Exploration in Continuous-time Model-based Reinforcement Learning](https://mlsanity.com/paper/2310.19848/) (2023)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Learning curves for Gaussian process regression with power-law priors and targets](https://mlsanity.com/paper/2110.12231/) (2021)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Communication Efficient Distributed Learning for Kernelized Contextual Bandits](https://mlsanity.com/paper/2206.04835/) (2022)
- [LLINBO: Trustworthy LLM-in-the-Loop Bayesian Optimization](https://mlsanity.com/paper/2505.14756/) (2025)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)
- [Hallucinated Adversarial Control for Conservative Offline Policy Evaluation](https://mlsanity.com/paper/2303.01076/) (2023)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)

## Abstract (arXiv)

Consider the sequential optimization of an expensive to evaluate and possibly non-convex objective function f from noisy feedback, that can be considered as a continuum-armed bandit problem. Upper bounds on the regret performance of several learning algorithms (GP-UCB, GP-TS, and their variants) are known under both a Bayesian (when f is a sample from a Gaussian process (GP)) and a frequentist (when f lives in a reproducing kernel Hilbert space) setting. The regret bounds often rely on the maximal information gain γT between T observations and the underlying GP (surrogate) model. We provide general bounds on γT based on the decay rate of the eigenvalues of the GP kernel, whose specialisation for commonly used kernels, improves the existing bounds on γT, and subsequently the regret bounds relying on γT under numerous settings. For the Mat'ern family of kernels, where the lower bounds on γT, and regret under the frequentist setting, are known, our results close a huge polynomial in T gap between the upper and lower bounds (up to logarithmic in T factors).