PaperlayerView exact revision on arXiv

Source-linked AI summary

Time-Varying Gaussian Process Bandit Optimization

Ilija Bogunovic, Jonathan Scarlett, Volkan Cevher

arXiv:1601.06650v1stat.MLcs.LG

TL;DR

Changing rewards make older observations potentially misleading in sequential Bayesian optimization. The paper models reward evolution with a Markov Gaussian process and introduces resetting and smooth-forgetting GP-UCB algorithms. Its regret bounds characterize the horizon–variation trade-off, with a lower bound showing unavoidable regret under fixed variation.

  • Problem

    In time-varying settings, standard algorithms may deteriorate because they treat stale and fresh data as equally important.

    Source: §1 · p. 1

  • Method

    The paper models the reward function as a Gaussian process evolving through a simple Markov model and introduces R-GP-UCB and TV-GP-UCB.

    Source: §1 · p. 1, §6 · p. 8

  • Results

    E[RT]=Ω(Tϵ) for any GP bandit optimization algorithm under the stated assumptions; the paper’s regret bounds explicitly characterize the trade-off between T and ϵ.

    Source: §1 · p. 2, §4.1 · p. 5

  • Takeaways & Limitations

    The algorithms balance forgetting and remembering while exploiting spatial and temporal correlations, and performed well on real-world data despite the model’s simplicity.

    Source: §6 · p. 8

    The model is primarily suited to steady changes; handling sudden changes is identified as a possible extension.

    Source: §6 · p. 8

Abstract

from arXiv · show

We consider the sequential Bayesian optimization problem with bandit feedback, adopting a formulation that allows for the reward function to vary with time. We model the reward function using a Gaussian process whose evolution obeys a simple Markov model. We introduce two natural extensions of the classical Gaussian process upper confidence bound (GP-UCB) algorithm. The first, R-GP-UCB, resets GP-UCB at regular intervals. The second, TV-GP-UCB, instead forgets about old data in a smooth fashion. Our main contribution comprises of novel regret bounds for these algorithms, providing an explicit characterization of the trade-off between the time horizon and the rate at which the function varies. We illustrate the performance of the algorithms on both synthetic and real data, and we find the gradual forgetting of TV-GP-UCB to perform favorably compared to the sharp resetting of R-GP-UCB. Moreover, both algorithms significantly outperform classical GP-UCB, since it treats stale and fresh data equally.

1 Introduction

Time variation can make old observations misleading, while time-varying GP bandit methods remain less developed than related multi-armed bandit approaches. The paper models evolving rewards with a Markov GP and introduces algorithms and regret bounds for balancing stale and fresh data.

1 Introduction

  • Because stale data can mislead when rewards vary, the paper models the reward function as a Gaussian process evolving according to a simple Markov model.The introduction notes applications such as sensor networks, recommender systems, and finance.Source: §1 · p. 1
  • Prior GP-UCB work addresses time-invariant, contextual, and high-dimensional settings, with smoothness governed by a kernel function.The cited works include regret bounds for GP-UCB.Source: §1 · p. 1
  • Time-varying models have been studied in multi-armed bandits, including restless and rested Markov-reward settings, while GP treatments remain limited.Prior work considered resetting and other forgetting strategies, but finite-arm methods do not exploit spatial correlations across actions.Source: §1 · pp. 1–2
  • The paper introduces regret bounds for two algorithms that characterize the trade-off between time horizon and function variation, and also gives an algorithm-independent lower bound.It demonstrates the model and algorithms on synthetic and real-world data.Source: §1 · p. 2

2 Problem Statement

The problem is to track the changing maximizer of a noisy reward function modeled by a time-varying Gaussian process. The analysis characterizes regret as a function of both the horizon and the rate of variation.

