Audrey Durand
email: audrey.durand.2@ulaval.ca

Odalric-Ambrym Maillard
email: odalric.maillard@inria.fr

Joelle Pineau
email: jpineau@cs.mcgill.ca

Maillard

Kevin Murphy

Bernhard Schölkopf

Streaming kernel regression with provably adaptive mean, variance, and regularization

Keywords: kernel, regression, online learning, adaptive tuning, bandits

Streaming kernel regression with provably adaptive mean, variance, and regularization

Introduction

Many applications require solving an online optimization problem for an unknown, noisy, function defined over a possibly large domain space. Kernel regression methods can learn such possibly non-linear functions by sharing information gathered across observations. These techniques are being used in many fields where they serve a variety of applications like hyperparameters optimization [START_REF] Snoek | Practical bayesian optimization of machine learning algorithms[END_REF], active preference learning [START_REF] Brochu | Active preference learning with discrete choice data[END_REF], and reinforcement learning [START_REF] Marchant | Bayesian optimisation for informative continuous path planning[END_REF][START_REF] Wilson | Using trajectory data to improve bayesian optimization for reinforcement learning[END_REF]. The idea is generally to rely on kernel regression to estimate a function that can be used for decision making and selecting the next observation point. Algorithmically speaking, standard kernel regression involves a regularization parameter that accounts for both the complexity of the unknown target function, and the variance of the noise. While most theoretical approaches rely on a fixed regularization parameter, in practice, people have often used heuristics in order to tune this parameter adaptively with time.

This however comes at the price of loosing theoretical guarantees. Indeed, in order for theoretical guarantees (based on concentration inequalities) to hold, existing approaches [START_REF] Srinivas | Gaussian process optimization in the bandit setting: No regret and experimental design[END_REF][START_REF] Valko | Finite-time analysis of kernelised contextual bandits[END_REF] require the regularization parameter in the kernel regression to be a fixed quantity. Further, they assume a prior and tight knowledge of the variance of the noise, which is unrealistic in practice. The reason for this cumbersome assumption is to adjust the regularization parameter in the kernel regression based on this deterministic quantity, as such a choice of regularization conveys a natural Bayesian interpretation [START_REF] Rasmussen | Gaussian processes for machine learning[END_REF]. Following this intuition, given an empirical estimate of the function noise based on gathered observations, one should be able to tune the regularization automatically. This is however non-trivial, first due to the streaming nature of the data, that allows the noise to be a measurable function of the past observations, second because concentration bounds on the empirical variance are currently unknown in such a general kernel setup, and finally because all existing theoretical bounds require the regularization parameter to be a deterministic constant, while we require here a parameterization that explicitly depends on past observations. The goal of this work is to provide the rigorous tools for performing an online tuning of the kernel regularization while preserving theoretical guarantees and confidence intervals in the context of streaming kernel regression with unknown noise. We thus hope to provide a sound method for adaptive tuning that is both interesting from a practical perspective and retains theoretical guarantees.

We gently start our contributions by Theorem 2.1 that generalizes existing concentration results (such as in [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF]; [START_REF] Wang | Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters[END_REF]), and is explicitly stated for a regularization parameter that may differ from the noise. This result paves the way to an even more general result (Theorem 2.2) that holds when the regularization is tuned online at each step. Afterwards, we introduce a streaming variance estimator (Theorem 3.1) that yields empirical upper-and lower-bounds on the function noise. Plugging-in the resulting estimates leads to empirical Bernstein-like concentration results (Corollary 3.1) for the kernel regression, where we use the variance estimates in order to tune the regularization parameter. Section 4 presents an application to kernelized bandits, where regret bounds for Kernel UCB and Kernel Thompson Sampling procedures are derived. Section 5 discusses our results and compares them against other approaches. Finally, Section 6 shows the potential of all the previously introduced results while comparing them to existing alternatives through different numerical experiments. We postpone most of the proofs to the appendix.

Kernel streaming regression with a predictable noise process

Let us consider a sequential regression problem. At each time step t ∈ N, a learner picks a point x t ∈ X and gets the observation

y t = f (x t ) + ξ t ,
where f is an unknown function assumed to belong to some function space F, and ξ t is a random noise. We assume the process generating the observations is predictable in the sense that there is a filtration H = (H t ) t∈N such that x t is H t-1 -measurable and y t is H t -measurable. Such an example is given by H t = σ(x 1 , . . . , x t+1 , y 1 , . . . , y t ). In the sub-Gaussian streaming predictable model, we assume that for some non-negative constant σ 2 the following holds ∀t ∈ N, ∀γ ∈ R, ln E exp(γξ t ) H t-1 γ 2 σ 2 2 .

Let k : X × X → R be a kernel function (that is continuous, symmetric positive definite) on a compact set X equipped with a positive finite Borel measure, and denote K the corresponding RKHS. We first provide a result bounding the prediction error of a standard regularized kernel estimate, where the regularization is given by a fixed parameter λ > 0.

Theorem 2.1 (Streaming Kernel Least-Squares) Assume we are in the sub-Gaussian streaming predictable model. For a parameter λ ∈ R, let us define the posterior mean and variances after observing

Y t = (y 1 , . . . , y t ) ∈ R t×1 as f λ,t (x) = k t (x) (K t + λI t ) -1 Y t s 2 λ,t (x) = σ 2 λ k λ,t (x, x) with k λ,t (x, x) = k(x, x) -k t (x) (K t + λI t ) -1 k t (x) .
where k t (x) = (k(x, x t )) t t is a t × 1 (column) vector and K t = (k(x s , x s )) s,s t . Then ∀δ ∈ [0, 1], with probability higher than 1-δ, it holds simultaneously over all x ∈ X and t 0,

|f (x)-f λ,t (x)| k λ,t (x, x) λ √ λ f K +σ 2 ln(1/δ) + 2γ t (λ) ,
where the quantity

γ t (λ) = 1 2 t t =1 ln 1+ 1 λ k λ,t -1 (x t , x t )
is the information gain.

Remark 2.1 This result should be considered as an extension of (Abbasi-Yadkori et al., 2011, Theorem 2) from finite-dimensional to possibly infinite dimensional function space.

It is a non-trivial result as the Laplace method must be amended in order to be applied.

Remark 2.2 This result holds uniformly over all x ∈ X and most importantly over all t 0, thanks to a random stopping time construction (related to the occurrence of bad events) and a self-normalized inequality handling this stopping time. This is in contrast with results such as [START_REF] Wang | Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters[END_REF], that are only stated separately for each t.

Remark 2.3 The quantity γ t (λ) directly generalizes the classical notion of information gain [START_REF] Cover | Elements of information theory[END_REF], that is recovered for the choice of regularization λ = σ 2 .

The case when

λ = λ def = σ 2 / f 2
K is of special interest, since we get on the one hand

f t (x) = k t (x) (K t + λ I t ) -1 Y t s 2 t (x) = f 2 K k t (x, x) with k t (x, x) = k(x, x) -k t (x) (K t + λ I t ) -1 k t (x)
and on the other hand f K k t (x, x) 1/2 1 + 2 ln(1/δ) + 2γ t (λ ) . In practice however, neither f 2 K nor σ 2 may be known exactly. In this paper, we assume that an upper bound C is given on f K . Then, we want to build an estimate of σ 2 at each time t in order to tune λ. Using a sequence of regularization parameters (λ t ) t 1 that is tuned adaptively based on the past observations requires to modify the previous theorem (it is only valid for a deterministic λ) into the following more general statement:

Theorem 2.2 (Streaming Kernel Least-Squares with online tuning) Under the same assumption as Theorem 2.1, let λ = (λ t ) t 1 be a predictable positive sequence of parameters, that is λ t is H t-1 -measurable for each t. Assume that for each t, λ t λ holds for a positive constant λ . Let us define the modified posterior mean and variances after observing

Y t ∈ R t as f λ,t (x) = k t (x) (K t + λ t+1 I t ) -1 Y t s 2 λ,t (x) = σ 2 λ t+1 k λ t+1 ,t (x, x) with k λ,t (x, x) = k(x, x)-k t (x) (K t + λI t ) -1 k t (x) ,
where k t (x) = (k(x, x t )) t t , and K t = (K(x s , x s )) s,s t . Then for all δ ∈ [0, 1], with probability higher than 1δ, it holds simultaneously over all x ∈ X and t 0

|f (x)-f λ,t (x)| k λ t+1 ,t (x, x) λ t+1 λ t+1 f K +σ 2 ln(1/δ)+2γ t (λ ) .
The proof is presented in Appendix A.

The regularization parameter λ t+1 is therefore used in conjunction with previous data up to time t to provide the posterior regression model (mean and variance) that is used in return to acquire the next observation y t+1 on point x t+1 .

