Data to 13 Oct 2026

On Information Gain and Regret Bounds in Gaussian Process Bandits

arXiv 2009.06966 ↗First posted 15 Sep 2020stat.ML cs.IT cs.LGcited by 156

Not on the map. Why?

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).

Key facts. Cited by 156 papers in the map (data through 13 Oct 2026). First posted on arXiv 15 Sep 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 16; 2022: 19; 2023: 28; 2024: 26; 2025: 37; 2026: 30.

156 papers.

Sort:

By area:

2021Gaussian Process Bandit Optimization with Few Batchescited by 57
2021Misspecified Gaussian Process Bandit Optimizationcited by 53
2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
2021Neural Contextual Bandits without Regretcited by 40
2023Optimistic Active Exploration of Dynamical Systemscited by 32
2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
2024MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximizationcited by 30
2023On the Sublinear Regret of GP-UCBcited by 25
2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
2023Efficient Exploration in Continuous-time Model-based Reinforcement Learningcited by 21
2021Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradientscited by 20

38 more

2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 15
2021Learning curves for Gaussian process regression with power-law priors and targetscited by 14
2022Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimizationcited by 14
2025LLINBO: Trustworthy LLM-in-the-Loop Bayesian Optimizationcited by 14
2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
2023Hallucinated Adversarial Control for Conservative Offline Policy Evaluationcited by 13
2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
2022Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Timescited by 12
2023Quantum Bayesian Optimizationcited by 12
2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
2022Near-Optimal Multi-Agent Learning for Safe Coverage Controlcited by 11
2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
2022Graph Neural Network Banditscited by 10
2023Delayed Feedback in Kernel Banditscited by 10
2022Batch Bayesian optimisation via density-ratio estimation with guaranteescited by 9
2023Tuning Legged Locomotion Controllers via Safe Bayesian Optimizationcited by 9
2024When to Sense and Control? A Time-adaptive Approach for Continuous-Time RLcited by 9
2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
2023Sample Complexity of Kernel-Based Q-Learningcited by 8
2024Safe Guaranteed Exploration for Non-linear Systemscited by 8
2021A Short Note on the Relationship of Information Gain and Eluder Dimensioncited by 7
2024Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Explorationcited by 7
2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 7
2024Bandits with Preference Feedback: A Stackelberg Game Perspectivecited by 7
2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
2023No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximationscited by 6
2024Variational Search Distributionscited by 6
2024Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimalcited by 6
2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
2025Koopman-Equivariant Gaussian Processescited by 6

50 most cited of 156 All 156 (JSON)