{\bm{\epsilon}}^{(n)}+{\bm{\mu}}^{(n)}_{t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})&(n\geq
2).\end{cases}$ (D.20)

Similarly, we define
$\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
as

$\displaystyle\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
$\displaystyle={\sigma}^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})$
(D.21)
$\displaystyle\qquad+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),$
(D.22)

where $m\in[M^{(n)}]$ and
$\tilde{\sigma}^{(1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)})=\sigma^{(1)}_{s,t}({\bm{0}},{\bm{x}}^{(1)})$.
Then, the following holds.

######  Theorem D.4.

Assume that Assumptions D.1 and C.3 hold. Also assume that
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\tilde{\mathcal{Y}}^{(n)}$
for any $n\in[N]$, iteration $t\geq 1$, realization ${\bm{\epsilon}}$ and
input $({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$. Let $\delta\in(0,1)$, and
define $\beta_{t}$ by D.18. Then, the following inequality holds with
probability at least $1-\delta$:

$\displaystyle|{z}^{(n)}_{{\bm{\epsilon}},m}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})-\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})|\leq{\beta}^{1/2}_{t}\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}),$
(D.23) $\displaystyle\qquad\forall n\in[N],m\in[M^{(n)}],t\geq
1,{\bm{\epsilon}},({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}),$ (D.24)

where ${z}^{(n)}_{{\bm{\epsilon}},m}$ and
$\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}$ are the $m$-th element of
${\bm{z}}^{(n)}_{{\bm{\epsilon}}}$ and
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}$, respectively.

###### Proof.

By using the same argument as in the proof of Theorem C.5, we get Theorem D.4.
∎

From Theorem D.4, taking expectation with respect to ${\bm{\epsilon}}$, we get
the following corollary.

######  Corollary D.5.

Assume that the same condition as in Theorem D.4 holds. Let $\delta\in(0,1)$,
and define $\beta_{t}$ by D.18. Then, with probability at least $1-\delta$,
the following inequality holds for any $n\in[N]$, $m\in[M^{(n)}]$, iteration
$t\geq 1$ and input ${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}$:

$\displaystyle\mathbb{E}_{\bm{\epsilon}}[\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})-\beta^{1/2}_{t}\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})]$
(D.25)
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}}[{z}^{(n)}_{{\bm{\epsilon}},m}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})]$
(D.26)
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}}[\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})+\beta^{1/2}_{t}\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})].$
(D.27)

In particular, when $n=N$ and $m=1$, it follows that

$\displaystyle\mathbb{E}_{\bm{\epsilon}}[\tilde{z}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})-\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})]$
(D.28) $\displaystyle\leq G({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$ (D.29)
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}}[\tilde{z}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})+\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})].$
(D.30)

###  D.2 UCB-based Optimization Strategy for Expected Regrets

Here, we give a UCB-based AF and regret bounds for $R_{G,T}$ and
$r^{(\text{S})}_{G,T}$. We define an expected cascade process upper confidence
bound (EcUCB) as

$\mathrm{EcUCB}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})=\mathbb{E}_{\bm{\epsilon}}[\tilde{z}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})+\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})].$
(D.31)

By using this AF, we select the next evaluation point
$({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})$ by

$\displaystyle({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})=\operatorname*{arg\,max}_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X}}\mathrm{EcUCB}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}).$
(D.32)

Moreover, let
$\tilde{A}=\\{{\bm{\tilde{}}{a}}_{1},\ldots,{\bm{\tilde{}}{a}}_{T}\\}$ be a
subset of $\tilde{\mathcal{Y}}^{(n-1)}\times\mathcal{X}^{(n)}$, and let
${\bm{y}}^{(n)}_{m,\tilde{A}}$ be a random vector, where the $i$-th element of
${\bm{y}}^{(n)}_{m,\tilde{A}}$ is given by
$y^{(n)}_{m,{\bm{\tilde{}}{a}}_{i}}=f^{(n)}_{m}({\bm{\tilde{}}{a}}_{i})+\varepsilon^{(n)}_{{\bm{\tilde{}}{a}}_{i}}$.
Then, the maximum information gain $\tilde{\gamma}^{(n)}_{m,T}$ at iteration
$T$ is given by

$\displaystyle\tilde{\gamma}^{(n)}_{m,T}=\max_{\tilde{A}\subset\tilde{\mathcal{Y}}^{(n-1)}\times\mathcal{X}^{(n)},|\tilde{A}|=T}\mathrm{I}({\bm{y}}^{(n)}_{m,\tilde{A}};f^{(n)}_{m}).$
(D.33)

Furthermore, we define $\tilde{\gamma}_{T}=\max_{1\leq n\leq N,1\leq m\leq
M^{(n)}}\tilde{\gamma}^{(n)}_{m,T}$. Then, the following theorem gives regret
bounds for $R_{G,T}$ and $r^{(\text{S})}_{G,T}$.

######  Theorem D.6.

Assume that Assumptions D.1, C.3 and C.4 hold. Also assume that
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\tilde{\mathcal{Y}}^{(n)}$
for any $n\in[N]$, iteration $t\geq 1$, realization ${\bm{\epsilon}}$ and
input $({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$. Let $\delta\in(0,1)$, and
define $\beta_{t}$ by D.18. Then, when the optimization is performed using
D.32, the following holds:

$\displaystyle\mathbb{P}$
$\displaystyle\left(R_{G,T}\leq\sqrt{32M^{2}_{\text{prod}}M^{2}_{\text{sum}}T{C}^{2N}_{0,T}\left(\log(5M_{\text{sum}}/\delta)+\frac{\tilde{\gamma}_{T}}{2\log(1+\sigma^{-2})}\right)}\quad\forall
T\geq 1\right)\geq 1-2\delta,$ (D.34) $\displaystyle\mathbb{P}$
$\displaystyle\left(r^{(\text{S})}_{G,T}\leq
T^{-1/2}\sqrt{32M^{2}_{\text{prod}}M^{2}_{\text{sum}}{C}^{2N}_{0,T}\left(\log(5M_{\text{sum}}/\delta)+\frac{\tilde{\gamma}_{T}}{2\log(1+\sigma^{-2})}\right)}\quad\forall
T\geq 1\right)\geq 1-2\delta,$ (D.35)

where $C_{0,t}=(1+L_{\sigma})\beta^{1/2}_{t}+L_{f}+1$.

###### Proof.

From Theorem D.4 and the definition of
$\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}(\cdot)$, noting that
${\sigma}^{(n)}_{m,t}(\cdot)$ is Lipschitz continuity, the following
inequality holds with probability at least $1-\delta$:

$\displaystyle\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
(D.36)
$\displaystyle=\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(D.37)
$\displaystyle\quad+\sigma^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})$
(D.38)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(D.39)
$\displaystyle\quad+|\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})|$
(D.40)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(D.41)
$\displaystyle\quad+L_{\sigma}\sum_{s=1}^{M^{(n-1)}}|{z}_{{\bm{\epsilon}},s}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})-\tilde{z}_{{\bm{\epsilon}},s,t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})|$
(D.42)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(D.43)
$\displaystyle\quad+L_{\sigma}\beta^{1/2}_{t}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(D.44)
$\displaystyle=\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+(L_{\sigma}\beta^{1/2}_{t}+L_{f})\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(D.45)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+{C}_{0,t}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}).$
(D.46)

Therefore, by repeating D.46 we get

$\displaystyle\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
(D.47)
$\displaystyle\leq\sigma^{(N)}_{1,t}({\bm{z}}^{(N-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-1)}),{\bm{x}}^{(N)})+{C}_{0,t}\sum_{s=1}^{M^{(N-1)}}\tilde{\sigma}^{(N-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-1)})$
(D.48)
$\displaystyle\leq\sigma^{(N)}_{1,t}({\bm{z}}^{(N-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-1)}),{\bm{x}}^{(N)})+{C}_{0,t}\sum_{s=1}^{M^{(N-1)}}\sigma^{(N-1)}_{s,t}({\bm{z}}^{(N-2)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-2)}),{\bm{x}}^{(N-1)})$
(D.49)
$\displaystyle\qquad+{C}^{2}_{0,t}M^{(N-1)}\sum_{u=1}^{M^{(N-2)}}\tilde{\sigma}^{(N-2)}_{{\bm{\epsilon}},u,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-2)})$
(D.50) $\displaystyle\vdots$ (D.51)
$\displaystyle\leq{C}^{N-1}_{0,t}M_{\text{prod}}\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)}),$
(D.52)

where
${\bm{z}}^{(0)}_{\bm{\epsilon}}({\bm{x}}^{(1)},{\bm{x}}^{(0)})={\bm{0}}$.
Hence, from the Cauchy–Schwarz inequality, it follows that

$\displaystyle\tilde{\sigma}^{(N)2}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
(D.53)
$\displaystyle\leq{C}^{2(N-1)}_{0,t}M^{2}_{\text{prod}}\left(\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}1\right)\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\Bigl{[}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})\Bigr{]}$
(D.54)
$\displaystyle={C}^{2(N-1)}_{0,t}M^{2}_{\text{prod}}M_{\text{sum}}\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\Bigl{[}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})\Bigr{]}.$
(D.55)

Next, from Corollary D.5 and the selection rule D.32, the following holds:

$\displaystyle G({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})$
$\displaystyle\leq\mathrm{EcUCB}_{t}({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})$
(D.56)
$\displaystyle\leq\mathrm{EcUCB}_{t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})$
(D.57)
$\displaystyle=\mathbb{E}_{\bm{\epsilon}}[\tilde{z}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})+\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})].$
(D.58)

Similarly, since $G({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})$
satisfies that

$G({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})\geq\mathbb{E}_{\bm{\epsilon}}[\tilde{z}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})],$
(D.59)

the regret $r_{G,t}$ can be bounded as follows:

$\displaystyle r_{G,t}$
$\displaystyle=G({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})-G({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})$
(D.60) $\displaystyle\leq
2\beta^{1/2}_{t}\mathbb{E}_{\bm{\epsilon}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})].$
(D.61)

Therefore, by using D.61, $R^{2}_{G,T}$ can be written as

$\displaystyle R^{2}_{G,T}$
$\displaystyle=\left(\sum_{t=1}^{T}r_{G,t}\right)^{2}$ (D.62)
$\displaystyle\leq T\sum_{t=1}^{T}r^{2}_{G,t}$ (D.63) $\displaystyle\leq
T\sum_{t=1}^{T}4\beta_{t}(\mathbb{E}_{\bm{\epsilon}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})])^{2}$
(D.64) $\displaystyle\leq
T\sum_{t=1}^{T}4\beta_{t}\mathbb{E}_{\bm{\epsilon}}[\tilde{\sigma}^{(N)2}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})],$
(D.65)

where the first inequality is given by the Cauchy–Schwarz inequality, and the
last inequality is given by Jensen’s inequality. Thus, by substituting D.55
into D.65, we obtain

$R^{2}_{G,T}\leq
4T\beta_{T}\tilde{C}^{2(N-1)}_{T}M^{2}_{\text{prod}}M_{\text{sum}}\sum_{t=1}^{T}\mathbb{E}_{\bm{\epsilon}}[S_{{\bm{\epsilon}},t}],$
(D.66)

where $S_{{\bm{\epsilon}},t}$ is given by

$S_{{\bm{\epsilon}},t}=\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(n-1)}_{t+1}),{\bm{x}}^{(n)}_{t+1}).$
(D.67)

Here, since $k^{(n)}(\cdot,\cdot)\leq 1$, the random variable
$S_{{\bm{\epsilon}},t}$ satisfies $0\leq S_{{\bm{\epsilon}},t}\leq
M_{\text{sum}}$. Hence, from Lemma 3 of Kirschner and Krause, (2018), the
following holds with probability at least $1-\delta$:

$\displaystyle\sum_{t=1}^{T}\mathbb{E}_{\bm{\epsilon}}[S_{{\bm{\epsilon}},t}]$
$\displaystyle\leq
2\sum_{t=1}^{T}S_{{\bm{\epsilon}}_{t+1},t}+4M_{\text{sum}}\log(1/\delta)+8M_{\text{sum}}\log(4M_{\text{sum}})+1$
(D.68) $\displaystyle\leq
2\sum_{t=1}^{T}S_{{\bm{\epsilon}}_{t+1},t}+8M_{\text{sum}}\log(1/\delta)+8M_{\text{sum}}\log(4M_{\text{sum}})+8M_{\text{sum}}\log
1.25$ (D.69)
$\displaystyle=2\sum_{t=1}^{T}S_{{\bm{\epsilon}}_{t+1},t}+8M_{\text{sum}}\log(5M_{\text{sum}}/\delta).$
(D.70)

Therefore, by combining D.66 and D.70, we have

$\displaystyle R^{2}_{G,T}$ $\displaystyle\leq
32T\beta_{T}{C}^{2(N-1)}_{T,0}M^{2}_{\text{prod}}M^{2}_{\text{sum}}\log(5M_{\text{sum}}/\delta)$
(D.71)
$\displaystyle\qquad+8T\beta_{T}{C}^{2(N-1)}_{0,T}M^{2}_{\text{prod}}M_{\text{sum}}\sum_{t=1}^{T}\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\Bigl{[}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}_{{\bm{\epsilon}}_{t+1}}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(n-1)}_{t+1}),{\bm{x}}^{(n)}_{t+1})\Bigr{]}.$
(D.72)

Furthermore, by using the same argument as in Lemma 5.3 and 5.4 of Srinivas et
al., (2010), we get

$\displaystyle\sum_{t=1}^{T}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}_{{\bm{\epsilon}}_{t+1}}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(n-1)}_{t+1}),{\bm{x}}^{(n)}_{t+1})$
$\displaystyle\leq\frac{2}{\log(1+\sigma^{-2})}\tilde{\gamma}^{(n)}_{m,T}$
(D.73) $\displaystyle\leq\frac{2}{\log(1+\sigma^{-2})}\tilde{\gamma}_{T}.$
(D.74)

Hence, from D.72 and D.74, noting that $\beta_{T}\leq{C}^{2}_{0,T}$ we obtain

$\displaystyle R^{2}_{G,T}$ $\displaystyle\leq
32T\beta_{T}{C}^{2(N-1)}_{0,T}M^{2}_{\text{prod}}M^{2}_{\text{sum}}\log(5M_{\text{sum}}/\delta)+\frac{16}{\log(1+\sigma^{-2})}T\beta_{T}{C}^{2(N-1)}_{0,T}M^{2}_{\text{prod}}M^{2}_{\text{sum}}\tilde{\gamma}_{T}$
(D.75)
$\displaystyle=32T\beta_{T}{C}^{2(N-1)}_{0,T}M^{2}_{\text{prod}}M^{2}_{\text{sum}}\left(\log(5M_{\text{sum}}/\delta)+\frac{\tilde{\gamma}_{T}}{2\log(1+\sigma^{-2})}\right)$
(D.76) $\displaystyle\leq
32T{C}^{2N}_{0,T}M^{2}_{\text{prod}}M^{2}_{\text{sum}}\left(\log(5M_{\text{sum}}/\delta)+\frac{\tilde{\gamma}_{T}}{2\log(1+\sigma^{-2})}\right).$
(D.77)

Therefore, with probability at least $1-2\delta$, $R_{G,T}$ can be bounded as
follows:

$R_{G,T}\leq\sqrt{32M^{2}_{\text{prod}}M^{2}_{\text{sum}}T{C}^{2N}_{0,T}\left(\log(5M_{\text{sum}}/\delta)+\frac{\tilde{\gamma}_{T}}{2\log(1+\sigma^{-2})}\right).}$
(D.78)

Similarly, from the definition of $r^{(\text{S})}_{G,T}$, it follows that

$\displaystyle Tr^{(\text{S})}_{G,T}$
$\displaystyle\leq\sum_{t=1}^{T}r_{G,t}=R_{G,T}$ (D.79)
$\displaystyle\leq\sqrt{32M^{2}_{\text{prod}}M^{2}_{\text{sum}}T{C}^{2N}_{0,T}\left(\log(5M_{\text{sum}}/\delta)+\frac{\tilde{\gamma}_{T}}{2\log(1+\sigma^{-2})}\right)}.$
(D.80)

∎

###  D.3 Optimistic Improvement-based AF for the Expectation of the Final
Stage Output

We give an optimistic improvement-based AF for $G$ under the noisy setting.
Let $s\in\\{0,\ldots,N-1\\}$ and ${\bm{y}}\in\tilde{\mathcal{Y}}^{(s)}$. Then,
we define ${\bm{z}}^{(n)}_{{\bm{\epsilon}}}(\cdot|{\bm{y}})$,
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}(\cdot|{\bm{y}})$ and
$\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}(\cdot|{\bm{y}})$ as

$\displaystyle{\bm{z}}^{(n)}_{{\bm{\epsilon}}}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})=$
$\displaystyle\begin{cases}{\bm{\epsilon}}^{(s+1)}+{\bm{f}}^{(s+1)}({\bm{y}},{\bm{x}}^{(s+1)})&(n=s+1),\\\
{\bm{\epsilon}}^{(n)}+{\bm{f}}^{(n)}({\bm{z}}^{(n-1)}_{{\bm{\epsilon}}}({\bm{x}}^{(s+1:n-1)}|{\bm{y}}),{\bm{x}}^{(n)})&(n\geq
s+2),\end{cases}$ (D.81)
$\displaystyle\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})=$
$\displaystyle\begin{cases}{\bm{\epsilon}}^{(s+1)}+{\bm{\mu}}^{(s+1)}_{t}({\bm{y}},{\bm{x}}^{(s+1)})&(n=s+1),\\\
{\bm{\epsilon}}^{(n)}+{\bm{\mu}}^{(n)}_{t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(s+1:n-1)}|{\bm{y}}),{\bm{x}}^{(n)})&(n\geq
s+2),\end{cases}$ (D.82)
$\displaystyle\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})$
$\displaystyle={\sigma}^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{y}}),{\bm{x}}^{(n)})$
(D.83)
$\displaystyle\quad+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{y}}),$
(D.84)