Remark 2.4 Since λ t is allowed to be H t-1 -measurable, this gives theoretical guarantees for virtually any adaptive tuning procedure of the regularization parameter.

Remark 2.5

The assumption that λ t λ will be naturally satisfied for the choice of regularization we consider.

Variance estimation

We now focus on the estimation of the variance parameter of the noise in the case when it is unknown, or loosely known. Theorem 2.2 suggests to define the sequence (λ t ) t 1 by

λ t = σ 2 +,t-1 /C 2 with σ +,t = min{σ +,t , σ +,t-1 } and σ +,0 = σ + , (1)
where σ + σ is an initial loose upper bound on σ and σ+,t is an upper-bound estimate on σ built from all observations gathered up to time t (inclusively). This ensures that λ t is H t-1 measurable for all t and satisfies λ t λ with high probability, where λ = σ 2 /C 2 . The crux is now to define the upper-bound estimate σ +,t on σ. In order to get a variance estimate, one obviously requires more than the sub-Gaussian assumption, since the term σ 2 has no reason to be tight (the inequality remains valid when σ 2 is replaced with any larger value). In order to convey the minimality of σ 2 , we assume that the noise sequence is both σ-sub-Gaussian and second-order1 σ-sub-Gaussian, in the sense that

∀t, ∀γ < 1 2σ 2 ln E exp(γξ 2 t ) H t-1 - 1 2 ln 1 -2γσ 2 .
Remark 3.1 To avoid any technicality, one may assume that ξ t |H t-1 is exactly N (0, σ 2 ), in which case it is trivially second-order σ-sub-Gaussian.

Now let σ 2 λ,T = 1 T T t=1 (y t -f λ,T (x t )
) 2 denote the (slightly biased) variance estimate for a regularization parameter λ.

Theorem 3.1 (Streaming Kernel variance estimate) Assume we are in the predictable second-order σ-sub-Gaussian streaming regression model, with a predictable positive sequence λ such that λ t λ holds for all t. Let us introduce the following quantities

C t (δ) = ln(e/δ) 1 + ln(π 2 ln(t)/6)/ ln(1/δ) , D λ,t (δ) = 2 ln(1/δ) + 2γ t (λ) and finally α = max 1 -Ct(δ ) t - Ct(δ )+2D λ ,t (δ ) t , 0 .
Then, let us introduce the following variance bounds, defined differently depending on whether a deterministic upper bound σ + σ is known (case 1) or not (case 2).

σ +,t (λ, λ ) =          σ λ,t + σ + Ct(δ ) t + Ct(δ )+2D λ ,t (δ ) t + 2σ + f K √ λD λ ,t (δ ) t (case 1) 1 α 2 σ λ,t α + f K √ λD λ ,t (δ ) 2t + f K √ λD λ ,t (δ ) 2t 2 (case 2) σ -,t (λ) =            σ λ,t -σ + 2Ct(δ ) t -f K λ t 1 - 1 max t t (1+ 1 λ k λ,t -1 (x t ,x t ))
(case 1)

σ λ,t -f K λ t 1 - 1 max t t (1+ 1 λ k λ,t -1 (x t ,x t )) 1 + 2Ct(δ ) t -1
(case 2).

Then with probability higher than 1 -3δ , it holds simultaneously for all t 0 σ -,t (λ t ) σ σ +,t (λ t , λ ) .

The proof is presented in Appendix B.

Remark 3.2 The case when absolutely no bound is known on the noise σ 2 is challenging in practice. In this case, it is intuitive that one should not be able to recover the noise with too few samples. The bound stated in Theorem 3.1 (see Appendix B) supports this intuition, as when the number of observations is too small, then α = 0 and the corresponding bound becomes trivial (σ ∞).

Remark 3.3 In the variance bounds of Theorem B.1 the term f K appears systematically with the factor √ λ. This suggests we need to choose λ proportional to 1/ f 2 K , which gives further justification to the target λ = σ 2 /C 2 , where C is a known upper bound on f . Remark 3.4 In practice, we advice to choose the best of case 1 and case 2 bounds when σ + σ is known.

In order to estimate the upper bound σ +,t (λ, λ ), one needs at least a lower-bound on λ . Let us define

σ -,t = max{σ -,t , σ -,t-1 } with σ -,0 = σ -, (2)
where 0 σ - σ is a initial lower-bound on σ and σ-,t is a lower-bound estimate on σ built from all observations gathered up to time t (inclusively). Then, one way to proceed is, at each time step t 1, to build an estimate σ-,t = σ -,t (λ), which in return can be used to compute the lower quantity λ -λ , and obtain the estimate σ+,t = σ +,t (λ, λ -) σ +,t (λ, λ ). Then, we compute the predictable sequence λ as described by equation 1. Further replacing the variance σ with its estimate σ +,t using a union bound in the result of Theorem 2.2, we derive confidence bounds that are fully computable in the context where the regularization parameter is adaptively tuned and the function noise is unknown. This is summarized in the following empirical Bernstein-style inequality:

Corollary 3.1 (Kernel empirical-Bernstein inequality) Assume that C f K . Let us define the following noise lower-bound for each t 1 σ -,t = max{σ -,t (λ t-1 ), σ -,t-1 } and define λ -= σ 2 -,t /C 2 as the corresponding lower bound on λ . Then, let us define the following noise upper bound for each t 1 σ +,t = min{σ +,t (λ t-1 , λ -), σ +,t-1 } .

Define the regularization parameterizing the regression model used for acquiring observation at time t to be λ t = σ 2 +,t /C 2 , according to Equation 1. Then with probability higher than 1 -4δ, the following is valid simultaneously for all x ∈ X and t 0,

f (x)-f λt,t (x) k λt,t (x, x) λ t B λt,t (δ) where
B λt,t (δ) = λ t C +σ +,t 2 ln(1/δ) + 2γ t (λ -) . (3)
Remark 3.5 This result is especially interesting since it provides a fully empirical confidence envelope function around f . When an initial bound on the noise σ + is known and considered to be tight, one may simply choose the constant deterministic sequence λ = (λ, . . . , λ), in which case the same result holds for λ -= λ and σ +,t = σ + .

We observe from Theorem 3.1 that the tightness of the noise estimates depends on the λ parameter that is used for computing σ-,t and σ+,t . Since σ 2 /C 2 λ t σ 2 + /C 2 holds with high probability by construction, using such an adaptive λ t should yield tighter bounds than using a fixed σ 2 + /C 2 . This is supported by the numerical experiments of Section 6.2.

Application to kernelized bandits

Here is a direct application of our results in the framework of stochastic multi-armed bandits with structured arms embedded in an RKHS [START_REF] Srinivas | Gaussian process optimization in the bandit setting: No regret and experimental design[END_REF][START_REF] Valko | Finite-time analysis of kernelised contextual bandits[END_REF]. At each time step t 1, a bandit algorithm recommends a point x t to sample and observes a noisy outcome y t = f (x t ) + ξ t , where ξ t ∼ N (0, σ 2 ). Let = argmax x∈X f (x) be the optimal arm. The goal of an algorithm is to pick a sequence of points (x t ) t T that minimizes the cumulative regret

R T = T t=1 f ( ) -f (x t ). ( 4
)
In this context, one needs to build tight confidence sets on the mean of each arm, and this will be given by Corollary 3.1. We illustrate our technique on two main bandit strategies: Upper Confidence Bound (UCB) [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] and Thompson Sampling (TS) [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF]; both are adapted here to the kernel setting with unknown variance.

Definition 4.1 (Information gain with unknown variance) We define the information gain at time t for a regularization parameter λ to be

γ t (λ) = 1 2 t t =1 ln 1 + 1 λ k λ,t -1 (x t , x t ) .
This definition directly extends the usual definition of information gain, that can be recovered by choosing λ = σ 2 . The following extension of Lemma 7 in Wang and de Freitas (2014) (see also [START_REF] Srinivas | Information-theoretic regret bounds for Gaussian process optimization in the bandit setting[END_REF]) to the case when the variance is estimated plays an important role in the regret analysis of both algorithms.

Lemma 4.1 (From sum of variances to information gain) Let us assume that the kernel is bounded by 1 in the sense that sup x∈X k(x, x) 1. Let λ be any sequence such that ∀λ ∈ λ, λ σ 2 /C 2 . For instance, this is satisfied with high probability when using Equation 1. Then, it holds

T t=1 s 2 λ,t-1 (x t ) = σ 2 T t=1 1 λ t k λt,t-1 (x t , x t ) 2C 2 ln(1 + C 2 /σ 2 ) γ T (σ 2 /C 2 ) .
In the sequel, it is useful to bound the confidence bound term B λt,t (δ) from Equation 3.

