How to gamble with non-stationary $\mathcal{X}$-armed bandits and have no regrets

Formally, we model the noise with a normal distribution and impose the zero-mean Gaussian Process prior with covariance function k (·, ·) on the regression function f GP (0,ρk ( ·, ·)), y j N (f (X j),σ 2) for j 1..n, where n is the number of covariate-response pairs under consideration and ρ is a regularization parameter. For a given covariate X the predictive distribution is also Gaussian with mean µ k K 1 y and variance σ 2 k (X,X) null k K 1,k null, where y [ y i] i 1..n, K [ ρk (X i,X j) σ 2 δ ij] i,j 1..nand k [ k (X,X i)] i 1..n. 2.2 Change-point detection procedure Our approach requires a change-point detection procedure as its crucial building block. To that end we suggest a novel approach, namely, Algorithm 1. Given a sequence of covariate and response pairs {( X t,y t)} 2n t 1, we train a Gaussian Process Regression twice - using only the first and only the second half of the 3 given data respectively. This way we obtain two predictive functions µ 1 and µ 2. Next we make predictions for all the provided covariates and calculate the discrepancy between these predictions ˆ 2: 1 n 2n null i 1( µ 1( X t) µ 2( X t)) 2 . Finally, we compare the discrepancy against some predetermined threshold θ n. Intuitively, if the covariate-response pairs were generated with the same functional relationship, ˆ 2 should be small, while violation of this assumption should lead to larger values. Algorithm 1: CPD Data: Covariate-response pairs {(X t,y t)} 2n t 1, threshold θ n, regularization parameter ρ CP Result: True if a break is detected, False otherwise 1 µ 1(·) train GPR on {( X t,y t) } n t 1w.