where
$\tilde{\sigma}^{(s)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(s)}|{\bm{y}})=0$
and
${\bm{z}}^{(s)}_{{\bm{\epsilon}}}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(s)}|{\bm{y}})=\tilde{\bm{z}}^{(s)}_{{\bm{\epsilon}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(s)}|{\bm{y}})={\bm{y}}$.
Then, the following theorem holds.

######  Theorem D.7.

Assume that Assumptions D.1 and C.3 hold. Also assume that
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})\in\tilde{\mathcal{Y}}^{(n)}$
for any $s\in\\{0,\ldots,N-1\\}$, $n\in\\{s+1,\ldots,N\\}$, iteration $t\geq
1$, realization ${\bm{\epsilon}}$, given
${\bm{y}}\in\tilde{\mathcal{Y}}^{(s)}$ and input
$({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)})$. Let $\delta\in(0,1)$, and define
$\beta_{t}$ by D.18. Then, the following inequality holds with probability at
least $1-\delta$:

$|{z}^{(n)}_{{\bm{\epsilon}},m}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})-\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})|\leq{\beta}^{1/2}_{t}\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}}),$
(D.85)

where $m\in[M^{(n)}]$, and ${z}^{(n)}_{{\bm{\epsilon}},m}(\cdot|{\bm{y}})$ and
$\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}(\cdot|{\bm{y}})$ are the $m$-th element
of ${\bm{z}}^{(n)}_{{\bm{\epsilon}}}(\cdot|{\bm{y}})$ and
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}(\cdot|{\bm{y}})$, respectively.

###### Proof.

By using the same argument as in the proof of Theorem C.5, we have Theorem
D.7. ∎

From Theorem D.7, taking expectation with respect to ${\bm{\epsilon}}$, we get
the following corollary.

######  Corollary D.8.

Assume that the same condition as in Theorem D.7 holds. Let $\delta\in(0,1)$,
and define $\beta_{t}$ by D.18. Then, the following inequality holds with
probability at least $1-\delta$:

$\displaystyle\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}}[\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})-{\beta}^{1/2}_{t}\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})]$
(D.86)
$\displaystyle\leq\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}}[{z}^{(n)}_{{\bm{\epsilon}},m}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})]$
(D.87)
$\displaystyle\leq\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}}[\tilde{z}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})+{\beta}^{1/2}_{t}\tilde{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})],$
(D.88)

where $\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}}[\cdot]$ is the conditional
expectation of $(\cdot)$ given ${\bm{y}}$.

Based on this lemma, we give valid AFs. Let $n\in[N]$ and
${\bm{y}}^{(n-1)}\in\tilde{\mathcal{Y}}^{(n-1)}$. Then, for any
${\bm{x}}^{(n)}\in\mathcal{X}^{(n)}$ and iteration $t\geq 1$, we define the
optimistic maximum value at the final stage under given ${\bm{y}}^{(n-1)}$,
$\mathrm{UCB}^{(G)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$, as

$\displaystyle\mathrm{UCB}^{(G)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=$ (D.89)
$\displaystyle\max_{({\bm{x}}^{(n+1)},\ldots,{\bm{x}}^{(N)})}\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}^{(n-1)}}\Bigl{[}(\tilde{{z}}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})+\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)}))\Bigr{]},$
(D.90)

where the max operator is ignored when $n=N$. Similarly, we define the
pessimistic maximum value at the final stage under given ${\bm{y}}^{(n-1)}$,
$\mathrm{LCB}^{(G)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$, as

$\displaystyle\mathrm{LCB}^{(G)}_{t}({\bm{y}}^{(n-1)})$ (D.91)
$\displaystyle=\max_{({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)})}\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}^{(n-1)}}\Bigl{[}(\tilde{z}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})-\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)}))\Bigr{]}.$
(D.92)

Moreover, for each $T\geq 1$, we define the pessimistic maximum value at the
final stage as

$Q_{T}=\max_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})}\mathbb{E}_{{\bm{\epsilon}}}\Bigl{[}(\tilde{z}^{(N)}_{{\bm{\epsilon}},1,T}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})-\beta^{1/2}_{T}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,T}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}))\Bigr{]}.$
(D.93)

Then, we define the pessimistic improvement for the final stage with respect
to ${\bm{x}}^{(n)}$ by

$\tilde{a}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\mathrm{UCB}^{(G)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})-\max\\{\mathrm{LCB}^{(G)}_{t}({\bm{y}}^{(n-1)}),Q_{t+n-1}\\}.$
(D.94)

We also define the maximum uncertainty for the final stage with respect to
${\bm{x}}^{(n)}$ as

$\displaystyle\tilde{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\max_{({\bm{x}}^{(n+1)},\ldots,{\bm{x}}^{(N)})}\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}^{(n-1)}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})].$
(D.95)

Then, we give the AF $\tilde{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$ by

$\tilde{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\max\Bigl{\\{}\tilde{a}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}),\eta_{t}\tilde{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\Bigr{\\}},$
(D.96)

where $\eta_{t}$ is a given learning rate. Furthermore, we select the next
point ${\bm{x}}^{(n)}_{t+n}$ by

$\displaystyle{\bm{x}}^{(n)}_{t+n}$
$\displaystyle=\operatorname*{arg\,max}_{{\bm{x}}^{(n)}\in\mathcal{X}^{(n)}}\tilde{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}_{t+n-1}),$
(D.97) $\displaystyle{\bm{y}}^{(n)}_{t+n}$
$\displaystyle={\bm{f}}^{(n)}({\bm{y}}^{(n-1)}_{t+n-1},{\bm{x}}^{(n)}_{t+n})+{\bm{\epsilon}}^{(n)}_{t+n},$
(D.98)

where ${\bm{y}}^{(0)}_{t}={\bm{0}}$. Finally, we define the estimated solution
$(\hat{\bm{x}}^{(1)}_{G,T},\ldots,\hat{\bm{x}}^{(N)}_{G,T})$ by using the
pessimistic maximum value as follows:

$\displaystyle(\hat{\bm{x}}^{(1)}_{G,T},\ldots,\hat{\bm{x}}^{(N)}_{G,T})=$
(D.99)
$\displaystyle\operatorname*{arg\,max}_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X},1\leq
t\leq
T}\mathbb{E}_{{\bm{\epsilon}}}\Bigl{[}(\tilde{z}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})-\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}))\Bigr{]}.$
(D.100)

Then, the following theorem holds.

######  Theorem D.9.

Assume that Assumptions D.1, C.3 and C.4 hold. Also assume that
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})\in\tilde{\mathcal{Y}}^{(n)}$
for any $s\in\\{0,\ldots,N-1\\}$, $n\in\\{s+1,\ldots,N\\}$, iteration $t\geq
1$, realization ${\bm{\epsilon}}$, given
${\bm{y}}\in\tilde{\mathcal{Y}}^{(s)}$ and input
$({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)})$. Let $\delta\in(0,1)$ and $\xi>0$,
and define $\beta_{t}$ by D.18 and $\eta_{t}=(1+\log t)^{-1}$. Then, when the
optimization is performed using D.98, the following inequality holds with
probability at least $1-(N+1)\delta$:

$G({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})-G(\hat{\bm{x}}^{(1)}_{G,T},\ldots,\hat{\bm{x}}^{(N)}_{G,T})<\xi,$
(D.101)

where $T$ is the smallest positive integer satisfying $T\in N\mathbb{Z}_{\geq
0}$ and

$\frac{N}{T}\sqrt{C^{2(N+2)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}<\xi.$
(D.102)

Here, $C_{6,t}$, $C_{7}$ and $C_{8}$ are given by
$C_{2,t}=4NM^{2}_{\text{prod}}M_{\text{sum}}C^{2N-2}_{0,t}C^{N}_{1},\
C_{3,t}=NC_{2,t}^{N},\
C_{6,t}=2C_{3,t}\eta^{-1}_{t}(2\beta^{1/2}_{t}+2),C_{5}=(1+L_{f})^{N}M_{\text{prod}}M_{\text{sum}},\
C_{7}=2\left(8C_{5}\log\frac{5C_{5}}{\delta}N\right)^{2},\
C_{8}=\frac{4M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}.$

In order to prove Theorem D.9, we give two lemmas.

######  Lemma D.10.

Assume that the same condition as in Theorem D.4 holds. Then, the following
holds with probability at least $1-\delta$:

$\displaystyle\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
$\displaystyle\leq
C_{3,t}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})+C_{3,t}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{{\bm{\epsilon}},i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)}).$
(D.103)

###### Proof.

By using the same argument as in Lemma C.13, we have Lemma D.10. ∎

######  Lemma D.11.

Assume that the same condition as in Theorem D.4 holds. Then, the following
inequality holds:

$\eta_{t}\tilde{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\leq\tilde{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\leq(2\beta^{1/2}_{t}+\eta_{t})\tilde{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}).$
(D.104)

###### Proof.

By using the same argument as in Lemma C.14, we get Lemma D.11. ∎

By using these lemmas, we prove Theorem D.9.

###### Proof.

From Lemma D.11, the following holds:

$\displaystyle\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
$\displaystyle\leq(2\beta^{1/2}_{t}+\eta_{t})\tilde{b}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}~{}{\bm{0}})$
(D.105)
$\displaystyle=(2\beta^{1/2}_{t}+\eta_{t})\mathbb{E}_{\bm{\epsilon}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})].$
(D.106)

In addition, for the positive integer $NK\equiv T\in N\mathbb{Z}_{\geq 0}$
satisfying the theorem’s inequality,
$\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$ satisfies that

$\displaystyle\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
$\displaystyle\leq(2\beta^{1/2}_{T}+2)\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{\bm{\epsilon}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})]$
(D.107) $\displaystyle=(2\beta^{1/2}_{T}+2)\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(1)}}[\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}\Bigl{[}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]\Bigr{]}.$
(D.108)

Here, the conditional expectation
$\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]$
is a non-negative random variable with respect to ${\bm{\epsilon}}^{(1)}$, and
satisfies that

$\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]\leq(1+L_{f})^{N}M_{\text{prod}}M_{\text{sum}}=C_{5},$
(D.109)

where the inequality is given by $k^{(n)}(\cdot,\cdot)\leq 1$. Hence, from
Lemma 3 of Kirschner and Krause, (2018), the following holds with probability
at least $1-\delta$:

$\displaystyle\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(1)}}[\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]]$
(D.110) $\displaystyle\leq
4C_{5}\log\frac{1}{\delta}+8C_{5}\log(4C_{5})+1+2\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}_{t}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}_{t}]$
(D.111) $\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}_{t}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}_{t}].$
(D.112)

Moreover, from Lemma D.10, with probability at least $1-\delta$ the following
inequality holds uniformly:

$\displaystyle\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}_{t}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}_{t}]$
(D.113)
$\displaystyle\leq\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}_{t}}[C_{3,T}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}(\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{y}}^{(1)}_{t+1})]+C_{3,T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1}).$
(D.114)

Therefore, it follows that

$\displaystyle\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(1)}}[\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]]$
(D.115) $\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}_{t}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}_{t}]$
(D.116) $\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2C_{3,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+2C_{3,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}_{t}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}(\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{y}}^{(1)}_{t+1})]$
(D.117) $\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2C_{3,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+2C_{3,T}\eta^{-1}_{T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\eta_{t}\tilde{b}^{(2)}_{t}(\hat{\bm{x}}^{(2)}_{t+1}|{\bm{y}}^{(1)}_{t+1})$
(D.118) $\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2C_{3,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+2C_{3,T}\eta^{-1}_{T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(2)}_{t}(\hat{\bm{x}}^{(2)}_{t+1}|{\bm{y}}^{(1)}_{t+1})$
(D.119) $\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2C_{3,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+2C_{3,T}\eta^{-1}_{T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(2)}_{t}({\bm{x}}^{(2)}_{t+2}|{\bm{y}}^{(1)}_{t+1})$ (D.120)
$\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2C_{3,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+2C_{3,T}\eta^{-1}_{T}(2\beta^{1/2}_{t}+2)\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\tilde{b}^{(2)}_{t}({\bm{x}}^{(2)}_{t+2}|{\bm{y}}^{(1)}_{t+1})$ (D.121)
$\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+2C_{3,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+2C_{3,T}\eta^{-1}_{T}(2\beta^{1/2}_{t}+2)$
(D.122) $\displaystyle\qquad\cdot\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(2)}}\Bigl{[}\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}^{(1)}_{t+1},{\bm{\epsilon}}^{(2)}}\Bigl{[}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(2)}_{t+2},\hat{\bm{x}}^{(3)}_{t+2},\ldots,\hat{\bm{x}}^{(N)}_{t+2}|{\bm{y}}^{(1)}_{t+1})|{\bm{\epsilon}}^{(2)}\Bigr{]}\Bigr{]}$
(D.123) $\displaystyle\leq 8C_{5}\log\frac{5C_{5}}{\delta}+C_{6,T}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{\epsilon}},1,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})$
(D.124) $\displaystyle\quad+C_{6,T}\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(2)}}\Bigl{[}\mathbb{E}_{{\bm{\epsilon}}|{\bm{y}}^{(1)}_{t+1},{\bm{\epsilon}}^{(2)}}\Bigl{[}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(2)}_{t+2},\hat{\bm{x}}^{(3)}_{t+2},\ldots,\hat{\bm{x}}^{(N)}_{t+2}|{\bm{y}}^{(1)}_{t+1})|{\bm{\epsilon}}^{(2)}\Bigr{]}\Bigr{]}.$
(D.125)

By repeating this process, with probability at least $1-(N+1)\delta$, the
following holds:

$\displaystyle\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(1)}}[\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]]$
(D.126) $\displaystyle\leq
8C_{5}\log\frac{5C_{5}}{\delta}NC_{6,T}^{N}+C_{6,T}^{N}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{{\bm{\epsilon}},i,t}({\bm{y}}^{(n-1)}_{t+n-1},{\bm{x}}^{(n)}_{t+n}).$
(D.127)

By combining this and

$\displaystyle\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
$\displaystyle\leq(2\beta^{1/2}_{T}+2)\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(1)}}[\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}\Bigl{[}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]\Bigr{]}$
(D.128) $\displaystyle\leq C_{6,T}\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\mathbb{E}_{{\bm{\epsilon}}^{(1)}}[\mathbb{E}_{{\bm{\epsilon}}|{\bm{\epsilon}}^{(1)}}\Bigl{[}\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,t}({\bm{x}}^{(1)}_{t+1},\hat{\bm{x}}^{(2)}_{t+1},\ldots,\hat{\bm{x}}^{(N)}_{t+1}|{\bm{0}})|{\bm{\epsilon}}^{(1)}]\Bigr{]},$
(D.129)

we get

$\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})\leq
8C_{5}\log\frac{5C_{5}}{\delta}NC_{6,T}^{N+1}+C_{6,T}^{N+1}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{{\bm{\epsilon}},i,t}({\bm{y}}^{(n-1)}_{t+n-1},{\bm{x}}^{(n)}_{t+n}).$
(D.130)

Thus, noting that $(a+b)^{2}\leq 2a^{2}+2b^{2}$, using the Cauchy–Schwarz
inequality and $\tilde{\gamma}_{T}$ we have

$\displaystyle\left(\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})\right)^{2}$
$\displaystyle\leq
2\left(8C_{5}\log\frac{5C_{5}}{\delta}NC_{6,T}^{N+1}\right)^{2}+2C^{2(N+1)}_{6,T}TM_{\text{sum}}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)2}_{{\bm{\epsilon}},i,t}({\bm{y}}^{(n-1)}_{t+n-1},{\bm{x}}^{(n)}_{t+n})$
(D.131) $\displaystyle\leq
2\left(8C_{5}\log\frac{5C_{5}}{\delta}NC_{6,T}^{N+1}\right)^{2}+2C^{2(N+1)}_{6,T}TM_{\text{sum}}\frac{2M_{\text{sum}}\tilde{\gamma}_{T}}{\log(1+\sigma^{-2})}$
(D.132) $\displaystyle=C^{2(N+1)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T}).$
(D.133)

This implies that

