Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance

• URL: http://arxiv.org/abs/2502.06363v1
• Date: Mon, 10 Feb 2025 11:29:27 GMT
• Title: Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance
• Authors: Shogo Iwazaki, Shion Takeno,
• Abstract summary: 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.
• Score: 6.379833644595456
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the Gaussian process (GP) bandit problem, whose goal is to minimize regret under an unknown reward function lying in some reproducing kernel Hilbert space (RKHS). The maximum posterior variance analysis is vital in analyzing near-optimal GP bandit algorithms such as maximum variance reduction (MVR) and phased elimination (PE). Therefore, we first show the new upper bound of the maximum posterior variance, which improves the dependence of the noise variance parameters of the GP. By leveraging this result, we refine the MVR and PE to obtain (i) a nearly optimal regret upper bound in the noiseless setting and (ii) regret upper bounds that are optimal with respect to the RKHS norm of the reward function. Furthermore, as another application of our proposed bound, we analyze the GP bandit under the time-varying noise variance setting, which is the kernelized extension of the linear bandit with heteroscedastic noise. For this problem, we show that MVR and PE-based algorithms achieve noise variance-dependent regret upper bounds, which matches our regret lower bound.

Related papers

• Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits [0.0]
  We introduce a novel frequentist IDS algorithm that iteratively refines a high-probability upper bound on the true parameter norm using accumulating data. We establish regret bounds for our algorithm that do not depend on an initially assumed parameter norm bound and demonstrate that our method outperforms state-of-the-art IDS and UCB algorithms.
  arXiv  Detail & Related papers  (2025-03-07T02:33:37Z)
• Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits [3.6985338895569204]
  We show 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.
  arXiv  Detail & Related papers  (2025-02-26T10:10:51Z)
• 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)
• Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
  We investigate the roles of gradient normalization and clipping in ensuring the convergence of Gradient Descent (SGD) under heavy-tailed noise. Our work provides the first theoretical evidence demonstrating the benefits of gradient normalization in SGD under heavy-tailed noise. We introduce an accelerated SGD variant incorporating gradient normalization and clipping, further enhancing convergence rates under heavy-tailed noise.
  arXiv  Detail & Related papers  (2024-10-21T22:40:42Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• 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)
• Small noise analysis for Tikhonov and RKHS regularizations [0.8133739801185272]
  We establish a small noise analysis framework to assess the effects of norms in Tikhonov and RKHS regularizations. This framework studies the convergence rates of regularized estimators in the small noise limit and reveals the potential instability of the conventional L2-regularizer. A surprising insight is that over-smoothing via these fractional RKHSs consistently yields optimal convergence rates.
  arXiv  Detail & Related papers  (2023-05-18T15:50:33Z)
• 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)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  We optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance.
  arXiv  Detail & Related papers  (2021-10-26T15:02:27Z)
• Weighted Gaussian Process Bandits for Non-stationary Environments [30.49357960656324]
  We develop WGP-UCB, a novel UCB-type algorithm based on weighted Gaussian process regression. A key challenge is how to cope with infinite-dimensional feature maps. We provide universal upper bounds and weight-dependent upper bounds for weighted maximum information gains.
  arXiv  Detail & Related papers  (2021-07-06T03:37:33Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• No-Regret Algorithms for Time-Varying Bayesian Optimization [0.0]
  We adopt the general variation budget model to capture the time-varying environment. We introduce two GP-UCB type algorithms: R-GP-UCB and SW-GP-UCB, respectively. Our results not only recover previous linear bandit results when a linear kernel is used, but complement the previous regret analysis of time-varying Gaussian process bandit.
  arXiv  Detail & Related papers  (2021-02-11T22:35:32Z)
• On Signal-to-Noise Ratio Issues in Variational Inference for Deep Gaussian Processes [55.62520135103578]
  We show that the gradient estimates used in training Deep Gaussian Processes (DGPs) with importance-weighted variational inference are susceptible to signal-to-noise ratio (SNR) issues. We show that our fix can lead to consistent improvements in the predictive performance of DGP models.
  arXiv  Detail & Related papers  (2020-11-01T14:38:02Z)

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.