# Gaussian Process bandits with adaptive discretization

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2017.

## Built on by (most cited first, 21 of 21)

- [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)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Uniform Error and Posterior Variance Bounds for Gaussian Process Regression with Application to Safe Control](https://mlsanity.com/paper/2101.05328/) (2021)
- [Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization](https://mlsanity.com/paper/2106.08598/) (2021)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Instance-Dependent Regret Analysis of Kernelized Bandits](https://mlsanity.com/paper/2203.06297/) (2022)
- [Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields](https://mlsanity.com/paper/2305.00322/) (2023)
- [Sample-efficient Bayesian Optimisation Using Known Invariances](https://mlsanity.com/paper/2410.16972/) (2024)
- [Gaussian Process Bandits with Aggregated Feedback](https://mlsanity.com/paper/2112.13029/) (2021)
- [BILBO: BILevel Bayesian Optimization](https://mlsanity.com/paper/2502.02121/) (2025)
- [Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes](https://mlsanity.com/paper/2110.02248/) (2021)
- [Contextual Combinatorial Multi-output GP Bandits with Group Constraints](https://mlsanity.com/paper/2111.14778/) (2021)
- [Optimistic Optimization of Gaussian Process Samples](https://mlsanity.com/paper/2209.00895/) (2022)
- [Episodic Gaussian Process-Based Learning Control with Vanishing Tracking Errors](https://mlsanity.com/paper/2307.04415/) (2023)
- [Adaptive Partitioning Schemes for Optimistic Optimization](https://mlsanity.com/paper/2610.04039/) (2026)

## Abstract (arXiv)

In this paper, the problem of maximizing a black-box function f:X → ℝ is studied in the Bayesian framework with a Gaussian Process (GP) prior. In particular, a new algorithm for this problem is proposed, and high probability bounds on its simple and cumulative regret are established. The query point selection rule in most existing methods involves an exhaustive search over an increasingly fine sequence of uniform discretizations of X. The proposed algorithm, in contrast, adaptively refines X which leads to a lower computational complexity, particularly when X is a subset of a high dimensional Euclidean space. In addition to the computational gains, sufficient conditions are identified under which the regret bounds of the new algorithm improve upon the known results. Finally an extension of the algorithm to the case of contextual bandits is proposed, and high probability bounds on the contextual regret are presented.