$\displaystyle\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})\leq\sqrt{C^{2(N+1)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}.$
(D.134)

Furthermore, letting $\tilde{t}=\operatorname*{arg\,max}_{t\in
N\mathbb{Z}_{\geq 0},t\leq
T}\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$ we get

$\displaystyle
K\tilde{c}^{(1)}_{\tilde{t}}({\bm{x}}^{(1)}_{\tilde{t}+1}|{\bm{0}})$
$\displaystyle\leq\sum_{t\in N\mathbb{Z}_{\geq
0}}^{T}\tilde{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$ (D.135)
$\displaystyle\leq\sqrt{C^{2(N+1)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}.$
(D.136)

By dividing both sides by $K$, we obtain

$\displaystyle\tilde{c}^{(1)}_{\tilde{t}}({\bm{x}}^{(1)}_{\tilde{t}+1}|{\bm{0}})$
$\displaystyle\leq
K^{-1}\sqrt{C^{2(N+1)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}$ (D.137)
$\displaystyle=\frac{N}{T}\sqrt{C^{2(N+1)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}.$
(D.138)

Finally, from the definition of the estimated solution and CIs, we get

$\displaystyle G({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})$
$\displaystyle\leq\min_{t\in N\mathbb{Z}_{\geq 0},t\leq
T}\mathrm{UCB}^{(G)}_{t}({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})$
$\displaystyle\leq\mathrm{UCB}^{(G)}_{\tilde{t}}({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast}),$
(D.139) $\displaystyle
G(\hat{\bm{x}}^{(1)}_{G,T},\ldots,\hat{\bm{x}}^{(N)}_{G,T})$
$\displaystyle\geq\max_{t\in N\mathbb{Z}_{\geq 0},t\leq
T}\mathrm{LCB}^{(G)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
$\displaystyle\geq\mathrm{LCB}^{(G)}_{\tilde{t}}({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast}).$
(D.140)

Thus, it follows that

$\displaystyle
G({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})-G(\hat{\bm{x}}^{(1)}_{G,T},\ldots,\hat{\bm{x}}^{(N)}_{G,T})$
$\displaystyle\leq
2\beta^{1/2}_{T}\mathbb{E}_{\bm{\epsilon}}[\tilde{\sigma}^{(N)}_{{\bm{\epsilon}},1,\tilde{t}}({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})]$
(D.141) $\displaystyle\leq
2\beta^{1/2}_{T}\tilde{b}^{(1)}_{\tilde{t}}({\bm{x}}^{(1)}_{G,\ast}|{\bm{0}})$
(D.142) $\displaystyle\leq
2{\beta}^{1/2}_{T}\eta^{-1}_{\tilde{t}}\tilde{c}^{(1)}_{\tilde{t}}({\bm{x}}^{(1)}_{G,\ast}|{\bm{0}})\leq
2{\beta}^{1/2}_{T}\eta^{-1}_{T}\tilde{c}^{(1)}_{\tilde{t}}({\bm{x}}^{(1)}_{\tilde{t}+1}|{\bm{0}}).$
(D.143)

Hence, by combining this and D.138, we have

$\displaystyle
G({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})-G(\hat{\bm{x}}^{(1)}_{G,T},\ldots,\hat{\bm{x}}^{(N)}_{G,T})$
$\displaystyle\leq
2{\beta}^{1/2}_{T}\eta^{-1}_{T}\frac{N}{T}\sqrt{C^{2(N+1)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}$
(D.144) $\displaystyle\leq
C_{6,T}\frac{N}{T}\sqrt{C^{2(N+1)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}$
(D.145)
$\displaystyle=\frac{N}{T}\sqrt{C^{2(N+2)}_{6,T}(C_{7}+C_{8}T\tilde{\gamma}_{T})}<\xi.$
(D.146)

∎

###  D.4 Optimistic Improvement-based AF for the Final Stage Output

We give an optimistic improvement-based AF for $F$ under the noisy setting.
First, we define the sum of the squares of the observation noise
$\epsilon_{\text{sum}}$ as

$\epsilon_{\text{sum}}=\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\epsilon^{(n)2}_{m}.$
(D.147)

Note that $\epsilon_{\text{sum}}$ is bounded by $M_{\text{sum}}A^{2}$ under
Assumption D.1. Moreover, we assume the following assumption for
$\epsilon_{\text{sum}}$.

######  Assumption D.12.

Under Assumption D.1, there exists a positive constant $C$ such that
$\mathbb{P}(\epsilon_{\text{sum}}<V)>CV$ for any $V$ with $0<V\leq
M_{\text{sum}}A^{2}$.

For example, if $\epsilon_{\text{sum}}$ is a discrete random variable with
$\mathbb{P}(\epsilon_{\text{sum}}=0)>0$, then Assumption D.12 holds.
Similarly, if $\epsilon_{\text{sum}}$ is a continuous random variable whose
probability density function $p_{\epsilon_{\text{sum}}}(x)$ satisfies
$p_{\epsilon_{\text{sum}}}(x)>K>0$, where $x$ is an arbitrary element of some
interval $[0,U]$. Then, Assumption D.12 also holds. Thus, Assumption D.12
guarantees that $\epsilon_{\text{sum}}$ can take values within an arbitrary
neighborhood of zero. Next, we define the variable $C_{9,t}$ as

$C_{9,t}=2\beta^{1/2}_{t}\eta^{-1}_{t}(2\beta^{1/2}_{t}+2)^{N}C^{N}_{3,t}\eta^{-N}_{t},$
(D.148)

where $\eta_{t}=(1+\log t)^{-1}$. Then, we assume the following assumption.

######  Assumption D.13.

For any $T\geq 1$, $C_{9,t}$ satisfies that

$\sum_{t=T}^{t^{\prime}}C^{-2}_{9,t}\to\infty\quad(\text{as}\
t^{\prime}\to\infty).$ (D.149)

Note that $C_{9,t}$ is a polynomial function on $\beta_{t}$. Furthermore, by
considering the definition of $\beta_{t}$, the closed form of the mutual
information, and $\tilde{\gamma}_{t}$, we can show that the order of $C_{9,t}$
is expressed as the polynomial function of $\tilde{\gamma}_{t}$. Here, under
certain conditions, it is known that the order of $\tilde{\gamma}_{t}$ for
commonly used kernels such as Gaussian kernels and linear kernels is a
logarithmic order Srinivas et al., (2010). Then, Assumption D.13 holds if we
use such kernels. Under this setting, we propose an algorithm to the regret
$r^{(\text{S})}_{F,T}$.

First, for each $t\geq 1$, we define the estimated solution
$\hat{\bm{x}}^{(1)}_{F,t},\dots,\hat{\bm{x}}^{(N)}_{F,t}$ as follows:

$\hat{\bm{x}}^{(1)}_{F,t},\dots,\hat{\bm{x}}^{(N)}_{F,t}=\operatorname*{arg\,max}_{\begin{subarray}{c}1\leq
t^{\prime}\leq t\\\
({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X}\end{subarray}}(\tilde{z}^{(N)}_{{\bm{0}},1,t^{\prime}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})-\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t^{\prime}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})).$
(D.150)

Then, we give the optimistic improvement-based AF. For any $n\in[N]$, given an
observation $\bm{y}^{(n-1)}$ of stage $n-1$, optimistic maximum estimator
$\widehat{\mathrm{UCB}}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$ w.r.t.
$\bm{x}^{(n)}$ is defined as:

$\displaystyle\widehat{\mathrm{UCB}}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$
(D.151)
$\displaystyle=\max_{({\bm{x}}^{(n+1)},\ldots,{\bm{x}}^{(N)})}\Bigl{(}\tilde{{z}}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})+\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})\Bigr{)},$
(D.152)

where the max operator is not needed when $n=N$. Similarly, pessimistic
maximum estimator $\widehat{\mathrm{LCB}}^{(F)}_{t}({\bm{y}}^{(n-1)})$ under
given an observation $\bm{y}^{(n-1)}$ is defined as follows:

$\displaystyle\widehat{\mathrm{LCB}}^{(F)}_{t}({\bm{y}}^{(n-1)})$ (D.153)
$\displaystyle=\max_{({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)})}\Bigl{(}\tilde{z}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})-\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})\Bigr{)}.$
(D.154)

Moreover, pessimistic maximum estimator of $F$ is given by:

$\hat{Q}_{T}=\max_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})}\Bigl{(}\tilde{z}^{(N)}_{{\bm{0}},1,T}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})-\beta^{1/2}_{t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,T}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\Bigr{)}.$
(D.155)

Then, we define the optimistic improvement with w.r.t. ${\bm{x}}^{(n)}$ as:

$\hat{a}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\widehat{\mathrm{UCB}}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})-\max\\{\widehat{\mathrm{LCB}}^{(F)}_{t}({\bm{y}}^{(n-1)}),\hat{Q}_{t+n-1}\\}.$
(D.156)

Furthermore, we define the maximum uncertainty w.r.t.
$({\bm{y}}^{(n-1)},{\bm{x}}^{(n)})$ as:

$\hat{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\max_{({\bm{x}}^{(n+1)},\ldots,{\bm{x}}^{(N)})}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)}).$
(D.157)

From D.156 and D.157, the AF
$\hat{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$ for this setting is given
by:

$\hat{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\max\\{\hat{a}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}),\eta_{t}\hat{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\\},$
(D.158)

where $\eta_{t}$ is some learning rate tends to zero. Using this AF
$\hat{c}^{(n)}_{t}$, we propose the following selection rule:

$\displaystyle{\bm{x}}^{(n)}_{t+n}$
$\displaystyle=\operatorname*{arg\,max}_{{\bm{x}}^{(n)}\in\mathcal{X}^{(n)}}\hat{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}_{t+n-1}),$
(D.159) $\displaystyle{\bm{y}}^{(n)}_{t+n}$
$\displaystyle={\bm{f}}^{(n)}({\bm{y}}^{(n-1)}_{t+n-1},{\bm{x}}^{(n)}_{t+n})+{\bm{\epsilon}}^{(n)}_{t+n},$
(D.160)

where ${\bm{y}}^{(0)}_{t}={\bm{0}}$. Then, the following theorem holds.

######  Theorem D.14.

Assume that Assumptions D.1, C.3, C.4, D.12 and D.13 hold. Also assume that
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})\in\tilde{\mathcal{Y}}^{(n)}$
for any $s\in\\{0,\ldots,N-1\\}$, $n\in\\{s+1,\ldots,N\\}$, iteration $t\geq
1$, realization ${\bm{\epsilon}}$, given
${\bm{y}}\in\tilde{\mathcal{Y}}^{(s)}$ and input
$({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)})$. Let $\delta\in(0,1)$ and $\xi>0$,
and define $\beta_{t}$ by D.18 and $\eta_{t}=(1+\log t)^{-1}$. Then, there
exists a sequence $0=T_{0}<T_{1}<T_{2}<\cdots$ such that $T_{k}\in
N\mathbb{Z}_{\geq 0}$ and

$\mathbb{P}(\exists t\in N\mathbb{Z}_{\geq 0}\ \text{s.t.}\ T_{k-1}\leq t\leq
T_{k},\
2C^{2}_{9,t}M_{\text{sum}}\epsilon_{\text{sum},t}<\xi^{2}/2)>1-\frac{6\delta}{\pi^{2}k^{2}}.$
(D.161)

Moreover, when the optimization is performed using D.160, the following
inequality holds with probability at least $1-2\delta$:

$F({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})-F(\hat{\bm{x}}^{(1)}_{F,T_{K}},\ldots,\hat{\bm{x}}^{(N)}_{F,T_{K}})<\xi,$
(D.162)

where $T_{K}$ is an element of the sequence $\\{T_{k}\\}_{k=0}^{\infty}$
satisfying

$\frac{4C^{2}_{9,T_{K}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\tilde{\gamma}_{T_{K}}K^{-1}<\xi^{2}/2.$
(D.163)

In order to prove Theorem D.14, we first give four lemmas.

######  Lemma D.15.

Assume that the same condition as in Theorem D.14 holds. Then, for any
$s\in\\{1,\ldots,N-1\\}$, $n\in\\{s+1,\ldots,N\\}$, $m\in[M^{(n)}]$, iteration
$t\geq 1$, realization $\bm{\epsilon}$ and input
${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}$, the following holds with probability
at least $1-\delta$:

$\displaystyle|\sigma^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s)}_{\bm{\epsilon}}),{\bm{x}}^{(n)})|$
(D.164) $\displaystyle\leq
2M_{\text{prod}}C^{N-1}_{0,t}\sum_{p=0}^{n-s-1}\sum_{i=1}^{M^{(n-1-p)}}\sigma^{(n-1-p)}_{i,t}\Bigl{(}\tilde{\bm{z}}^{(n-2-p)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2-p)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)}),{\bm{x}}^{(n-1-p)}\Bigr{)}$
(D.165)
$\displaystyle\quad+2M_{\text{prod}}C^{N-1}_{0,t}\sum_{q=1}^{M^{(s)}}|\epsilon^{(s)}_{q}|.$
(D.166)

###### Proof.

By using the same argument as in the proof of Lemma C.11, the following holds
with probability at least $1-\delta$:

$\displaystyle|\sigma^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}(\tilde{\bm{z}}^{(n-1)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}_{\bm{\epsilon}}^{(s)}),{\bm{x}}^{(n)})|$
(D.167) $\displaystyle\leq
2\beta^{1/2}_{t}L_{\sigma}\sum_{j=1}^{M^{(n-1)}}\sigma^{(n-1)}_{j,t}\Bigl{(}\tilde{\bm{z}}^{(n-2)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}_{\bm{\epsilon}}^{(s)}),{\bm{x}}^{(n-1)}\Bigr{)}+L_{\sigma}M^{(n-1)}(L_{f}+\beta^{1/2}_{t}L_{\sigma})$
(D.168)
$\displaystyle\quad\cdot\sum_{i=1}^{M^{(n-2)}}\Bigl{[}|\tilde{z}^{(n-2)}_{{\bm{0}},i,t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)})-\tilde{z}^{(n-2)}_{{\bm{0}},i,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})|\Bigr{]}$
(D.169) $\displaystyle\leq
2\beta^{1/2}_{t}L_{\sigma}\sum_{j=1}^{M^{(n-1)}}\sigma^{(n-1)}_{j,t}(\tilde{\bm{z}}^{(n-2)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(n-1)})$
(D.170)
$\displaystyle\quad+2\beta^{1/2}_{t}L_{\sigma}M^{(n-1)}(L_{f}+\beta^{1/2}_{t}L_{\sigma})\sum_{i=1}^{M^{(n-2)}}\sigma^{(n-2)}_{i,t}(\tilde{\bm{z}}^{(n-3)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-3)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)}),{\bm{x}}^{(n-2)})$
(D.171)
$\displaystyle\quad+L_{\sigma}M^{(n-1)}M^{(n-2)}(L_{f}+\beta^{1/2}_{t}L_{\sigma})^{2}$
(D.172)
$\displaystyle\quad\cdot\sum_{q=1}^{M^{(n-3)}}\Bigl{[}|\tilde{z}^{(n-3)}_{{\bm{0}},q,t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-3)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)})-\tilde{z}^{(n-3)}_{{\bm{0}},q,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-3)}|{\bm{z}}_{\bm{\epsilon}}^{(s)})|\Bigr{]}$
(D.173) $\displaystyle\leq$ (D.174) $\displaystyle\vdots$ (D.175)
$\displaystyle\leq
2\beta^{1/2}_{t}L_{\sigma}M_{\text{prod}}(L_{f}+\beta^{1/2}_{t}L_{\sigma}+1)^{N-2}$
(D.176)
$\displaystyle\quad\cdot\sum_{p=0}^{n-s-2}\sum_{i=1}^{M^{(n-1-p)}}\Bigl{[}\sigma^{(n-1-p)}_{i,t}(\tilde{\bm{z}}^{(n-2-p)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2-p)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(n-1-p)})\Bigr{]}$
(D.177)
$\displaystyle\quad+2M_{\text{prod}}L_{\sigma}(L_{f}+\beta^{1/2}_{t}L_{\sigma}+1)^{N-2}\sum_{q=1}^{M^{(s)}}\Bigl{[}|\mu^{(s)}_{q,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})-f^{(s)}_{q}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})-\epsilon^{(s)}_{q}|\Bigr{]}$
(D.178) $\displaystyle\leq
2M_{\text{prod}}(L_{f}+\beta^{1/2}_{t}L_{\sigma}+1)^{N-1}$ (D.179)
$\displaystyle\quad\cdot\sum_{p=0}^{n-s-1}\sum_{i=1}^{M^{(n-1-p)}}\Bigl{[}\sigma^{(n-1-p)}_{i,t}(\tilde{\bm{z}}^{(n-2-p)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2-p)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(n-1-p)})\Bigr{]}$
(D.180)
$\displaystyle\quad+2M_{\text{prod}}(L_{f}+\beta^{1/2}_{t}L_{\sigma}+1)^{N-1}\sum_{q=1}^{M^{(s)}}|\epsilon^{(s)}_{q}|$
(D.181)
$\displaystyle=2M_{\text{prod}}C_{0,t}^{N-1}\sum_{p=0}^{n-s-1}\sum_{i=1}^{M^{(n-1-p)}}\Bigl{[}\sigma^{(n-1-p)}_{i,t}(\tilde{\bm{z}}^{(n-2-p)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2-p)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(n-1-p)})\Bigr{]}$
(D.182)
$\displaystyle\quad+2M_{\text{prod}}C_{0,t}^{N-1}\sum_{q=1}^{M^{(s)}}|\epsilon^{(s)}_{q}|.$
(D.183)

∎

######  Lemma D.16.

Assume that the same condition as in Theorem D.14 holds. Then, for any
$s\in\\{1,\ldots,N-1\\}$, $j\geq 0$ with $s+j\leq N$, iteration $t\geq 1$,
realization $\bm{\epsilon}$ and input ${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}$,
the following holds with probability at least $1-\delta$:

$\displaystyle\tilde{\sigma}^{(N-j)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.184) $\displaystyle\leq
C_{2,t}\tilde{\sigma}^{(N-j)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})+C_{2,t}\tilde{\sigma}^{(N-j-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j-1)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.185)
$\displaystyle\quad+C_{2,t}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})+C_{2,t}\sum_{i=1}^{M^{(s)}}|\epsilon^{(s)}_{i}|,$
(D.186)

where

$\displaystyle\tilde{\sigma}^{(N-j)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.187)
$\displaystyle=\sum_{p=j}^{N-s}\prod_{q=1}^{p}M^{(N-q+1)}L_{f}^{p}\sum_{i=1}^{M^{(N-p)}}\Bigl{[}\sigma^{(N-p)}_{i,t}(\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(N-p)})\Bigr{]}.$
(D.188)

###### Proof.