Lemma 4.2 (Deterministic bound on the confidence bound) Assume that we are given a constant 0 < σ -< σ, so that σ t,- σ -holds for all t. Then for all t T , the confidence bound term is upper-bounded by the following deterministic quantity

B λt,t (δ) σ + 1 + 2 ln(1/δ) + 2γ T (σ 2 -/C 2 ) . Further, we have γ t (σ 2 t,-/C 2 ) = γ t (σ 2 -/C 2 ) + O(1/ √ t).
Remark 4.1 The term σ + can be replaced with a more refined term σ + O(1/ √ t) thanks to the confidence bounds on the variance estimates.

Kernel UCB with unknown variance The upper bound on the error can be used directly in order to build a UCB-style algorithm. Formally, the vanilla UCB algorithm [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] corresponding to our setting picks at time t the arm

x t ∈ argmax x∈X f + λt,t-1 (x) where f + λ,t (x) = f λ,t (x) + k λ,t (x, x) λ B λ,t (δ) . (5)
Following the regret proof strategy of [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF], with some minor modifications, yields the following guarantee on the regret of this strategy:

Theorem 4.1 (Kernel UCB with unknown noise and adaptive regularization) With probability higher than 1-δ, the regret of Kernel UCB with adaptive regularization and variance estimation satisfies for all T 0 (recall that B λ t+1 ,t (δ) is defined in Equation 3):

R T 2 T t=1 k λt,t-1 (x t , x t ) λ t B λt,t-1 (δ/4) .
In particular, we have

R T 2 σ + σ 1 + 2 ln(4/δ) + 2γ T (σ 2 -/C 2 ) C T 2γ T (σ 2 /C 2 ) ln(1 + C 2 /σ 2 ) .
Remark 4.2 This result that holds simultaneously over all time horizon T extends that of [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] first to kernel regression and then to the case when the variance of the noise is unknown. This should also be compared to [START_REF] Valko | Finite-time analysis of kernelised contextual bandits[END_REF] that assumes bounded observations, which implies a bounded noise (with known bound) and a bounded f , and Srinivas et al. ( 2010) that provides looser bounds.

Kernel TS with unknown variance Another application of our confidence bounds is in the analysis of Thompson sampling in the kernel scenario. Before presenting the result, let us say a few words about the design of TS algorithm in a kernel setting. Such an algorithm requires sampling from a posterior distribution over the arms. It is natural to consider a Gaussian posterior with posterior means and variances given by the kernel estimates. However, it has been noted in a series of papers [START_REF] Agrawal | Thompson sampling for contextual bandits with linear payoffs[END_REF][START_REF] Abeille | Linear Thompson sampling revisited[END_REF] that, in order to obtain provable regret minimization guarantees, the posterior variance should be inflated (although in practice, the vanilla version without inflation may work better). Following these lines of research, and owing to our novel confidence bounds, we derive the following TS algorithm using a posterior variance inflation factor v 2 t .

Remark 4.3 The algorithm does not know the variance σ 2 of the noise, but uses an upper estimate σ 2 +,t-1 .

Remark 4.4 We assume that the set of arms X is discrete. This is merely for practical reasons since otherwise updating the estimate of f in a RKHS requires memory and computational times that are unbounded with t. This also simplifies the analysis.

Algorithm 1 Kernel TS with adaptive variance estimation and regularization tuning Parameters: regularization sequence λ, variance inflation factor v 2 t for each t. 1: for all t 1 do 2:

compute the posterior mean

f t-1 = (f λt,t-1 (x)) x∈X 3: compute the posterior covariance Σ t-1 = σ 2 +,t-1 λt k λt,t-1 (x, x ) x,x ∈X 4: sample ft = N ( f t-1 , v 2 t Σ t-1 )
5:

play x t = argmax x∈X ft (x) 6:
observe outcome y t = f (x t ) + ξ t 7: end for

The following regret bound can then be obtained after some careful but easy adaptation of [START_REF] Agrawal | Thompson sampling for contextual bandits with linear payoffs[END_REF]. We provide the proof of this result in Appendix C, which can be of independent interest, being a more rigorous and somewhat simpler rewriting of the original proof technique from [START_REF] Agrawal | Thompson sampling for contextual bandits with linear payoffs[END_REF].

Theorem 4.2 (Regularized Kernel TS with variance estimate) Assume that the max- imal instantaneous pseudo-regret R = max x∈X f ( ) -f (x) is finite. Then, the regret of Kernel TS (Algorithm 1) with v t = B λ t ,t-1 (δ/4) σ +,t-1 after T episodes is O(C T ln(T |X|)γ T (σ 2 /C 2 ))
with probability 1 -3δ. More precisely, with probability 1 -3δ, the regret is bounded for all T 0:

R T C 1,T T t=1 k λt,t-1 (x t , x t ) λ t B λt,t-1 (δ/4) + C 2 R T ln(1/δ) + 4πeRδ ,
where C 1,T = (4

√ πe + 1) 1 + 2 ln T (T +1)|X| √ πδ and C 2 = 8πe(1 + δ √ 4πe) 2 .
Further, we have

R T C 1,T σ + σ 1 + 2 ln(4/δ) + 2γ T (σ 2 -/C 2 ) C T 2γ T (σ 2 /C 2 ) ln(1 + C 2 /σ 2 ) +C 2 R T ln(1/δ) + 4πeRδ .
Remark 4.5 As our confidence intervals do not require a bounded noise, likewise we can control the regret with high probability without requiring bounded observations, contrary to earlier works such as [START_REF] Valko | Finite-time analysis of kernelised contextual bandits[END_REF].

Discussion and related works

Concentration results Theorem 2.1 extends the self-normalized bounds of [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] from the setting of linear function spaces to that of an RKHS with sub-Gaussian noise. Based on a nontrivial adaptation of the Laplace method, it yields self-normalized inequalities in a setting of possibly infinite dimension. It generalizes the following result of [START_REF] Wang | Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters[END_REF] to kernel regression with λ = σ 2 , which was already a generalization of a previous result by [START_REF] Srinivas | Gaussian process optimization in the bandit setting: No regret and experimental design[END_REF] for bounded noise. It is also more general than the concentration result from [START_REF] Valko | Finite-time analysis of kernelised contextual bandits[END_REF], for kernel regression with λ = σ 2 , which holds under the assumption of bounded observations. Lemma 5.1 (Proposition 1 from Wang and de Freitas ( 2014)) Let f denote a function in the RKHS K induced by kernel k and let us define the posterior mean and variances with λ = σ 2 , for (arbitrary) data (x t ) t t . Assuming σ-sub-Gaussian noise variables, then for all δ ∈ (0, 1) we have that

P ∃x ∈ X : |f λ,t (x) -f (x)| λ,t+1 (δ )k 1/2 λ,t (x, x) δ , where 2 λ,t (δ ) = f 2 K + 8γ t-1 (λ) ln 2 δ + 2 ln 4 δ f K + 2γ t-1 (λ) + 2σ ln 2 δ and γ t (λ) = 1 2 t t =1 ln 1 + 1 λ k λ,t -1 (x t , x t )
is the information gain.

Remark 5.1 This results provides a bound that is valid for each t, with probability higher 1δ. In contrast, results from Abbasi-Yadkori et al. ( 2011), as well as Theorem 2.1 hold with probability higher 1δ, uniformly for all t, and are thus much stronger in this sense.

Theorem 2.2 extends Theorem 2.1 to the case when the regularization is tuned online based on gathered observations. To the best of our knowledge, no such result exists in the literature at the time of writing this paper. Moreover, Theorem 3.1 provides variance estimates with confidence bounds scaling with 1/ √ t, in the spirit of the results from [START_REF] Maurer | Empirical Bernstein bounds and sample variance penalization[END_REF], that were provided in the i.i.d. case. Thus, Theorem 3.1 also appears to be new. Finally, Corollary 3.1 further specifies Theorem 2.2 to the situation where the regularization is tuned according to Theorem 3.1, yielding a fully adaptive regularization procedure with explicit confidence bounds.

Bandits optimization When applied to the setting of multi-armed bandits, Theorems 4.2 and 4.1 respectively extend linear TS [START_REF] Agrawal | Thompson sampling for contextual bandits with linear payoffs[END_REF][START_REF] Abeille | Linear Thompson sampling revisited[END_REF] and UCB [START_REF] Li | A contextual-bandit approach to personalized news article recommendation[END_REF][START_REF] Chu | Contextual bandits with linear payoff functions[END_REF] to the RKHS setting. Similar extensions have been provided in the literature: GP-UCB [START_REF] Srinivas | Gaussian process optimization in the bandit setting: No regret and experimental design[END_REF] generalizes UCB from the linear to the RKHS setting through the use of Gaussian processes; this corresponds to the case when λ = σ 2 . The bounds they provide in the case when the target function belongs to an RKHS is however quite loose. KernelUCB [START_REF] Valko | Finite-time analysis of kernelised contextual bandits[END_REF]) also generalizes UCB from the linear to the RKHS setting through the use of kernel regression. However the analysis of this algorithm was out of reach of their proof technique (that requires independence between arms) and they analyze instead the arguably less appealing variant called SupKernelUCB. Also, the analysis of both GP-UCB and SupKernelUCB in the agnostic setting are respectively limited to bounded noise and bounded observations.

