Supplementary Material: " Optimal Order Simple Regret for Gaussian Process Bandits "

Mercer's representation theorem indicates that The proof of Proposition 1 uses the following lemma. Lemma 1 F or a positive definite kernel k and its corresponding RKHS, the following holds. For a proof, see [1, Lemma 3.9 ]. Expanding the RKHS norm in the right hand side through an algebraic manipulation, we get null null null null null null null null k (.,x) The first equation uses the reproducing property of the RKHS. We now move to the proof of Theorem 2. For the simplicity of the notation let us use τ = nullZ The MVR algorithm selects the points with the highest variance first.