From the definition of
$\tilde{\sigma}^{(N-j)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$,
the following inequality holds with probability at least $1-\delta$:

$\displaystyle\tilde{\sigma}^{(N-j)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.189)
$\displaystyle=\sum_{p=j}^{N-s}\prod_{q=1}^{p}M^{(N-q+1)}L_{f}^{p}\sum_{i=1}^{M^{(N-p)}}\Bigl{[}\sigma^{(N-p)}_{i,t}(\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(N-p)})\Bigr{]}$
(D.190) $\displaystyle\leq
M_{\text{prod}}C^{N-1}_{0}\sum_{p=j}^{N-s}\sum_{i=1}^{M^{(N-p)}}\Bigl{[}\sigma^{(N-p)}_{i,t}(\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(N-p)})\Bigr{]}$
(D.191)
$\displaystyle=M_{\text{prod}}C^{N-1}_{0}\sum_{p=j}^{N-s-1}\sum_{i=1}^{M^{(N-p)}}\Bigl{[}\sigma^{(N-p)}_{i,t}(\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}_{\bm{\epsilon}}),{\bm{x}}^{(N-p)})\Bigr{]}$
(D.192)
$\displaystyle\quad+M_{\text{prod}}C^{N-1}_{0}\sum_{p=j}^{N-s-1}\sum_{i=1}^{M^{(N-p)}}\Bigl{[}\left(\sigma^{(N-p)}_{i,t}\Bigl{(}\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}}),{\bm{x}}^{(N-p)}\Bigr{)}\Bigr{]}\right.$
(D.193)
$\displaystyle\quad\left.-\sigma^{(N-p)}_{i,t}(\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}_{\bm{\epsilon}}),{\bm{x}}^{(N-p)})\right)+M_{\text{prod}}C^{N-1}_{0}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)}).$
(D.194)

Hence, from Lemma D.15, it follows that

$\displaystyle|\sigma^{(N-p)}_{i,t}(\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s:N-p-1)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)}),{\bm{x}}^{(N-p)})-\sigma^{(N-p)}_{i,t}(\tilde{\bm{z}}^{(N-p-1)}_{{\bm{0}},t}({\bm{x}}^{(s+1:N-p-1)}|{\bm{z}}_{\bm{\epsilon}}^{(s)}),{\bm{x}}^{(N-p)})|$
(D.195) $\displaystyle\leq
2M_{\text{prod}}C^{N-1}_{0}\sum_{r=0}^{N-p-s-1}\sum_{j=1}^{M^{(N-p-1-r)}}\Bigl{[}\sigma^{(N-p-1-r)}_{j,t}\Bigl{(}\tilde{\bm{z}}^{(N-p-2-r)}_{{\bm{0}},t}({\bm{x}}^{(s:N-p-2-r)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)}),{\bm{x}}^{(N-p-1-r)}\Bigr{)}\Bigr{]}$
(D.196)
$\displaystyle\quad+2M_{\text{prod}}C^{N-1}_{0}\sum_{q=1}^{M^{(s)}}|\epsilon^{(s)}_{q}|.$
(D.197)

Hence, using the same argument as in the proof of Lemma C.12, we have the
desired result. ∎

######  Lemma D.17.

Assume that the same condition as in Theorem D.14 holds. Then, for any
$s\in\\{1,\ldots,N-1\\}$, iteration $t\geq 1$, realization $\bm{\epsilon}$ and
input ${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}$, the following holds with
probability at least $1-\delta$:

$\displaystyle\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}_{\bm{\epsilon}}^{(s-1)})$
(D.198) $\displaystyle\quad\leq
C_{3,t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})+C_{3,t}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})+C_{3,t}\sum_{i=1}^{M^{(s)}}|\epsilon^{(s)}_{i}|.$
(D.199)

###### Proof.

By repeating Lemma D.16, the following holds with probability at least
$1-\delta$:

$\displaystyle\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.200)
$\displaystyle=\tilde{\sigma}^{(N-0)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-0)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.201) $\displaystyle\leq
C_{2,t}\tilde{\sigma}^{(N-0)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-0)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})+C_{2,t}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})+C_{2,t}\sum_{i=1}^{M^{(s)}}|\epsilon^{(s)}_{i}|$
(D.202)
$\displaystyle\quad+C_{2,t}\tilde{\sigma}^{(N-1)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-1)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.203) $\displaystyle\leq
C_{2,t}\tilde{\sigma}^{(N-0)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-0)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})+C_{2,t}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})+C_{2,t}\sum_{i=1}^{M^{(s)}}|\epsilon^{(s)}_{i}|$
(D.204)
$\displaystyle\quad+C^{2}_{2,t}\tilde{\sigma}^{(N-1)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-1)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})+C^{2}_{2,t}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})+C^{2}_{2,t}\sum_{i=1}^{M^{(s)}}|\epsilon^{(s)}_{i}|$
(D.205)
$\displaystyle\quad+C^{2}_{2,t}\tilde{\sigma}^{(N-2)}_{{\bm{0}},t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-2)}|{\bm{z}}^{(s-1)}_{\bm{\epsilon}})$
(D.206) $\displaystyle\leq$ (D.207) $\displaystyle\vdots$ (D.208)
$\displaystyle\leq(C_{2,t}+C^{2}_{2,t}+\cdots+C^{N}_{2,t})\tilde{\sigma}^{(N-0)}_{{\bm{0}},t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-0)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})$
(D.209)
$\displaystyle\quad+(C_{2,t}+C^{2}_{2,t}+\cdots+C^{N}_{2,t})\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})+(C_{2,t}+C^{2}_{2,t}+\cdots+C^{N}_{2,t})\sum_{i=1}^{M^{(s)}}|\epsilon^{(s)}_{i}|$
(D.210) $\displaystyle\leq
NC^{N}_{2,t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}^{(s)}_{\bm{\epsilon}})+NC^{N}_{2,t}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)}_{\bm{\epsilon}},{\bm{x}}^{(s)})+NC^{N}_{2,t}\sum_{i=1}^{M^{(s)}}|\epsilon^{(s)}_{i}|.$
(D.211)

∎

######  Lemma D.18.

Assume that the same condition as in Theorem D.14 holds. Then, for any
$n\in[N]$, iteration $t\geq 1$,
${\bm{y}}^{(n-1)}\in\tilde{\mathcal{Y}}^{(n-1)}$ and input
${\bm{x}}^{(n)}\in\mathcal{X}^{(n)}$, the following holds:

$\eta_{t}\hat{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\leq\hat{c}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\leq(2\beta^{1/2}_{t}+\eta_{t})\hat{b}^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}).$
(D.212)

###### Proof.

By using the same argument as in the proof of Lemma C.14, we get Lemma D.18. ∎

Using these lemmas we prove Theorem D.14.

###### Proof.

Let $t\in N\mathbb{Z}_{\geq 0}$. Then, from Lemma D.18, ${\bm{x}}^{(1)}_{t+1}$
satisfies that

$\hat{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})\leq(2\beta^{1/2}_{t}+\eta_{t})\hat{b}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})=(2\beta^{1/2}_{t}+\eta_{t})\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(1)}_{t+1},\tilde{\bm{x}}^{(2)},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{0}}).$
(D.213)

In addition, from D.213 and Lemma D.17, using the same argument as in the
proof of Theorem C.10, with probability at least $1-\delta$,
$\hat{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$ can be bounded as follows:

$\displaystyle\hat{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
$\displaystyle\leq(2\beta^{1/2}_{t}+\eta_{t})C_{3,t}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{0}},i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}_{t}+\eta_{t})C_{3,t}\sum_{i=1}^{M^{(1)}}|\epsilon^{(1)}_{i}|$
(D.214)
$\displaystyle\qquad+(2\beta^{1/2}_{t}+\eta_{t})C_{3,t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}(\tilde{\bm{x}}^{(2)},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(1)}_{t+1})$
(D.215)
$\displaystyle\leq(2\beta^{1/2}_{t}+\eta_{t})C_{3,t}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{{\bm{0}},i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}_{t}+\eta_{t})C_{3,t}\sum_{i=1}^{M^{(1)}}|\epsilon^{(1)}_{i}|$
(D.216)
$\displaystyle\qquad+(2\beta^{1/2}_{t}+\eta_{t})^{2}C_{3,t}\eta^{-1}_{t}\tilde{\sigma}^{(N)}_{{\bm{0}},1,t}({\bm{x}}^{(2)}_{t+2},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(1)}_{t+1}).$
(D.217)

By using Lemma D.17 again, it follows that

$\displaystyle\hat{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
$\displaystyle\leq(2\beta^{1/2}_{t}+\eta_{t}+1)^{N}C^{N}_{3,t}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{{\bm{0}},i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})$
(D.218)
$\displaystyle\qquad+(2\beta^{1/2}_{t}+\eta_{t}+1)^{N}C^{N}_{3,t}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}|\epsilon^{(n)}_{i}|$
(D.219)
$\displaystyle\leq(2\beta^{1/2}_{t}+1+1)^{N}C^{N}_{3,t}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{{\bm{0}},i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})$
(D.220)
$\displaystyle\qquad+(2\beta^{1/2}_{t}+1+1)^{N}C^{N}_{3,t}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}|\epsilon^{(n)}_{i}|.$
(D.221)

Thus, multiplying both sides by $2\beta^{1/2}_{t}\eta^{-1}_{t}$, we get

$\displaystyle
2\beta^{1/2}_{t}\eta^{-1}_{t}\hat{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
$\displaystyle\leq
2\beta^{1/2}_{t}\eta^{-1}_{t}(2\beta^{1/2}_{t}+2)^{N}C^{N}_{3,t}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{{\bm{0}},i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})$
(D.222)
$\displaystyle\qquad+2\beta^{1/2}_{t}\eta^{-1}_{t}(2\beta^{1/2}_{t}+2)^{N}C^{N}_{3,t}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}|\epsilon^{(n)}_{i}|$
(D.223)
$\displaystyle=C_{9,t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{{\bm{0}},i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})+C_{9,t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}|\epsilon^{(n)}_{i}|.$
(D.224)

Here, using $(a+b)^{2}\leq 2a^{2}+2b^{2}$ and the Cauchy–Schwarz inequality,
we obtain

$(2\beta^{1/2}_{t}\eta^{-1}_{t}\hat{c}^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}}))^{2}\leq
2C^{2}_{9,t}M_{\text{sum}}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)2}_{{\bm{0}},i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})+2C^{2}_{9,t}M_{\text{sum}}\epsilon_{\text{sum}}.$
(D.225)

Next, we show the existence of the sequence $T_{0}<T_{1}<\cdots$ satisfying

$\mathbb{P}(\exists t\in N\mathbb{Z}_{\geq 0}\ \text{s.t.}\ T_{k-1}\leq t\leq
T_{k},\
2C^{2}_{9,t}M_{\text{sum}}\epsilon_{\text{sum},t}<\xi^{2}/2)>1-\frac{6\delta}{\pi^{2}k^{2}}.$
(D.226)

From Assumption D.12, we have

$\mathbb{P}(2C^{2}_{9,t}M_{\text{sum}}\epsilon_{\text{sum},t}<\xi^{2}/2)=\mathbb{P}(\epsilon_{\text{sum},t}<M^{-1}_{\text{sum}}C^{-2}_{9,t}\xi^{2}/4)>\frac{C\xi^{2}}{4M_{\text{sum}}C^{2}_{9,t}}.$
(D.227)

This implies that

$1-\mathbb{P}(2C^{2}_{9,t}M_{\text{sum}}\epsilon_{\text{sum},t}<\xi^{2}/2)\leq
1-\frac{C\xi^{2}}{4M_{\text{sum}}C^{2}_{9,t}}.$ (D.228)

Therefore, using $1+x\leq e^{x}$ we get

$\displaystyle\prod_{q=t}^{t^{\prime}}(1-\mathbb{P}(2C^{2}_{9,q}M_{\text{sum}}\epsilon_{\text{sum},q}<\xi^{2}/2))$
$\displaystyle\leq\prod_{q=t}^{t^{\prime}}\left(1-\frac{C\xi^{2}}{4M_{\text{sum}}C^{2}_{9,q}}\right)$
(D.229)
$\displaystyle\leq\prod_{q=t}^{t^{\prime}}\exp\left(-\frac{C\xi^{2}}{4M_{\text{sum}}C^{2}_{9,q}}\right)$
(D.230)
$\displaystyle=\exp\left(-\frac{C\xi^{2}}{4M_{\text{sum}}}\sum_{q=t}^{t^{\prime}}C^{-2}_{9,q}\right).$
(D.231)

Moreover, from Assumption D.13, the right hand side of D.231 tends to zero
when $t^{\prime}\to\infty$. Thus, we can construct the sequence
$T_{1},T_{2},\ldots$ satisfying D.161. Then, with probability at least
$1-\delta$, the following holds:

$\forall k\in\mathbb{N},\ \exists\tilde{T}_{k}\quad\mathrm{s.t.}\quad
T_{k-1}\leq\tilde{T}_{k}\leq T_{k},\
2C^{2}_{9,\tilde{T}_{k}}M_{\text{sum}}\epsilon_{\text{sum},\tilde{T}_{k}}<\xi^{2}/2.$
(D.232)

On the other hand, for the positive number $K$ satisfying the theorem’s
inequality, we define

$\hat{T}=\operatorname*{arg\,min}_{1\leq k\leq
K}(2\beta^{1/2}_{\tilde{T}_{k}}\eta^{-1}_{\tilde{T}_{k}}\hat{c}^{(1)}_{\tilde{T}_{k}}({\bm{x}}^{(1)}_{{\tilde{T}_{k}}+1}|{\bm{0}}))^{2}.$
(D.233)

Then, it follows that