Illustrative numerical experiments

In this section, we illustrate the results introduced in the previous Sections 2 and 3 on a few examples. The first one is the concentration result on the mean from Theorem 2.1, the second one is the variance estimate from Theorem 3.1, and the last one combines the formers by using the noise estimate to tune λ t+1 = σ 2 t /C 2 in Theorem 2.2, which corresponds to Corollary 3.1. We finally show the performance of kernelized bandits techniques using the provided variance estimates and adaptative regularization schemes.

We conduct the experiments using the function f shown by Figure 1, which has norm

f K = θ 2 = 2.06 in the RKHS induced by a Gaussian kernel k(x, x ) = e - (x-x ) 2 2ρ 2
with length scale ρ = 0.3. We consider the space X = [0, 1] and that the standard deviation of the noise is σ = 0.1. All further experiments use the upper-bound C = 5 on f K and the lower-bound σ -= 0.01 on σ.

Kernel concentration bound

The following experiments compare the concentration result given by Theorem 2.1 with the kernel concentration bounds from Wang and de Freitas (2014) reported by Lemma 5.1. The true noise σ = 0.1 is assumed to be known and all observations are uniformly sampled from X . In both cases, we use a fixed confidence level δ = 0.1. Figure 2 shows that for λ = σ 2 , the result given by Theorem 2.1 recovers the confidence envelope of [START_REF] Wang | Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters[END_REF]. Note however that the confidence bound that we plot for Theorem 2.1 are valid uniformly over all time steps, while the one derived from Wang and de Freitas ( 2014) is only valid separately for each time. Further, Theorem 2.1 generalizes the latter result to the case where λ = σ 2 . For illustration, Figure 3 illustrates the confidence envelopes in the special case where λ = σ 2 /C 2 , which also shows the potential benefit of such a tuning.

Empirical variance estimate

We now illustrate the convergence rate of the noise estimates σ -,t = max{σ -,t (λ), σ -,t-1 } and σ +,t = min{σ +,t (λ, λ -), σ +,t-1 } computed using Theorem 3.1, where λ -= σ 2 -,t /C 2 and δ = 0.1. All observations are uniformly sampled from X . Section 3 suggests that λ = σ 2 +,t-1 /C 2 should provide tighter bounds than a fixed λ = σ 2 + /C 2 . Figure 4 shows that this is indeed the case especially for large values of t. We also see that the adaptive update of λ converges to the same value, whatever the initial bound σ + . This is especially interesting when σ + is a loose initial upper bound on σ.

In practice, the bound of Theorem 3.1 not using the knowledge of σ + may be useful even when σ + is known. This is illustrated by Figure 5a estimate σ +,t (λ, λ -) for λ = σ 2 +,t-1 /C 2 in both cases. In practice, we suggest to use the minimum of the bound using the knowledge of σ + (case 1) and of the agnostic one (case 2) to set σ +,t (λ, λ -) and the maximum for σ -,t (λ). Figure 5b shows the resulting noise estimate envelopes for different σ + values (recall that σ = 0.1).

Adaptive regularization

We now combine the previous experiments and use the estimated noise in order to tune the regularization. Recall that we consider σ -,0 = σ -, σ +,0 = σ + , and λ 0 = σ 2 + /C 2 . On each time t 1, we estimate the noise lower-bound σ -,t = max{σ -,t (λ t-1 ), σ -,t-1 } using Theorem 3.1 and set λ -= σ 2 -,t /C 2 . We then compute the upper-bound noise estimate σ +,t = min{σ +,t (λ t-1 , λ -), σ +,t-1 } using Theorem 3.1 and set λ t = σ 2 +,t /C 2 . We are now ready to compute the confidence interval given by Corollary 3.1. Note that δ = 0.1 is used everywhere and all observations are uniformely sampled from X . Figure 6 illustrates the resulting confidence envelope of this fully empirical model for noise upper-bound σ + = 1 (recall that the noise satisfies σ = 0.1) plotted against the confidence envelope obtained with Theorem 2.1 with fixed λ = σ 2 + /C 2 . We observe the improvement of the confidence intervals with the number of observations. Recall that this setting is especially challenging since the variance is unknown, the regularization parameter is tuned online, and the confidence bounds are valid uniformly over all time steps.

f Fixed λ = σ 2 + /C 2 Adaptive λ t = σ 2 +,t-1 /C 2

Kernelized bandits optimization

In this section, we now evaluate the potential of kernelized bandits algorithms with variance estimate. We consider X as the linearly discretized space X = [0, 1] into 100 arms. Recall that the goal is to minimize the cumulative regret (Equation 4) and that we are optimizing the function shown by Figure 1 with σ = 0.1. We evaluate Kernel UCB (Equation 5) and Kernel TS (Algorithm 1 with v t = B λt,t-1 (δ)/σ +,t-1 ) with three different configurations: a) the oracle, that is with fixed λ t = σ 2 /C 2 , assuming knowledge of σ; b) the fixed λ t = σ 2 + /C 2 , that is the best one can do without prior knowledge of σ 2 ; c) the adaptative regularization tuned with Corollary 3.1. All configurations use C = 5. Kernel UCB uses δ = 0.1/4 and Kernel TS uses δ = 0.1/12 such that their regret bounds respectively hold with probability 0.9. Recall that observations are now sampled from X using the bandits algorithms (they are not i.i.d.). Configurations b) and c) use σ + = 1, while the oracle a) uses σ + = σ. Figure 7 shows the cumulative regret averaged over 100 repetitions. Note that the oracle corresponds to the best performance that could be expected by Kernel UCB and Kernel TS given knowledge of the noise. The plots confirm that adaptively tuning the regularization using the variance estimates can lead to a major improvement compared to using a fixed, non-accurate guess: after an initial burn-in phase, the regret of the adaptively tuned algorithm increases at the same rate as that of the oracle algorithm knowing the noise exactly. The fact that Kernel UCB outperforms Kernel TS much implies that inflating the variance in Kernel TS, as suggested per the theory presented previously, may not be optimal in practice. Further attention should be given to this question.

In order to evaluate the benefit of the concentration bound provided by Theorem 2.1, we compare the Kernel TS (Algorithm 1) oracle using v t = B λ,t-1 /σ and λ = σ 2 /C 2 , where B λ,t-1 is given by Theorem 2.1, against v t = t (δ) where t (δ) is given by Lemma 5.1 [START_REF] Wang | Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters[END_REF] with δ = 0.1. Figure 8 shows that the concentration bound given by Theorem 2.1 improves the performance of Kernel TS compared with existing concentration results [START_REF] Wang | Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters[END_REF]. It highlights the relevance of expliciting the regularization parameter, which allows us to take advantage of regularization rates that may be better adapted.

Conclusion

This work addresses two problems: the online tuning of the regularization parameter in streaming kernel regression and the online estimation of the noise variance. To this extent, we introduce novel concentration bounds on the posterior mean estimate in streaming kernel regression with fixed and explicit regularization (Theorem 2.1), which we then extend to the setting where the regularization parameter is tuned (Theorem 2.2). We further introduce upper-and lower-bound estimates of the noise variance (Theorem 3.1). Putting these tools together, we show how the estimate of the noise variance can be used to tune the kernel regularization in an online fashion (Corollary 3.1) while retaining theoretical guarantees. We also show how to use the proposed results in order to derive kernelized variations of the most common bandits algorithms UCB and Thompson sampling, for which regret bounds are also provided (Theorems 4.1 and 4.2).

All the proposed results and tools are illustrated through numerical experiments. The obtained results show the relevance of the introduced kernel regression concentration intervals for explicit regularization, which hold when the regularization does not correspond to the noise variance. The potential of the proposed regularization tuning procedure is illustrated through the application to kernelized bandits, where the benefits of adaptive regularization is undeniable when the noise variance is unknown (this is usually the case in practice). Finally, one must note that a major strength of the tools proposed in this work is to allow for an adaptively tuned regularization parameter while preserving theoretical guarantees, which is not the case when regularization is tuned for example by cross-validation.

