Preprint

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

Matthias Mandl Hanne Kekkonen

Aug 2026 · 0 citations · 26 references

Mathematics Computer Science

TL;DR

Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model is studied, and GP-UCB can be run with a constant exploration parameter and obtained an expected-regret bound whose coefficient depends on the drift rate.

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\gamma_T/T=\widetilde{\mathcal O}(\epsilon^{1/2})$ and expected average regret $\widetilde{\mathcal O}(\epsilon^{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/\epsilon$.

arXiv Semantic Scholar

View source

Similar papers

Preprint Jul 2026

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

We study online convex optimization with stochastic gradient noise whose conditional $p$-th central moment is bounded by $\sigma^p$, for an unknown $p\in(1,2]$. For losses with Lipschitz bound $G$ on a domain of diameter $D$, we obtain expected universal dynamic regret $\widetilde O(GD\sqrt{T\Lambda}+\sigma DT^{1/p}\La...

Vaneet Aggarwal · 0 citations

#machine learning Preprint Sep 2026

Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling

This work introduces a variant of the Thompson Sampling algorithm that uses a fractional or $\alpha$-posterior instead of the standard posterior, and identifies general regularity conditions on the prior and reward distributions that enable a regret analysis of $\alpha$-TS without assuming any tractable approximation o...

Prateek Jaiswal, D. Pati, A. Bhattacharya et al. · 0 citations

Preprint Aug 2026

Time-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Corrections

It is shown that, when $\delta\leq1/2$ and $T/\delta$ is sufficiently large, any deterministic anytime boundary valid uniformly over the stated conditionally sub-Gaussian model class must be at least of order at some time by horizon $T$; for nondecreasing boundaries, this order is required at time $T$.

Yi-Shan Wu · 0 citations

Preprint Aug 2026

Stochastic gradient descent with initial regularization

A variant of stochastic gradient descent with initial regularization with initial regularization is analyzed and dimension-free upper bounds on its expected excess risk for the squared loss are derived.

Nabil Kahalé · 0 citations

Preprint Aug 2026

Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning

This work establishes finite-time rates of $\tilde{O} (1/\sqrt{n})$ for the aforementioned two algorithms under asynchronous Markovian sampling, where $n$ is the iteration index and $\tilde{O}$ hides logarithmic expressions.

Ankur Naskar, A. VivekT, Aditya Kumar et al. · 0 citations

Jul 2026

Parameter-Free Heavy-Tailed Bandits

This work resolves the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters and introduces a scheduled-exploration algorithm that requires no knowledge of $u$ and matches the resulting adaptation frontier up to logarithmic factors.

Gianmarco Genalti, A. Metelli · arXiv.org · 1 citation