$\displaystyle
K(2\beta^{1/2}_{\hat{T}}\eta^{-1}_{\hat{T}}\hat{c}^{(1)}_{\hat{T}}({\bm{x}}^{(1)}_{{\hat{T}}+1}|{\bm{0}}))^{2}$
$\displaystyle\leq\sum_{k=1}^{K}(2\beta^{1/2}_{\tilde{T}_{k}}\eta^{-1}_{\tilde{T}_{k}}\hat{c}^{(1)}_{\tilde{T}_{k}}({\bm{x}}^{(1)}_{{\tilde{T}_{k}}+1}|{\bm{0}}))^{2}$
(D.234) $\displaystyle\leq
K\xi^{2}/2+2C^{2}_{9,T_{K}}M_{\text{sum}}\sum_{t=1}^{T_{K}}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)2}_{{\bm{0}},i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})$
(D.235) $\displaystyle\leq
K\xi^{2}/2+\frac{4C^{2}_{9,T_{K}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\tilde{\gamma}_{T_{K}}.$
(D.236)

By dividing both sides by $K$, we obtain

$\displaystyle(2\beta^{1/2}_{\hat{T}}\eta^{-1}_{\hat{T}}\hat{c}^{(1)}_{\hat{T}}({\bm{x}}^{(1)}_{{\hat{T}}+1}|{\bm{0}}))^{2}$
$\displaystyle\leq\xi^{2}/2+\frac{4C^{2}_{9,T_{K}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\tilde{\gamma}_{T_{K}}K^{-1}$
(D.237) $\displaystyle<\xi^{2}/2+\xi^{2}/2=\xi^{2}.$ (D.238)

This implies that

$2\beta^{1/2}_{\hat{T}}\eta^{-1}_{\hat{T}}\hat{c}^{(1)}_{\hat{T}}({\bm{x}}^{(1)}_{{\hat{T}}+1}|{\bm{0}})<\xi.$
(D.239)

Finally, from the definition of the estimated solution and CIs, $F(\cdot)$ can
be bounded as follows:

$\displaystyle F({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})$
$\displaystyle\leq\min_{t\in N\mathbb{Z}_{\geq 0},t\leq
T_{K}}\widehat{\mathrm{UCB}}^{(F)}_{t}({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})$
(D.240)
$\displaystyle\leq\widehat{\mathrm{UCB}}^{(F)}_{\hat{T}}({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast}),$
(D.241) $\displaystyle
F(\hat{\bm{x}}^{(1)}_{F,T_{K}},\ldots,\hat{\bm{x}}^{(N)}_{F,T_{K}})$
$\displaystyle\geq\max_{t\in N\mathbb{Z}_{\geq 0},t\leq
T_{K}}\widehat{\mathrm{LCB}}^{(F)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
(D.242)
$\displaystyle\geq\widehat{\mathrm{LCB}}^{(F)}_{\hat{T}}({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast}).$
(D.243)

Therefore, the following holds with probability at least $1-2\delta$:

$\displaystyle
F({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})-F(\hat{\bm{x}}^{(1)}_{F,T_{K}},\ldots,\hat{\bm{x}}^{(N)}_{F,T_{K}})$
$\displaystyle\leq
2\beta^{1/2}_{\hat{T}}\tilde{\sigma}^{(N)}_{{\bm{0}},1,\hat{T}}({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})$
(D.244) $\displaystyle\leq
2\beta^{1/2}_{\hat{T}}\hat{b}^{(1)}_{\hat{T}}({\bm{x}}^{(1)}_{F,\ast}|{\bm{0}})$
(D.245) $\displaystyle\leq
2{\beta}^{1/2}_{\hat{T}}\eta^{-1}_{\hat{T}}\hat{c}^{(1)}_{\hat{T}}({\bm{x}}^{(1)}_{F,\ast}|{\bm{0}})\leq
2{\beta}^{1/2}_{\hat{T}}\eta^{-1}_{\hat{T}}\hat{c}^{(1)}_{\hat{T}}({\bm{x}}^{(1)}_{\hat{T}+1}|{\bm{0}}).$
(D.246)

Hence, by substituting D.239 into D.246, we have Theorem D.14. ∎

##  E Sufficient Conditions and Modifications for the Proposed Method

In this section, we consider theorem’s conditions and its modifications.
First, in the noiseless setting, we assume that
$\tilde{\bm{\mu}}_{t}^{(m)}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(m)}|{\bm{y}}^{(n-1)})\in\mathcal{Y}^{(m)}$
to construct the valid CI . For this assumption, the following sufficient
condition exists.

######  Theorem E.1.

Assume that each $\mathcal{X}^{(n)}$ is a compact set, and each observation is
noiseless. Also assume that each $f^{(n)}_{m}$ is a function defined on
$[-2B_{n-1},2B_{n-1}]^{M^{(n-1)}}\times\mathcal{X}^{(n)}$ and satisfies
$f^{(n)}_{m}\in\mathcal{H}_{k^{(n)}}$, where $B_{n}$ is some positive constant
satisfying $\|f^{(n)}_{m}\|_{\mathcal{H}_{k^{(n)}}}\leq B_{n}$ and $B_{0}=0$.
Then,
$\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in[-2B_{n},2B_{n}]^{M^{(n)}}$
for any $n\in[N]$, $t\geq 1$ and ${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}$.

###### Proof.

From the reproducing property of $k^{(n)}$, noting that
$k^{(n)}({\bm{a}},{\bm{a}})\leq 1$ we have

$\displaystyle|f^{(1)}_{m}({\bm{a}})|$ $\displaystyle=|\langle
f^{(1)}_{m}(\cdot),k^{(1)}(\cdot,{\bm{a}})\rangle_{\mathcal{H}_{k^{(1)}}}|$
(E.1)
$\displaystyle\leq\|f^{(1)}_{m}\|_{\mathcal{H}_{k^{(1)}}}k^{(1)}({\bm{a}},{\bm{a}})^{1/2}\leq
B_{1}.$ (E.2)

In addition, since $\mathcal{X}^{(1)}$ is the compact set,
$[-2B_{0},2B_{0}]^{M^{(0)}}\times\mathcal{X}^{(1)}$ is also the compact set.
Hence, from C.1 the following holds for any $m\in[M^{(1)}]$, $t\geq 1$ and
$({\bm{w}},{\bm{x}})\in[-2B_{0},2B_{0}]^{M^{(0)}}\times\mathcal{X}^{(1)}$:

$\displaystyle|\mu^{(1)}_{m,t}({\bm{w}},{\bm{x}})|$
$\displaystyle=|\mu^{(1)}_{m,t}({\bm{w}},{\bm{x}})-f^{(n)}_{m}({\bm{w}},{\bm{x}})+f^{(n)}_{m}({\bm{w}},{\bm{x}})|$
(E.3)
$\displaystyle\leq|\mu^{(1)}_{m,t}({\bm{w}},{\bm{x}})-f^{(n)}_{m}({\bm{w}},{\bm{x}})|+|f^{(n)}_{m}({\bm{w}},{\bm{x}})|$
(E.4) $\displaystyle\leq B_{1}+B_{1}=2B_{1}.$ (E.5)

This implies that
${\bm{\mu}}^{(1)}_{t}({\bm{0}},{\bm{x}}^{(1)})=\tilde{\bm{\mu}}^{(1)}_{t}({\bm{x}}^{(1)})\in[-2B_{1},2B_{1}]^{M^{(1)}}$.
By repeating this process, we get

$\displaystyle{\bm{\mu}}^{(n)}_{t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})=\tilde{\bm{\mu}}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in[-2B_{n},2B_{n}]^{M^{(n)}}.$
(E.6)

∎

Theorem E.1 implies that by defining $\mathcal{Y}^{(n)}$ as
$[-2B_{n},2B_{n}]^{M^{(n)}}$ and $B=\max_{1\leq n\leq N}B_{n}$, we obtain
Assumption C.1 and
$\tilde{\bm{\mu}}_{t}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\mathcal{Y}^{(n)}$.
Similarly, under the same assumption we have
$\tilde{\bm{\mu}}_{t}^{(m)}({\bm{x}}^{(n)},\ldots,{\bm{x}}^{(m)}|{\bm{y}}^{(n-1)})\in\mathcal{Y}^{(m)}$.

Next, we consider the condition
$\tilde{\bm{z}}_{{\bm{\epsilon}},t}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\tilde{\mathcal{Y}}^{(n)}$
for the noisy observation setting. In the noisy setting, it is not easy to
give a sufficient condition for this condition to be satisfied. Nevertheless,
we can avoid this condition by modifying the definition of
$\tilde{\bm{z}}_{{\bm{\epsilon}},t}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$.
Let $\mathcal{L}=[-L,L]^{d}$ be a $d$-dimensional hypercube. For each
${\bm{a}}=(a_{1},\ldots,a_{d})\in\mathbb{R}^{d}$, suppose that
$\mathcal{P}(\mathcal{M},{\bm{a}})$ is a projection of ${\bm{a}}$ onto
$\mathcal{M}$, where the $i$-th element of
$\mathcal{P}(\mathcal{M},{\bm{a}})$, $\mathcal{P}_{i}(\mathcal{M},{\bm{a}})$,
is given by

$\mathcal{P}_{i}(\mathcal{M},{\bm{a}})=\operatorname*{arg\,min}_{l\in[-L,L]}|a_{i}-l|.$
(E.7)

Then, the following theorem holds.

######  Theorem E.2.

Assume that each $\mathcal{X}^{(n)}$ is a compact set, and each observation
noise $\epsilon^{(n)}_{m}$ is a zero mean random variable with
$-A\leq\epsilon^{(n)}_{m}\leq A$. Also assume that each $f^{(n)}_{m}$ is a
function defined on
$[-A_{n-1}-B_{n-1},A_{n-1}+B_{n-1}]^{M^{(n-1)}}\times\mathcal{X}^{(n)}$ and
satisfies $f^{(n)}_{m}\in\mathcal{H}_{k^{(n)}}$, where $A_{0}=B_{0}=0$,
$A_{n}=A$ and $B_{n}$ is some positive constant satisfying
$\|f^{(n)}_{m}\|_{\mathcal{H}_{k^{(n)}}}\leq B_{n}$. For each $t\geq 1$ and
$({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$, define

$\hat{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})=\begin{cases}{\bm{\epsilon}}^{(1)}+\mathcal{P}(\mathcal{Y}^{(1)},{\bm{\mu}}^{(1)}_{t}({\bm{0}},{\bm{x}}^{(1)}))&(n=1),\\\
{\bm{\epsilon}}^{(n)}+\mathcal{P}(\mathcal{Y}^{(n)},{\bm{\mu}}^{(n)}_{t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1:n-1)}),{\bm{x}}^{(n)}))&(n\geq
2),\end{cases}$ (E.8)

where $\mathcal{Y}^{(n)}=[-B_{n},B_{n}]^{M^{(n)}}$. Then,
$\hat{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in[-A_{n}-B_{n},A_{n}+B_{n}]^{M^{(n)}}=\tilde{\mathcal{Y}}^{(n)}$
for all $n\in[N]$, $t\geq 1$, ${\bm{\epsilon}}$ and
$({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$. Moreover, ${\bm{f}}^{(n)}$ satisfies
${\bm{f}}^{(n)}({\bm{w}},{\bm{x}})+{\bm{\epsilon}}^{(n)}\in\tilde{\mathcal{Y}}^{(n)}$
for all ${\bm{w}}\in\tilde{\mathcal{Y}}^{(n-1)}$,
${\bm{x}}\in\mathcal{X}^{(n)}$ and ${\bm{\epsilon}}^{(n)}$.

###### Proof.

From the reproducing property of $k^{(n)}(\cdot,\cdot)$, and the assumptions
$k^{(n)}(\cdot,\cdot)\leq 1$ and $\|f^{(n)}_{m}\|_{\mathcal{H}_{k^{(n)}}}\leq
B_{n}$, we have $f^{(n)}_{m}({\bm{w}},{\bm{x}})\in[-B_{n},B_{n}]$. Therefore,
noting that $-A\leq\epsilon^{(n)}_{m}\leq A$, we get ${\bm{f}}^{(n)}$
satisfies
${\bm{f}}^{(n)}({\bm{w}},{\bm{x}})+{\bm{\epsilon}}^{(n)}\in\tilde{\mathcal{Y}}^{(n)}$.
Similarly, from the definition of $\mathcal{P}(\mathcal{Y}^{(n)},{\bm{a}})$,
it follows that

$\mathcal{P}(\mathcal{Y}^{(n)},{\bm{\mu}}^{(n)}_{t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)}))\in\mathcal{Y}^{(n)}=[-B_{n},B_{n}]^{M^{(n)}}.$
(E.9)

Thus, we obtain
$\hat{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\tilde{\mathcal{Y}^{(n)}}$.
∎

In this modified
$\hat{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$,
similar results given in Theorem D.4 hold.

######  Theorem E.3.

Assume that the same condition as in Theorem E.2 holds. Given
$\delta\in(0,1)$, define $B=\max_{1\leq n\leq N}B_{n}$ and $\beta_{t}$ as in
D.18. Moreover, assume that Assumptions C.3 and C.4 hold. Then, with
probability at least $1-\delta$, the following holds for any realization of
${\bm{\epsilon}}$:

$\displaystyle|{z}^{(n)}_{{\bm{\epsilon}},m}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})-\hat{z}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})|\leq$
$\displaystyle{\beta}^{1/2}_{t}\hat{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
(E.10) $\displaystyle\quad\forall n\in[N],m\in[M^{(n)}],t\geq 1,$ (E.11)

where $\hat{z}^{(n)}_{{\bm{\epsilon}},m,t}$ is the $m$-th element of
$\hat{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}$, and
$\hat{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
is given by

$\displaystyle\hat{\sigma}^{(n)}_{{\bm{\epsilon}},m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})=$
(E.12)
$\displaystyle\quad{\sigma}^{(n)}_{m,t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\hat{\sigma}^{(n-1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),$
(E.13)

and
$\hat{\sigma}^{(1)}_{{\bm{\epsilon}},s,t}({\bm{x}}^{(1)})=\sigma^{(1)}_{s,t}({\bm{0}},{\bm{x}}^{(1)})$.

###### Proof.

For any $t\geq 1$, $n\in[N]$, $m\in[M^{(n)}]$,
${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}$ and realization of ${\bm{\epsilon}}$,
it follows that

$\displaystyle|f^{(n)}_{m}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})-{\mu}^{(n)}_{m,t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})|$
(E.14)
$\displaystyle=|f^{(n)}_{m}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})-\mathcal{P}_{m}(\mathcal{Y}^{(n)},{\bm{\mu}}^{(n)}_{t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)}))|$
(E.15)
$\displaystyle\quad+|\mathcal{P}_{m}(\mathcal{Y}^{(n)},{\bm{\mu}}^{(n)}_{t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)}))-{\mu}^{(n)}_{m,t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})|$
(E.16)
$\displaystyle\geq|f^{(n)}_{m}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})-\mathcal{P}_{m}(\mathcal{Y}^{(n)},{\bm{\mu}}^{(n)}_{t}(\hat{\bm{z}}^{(n-1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)}))|,$
(E.17)

where the first equality is derived by
$f^{(n)}_{m}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})\in\mathcal{Y}^{(n)}$
and the definition of $\mathcal{P}(\mathcal{Y}^{(n)},{\bm{a}})$. Thus, for
$i\in[M^{(2)}]$ and $({\bm{x}}^{(1)},{\bm{x}}^{(2)})$, the following
inequality holds with probability at least $1-\delta$:

$\displaystyle|z^{(2)}_{{\bm{\epsilon}},i}({\bm{x}}^{(1)},{\bm{x}}^{(2)})-\hat{z}^{(2)}_{{\bm{\epsilon}},i,t}({\bm{x}}^{(1)},{\bm{x}}^{(2)})|$
(E.18)
$\displaystyle\leq|f^{(2)}_{i}({\bm{z}}^{(1)}_{\bm{\epsilon}}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})-f^{(2)}_{i}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(1)}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})|$
(E.19)
$\displaystyle\qquad+|f^{(2)}_{i}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(1)}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})-\mathcal{P}_{i}(\mathcal{Y}^{(2)},{\bm{\mu}}^{(2)}_{t}(\hat{\bm{z}}^{(1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)}),{\bm{x}}^{(2)}))|$
(E.20) $\displaystyle\leq
L_{f}\|{\bm{f}}^{(1)}({\bm{0}},{\bm{x}}^{(1)})-\mathcal{P}(\mathcal{Y}^{(1)},{\bm{\mu}}^{(1)}_{t}({\bm{0}},{\bm{x}}^{(1)}))\|_{1}$
(E.21)
$\displaystyle\qquad+|f^{(2)}_{i}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(1)}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})-\mathcal{P}_{i}(\mathcal{Y}^{(2)},{\bm{\mu}}^{(2)}_{t}(\hat{\bm{z}}^{(1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)}),{\bm{x}}^{(2)}))|$
(E.22) $\displaystyle\leq
L_{f}\sum_{j=1}^{M^{(1)}}|{f}_{j}^{(1)}({\bm{0}},{\bm{x}}^{(1)})-\mathcal{P}_{j}(\mathcal{Y}^{(1)},{\bm{\mu}}^{(1)}_{t}({\bm{0}},{\bm{x}}^{(1)}))|$
(E.23)
$\displaystyle\qquad+|f^{(2)}_{i}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(1)}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})-\mathcal{P}_{i}(\mathcal{Y}^{(2)},{\bm{\mu}}^{(2)}_{t}(\hat{\bm{z}}^{(1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)}),{\bm{x}}^{(2)}))|$
(E.24) $\displaystyle\leq
L_{f}\sum_{j=1}^{M^{(1)}}|{f}_{j}^{(1)}({\bm{0}},{\bm{x}}^{(1)})-{\mu}^{(1)}_{j,t}({\bm{0}},{\bm{x}}^{(1)})|$
(E.25)
$\displaystyle\qquad+|f^{(2)}_{i}(\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(1)}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})-{\mu}^{(2)}_{i,t}(\hat{\bm{z}}^{(1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})|$
(E.26)
$\displaystyle\leq\beta^{1/2}_{t}\sigma^{(2)}_{i,t}(\hat{\bm{z}}^{(1)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)}),{\bm{x}}^{(2)})+L_{f}\beta^{1/2}_{t}\sum_{j=1}^{M^{(1)}}\sigma^{(1)}_{j,t}({\bm{0}},{\bm{x}}^{(1)})$
(E.27)
$\displaystyle=\beta^{1/2}_{t}\hat{\sigma}^{(2)}_{{\bm{\epsilon}},i,t}({\bm{x}}^{(1)},{\bm{x}}^{(2)}).$
(E.28)

Therefore, by repeating this process up to $n$, we get the desired inequality.
∎

We emphasize that by using the same technique as used in this proof, it can
also be shown that Theorems D.6, D.9 and D.14 hold when using
$\hat{\bm{z}}_{{\bm{\epsilon}},t}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
instead of
$\tilde{\bm{z}}_{{\bm{\epsilon}},t}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$.

Finally, we provide the sufficient condition for the Lipschitz continuity
assumption (L2).

######  Theorem E.4.

Let $k({\bm{x}},{\bm{y}}):\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ be
one of the following kernel functions:

Linear kernel:

$k({\bm{x}},{\bm{y}})=a^{2}{\bm{x}}^{\top}{\bm{y}}$, where $a$ is a positive
parameter.

Gaussian kernel:

$k({\bm{x}},{\bm{y}})=a^{2}\exp(-\|{\bm{x}}-{\bm{y}}\|^{2}/(2\rho^{2}))$,
where $a$ and $\rho$ are positive parameters.

Matérn kernel:

$k({\bm{x}},{\bm{y}})=a^{2}\frac{2^{1-\nu}}{\Gamma(\nu)}\left(\sqrt{2\nu}\frac{\|{\bm{x}}-{\bm{y}}\|}{\rho}\right)^{\nu}K_{\nu}\left(\sqrt{2\nu}\frac{\|{\bm{x}}-{\bm{y}}\|}{\rho}\right),$

where $a$ and $\rho$ are positive parameters, $\nu$ is a degree of freedom
with $\nu>1$, $\Gamma$ is the gamma function, and $K_{\nu}$ is the modified
Bessel function of the second kind.

Moreover, assume that a user-specified variance parameter $\sigma^{2}$ is
positive. Then, for any $t\geq 1$ and observed points
${\bm{x}}_{1},\ldots,{\bm{x}}_{t}$, the posterior standard deviation
$\sigma_{t}({\bm{x}})$ satisfies that

${}^{\forall}{\bm{x}},{\bm{y}}\in\mathbb{R}^{d},\
|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|\leq C\|{\bm{x}}-{\bm{y}}\|_{1},$
(E.29)

where $C$ is a positive constant given by

