📊 statistics

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

This paper demonstrates that GP-UCB can achieve sharper expected and realized regret bounds in time-varying Gaussian process bandits by utilizing per-round local confidence events to operate with a constant exploration parameter, rather than the horizon-growing parameter required by existing analyses.

Original authors: Matthias Mandl, Hanne Kekkonen

Published 2026-08-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthias Mandl, Hanne Kekkonen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where the rules of a game are constantly shifting. You are trying to find the highest point on a landscape, but the ground itself is slowly moving, rising and falling as time passes. This is the reality of many modern decision-making problems, from tuning the settings of a complex computer program to guiding a robot through a changing environment. In these situations, an agent must constantly balance two competing needs: exploring new areas to learn where the ground is going, and exploiting what it already knows to get the best immediate reward. If the landscape were frozen, the agent could eventually map it perfectly and stop searching. But when the terrain drifts, the agent can never truly rest; it must keep moving to stay ahead of the changes.

For decades, scientists have used a mathematical framework called Gaussian processes to model these unknown landscapes. These models act like a flexible sheet that stretches over data points, predicting the shape of the terrain in between. To decide where to look next, algorithms often use a strategy that adds a "confidence bonus" to uncertain areas, encouraging the agent to explore. However, in a world where the ground is moving, previous theories suggested that this confidence bonus had to grow larger and larger as time went on. The logic was that as the agent accumulated more history, the risk of being wrong about the current state of the world increased, so the algorithm needed to become increasingly aggressive in its exploration to stay safe. This requirement meant that the algorithm's behavior had to be carefully tuned to the length of the task, a process that was often difficult and led to inefficient searching over long periods.

A new study by Matthias Mandl and Hanne Kekkonen challenges this long-held assumption. They investigated whether an algorithm could succeed in a drifting environment without ever changing its level of curiosity. By analyzing a specific model where the landscape evolves at a steady, predictable rate, the researchers demonstrated that the algorithm does not need to ramp up its exploration over time. Instead, it can run with a single, fixed level of confidence bonus from the very first moment to the very last. Their work shows that this constant approach is not only possible but also mathematically sound, providing a guarantee that the total error made by the algorithm remains controlled, even as the environment continues to shift.

The key to this discovery lies in how the researchers viewed the passage of time. In a static world, old data remains perfectly relevant forever, so the algorithm must constantly widen its safety margins to account for the growing number of possibilities it has considered. In a drifting world, however, old data naturally loses its value. The researchers realized that because the environment changes, the algorithm effectively "forgets" the distant past. This built-in forgetting prevents the agent from becoming permanently overconfident in its old observations. Consequently, the algorithm does not need to increase its exploration bonus to compensate for the passage of time; the changing environment does that work for it.

The study provides a precise formula for how this fixed level of curiosity should be set. It turns out that the ideal setting depends on how fast the environment is changing. If the landscape shifts very slowly, the agent can afford to be more confident in its past observations, and the optimal setting for the exploration bonus is lower. If the landscape changes rapidly, the agent must be more cautious, and the optimal setting is higher. The researchers found that this relationship is logarithmic, meaning that even if the speed of change varies significantly, the adjustment needed in the algorithm's settings is relatively small and manageable. This offers a simple, practical rule for tuning these systems: look at how fast the world is moving, and set the curiosity level accordingly, then leave it there.

To verify these theoretical findings, the team ran extensive computer simulations. They created a virtual landscape that evolved over ten thousand rounds of decision-making, testing the algorithm with different speeds of change and different fixed levels of curiosity. The results confirmed their theory: the algorithm performed best when the curiosity level was tuned to match the speed of the drift, and this fixed setting consistently outperformed older methods that tried to increase exploration over time. The simulations showed that the algorithm could maintain a steady, low level of error, proving that a constant approach is robust and effective for long-term tasks in changing environments.

This work suggests a fundamental shift in how we might design intelligent systems for dynamic worlds. Instead of programming an agent to become increasingly anxious and exploratory as time passes, we can give it a steady, unwavering level of curiosity that is simply calibrated to the rate of change. This simplifies the design of these systems, removing the need for complex schedules that grow with time. It implies that in a world that never stands still, the most reliable strategy is not to panic and explore more and more, but to maintain a consistent, measured pace of discovery that respects the natural rhythm of the changing environment.

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

Problem Setting
The paper addresses Bayesian optimization in non-stationary environments where the unknown reward function $f_t: S \to \mathbb{R}$ evolves over time. Specifically, the authors consider the Time-Varying Gaussian Process (TV-GP) model introduced by Bogunovic et al. [2016]. In this setting, the latent function evolves according to a Markov recursion driven by GP innovations:
$f_{t+1}(x) = \sqrt{1-\epsilon} f_t(x) + \sqrt{\epsilon} g_{t+1}(x)$
where $g_t$ are i.i.d. draws from a spatial Gaussian process with kernel $k_S$ , and $\epsilon \in (0, 1]$ is a drift parameter controlling the rate of temporal change. The goal is to minimize cumulative regret $R_T = \sum_{t=1}^T (f_t(x_t^*) - f_t(x_t))$ . Unlike static settings, sublinear cumulative regret is generally unachievable here; the objective is to bound the average regret $R_T/T$ as a function of the drift rate $\epsilon$ .

Methodology
The authors revisit the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm in this dynamic setting. Standard analyses for TV-GP bandits typically require the exploration parameter $\beta_t$ to grow with time $t$ to maintain uniform confidence bounds over the entire horizon. This paper proposes a different analytical approach:

