Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

• URL: http://arxiv.org/abs/2608.18863v1
• Date: Wed, 19 Aug 2026 12:36:05 GMT
• Title: Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
• Abstract summary: GP-UCB can be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate.<n>For the squared exponential kernel, it yields $tilde_T/T=widetildemathcal O(1/2)$ and expected average regret $widetildemathcal O(1/4)$ in the persistent-drift regime.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields $\tildeγ_T/T=\widetilde{\mathcal O}(ε^{1/2})$ and expected average regret $\widetilde{\mathcal O}(ε^{1/4})$ in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on $1/ε$.

Related papers

• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Frequentist Regret Analysis of Gaussian Process Thompson Sampling via Fractional Posteriors [5.7099901327884695]
  We show that variance inflation commonly assumed in existing analyses of GP-TS can be interpreted as Thompson Sampling.<n>We derive a kernel-agnostic regret bound expressed in terms of the information gain parameter $_t$ and the posterior contraction rate $_t$.<n>Overall, our analysis provides a unified and discretization-free regret framework for GP-TS that applies broadly across kernel classes.
  arXiv  Detail & Related papers  (2026-02-16T05:18:13Z)
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  We study stopping rules for gradient descent (SGD) for convex optimization.<n>We develop an anytime-valid, data-dependent upper confidence sequence for the weighted average suboptimality of projected SGD.<n>These are the first rigorous, time-uniform performance guarantees and finitetime $varepsilon$-optimality certificates.
  arXiv  Detail & Related papers  (2025-12-15T09:26:45Z)
• Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization [3.6985338895569204]
  We show that the Gaussian process GP-UCB algorithm achieves $tildeO(sqrtT)$ cumulative regret with high probability.<n>Our analysis yields $O(sqrtT ln2 T)$ regret under a squared exponential kernel.
  arXiv  Detail & Related papers  (2025-06-02T07:38:58Z)
• Regret Analysis for Randomized Gaussian Process Upper Confidence Bound [9.967062483758632]
  This paper analyzes the randomized variant of GP-UCB called improved randomized GP-UCB.<n>We show that GP-UCB using a constant confidence parameter can incur linearly growing expected cumulative regret.
  arXiv  Detail & Related papers  (2024-09-02T06:49:29Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning [0.0]
  We study the problem of episodic reinforcement learning in continuous state-action spaces with unknown rewards and transitions. We propose an algorithm, BEF-RLSVI, that uses penalized maximum likelihood estimators to learn the unknown parameters.
  arXiv  Detail & Related papers  (2022-10-05T08:26:49Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  We study the regret of reinforcement learning from offline data generated by a fixed behavior policy in an infinitehorizon discounted decision process (MDP) We show that given any estimate for the optimal quality function $Q*$, the regret of the policy it defines converges at a rate given by the exponentiation of the $Q*$-estimate's pointwise convergence rate.
  arXiv  Detail & Related papers  (2021-01-31T16:17:56Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  We show how to characterize the trade-off between regret bounds of GP bandit algorithms and complexity of the posterior distributions. We observe state of the art accuracy and complexity trade-offs for GP bandit algorithms applied to global optimization.
  arXiv  Detail & Related papers  (2020-03-23T21:05:15Z)
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
  We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL) In this paper, we introduce an optimistically-perturbed variant of the popular randomized least-squares value (RLSVI) Under the assumption that the Markov decision process has low-rank transition dynamics, we prove that the frequentist regret of RLSVI is upper-bounded by $widetilde O(d2 H2 sqrtT)$ where $ d $ are the feature dimension, $ H $ is the horizon, and $ T $ is the total number of
  arXiv  Detail & Related papers  (2019-11-01T19:48:57Z)

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.