Future work includes a natural extension of these techniques to obtain an empirical estimate of the kernel length scales. This information is often assumed to be known, while in practice it is often not available. Although some preliminary work has been done in that direction [START_REF] Wang | Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters[END_REF], designing theoretically motivated algorithms addressing these concerns would help to fill an important gap between theory and practice. On a different matter, the current work gives the basis for performing Thompson sampling in RKHS, and could be extended to the contextual setting in a near future, as was done with CGP-UCB [START_REF] Krause | Contextual Gaussian process bandit optimization[END_REF][START_REF] Valko | Finite-time analysis of kernelised contextual bandits[END_REF].

Appendix A. Laplace method for tuned kernel regression

In this section, we want to control the term |f λ,t (x)f (x)| simultaneously over all t T . To this end, we resort to a version of the Laplace method carefully extended to the RKHS setting.

Before proceeding, we note that since k : X × X → R is a kernel function (that is continuous, symmetric positive definite) on a compact set X equipped with a positive finite Borel measure µ, then there is an at most countable sequence (σ i , ψ i ) i∈N where σ i 0, lim i→∞ σ i = 0 and {ψ i } form an orthonormal basis of L 2,µ (X ), such that

k(x, y) = ∞ j=1 σ j ψ j (x)ψ j (y ) and f 2 K = ∞ j=1 f, ψ j 2 L 2,µ σ j Let ϕ i = √ σ i ψ i . Note that ϕ i L 2 = √ σ i , ϕ i K = 1. Further, if f = i θ i ϕ i , then f 2 K = i θ 2 i and f 2 L 2 = i θ 2 i σ i .
In particular f belongs to the RKHS if and only if i θ 2 i < ∞. For ϕ(x) = (ϕ 1 (x), . . . ) and θ = (θ 1 , . . . ), we now denote θ ϕ(x) for i∈N θ i ϕ i (x), by analogy with the finite dimensional case. Note that k(x, y) = ϕ(x) ϕ(y).

In the sequel, the following Martingale control will be a key component of the analysis.

Lemma A.1 (Hilbert Martingale Control) Assume that the noise sequence {ξ t } ∞ t=0 is conditionally σ 2 -sub-Gaussian ∀t ∈ N, ∀γ ∈ R, ln E[exp(γξ t )|H t-1 ] γ 2 σ 2 2 .
Let τ be a stopping time with respect to the filtration {H t } ∞ t=0 generated by the variables {x t , ξ t } ∞ t=0 . For any q = (q 1 , q 2 , . . . ) such that q ϕ i (x) = i∈N q i ϕ(x) < ∞, and deterministic positive λ, let us denote

M q m,λ = exp m t=1 q ϕ(x t ) √ λ ξ t - σ 2 2 m t=1 (q ϕ(x t )) 2 λ
Then, for all such q the quantity M q τ,λ is well defined and satisfies

ln E[M q τ,λ ] 0 .
Proof The only difficulty in the proof is to handle the stopping time. Indeed, for all m ∈ N, thanks to the conditional R-sub-Gaussian property, it is immediate to show that {M q m,λ } ∞ m=0 is a non-negative super-martingale and actually satisfies ln E[M q m,λ ] 0. By the convergence theorem for nonnegative super-martingales, M q ∞ = lim m→∞ M q m,λ is almost surely well-defined, and thus M q τ,λ is well-defined (whether τ < ∞ or not) as well. In order to show that ln E[M q τ,λ ] 0, we introduce a stopped version

Q q m = M q min{τ,m},λ of {M q m,λ } m . Now E[M q τ,λ ] = E[lim inf m→∞ Q q m ] lim inf m→∞ E[Q q m ]
1 by Fatou's lemma, which concludes the proof. We refer to [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] for further details.

We are now ready to prove the following result.

Proof of Theorem 2.2 (Streaming Kernel Least-Squares) We make use of the features in an explicit way. Let λ = λ t+1 . For f ∈ K, we denote θ its corresponding parameter sequence. We let Φ t = (ϕ(x t )) t t be a t × ∞ matrix built from the features and introduce the bi-infinite matrix V λ,t = I + 1 λ Φ t Φ t as well as the noise vector E t = (ξ 1 , . . . , ξ t ). In order to control the term |f λ,tf (x)|, we first decompose the estimation term. Indeed, using the feature map, it holds that

f λ,t (x) = k t (x) (K t + λI t ) -1 Y t = ϕ(x) Φ t (Φ t Φ t + λI t ) -1 Y t = ϕ(x) Φ t I t λ - 1 λ Φ t λI +Φ t Φ t -1 Φ t Y t = ϕ(x) (Φ t Φ t + λI) -1 Φ t (Φ t θ + E t )
where in the third line, we used the Shermann-Morrison formula. From this, simple algebra yields

f λ,t (x) -f (x) = 1 λ ϕ(x) V -1 λ,t Φ t E t -λθ .
We then obtain, from a simple Hölder inequality using the appropriate matrix norm, the following decomposition, that is valid provided that all terms involved are finite.

|f λ,t (x) -f (x)| 1 √ λ ϕ(x) V -1 λ,t 1 √ λ Φ t E t V -1 λ,t + √ λ θ V -1 λ,t
Now, we note that a simple application of the Shermann-Morrison formula yields

ϕ(x) 2 V -1 λ,t = k t (x, x) .
On the other hand, the last term of the bound is controlled as θ

V -1 λ,t θ . Thus, |f λ,t (x) -f (x)| k 1/2 λ,t (x, x) λ t+1 1 λ t+1 Φ t E t V -1 λ t+1 ,t + λ t+1 θ 2 .
In order to control the remaining term, 1 √

λ t+1 Φ t E t V -1 λ t+1 ,t
, for all t, we now want to apply Lemma A.1. However, the lemma does not apply since λ t+1 is H t -measurable. Thus, before proceeding, we upper-bound it by the similar expression involving λ :

1 λ Φ t E t 2 V -1 λ,t = E t Φ t λ (I + 1 λ Φ t Φ t ) -1 Φ t E t = E t Φ t (λI + Φ t Φ t ) -1 Φ t E t E t Φ t (λ I + Φ t Φ t ) -1 Φ t E t ,
where in the last line, we use the fact that the function f : λ → u (λI +A) -1 u, for u = Φ t E t and A = Φ t Φ t is non increasing (see Lemma A.2 below). Thus,

1 √ λ t+1 Φ t E t V -1 λ t+1 ,t 1 √ λ Φ λ ,t E t V -1 λ ,t
. Next, we introduce a random stopping time τ , to be defined later and apply Lemma A.1.

More precisely, let Q ∼ N (0, I) be an infinite Gaussian random sequence which is independent of all other random variables. We denote Q ϕ

(x) = i∈N Q i ϕ i (x). For all x, k(x, x) = i∈N ϕ 2 i (x) < ∞ and thus V(Q ϕ(x)) < ∞. We define M m,λ = E[M Q m,λ ]. Clearly, we still have E[M λ ,τ ] = E[E[M Q m,λ ]|Q] 1. Since V λ ,τ = I + 1 λ Φ τ Φ τ , elementary algebra gives det(V λ ,τ ) = det(V λ ,τ -1 + 1 λ ϕ(x τ )ϕ(x τ ) ) = det(V λ ,τ -1 )(1 + 1 λ ϕ(x τ ) 2 V -1 λ ,τ -1 ) = det(V λ ,0 ) τ t =1 1 + 1 λ ϕ(x t ) 2 V -1 λ ,t -1
, where we used the fact that the eigenvalues of a matrix of the form I + xx are all ones except for the eigenvalue 1 + x 2 corresponding to x. Then, note that det(V λ ,0 ) = 1 and thus

ln(det(V λ ,τ )) = τ t =1 ln(1 + 1 λ ϕ(x t ) 2 V -1 λ ,t -1 ) = 1 2 τ t =1 ln 1 + 1 λ k λ ,t -1 (x t , x t ) .
In particular, ln(det(V λ ,τ )) is finite. The only difficulty in the proof is now to handle the possibly infinite dimension. To this end, it is enough to take a look at the approximations using the d first dimension of the sequence for each d. We note Q d , M λ ,τ , Φ τ,d and V τ,d the restriction of the corresponding quantities to the components {1, . . . , d}. Thus Q d is Gaussian N (0, I d ). Following the steps from Abbasi-Yadkori et al. ( 2011), we obtain that

M m,d,λ = 1 det(V λ ,m,d ) 1/2 exp 1 2σ 2 λ Φ m,d E m 2 V -1 λ ,m,d
.

Note also that E[M τ,d,λ ] 1 for all d ∈ N. Thus, we obtain by an application of Fatou's lemma that