2 Problem Statement

  • Rewards are modeled as Gaussian-process samples with kernel-determined smoothness and Markov evolution; ϵ=0 recovers the standard model, while ϵ=1 makes rewards independent across time.For any ϵ, each ft has marginal distribution GP(0,k), and the model adds one hyperparameter to the standard GP model.Source: §2 · p. 2
  • The model is equivalent to a spatiotemporal kernel with temporal kernel (1−ϵ)^|t1−t2|/2.The paper focuses on this kernel while noting that similar techniques may apply to other stationary temporal kernels.Source: §2 · p. 2
  • Figure 1 illustrates that the location of the maximum can change substantially at distant times for both example kernels.The panels show squared exponential and Matérn kernels with ϵ=0.01 and l=0.2.Source: Figure 1 · p. 3
  • The objective is cumulative regret against the maximizer at each time, rather than competition with a fixed strategy.At each step, the algorithm queries a point in D and observes a noisy reward; the time-varying regret definitions reduce to the time-invariant ones when ϵ=0.Source: §2 · pp. 2–3
  • For fixed ϵ, any GP bandit optimization algorithm incurs expected regret E[RT]=Ω(Tϵ) under the theorem’s kernel assumptions.The lower bound motivates studying the joint dependence of regret on T and ϵ.Source: §2 · p. 3
  • For squared exponential and Matérn kernels, regret bounds are of the form ˜O(Tϵ^α), and are sublinear when ϵ=O(T^-c) for some c>0.When c<1, correlation between f1(x) and fT(x) may be negligible and the maximum may change drastically over the horizon.Source: §2 · p. 3
  • Classical GP-UCB treats previous samples equally, although the model makes older samples increasingly stale.The time-invariant algorithm uses posterior mean and standard deviation to balance exploitation and exploration.Source: §2 · p. 3

3 Algorithms

The algorithms adapt GP-UCB to time-varying rewards through either periodic resets or smooth forgetting. Their update strategies differ in how they retain the influence of older observations.

3 Algorithms

  • R-GP-UCB runs GP-UCB in blocks of size N and resets the posterior at each block’s start, using only samples collected since the latest reset.Its matrix operations are on matrices of size N rather than the full horizon T.Source: §3 · pp. 3–4
  • TV-GP-UCB uses the time-varying model’s posterior updates so older samples contribute less to the posterior mean and variance.It is a special case of contextual GP-UCB with a spatiotemporal kernel, with analysis that characterizes dependence on T and ϵ.Source: §3 · p. 4
  • TV-GP-UCB has the same sequential Bayesian-update complexity as GP-UCB, O(T^2), while R-GP-UCB is less complex.TV-GP-UCB may also be modified to improve efficiency by occasionally resetting or discarding stale data.Source: §3 · p. 4

4 Theoretical Bounds

The paper establishes variation-dependent regret bounds for R-GP-UCB and TV-GP-UCB, with TV-GP-UCB yielding better scaling laws for the specified kernels. An algorithm-independent lower bound shows that regret must grow with the reward function’s rate of variation.

4 Theoretical Bounds

  • The algorithm-independent lower bound and regret results rely on kernel smoothness conditions, with the section assuming known spatial-kernel hyperparameters and ε.The stated assumptions cover the squared-exponential kernel and some Matérn kernels, while the lower-bound assumptions are stronger than those used for the upper bounds.Source: §4 · p. 4, §4.1 · pp. 4–5, §4.2 · p. 5

4.1 Preliminary Definitions and Results

  • Any GP bandit optimization algorithm has expected regret Ω(Tε) under the stated smoothness assumptions.The lower bound also holds in the full-information setting, because the maximum value and its location can change with nonzero probability as the function varies.Source: §4.1 · p. 5

4.2 Main Results

  • The general regret bounds for both algorithms have similar forms, but their analysis must account for the difference between R-GP-UCB’s assumed posterior updates and the true time-varying posterior.The TV-GP-UCB analysis bounds time-varying maximum mutual information using the time-invariant quantity over smaller analysis blocks; these blocks are not algorithmic resets.Source: §4.2 · p. 5
  • For squared-exponential and Matérn kernels, the bounds are specialized and optimized over block length; the resulting TV-GP-UCB bounds have better scaling laws than R-GP-UCB’s.For R-GP-UCB, the optimized block length increases as ε decreases and as the kernel becomes smoother.Source: §4.2 · pp. 5–6
  • When ε vanishes more slowly, TV-GP-UCB’s regret bounds are strictly better than R-GP-UCB’s; for ε = 0, both reduce to the time-invariant bounds.The comparison is stated for the specific-kernel bounds.Source: §4.2 · p. 6

5 Experiments