$\displaystyle C=\left\\{\begin{array}[]{ll}a&\text{if}\ k({\bm{x}},{\bm{y}})\
\text{is {\ the \ linear kernel}},\\\ \frac{\sqrt{2}a}{\rho}&\text{if}\
k({\bm{x}},{\bm{y}})\ \text{is {\ the \ Gaussian kernel}},\\\
\frac{\sqrt{2}a}{\rho}\sqrt{\frac{\nu}{\nu-1}}&\text{if}\
k({\bm{x}},{\bm{y}})\ \text{is {\ the \ Mat\'{e}rn
kernel}}.\end{array}\right.$ (E.33)

###### Proof.

First, we show the case of the linear kernel. Let the matrix ${\bm{X}}_{t}$ be
${\bm{X}}_{t}=({\bm{x}}_{1},\ldots,{\bm{x}}_{t})^{\top}$. Then,
$\sigma^{2}_{t}({\bm{x}})$ is given by

$\displaystyle\sigma^{2}_{t}({\bm{x}})$
$\displaystyle=a^{2}{\bm{x}}^{\top}{\bm{x}}-a^{4}{\bm{x}}^{\top}{\bm{X}}^{\top}_{t}(a^{2}{\bm{X}}_{t}{\bm{X}}^{\top}_{t}+\sigma^{2}{\bm{I}}_{t})^{-1}{\bm{X}}_{t}{\bm{x}}$
$\displaystyle=a^{2}{\bm{x}}^{\top}{\bm{x}}-a^{2}{\bm{x}}^{\top}{\bm{X}}^{\top}_{t}({\bm{X}}_{t}{\bm{X}}^{\top}_{t}+a^{-2}\sigma^{2}{\bm{I}}_{t})^{-1}{\bm{X}}_{t}{\bm{x}}$
(E.34)
$\displaystyle=a^{2}{\bm{x}}^{\top}({\bm{I}}_{d}-{\bm{X}}^{\top}_{t}({\bm{X}}_{t}{\bm{X}}^{\top}_{t}+a^{-2}\sigma^{2}{\bm{I}}_{t})^{-1}{\bm{X}}_{t}){\bm{x}}.$

The matrix ${\bm{X}}_{t}$ can be decomposed as

${\bm{X}}_{t}={\bm{H}}^{\prime}{\bm{\Lambda}}{\bm{H}}^{\top},$

where
${\bm{H}}^{\prime}=({\bm{h}}^{\prime}_{1},\ldots,{\bm{h}}^{\prime}_{t})^{\top}$
and ${\bm{H}}=({\bm{h}}_{1},\ldots,{\bm{h}}_{d})^{\top}$ are orthogonal
matrices, and ${\bm{\Lambda}}$ is the $t\times d$ rectangular diagonal matrix
whose $(j,j)$ element is the $j$th singular value $s_{j}\geq 0$ of
${\bm{X}}_{t}$. Thus,
${\bm{I}}_{d}-{\bm{X}}^{\top}_{t}({\bm{X}}_{t}{\bm{X}}^{\top}_{t}+a^{-2}\sigma^{2}{\bm{I}}_{t})^{-1}{\bm{X}}_{t}$
can be rewritten as follows:

${\bm{I}}_{d}-{\bm{X}}^{\top}_{t}({\bm{X}}_{t}{\bm{X}}^{\top}_{t}+a^{-2}\sigma^{2}{\bm{I}}_{t})^{-1}{\bm{X}}_{t}={\bm{H}}{\bm{\Theta}}{\bm{H}}^{\top},$

where $\Theta$ is the diagonal matrix whose $(j,j)$ element is
$1-s^{2}_{j}/(s^{2}_{j}+a^{-2}\sigma^{2})$. Thus, the posterior standard
deviation $\sigma_{t}({\bm{x}})$ can be expressed as

$\sigma_{t}({\bm{x}})=\sqrt{a^{2}{\bm{x}}^{\top}{\bm{H}}{\bm{\Theta}}{\bm{H}}^{\top}{\bm{x}}}=a\|{\bm{\Theta}}^{1/2}{\bm{H}}^{\top}{\bm{x}}\|.$

Hence, using the triangle inequality we have

$\displaystyle|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|$
$\displaystyle=a|\|{\bm{\Theta}}^{1/2}{\bm{H}}^{\top}{\bm{x}}\|-\|{\bm{\Theta}}^{1/2}{\bm{H}}^{\top}{\bm{y}}\||$
$\displaystyle\leq
a\|{\bm{\Theta}}^{1/2}{\bm{H}}^{\top}{\bm{x}}-{\bm{\Theta}}^{1/2}{\bm{H}}^{\top}{\bm{y}}\|$
$\displaystyle=a\|{\bm{\Theta}}^{1/2}{\bm{H}}^{\top}({\bm{x}}-{\bm{y}})\|.$
(E.35)

Noting that the diagonal element $\theta_{j}$ of ${\bm{\Theta}}$ satisfies
$0\leq\theta_{j}\leq 1$, from
$\|{\bm{x}}-{\bm{y}}\|\leq\|{\bm{x}}-{\bm{y}}\|_{1}$ we get

$\displaystyle\|{\bm{\Theta}}^{1/2}{\bm{H}}^{\top}({\bm{x}}-{\bm{y}})\|$
$\displaystyle=\sqrt{({\bm{x}}-{\bm{y}})^{\top}{\bm{H}}{\bm{\Theta}}{\bm{H}}^{\top}({\bm{x}}-{\bm{y}})}$
$\displaystyle\leq\sqrt{({\bm{x}}-{\bm{y}})^{\top}{\bm{H}}{\bm{I}}_{d}{\bm{H}}^{\top}({\bm{x}}-{\bm{y}})}=\|{\bm{x}}-{\bm{y}}\|\leq\|{\bm{x}}-{\bm{y}}\|_{1}.$
(E.36)

Therefore, by substituting (E.36) into (E.35), we have the desired result.

Next, we show the case of the Gaussian kernel. From Bochner’s theorem, the
Gaussian kernel can be rewritten as follows (see, e.g., section 4.2.1 in
Rasmussen and Williams, (2005)):

$\displaystyle k({\bm{x}},{\bm{y}})=a^{2}\int_{\mathbb{R}^{d}}e^{2\pi{\rm
i}({\bm{x}}-{\bm{y}})^{\top}{\bm{\lambda}}}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}\|^{2}}\text{d}{\bm{\lambda}},$

where ${\rm i}$ is the imaginary unit. Furthermore, for each natural number
$s\in\mathbb{N}$, let $\mathcal{I}_{s}$ and $\mathcal{C}_{s}$ be families of
sets given by

$\displaystyle\mathcal{I}_{s}$
$\displaystyle=\left\\{\left[-s+\frac{j-1}{2^{s}},-s+\frac{j}{2^{s}}\right)\mid
j=1,\ldots,2s2^{s}\right\\},$ $\displaystyle\mathcal{C}_{s}$
$\displaystyle=\\{I_{1}\times\cdots\times I_{d}\mid
I_{1},\ldots,I_{d}\in\mathcal{I}_{s}\\}.$

In addition, for each element
$C_{s,k}=[a^{(1)}_{s,k},b^{(1)}_{s,k})\times\cdots[a^{(d)}_{s,k},b^{(d)}_{s,k})$
of $\mathcal{C}_{s}$, $(k=1,\ldots,(2s2^{s})^{d})$, we define the
representative point ${\bm{\lambda}}_{s,k}$ of $C_{s,k}$ as

${\bm{\lambda}}_{s,k}=\left(\frac{a^{(1)}_{s,k}+b^{(1)}_{s,k}}{2},\ldots,\frac{a^{(d)}_{s,k}+b^{(d)}_{s,k}}{2}\right)^{\top}=(\lambda_{s,k}^{(1)},\ldots,\lambda_{s,k}^{(d)})^{\top}.$

Moreover, let ${\bm{\phi}}_{s}({\bm{x}})$ be the $(2s2^{s})^{d}$-dimensional
vector whose $k$th element $\phi_{s,k}({\bm{x}})$ is given by

$\displaystyle\phi_{s,k}({\bm{x}})=ae^{2\pi{\rm
i}{\bm{x}}^{\top}{\bm{\lambda}}_{s,k}}(2\pi\rho^{2})^{d/4}e^{-\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d/2}.$
(E.37)

Then, the inner product
$\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{y}})\rangle\equiv\overline{{\bm{\phi}}_{s}({\bm{x}})}^{\top}{\bm{\phi}}_{s}({\bm{y}})$
satisfies

$\displaystyle\lim_{s\to\infty}\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{y}})\rangle$
$\displaystyle=\lim_{s\to\infty}\sum_{k=1}^{(2s2^{s})^{d}}a^{2}e^{2\pi{\rm
i}(-{\bm{x}}+{\bm{y}})^{\top}{\bm{\lambda}}_{s,k}}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d}$
$\displaystyle=a^{2}\int_{\mathbb{R}^{d}}e^{2\pi{\rm
i}(-{\bm{x}}+{\bm{y}})^{\top}{\bm{\lambda}}}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}\|^{2}}\text{d}{\bm{\lambda}}$
$\displaystyle=a^{2}\int_{\mathbb{R}^{d}}e^{2\pi{\rm
i}({\bm{x}}-{\bm{y}})^{\top}{\bm{\lambda}}}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}\|^{2}}\text{d}{\bm{\lambda}}=k({\bm{x}},{\bm{y}}).$

Furthermore, we define $\check{\sigma}^{2}_{t,s}({\bm{x}})$ and
$\epsilon_{t,s}({\bm{x}})$ as

$\displaystyle\check{\sigma}^{2}_{t,s}({\bm{x}})$
$\displaystyle=\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{x}})\rangle-(\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{x}}_{1})\rangle,\ldots,\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{x}}_{t})\rangle)$
(E.38)
$\displaystyle({\bm{K}}_{t,s}+\sigma^{2}{\bm{I}}_{t})^{-1}(\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{x}}_{1})\rangle,\ldots,\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{x}}_{t})\rangle)^{\top},$
$\displaystyle\epsilon_{t,s}({\bm{x}})$
$\displaystyle=k({\bm{x}},{\bm{x}})-(k({\bm{x}},{\bm{x}}_{1}),\ldots,k({\bm{x}},{\bm{x}}_{t}))({\bm{K}}_{t}+\sigma^{2}{\bm{I}}_{t})^{-1}(k({\bm{x}},{\bm{x}}_{1}),\ldots,k({\bm{x}},{\bm{x}}_{t}))^{\top}$
(E.39) $\displaystyle\quad-\check{\sigma}^{2}_{t,s}({\bm{x}})$ (E.40)
$\displaystyle=\sigma^{2}_{t}({\bm{x}})-\check{\sigma}^{2}_{t,s}({\bm{x}}),$

where ${\bm{K}}_{t,s}$ and ${\bm{K}}_{t}$ are $t\times t$ matrices whose
$(i,j)$ elements are given by
$\langle{\bm{\phi}}_{s}({\bm{x}}_{i}),{\bm{\phi}}_{s}({\bm{x}}_{j})\rangle$
and
$\langle{\bm{\phi}}_{s}({\bm{x}}_{i}),{\bm{\phi}}_{s}({\bm{x}}_{j})\rangle$,
respectively. Then, noting that
$\lim_{s\to\infty}\langle{\bm{\phi}}_{s}({\bm{x}}),{\bm{\phi}}_{s}({\bm{y}})\rangle=k({\bm{x}},{\bm{y}})$
we get

$\lim_{s\to\infty}\check{\sigma}^{2}_{t,s}({\bm{x}})=\sigma^{2}_{t}({\bm{x}}),\quad\lim_{s\to\infty}\epsilon_{t,s}({\bm{x}})=0.$

We now consider $\sigma_{t}({\bm{x}})$ and $\sigma_{t}({\bm{y}})$. Without
loss of generality, we can assume that
$\sigma_{t}({\bm{x}})\geq\sigma_{t}({\bm{y}})$. Then, we have

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|=\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}}).$
(E.41)

In addition, the following inequality holds:

$\displaystyle\sigma_{t}({\bm{x}})=\sqrt{\sigma^{2}_{t}({\bm{x}})}=\sqrt{\check{\sigma}^{2}_{t,s}({\bm{x}})+\epsilon_{t,s}({\bm{x}})}$
$\displaystyle\leq\sqrt{\check{\sigma}^{2}_{t,s}({\bm{x}})+|\epsilon_{t,s}({\bm{x}})|}$
(E.42)
$\displaystyle\leq\sqrt{\check{\sigma}^{2}_{t,s}({\bm{x}})}+\sqrt{|\epsilon_{t,s}({\bm{x}})|}.$
(E.43)

Similarly, if $\epsilon_{t,s}({\bm{y}})>0$, then $\sigma_{t}({\bm{y}})$
satisfies

$\sigma_{t}({\bm{y}})=\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})+\epsilon_{t,s}({\bm{y}})}\geq\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})}\geq\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})}-\sqrt{|\epsilon_{t,s}({\bm{y}})|}.$

On the other hand, if $\epsilon_{t,s}({\bm{y}})\leq 0$, then
$\sigma_{t}({\bm{y}})$ satisfies

$\sigma_{t}({\bm{y}})=\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})+\epsilon_{t,s}({\bm{y}})}=\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})-|\epsilon_{t,s}({\bm{y}})|}\geq\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})}-\sqrt{|\epsilon_{t,s}({\bm{y}})|},$

where the last inequality is given by $\sqrt{u}-\sqrt{v}\leq\sqrt{u-v}$,
$(u\geq v\geq 0)$. Hence, for both cases, the following holds:

$\sigma_{t}({\bm{y}})\geq\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})}-\sqrt{|\epsilon_{t,s}({\bm{y}})|}.$
(E.44)

Thus, by substituting (E.43) and (E.44) into (E.41), we obtain

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|\leq\sqrt{\check{\sigma}^{2}_{t,s}({\bm{x}})}-\sqrt{\check{\sigma}^{2}_{t,s}({\bm{y}})}+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|}.$
(E.45)

Furthermore, we define the matrix ${\bm{X}}_{t,s}$ as
${\bm{X}}_{t,s}=({\bm{\phi}}_{s}({\bm{x}}_{1}),\ldots,{\bm{\phi}}_{s}({\bm{x}}_{t}))^{\ast}$,
where ${\bm{A}}^{\ast}$ is the conjugate transpose of ${\bm{A}}$. Then,
$\check{\sigma}^{2}_{t,s}({\bm{x}})$ can be rewritten as follows:

$\check{\sigma}^{2}_{t,s}({\bm{x}})=\overline{{\bm{\phi}}_{s}({\bm{x}})}^{\top}({\bm{I}}_{(2s2^{s})^{d}}-{\bm{X}}^{\ast}_{t,s}({\bm{X}}_{t,s}{\bm{X}}_{t,s}^{\ast}+\sigma^{2}{\bm{I}}_{t})^{-1}{\bm{X}}_{t,s}){\bm{\phi}}_{s}({\bm{x}}).$

Therefore, by using the singular decomposition of ${\bm{X}}_{t,s}$, we have

$\check{\sigma}^{2}_{t,s}({\bm{x}})=\overline{{\bm{\phi}}_{s}({\bm{x}})}^{\top}{\bm{U}}{\bm{\Theta}}{\bm{U}}^{\ast}{\bm{\phi}}_{s}({\bm{x}}),$

where ${\bm{U}}$ and ${\bm{\Theta}}$ are unitary and diagonal matrices,
respectively. By using the same argument as in the case of the linear kernel,
it can be shown that the $(k,k)$ element $\theta_{k}$ of ${\bm{\Theta}}$
satisfies $0\leq\theta_{k}\leq 1$. Hence, noting that

$\check{\sigma}_{t,s}({\bm{x}})=\sqrt{\check{\sigma}^{2}_{t,s}({\bm{x}})}=\|{\bm{\Theta}}^{1/2}{\bm{U}}^{\ast}{\bm{\phi}}_{s}({\bm{x}})\|$

and (E.45), from the triangle inequality we get

$\displaystyle|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|$
$\displaystyle\leq\|{\bm{\Theta}}^{1/2}{\bm{U}}^{\ast}{\bm{\phi}}_{s}({\bm{x}})\|-\|{\bm{\Theta}}^{1/2}{\bm{U}}^{\ast}{\bm{\phi}}_{s}({\bm{y}})\|+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|}$
$\displaystyle\leq\|{\bm{\Theta}}^{1/2}{\bm{U}}^{\ast}{\bm{\phi}}_{s}({\bm{x}})-{\bm{\Theta}}^{1/2}{\bm{U}}^{\ast}{\bm{\phi}}_{s}({\bm{y}})\|+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|}$
$\displaystyle=\|{\bm{\Theta}}^{1/2}{\bm{U}}^{\ast}({\bm{\phi}}_{s}({\bm{x}})-{\bm{\phi}}_{s}({\bm{y}}))\|+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|}$
$\displaystyle\leq\|{\bm{\phi}}_{s}({\bm{x}})-{\bm{\phi}}_{s}({\bm{y}})\|+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|},$
(E.46)

where the last inequality is given by $0\leq\theta_{k}\leq 1$. Moreover, for
each $j$ with $1\leq j\leq d-1$, let
${\bm{x}}[j]=(y_{1},\ldots,y_{j},x_{j+1},\ldots,x_{d})^{\top}$, and let
${\bm{x}}[0]\equiv{\bm{x}}$ and ${\bm{x}}[d]\equiv{\bm{y}}$. Then, the
following inequality holds:

$\displaystyle\|{\bm{\phi}}_{s}({\bm{x}})-{\bm{\phi}}_{s}({\bm{y}})\|$
$\displaystyle=\left\|\sum_{j=1}^{d}\\{{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\\}\right\|$
(E.47)
$\displaystyle\leq\sum_{j=1}^{d}\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|.$
(E.48)

Thus, by substituting (E.48) into (E.46), we obtain

$\displaystyle|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|\leq\sum_{j=1}^{d}\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|}.$
(E.49)

In addition, for any $j$ and $k$ with $1\leq j\leq d$ and $1\leq
k\leq(2s2^{s})^{d}$, from the definition of $\phi_{s,k}({\bm{x}})$ we have

$\displaystyle\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j])$
$\displaystyle=aD(2\pi\rho^{2})^{d/4}e^{-\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d/2}(e^{2\pi{\rm
i}x_{j}{\lambda}^{(j)}_{s,k}}-e^{2\pi{\rm i}y_{j}{\lambda}^{(j)}_{s,k}}),$
$\displaystyle D$ $\displaystyle=e^{2\pi{\rm
i}(y_{1},\ldots,y_{j-1},x_{j+1},\ldots,x_{d})({\lambda}^{(1)}_{s,k},\ldots,{\lambda}^{(j-1)}_{s,k},{\lambda}^{(j+1)}_{s,k},\ldots,{\lambda}^{(d)}_{s,k})^{\top}}.$

Hence, it follows that

$\displaystyle\overline{(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))}(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))$
$\displaystyle=|\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j])|^{2}$
$\displaystyle\leq
a^{2}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d}|e^{2\pi{\rm
i}x_{j}{\lambda}^{(j)}_{s,k}}-e^{2\pi{\rm i}y_{j}{\lambda}^{(j)}_{s,k}}|^{2}.$
(E.50)