P lim d→∞ Φ τ,d E τ 2 V -1 λ ,τ,d 2σ 2 λ log det(V λ ,τ,d ) 1/2 /δ > 1 E lim d→∞ δ exp 1 2λ σ 2 Φ τ,d E τ 2 V -1 τ,d det(V λ ,τ,d ) 1/2 δ lim d→∞ E[M τ,d,λ ] δ .
We conclude by defining τ following [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF], by

τ (ω) = min t 0; ω ∈ Ω s.t. Φ t E t 2 V -1 λ ,t > 2σ 2 λ log det(V λ ,t ) 1/2 /δ .
Then τ is a random stopping time and

P ∃t, Φ t E t 2 V -1 λ ,t > 2σ 2 λ log det(V λ ,t ) 1/2 /δ = P(τ < ∞) δ.
Finally, combining this result with the previous remarks we obtain that with probability higher than 1δ, uniformly over x ∈ X and t T , it holds that

|f λ,t -f (x)| k 1/2 λ,t (x, x) λ t+1 2σ 2 ln det(I + 1 λ Φ t Φ t ) 1/2 δ + λ t+1 f K .
Lemma A.2 (Technical lemma) The function f : λ → u (λI + A) -1 u, where A is a semi-definite positive matrix and u is any vector, is non-decreasing on λ ∈ R + .

Proof Indeed, let h > 0. By the Sherman-Morrison formula, we obtain

f (λ + h) = f (λ) -hu (λI + A) -1 (I + h(λI + A) -1 ) -1 (λI + A) -1 u .
Thus, since λI + A is also semi-definite positive, we have

lim h→0 f (λ + h) -f (λ) h = -u (λI + A) -1 (λI + A) -1 u 0 .

Appendix B. Variance estimation

In this section, we give the proof of Theorem 3.1. To this end, we proceed in two steps. First, we provide an upper bound and lower bound on the variance estimate in the next theorem. Then, we use these bounds in order to derive the final statement.

Theorem B.1 (Regularized variance estimate) Under the second-order sub-Gaussian predictable assumption, for any random stopping time τ for the filtration of the past, with probability higher than 1 -3δ, it holds

σ 2 k,λ,τ σ 1 + 2C τ (δ) τ + f K λ τ 1 - 1 max t τ (1 + k λ,t-1 (x t , x t )) σ 2 k,λ,τ σ 1 - C τ (δ) τ - C τ (δ) + 2D λ ,τ (δ) τ - 2σλ 1/2 f K D λ ,τ (δ) τ .
where we introduced for convenience the constants C τ (δ) = ln(e/δ) 1+ln(π 2 ln(τ )/6)/ ln(1/δ) and D λ ,τ (δ) = 2 ln(1/δ) + τ t=1 ln(1+ 1 λ k λ ,t-1 (x t , x t )).

Proof We use the feature maps and start with the following decomposition

τ σ 2 k,λ,τ = τ t=1 (y t -f λ,τ (x t )) 2 = τ t=1 (y t -θ λ,τ , ϕ(x t ) ) 2 = (θ -θ λ,τ ) G τ (θ -θ λ,τ ) + E τ 2 + 2(θ -θ λ,τ ) Φ τ E τ . (6)
where

θ -θ λ,τ = (I -G -1 λ,τ G τ )θ -G -1 λ,τ Φ τ E τ with G λ,τ = λI + G τ and G τ = Φ τ Φ τ .
On the one hand, we can control the first term in ( 6) via

(θ -θ λ,τ ) G τ (θ -θ λ,τ ) = [(I -G -1 λ,τ G τ )θ -G -1 λ,τ Φ τ E τ ] G τ [(I -G -1 λ,τ G τ )θ -G -1 λ,τ Φ τ E τ ] = [λθ -Φ τ E τ ] G -1 λ,τ G τ G -1 λ,τ [λθ -Φ τ E τ ] = [λθ -Φ τ E τ ] [G -1 λ,τ -λG -2 λ,τ ][λθ -Φ τ E τ ] = Φ τ E τ 2 G -1 λ,τ -λ Φ τ E τ 2 G -2 λ,τ + λ 2 θ 2 G -1 λ,τ -λ 3 θ 2 G -2 λ,τ -2λθ [G -1 λ,τ -λG -2 λ,τ ]Φ τ E τ
where we used the fact that

I -G -1 λ,τ G τ = λG -1 λ,τ and then that G -1 λ,τ G τ G -1 λ,τ = G -1 λ,τ -λG -2 λ,τ . Likewise, we control the third term in (6) via 2(θ -θ λ,τ ) Φ τ E τ = 2[(I -G -1 λ,τ G τ )θ -G -1 λ,τ Φ τ E τ ] Φ τ E τ = 2[λθ -Φ τ E τ ] G -1 λ,τ Φ τ E τ = 2λθ G -1 λ,τ Φ τ E τ -2 Φ τ E τ 2 G -1 λ,τ
.

Combining these two bounds, we have τ t=1

(y t -θ λ,τ , ϕ(x t ) ) 2 = E τ 2 -Φ τ E τ 2 G -1 λ,τ -λ Φ τ E τ 2 G -2 λ,τ +λ 2 θ 2 G -1 λ,τ -λ 3 θ 2 G -2 λ,τ + 2λ 2 θ G -2 λ,τ Φ τ E τ E τ 2 + λ 2 λ min(G λ,τ ) θ 2 2 1 - λ λ max (G λ,τ ) + 2 λ 2 λ min 3/2 (G λ,τ ) θ 2 Φ τ E τ G -1 λ,τ E τ 2 + λ 2 λ max (G λ,τ ) θ 2 2 1 - λ λ min(G λ,τ ) -2 λ 2 λ min 3/2 (G λ,τ ) θ 2 Φ τ E τ G -1 λ,τ -Φ τ E τ 2 G -1 λ,τ 1 + λ λ min(G λ,τ )
.

Now, from Lemma B.1, it holds on an event Ω 1 of probability higher than 1δ,

0 Φ τ E τ 2 G -1 λ,τ = 1 λ Φ τ E τ 2 V -1 λ,τ 1 λ Φ τ E τ 2 V -1 λ ,τ σ 2 D λ ,τ (δ) .
On the other hand, we control the second term E τ 2 by Lemma B.1 below, and obtain that with probability higher than 1 -2δ,

E τ 2 τ σ 2 + 2σ 2 2τ C τ (δ) + 2σ 2 C τ (δ) E τ 2 τ σ 2 -2σ 2 τ C τ (δ) ,
where C τ (δ) = ln(e/δ)(1 + c τ / ln(1/δ)). Thus, combining these two results with a union bound, we deduce that with probability higher than 1 -3δ it holds that

σ 2 λ,τ σ 2 + 2σ 2 2C τ (δ) τ + 2σ 2 C τ (δ) τ + λ 2 τ λ min(G λ,τ ) θ 2 2 1 - λ λ max (G λ,τ ) -2 σλ 2 τ λ min 3/2 (G λ,τ ) θ 2 D λ ,τ (δ) σ 2 λ,τ σ 2 -2σ 2 C τ (δ) τ + λ 2 τ λ max (G λ,τ ) θ 2 2 1 - λ λ min(G λ,τ ) -2 λ 2 σ τ λ min 3/2 (G λ,τ ) θ 2 D λ ,τ (δ) - σ 2 D λ ,τ (δ) τ 1 + λ λ min(G λ,τ )
.

We can now derive a bound on σ 2 λ,τ . Indeed,

σ 2 λ,τ σ + 2σ 2 C τ (δ) τ 2 + λ 2 τ λ min(G λ,τ ) θ 2 2 1 - λ λ max (G λ,τ ) σ 2 λ,τ σ - σ 2 C τ (δ) τ 2 - σ 2 τ C τ (δ) + D λ ,τ (δ) 1 + λ λ min(G λ,τ ) - 2λ 2 σ τ λ min 3/2 (G λ,τ ) θ 2 D λ ,τ (δ) .
Thus, using the inequality √ a + b √ a + √ b, on both inequalities, we get

σ 2 λ,τ σ + σ 2C τ (δ) τ + λ θ 2 τ λ min(G λ,τ ) 1 - λ λ max (G λ,τ ) σ 2 λ,τ σ -σ C τ (δ) τ -σ C τ (δ) + D λ ,τ (δ) 1+ λ λ min(G λ,τ ) τ -λ 2σ θ 2 D λ ,τ (δ) τ λ min 3/2 (G λ,τ ) .
Corollary 1 (Extension of Corollary 3.13 in Maillard (2016)) With probability higher than 1 -3δ , it holds simultaneously over all t 0,

σ 1 α 2 √ λ f K D t,λ (δ ) 2t + √ λ f K D λ ,t (δ ) 2t + σ λ,t α 2 σ σ λ,t -f K λ t 1 - 1 max t t (1 + k λ,t -1 (x t , x t )) 1 + 2C t (δ ) t -1
,

