Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits

• URL: http://arxiv.org/abs/2502.19006v1
• Date: Wed, 26 Feb 2025 10:10:51 GMT
• Title: Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits
• Authors: Shogo Iwazaki,
• Abstract summary: We show the nearly optimal regret upper bound of noise-free GP-UCB.<n>Specifically, our analysis shows the first constant cumulative regret in the noise-free settings for the squared exponential kernel and Mat'ern kernel.
• Score: 3.6985338895569204
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the noise-free Gaussian Process (GP) bandits problem, in which the learner seeks to minimize regret through noise-free observations of the black-box objective function lying on the known reproducing kernel Hilbert space (RKHS). Gaussian process upper confidence bound (GP-UCB) is the well-known GP-bandits algorithm whose query points are adaptively chosen based on the GP-based upper confidence bound score. Although several existing works have reported the practical success of GP-UCB, the current theoretical results indicate its suboptimal performance. However, GP-UCB tends to perform well empirically compared with other nearly optimal noise-free algorithms that rely on a non-adaptive sampling scheme of query points. This paper resolves this gap between theoretical and empirical performance by showing the nearly optimal regret upper bound of noise-free GP-UCB. Specifically, our analysis shows the first constant cumulative regret in the noise-free settings for the squared exponential kernel and Mat\'ern kernel with some degree of smoothness.

Related papers

• Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance [6.379833644595456]
  We study the Gaussian process (GP) bandit problem, whose goal is to minimize regret under an unknown reward function.<n>We show the new upper bound of the maximum posterior variance, which improves the dependence of the noise variance parameters of the GP.<n>We show that MVR and PE-based algorithms achieve noise variance-dependent regret upper bounds, which matches our regret lower bound.
  arXiv  Detail & Related papers  (2025-02-10T11:29:27Z)
• On Improved Regret Bounds In Bayesian Optimization with Gaussian Noise [2.250251490529229]
  convergence analysis of BO algorithms has focused on the cumulative regret under both the Bayesian and frequentist settings for the objective.<n>We establish new pointwise on the prediction error of GP under the frequentist setting with Gaussian noise.<n>We prove improved convergence rates of cumulative regret bound for both GP-UCB and GP-TS.
  arXiv  Detail & Related papers  (2024-12-25T05:57:27Z)
• Regret Optimality of GP-UCB [12.323109084902228]
  Gaussian Process Upper Confidence Bound (GP-UCB) is one of the most popular methods for optimizing black-box functions with noisy observations. We establish new upper bounds on both the simple and cumulative regret of GP-UCB when the objective function to optimize admits certain smoothness property. With the same level of exploration, GP-UCB can simultaneously achieve optimality in both simple and cumulative regret.
  arXiv  Detail & Related papers  (2023-12-03T13:20:08Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
  arXiv  Detail & Related papers  (2023-07-14T13:56:11Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• 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)
• 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)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  We consider the problem of optimizing an unknown (typically non-producing) function with a bounded norm. We introduce an algorithm based on Fast-Slow GP-UCB based on "fast but non-robust" and "slow" We argue that certain dependencies cannot be required depending on the corruption level.
  arXiv  Detail & Related papers  (2020-03-04T09:46:58Z)

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.