Supplementary Material

We say a real-valued random variable X is -sub-Gaussian if it its mean is zero and for all " 2 R we have E[exp("X)] exp Such assumptions on the noise variables are frequently used in bandit optimization. Typically, in kernelized bandits, we assume that unknown f 2F k(D;B)= {f 2H k(D): kfkk B}, where Hk(D) is the reproducing kernel Hilbert space of functions associated with the given positive-definite kernel function. Typically, the learner knows Fk(D;B), meaning that both k(,) and B are considered as input to the learner's algorithm. We outline some commonly used kernel functions k: D D! R, that we also consider: Linear kernel: klin(x,x0)= xTx0, Squared exponential kernel: kSE(x,x0)=exp kx x0k2 2l2, Matérn kernel: kMat(x,x0)= 2 Maximum information gain is a kernel-dependent quantity that measures the complexity of the given function class. It has first been introduced in [40], and since then it has been used in numerous works on Gaussian process bandits.