SupplementaryMaterial: " OptimalOrderSimple RegretforGaussianProcessBandits "

InthecaseofSEkernel, the regularity assumption implies the existence ofall weak derivativesoff. The third equation follows from the definition of Zn(x). The first inequality holds by Assumption 2. We utilize Proposition 1 to conclude thatkZn(x)k2 σ Thesecond inequality holds bydefinition oflight-tailed distributions. Notice thatthecareful choice ofτ andθ ensures θζi(x) h0, which will be validated next. The seventh line is obtained by replacing the valueof θ.