where α = max 1 -Ct(δ ) t - Ct(δ )+2D λ ,t (δ ) t
, 0 . Further, if an upper bound σ + σ is known, one can derive the following inequalities that hold with probability higher than 1 -3δ ,

σ σ λ,t + σ + C t (δ ) t + C t (δ ) + 2D λ ,t (δ ) t + 2σ + λ 1/2 f K D t,λ (δ ) t σ σ λ,t -σ + 2C t (δ ) t -f K λ t 1 - 1 max t t (1 + k λ,t -1 (x t , x t ))
.

Proof Using Theorem B.1, it holds with high probability that

σ λ,τ A σ 1 - C τ (δ ) τ - C τ (δ ) + 2D λ ,τ (δ ) τ C - √ σ 2 √ λ f K D λ ,τ (δ ) τ B .
The inequality rewrites A σC -√ σB. Now, let y 2 = σ. If C > 0, the inequality holds provided that y 0 and A + yB -Cy 2 0, that is when 0 y

B+ √ B 2 +4AC 2C
. We conclude by choosing the stopping time τ corresponding to the probability of bad events, as in the proof of Theorem 2.2, then by remarking that t → C t (δ ) is an increasing function.

Lemma B.1 (Lemma 5.10 from [START_REF] Maillard | Self-normalization techniques for streaming confident regression[END_REF]) Assume that T n is a random stopping time that satisfies T n n almost surely, then

P 1 T n Tn i=1 ξ 2 i σ 2 + 2σ 2 2 ln(e/δ) T n + 2σ 2 ln(e/δ) T n ln(n) ln(e/δ) δ , P 1 T n Tn i=1 ξ 2 i σ 2 -2σ 2 ln(e/δ) T n ln(n) ln(e/δ) δ .
Further, for a random stopping time T , and if we introduce c T = ln(π 2 ln 2 (T )/6), then

P 1 T T i=1 ξ 2 i σ 2 +2σ 2 2 ln(e/δ)(1 + c T / ln(1/δ)) T + 2σ 2 ln(e/δ)(1 + c T / ln(1/δ)) T δ , P 1 T T i=1 ξ 2 i σ 2 -2σ 2 ln(e/δ)(1 + c T / ln(1/δ)) T δ . s 2 λ,t-1 (x t ) = σ 2 T t=1 1 λ t k λt,t-1 (x t , x t ) σ 2 T t=1 C 2 σ 2 k σ 2 /C 2 ,t-1 (x t , x t ) = σ 2 T t=1 min C 2 σ 2 k σ 2 /C 2 ,t-1 (x t , x t ), C 2 σ 2 2C 2 ln(1 + C 2 /σ 2 ) γ T (σ 2 /C 2 ).
In particular, we obtain by a Cauchy-Schwarz inequality,

T t=1 k λt,t-1 (x t , x t ) λ t T 2C 2 /σ 2 ln(1 + C 2 /σ 2 ) γ T (σ 2 /C 2 ) .
Proof of Lemma 4.2 We want to control the quantity B λt,t (δ). First of all, recall from Equation 3 that

B λt,t (δ) = λ t C +σ +,t 2 ln(1/δ) + 2γ t (λ -) σ + + σ + 2 ln(1/δ) + 2γ t (σ 2 t,-/C 2 ) ,
where we use the facts that λ t σ 2 + /C 2 and λ -σ 2 t,-/C 2 . Then, using that σ 2 t,-σ -, that γ t (•) is non-increasing and non-decreasing with t, it comes

B λt,t (δ) σ + + σ + 2 ln(1/δ) + 2γ T (σ 2 -/C 2 ) .
Alternatively one may use Theorem B.1 in order to control the random variables σ t,+ and σ t,-in a tighter way. For instance, by Theorem B.1, we easily obtain that with high probability, for all t,

σ σ t,- σ - σ √ t ( √ 2 + 1) C t (δ) -C t (δ) + 2D λ ,t (δ) 1 + 2C t (δ)/t - 2σλ 1/2 f K D λ ,t (δ) + C √ λ 1 - 1 max t t (1+k λ,t-1 (xt,xt)) √ t(1 + 2C t (δ)/t) , that is the estimate satisfies σ σ t,- σ -O(1/ √ t). This in turns implies that γ t (σ 2 -,t /C 2 ) γ t (σ 2 /C 2 ) + O(1/ √ t). Likewise, it can be shown that σ σ t,+ σ + O(1/ √ t), which yields B λt,t (δ) σ 1 + 2 ln(1/δ) + 2γ T (σ 2 -/C 2 ) + o(1) .
Proof of Theorem 4.1 (UCB algorithm for kernel bandits) Let r t denote the instantaneous regret at time t and f + (x t ) denote the optimistic value at the chosen point x t , built from the confidence set used by the UCB algorithm. The following holds with probability higher than 1 -4δ for each time-step t

r t (λ t ) = f (x ) -f (x t ) f + t-1 (x t ) -f (x t ) |f + t-1 (x t ) -f λt,t-1 (x t )| + |f λt,t-1 (x t ) -f (x t )| 2 k λt,t-1 (x t , x t ) λ t B λt,t-1 (δ) .
Thus, we deduce that with probability higher than 1 -4δ:

R T = T t=1 r t (λ) 2 T t=1 k λt,t-1 (x t , x t ) λ t B λt,t-1 (δ) .
We then use Lemma 4.2 in order to control the term B λt,t-1 (δ), and Lemma 4.1 in order to control the sum of

k λ t ,t-1 (xt,xt) λt
. This yields the following bound on the regret:

R T 2σ + 1 + 2 ln(1/δ) + 2γ T (σ 2 -/C 2 ) T 2C 2 /σ 2 ln(1 + C 2 /σ 2 ) γ T (σ 2 /C 2 ) .
Proof of Theorem 4.2 (TS algorithm for kernel bandits) We closely follow the proof technique of [START_REF] Agrawal | Thompson sampling for contextual bandits with linear payoffs[END_REF], while clarifying and simplifying some steps. The general idea is to split the arms into two groups: saturated arms and unsaturated arms. The former designates arms where samples ft have low probability of dominating f ( ) while the latter designates the other case. This is related to the optimism [START_REF] Abeille | Linear Thompson sampling revisited[END_REF], that is the possibility of sampling a value that is higher than the optimum. Let E t and Ẽt be the events that f t and ft are concentrated around their respective means. More precisely, for a given confidence level δ, we introduce E t,δ = {∀x ∈ X , |f (x)f λt,t-1 (x)| C t,δ (x)} Ẽt,δ = {∀x ∈ X , |f λt,t-1 (x) -ft (x)| Ct,δ (x)} , for some quantities C t,δ (x), Ct,δ (x) to be defined.

Controlling the event E t,δ Choosing the confidence bound to be C t,δ (x) = k λt,t-1 (x, x) λ t B λt,t-1 (δ/4) , then the event E t,δ is controlled as P ∀t 0, E t,δ 1δ.

Controlling the event Ẽt,δ On the other hand, since ft (x)|H t-1 = N (f λt,t-1 (x), V t )

where we introduced the notation Anti-concentration We now resort to an anti-concentration result for Gaussian variables [START_REF] Abramowitz | Handbook of mathematical functions: with formulas, graphs, and mathematical tables[END_REF]. More precisely, the following inequality holds

V t =
P ft ( ) -f λt,t-1 ( ) > C t,δ ( ) H t-1 1 2 √ πz e -z 2 /2
where we introduced the H t-1 -measurable random variable z = C t,δ ( )

v t σ +,

Figure 1 :

 1 Figure 1: Test function f used in the following numerical experiments.

Figure 2 :Figure 3 :

 23 Figure 2: Confidence interval of Theorem 2.1 and Lemma 5.1 (Wang and de Freitas, 2014).

Figure 4 :

 4 Figure 4: Noise estimate from Theorem 3.1 with σ + for a) fixed λ= σ 2 + /C 2 ; b) λ = σ 2 +,t-1 /C 2 .

Figure 5 :

 5 Figure 5: Variance estimate a) from Theorem 3.1, with and without σ + ; b) as minimum of the bounds and σ + , for different upper-bounds.

Figure 6 :

 6 Figure 6: Confidence interval using fixed (Theorem 2.1) and adaptive (Corollary 3.1) regularization, for σ + = 1 and δ = 0.1.

Figure 7 :

 7 Figure 7: Averaged cumulative regret along episodes for a) Kernel UCB and b) Kernel TS.