Across real and synthetic experiments, TV-GP-UCB generally performs better than resetting or standard GP-UCB, while its smooth forgetting produces steadier regret curves. The experiments also examine sensitivity to mismatched variation and reset parameters.

5 Experiments

  • The experiments use synthetic and real datasets, compare against GP-UCB and random selection, and assess parameter mismatch as well as the effects of ϵ and N.Real-data parameters are learned using training data; synthetic experiments include matched and imperfect-knowledge settings for ϵ.Source: §5 · p. 6, §5.1 · p. 6

5.1 Synthetic Data

  • Across both kernels and all tested ϵ values, TV-GP-UCB outperforms R-GP-UCB; resetting produces oscillatory regret, while smooth forgetting yields steadier curves.The curves average 200 independent trials.Source: §5.1 · p. 7
  • TV-GP-UCB is robust to overestimating ϵ, but regret rises rapidly after sufficient underestimation; setting ϵ to zero gives the worst performance shown.This comparison uses the squared-exponential kernel with true ϵ = 0.01 and T = 200.Source: §5.1 · p. 7
  • For R-GP-UCB, very small N causes frequent resets, while increasing N leaves mean regret robust but steadily increases its standard deviation.GP-UCB is recovered when N = T.Source: §5.1 · p. 7

5.2 Real Data

  • For temperature data, algorithms learned from the first three days and ran on the final two; for I-880 traffic, the last 10 days tested performance using a randomly chosen 50-sensor domain (T = 84).The highway dataset contains 357 sensors, with 84 measurements per day.Source: §5.2 · p. 7
  • TV-GP-UCB outperforms GP-UCB on most highway test days and improves over R-GP-UCB on the temperature data, where GP-UCB eventually approaches random performance.On highway days with sudden speed changes, TV-GP-UCB also recovers more quickly than GP-UCB; R-GP-UCB was omitted from that short-horizon experiment.Source: §5.2 · pp. 7–8, Figure 3 · p. 8

6 Conclusion

The paper models time-varying rewards with a Markov-evolving Gaussian process and introduces R-GP-UCB and TV-GP-UCB. Its regret bounds characterize the dependence on the horizon and variation rate, while the authors identify open directions in improving those bounds and handling abrupt changes.

6 Conclusion

  • R-GP-UCB and TV-GP-UCB combine forgetting and remembering while exploiting spatial and temporal correlations under a Markov-evolving Gaussian-process model.The algorithms are introduced for bandit optimization with time-varying rewards.Source: §6 · p. 8
  • The regret bounds explicitly characterize dependence on horizon T and variation rate ϵ; an algorithm-independent bound shows linear dependence on T is unavoidable for fixed ϵ.The algorithms also performed well on real-world datasets that need not match the theoretical model.Source: §6 · p. 8
  • Future work includes improving the bounds' dependence on ϵ and adapting the model to sudden changes, potentially by combining it with changepoint-detection techniques.The current time-varying model is described as primarily suited to steady changes.Source: §6 · p. 8

Supplementary Material for “Time-Varying Gaussian Process Bandit Optimization”

The supplementary material derives posterior updates for the evolving GP, describes likelihood-based hyperparameter fitting, and supplies proof details for TV-GP-UCB's regret analysis.

A Posterior Updates

  • The time-varying posterior update follows by deriving the joint Gaussian distribution of past noisy outputs and the next function value, then conditioning to obtain its mean and variance.The covariance between function values at times t and t+j is scaled by (1 − ϵ)^(j/2) relative to the spatial kernel.Source: A Posterior Updates · p. 11

B Learning ϵ via Maximum-Likelihood

  • The variation parameter ϵ and other GP hyperparameters can be fitted by maximizing the marginal likelihood of the training observations.The covariance combines the spatial kernel with a time-decay matrix and observation noise; quasi-Newton methods are one suggested optimizer.Source: B Learning ϵ via Maximum-Likelihood · p. 11

C Analysis of TV-GP-UCB (Theorem 4.3)

  • The TV-GP-UCB analysis bounds time-varying mutual information by relating it to the time-invariant quantity, a key non-trivial step in the regret proof.The proof divides the horizon into shorter blocks within which the function varies only modestly.Source: C Analysis of TV-GP-UCB (Theorem 4.3) · p. 11, §C.1 · p. 12

