Efficient Prior Selection in Gaussian Process Bandits with Thompson Sampling

• URL: http://arxiv.org/abs/2502.01226v1
• Date: Mon, 03 Feb 2025 10:29:35 GMT
• Title: Efficient Prior Selection in Gaussian Process Bandits with Thompson Sampling
• Authors: Jack Sandberg, Morteza Haghir Chehreghani,
• Abstract summary: We propose two algorithms for joint prior selection and regret minimization in GP bandits. We theoretically analyze the algorithms and establish upper bounds for their respective regret.
• Score: 6.466505075075075
• License:
• Abstract: Gaussian process (GP) bandits provide a powerful framework for solving blackbox optimization of unknown functions. The characteristics of the unknown function depends heavily on the assumed GP prior. Most work in the literature assume that this prior is known but in practice this seldom holds. Instead, practitioners often rely on maximum likelihood estimation to select the hyperparameters of the prior - which lacks theoretical guarantees. In this work, we propose two algorithms for joint prior selection and regret minimization in GP bandits based on GP Thompson sampling (GP-TS): Prior-Elimination GP-TS (PE-GP-TS) and HyperPrior GP-TS (HP-GP-TS). We theoretically analyze the algorithms and establish upper bounds for their respective regret. In addition, we demonstrate the effectiveness of our algorithms compared to the alternatives through experiments with synthetic and real-world data.

Related papers

• Bayesian Analysis of Combinatorial Gaussian Process Bandits [6.594362025904486]
  We provide novel cumulative regret bounds for three GP-based algorithms: GP-UCB, GP-BayesUCB and GP-TS. We employ our framework to address the challenging real-world problem of online energy-efficient navigation.
  arXiv  Detail & Related papers  (2023-12-20T00:31:43Z)
• Domain Invariant Learning for Gaussian Processes and Bayesian Exploration [39.83530605880014]
  We propose a domain invariant learning algorithm for Gaussian processes (DIL-GP) with a min-max optimization on the likelihood. Numerical experiments demonstrate the superiority of DIL-GP for predictions on several synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-12-18T16:13:34Z)
• Surrogate modeling for Bayesian optimization beyond a single Gaussian process [62.294228304646516]
  We propose a novel Bayesian surrogate model to balance exploration with exploitation of the search space. To endow function sampling with scalability, random feature-based kernel approximation is leveraged per GP model. To further establish convergence of the proposed EGP-TS to the global optimum, analysis is conducted based on the notion of Bayesian regret.
  arXiv  Detail & Related papers  (2022-05-27T16:43:10Z)
• Fast Gaussian Process Posterior Mean Prediction via Local Cross Validation and Precomputation [0.0]
  We present a fast posterior mean prediction algorithm called FastMuyGPs. It is based upon the MuyGPs hyper parameter estimation algorithm and utilizes a combination of leave-one-out cross-validation, nearest neighbors sparsification, and precomputation. It attains superior accuracy and competitive or superior runtime to both deep neural networks and state-of-the-art GP algorithms.
  arXiv  Detail & Related papers  (2022-05-22T17:38:36Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty. We propose a variant of EI with a standard incumbent defined via the GP predictive mean. We show that our algorithm converges, and achieves a cumulative regret bound of $mathcal O(gamma_TsqrtT)$.
  arXiv  Detail & Related papers  (2022-03-15T13:17:53Z)
• Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times [119.41129787351092]
  We show that sequential black-box optimization based on GPs can be made efficient by sticking to a candidate solution for multiple evaluation steps. We modify two well-established GP-Opt algorithms, GP-UCB and GP-EI to adapt rules from batched GP-Opt.
  arXiv  Detail & Related papers  (2022-01-30T20:42:14Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• Non-Gaussian Gaussian Processes for Few-Shot Regression [71.33730039795921]
  We propose an invertible ODE-based mapping that operates on each component of the random variable vectors and shares the parameters across all of them. NGGPs outperform the competing state-of-the-art approaches on a diversified set of benchmarks and applications.
  arXiv  Detail & Related papers  (2021-10-26T10:45:25Z)
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits [43.03669155559218]
  We study the problem of Gaussian process (GP) bandits under relaxed optimization criteria stating that any function value above a certain threshold is "good enough" On the practical side, we consider the problem of finding a single "good action" according to a known pre-specified threshold, and introduce several good-action identification algorithms that exploit knowledge of the threshold.
  arXiv  Detail & Related papers  (2021-02-11T01:16:58Z)
• Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification [119.41129787351092]
  We introduce BBKB, the first no-regret GP optimization algorithm that provably runs in near-linear time and selects candidates in batches. We show that the same bound can be used to adaptively delay costly updates to the sparse GP approximation, achieving a near-constant per-step amortized cost.
  arXiv  Detail & Related papers  (2020-02-23T17:43:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.