Figure 8 :

 8 Figure 8: Averaged cumulative regret and one standard deviation along episodes for Kernel TS oracle with Theorem 2.1 and Lemma 5.1 (Wang and de Freitas, 2014).

  (k λt,t-1 (x, x )) x,x ∈X , then we have by a simple union bound over x ∈ X,P( Ẽc t,δ |H t-1 )Summary By definition of the events, under E t,δ and Ẽt,δ , it thus holds that∀x ∈ X , f (x) -ft (x) f (x)f λt,t-1 (x) + f λt,t-1 (x) -ft (x)while on the other hand we have the inclusion {∀x ∈ S t,δ , ft ( ) > ft (x)} ⊂ {x t ∈ S t,δ }. Thus, combining these two properties, we deduce that{x t ∈ S t,δ } ∩ E t,δ ∩ Ẽt,δ ⊂ ∃x ∈ S t,δ , ft ( ) ft (x) ∩ ∀x ∈ S t,δ , ft (x) f ( ) Further, using that ft (x)|H t-1 = N (f λt,t-1 (x), V t ) yields {x t ∈ S t,δ } ∩ E t,δ ∩ Ẽt,δ ⊂ ft ( )f λt,t-1 ( ) f ( )f λt,t-1 ( ) ∩ E t,δ ∩ Ẽt,δ

	⊂		ft ( ) f ( ) .
				t v 2	σ 2 +,t-1
				x∈X	1 √ πz x	e -z 2 x /2
	provided that z x = definition,	vt	Ct,δ (x) +,t-1 σ 2 k λ t ,t-1 (x,x) λ t	1 for all x ∈ X. This motivates the following
			Ct,δ (x) = c t,δ v t	σ 2 +,t-1 λ √ πδ), 1} ensures
	that
	P(∃t 0 Ẽc t,δ |H t-1 )	t 0	|X| √ πc t,δ	e -c 2 t,δ /2 =	t 0	δ c t,δ t(t + 1)
				t 0	δ t(t + 1)	= δ,
	from which we obtain P ∀t 0, Ẽt,δ	1 -δ.
			C t,δ (x) + Ct,δ (x)
			=	k λt,t-1 (x, x) λ t	B λt,t-1 (δ/4) + c t,δ v t σ +,t-1

λt t

k λt,t-1 (x, x) , for a well-chosen sequence (c t,δ ) t . The choice c t,δ = max{ 2 ln(t(t + 1)|X|/ = s λ,t-1 (x)

B λt,t-1 (δ/4) σ + c t,δ v t σ +,t-1 σ gt(δ) . ⊂ ft ( )f λt,t-1 ( ) C t,δ ( ) ⊂ ft ( )f λt,t-1 ( ) C t,δ ( ) , from which we obtain ft ( )f λt,t-1 ( ) > C t,δ ( ) ∩ E t,δ ⊂ {x t ∈ S t,δ } ∪ Ẽc t,δ .

Thus, we have proved that

P x t / ∈ S t,δ H t-1 P ft ( )f λt,t-1 ( ) > C t,δ ( ), E t,δ H t-1 -P Ẽc t,δ H t-1 = P ft ( )f λt,t-1 ( ) > C t,

δ ( ) H t-1 I{ E t,δ } -P Ẽc t,δ H t-1 .

  for constants α t , β t such that 2α t ln(β t ) 1 thus yields By construction, E[X t |H t-1 ] = 0 and |X t | Rη t . Thus, by an application of Azumahoeffding's inequality for martingales, we obtain that for all δ ∈ (0, 1), with probability higher than 1δ, (x t )g t (δ), R η t + s λ,t-1 (x t )g t (δ) + 2 This concludes the proof of the main result, since c t,δ c T,δ .Final bound Then, using Lemma 4.2 we can rewrite the regret asR T = (4 √ πe + 1)(1 + c T,δ )σ + 1 + 2 ln(4/δ) + 2γ T (σ 2 -/C 2 )

						T	T
						X t	2	R 2 η 2 t ln(1/δ) ,
						t=1	t=1
	and thus that on an event of probability higher than 1 -3δ,
	R T		T	min 2s λ,t-1 T	R 2 η 2 t ln(1/δ) .
			t=1				t=1
	Replacing η t with its expression, that is η t = √ 4πe 1 + δ max{ 2 ln(t(t + 1)|X|/ √ 4πe √ 4πe 1 + δ √ 4πe t(t + 1) ,	√ πδ), 1}t(t + 1)
	we deduce that with probability higher than 1 -3δ, R T (4 √ πe + 1)	T t=1	(1 + δ	√ 4πe t(t + 1)	) 2 ln(1/δ)
	(4 √	πe + 1)	T	s λ,t-1 (x t )g t (δ) + Rδ4πe + 8πe(1 + δ	√	4πe) 2 R T ln(1/δ)
					t=1
	= (4	√	πe + 1)	T t=1	k λt,t-1 (x t , x t ) λ t	B λt,t-1 (δ/4)(1 + c t,δ )
	+Rδ4πe + 8πe(1 + δ	√	4πe) 2 R T ln(1/δ) .
							T	k λt,t-1 (x t , x t )
							t=1	λ t
	+Rδ4πe + 8πe(1 + δ	√	4πe) 2 R T ln(1/δ) .
	t-1 Using Lemma 4.1 together with a Cauchy-Schwarz inequality, we finally obtain k λ t ,t-1 ( , ) λt = B λt,t-1 (δ/4) , provided that z 1 . v t σ +,t-1 Taking v t = R T = (4 √ πe + 1)(1 + c T,δ )σ + 1 + 2 ln(4/δ) + 2γ T (σ 2 -/C 2 ) T 2C 2 /σ 2 ln(1 + C 2 /σ 2 ) B λ t ,t-1 (δ/4) σ +,t-1 √ 2αt ln(βt) +Rδ4πe + 8πe(1 + δ √ 4πe) 2 R T ln(1/δ) .	γ T (σ 2 /C 2 )

P ft ( )f λt,t-1 ( ) > C t,δ ( ) H t-1 p t def = β -αt t 2 √ π 2α t ln(β t ) . T t=1 s λ,t-1 (x t )g t (δ) + Rδ4πe + R 8πe

The term on the right-hand side corresponds to the cumulant generating function of the chi-squared distribution with 1 degree of freedom. This assumption naturally holds for Gaussian variables.

Acknowledgments

This work was supported through funding from the Natural Sciences and Engineering Research Council of Canada (NSERC, Canada), the REPARTI strategic network (FRQ-NT, Québec), MITACS, and E Machine Learning Inc. O.-A. M. acknowledges the support of the French Agence Nationale de la Recherche (ANR), under grant ANR-16-CE40-0002 (project BADASS).

Appendix C. Application to stochastic multi-armed bandits

Proof of Lemma 4.1 Using the facts that min{r, α} (α/ ln(1 + α)) ln(1 + r) and min λ∈λ λ σ 2 /C 2 : T Saturated arms It is now convenient to introduce the set of saturated times a time t S t,δ = x ∈ X : f ( )f (x) > s λ,t-1 (x)g t (δ) together with x S,t = argmin

x / ∈S t,δ s λ,t-1 (x) .

We remark that by construction / ∈ S t,δ for all t. Now, by the strategy of the Kernel TS algorithm, x t = argmax x∈X ft (x). Thus, we deduce that on the event E t,δ ∩ Ẽt,δ

We then remark that by definition of x S,t , we have

.

Since on the other hand, (f ( )

Lower bounding the denominator At this point, we note that on the event E t,δ ∩ Ẽt,δ , for all x ∈ S t,δ ,

Summary At this point of the proof, we have proved that

where in the second inequality, we used the property 1 p-q = 1 p + q p(p-q) 1 p + q p 2 , for p > q. Combining the bound on P( Ẽc t,δ |H t-1 ) and the definition of p t , we obtain

Pseudo-regret Summing-up the previous terms over t 1, we obtain that the pseudoregret of the Kernel TS strategy satisfies, on the event t 1 E t,δ ∩ Ẽt,δ that holds with probability higher than 1 -2δ,

where c t,δ = max{ 2 ln(t(t + 1)|X|/ √ πδ), 1}, and the constants α t , β t must be such that 2α t ln(β t ) 1 and 8πα t ln(β t )β αt t 1. Also, let us recall that

In particular, the specific choice α t = 1/2 ln(β t ) where β t > 1 (which satisfies 1 1 and √ 4πe 1) yields

where we introduced the deterministic quantity η t+1) .

Concentration In order to finish the proof, we now relate the sum of the terms E[s λ,t-1 (x t )|H t-1 ], t 1 to the sum of the terms s λ,t-1 (x t ). More precisely, let us introduce the following random variable X t = E min 2s λ,t-1 (x t )g t (δ), R H t-1 η tmin 2s λ,t-1 (x t )g t (δ), R η t .