AInstantaneous Regret Bound Conditioned on the event that (8) in Lemma 1 holds (with probability 1 δ), it follows that

As wt is selected as an LV w.r.t. From (18), (19), and (20), we obtain (9), (10), and (11), respectively. C1TβTγT (21) where C1 = 8/log(1 + σ 2n) and γT is the maximum information gain about f that can be obtained by observing any set of T observations. By selecting xtas a sample from the posterior belief of x given yDt 1, it is noted that the distribution of xt and x are the same, i.e., p(xt|yDt 1) = p(x |yDt 1). We prove the following Lemma 4 which is then used to prove Lemma 5. Lemma 3 follows from Lemma 5. Lemma 5. Consider a realization f1 of the black-box function f following the GP posterior belief Thus, Lemma 5 implies Lemma 3. Let us consider CV-TS with a batch query of size k at each iteration.