Thus, noting that $|\cos(u)-\cos(v)|\leq|u-v|$ and
$|\sin(u)-\sin(v)|\leq|u-v|$ for any $u,v\in\mathbb{R}$, we get

$\displaystyle|e^{2\pi{\rm i}x_{j}{\lambda}^{(j)}_{s,k}}-e^{2\pi{\rm
i}y_{j}{\lambda}^{(j)}_{s,k}}|$ (E.51) $\displaystyle=|\cos(2\pi
x_{j}{\lambda}^{(j)}_{s,k})+{\rm i}\sin(2\pi
x_{j}{\lambda}^{(j)}_{s,k})-\cos(2\pi y_{j}{\lambda}^{(j)}_{s,k})-{\rm
i}\sin(2\pi y_{j}{\lambda}^{(j)}_{s,k})|$ $\displaystyle=\sqrt{|\cos(2\pi
x_{j}{\lambda}^{(j)}_{s,k})-\cos(2\pi
y_{j}{\lambda}^{(j)}_{s,k})|^{2}+|\sin(2\pi
x_{j}{\lambda}^{(j)}_{s,k})-\sin(2\pi y_{j}{\lambda}^{(j)}_{s,k})|^{2}}$
$\displaystyle\leq\sqrt{8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}}.$
(E.52)

Therefore, by substituting (E.52) into (E.50), we obtain

$\displaystyle\overline{(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))}(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))$
$\displaystyle\leq
a^{2}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}.$

This implies that

$\displaystyle\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|^{2}\leq\sum_{k=1}^{(2s2^{s})^{d}}a^{2}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}.$
(E.53)

Moreover, the following holds when $s\to\infty$:

$\displaystyle\lim_{s\to\infty}\sum_{k=1}^{(2s2^{s})^{d}}a^{2}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}$
$\displaystyle=a^{2}(2\pi\rho^{2})^{d/2}8\pi^{2}(x_{j}-y_{j})^{2}\int_{\mathbb{R}^{d}}e^{-2\pi^{2}\rho^{2}{\bm{\lambda}}^{\top}{\bm{\lambda}}}\lambda^{2}_{j}\text{d}{\bm{\lambda}}$
$\displaystyle=a^{2}8\pi^{2}(x_{j}-y_{j})^{2}\left(\int_{\mathbb{R}}(2\pi\rho^{2})^{1/2}\lambda_{j}^{2}e^{-2\pi^{2}\rho^{2}\lambda^{2}_{j}}\text{d}\lambda_{j}\right)\prod_{i\neq
j}^{d}\left(\int_{\mathbb{R}}(2\pi\rho^{2})^{1/2}e^{-2\pi^{2}\rho^{2}\lambda^{2}_{i}}\text{d}\lambda_{i}\right).$

By putting $2\pi\rho\lambda_{i}=u_{i}$ for each $i$ with $1\leq i\leq d$, we
have

$\displaystyle
a^{2}8\pi^{2}(x_{j}-y_{j})^{2}\left(\int_{\mathbb{R}}(2\pi\rho^{2})^{1/2}\lambda_{j}^{2}e^{-2\pi^{2}\rho^{2}\lambda^{2}_{j}}\text{d}\lambda_{j}\right)\prod_{i\neq
j}^{d}\left(\int_{\mathbb{R}}(2\pi\rho^{2})^{1/2}e^{-2\pi^{2}\rho^{2}\lambda^{2}_{i}}\text{d}\lambda_{i}\right)$
$\displaystyle=a^{2}2\rho^{-2}(x_{j}-y_{j})^{2}\int_{\mathbb{R}}(2\pi)^{-1/2}u^{2}_{j}e^{-u^{2}_{j}/2}\text{d}u_{j}\prod_{i\neq
j}^{d}\left(\int_{\mathbb{R}}(2\pi)^{-1/2}e^{-u^{2}_{i}/2}\text{d}u_{i}\right)$
$\displaystyle=\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}.$ (E.54)

Thus, (E.53) can be rewritten as follows:

$\displaystyle\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|^{2}$
$\displaystyle\leq\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}$ (E.55)
$\displaystyle\quad+\sum_{k=1}^{(2s2^{s})^{d}}a^{2}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}-\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}$
$\displaystyle\leq\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}$ (E.56)
$\displaystyle\quad+\left|\sum_{k=1}^{(2s2^{s})^{d}}a^{2}(2\pi\rho^{2})^{d/2}e^{-2\pi^{2}\rho^{2}\|{\bm{\lambda}}_{s,k}\|^{2}}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}-\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}\right|$
$\displaystyle\equiv\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}+\tilde{\epsilon}_{s,j},$

where $\tilde{\epsilon}_{s,j}$ satisfies that
$\lim_{s\to\infty}|\tilde{\epsilon}_{s,j}|=0$ from (E.54). Hence, we get

$\displaystyle\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|\leq\sqrt{\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}+\tilde{\epsilon}_{s,j}}\leq\frac{\sqrt{2}a}{\rho}|x_{j}-y_{j}|+\sqrt{\tilde{\epsilon}_{s,j}}.$
(E.57)

By substituting (E.57) into (E.49), we obtain

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|\leq\frac{\sqrt{2}a}{\rho}\|{\bm{x}}-{\bm{y}}\|_{1}+\sum_{j=1}^{d}\sqrt{\tilde{\epsilon}_{s,j}}+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|}.$

Furthermore, because the number $s$ is an arbitrary natural number, and

$\lim_{s\to\infty}\left(\sum_{j=1}^{d}\sqrt{\tilde{\epsilon}_{s,j}}+\sqrt{|\epsilon_{t,s}({\bm{x}})|}+\sqrt{|\epsilon_{t,s}({\bm{y}})|}\right)=0,$

we have

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|\leq\frac{\sqrt{2}a}{\rho}\|{\bm{x}}-{\bm{y}}\|_{1}.$

Finally, we show the case of the Matérn kernel. From Bochner’s theorem, the
Matérn kernel can be rewritten as follows (see, section 4.2.1 in Rasmussen and
Williams, (2005)):

$\displaystyle k({\bm{x}},{\bm{y}})=a^{2}\int_{\mathbb{R}^{d}}e^{2\pi{\rm
i}({\bm{x}}-{\bm{y}})^{\top}{\bm{\lambda}}}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}\|^{2}\right)^{-(\nu+d/2)}\text{d}{\bm{\lambda}}.$

For each $s\in\mathbb{N}$ and $k$ with $k=1,\ldots,(2s2^{s})^{d}$, we define
$\mathcal{I}_{s}$, $\mathcal{C}_{s}$, the element
$C_{s,k}=[a^{(1)}_{s,k},b^{(1)}_{s,k})\times\cdots[a^{(d)}_{s,k},b^{(d)}_{s,k})$
of $\mathcal{C}_{s}$, and the representative point ${\bm{\lambda}}_{s,k}$ of
$C_{s,k}$ as in the case of the Gaussian kernel. Similarly, let
${\bm{\phi}}_{s}({\bm{x}})$ be the $(2s2^{s})^{d}$-dimensional vector whose
$k$th element $\phi_{s,k}({\bm{x}})$ is given by

$\displaystyle\phi_{s,k}({\bm{x}})$ (E.58) $\displaystyle=ae^{2\pi{\rm
i}{\bm{x}}^{\top}{\bm{\lambda}}_{s,k}}\left(\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}_{s,k}\|^{2}\right)^{-(\nu+d/2)}\right)^{1/2}\left(\frac{1}{2^{s}}\right)^{d/2}.$
(E.59)

Then, by using the same argument as in the case of the Gaussian kernel, we
obtain the following inequality similar to (E.49):

$\displaystyle|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|\leq\sum_{j=1}^{d}\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|+|\epsilon_{t,s}({\bm{x}},{\bm{y}})|,$
(E.60)

where $\lim_{s\to\infty}|\epsilon_{t,s}({\bm{x}},{\bm{y}})|=0$. Moreover, for
any $j$ and $k$ with $1\leq j\leq d$ and $1\leq k\leq(2s2^{s})^{d}$, from the
definition of $\phi_{s,k}({\bm{x}})$ we get

$\displaystyle\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j])$
$\displaystyle=aD\left(\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}_{s,k}\|^{2}\right)^{-(\nu+d/2)}\right)^{1/2}\left(\frac{1}{2^{s}}\right)^{d/2}$
(E.61) $\displaystyle\quad(e^{2\pi{\rm
i}x_{j}{\lambda}^{(j)}_{s,k}}-e^{2\pi{\rm i}y_{j}{\lambda}^{(j)}_{s,k}}),$
$\displaystyle D=e^{2\pi{\rm
i}(y_{1},\ldots,y_{j-1},x_{j+1},\ldots,x_{d})({\lambda}^{(1)}_{s,k},\ldots,{\lambda}^{(j-1)}_{s,k},{\lambda}^{(j+1)}_{s,k},\ldots,{\lambda}^{(d)}_{s,k})^{\top}}.$

It follows that

$\displaystyle\overline{(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))}(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))$
$\displaystyle=|\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j])|^{2}$
$\displaystyle\leq
a^{2}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}_{s,k}\|^{2}\right)^{-(\nu+d/2)}\left(\frac{1}{2^{s}}\right)^{d}|e^{2\pi{\rm
i}x_{j}{\lambda}^{(j)}_{s,k}}-e^{2\pi{\rm i}y_{j}{\lambda}^{(j)}_{s,k}}|^{2}.$
(E.62)

By substituting (E.52) into (E.62), we have

$\displaystyle\overline{(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))}(\phi_{s,k}({\bm{x}}[j-1])-\phi_{s,k}({\bm{x}}[j]))$
$\displaystyle\leq
a^{2}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}_{s,k}\|^{2}\right)^{-(\nu+d/2)}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}.$

This implies that

$\displaystyle\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|^{2}$
$\displaystyle\leq\sum_{k=1}^{(2s2^{s})^{d}}a^{2}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}_{s,k}\|^{2}\right)^{-(\nu+d/2)}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}.$

Furthermore, the following holds when $s\to\infty$:

$\displaystyle\lim_{s\to\infty}\sum_{k=1}^{(2s2^{s})^{d}}a^{2}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}_{s,k}\|^{2}\right)^{-(\nu+d/2)}\left(\frac{1}{2^{s}}\right)^{d}8\pi^{2}\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}$
$\displaystyle=a^{2}8\pi^{2}(x_{j}-y_{j})^{2}\int_{\mathbb{R}^{d}}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}\|^{2}\right)^{-(\nu+d/2)}\lambda_{j}^{2}\text{d}{\bm{\lambda}}.$

In addition, by putting $2\nu=\tilde{\nu}$ and
${\bm{\Sigma}}=(4\pi^{2}\rho^{2})^{-1}{\bm{I}}_{d}$, we obtain

$\displaystyle\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}\|^{2}\right)^{-(\nu+d/2)}$
$\displaystyle=\frac{\Gamma((\tilde{\nu}+d)/2)}{\Gamma(\tilde{\nu}/2)\tilde{\nu}^{d/2}\pi^{d/2}|{\bm{\Sigma}}|^{1/2}}\left(1+\frac{1}{\tilde{\nu}}{\bm{\lambda}}^{\top}{\bm{\Sigma}}^{-1}{\bm{\lambda}}\right)^{-(\tilde{\nu}+d)/2}\equiv
f({\bm{\lambda}};\tilde{\nu},{\bm{\Sigma}}).$

Note that $f({\bm{\lambda}};\tilde{\nu},{\bm{\Sigma}})$ is the probability
density function of ${\bm{T}}_{\tilde{\nu}}({\bm{0}},{\bm{\Sigma}})$, where
${\bm{T}}_{\tilde{\nu}}({\bm{0}},{\bm{\Sigma}})$ is the multivariate
$t$-distribution with location parameter ${\bm{0}}$, scale matrix
${\bm{\Sigma}}$ and $\tilde{\nu}$ degrees of freedom. It is known that the
mean vector and covariance matrix of
${\bm{T}}_{\tilde{\nu}}({\bm{0}},{\bm{\Sigma}})$ are respectively given by
${\bm{0}}$ and $\frac{\tilde{\nu}}{\tilde{\nu}-2}{\bm{\Sigma}}$ when
$\tilde{\nu}>2$ (see, e.g., Kotz and Nadarajah, (2004)). From the assumption
$\nu>1$, noting that $\tilde{\nu}=2\nu>2$ we have

$\displaystyle\int_{\mathbb{R}^{d}}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}\|^{2}\right)^{-(\nu+d/2)}\lambda_{j}^{2}\text{d}{\bm{\lambda}}$
(E.63)
$\displaystyle=\int_{\mathbb{R}^{d}}f({\bm{\lambda}};\tilde{\nu},{\bm{\Sigma}})\lambda_{j}^{2}\text{d}{\bm{\lambda}}$
$\displaystyle=\frac{\tilde{\nu}}{\tilde{\nu}-2}\frac{1}{4\pi^{2}\rho^{2}}=\frac{{\nu}}{{\nu}-1}\frac{1}{4\pi^{2}\rho^{2}}.$

This implies that

$\displaystyle\lim_{s\to\infty}\sum_{k=1}^{(2s2^{s})^{d}}a^{2}\frac{2^{d}\pi^{d/2}\Gamma(\nu+d/2)(2\nu)^{\nu}}{\Gamma(\nu)\rho^{2\nu}}\left(\frac{2\nu}{\rho^{2}}+4\pi^{2}\|{\bm{\lambda}}_{s,k}\|^{2}\right)^{-(\nu+d/2)}\left(\frac{1}{2^{s}}\right)^{d}2\lambda^{(j)2}_{s,k}(x_{j}-y_{j})^{2}$
$\displaystyle=\frac{2a^{2}}{\rho^{2}}(x_{j}-y_{j})^{2}\frac{{\nu}}{{\nu}-1}.$

Therefore, by using the same argument as in the case of the Gaussian kernel,
we obtain

$\displaystyle\|{\bm{\phi}}_{s}({\bm{x}}[j-1])-{\bm{\phi}}_{s}({\bm{x}}[j])\|\leq\frac{\sqrt{2}a}{\rho}\sqrt{\frac{\nu}{\nu-1}}|x_{j}-y_{j}|+|\hat{\epsilon}_{s,j}|,$
(E.64)

where $\lim_{s\to\infty}|\hat{\epsilon}_{s,j}|=0$. Hence, by substituting
(E.64) into (E.60), and taking $s\to\infty$ we get

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{y}})|\leq\frac{\sqrt{2}a}{\rho}\sqrt{\frac{\nu}{\nu-1}}\|{\bm{x}}-{\bm{y}}\|_{1}.$

∎

The condition that $\sigma^{2}$ in Theorem E.4 is positive is necessary only
for the inverse matrix calculation. Note that $\sigma^{2}$ is a user-specified
variance parameter of a formal GP model, and is different from the true noise
variance. That is, Theorem E.4 holds even when the variance of the true noise
is zero, i.e., in the noiseless setting. Also note that $C$ in Theorem E.4 is
a constant independent of $\sigma^{2}$. The result for the Matérn kernel is
for the case of $\nu>1$ degrees of freedom, and it is a future work to clarify
whether the same result holds for $\nu\leq 1$ as well. On the other hand,
unfortunately, it can be shown that (E.29) does not hold for $\nu=1/2$, which
is often used in practice for Matérn kernels.

######  Theorem E.5.

In the setting of Theorem E.4, the Matérn kernel with $\nu=1/2$ does not
satisfy (E.29).

###### Proof.

Let $C$ be an arbitrary positive number. The Matérn kernel with $\nu=1/2$ is
given by

$k({\bm{x}},{\bm{y}})=a^{2}\exp(-\|{\bm{x}}-{\bm{y}}\|/\rho).$

In addition, suppose that ${\bm{x}}_{1}=\cdots={\bm{x}}_{t}={\bm{0}}$.
Moreover, we define ${\bm{K}}_{t}$ as

${\bm{K}}_{t}=a^{2}{\bm{1}}_{t}{\bm{1}}^{\top}_{t}+\sigma^{2}{\bm{I}}_{t}.$

Then, the inverse matrix ${\bm{K}}^{-1}_{t}$ can be expressed as

${\bm{K}}^{-1}_{t}=\sigma^{-2}{\bm{I}}_{t}-\frac{\frac{a^{2}}{\sigma^{4}}{\bm{1}}_{t}{\bm{1}}^{\top}_{t}}{1+\frac{a^{2}}{\sigma^{2}}t}.$

Therefore, the posterior variance at point ${\bm{0}}$ is given by

$\sigma^{2}_{t}({\bm{0}})=a^{2}-a^{4}{\bm{1}}^{\top}_{t}{\bm{K}}^{-1}_{t}{\bm{1}}_{t}=a^{2}-a^{4}\frac{t}{\sigma^{2}+a^{2}t}=\frac{a^{2}\sigma^{2}}{\sigma^{2}+a^{2}t}.$

Next, let $s$ be a number with $0<s<\rho/2$, and let
${\bm{x}}=(s,0,\ldots,0)^{\top}$. Then, we have

$\displaystyle\sigma^{2}_{t}({\bm{x}})$
$\displaystyle=a^{2}-a^{4}\exp(-2s/\rho){\bm{1}}^{\top}_{t}{\bm{K}}^{-1}_{t}{\bm{1}}_{t}$
$\displaystyle=a^{2}-a^{4}\exp(-2s/\rho)\frac{t}{\sigma^{2}+a^{2}t}$
$\displaystyle=a^{2}-a^{4}(1+\exp(-2s/\rho)-1)\frac{t}{\sigma^{2}+a^{2}t}$
$\displaystyle=\sigma^{2}_{t}({\bm{0}})+\frac{a^{4}t}{\sigma^{2}+a^{2}t}(1-\exp(-2s/\rho))$
(E.65)
$\displaystyle=\sigma^{2}_{t}({\bm{0}})\left\\{1+\frac{a^{4}t}{\sigma^{2}_{t}({\bm{0}})(\sigma^{2}+a^{2}t)}(1-\exp(-2s/\rho))\right\\}\equiv\sigma^{2}_{t}({\bm{0}})(1+u).$