Local Confidence Events: Instead of relying on a single global confidence event that holds uniformly over the horizon (which necessitates time-increasing $\beta_t$ ), the analysis constructs local confidence events $E_t$ for each round $t$ .
Constant Exploration Parameter: By utilizing these local events, the authors demonstrate that GP-UCB can be run with a constant exploration parameter $\beta_t \equiv \beta$ .
Discretization and Tail Bounds: The proof combines a per-round UCB regret bound on a local confidence event with an algorithm-agnostic bound on the rare complement event. This involves:
- A spatial grid discretization of size $\tau^d$ .
- Derivative tail bounds (Assumption 1) to control discretization error.
- Sub-Gaussian concentration of the function span $W_t = \sup f_t - \inf f_t$ .
Time-Decayed Information Gain: The authors derive a sharper bound on the time-varying maximum information gain $\tilde{\gamma}_T$ , which controls the sum of posterior variances. They utilize a block decomposition technique to relate $\tilde{\gamma}_T$ to the static information gain $\gamma_N$ and the drift parameter $\epsilon$ .

Key Contributions and Results

Constant Exploration Regret Bound: The primary theoretical result (Theorem 1) establishes an expected cumulative regret bound for constant- $\beta$ TV-GP-UCB:
$E[R_T] \le \sqrt{C_1 T \beta \tilde{\gamma}_T} + T C_2 + T \delta C_3$
where $\tilde{\gamma}_T$ is the time-varying maximum information gain. This bound holds for any fixed drift rate $\epsilon > 0$ without requiring $\beta$ to scale with $T$ .
Sharper Information Gain Scaling: The paper derives a new bound for the time-varying information gain. If the static information gain satisfies $\gamma_N = \tilde{O}(N^q)$ , then in the persistent-drift regime (where the horizon $T$ exceeds the effective block length), the average information gain scales as:
$\frac{\tilde{\gamma}_T}{T} = \tilde{O}\left(\epsilon^{\frac{2(1-q)}{4-q}}\right)$
Consequently, the expected average regret scales as:
$\frac{E[R_T]}{T} = \tilde{O}\left(\epsilon^{\frac{1-q}{4-q}}\right)$
For the squared exponential kernel ( $q=0$ ), this yields an average regret of $\tilde{O}(\epsilon^{1/4})$ .
Bound-Suggested Exploration Parameter: The analysis reveals that the optimal constant $\beta$ (denoted $\beta_{opt}$ ) suggested by balancing the regret bound terms depends logarithmically on the inverse of the drift rate:
$\beta_{opt} \propto \log(1/\epsilon)$
This contrasts with previous schedules where $\beta_t$ was independent of $\epsilon$ . The paper argues that as drift slows ( $\epsilon \to 0$ ), past observations remain informative longer, reducing posterior variance; a larger $\beta$ compensates for this by placing higher value on reducing remaining uncertainty.
Realized Regret Guarantees: The paper provides both post-hoc and prescribed-confidence guarantees for realized regret. In the prescribed-confidence setting, the algorithm can run with a constant $\beta$ while achieving a high-probability regret bound with logarithmic dependence on the failure probability $\omega$ .
Sampling Frequency Adaptation: The framework provides a heuristic for adjusting $\beta$ when the sampling frequency changes. If observations are collected every $\Delta$ time units, the effective drift becomes $\epsilon_\Delta = 1 - (1-\epsilon)^\Delta$ , and the suggested $\beta$ scales with $\log(1/\epsilon_\Delta)$ .

Significance and Claims
The paper claims that its analysis resolves a recurring limitation in time-varying GP bandit literature: the need for time-increasing exploration schedules that lead to deteriorating performance on long horizons and require difficult tuning. By shifting from global to local confidence events, the authors show that rigorous performance guarantees can be maintained with a constant exploration parameter.

The significance lies in:

Improved Long-Horizon Scaling: Removing the $\sqrt{\log T}$ factor often introduced by union bounds over time in the leading regret term.
Explicit Drift Dependence: Providing a theoretical basis for how the exploration parameter should scale with the environmental drift rate $\epsilon$ , rather than just time $t$ .
Sharper Bounds: Offering tighter rates for the time-varying information gain compared to prior work (e.g., Bogunovic et al. [2016], Imamura et al. [2020]).

Empirical Validation
The authors support their theoretical findings with a simulation study on a 2D domain using a squared exponential kernel. They simulate $T=10,000$ rounds using a Kalman filter implementation to handle the time-varying posterior efficiently. The results confirm that:

A broad range of constant $\beta$ values outperforms time-growing logarithmic heuristics.
The empirically optimal constant $\hat{\beta}_{opt}$ increases linearly with $-\log(\epsilon)$ , validating the theoretical prediction $\beta_{opt} \propto \log(1/\epsilon)$ .

Limitations and Future Directions
The authors note that their analysis relies on the specific geometric temporal kernel induced by the Markov drift model. Extending these guarantees to more general temporal kernels remains an open problem. Additionally, the current analysis assumes the drift parameter $\epsilon$ is known; adapting $\beta$ online when $\epsilon$ is unknown is a suggested direction for future work. The paper also acknowledges that the constant-exploration result is a "positive-drift" result and does not recover the standard static sublinear regret guarantee at $\epsilon=0$ , which requires separate analysis.

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

More like this