C.1 Proof of (20)

  • The proof discretizes the decision domain and combines high-probability events to bound instantaneous and cumulative regret.A uniformly spaced grid can ensure that each point is close to its discretized representative.Source: §C.1 · pp. 12–13

C.2 Proof of (21)

The proof of the time-varying mutual-information bound reduces the problem to shorter blocks and controls the covariance difference from the time-invariant case.

C.2 Proof of (21)

  • The proof splits the horizon into blocks of length ˜N, within which the function varies only modestly, and compares each block's information to the time-invariant quantity.The argument uses the chain rule for mutual information and independent observation noise.Source: §C.2 · pp. 13–14
  • Within a block, the time-varying covariance is written as the time-invariant kernel matrix plus a perturbation induced by temporal decay.The entrywise difference is bounded using ϵ and the separation between observation indices.Source: §C.2 · p. 14
  • A Frobenius-norm bound and Mirsky's theorem control the eigenvalue changes, yielding a bound on time-varying mutual information in terms of the time-invariant quantity.The general horizon case adds one because the mutual-information bound increases with T.Source: §C.2 · pp. 14–15

D Analysis of R-GP-UCB (Theorem 4.2)

The R-GP-UCB analysis adapts the TV-GP-UCB proof to data windows since the previous reset, while accounting for the mismatch between the algorithm’s time-invariant posterior and the evolving reward function.

D Analysis of R-GP-UCB (Theorem 4.2)

  • R-GP-UCB uses only samples since the previous reset, but computes its algorithmic posterior using time-invariant quantities, creating a mismatch with the evolving model.The reset window has length at most N.Source: D Analysis of R-GP-UCB (Theorem 4.2) · p. 15
  • A union bound combines four high-probability events, while discretization controls the reward-function approximation error.The four events hold jointly with probability at least 1 − δ.Source: D Analysis of R-GP-UCB (Theorem 4.2) · p. 15
  • The proof bounds errors between the true and mismatched posterior updates, conditioning only on observations since the last reset.It handles terms involving the kernel vector and covariance matrices, including bounds on their spectral-norm differences.Source: D Analysis of R-GP-UCB (Theorem 4.2) · pp. 15, 17

E Applications to Specific Kernels (Corollary 4.1)

The kernel-specific regret bounds depend on the variation rate ε and kernel, with different scalings for TV-GP-UCB and reset-window R-GP-UCB.

E Applications to Specific Kernels (Corollary 4.1)

F Lower Bound (Theorem 4.1)

The lower-bound analysis considers a genie-aided strategy that knows the previous reward function. It establishes that regret can persist even with full information because function maxima may shift as the reward evolves.

F Lower Bound (Theorem 4.1)

  • Even when the entire previous function is known, the regret-minimizing strategy is to choose its maximizer, since the next function’s conditional mean is largest there.The next value at each point is distributed as N(√(1 − ε)f_(t−1)(x), ε).Source: F Lower Bound (Theorem 4.1) · p. 18
  • A positive-probability event with an interior maximum and bounded derivatives supports the local perturbation argument for the lower bound.For suitable η and L, the intersection of the four specified events has strictly positive probability.Source: F Lower Bound (Theorem 4.1) · p. 18
  • The proof compares the previous function’s maximizer with a nearby point in the direction of the innovation gradient to lower-bound instantaneous regret.A second-order Taylor expansion and Hessian bounds control the comparison.Source: F Lower Bound (Theorem 4.1) · p. 18

G Further results for traffic speed data

Figure 4 reports numerical performance of upper confidence bound algorithms on the traffic-speed dataset, covering all testing days in the Section 5.2 experiment.

G Further results for traffic speed data

  • The figure outlines the complete results across all testing days for the experiment described in Section 5.2.Source: G Further results for traffic speed data · p. 19
  • The experiment uses the listed sensors, whose identifiers are given in the text accompanying Figure 4.The passage lists the sensor IDs but does not state how they are encoded in the figure.Source: G Further results for traffic speed data · p. 19
  • Figure 4 compares the numerical performance of upper confidence bound algorithms on the traffic-speed dataset.The caption identifies the dataset and algorithm family, but the supplied text gives no result values or winner.Source: Figure 4 · p. 19
Loading 1601.06650v1…