Thus, from $u\geq 0$ we get

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{0}})|=\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{0}})=\sigma_{t}({\bm{0}})\sqrt{1+u}-\sigma_{t}({\bm{0}}).$

Furthermore, by using Taylor’s expansion of $f(u)=\sqrt{1+u}$ at point $u=0$,
we obtain

$\sqrt{1+u}\geq 1+\frac{1}{2}u-\frac{1}{8}u^{2}.$

Moreover, for each $t$, there exists a number $s$ such that $0<s<\rho/2$ and
$u\leq 1$. Therefore, it follows that

$\sqrt{1+u}\geq 1+\frac{1}{2}u-\frac{1}{8}u^{2}\geq
1+\frac{1}{2}u-\frac{1}{8}u=1+\frac{3}{8}u.$

By using this, we have

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{0}})|\geq\frac{3}{8}u\sigma_{t}({\bm{0}})=\frac{3}{8}\frac{a^{4}t}{\sigma_{t}({\bm{0}})(\sigma^{2}+a^{2}t)}(1-\exp(-2s/\rho)).$

In addition, noting that $\exp(-2s/\rho)\leq 1-2s/\rho+(2s/\rho)^{2}/2$ and
$1-s/\rho\geq 1/2$, we get

$1-\exp(-2s/\rho)\geq 2s/\rho-(2s/\rho)^{2}/2=2s/\rho(1-s/\rho)\geq s/\rho.$

Therefore, the following inequality holds:

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{0}})|\geq\frac{3}{8}\frac{a^{4}t/\rho}{\sigma_{t}({\bm{0}})(\sigma^{2}+a^{2}t)}s=\frac{3}{8}\frac{a^{4}/\rho}{\sigma_{t}({\bm{0}})(\sigma^{2}/t+a^{2})}\|{\bm{x}}-{\bm{0}}\|_{1}.$

Hence, since $\lim_{t\to\infty}\sigma_{t}({\bm{0}})=0$, the following
inequality holds for sufficiently large $t$:

$|\sigma_{t}({\bm{x}})-\sigma_{t}({\bm{0}})|\geq\frac{3}{8}\frac{a^{4}/\rho}{\sigma_{t}({\bm{0}})(\sigma^{2}/t+a^{2})}\|{\bm{x}}-{\bm{0}}\|_{1}>C\|{\bm{x}}-{\bm{0}}\|_{1}.$

∎

##  F Details of the Experimental Settings and Pseudo-codes

In this section, we describe the experimental settings.

###  F.1 Common Settings

We used a multi-start L-BFGS-B method Byrd et al., (1995) (SciPy Virtanen et
al., (2020) implementation) to perform various optimization such as optimizing
AFs, finding the optimal value of synthetic functions. First, we sample $1000$
initial points using Latin hypercube sampling (LHS) McKay et al., (2000).
Then, we run L-BFGS-B with parameter
$\mathtt{ftol}=10^{-3},\mathtt{gtol}=10^{-3}$ for each initial point and pick
the top 5 results. Finally, we run L-BFGS-B with default parameters for these
five results and return the best result. We implemented GP models and all the
comparison methods mainly using PyTorch Paszke et al., (2019) and GPyTorch
Gardner et al., (2018). By utilizing the automatic differentiation of PyTorch,
we can easily apply gradient methods to optimize AFs.

###  F.2 Comparison Methods

#### CBO

In CBO, a scalar output is assumed for each stage. For each iteration $t$, it
first chooses the controllable parameter of the final stage $\bm{x}^{(N)}_{t}$
and desired output of previous stage $y^{(N-1)}_{\mathrm{desire}}$ by
maximizing EI:

$(y^{(N-1)}_{\mathrm{desire}},\bm{x}^{(N)}_{t})=\operatorname*{arg\,max}_{y^{(N-1)},\bm{x}^{(N)}}\sigma^{(N)}_{t-1}(y^{(N-1)},\bm{x}^{(N)})(Z\Phi(Z)+\phi(Z)),$
(F.1)

where $\Phi,\phi$ are the cumulative distribution function and probability
density function of the standard normal distribution, respectively, $Z=0$ if
$\sigma^{(N)}_{t-1}(y^{(N-1)},\bm{x}^{(N)})=0$ and be
$Z=(\mu_{t-1}^{(N)}(y^{(N-1)},\bm{x}^{(N)})-F_{\mathrm{best}})/\sigma^{(N)}_{t-1}(y^{(N-1)},\bm{x}^{(N)})$
otherwise. We could not find any description about the range of optimization
parameters in Dai Nguyen et al., (2016). We used $\mathcal{X}^{(N)}$ for the
range of $\bm{x}^{(N)}$, and we used the range twice as wide as the actual
range for the range of $y^{(N-1)}$, which is supposed to be unknown. Then, CBO
chooses $(y^{(N-2)}_{\mathrm{desire}},\bm{x}_{t}^{(N-1)})$ of stage $N-1$ as
follows:

$(y^{(N-2)}_{\mathrm{desire}},\bm{x}^{(N-1)}_{t})=\operatorname*{arg\,min}_{y^{(N-2)},\bm{x}^{(N-1)}}\left(\kappa_{1}v^{-1}+\kappa_{2}v\right)\|m-y_{\mathrm{desire}}^{(N-1)}\|_{2}^{2}+\mathrm{cost}(y^{(N-2)},\bm{x}^{(N-1)}),$
(F.2)

where
$m=\mu_{t-1}^{(N-1)}(y^{(N-2)},\bm{x}^{(N-1)}),\;v=\sigma^{(N-1)\,2}_{t-1}(y^{(N-2)},\bm{x}^{(N-1)})$,
$\mathrm{cost}(\cdot)$ is the cost function, and $\kappa_{1},\kappa_{2}$ are
hyperparameters. By repeating this operation, a controllable parameter of
stage 1 $\bm{x}_{t}^{(1)}$ is determined finally. We used
$\mathrm{cost}(\cdot)=0$ for simplicity and set $\kappa_{1}=1,\kappa_{2}=1$.

In the solar cell simulator experiments, output of stage $1$ and stage $2$ are
vectors. To deal with vector output, we replace a predictive mean and variance
in F.2 with a mean vector and covariance matrix. Therefore, for the vector
output setting, the following AF was used instead of F.2:

$(\bm{y}^{(n-1)}_{\mathrm{desire}},\bm{x}^{(n)}_{t})=\operatorname*{arg\,min}_{\bm{y}^{(n-1)},\bm{x}^{(x)}}\Bigl{[}\left(\bm{m}-\bm{y}_{\mathrm{desire}}^{(n)}\right)^{\top}\left(\kappa_{1}{\bm{\Sigma}^{-1}}+\kappa_{2}\bm{\Sigma}\right)\left(\bm{m}-\bm{y}_{\mathrm{desire}}^{(n)}\right)\Bigr{]},$
(F.3)

where $\bm{m}=\bm{\mu}_{t-1}^{(n)}(\bm{y}^{(n-1)},\bm{x}^{(n)})$ and
$\bm{\Sigma}$ is a diagonal matrix whose $(i,i)$-th element is defined as
$\sigma^{(n)\,2}_{m,t-1}(\bm{y}^{(n-1)},\bm{x}^{(n)})$.

#### FB-EI, FB-UCB

In FB-EI and FB-UCB, the next sampling point is determined by using a fully
black-box GP model. To construct this model, we employed an ARD Gaussian
kernel and set the noise variance of GP to $10^{-4}$. The kernel parameters
were estimated by maximizing the marginal likelihood. In particular, FB-UCB
used GP-UCB method Srinivas et al., (2010), and we set its exploration
parameter $\beta_{\mathrm{GP-UCB}}^{1/2}=2$.

#### EI-based

Since EI-based AF is computed through sampling, we have to use stochastic
gradient methods to optimize it in a naive implementation. However, L-BFGS-B
can also be applied by utilizing reparameterization-trick Kingma and Welling,
(2014). At the beginning of the optimization, we draw base-samples
$\bm{\omega}^{(n)}\in\mathbb{R}^{S}$ from standard multivariate Gaussian
distribution for each middle stage. Then, instead of sampling each
$\\{y_{s}^{(n)}\\}_{s=1}^{S}$ directly from Gaussian distribution, we sample
it as follows:

$y^{(n)}_{s}=\mu_{y^{(n)}_{s}}+\sigma_{y^{(n)}_{s}}\omega^{(n)}_{s}.$ (F.4)

Here, $\mu_{y^{(n)}_{s}},\sigma_{y^{(n)}_{s}}$ are the mean and standard
deviation of the Gaussian distribution that follows $y^{(n)}_{s}$,
respectively. The EI-based AF becomes a deterministic and differentiable
function with the above modifications, and the L-BFGS-B method can be applied.
Moreover, EI-based AF can also be applied to the vector output setting. We
only need to change it to sample $\bm{y}^{(n)}_{s}$ instead of $y^{(n)}_{s}$
in the middle stage.

In EI-SUS-R for the suspension setting experiments, we applied the stock
reduction rule (13) except for the stock obtained in the last iteration.

###  F.3 Synthetic functions and Solar Cell Simulator

#### Sample Paths:

In the sample path experiments, we used random Fourier features (RFFs) to draw
continuous functions from GP priors. We first sampled 1000 RFFs and built
Bayesian linear regression (BLR) model. From the BLR model, we sampled weight
parameters and constructed functions.

#### Rosenbrock Function:

For any $d\geq 2$, $d$-dimensional Rosenbrock function is defined as follows:

$f(\bm{x})=\sum_{i=1}^{d}\left(100(x_{i+1}-x_{i}^{2})^{2}+(x_{i}-1)^{2}\right).$
(F.5)

In our experiments, we used negative Rosenbrock functions, which are
multiplied by $-1$.

#### Sphere Function:

For any $d\geq 2$, $d$-dimensional Sphere function is defined as follows:

$f(\bm{x})=\sum_{i=1}^{d}x_{i}^{2}.$ (F.6)

In our experiments, we used negative Sphere functions, which are multiplied by
$-1$.

#### Matyas Function:

Matyas function ($d=2$) is defined as follows:

$f(\bm{x})=0.26(x_{1}^{2}+x_{2}^{2})-0.48x_{1}x_{2}.$ (F.7)

In our experiments, we used negative Matyas functions, which are multiplied by
$-1$.

#### Solar Cell Simulator:

The simulators for stages one and two are Python implementations of the
physical models described in Section 4 of Bentzen, (2006). The simulator of
stage three is based on PC1Dmod 6.2 Haug and Greulich, (2016), which is the
software for simulating solar cells. We confirmed that PC1D sometimes caused
errors due to convergence failure of the internal calculations. However,
standard BO frameworks cannot handle the situation where the observation
fails. Thus, we used a kernel ridge regression model constructed using the
data collected from PC1D as the simulator of stage 3. To create this
simulator, we ran PC1D on each of the 2000 input points sampled using the LHS,
and used the 1935 data points among them that could be run without error.

#### Hydrogen plasma treatment process:

The real-world datasets for the first and second stages are from (Miyagawa et
al., 2021a, ) and the simulator in https://www.pvlighthouse.com.au/equivalent-
circuit, respectively. For both stages, we fitted the GPs with a Gaussian
kernel, in which hyperparameters are selected by the marginal likelihood
maximization. Then, as with sample paths, we sampled 1000 RFFs, built BLR
models, and generate continuous sample paths once. We used these sample paths
as the surrogate objectives.

###  F.4 Pseudo-codes of the proposed methods

We describe the proposed method of section 3 in algorithm 1. Additionally, we
also describe the proposed method of extension setting in algorithm 2.

Input: Initial data $\\{\mathcal{D}_{0}^{(n)}\\}_{n=1}^{N}$, $\beta$,
$\eta_{t}$

1 for  _$t=0,N,2N,\dots,T$_ do

2 Fit GP models using $\\{\mathcal{D}_{t-1}^{(n)}\\}_{n=1}^{N}$

3 for  _$n=1,\ldots,N$_ do

4 Select $\bm{x}^{(n)}_{t+n}$ by maximizing 5c or 14

5 Observe output $\bm{y}_{t+n}^{(n)}$ corresponding input
$(\bm{y}^{(n-1)}_{t+n-1},\bm{x}^{(n)}_{t+n})$

6
$\mathcal{D}_{t+n}^{(n)}\leftarrow\mathcal{D}_{t+n-1}^{(n)}\cup\\{((\bm{y}^{(n-1)}_{t+n-1},\bm{x}_{t+n}^{(n)}),\bm{y}_{t+n}^{(n)})\\}$

7

8 end for

9 $t\leftarrow t+N$

10

11 end for

Output: Estimated solution
$\hat{\bm{x}}_{t}^{(1)},\dots,\hat{\bm{x}}_{t}^{(N)}$

Algorithm 1 Cascade process optimization in sequential observation

Input: $\\{\mathcal{D}_{0}^{(n)}\\}_{n=1}^{N}$, $\beta$, $\eta_{t}$, stage
cost $\\{\lambda^{(n)}\\}_{n=1}^{N}$, budget $\lambda_{\max}$

1 $t\leftarrow 1$,
$\mathcal{S}_{t}^{(0)}\leftarrow\\{\bm{0}\\},\\{\mathcal{S}_{t}^{(n)}\leftarrow\emptyset\\}_{n=1}^{N-1}$,
spend cost $\lambda\leftarrow 0$

2 while  _$\lambda\leq\lambda_{\max}$_ do

3 Fit GP models using $\\{\mathcal{D}_{t-1}^{(n)}\\}_{n=1}^{N}$

4 Select $n_{t},\bm{y}_{t}^{(n_{t}-1)},\bm{x}_{t}^{(n)}$ by 20

5 Observe $\bm{y}_{t}^{(n_{t})}$

6
$\mathcal{D}_{t}^{(n_{t})}\leftarrow\mathcal{D}_{t-1}^{(n_{t})}\cup\\{((\bm{y}_{t}^{(n_{t}-1)},\bm{x}_{t}^{(n_{t})}),\bm{y}_{t}^{(n_{t})})\\}$

7 Remove stock
$\mathcal{S}_{t}^{(n_{t}-1)}\leftarrow\mathcal{S}_{t}^{(n_{t}-1)}\setminus\bm{y}_{t}^{(n_{t}-1)}$

8 if  _$n_{t}\neq N$_ then

9 Add observed stock
$\mathcal{S}_{t}^{(n_{t})}\leftarrow\mathcal{S}_{t}^{(n_{t})}\cup\\{\bm{y}_{t}^{(n_{t})}\\}$

10

11 $\lambda\leftarrow\lambda+\lambda^{(n_{t})},\;t\leftarrow t+1$

12

13 end while

Output: Estimated solution
$\hat{\bm{x}}_{t}^{(1)},\dots,\hat{\bm{x}}_{t}^{(N)}$

Algorithm 2 Cascade process optimization in suspension setting

Figure 7: Results of comparison between EI-based and EI-FN

.

##  G Additional Experimental Results

We additionally show the comparison between EI-based AF and EI-FN Astudillo
and Frazier, (2021). In this experiment, we used a three- and five-stage
cascade consisting of GP pre-distributed sample paths. We set
$\ell_{d}^{(n)}=1,\ell_{w}^{(n)}=1$, and the other experimental settings are
the same as those described in Section 6. Figure 7 shows the results of 20
runs with different random seeds. Since the parameters $\ell_{d}^{(n)}$ and
$\ell_{w}^{(n)}$ are relatively small, the sample paths can be sensitive to
the input uncertainty. Therefore, in this experiment, EI-based AF that
performs adaptive decision-making using intermediate observations clearly
outperforms EI-FN, which is nonadaptive.

## References

  * Abbasi-Yadkori, (2012) Abbasi-Yadkori, Y. (2012).  Online Learning for Linearly Parametrized Control Problems.  PhD thesis, Department of Computing Science, University of Alberta.
  * Byrd et al., (1995) Byrd, R. H., Lu, P., Nocedal, J., & Zhu, C. (1995).  A limited memory algorithm for bound constrained optimization.  SIAM Journal on scientific computing, 16(5), 1190–1208.
  * Gardner et al., (2018) Gardner, J. R., Pleiss, G., Bindel, D., Weinberger, K. Q., & Wilson, A. G. (2018).  GPyTorch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration.  In Advances in Neural Information Processing Systems, (Vol. 31, ). Curran Associates, Inc.
  * Kirschner and Krause, (2018) Kirschner, J. & Krause, A. (2018).  Information directed sampling and bandits with heteroscedastic noise.  In Proceedings of the 31st Conference On Learning Theory, (Vol. 75, pp. 358–384). PMLR.
  * Kotz and Nadarajah, (2004) Kotz, S. & Nadarajah, S. (2004).  Multivariate t-distributions and their applications.  Cambridge University Press.
  * Massart, (2007) Massart, P. (2007).  Concentration inequalities and model selection.  Springer.
  * McKay et al., (2000) McKay, M. D., Beckman, R. J., & Conover, W. J. (2000).  A comparison of three methods for selecting values of input variables in the analysis of output from a computer code.  Technometrics, 42(1), 55–61.
  * Papoulis and Pillai, (2002) Papoulis, A. & Pillai, S. U. (2002).  Probability, random variables, and stochastic processes.  Tata McGraw-Hill Education.
  * Paszke et al., (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019).  PyTorch: An imperative style, high-performance deep learning library.  In Advances in Neural Information Processing Systems, (Vol. 32, pp. 8024–8035). Curran Associates, Inc.
  * Virtanen et al., (2020) Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., et al. (2020).  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  Nature Methods, 17, 261–272.