Cref 11affiliationtext: Nagoya Institute of Technology 22affiliationtext:
RIKEN Center for Advanced Intelligent Project 33affiliationtext: Nagoya
University affiliationtext:  {kusakawa.s, takeno.s,
<EMAIL_ADDRESS>{inatsu.yu<EMAIL_ADDRESS><EMAIL_ADDRESS>affiliationtext:
<EMAIL_ADDRESS><EMAIL_ADDRESS> affiliationtext:
<EMAIL_ADDRESS>
# Bayesian Optimization for Cascade-type Multistage Processes

Shunya Kusakawa  Shion Takeno  Yu Inatsu  Kentaro Kutsukake  Shogo Iwazaki
Takashi Nakano  Toru Ujihara  Masayuki Karasuyama  Ichiro Takeuchi

###### Abstract

Complex processes in science and engineering are often formulated as
multistage decision-making problems. In this paper, we consider a type of
multistage decision-making process called a cascade process. A cascade process
is a multistage process in which the output of one stage is used as an input
for the subsequent stage. When the cost of each stage is expensive, it is
difficult to search for the optimal controllable parameters for each stage
exhaustively. To address this problem, we formulate the optimization of the
cascade process as an extension of the Bayesian optimization framework and
propose two types of acquisition functions based on credible intervals and
expected improvement. We investigate the theoretical properties of the
proposed acquisition functions and demonstrate their effectiveness through
numerical experiments. In addition, we consider an extension called suspension
setting in which we are allowed to suspend the cascade process at the middle
of the multistage decision-making process that often arises in practical
problems. We apply the proposed method in a test problem involving a solar
cell simulator, which was the motivation for this study.

##  1 Introduction

(a) Production process of semiconductor chips.

(b) Schematic illustration of a cascade process.

Figure 1:  (a) Example of the cascade manufacturing process for semiconductor
chips. (b) The left part shows a cascade process with $N$ stages, where the
function ${f}^{(n)}$ is the black-box function representing the
$n^{\mathrm{t}h}$ stage for $n\in[N]$. The function ${f}^{(n)}$ considers two
types of inputs: the controllable parameters of that stage $\bm{x}^{(n)}$ and
the output of the previous stage. The goal of the cascade process optimization
is to identify the controllable parameters of all the stages
$\\{\bm{x}^{(n)}\\}_{n\in[N]}$ that optimize the output of the final stage.
The right part shows the fully black-box model view of the problem, where the
function $F$ collectively considers all the controllable parameters
$\\{\bm{x}^{(n)}\\}_{n\in[N]}$ as the inputs. By properly modeling each stage
and incorporating the observable outputs in the middle of the cascade process
$y^{(1)},\ldots,y^{(N-1)}$, more efficient optimization than that of the fully
black-box model $F$ is possible.

A complex process in science and engineering problems is often formulated as a
multistage _cascade_ process. For example, the production process of
semiconductor chips consists of hundreds of process steps such as ingot
growth, wafer slicing, and polishing, device fabrication, and packaging as
shown in Figure 1 (a). Similarly, most manufacturing processes, including
garment manufacturing, automobile manufacturing, and building construction are
multi-stage processes. These multistage processes are often formulated as a
cascade process in which the output of one stage is used as a part of the
input for the subsequent stage.

Figure 1 (b) shows a schematic illustration of a cascade process. Each stage
of a cascade process is formulated as a function with two types of inputs: the
controllable parameters of that stage and the output of the previous stage.
The former is controllable, whereas the latter is uncontrollable because of
the uncertainty in the previous stage. The optimization of the entire cascade
process can be formulated as a joint optimization problem by collectively
considering the controllable parameters of all the stages as the inputs.
Nevertheless, more efficient optimization is possible by properly modeling
each stage and incorporating the observable outputs in the middle of the
cascade process.

In this study, we consider the problem of optimizing a cascade process
composed of black-box functions with expensive evaluation costs within the
framework of Gaussian process-based (GP-based) Bayesian optimization (BO).
Each stage is modeled as a GP, whose inputs consist of controllable parameters
and the outputs from the previous stage. To optimize the output of the final
stage, we consider the identification of the controllable parameters for each
stage by considering the uncertainties of the GP models. The difficulty with
this problem is that when setting the controllable parameters for each stage,
decisions are made by considering the influence of the output of that stage on
the subsequent stages.

Considering the main contribution of this study, we propose a method that
deals with the intractable predictive distribution and develop two acquisition
functions (AFs) based on the expected improvement (EI) and credible interval
(CI). The proposed AFs can quantify the uncertainties of the subsequent stages
in the cascade process using techniques developed in a multistep look-ahead
strategy Ginsbourger and Le Riche, (2010); Lam et al., (2016). The validity of
the AFs was clarified through theoretical analysis, and their effectiveness
was demonstrated using numerical experiments. Furthermore, as generalizations,
we consider extensions of a cascade process optimization problem, such as the
case where suspensions and resumes are possible in the middle of the cascade
process and where the cost of each stage is different. Finally, we apply the
proposed method to a test problem involving a solar cell simulator, which is
the motivation for this study.

#### Related Studies

GP-based BO has been intensively studied as an efficient way to optimize
black-box functions with high evaluation costs Shahriari et al., (2015);
Frazier, (2018). Various types of AFs were proposed for BO, such as Gaussian
process upper confidence bound (GP-UCB) Srinivas et al., (2010) and expected
improvement Močkus, (1975); Jones et al., (1998). The GP-based BO framework
was extended to various problem settings, such as constrained optimization
Gardner et al., (2014); Takeno et al., 2022b , multiobjective optimization
Couckuyt et al., (2014); Suzuki et al., (2020), and multifidelity optimization
Swersky et al., (2013); Takeno et al., (2020); Takeno et al., 2022a .

However, the only existing studies on cascade process optimization using a GP-
based BO framework can be found in Dai Nguyen et al., (2016) and Astudillo and
Frazier, (2021). In CBO Dai Nguyen et al., (2016), the controllable parameters
for each stage are determined in a reverse order (i.e., starting from the
controllable parameters for the last stage, the second last stage, etc). That
is, CBO selects the controllable parameters that are likely to produce the
desired output, which is defined through the inverse function of the
predictive mean function of the GP model in the subsequent stage. Importantly,
since this desired output does not depend on the outputs from the previous
stages, incorporating the observed outputs of the previous stages is difficult
in CBO. Furthermore, if the earlier stages cannot achieve the desired output
(which typically occurs when the range of each stage is unknown), the
algorithm can become stuck. In addition, the exploration-exploitation trade-
off cannot be considered in their method because the uncertainty of each stage
is ignored when the desired output is predetermined by the predictive mean
functions. Recently, a modified version of CBO was proposed in material
science Nakano et al., (2022). However, their approach is to address the
practical application issues of CBO with some heuristics and does not
fundamentally solve the drawbacks of CBO. EI-FN Astudillo and Frazier, (2021)
focuses on the optimization of a function network represented as a directed
acyclic graph (DAG). Whereas their problem settings include the cascade
structure as one of the DAGs, decision-making at each middle stage is not
incorporated. In addition, noisy observations and suspension settings are not
considered in their study. Furthermore, their approach is based on EI with
full sampling (even the final stage), whereas our EI-based approach uses
partial sampling, and we also provide a CI-based AF. Thus, our proposed method
is clearly different from EI-FN.

One important related study is the study on multistep forward time-series
prediction based on GP Quinonero-Candela et al., (2002). In their study, the
output of the GP at a time point becomes the input of the GP at the subsequent
time point. This can be interpreted as a cascade process without controllable
parameters. They introduced an iterative Gaussian approximation method to
approximate the predictive distribution for the multistep forward time points.
However, their method cannot be directly extended to cases with controllable
parameters at each stage. Cascade process optimization is partially related to
BO under input uncertainty because the output of the previous stage with
uncertainty becomes the input of the subsequent stage. Recently, BO under
input uncertainty was intensively studied Beland and Nair, (2017); Oliveira et
al., (2019); Iwazaki et al., (2021); Inatsu et al., (2021, 2022). However,
these existing methods cannot be easily extended to our problem because the
uncertainties in multiple stages are accumulated in a complicated manner in a
cascade process. For example, an approach using the Bayesian quadrature
framework (O’Hagan,, 1991; Beland and Nair,, 2017) cannot model the same
cascade process correctly (see Appendix B for details). In our proposed
method, the expected improvement in the cascade process is computed based on a
multistage look-ahead strategy. Therefore, the BO methods for multistep look-
ahead Ginsbourger and Le Riche, (2010); Lam et al., (2016) are closely related
to our method. In general, the exact evaluation of a look-ahead AF is
difficult owing to its computational complexity. Our proposed method is based
on several computational analyses developed in look-ahead type AFs, especially
batch-type approximations Jiang et al., (2020).

Reinforcement learning (RL) (Sutton and Barto,, 2018; Bertsekas,, 2019) is
also formulated as a multi-stage decision-making problem, which often involves
several uncertainties similar to the output of each stage in the cascade
process. Thus, RL can be casted into the optimization of the cascade process
by setting the state and action as the output from the previous stage and the
input of the current stage, respectively. On the other hand, it is difficult
to directly apply the RL algorithm to our cascade optimization problem because
the problem setup differs in many aspects. For example, while the goal of RL
is to maximize cumulative rewards, the goal of cascade process optimization is
to find optimal input conditions for multiple stages. Furthermore, cascade
process optimization has the limitation that function evaluation is costly and
cannot be performed many times, making it difficult to apply the RL algorithm
under such a limitation.

##  2 Preliminaries

###  2.1 Cascade Process Optimization

We consider a cascade process with $N$ stages. Let
$\bm{x}^{(n)}\in\mathcal{X}^{(n)}\subset\mathbb{R}^{D^{(n)}}$ be a
$D^{(n)}$-dimensional controllable input and
$y^{(n)}\in\mathcal{Y}^{(n)}\subset\mathbb{R}$ be a scalar output of the stage
$n\in[N]:=\\{1,\ldots,N\\}$. Each stage is formulated as a function
$f^{(n)}:\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)}\to\mathcal{Y}^{(n)}$ and
is written as

$y^{(n)}=f^{(n)}(y^{(n-1)},\bm{x}^{(n)}),n\in[N],$ (1)

where we define $y^{(0)}=0$ and $\mathcal{Y}^{(0)}=\\{0\\}$ for notational
simplicity.

Combining all the inputs $\bm{x}^{(1)},\ldots,\bm{x}^{(N)}$, the entire
cascade process can be represented as
$y^{(N)}=F(\bm{x}^{(1)},\ldots,\bm{x}^{(N)})$, where
$F:\mathcal{X}^{(1)}\times\cdots\times\mathcal{X}^{(N)}\to\mathcal{Y}^{(N)}$
is recursively defined using 1. The goal of a cascade process optimization is
to solve the following optimization problem:

$\bm{x}^{(1)}_{*},\dots,\bm{x}^{(N)}_{*}=\operatorname*{arg\,max}_{(\bm{x}^{(1)},\dots,\bm{x}^{(N)})\in\mathcal{X}}F(\bm{x}^{(1)},\dots,\bm{x}^{(N)})$
(2)

with a number of function evaluations as small as possible, where
$\mathcal{X}:=\mathcal{X}^{(1)}\times\cdots\times\mathcal{X}^{(N)}$.

For simplicity, we consider the case in which the output of each stage is
scalar. Furthermore, we assume that the output $y^{(n)}$ is observed without
noise. Extensions to the case of multidimensional output and noisy observation
settings are described in the Appendix.

###  2.2 GP Models

In this study, we employed GP models as surrogate models for black-box
functions. One simple way to model the cascade process is the fully black-box
model view, where we regard $F$ as a single black-box function that outputs
$y^{(N)}$ for a collected input $(\bm{x}^{(1)},\ldots,\bm{x}^{(N)})$. However,
regarding the fully black-box model view, the outputs observed in the
intermediate stages of the cascade process cannot be effectively used.
Therefore, we employ a cascade model , in which all stages are modeled by
independent GP surrogate models. We assume that the prior distribution for
$f^{(n)}$ is $\mathcal{GP}(0,k^{(n)})$, where $\mathcal{GP}(\mu,k)$ denotes a
GP with mean and kernel functions $\mu$ and $k$, respectively. From the
properties of a GP, given the observed data, the posterior distribution of
$f^{(n)},n\in[N]$ is also represented as a GP, and its mean and variance
functions can be obtained in a closed form Rasmussen and Williams, (2005).

##  3 Proposed Method

In this section, we consider the sequential observations of a cascade process
from stage $1$ to $N$. For each iteration $t\in\\{0,N,2N,\ldots\\}$, users
determine $\bm{x}^{(1)}_{t+1}$, a controllable parameter of stage $1$, and
observe an output $y_{t+1}^{(1)}=f^{(1)}(0,\bm{x}^{(1)}_{t+1})$. Subsequently,
users choose $\bm{x}^{(2)}_{t+2}$, a controllable parameter of stage $2$, and
observe $y_{t+2}^{(2)}=f^{(2)}(y^{(1)}_{t+1},\bm{x}^{(2)}_{t+2})$. By
repeating this operation, users obtain
$y^{(N)}_{t+N}=f^{(N)}(y^{(N-1)}_{t+N-1},\bm{x}^{(N)}_{t+N})$.

Regarding the cascade process optimization problem in 2, the following two
points should be considered: First, because the optimization target is the
output of the final stage, a multistep look-ahead is indispensable when a
decision is made in the earlier stages. Second, the input at each stage can be
determined after observing the output of the previous stage. Therefore, when
designing the AF for stage $n$, we need to consider $F(\bm{x}^{(n:N)}\mid
y^{(n-1)})$, where the output of the final stage is represented as a function
of the remaining controllable parameters
$\bm{x}^{(n:N)}:=(\bm{x}^{(n)},\ldots,\bm{x}^{(N)})$ given the output of the
previous stage $y^{(n-1)}$. If the predictive distribution of
$F(\bm{x}^{(n:N)}\mid y^{(n-1)})$ is available, appropriate AFs can be easily
derived for stage $n$. However, in the cascade model, the predictive
distributions of $F(\bm{x}^{(n:N)}|y^{(n-1)})$ cannot be explicitly written
because of the nested structure of the cascade process. To address this
problem, we consider two approaches. First, by utilizing the property that is
easy to sample from nested predictive distributions, we propose an EI-based AF
in section 3.1. Second, by constructing the credible interval of
$F(\bm{x}^{(n:N)}|y^{(n-1)})$, we propose a CI-based AF in section 3.2.

###  3.1 EI-based Acquisition Function

In this subsection, we assume that the true black-box function $f^{(n)}$ is
sampled from the GP prior $\mathcal{G}\mathcal{P}(0,k^{(n)})$ for each
$n\in[N]$. Let $F_{\text{best}}=\max_{1\leq t^{\prime}\leq
t}y^{(N)}_{t^{\prime}}$ be the maximum value of the objective function $F$
observed up to iteration $t$. Thereafter, we define the improvement
$U_{n}({\bm{x}}^{(n)}|{y}^{(n-1)})$ for the observation of stage $n$ with
input $({y}^{(n-1)},{\bm{x}}^{(n)})$ as the expected improvement of
$F_{\text{best}}$. First, in the case of $n=N$, $F_{\text{best}}$ is improved
when $f^{(N)}({y}^{(N-1)},\bm{x}^{(N)})>F_{\text{best}}$. Therefore, the
expected improvement of $F_{\text{best}}$, $U_{N}(\bm{x}^{(N)}|y^{(N-1)})$, is
given by:

$U_{N}(\bm{x}^{(N)}|y^{(N-1)})=\mathbb{E}_{f^{(N)}}\left[\left(F(\bm{x}^{(N)}|y^{(N-1)})-F_{\text{best}}\right)^{+}\right],$
(3)

where $(\cdot)^{+}\coloneqq\max(0,\cdot)$. Equation 3 is the same formulation
as in the ordinary EI, and its expectation can be calculated analytically.

With regard to the case of $n\neq N$, we define
$U_{n}(\bm{x}^{(n)}|y^{(n-1)})$ as the maximum expected improvement of
$F(\bm{x}^{(n:N)}|y^{(n-1)})$:

$U_{n}(\bm{x}^{(n)}|y^{(n-1)})=\mathbb{E}_{f^{(n)}}\left[\max_{\bm{x}^{(n+1)}}U_{n+1}(\bm{x}^{(n+1)}|y^{(n)})\right].$
(4)

Equation 4 is a recursive expression that contains the max operator and
expectation. Thus, it is difficult to calculate it analytically. In the
context of multistep look-ahead approaches, methods to avoid this problem
through approximation and sampling have been investigated Lam et al., (2016);
González et al., 2016b ; Wu and Frazier, (2019); Jiang et al., (2020). We use
the similar approach as in Jiang et al., (2020) to approximate the lower bound
of 4. Using the Monte Carlo integration with $S$ samples and the exchange of
expectation and max operators (note that 5a contains the nested max operators
and expectation), 4 can be approximated as follows:

$\displaystyle{U}_{n}(\bm{x}^{(n)}|y^{(n-1)})$
$\displaystyle=\mathbb{E}_{f^{(n)}}\left[\max_{\bm{x}^{(n+1)}}\cdots\mathbb{E}_{f^{(N-1)}}\left[\max_{\bm{x}^{(N)}}U_{N}(\bm{x}^{(N)}|y^{(N-1)})\right]\right]$
(5a)
$\displaystyle\geq\max_{\bm{x}^{(n+1)},\dots,\bm{x}^{(N)}}\mathbb{E}_{f^{(n)},\ldots,f^{(N-1)}}\left[U_{N}(\bm{x}^{(N)}|y^{(N-1)})\right]$
(5b)
$\displaystyle\approx\max_{\bm{x}^{(n+1)},\dots,\bm{x}^{(N)}}\frac{1}{S}\sum_{s=1}^{S}U_{N}(\bm{x}^{(N)}|y_{s}^{(N-1)}),$
(5c)

where the inequality 5b can be derived by Jiang et al., (2020), and the
sampling of $y^{(N-1)}_{s}$ is based on the GP model. First, we generate each
$y^{(n)}_{s}$ from the predicted distribution of
${f}^{(n)}(y^{(n-1)},\bm{x}^{(n)})$ independently. Then, we calculate the
predicted distribution of ${f}^{(n+1)}(y^{(n)}_{s},\bm{x}^{(n+1)})$ using the
generated $y^{(n)}_{s}$, and we generate $y^{(n+1)}_{s}$ based on that. By
repeating this process, $y^{(N-1)}_{s}$ can be generated. We propose the
approximated utility function $\widetilde{U}_{n}(\bm{x}^{(n)}|y^{(n-1)})$,
defined as 5c, as the EI-based AF. Therefore, given the observation
$y_{t+n-1}^{(n-1)}$ of the previous stage, the observation point of the
subsequent stage $n$ is given by:

${\bm{x}}^{(n)}_{t+n}=\operatorname*{arg\,max}_{{\bm{x}}^{(n)}\in\mathcal{X}^{(n)}}\widetilde{U}_{n}(\bm{x}^{(n)}|y_{t+n-1}^{(n-1)}).$
(6)

Although 5c is the optimization problem for a stochastically determined
function, deterministic gradient-based methods can be applied by applying the
reparameterization trick Kingma and Welling, (2014). Compared to EI-FN, which
approximates all expectations by the Monte Carlo estimation, we analytically
calculate the expectation with respect to $f^{(N)}$ in 5c. Furthermore, we
select the controllable input in each stage depending on the output from the
previous stage by using 6 in contrast to EI-FN which does not incorporate
intermediate observations.

###  3.2 CI-based Acquisition Function

Thus far, we assume that each $f^{(n)}$ is sampled from the GP prior.
Hereafter, we assume that each $f^{(n)}$ is an element of a reproducing kernel
Hilbert space (RKHS). Under this RKHS setting, we propose a CI-based AF that
can be interpreted as an optimistic improvement. First, we provide a credible
interval of $F(\bm{x}^{(n:N)}|y^{(n-1)})$ and then, design the AF. To
construct a valid CI, we assume the following regularity assumptions.

#### Regularity Assumptions

We assume that $\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)}$ is a compact set,
and let $k^{(n)}$ be a positive definite kernel with
$k^{(n)}(({w},{\bm{x}}),({w},{\bm{x}}))\leq 1$ for any $n\in[N]$ and
$({w},{\bm{x}})\in\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)}$. Furthermore,
let $\mathcal{H}_{k^{(n)}}$ be an RKHS corresponding to the kernel $k^{(n)}$.
Additionally, for each $n\in[N]$, we assume that
$f^{(n)}\in\mathcal{H}_{k^{(n)}}$ and $\|f^{(n)}\|_{{k^{(n)}}}\leq B$, where
$B>0$ is a constant, and $\|\cdot\|_{{k^{(n)}}}$ denotes the RKHS norm on
$\mathcal{H}_{k^{(n)}}$. There are several studies on BO using a GP model for
the black-box function assumed as an element of an RKHS Srinivas et al.,
(2010); Oliveira et al., (2019); Iwazaki et al., (2021).

To construct the credible interval of $F(\bm{x}^{(n:N)}|y^{(n-1)})$, we first
formally define a posterior mean and variance of a GP with independent
Gaussian noise $\mathcal{N}(0,\sigma^{2})$. Note that what we have just
introduced is the noise model $\mathcal{N}(0,\sigma^{2})$ of a GP, and the
actual observations are still noiseless. For each $n\in[N]$,
$(w,{\bm{x}})\in\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)}$ and $t\geq 1$, let
$\mu^{(n)}_{t}(w,{\bm{x}})$ and $\sigma^{(n)2}_{t}(w,{\bm{x}})$ be the
posterior mean and variance of $f^{(n)}(w,{\bm{x}})$, respectively. The
interval
$[\mu^{(n)}_{t}(w,{\bm{x}})\pm\beta^{1/2}\sigma^{(n)}_{t}(w,{\bm{x}})]$ with
an appropriate trade-off parameter $\beta$ is the credible interval for
$f^{(n)}(w,{\bm{x}})$ Srinivas et al., (2010). We apply this interval to
construct a valid credible interval for $F(\bm{x}^{(n:N)}|y^{(n-1)})$.
However, it cannot be used directly because it has an uncontrollable variable
$w$. To avoid this issue, we additionally consider the following assumptions.

#### Lipschitz Continuity Assumptions

We assume that $f^{(n)}$ and $\sigma^{(n)}_{t}$ satisfy the following
assumptions:

(L1)

Assume that $f^{(n)}$ is $L_{f}$-Lipschitz continuous with respect to
$L_{1}$-distance for any $n\in\\{2,\ldots,N\\}$, where $L_{f}>0$ is a
Lipschitz constant.

(L2)

Assume that $\sigma^{(n)}_{t}$ is $L_{\sigma}$-Lipschitz continuous with
respect to $L_{1}$-distance for any $n\in\\{2,\ldots,N\\}$ and $t\geq 1$,
where $L_{\sigma}>0$ is a Lipschitz constant.

This assumption enables us to give the CI of the output using the CI of the
input. Since the output becomes the input of the next stage in the cascade
process, CIs of the subsequent stages can be constructed in a chain reaction.

Under these assumptions, we introduce a credible interval of
$F(\bm{x}^{(n:N)}|y^{(n-1)})$ using a cascade model.

######  Theorem 3.1.

Let

$\displaystyle\tilde{{\mu}}^{(m)}_{t}(\bm{x}^{(n:m)}|y^{(n-1)})$
$\displaystyle={\mu}^{(m)}_{t}\left(\tilde{{\mu}}^{(m-1)}_{t}(\bm{x}^{(n:m-1)}|y^{(n-1)}),\;\bm{x}^{(m)}\right),$
(7) $\displaystyle\tilde{\sigma}^{(m)}_{t}(\bm{x}^{(n:m)}|y^{(n-1)})$
$\displaystyle={\sigma}^{(m)}_{t}\left(\tilde{{\mu}}^{(m-1)}_{t}(\bm{x}^{(n:m-1)}|y^{(n-1)}),\;\bm{x}^{(m)}\right)+L_{f}\tilde{\sigma}^{(m-1)}_{t}(\bm{x}^{(n:m-1)}|y^{(n-1)}),$

where
$\tilde{\mu}^{(n)}_{t}({\bm{x}}^{(n)}|y^{(n-1)})={\mu}^{(n)}_{t}(y^{(n-1)},{\bm{x}}^{(n)})$
and
$\tilde{\sigma}^{(n)}_{t}({\bm{x}}^{(n)}|y^{(n-1)})={\sigma}^{(n)}_{t}(y^{(n-1)},{\bm{x}}^{(n)})$.
Assume that regularity assumptions and the Lipschitz continuity assumption
(L1) hold. Also assume that
$\tilde{\mu}^{(m)}_{t}({\bm{x}}^{(n:m)}|y^{(n-1)})\in\mathcal{Y}^{(n)}$ for
all $m\in[N]$, $t\geq 1$ and ${\bm{x}}^{(n:m)}$. Define $\beta=B^{2}$. Then,
the following holds:

$|F(\bm{x}^{(n:N)}|y^{(n-1)})-\tilde{\mu}^{(N)}_{t}(\bm{x}^{(n:N)}|y^{(n-1)})|\leq\beta^{1/2}\tilde{\sigma}^{(N)}_{t}(\bm{x}^{(n:N)}|y^{(n-1)}).$
(8)

From Theorem 3.1, a lower confidence bound
$\mathrm{LCB}^{(F)}_{t}(\bm{x}^{(n:N)}|y^{(n-1)})$ and an upper confidence
bound $\mathrm{UCB}^{(F)}_{t}(\bm{x}^{(n:N)}|y^{(n-1)})$ of
$F(\bm{x}^{(n:N)}|y^{(n-1)})$ are given by:

$\displaystyle\mathrm{LCB}^{(F)}_{t}(\bm{x}^{(n:N)}|y^{(n-1)})$
$\displaystyle=\tilde{\mu}^{(N)}_{t-1}(\bm{x}^{(n:N)}|y^{(n-1)})-\beta^{1/2}\tilde{\sigma}^{(N)}_{t-1}(\bm{x}^{(n:N)}|y^{(n-1)}),$
(9) $\displaystyle\mathrm{UCB}^{(F)}_{t}(\bm{x}^{(n:N)}|y^{(n-1)})$
$\displaystyle=\tilde{\mu}^{(N)}_{t-1}(\bm{x}^{(n:N)}|y^{(n-1)})+\beta^{1/2}\tilde{\sigma}^{(N)}_{t-1}(\bm{x}^{(n:N)}|y^{(n-1)}).$

Based on the above credible intervals, we define the pessimistic maximum
estimator of $F(\bm{x}^{(1:n)})$ as
$Q_{t}\coloneqq\max_{\bm{x}^{(1:N)}}\mathrm{LCB}^{(F)}_{t}(\bm{x}^{(1:N)})$.
In addition, given the observation $y_{t+n-1}^{(n-1)}$ in stage $n-1$, we
define the pessimistic maximum estimator of $F(\bm{x}^{(n:N)}|y^{(n-1)})$ as
follows:

$\mathrm{LCB}^{(F)}_{t+n}(y_{t+n-1}^{(n-1)})=\max_{\bm{x}^{(n:N)}}\mathrm{LCB}^{(F)}_{t+n}(\bm{x}^{(n:N)}|y_{t+n-1}^{(n-1)}),$
(10)

where the $\max$ operator is not necessary when $n=N$. Similarly, the
optimistic maximum estimator of $F(\bm{x}^{(n:N)}|y_{t+n-1}^{(n-1)})$ is
defined as follows:

$\displaystyle\mathrm{UCB}^{(F)}_{t+n}({\bm{x}}^{(n)}|y_{t+n-1}^{(n-1)})\coloneqq\max_{\bm{x}^{(n+1:N)}}\mathrm{UCB}^{(F)}_{t+n}(\bm{x}^{(n:N)}|y_{t+n-1}^{(n-1)}).$
(11)

Then, we define the optimistic improvement with respect to
$(y^{(n-1)},{\bm{x}}^{(n)})$ as follows:

$a^{(n)}_{t+n}({\bm{x}}^{(n)}|y_{t+n-1}^{(n-1)})=\mathrm{UCB}^{(F)}_{t+n}({\bm{x}}^{(n)}|y_{t+n-1}^{(n-1)})-\max\left\\{\mathrm{LCB}^{(F)}_{t+n}(y_{t+n-1}^{(n-1)}),\>Q_{t+n}\right\\}.$
(12)

Furthermore, we define the maximum uncertainty

$b^{(n)}_{t+n}({\bm{x}}^{(n)}|{y}_{t+n-1}^{(n-1)})=\max_{{{\bm{x}}^{(n+1:N)}}}\tilde{\sigma}^{(N)}_{t+n-1}(\bm{x}^{(n:N)}|{y}_{t+n-1}^{(n-1)}).$
(13)

Using 12 and 13, we propose a CI-based AF
$c^{(n)}_{t+n}({\bm{x}}^{(n)}|{y}_{t+n-1}^{(n-1)})$:

$c^{(n)}_{t+n}({\bm{x}}^{(n)}|{y}_{t+n-1}^{(n-1)})=\max\left\\{a^{(n)}_{t+n}({\bm{x}}^{(n)}|{y}_{t+n-1}^{(n-1)}),\eta_{t}b^{(n)}_{t+n}({\bm{x}}^{(n)}|{y}_{t+n-1}^{(n-1)})\right\\},$
(14)

where $\eta_{t}$ is some learning rate and tends to zero. Therefore, the
subsequent observation point is given by
$\bm{x}^{(n)}_{t+n}\coloneqq\operatorname*{arg\,max}_{\bm{x}^{(n)}\in\mathcal{X}^{(n)}}c^{(n)}_{t+n}(\bm{x}^{(n)}|y_{t+n-1}^{(n-1)})$.

Equation 10 denotes the pessimistic maximum when we observe in the subsequent
stages with the previous output, and $Q_{t}$ represents the pessimistic
maximum when the observation is performed from the first stage. Thus, the
second term of 12 indicates a pessimistic maximum estimator in the current
iteration, and $a^{(n)}_{t}$ optimistically evaluates how much the observed
value exceeds the pessimistically estimated maximum value. Intuitively, CI-
based AF selects the point that has high optimistic improvement, and if no
optimistic improvement is expected (i.e., $a^{(n)}_{t}$ is small), it selects
the point with the highest uncertainty of the cascade process.

The Lipschitz constant $L_{f}$ is a new parameter derived from our proposed
method. Since each $f^{(n)}$ is a black-box function, it is difficult to
obtain the exact value of $L_{f}$. In practice, we have to estimate $L_{f}$,
and one simple way is to determine it from prior knowledge. Another way is to
estimate it from a GP surrogate model. For any Lipschitz continuous function
$f$ on a compact set $\mathcal{X}\subset\mathbb{R}^{d}$,
$\bar{L}=\max_{\bm{x}\in\mathcal{X}}\|\nabla f(\bm{x})\|_{1}$ satisfies the
Lipschitz condition González et al., 2016a . Additionally, it is known that if
a GP is differentiable, its derivative is also a GP. Based on these facts, we
can estimate $L_{f}$ by constructing a GP surrogate model of $\nabla f$ and
using its sample paths and predictive mean Sui et al., (2015); González et
al., 2016a . On the other hand, for the Lipschitz continuity assumption (L2),
it depends on how the kernel function is chosen. If we use a kernel that does
not consider any similarity between different points, i.e., a pathological
kernel such as $k({\bm{x}},{\bm{x}}^{\prime})=1$ if
${\bm{x}}={\bm{x}}^{\prime}$, and otherwise zero, the posterior standard
deviation is discontinuous at the observed points, and (L2) does not hold. On
the other hand, (L2) is shown to hold for commonly used kernels such as linear
kernels, Gaussian kernels, and Matérn kernels with more than one degree of
freedom (see Appendix E for details).

We discuss the multidimensional output setting and the noisy observation
setting in the Appendix. Particularly in noisy situations, two different
target functions can be considered. One is to maximize $F$ through noisy
observations, and the other is to maximize the expected final output with
respect to the noise at each stage. We also propose the modified version of
CI-based AFs for both target functions and show the theoretical analyses of
them in Appendix D.

##  4 Theoretical Results

In this section, we provide the theoretical guarantee for the CI-based AF.
First, we define the estimated solution
$\hat{\bm{x}}_{t}^{(1)},\dots,\hat{\bm{x}}_{t}^{(N)}$ and regret $r_{t}$ at
iteration $t$ as follows:

$\displaystyle\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t}=\operatorname*{arg\,max}_{\bm{x}^{(1:N)}\in\mathcal{X},1\leq\tilde{t}\leq
t}\mathrm{LCB}^{(F)}_{\tilde{t}}(\bm{x}^{(1:N)}),$ (15) $\displaystyle
r_{t}=F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t}).$
(16)

Then, the following theorem holds.

######  Theorem 4.1.

Under the same assumptions as in Theorem 3.1, define the estimated solution
$(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})$ by 15. Then, for any
positive number $\xi$, the following holds:

$\displaystyle\max_{\bm{x}^{(1:N)}}\mathrm{UCB}^{(F)}_{t}(\bm{x}^{(1:N)})-\max_{\bm{x}^{(1:N)}}\mathrm{LCB}^{(F)}_{t}(\bm{x}^{(1:N)})<\xi$
(17) $\displaystyle\Rightarrow
F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})<\xi.$

Theorem 4.1 states that if the credible interval width for $F$ is small, then
regret $r_{t}$ is also small. On the contrary, it does not guarantee whether
the credible interval width becomes small or not. Theorem 4.2 shows that the
interval width can be made arbitrarily small when 14 is used as the AF. Let
$\gamma^{(n)}_{t}$ be a maximum information gain for $f^{(n)}$ at iteration
$t$, and let $\gamma_{t}=\max_{n\in[N]}\gamma_{t}^{(n)}$. Here, the maximum
information gain is a commonly used sample complexity measure in the context
of the GP-based BO Srinivas et al., (2010). The exact formulation is provided
in Appendix A. The following theorem also holds.

######  Theorem 4.2.

Assume that the same conditions as in Theorem 3.1 hold. Also assume that the
Lipschitz continuity assumption (L2) holds. Let $\xi$ be a positive number,
and let $\eta_{t}=(1+\log t)^{-1}$. Then, the following inequality holds after
at most $T$ iterations:

$F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{T},\ldots,\hat{\bm{x}}^{(N)}_{T})<\xi,$
(18)

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

$\frac{8\beta
C^{2}_{4}N^{3}}{\log(1+\sigma^{-2})}\gamma_{T}\eta^{-2N-2}_{T}T^{-1}<\xi^{2}.$
(19)

Here, each constant is given by
$C_{0}=L_{\sigma}\beta^{1/2}+L_{f}+1,C_{1}=\max\\{1,L_{f},L^{-1}_{f}\\},C_{2}=4N^{2}C^{2N-3}_{0}C^{N}_{1},C_{3}=NC^{N}_{2},C_{4}=(2\beta^{1/2}+2)^{N}C^{N}_{3}$.

The inequality 19 still has the variable $\gamma_{T}$. Nevertheless, the order
of $\gamma_{T}$ for commonly used kernels such as the linear and Gaussian
kernels is sub-linear under mild conditions Srinivas et al., (2010). Hence,
the integer $T$ satisfying 19 exists in these cases. This indicates that a
solution $\hat{\bm{x}}^{(1)}_{T},\ldots,\hat{\bm{x}}^{(N)}_{T}$ that achieves
an arbitrary accuracy $\xi$ can be obtained in a finite number of
observations.

In terms of the stopping criterion, if the accuracy parameter $\xi$ is
provided, we can use the condition 17 as the stopping criterion for EI- and
CI-based AFs. Although EI-based AF is not necessarily terminated by this
stopping criterion, Theorem 4.2 shows that CI-based AF terminates after at
most $T$ iteration that satisfies 19 when all assumptions hold.

##  5 Extensions

In this section, we consider an extension called _suspension_ setting in which
we are allowed to suspend the cascade process in the middle of the multistage
decision-making process. Suspension is beneficial, especially when the output
of a middle stage is significantly different from the prediction, and the
output is not expected to be beneficial for the subsequent stages. For
example, if a suspension occurs at stage $n$, the output $y^{(n-1)}$ of the
previous stage remains unused, and this can be stored as a _stock_. If a
stored stock turns out to be useful later, we can reuse the stock and resume
the cascade process from the middle stage.

#### Formulation

Let $\mathcal{S}_{t}^{(n)}$ be the set of stocks at stage
$n\in\\{0,...,N-1\\}$ in iteration $t$ 111We set
$\mathcal{S}_{t}^{(0)}=\\{{0}\\}$ for all $t$.. Because the process can be
resumed from the middle stage in the suspension setting, the user’s task in
each iteration $t$ is to select the best pair $(y^{(n-1)},\bm{x}^{(n)})$ from
the set of candidates
$\\{\mathcal{S}_{t}^{(n)}\times\mathcal{X}^{(n)}\\}_{n=0}^{N-1}$. Because of a
user’s choice, the used stock $y^{(n-1)}$ is removed from the set of stocks,
and the newly obtained output $y^{(n)}$ is added to the set of stocks. The
difference in the cost of each stage is important in the suspension setting
because, for example, if the costs of the later stages are greater than those
of former stages, then the suspension strategy can be more beneficial.
Therefore, we introduce the cost of each stage $\lambda^{(n)}>0$ for
$n\in[N]$. Figure 2 shows a conceptual diagram of the suspension setting.

(a) Suspension

(b) Resumption

Figure 2:  Conceptual diagram of the suspension setting. 2(a) shows the case
where the output $y^{(n)}$ is stored as a stock in stage $n$, and the
observation from the subsequent stage is suspended. 2(b) shows the case where
the observation is reused from stage two using the stock $y^{(1)}_{b}$.

#### Acquisition function for suspension setting

We propose the following AF for the suspension setting:

$n_{t},\bm{y}_{t}^{(n-1)},\bm{x}_{t}^{(n)}=\operatorname*{arg\,max}_{\mathclap{\begin{subarray}{c}i\in[N],\\\
y^{(i-1)}\in\mathcal{S}_{t}^{(i-1)},\\\
\bm{x}^{(i)}\in\mathcal{X}^{(i)}\end{subarray}}}\widetilde{U}_{i}(y^{(i-1)},\bm{x}^{(i)})/\sum_{j=i}^{N}\lambda^{(j)}.$
(20)

There are two differences between the AF in 20 and the EI-based AF in 5c.
First, in 20, based on the set of stocks
$\\{\mathcal{S}_{t}^{(i-1)}\\}_{i\in[N]}$, we determine which stage to resume
from, which stock to use, and what input to use. Thus, 20 implicitly
determines whether the sequential evaluation in cascade is suspended or not.
Second, the utility is divided by the total cost from stages $n$ to $N$, which
suggests that a cost-effective choice is performed. Resuming from a later
stage has advantages (considering cost) because the goal is to optimize the
output of the final stage. The AF in 20 can be interpreted as an extension of
the EI-based AF in 5c because it handles the two cases of starting from the
first stage and resuming from the middle stage using a stock. It is necessary
to compute the utility function for many candidates when solving the
optimization problem in 20. Nonetheless, this can be done efficiently by
exploiting the fact that the evaluation of $\widetilde{U}_{n}$ in stage $n$
does not depend on the observations in the earlier stages.

#### Stock Reduction

In the suspension setting, having a larger number of stocks provides us a
wider choice. However, practically, it can be costly to store several stocks.
In such a situation, it is necessary to be able to decide which stocks to
retain and which ones to discard. A reasonable way is to discard the stocks
that are not expected to contribute to the optimal solution. We implement this
based on the credible interval.

For any stock $y^{(n)}\in\mathcal{S}^{(n)}$ in stage $0\leq n\leq N-1$, let

$F(y^{(n)})=\max_{\bm{x}^{(n+1:N)}}F(\bm{x}^{(n+1:N)}|y^{(n)})$ (21)

be the maximum function value when the observation is performed until the
final stage using $y^{(n)}$. Therefore, the LCB and UCB of $F(y^{(n)})$ are
given as

$\displaystyle\mathrm{LCB}^{(F)}_{t}({y}^{(n)})$
$\displaystyle=\max_{\bm{x}^{(n+1:N)}}\mathrm{LCB}^{(F)}_{t}(\bm{x}^{(n+1:N)}|y^{(n)}),$
(22) $\displaystyle\mathrm{UCB}^{(F)}_{t}({y}^{(n)})$
$\displaystyle=\max_{\bm{x}^{(n+1:N)}}\mathrm{UCB}^{(F)}_{t}(\bm{x}^{(n+1:N)}|y^{(n)}).$
(23)

Then, the following theorem holds.

######  Theorem 5.1.

For any $n\in[N-1]$ and ${y}^{(n)}\in\mathcal{S}^{(n)}$, under the same
assumptions as in Theorem 3.1, assume that the following holds:

$\mathrm{UCB}^{(F)}_{t}({y}^{(n)})<\max_{\tilde{y}\in\bigcup_{s=0}^{N-1}\mathcal{S}_{t}^{(s)}}\mathrm{LCB}^{(F)}_{t}(\tilde{y}^{(s)}).$
(24)

Then, $F({y}^{(n)})<F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
holds.

The proof of the theorem is presented in Appendix C. From Theorem 5.1, the
condition 24 is used to decide which stocks to discard. Theorem 5.1 only
guarantees that the stock will not become the optimal value. Suboptimal stocks
may also be effectively used in the optimization process.

##  6 Experiments

Figure 3:  Experimental results of the synthetic functions. The solid line
represents the average performance, and the error bar represents the standard
error.

Figure 4:  Results of the solar cell simulator. The right plot is an enlarged
version of the left plot.

Figure 5:  Results of the hydrogen plasma treatment.

(a) $\bm{\lambda}=(1,1,1)$

(b) $\bm{\lambda}=(1,1,10)$

(c) Stock reuse

Figure 6:  Results in extension setting. In the above experiments for sample
paths, a solid line implies the methods with suspension and a dashed line
represents a sequential method.

We demonstrated the optimization performance of the proposed methods in both
synthetic functions and a solar cell simulator. Details of the experimental
settings are provided in Appendix F. First, we compared the methods in the
sequential setting. We used CBO, EI-FN and random sampling (Random) as the
comparison methods. In Random, each $\bm{x}^{(n)}\in\mathcal{X}^{(n)}$ is
randomly and uniformly selected. Regarding CBO, its AF is optimized by
considering the output of the previous stage as the controllable variable.
Because the range of the previous output is unknown, we used a widely
estimated range that was twice the actual range. Additionally, we set its
hyperparameters $\kappa_{1},\kappa_{2}$ to one. We also compared the proposed
methods to a fully black-box BO that used EI and GP-UCB under a fully black-
box model (FB-EI, FB-UCB). The proposed methods with EI- and CI-based AFs are
labeled as EI-based and CI-based, respectively. We set the number of Monte
Carlo sampling to $S=1000$, and we used $\eta_{t}=10^{-4}(1+\log t)^{-1}$ to
calculate CI-based. In all the experiments, we employed a Gaussian kernel
$k^{(n)}\left((w,\bm{x}),(w^{\prime},\bm{x}^{\prime})\right)=\sigma^{(n)}_{f}\exp\left(-\frac{(w-w^{\prime})^{2}}{2\ell_{w}^{2\>(n)}}-\sum_{d=1}^{D^{(n)}}\frac{(\bm{x}_{d}-\bm{x}^{\prime}_{d})^{2}}{2\ell_{d}^{2\>(n)}}\right)$
and we set the noise variance of the GP model as $\sigma^{2}=10^{-4}$. The
performance was evaluated by the simple regret
$F(\bm{x}^{(1)}_{*},\dots,\bm{x}^{(N)}_{*})-F(\bm{x}^{(1)}_{\bar{t}},\dots,\bm{x}^{(N)}_{\bar{t}})$,
where $\bar{t}=\operatorname*{arg\,max}_{1\leq t^{\prime}\leq
t}y^{(N)}_{t^{\prime}}$. Additional results comparing EI-based and EI-FN are
shown in Appendix G.

###  6.1 Synthetic Functions

We used sample paths from the GP priors, Rosenbrock function, Sphere function,
and Matyas function as the synthetic functions. Regarding both functions, we
constructed three- and five-stage cascade processes, and set $D^{(n)}=2$ for
all $n$. We used $L_{f}=1,\beta^{1/2}=2$ for the calculation 9. In addition,
10 and 20 points for $N=3$ and $N=5$ were randomly selected and provided as
the initial data.

#### Sample Paths from GP Priors:

We employed the random Fourier feature Rahimi and Recht, (2008) to sample
${f}^{(n)}$ from the GP prior and constructed $F$ using them. Each ${f}^{(n)}$
was sampled ten times, and the experiments were conducted with two different
random seeds for each. The hyperparameters were set to
$\sigma^{(n)}_{f}=15.02,\ell_{d}^{(n)}=3,\ell_{w}^{(n)}=3$. We also set the
domain of the control parameter to $\mathcal{X}^{(n)}=[-10,10]^{D^{(n)}}$.

For the following synthetic functions, we ran experiments with 20 different
random seeds. Furthermore, we scaled ${f}^{(n)}$ such that the range of the
function value is equal to the input domain for numerical stability. The GP
hyperparameters were selected by maximizing the marginal likelihood at every
iteration.

#### Rosenbrock Function:

Each ${f}^{(n)}$ is Rosenbrock function, whose domain of the control
parameters were set to $\mathcal{X}^{(n)}=[-2,2]^{D^{(n)}}$. We perform the
experiments with the number of stages $N=3$ and $5$. We set
$\bm{x}^{(1)}\in\mathbb{R}^{3}$ and $\bm{x}^{(n)}\in\mathbb{R}^{2}$ for each
$n=2,\dots,N$, and output $y^{(n)}\in\mathbb{R}$ for $n\in[N]$.

#### Sphere function:

Each ${f}^{(n)}$ is Sphere function, whose domain of the control parameters
were set to $\mathcal{X}^{(n)}=[-5.12,5.12]^{D^{(n)}}$. Each output
$y^{(n)}\in\mathbb{R}$ for $n\in[N]$ and the number of stages is $N=3$. We set
$\bm{x}^{(1)}\in\mathbb{R}^{3}$ and
$\bm{x}^{(2)},\bm{x}^{(3)}\in\mathbb{R}^{2}$.

#### Matyas function:

Each ${f}^{(n)}$ is Matyas function, whose domain of the control parameters
were set to $\mathcal{X}^{(n)}=[-10,10]^{D^{(n)}}$. Each output
$y^{(n)}\in\mathbb{R}$ for $n\in[N]$ and the number of stages is $N=3$. We set
$\bm{x}^{(1)}\in\mathbb{R}^{2}$ and $x^{(2)},x^{(3)}\in\mathbb{R}^{1}$.

Figure 3 shows the average value of the simple regret. We see that our
proposed methods and EI-FN clearly outperform other baselines including CBO.
Although EI-based, which can be roughly seen as the adaptive version of EI-FN,
is comparable to EI-FN in most experiments, EI-based shows better performance
than EI-FN in the Sphere function. This can be seen as a benefit of adaptive
decision-making. Although CI-based has superior theoretical properties, CI-
based is inferior to EI-based except for Rosenbrock ($N=3$) and Matyas
functions. One of the reasons for these results is the setting of the
hyperparameters, such as $\beta$ and $L_{f}$.

###  6.2 Solar Cell Simulator

We applied the proposed methods to the solar cell simulator. This simulator
consists of three-stage processes. Stages one and two are two-step annealing
processes to diffuse phosphorus into the silicon substrate from the surface,
forming a p-n junction near the surface. The controllable parameters of stage
one are the phosphorus concentration at the surface, temperature, and time of
the first-step annealing. In addition, the controllable parameters of stage
two are the temperature and time of the second-step annealing. The outputs of
stages one and two are the four parameters that indicate the distribution of
phosphorus concentration in the depth direction. In stage three, the solar
cell is constructed using controllable parameters composed of wafer thickness
and boron concentration of the substrate, and the performance is evaluated
under standard measurement conditions. The final output is the power
generation efficiency of the solar cell, and our goal is to maximize this
output. Regarding the real-world simulators, the simulators of stages one and
two are based on the physical model Bentzen, (2006). Moreover, the simulator
of stage three was constructed using the data collected from PC1Dmod6.2 Haug
and Greulich, (2016). In stages one and two, the simulators produce vector
outputs. However, CBO does not support vector outputs, so we calculated its AF
by replacing the predictive mean and variance with the mean vector and
covariance matrix, respectively. The domain of the controllable parameters are
$\mathcal{X}^{(1)}=[700,1050]\times[100,5000]\times[19,21.18]$,
$\mathcal{X}^{(2)}=[700,1050]\times[100,5000]$, and
$\mathcal{X}^{(3)}=[50,250]\times[14,17]$. We randomly chose 20 points as the
initial data. In addition, we set $L_{f}=0.1,\beta^{1/2}=2$ in this setting.
Furthermore, we tuned the hyperparameters by maximizing the marginal
likelihood and ran the experiment for 50 iterations using 20 different random
seeds.

Figure 4 shows the average of the best observed value $\max_{1\leq
t^{\prime}\leq t}y^{(N)}_{t^{\prime}}$. This result shows that the proposed
method outperforms the existing methods in the simulator experiments. It is
also confirmed that the best value found in 50 iterations in the existing
methods is achieved in less than half of the iterations in the proposed
method. In a comparison between EI-based and EI-FN, the error bars are not
overlapped after the $40$ iteration. Thus, EI-based shows a slightly small but
substantial improvement by adaptive decision-making.

###  6.3 Hydrogen Plasma Treatment Process

We applied the proposed method to the hydrogen plasma treatment (HPT) process,
which is a part of the production process of solar cells. In the previous
practical study, one of the authors (KK) optimized one-stage HPT process
parameters through real experiments using simple BO (Miyagawa et al., 2021b, ;
Miyagawa et al., 2021a, ). In this study, we extended this HPT process to the
virtual two-stage cascade process. The first stage is the HPT process with 7
inputs, temperature, pressure, flow rate, process time, electrode distance,
radio frequency power, and cycle time, and 2 outputs, saturation current
density, and contact resistance. The second process is the solar cell
production process in which surface electrode width is the controllable
parameter. The final output is the power generation efficiency of the solar
cell, and our goal is to maximize this output as in the case of the solar cell
simulation. The domain of the controllable parameters are
$\mathcal{X}^{(1)}=[50,300]\times[0.25,4]\times[100,1000]\times[10,100]\times[270,420]\times[10,40]\times[15,60]$
and $\mathcal{X}^{(2)}=[0.01,0.1]$. Since the real dataset is small with
respect to the input domain, we used surrogate objectives, which are sample
paths of GPs fitting to the real dataset for each stage. The details of these
sample paths are shown in Appendix F. Other experimental settings are set as
with the solar cell simulator experiment.

Figure 5 shows the average of the best observed value $\max_{1\leq
t^{\prime}\leq t}y^{(N)}_{t^{\prime}}$. Our proposed methods EI-based and CI-
based are superior to other baselines including EI-FN and CBO. In particular,
the difference between EI-based and EI-FN implies the improvement by adaptive
decision-making.

###  6.4 Suspension Setting

We also conducted experiments in a suspension setting using the proposed
method 20 (EI-based-SUS). In this setting, we used the sample path function
with $N=3$ and $5$. For the cost of each stage
$\bm{\lambda}\coloneqq(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)})$, we
consider two settings: $\bm{\lambda}=(1,1,1),\,\bm{\lambda}=(1,1,10)$.
Furthermore, we apply the stock reduction rule 24 to EI-based-SUS and executed
it in both settings. We refer to this as EI-SUS-R. The results are shown in
Figure 66(a) and 66(b). Comparing EI-based and EI-based-SUS, we can observe
that the performance is improved by incorporating the suspension. Moreover,
the performance did not deteriorate even when the stock reduction rule was
applied. In addition, the stocks are not consumed in the simulator, and once a
stock is acquired, it can be used a number of times. In this case, we can
reduce the number of observations in the earlier stages by reusing the stock.
We compared the situation in which stocks are available only once (EI-SUS (1))
and the situation in which stocks can be used a number of times (EI-SUS
($\infty$)). From Figure 66(c), we confirm that EI-SUS ($\infty$) performs a
more efficient optimization.

## Conclusion

We proposed a new BO framework for cascade-type multistage processes that
often appear in science and engineering. Moreover, we have designed two AFs
based on CIs and EI by handling intractable predictive distributions using
different approaches. From both the theoretical analysis and numerical
experiments, it is confirmed that the proposed methods have a superior
performance.

### Acknowledgments

This study was partially supported by MEXT/JSPS KAKENHI (16H06538, 17H04694,
20H00601, 21H03498, 22H00300, JP21J14673), JST CREST (JPMJCR21D3), JST
Moonshot R&D (JPMJMS2033-05), NEDO (JPNP18002, JPNP20006), and RIKEN Center
for Advanced Intelligence Project. The authors acknowledge Takuto Kojima and
Kazuhiro Gotoh of Nagoya University for their support of the solar cell
simulation, and Shinsuke Miyagawa, Kazuhiro Gotoh, Yasuyoshi Kurokawa, and
Noritaka Usami of Nagoya University for providing HPT data.

## References

  * Astudillo and Frazier, (2021) Astudillo, R. & Frazier, P. (2021).  Bayesian optimization of function networks.  In Advances in Neural Information Processing Systems, (Vol. 34, pp. 14463–14475). Curran Associates, Inc.
  * Beland and Nair, (2017) Beland, J. J. & Nair, P. B. (2017).  Bayesian optimization under uncertainty.  In NIPS BayesOpt 2017 workshop.
  * Bentzen, (2006) Bentzen, A. (2006).  Phosphorus diffusion and gettering in silicon solar cells.  PhD thesis, Department of Physics, University of Oslo.
  * Bertsekas, (2019) Bertsekas, D. (2019).  Reinforcement learning and optimal control.  Athena Scientific.
  * Couckuyt et al., (2014) Couckuyt, I., Deschrijver, D., & Dhaene, T. (2014).  Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization.  Journal of Global Optimization, 60(3), 575–594.
  * Dai Nguyen et al., (2016) Dai Nguyen, T., Gupta, S., Rana, S., Nguyen, V., Venkatesh, S., Deane, K. J., & Sanders, P. G. (2016).  Cascade Bayesian optimization.  In Australasian Joint Conference on Artificial Intelligence, (pp. 268–280). Springer.
  * Frazier, (2018) Frazier, P. I. (2018).  A tutorial on Bayesian optimization.  arXiv:1807.02811.
  * Gardner et al., (2014) Gardner, J. R., Kusner, M. J., Xu, Z. E., Weinberger, K. Q., & Cunningham, J. P. (2014).  Bayesian optimization with inequality constraints.  In Proceedings of the 31st International Conference on Machine Learning, (Vol. 32, pp. 937–945). PMLR.
  * Ginsbourger and Le Riche, (2010) Ginsbourger, D. & Le Riche, R. (2010).  Towards Gaussian process-based optimization with finite time horizon.  In mODa 9–Advances in Model-Oriented Design and Analysis, 89–96. Springer.
  * (10) González, J., Dai, Z., Hennig, P., & Lawrence, N. (2016a).  Batch Bayesian optimization via local penalization.  In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, (Vol. 51, pp. 648–657). PMLR.
  * (11) González, J., Osborne, M., & Lawrence, N. (2016b).  GLASSES: Relieving the myopia of Bayesian optimisation.  In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, (Vol. 51, pp. 790–799). PMLR.
  * Haug and Greulich, (2016) Haug, H. & Greulich, J. (2016).  PC1Dmod 6.2–improved simulation of c-Si devices with updates on device physics and user interface.  Energy Procedia, 92, 60–68.
  * Inatsu et al., (2021) Inatsu, Y., Iwazaki, S., & Takeuchi, I. (2021).  Active learning for distributionally robust level-set estimation.  In Proceedings of the 38th International Conference on Machine Learning, (Vol. 139, pp. 4574–4584). PMLR.
  * Inatsu et al., (2022) Inatsu, Y., Takeno, S., Karasuyama, M., & Takeuchi, I. (2022).  Bayesian optimization for distributionally robust chance-constrained problem.  In Proceedings of the 39th International Conference on Machine Learning, (Vol. 162, pp. 9602–9621). PMLR.
  * Iwazaki et al., (2021) Iwazaki, S., Inatsu, Y., & Takeuchi, I. (2021).  Mean-variance analysis in Bayesian optimization under uncertainty.  In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, (Vol. 130, pp. 973–981). PMLR.
  * Jiang et al., (2020) Jiang, S., Chai, H., González, J., & Garnett, R. (2020).  BINOCULARS for efficient, nonmyopic sequential experimental design.  In Proceedings of the 37th International Conference on Machine Learning, (Vol. 119, pp. 4794–4803). PMLR.
  * Jones et al., (1998) Jones, D. R., Schonlau, M., & Welch, W. J. (1998).  Efficient global optimization of expensive black-box functions.  Journal of Global optimization, 13(4), 455–492.
  * Kingma and Welling, (2014) Kingma, D. P. & Welling, M. (2014).  Auto-encoding variational Bayes.  In International Conference on Learning Representations.
  * Lam et al., (2016) Lam, R., Willcox, K., & Wolpert, D. H. (2016).  Bayesian optimization with a finite budget: An approximate dynamic programming approach.  In Advances in Neural Information Processing Systems, (Vol. 29, ). Curran Associates, Inc.
  * (20) Miyagawa, S., Gotoh, K., Kutsukake, K., Kurokawa, Y., & Usami, N. (2021a).  Application of Bayesian optimization for high-performance TiOx/SiOy/c-Si passivating contact.  Solar Energy Materials and Solar Cells, 230, 111251.
  * (21) Miyagawa, S., Gotoh, K., Kutsukake, K., Kurokawa, Y., & Usami, N. (2021b).  Application of Bayesian optimization for improved passivation performance in TiO x/SiO y/c-Si heterostructure by hydrogen plasma treatment.  Applied Physics Express, 14(2), 025503.
  * Močkus, (1975) Močkus, J. (1975).  On Bayesian methods for seeking the extremum.  In Optimization techniques IFIP technical conference, (pp. 400–404). Springer.
  * Nakano et al., (2022) Nakano, T., Kutsukake, K., Kusakawa, S., Takeuchi, I., & Ujihara, T. (2022).  Practical cascade Bayesian optimization.  Unpublished.
  * O’Hagan, (1991) O’Hagan, A. (1991).  Bayes–hermite quadrature.  Journal of statistical planning and inference, 29(3), 245–260.
  * Oliveira et al., (2019) Oliveira, R., Ott, L., & Ramos, F. (2019).  Bayesian optimisation under uncertain inputs.  In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, (Vol. 89, pp. 1177–1184). PMLR.
  * Quinonero-Candela et al., (2002) Quinonero-Candela et al. (2002).  Prediction at an uncertain input for Gaussian processes and relevance vector machines-application to multiple-step ahead time-series forecasting.  In tech. rep., Technical Report, IMM. Danish Technical University.
  * Rahimi and Recht, (2008) Rahimi, A. & Recht, B. (2008).  Random features for large-scale kernel machines.  In Advances in Neural Information Processing Systems, (Vol. 20, ). Curran Associates, Inc.
  * Rasmussen and Williams, (2005) Rasmussen, C. E. & Williams, C. K. I. (2005).  Gaussian Processes for Machine Learning.  The MIT Press.
  * Shahriari et al., (2015) Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., & De Freitas, N. (2015).  Taking the human out of the loop: A review of Bayesian optimization.  Proceedings of the IEEE, 104(1), 148–175.
  * Srinivas et al., (2010) Srinivas, N., Krause, A., Kakade, S., & Seeger, M. (2010).  Gaussian process optimization in the bandit setting: No regret and experimental design.  In Proceedings of the 27th International Conference on Machine Learning, (pp. 1015–1022). Omnipress.
  * Sui et al., (2015) Sui, Y., Gotovos, A., Burdick, J., & Krause, A. (2015).  Safe exploration for optimization with Gaussian processes.  In Proceedings of the 32nd International Conference on Machine Learning, (Vol. 37, pp. 997–1005). PMLR.
  * Sutton and Barto, (2018) Sutton, R. S. & Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Suzuki et al., (2020) Suzuki, S., Takeno, S., Tamura, T., Shitara, K., & Karasuyama, M. (2020).  Multi-objective Bayesian optimization using pareto-frontier entropy.  In Proceedings of the 37th International Conference on Machine Learning, (Vol. 119, pp. 9279–9288). PMLR.
  * Swersky et al., (2013) Swersky, K., Snoek, J., & Adams, R. P. (2013).  Multi-task Bayesian optimization.  In Advances in Neural Information Processing Systems, (Vol. 26, ). Curran Associates, Inc.
  * Takeno et al., (2020) Takeno, S., Fukuoka, H., Tsukada, Y., Koyama, T., Shiga, M., Takeuchi, I., & Karasuyama, M. (2020).  Multi-fidelity Bayesian optimization with max-value entropy search and its parallelization.  In Proceedings of the 37th International Conference on Machine Learning, (Vol. 119, pp. 9334–9345). PMLR.
  * (36) Takeno, S., Fukuoka, H., Tsukada, Y., Koyama, T., Shiga, M., Takeuchi, I., & Karasuyama, M. (2022a).  A generalized framework of multi-fidelity max-value entropy search through joint entropy.  Neural Computation.  To appear.
  * (37) Takeno, S., Tamura, T., Shitara, K., & Karasuyama, M. (2022b).  Sequential and parallel constrained max-value entropy search via information lower bound.  In Proceedings of the 39th International Conference on Machine Learning, (Vol. 162, pp. 20960–20986). PMLR.
  * Wu and Frazier, (2019) Wu, J. & Frazier, P. (2019).  Practical two-step lookahead Bayesian optimization.  In Advances in Neural Information Processing Systems, (Vol. 32, ). Curran Associates, Inc.

## Appendix

##  A Generalization of Problem Setting

Hereafter, we consider the generalized settings, including vector output and
noisy observations. First, we generalize the problem setting in this section.
In Appendix C, we consider the noiseless setting. We also consider the noisy
observation setting in Appendix D and provide the optimization algorithm.
Furthermore, we discuss the conditions of our theorems in Appendix E. Details
of our experiments and additional experiments are described in Appendix F and
G, respectively.

Let $\mathcal{Y}^{(n)}\subset\mathbb{R}^{M^{(n)}}$ be the
$M^{(n)}$-dimensional output space222 Since we focus on single-objective
optimization, the output of the final stage is assumed to be scalar (i.e.,
$M^{(N)}=1$)., and vector-output black-box function of stage $n$ is denoted by
$\bm{f}^{(n)}$, and $f^{(n)}_{m}$ denotes the $m$-th function of
$\bm{f}^{(n)}$. Output $\bm{y}^{(n)}$ corresponding to an input
$(\bm{y}^{(n-1)},\bm{x}^{(n)})$ is observed with noise $\bm{\epsilon}^{(n)}$:
$\bm{y}^{(n)}=\bm{f}^{(n)}(\bm{y}^{(n-1)},\bm{x}^{(n)})+\bm{\epsilon}^{(n)}$.
The noiseless settings are the case of $\bm{\epsilon}^{(n)}=\bm{0}$.
Furthermore, we consider that $\bm{\epsilon}^{(n)}$ is uniformly bounded and
zero mean noise in Appendix D.

In order to construct a surrogate model of $\bm{f}^{(n)}$, we set
$\mathcal{GP}(0,k^{(n)})$ to the prior for each $f^{(n)}_{m}$, where
$\mathcal{GP}(\mu,k^{(n)})$ represents the GP with mean function $\mu$ and
kernel function $k^{(n)}$. Additionally, we assume that $k^{(n)}$ is a
positive-definite kernel and
$\forall(\bm{y}^{(n-1)},\bm{x}^{(n)})\in\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)},\>k^{(n)}\left((\bm{y}^{(n-1)},\bm{x}^{(n)}),\,(\bm{y}^{(n-1)},\bm{x}^{(n)})\right)\leq
1$. Let
$\mathcal{D}^{(n)}_{t}=\left\\{\left((\bm{y}_{i}^{(n-1)},\bm{x}_{i}^{(n)}),\bm{y}_{i}^{(n)}\right)\right\\}_{i=1}^{L_{t}^{(n)}}$
be observed data of stage $n$ at iteration $t$. As the noise model of GP, we
use $\bm{\epsilon}^{(n)}\sim\mathcal{N}(\bm{0},\sigma^{2}\bm{I}_{M^{(n)}})$,
where $\bm{I}_{M^{(n)}}$ denotes $M^{(n)}\times M^{(n)}$ identity matrix. Note
that this noise model is different from the actual noise assumption. Given the
observation $\mathcal{D}^{(n)}_{t}$, the posterior of $f^{(n)}_{m}$ is also
GP, and the predictive distribution of
$f^{(n)}_{m}(\bm{y}^{(n-1)},\bm{x}^{(n)})$ is given by:

$\displaystyle
f^{(n)}_{m}(\bm{y}^{(n-1)},\bm{x}^{(n)})\sim\mathcal{N}\bigl{(}\mu^{(n)}_{m,t}(\bm{y}^{(n-1)},\bm{x}^{(n)}),\>\sigma^{(n)\,2}_{m,t}(\bm{y}^{(n-1)},\bm{x}^{(n)})\bigr{)},$
(A.1)
$\displaystyle\mu^{(n)}_{m,t}(\bm{y}^{(n-1)},\bm{x}^{(n)})=\bm{k}\left(\bm{y}^{(n-1)},\bm{x}^{(n)}\right)^{\top}(\bm{K}^{(n)}_{t}+\sigma^{2}\bm{I}_{L_{t}^{(n)}})^{-1}\bm{y}^{(n)}_{m},$
(A.2)

Here,
$\bm{k}(\bm{y}^{(n-1)},\bm{x}^{(n)})=\left[k^{(n)}\left((\bm{y}^{(n-1)},\bm{x}^{(n)}),\,(\bm{y}^{(n-1)}_{i},\bm{x}^{(n)}_{i})\right)\right]_{i=1}^{L_{t}^{(n)}}$,
$\bm{y}^{(n)}_{m}=\left[y^{(n)}_{1m},\dots,y^{(n)}_{Lm}\right]^{\top}$, and
$\bm{K}^{(n)}_{t}$ is a kernel matrix which has
$k^{(n)}\bigl{(}(\bm{y}^{(n-1)}_{i},\bm{x}^{(n)}_{i}),\,(\bm{y}^{(n-1)}_{j},\bm{x}^{(n)}_{j})\bigr{)}$
in $(i,j)$-th element. In addition, we define
$\bm{\mu}_{t}^{(n)}(\bm{y}^{(n-1)},\bm{x}^{(n)})=\left[\,\mu^{(n)}_{m,t}(\bm{y}^{(n-1)},\bm{x}^{(n)})\,\right]_{m=1}^{M^{(n)}}$.

For a GP model of $f^{(n)}_{m}$, we give a definition of the maximum
information gain. Let
$A^{(n)}=\\{\bm{a}^{(n)}_{1},\dots,\bm{a}^{(n)}_{T}\\}\subset\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)}$
be a finite set of sampling points. We define
$\bm{y}^{(n)}_{A,m}\in\mathbb{R}^{T}$ as observation vector w.r.t. $A^{(n)}$,
whose $i$-th element is given by
$y^{(n)}_{\bm{a}_{i},m}=f^{(n)}_{m}(\bm{a}_{i})+{\varepsilon}_{\bm{a}_{i},m}^{(n)}$.
Then, the maximum information gain $\gamma^{(n)}_{m,T}$ is defined as:

$\gamma^{(n)}_{m,T}=\max_{\begin{subarray}{c}A^{(n)}\subset\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)},\>|A^{(n)}|=T\end{subarray}}\mathrm{I}(\bm{y}^{(n)}_{A,m};f^{(n)}_{m}),$
(A.3)

where $\mathrm{I}(\bm{y}^{(n)}_{A,m};f^{(n)}_{m})$ is the mutual information
between $\bm{y}^{(n)}_{A,m}$ and $f^{(n)}_{m}$. Furthermore, it is known that
this mutual information can be written in closed form as follows Srinivas et
al., (2010):

$\mathrm{I}(\bm{y}^{(n)}_{A,m};f^{(n)}_{m})=\frac{1}{2}\log\det\left(\bm{I}_{|A^{(n)}|}+\sigma^{-2}\bm{K}^{(n)}_{A^{(n)}}\right),$
(A.4)

where
$\bm{K}^{(n)}_{A^{(n)}}=\left[k^{(n)}(\bm{a}^{(n)}_{i},\bm{a}^{(n)}_{j})\right]_{\bm{a}^{(n)}_{i}\in
A^{(n)},\>\bm{a}^{(n)}_{j}\in A^{(n)}}$.

Additionally, we define $\mathcal{S}_{t}^{(n)}$ as the set of stocks in stage
$n$ at iteration $t$.

###  A.1 Proofs of Theorems

Theorem 3.1 is a special case of Theorem C.7 with $M^{(n)}=1$ for all $n$.
Likewise, Theorems 4.1 and 4.2 are corresponding to Theorems C.6 and C.10 with
$M^{(n)}=1$, respectively. The proofs of these theorems are given in the
generalized problem setting. Moreover, we also provide the proof of Theorem
5.1 in Corollary C.8.

##  B Prediction of Cascade Processes using Bayesian Quadrature

In this section, we consider the cascade process as a Bayesian quadrature
O’Hagan, (1991) framework and introduce one of its problems. For black-box
functions at each stage of the cascade process, we consider a predictive model
using GP. The problem is that it is difficult to predict each stage from the
first stage because each stage contains controllable variables and outputs
from the previous stage that are not controllable. Nevertheless, the output
from the previous stage can be predicted using the posterior distribution.
Therefore, integrating the black-box function of each stage with respect to
this posterior distribution, i.e., taking the expectation, allows prediction
of each stage with respect to the average case of uncontrollable inputs. This
approach is known as Bayesian quadrature, and furthermore, since each stage
follows a GP, it is known that the integration of the black-box function is
again a GP (see, e.g., Papoulis and Pillai, (2002)). Therefore, the advantage
of this approach is that it is easy to construct credible intervals based on
the properties of GP. However, this modeling has the problem that it cannot
always correctly predict the target it originally wants to predict.

######  Lemma B.1.

Suppose that $f_{1}:\mathbb{R}\to\mathbb{R}$ follows
$\mathcal{G}\mathcal{P}(0,k_{1}(x,x^{\prime}))$. Also suppose that
$f_{2}:\mathbb{R}^{2}\to\mathbb{R}$ follows
$\mathcal{G}\mathcal{P}(0,k_{2}((x_{1},x_{2}),(x^{\prime}_{1},x^{\prime}_{2}))$.
Assume that the first variable of $f_{2}$ is the output of $f_{1}$. Then, the
stochastic process $f_{2}(f_{1}(x_{1}),x_{2})$ is not necessarily the same as

$\displaystyle\mathbb{E}_{f_{1}(x_{1})\sim\mathcal{G}\mathcal{P}(0,k_{1}(x,x^{\prime}))}[f_{2}(f_{1}(x_{1}),x_{2})].$
(B.1)

.

###### Proof.

Let $k_{1}(x,x^{\prime})=\exp(-(x-x^{\prime})^{2})$ and
$k_{2}({\bm{y}},{\bm{y}}^{\prime})={\bm{y}}^{\top}{\bm{y}}^{\prime}$. Since
the expectation of GP with respect to inputs is again a GP, (B.1) follows GP.
Therefore, the probability distribution given by (B.1) at point
$x_{1}=x_{2}=0$ follows some normal distribution. On the other hand, since
$f_{1}(x_{1})\sim\mathcal{G}\mathcal{P}(0,k_{1}(x,x^{\prime}))$, from the
definition of $k_{1}(x,x^{\prime})$ we have $f_{1}(0)\sim N(0,1)$. Similarly,
we get $f_{2}(f_{1}(0),0)\sim
N(0,f^{2}_{1}(0))\stackrel{{\scriptstyle\mathrm{d}}}{{=}}N(0,\chi^{2}_{1})\stackrel{{\scriptstyle\mathrm{d}}}{{=}}\sqrt{\chi^{2}_{1}}N(0,1)$,
where $\chi^{2}_{1}$ is the chi-squared distribution with one degree of
freedom. The mean and variance of $\sqrt{\chi^{2}_{1}}N(0,1)$ are zero and
one, respectively. Furthermore, the fourth moment of
$\sqrt{\chi^{2}_{1}}N(0,1)$ is given by

$\mathbb{E}\left[\left(\sqrt{\chi^{2}_{1}}N(0,1)\right)^{4}\right]=\mathbb{E}[(\chi^{2}_{1})^{2}]\mathbb{E}[N(0,1))^{4}]=(\mathbb{V}[\chi^{2}_{1}]+\mathbb{E}[\chi^{2}_{1}]^{2})3=9.$

Hence, $\sqrt{\chi^{2}_{1}}N(0,1)$ does not follow a normal distribution
because the fourth moment of the normal distribution with mean zero and
variance one, i.e., the standard normal distribution, is three. Thus, the
stochastic process $f_{2}(f_{1}(x_{1}),x_{2})$ is not the same as (B.1). ∎

Although it is possible to construct a GP prediction model as an integral of
GP, the final stage does not necessarily follow GP. Hence, it is not always
easy to judge whether the composition of the credible interval or the design
of AF based on the constructed GP prediction model is appropriate or not.
Therefore, modeling the final stage of the cascade process based on the
integration of GP is not the most natural approach.

##  C Cascade Process Optimization Using CI-based AFs under Noiseless Setting

In this section, we consider CI-based cascade process optimization methods
without observation noise.

###  C.1 Credible Interval

We construct a valid CI for the objective function
$F({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$. First, we assume the following
regularity assumption which is commonly assumed in many BO studies.

######  Assumption C.1 (Regularity assumption under noiseless setting).

For each $n\in[N]$, let $\mathcal{Y}^{(n-1)}\times\mathcal{X}^{(n)}$ be a
compact set, and let $\mathcal{H}_{k^{(n)}}$ be an RKHS corresponding to the
kernel $k^{(n)}$. In addition, for each $n\in[N]$ and $m\in[M^{(n)}]$, assume
that $f^{(n)}_{m}\in\mathcal{H}_{k^{(n)}}$ with
$\|f^{(n)}_{m}\|_{{k^{(n)}}}\leq B$, where $B>0$ is some constant, and
$\|\cdot\|_{{k^{(n)}}}$ denotes the RKHS norm on $\mathcal{H}_{k^{(n)}}$.
Furthermore, assume that the observation noise $\epsilon^{(n)}_{m}$ is zero.

Under this assumption, it is known that the following lemma holds.

######  Lemma C.2 (Abbasi-Yadkori, 2012, Theorem 3.11).

Assume that Assumption C.1 holds. Define $\beta=B^{2}$. Then, for any
$n\in[N]$ and $m\in[M^{(n)}]$, the following inequality holds:

$\left|f^{(n)}_{m}(\bm{w},\bm{x})-\mu^{(n)}_{m,t}(\bm{w},\bm{x})\right|\leq\beta^{1/2}\sigma^{(n)}_{m,t}(\bm{w},\bm{x}),\>\forall\bm{w}\in\mathcal{Y}^{(n-1)},\;\forall\bm{x}\in\mathcal{X}^{(n)},\;\forall
t\geq 1.$ (C.1)

Based on C.1, we construct the valid CI. However, we cannot use C.1 to
construct CIs directly because the input ${\bm{w}}\in\mathcal{Y}^{(n-1)}$ is
the output of the previous stage. In order to avoid this issue, we introduce
additional assumptions for Lipschitz continuity.

######  Assumption C.3 (Lipschitz continuity for $f^{(n)}_{m}$).

Assume that $f^{(n)}_{m}$ is $L_{f}$-Lipschitz continuous with respect to
$L_{1}$-distance for any $n\in\\{2,\ldots,N\\}$ and $m\in[M^{(n)}]$, where
$L_{f}>0$ is a Lipschitz constant.

######  Assumption C.4 (Lipschitz continuity for $\sigma^{(n)}_{m}$).

Assume that $\sigma^{(n)}_{m,t}$ is $L_{\sigma}$-Lipschitz continuous with
respect to $L_{1}$-distance for any $n\in\\{2,\ldots,N\\}$, $m\in[M^{(n)}]$
and $t\geq 1$, where $L_{\sigma}>0$ is a Lipschitz constant.

Then, the following theorem gives CIs for the $N$-stage cascade process.

######  Theorem C.5 (CIs for $N$-stage cascade process).

Assume that Assumptions C.1 and C.3 hold. Define $\beta=B^{2}$ and

$\displaystyle{\bm{z}}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
$\displaystyle=\begin{cases}{\bm{f}}^{(1)}({\bm{0}},{\bm{x}}^{(1)})&(n=1),\\\
{\bm{f}}^{(n)}({\bm{z}}^{(n-1)}({\bm{x}}^{(1:n-1)}),{\bm{x}}^{(n)})&(2\leq
n\leq N),\end{cases}$ (C.2)
$\displaystyle\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
$\displaystyle=\begin{cases}{\bm{\mu}}^{(1)}_{t}({\bm{0}},{\bm{x}}^{(1)})&(n=1),\\\
{\bm{\mu}}_{t}^{(n)}(\tilde{\bm{\mu}}^{(n-1)}({\bm{x}}^{(1:n-1)}),{\bm{x}}^{(n)})&(2\leq
n\leq N),\end{cases}$ (C.3)
$\displaystyle\tilde{\sigma}^{(n)}_{m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
$\displaystyle=\begin{dcases}\sigma^{(1)}_{m,t}({\bm{0}},{\bm{x}}^{(1)})&(n=1),\\\
\begin{aligned}
&\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(1:n-1)}),{\bm{x}}^{(n)})\\\
&\quad+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1:n-1)})\end{aligned}&(2\leq
n\leq N).\end{dcases}$ (C.4)

Moreover, assume that
$\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\mathcal{Y}^{(n)}$
for any $n\in[N]$, $t\geq 1$ and
$({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\mathcal{X}^{(1)}\times\cdots\times\mathcal{X}^{(n)}$.
Then, it follows that

$|{z}_{m}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})-\tilde{\mu}^{(n)}_{m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})|\leq\beta^{1/2}\tilde{\sigma}^{(n)}_{m,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}),$
(C.5)

where $m\in[M^{(n)}]$, and $z^{(n)}_{m}(\cdot)$ and
$\tilde{\mu}^{(n)}_{m,t}(\cdot)$ are the $m$-th element of
${\bm{z}}^{(n)}_{m}(\cdot)$ and $\tilde{\bm{\mu}}^{(n)}_{m,t}(\cdot)$,
respectively. In particular, when $n=N$, it follows that

$|F({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})-\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})|\leq\quad\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}).$
(C.6)

###### Proof.

Fix ${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}$, $t\geq 1$ and $m\in[M^{(n)}]$. For
simplicity, hereafter, we sometimes omit the notation
$({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$ such as $z^{(n)}_{m}$ and
$\tilde{\mu}^{(n)}_{m,t}$. Then, for $i\in[M^{(2)}]$, it follows that

$\displaystyle|z^{(2)}_{i}-\tilde{\mu}^{(2)}_{i,t}|$
$\displaystyle=|z^{(2)}_{i}-f^{(2)}_{i}(\tilde{\bm{\mu}}^{(1)}_{t},{\bm{x}}^{(2)})+f^{(2)}_{i}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})-\tilde{\mu}^{(2)}_{i,t}|$
(C.7)
$\displaystyle\leq|z^{(2)}_{i}-f^{(2)}_{i}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})|+|f^{(2)}_{i}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})-\tilde{\mu}^{(2)}_{i,t}|$
(C.8)
$\displaystyle=|z^{(2)}_{i}({\bm{z}}^{(1)},{\bm{x}}^{(2)})-f^{(2)}_{i}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})|+|f^{(2)}_{i}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})-{\mu}^{(2)}_{i,t}(\tilde{\bm{\mu}}^{(1)}_{t},{\bm{x}}^{(2)})|$
(C.9) $\displaystyle\leq
L_{f}\|{\bm{z}}^{(1)}-\tilde{\bm{\mu}}^{(1)}_{t}\|_{1}+\beta^{1/2}\sigma^{(2)}_{i,t}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})$
(C.10)
$\displaystyle=\beta^{1/2}\sigma^{(2)}_{i,t}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})+L_{f}\sum_{m=1}^{M^{(1)}}|z^{(1)}_{m}-\tilde{\mu}^{(1)}_{m,t}|$
(C.11)
$\displaystyle\leq\beta^{1/2}\sigma^{(2)}_{i,t}(\tilde{\bm{\mu}}_{t}^{(1)},{\bm{x}}^{(2)})+L_{f}\sum_{m=1}^{M^{(1)}}\beta^{1/2}\sigma^{(1)}_{m,t}({\bm{0}},{\bm{x}}^{(1)})$
(C.12)
$\displaystyle=\beta^{1/2}\tilde{\sigma}^{(2)}_{i,t}({\bm{x}}^{(1)},{\bm{x}}^{(2)}).$
(C.13)

Similarly, $z^{(3)}_{j}$ and $\tilde{\mu}^{(3)}_{j,t}$ satisfy that

$\displaystyle|z^{(3)}_{j}-\tilde{\mu}^{(3)}_{j,t}|$
$\displaystyle=|z^{(3)}_{j}-f^{(3)}_{j}(\tilde{\bm{\mu}}_{t}^{(2)},{\bm{x}}^{(3)})+f^{(3)}_{j}(\tilde{\bm{\mu}}_{t}^{(2)},{\bm{x}}^{(3)})-\tilde{\mu}^{(3)}_{j,t}|$
(C.14)
$\displaystyle\leq|z^{(3)}_{j}-f^{(3)}_{j}(\tilde{\bm{\mu}}_{t}^{(2)},{\bm{x}}^{(3)})|+|f^{(3)}_{j}(\tilde{\bm{\mu}}_{t}^{(2)},{\bm{x}}^{(3)})-\tilde{\mu}^{(3)}_{j,t}|$
(C.15) $\displaystyle\leq
L_{f}\|{\bm{z}}^{(2)}-\tilde{\bm{\mu}}_{t}^{(2)}\|_{1}+\beta^{1/2}\sigma^{(3)}_{j,t}(\tilde{\bm{\mu}}_{t}^{(2)},{\bm{x}}^{(3)})$
(C.16)
$\displaystyle=\beta^{1/2}\sigma^{(3)}_{j,t}(\tilde{\bm{\mu}}_{t}^{(2)},{\bm{x}}^{(3)})+L_{f}\sum_{i=1}^{M^{(2)}}|z^{(2)}_{i}-\tilde{\mu}^{(2)}_{i,t}|.$
(C.17)

Hence, by substituting C.13 into C.17, we get

$\displaystyle|z^{(3)}_{j}-\tilde{\mu}^{(3)}_{j,t}|$
$\displaystyle\leq\beta^{1/2}\left(\sigma^{(3)}_{j,t}(\tilde{\bm{\mu}}_{t}^{(2)},{\bm{x}}^{(3)})+L_{f}\sum_{u=1}^{M^{(2)}}\tilde{\sigma}^{(2)}_{u,t}({\bm{x}}^{(1)},{\bm{x}}^{(2)})\right)$
(C.18)
$\displaystyle=\beta^{1/2}\tilde{\sigma}^{(3)}_{j,t}({\bm{x}}^{(1)},{\bm{x}}^{(2)},{\bm{x}}^{(3)}).$

By repeating this process up to $n$, we have Theorem C.5. ∎

From Theorem C.5, we can construct the valid CI
$Q^{(F)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$ of
$F({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$ as follows:

$\displaystyle Q^{(F)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
$\displaystyle=[\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\pm\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})]$
(C.19)
$\displaystyle=[\mathrm{LCB}^{(F)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}),\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})].$
(C.20)

Next, we consider the property of estimated solutions based on the proposed CI
C.20. For any $t\geq 1$, we define the estimated solution
$(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})$ as

$(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})=\operatorname*{arg\,max}_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X},1\leq\tilde{t}\leq
t}\mathrm{LCB}^{(F)}_{\tilde{t}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}).$
(C.21)

Then, the following theorem holds.

######  Theorem C.6.

Let $(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})$ be the estimated
solution given by C.21. Assume that the same assumption as in Theorem C.5
holds. Then, for any $t\geq 1$ and $\xi>0$, it follows that

$\displaystyle\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1:N)})-\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{LCB}^{(F)}_{t}({\bm{x}}^{(1:N)})<\xi$
(C.22) $\displaystyle\Rightarrow
F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})<\xi.$
(C.23)

###### Proof.

From the definition of CIs, using Theorem C.5 we have

$\displaystyle F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
$\displaystyle\leq\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast}),$
(C.24)
$\displaystyle\mathrm{LCB}^{(F)}_{\hat{t}}(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})$
$\displaystyle\leq F(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t}),$
(C.25)

where
$\hat{t}=\operatorname*{arg\,max}_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X},1\leq\tilde{t}\leq
t}\mathrm{LCB}^{(F)}_{\tilde{t}}({\bm{x}}^{(1:N)}).$ Similarly, from the
definition of $(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})$, noting
that

$\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{LCB}^{(F)}_{t}({\bm{x}}^{(1:N)})\leq\mathrm{LCB}^{(F)}_{\hat{t}}(\hat{\bm{x}}^{(1:N)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t}),$
(C.26)

we get

$\displaystyle F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
$\displaystyle\leq\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
$\displaystyle\leq\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1:N)}),$
(C.27)
$\displaystyle\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{LCB}^{(F)}_{t}({\bm{x}}^{(1:N)})$
$\displaystyle\leq\mathrm{LCB}^{(F)}_{\hat{t}}(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})$
$\displaystyle\leq F(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t}).$
(C.28)

This implies that

$\displaystyle
F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{t},\ldots,\hat{\bm{x}}^{(N)}_{t})$
(C.29)
$\displaystyle\leq\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1:N)})-\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{LCB}^{(F)}_{t}({\bm{x}}^{(1:N)}).$
(C.30)

Therefore, by combining C.30 and

$\max_{{\bm{x}}^{(1:N)}\in\mathcal{X}}\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1:N)})-\max_{({\bm{x}}^{(1:N)})\in\mathcal{X}}\mathrm{LCB}^{(F)}_{t}({\bm{x}}^{(1:N)})<\xi,$
(C.31)

we get Theorem C.6. ∎

Finally, we consider the construction of CIs when the observations up to the
$s$-th stage are given. Let $s$ be an integer with $0\leq s\leq N-1$, and let
${\bm{y}}$ be an element of $\mathcal{Y}^{(s)}$. Then, for each
$n\in\\{s+1,\ldots,N\\}$, $m\in[M^{(n)}]$, $t\geq 1$ and
${\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}$, we define
${\bm{z}}^{(n)}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})$,
$\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})$
and
$\tilde{\sigma}^{(n)}_{m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})$
as

$\displaystyle{\bm{z}}^{(n)}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})$
$\displaystyle=\begin{cases}{\bm{f}}^{(s+1)}({\bm{y}},{\bm{x}}^{(s+1)})&(n=s+1),\\\
{\bm{f}}^{(n)}({\bm{z}}^{(n-1)}({\bm{x}}^{(s+1:n-1)}|{\bm{y}}),{\bm{x}}^{(n)})&(n\geq
s+2),\end{cases}$ (C.32)
$\displaystyle\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})$
$\displaystyle=\begin{cases}{\bm{\mu}}^{(s+1)}_{t}({\bm{y}},{\bm{x}}^{(s+1)})&(n=s+1),\\\
{\bm{\mu}}_{t}^{(n)}(\tilde{\bm{\mu}}^{(n-1)}({\bm{x}}^{(s+1:n-1)}|{\bm{y}}),{\bm{x}}^{(n)})&(n\geq
s+2),\end{cases}$ (C.33)
$\displaystyle\tilde{\sigma}^{(n)}_{m,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})$
$\displaystyle=\begin{cases}\sigma^{(s+1)}_{m,t}({\bm{y}},{\bm{x}}^{(s+1)})&(n=s+1),\\\
\begin{aligned}
&\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s+1:n-1)}|{\bm{y}}),{\bm{x}}^{(n)})\\\
&\>\>+L_{f}\sum_{u=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{u,t}({\bm{x}}^{(s+1:n-1)}|{\bm{y}})\end{aligned}&(n\geq
s+2).\end{cases}$ (C.34)

Moreover, we formally define
${\bm{z}}^{(s)}({\bm{x}}^{(s+1)},{\bm{x}}^{(s)}|{\bm{y}})=\tilde{\bm{\mu}}^{(s)}_{t}({\bm{x}}^{(s+1)},{\bm{x}}^{(s)}|{\bm{y}})={\bm{y}}$
and $\tilde{\sigma}^{(s)}_{m,t}({\bm{x}}^{(s+1)},{\bm{x}}^{(s)}|{\bm{y}})=0$.
Then, the following theorem holds.

######  Theorem C.7 (CIs for $N$-stage cascade process under given
observation).

Assume that Assumptions C.1 and C.3 hold. Define $\beta=B^{2}$, and assume
that
$\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})\in\mathcal{Y}^{(n)}$
for any $s\in\\{0,\ldots,N-1\\}$, $n\in\\{s+1,\ldots,N\\}$,
${\bm{y}}\in\mathcal{Y}^{(s)}$, $t\geq 1$ and
$({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)})\in\mathcal{X}^{(s+1)}\times\cdots\times\mathcal{X}^{(n)}$.
Then, it follows that

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

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

###### Proof.

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

Based on Theorem C.7, we give a stock reduction rule. For each $t\geq 1$ and
${\bm{y}}\in\mathcal{Y}^{(s)}$ with $0\leq s\leq N-1$, we define
$F({\bm{y}})$, $\mathrm{LCB}^{(F)}_{t}({\bm{y}})$ and
$\mathrm{UCB}^{(F)}_{t}({\bm{y}})$ as

$\displaystyle F({\bm{y}})$
$\displaystyle=\max_{{\bm{x}}^{(s+1)}\cdots{\bm{x}}^{(N)}}{\bm{z}}^{(N)}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{y}}),$
(C.36) $\displaystyle\mathrm{LCB}^{(F)}_{t}({\bm{y}})$
$\displaystyle=\max_{{\bm{x}}^{(s+1)}\cdots{\bm{x}}^{(N)}}(\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{y}})-\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{y}})),$
(C.37) $\displaystyle\mathrm{UCB}^{(F)}_{t}({\bm{y}})$
$\displaystyle=\max_{{\bm{x}}^{(s+1)}\cdots{\bm{x}}^{(N)}}(\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{y}})+\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{y}})),$
(C.38)

where
$\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{y}})$ is
the first element of
$\tilde{\bm{\mu}}^{(N)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{y}})$.
Then, the following corollary holds.

######  Corollary C.8 (Stock reduction).

Assume that the same assumption as in Theorem C.7 holds. Let $t\geq 1$, and
let $\mathcal{S}^{(u)}_{t}$ be a set of stocks at stage
$u\in\\{0,\ldots,N-1\\}$ in iteration $t$. Assume that an element ${\bm{y}}$
in $\mathcal{S}^{(s)}_{t}$ satisfies

$\mathrm{UCB}^{(F)}_{t}({\bm{y}})<\max_{\tilde{\bm{y}}\in\bigcup_{u=0}^{N-1}\mathcal{S}^{(u)}_{t}}\mathrm{LCB}^{(F)}_{t}(\tilde{\bm{y}}).$
(C.39)

Then, it follows that
$F({\bm{y}})<F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$.

###### Proof.

From Theorems C.5 and C.7, noting that ${\bm{y}}\in\mathcal{S}^{(u)}_{t}$ is
the observed value corresponding to some input, it follows that

$\displaystyle F({\bm{y}})$
$\displaystyle\leq\mathrm{UCB}^{(F)}_{t}({\bm{y}})$ (C.40)
$\displaystyle<\max_{\tilde{\bm{y}}\in\bigcup_{u=0}^{N-1}\mathcal{S}^{(u)}_{t}}\mathrm{LCB}^{(F)}_{t}(\tilde{\bm{y}})$
(C.41)
$\displaystyle\leq\max_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X}}{\bm{z}}^{(N)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}|{\bm{0}})$
(C.42) $\displaystyle=F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast}).$
(C.43)

∎

###  C.2 Cascade Process Upper Confidence Bound

Here, we consider a UCB-based optimization strategy, and give a cascade
process upper confidence bound (cUCB) AF. For each iteration $t\geq 1$ and
input $({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$, we define cUCB as

$\mathrm{cUCB}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})=\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})+\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}).$
(C.44)

Next, we consider the theoretical property of cUCB. Suppose that the next
evaluation point is selected by

$({\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{cUCB}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}).$
(C.45)

Moreover, in order to evaluate the goodness of the optimization strategy, we
introduce the regret $r_{t}$, cumulative regret $R_{T}$ and simple regret
$r^{(\text{S})}_{T}$ as

$\displaystyle
r_{t}=F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F({\bm{x}}^{(1)}_{t},\ldots,{\bm{x}}^{(N)}_{t}),$
(C.46) $\displaystyle R_{T}=\sum_{t=1}^{T}r_{t},\quad
r^{(\text{S})}_{T}=\min_{1\leq t\leq T}r_{t}.$ (C.47)

Then, the following theorem gives regret bounds for $R_{T}$ and
$r^{(\text{S})}_{T}$.

######  Theorem C.9.

Assume that Assumptions C.1, C.3 and C.4 hold. Define $\beta=B^{2}$, and
assume that
$\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})\in\mathcal{Y}^{(n)}$
for any $s\in\\{0,\ldots,N-1\\}$, $n\in\\{s+1,\ldots,N\\}$,
${\bm{y}}\in\mathcal{Y}^{(s)}$, $t\geq 1$ and
$({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)})\in\mathcal{X}^{(s+1)}\times\cdots\times\mathcal{X}^{(n)}$.
Then, when the optimization is performed using cUCB, the following inequality
holds for any $T\geq 1$:

$\displaystyle R_{T}$ $\displaystyle\leq\sqrt{\frac{8\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}T\gamma_{T}},$
(C.48) $\displaystyle r^{(\text{S})}_{T}$ $\displaystyle\leq
T^{-1/2}\sqrt{\frac{8\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\gamma_{T}},$
(C.49)

where $C_{0}=L_{\sigma}\beta^{1/2}+L_{f}+1$,
$M_{\text{prod}}=\prod_{n=1}^{N}M^{(n)}$ and
$M_{\text{sum}}=\sum_{n=1}^{N}M^{(n)}$.

###### Proof.

From the definition of $\tilde{\sigma}^{(n)}_{m,t}(\cdot)$, using Lipschitz
continuity of ${\sigma}^{(n)}_{m,t}(\cdot)$ we have

$\displaystyle\tilde{\sigma}^{(n)}_{m,t}$
$\displaystyle({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$ (C.50)
$\displaystyle=\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(C.51)
$\displaystyle\quad+\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}_{t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})$
(C.52)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(C.53)
$\displaystyle\quad+|\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}_{t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})|$
(C.54)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(C.55)
$\displaystyle\quad+L_{\sigma}\sum_{s=1}^{M^{(n-1)}}|{z}_{s}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})-\tilde{\mu}_{s,t}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})|$
(C.56)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+L_{f}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(C.57)
$\displaystyle\quad+L_{\sigma}\beta^{1/2}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(C.58)
$\displaystyle=\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+(L_{\sigma}\beta^{1/2}+L_{f})\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)})$
(C.59)
$\displaystyle\leq\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+C_{0}\sum_{s=1}^{M^{(n-1)}}\tilde{\sigma}^{(n-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}).$
(C.60)

Thus, by repeating the same argument as C.60 up to $N$, we get

$\displaystyle\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
(C.61)
$\displaystyle\leq\sigma^{(N)}_{1,t}({\bm{z}}^{(N-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-1)}),{\bm{x}}^{(N)})+C_{0}\sum_{s=1}^{M^{(N-1)}}\tilde{\sigma}^{(N-1)}_{s,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-1)})$
(C.62)
$\displaystyle\leq\sigma^{(N)}_{1,t}({\bm{z}}^{(N-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-1)}),{\bm{x}}^{(N)})$
(C.63)
$\displaystyle\quad+C_{0}\sum_{s=1}^{M^{(N-1)}}\sigma^{(N-1)}_{s,t}({\bm{z}}^{(N-2)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-2)}),{\bm{x}}^{(N-1)})$
(C.64)
$\displaystyle\quad+C^{2}_{0}M^{(N-1)}\sum_{u=1}^{M^{(N-2)}}\tilde{\sigma}^{(N-2)}_{u,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-2)})$
(C.65) $\displaystyle\leq$ (C.66) $\displaystyle\vdots$ (C.67)
$\displaystyle\leq\sigma^{(N)}_{1,t}({\bm{z}}^{(N-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N-1)}),{\bm{x}}^{(N)})$
(C.68)
$\displaystyle\quad+\sum_{n=1}^{N-1}C_{0}^{N-n}\prod_{s=n+1}^{N}M^{(s)}\sum_{m=1}^{M^{(n)}}\Bigl{[}\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})\Bigr{]}$
(C.69) $\displaystyle\leq
C_{0}^{N-1}M_{\text{prod}}\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\sigma^{(n)}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)}).$
(C.70)

In addition, using the Cauchy–Schwarz inequality, it follows that

$\displaystyle\tilde{\sigma}^{(N)2}_{1,t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
(C.71) $\displaystyle\leq
C_{0}^{2(N-1)}M^{2}_{\text{prod}}\left(\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}1\right)\left(\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})\right)$
(C.72)
$\displaystyle=C_{0}^{2(N-1)}M^{2}_{\text{prod}}M_{\text{sum}}\cdot\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)}).$
(C.73)

Moreover, from Theorem C.5 and the selection rule C.45,
$F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$ can be bounded as
follows:

$\displaystyle F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
$\displaystyle\leq\mathrm{cUCB}_{t}({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
(C.74)
$\displaystyle\leq\mathrm{cUCB}_{t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})$
(C.75)
$\displaystyle=\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})+\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1}).$
(C.76)

Similarly, since $F({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})$ can be
bounded as

$F({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})\geq\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})-\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1}),$
(C.77)

we get

$\displaystyle r_{t}$
$\displaystyle=F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1})$
(C.78) $\displaystyle\leq
2\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(N)}_{t+1}).$
(C.79)

Here, from the Cauchy–Schwarz inequality, $R^{2}_{T}$ can be evaluated as

$R^{2}_{T}=\left(\sum_{t=1}^{T}r_{t}\right)^{2}\leq T\sum_{t=1}^{T}r^{2}_{t}.$
(C.80)

Hence, by combining C.73 and C.79 we have

$\displaystyle\sum_{t=1}^{T}r^{2}_{t}$ $\displaystyle\leq
4\sum_{t=1}^{T}\left(\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M_{\text{sum}}\sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(n-1)}_{t+1}),{\bm{x}}^{(n)}_{t+1})\right)$
(C.81) $\displaystyle\leq 4\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M_{\text{sum}}sum_{n=1}^{N}\sum_{m=1}^{M^{(n)}}\sum_{t=1}^{T}\Bigl{[}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(n-1)}_{t+1}),{\bm{x}}^{(n)}_{t+1})\Bigr{]}.$
(C.82)

Furthermore, by using the same argument as in Lemma 5.3 and 5.4 of Srinivas et
al., (2010), under the assumption $k^{(n)}(\cdot,\cdot)\leq 1$ we get

$\sum_{t=1}^{T}\sigma^{(n)2}_{m,t}({\bm{z}}^{(n-1)}({\bm{x}}^{(1)}_{t+1},\ldots,{\bm{x}}^{(n-1)}_{t+1}),{\bm{x}}^{(n)}_{t+1})\leq\frac{2}{\log(1+\sigma^{-2})}\gamma^{(n)}_{m,T}\leq\frac{2}{\log(1+\sigma^{-2})}\gamma_{T}.$
(C.83)

Thus, from C.82 and C.83 we obtain

$\displaystyle\sum_{t=1}^{T}r^{2}_{t}$ $\displaystyle\leq\frac{8\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\gamma_{T}.$
(C.84)

Hence, by using C.80 and C.84, it follows that

$R_{t}\leq\sqrt{\frac{8\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}T\gamma_{T}}.$
(C.85)

Finally, since $r^{(\text{S})}_{T}$ satisfies

$Tr^{(\text{S})}_{T}\leq\sum_{t=1}^{T}r_{t}=R_{T}\leq\sqrt{\frac{8\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}T\gamma_{T}},$
(C.86)

the following inequality holds:

$r^{(\text{S})}_{T}\leq T^{-1/2}\sqrt{\frac{8\beta
C_{0}^{2(N-1)}M^{2}_{\text{prod}}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\gamma_{T}}.$
(C.87)

∎

###  C.3 Optimistic Improvement-based AF

In this subsection, we consider sequential observations of a cascade process
from stage $1$ to $N$. For each iteration $t\in\\{0,N,2N,\ldots\\}\equiv
N\mathbb{Z}_{\geq 0}$, users determine ${\bm{x}}^{(1)}_{t+1}$ and observe
$\bm{y}_{t+1}^{(1)}={\bm{f}}^{(1)}({\bm{0}},{\bm{x}}^{(1)}_{t+1})$. After
that, users choose ${\bm{x}}^{(2)}_{t+2}$ and observe
$\bm{y}_{t+2}^{(2)}={\bm{f}}^{(2)}(\bm{y}^{(1)}_{t+1},{\bm{x}}^{(2)}_{t+2})$.
By repeating this operation, users obtain
$y^{(N)}_{t+N}={\bm{f}}^{(N)}(\bm{y}^{(N-1)}_{t+N-1},{\bm{x}}^{(N)}_{t+N})$
finally. We design the CI-based AF according to the following strategy: (1)
given an observation ${\bm{y}}^{(n)}$, we seek the maximum of $F$ if it is
expected to be found; (2) if the maximum is not expected to be found, we
collect the information by using another policy. We use the optimistic
improvement for (1), and we adopt uncertainty sampling (US) policy for (2).
First, we define the pessimistic maximum of
$F(\bm{x}^{(1)},\dots,\bm{x}^{(N)})$ as

$Q_{T}=\max_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})}\left(\tilde{\mu}^{(N)}_{1,T}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})-\beta^{1/2}\tilde{\sigma}^{(N)}_{1,T}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\right).$
(C.88)

In addition, given the observation ${\bm{y}}^{(n-1)}$ in stage $n-1$, we
define the pessimistic maximum of $F$ obtained through ${\bm{y}}^{(n-1)}$ as
follows:

$\mathrm{LCB}^{(F)}_{t}({\bm{y}}^{(n-1)})=\max_{{\bm{x}}^{(n:N)}}\left(\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(n:N)}|{\bm{y}}^{(n-1)})-\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(n:N)}|{\bm{y}}^{(n-1)})\right),$
(C.89)

where the $\max$ operator is not necessary when $n=N$. Similarly, the
optimistic maximum for given the input $(\bm{y}^{(n-1)},\bm{x}^{(n)})$ is
defined as follows:

$\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\max_{{\bm{x}}^{(n+1:N)}}\left(\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(n:N)}|{\bm{y}}^{(n-1)})+\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(n:N)}|{\bm{y}}^{(n-1)})\right).$
(C.90)

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

$a^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})-\max\\{\mathrm{LCB}^{(F)}_{t}({\bm{y}}^{(n-1)}),Q_{t+n-1}\\}.$
(C.91)

Furthermore, we define the maximum uncertainty

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

Using C.91 and C.92, optimistic improvement-based AF (presented as CI-based AF
in section 3.2) $c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$ is defined as

$c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\max\left\\{a^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}),\eta_{t}b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\right\\},$
(C.93)

where $\eta_{t}$ is some learning rate tends to zero. Therefore, given the
observation $\bm{y}^{(n-1)}$ at iteration $t$, the next observation point is
given by

${\bm{x}}^{(n)}_{t+n}=\operatorname*{arg\,max}_{{\bm{x}}^{(n)}\in\mathcal{X}^{(n)}}c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}_{t+n-1}^{(n-1)}),$
(C.94)

where ${\bm{y}}^{(0)}={\bm{0}}$.

######  Theorem C.10.

Assume that Assumptions C.1, C.3 and C.4 hold. Also assume that
$\tilde{\bm{\mu}}^{(n)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)}|{\bm{y}})\in\mathcal{Y}^{(n)}$
for any $s\in\\{0,\ldots,N-1\\}$, $n\in\\{s+1,\ldots,N\\}$,
${\bm{y}}\in\mathcal{Y}^{(s)}$, $t\geq 1$ and
$({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n)})\in\mathcal{X}^{(s+1)}\times\cdots\times\mathcal{X}^{(n)}$.
Let $\xi$ be a positive number, and define $\beta=B^{2}$ and $\eta_{t}=(1+\log
t)^{-1}$. Then, when the optimization is performed using C.94, the estimated
solution $(\hat{\bm{x}}^{(1)}_{T},\ldots,\hat{\bm{x}}^{(N)}_{T})$ satisfies
that

$F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{T},\ldots,\hat{\bm{x}}^{(N)}_{T})<\xi,$
(C.95)

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

$\frac{8\beta
C^{2}_{4}M^{2}_{\text{sum}}N}{\log(1+\sigma^{-2})}\gamma_{T}\eta^{-2N-2}_{T}T^{-1}<\xi^{2}.$
(C.96)

Here, $C_{4}$ is the positive constant given by

$C_{1}=\max\\{1,L_{f},L^{-1}_{f}\\},C_{2}=4NM^{2}_{\text{prod}}M_{\text{sum}}C^{2N-3}_{0}C^{N}_{1},C_{3}=NC_{2}^{N},C_{4}=(2\beta^{1/2}+2)^{N}C^{N}_{3}.$
(C.97)

In order to prove Theorem C.10, we give four lemmas.

######  Lemma C.11.

Assume that the same condition as in Theorem C.10 holds. Let
$s\in\\{1,\ldots,N-1\\}$ and $n\in\\{s+1,\ldots,N\\}$. Then, for any iteration
$t\geq 1$, element $m\in[M^{(n)}]$ and input
${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}$, the following inequality holds:

$\displaystyle|\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(n)})|$
(C.98) $\displaystyle\leq
2M_{\text{prod}}C_{0}^{N-1}\sum_{p=0}^{n-s-1}\sum_{i=1}^{M^{(n-1-p)}}\Bigl{[}\sigma^{(n-1-p)}_{i,t}(\tilde{\bm{\mu}}^{(n-2-p)}_{t}({\bm{x}}^{(s:n-2-p)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n-1-p)})\Bigr{]}.$
(C.99)

###### Proof.

From Lipschitz continuity of $\sigma^{(n)}_{m,t}(\cdot)$, the following holds:

$\displaystyle|\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(n)})|$
(C.100) $\displaystyle\leq
L_{\sigma}\|\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s-1)})-\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s)})\|_{1}$
(C.101)
$\displaystyle=L_{\sigma}\sum_{j=1}^{M^{(n-1)}}|\tilde{\mu}^{(n-1)}_{j,t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s-1)})-\tilde{\mu}^{(n-1)}_{j,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s)})|$
(C.102)
$\displaystyle=L_{\sigma}\sum_{j=1}^{M^{(n-1)}}|{\mu}^{(n-1)}_{j,t}(\tilde{\bm{\mu}}^{(n-2)}_{t}({\bm{x}}^{(s:n-2)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n-1)})-{\mu}^{(n-1)}_{j,t}(\tilde{\bm{\mu}}^{(n-2)}_{t}({\bm{x}}^{(s+1:n-2)}|{\bm{z}}^{(s)}),{\bm{x}}^{(n-1)})|.$
(C.103)

Here, noting that

$\displaystyle
f^{(k)}_{m}({\bm{y}},{\bm{x}})-\beta^{1/2}\sigma^{(k)}_{m,t}({\bm{y}},{\bm{x}})$
$\displaystyle\leq\mu^{(k)}_{m,t}({\bm{y}},{\bm{x}})$ (C.104)
$\displaystyle\leq
f^{(k)}_{m}({\bm{y}},{\bm{x}})+\beta^{1/2}\sigma^{(k)}_{m,t}({\bm{y}},{\bm{x}}),$
(C.105)

we have

$\displaystyle|$
$\displaystyle\mu^{(k)}_{m,t}({\bm{y}},{\bm{x}})-\mu^{(k)}_{m,t}({\bm{y}}^{\prime},{\bm{x}})|$
(C.106)
$\displaystyle\leq|f^{(k)}_{m}({\bm{y}},{\bm{x}})-f^{(k)}_{m}({\bm{y}}^{\prime},{\bm{x}})|+\beta^{1/2}\sigma^{(k)}_{m,t}({\bm{y}},{\bm{x}})+\beta^{1/2}\sigma^{(k)}_{m,t}({\bm{y}}^{\prime},{\bm{x}})$
(C.107)
$\displaystyle\leq|f^{(k)}_{m}({\bm{y}},{\bm{x}})-f^{(k)}_{m}({\bm{y}}^{\prime},{\bm{x}})|+\beta^{1/2}|\sigma^{(k)}_{m,t}({\bm{y}},{\bm{x}})-\sigma^{(k)}_{m,t}({\bm{y}}^{\prime},{\bm{x}})|+2\beta^{1/2}\sigma^{(k)}_{m,t}({\bm{y}}^{\prime},{\bm{x}})$
(C.108)
$\displaystyle\leq(L_{f}+\beta^{1/2}_{t}L_{\sigma})\|{\bm{y}}-{\bm{y}}^{\prime}\|_{1}+2\beta^{1/2}\sigma^{(k)}_{m,t}({\bm{y}}^{\prime},{\bm{x}}).$
(C.109)

Therefore, by substituting C.109 into C.103, it follows that

$\displaystyle|\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n)})-\sigma^{(n)}_{m,t}(\tilde{\bm{\mu}}^{(n-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(n)})|$
(C.110) $\displaystyle\leq
2\beta^{1/2}L_{\sigma}\sum_{j=1}^{M^{(n-1)}}\sigma^{(n-1)}_{j,t}\bigl{(}\tilde{\bm{\mu}}^{(n-2)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}^{(s)}),{\bm{x}}^{(n-1)})+L_{\sigma}M^{(n-1)}(L_{f}+\beta^{1/2}L_{\sigma})$
(C.111)
$\displaystyle\quad\cdot\|\tilde{\bm{\mu}}^{(n-2)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}^{(s-1)})-\tilde{\bm{\mu}}^{(n-2)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}^{(s)})\|_{1}$
(C.112) $\displaystyle\leq
2\beta^{1/2}L_{\sigma}\sum_{j=1}^{M^{(n-1)}}\sigma^{(n-1)}_{j,t}\bigl{(}\tilde{\bm{\mu}}^{(n-2)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(n-2)}|{\bm{z}}^{(s)}),{\bm{x}}^{(n-1)})$
(C.113)
$\displaystyle\quad+L_{\sigma}M^{(n-1)}(L_{f}+\beta^{1/2}L_{\sigma})\sum_{i=1}^{M^{(n-2)}}|\tilde{\mu}^{(n-2)}_{i,t}({\bm{x}}^{(s:n-2)}|{\bm{z}}^{(s-1)})-\tilde{\mu}^{(n-2)}_{i,t}({\bm{x}}^{(s+1:n-2)}|{\bm{z}}^{(s)})|$
(C.114) $\displaystyle\leq
2\beta^{1/2}L_{\sigma}\sum_{j=1}^{M^{(n-1)}}\sigma^{(n-1)}_{j,t}(\tilde{\bm{\mu}}^{(n-2)}_{t}({\bm{x}}^{(s:n-2)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n-1)})$
(C.115)
$\displaystyle\quad+2\beta^{1/2}L_{\sigma}M^{(n-1)}(L_{f}+\beta^{1/2}L_{\sigma})\cdot\sum_{i=1}^{M^{(n-2)}}\sigma^{(n-2)}_{i,t}(\tilde{\bm{\mu}}^{(n-3)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-3)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n-2)})$
(C.116)
$\displaystyle+L_{\sigma}M^{(n-1)}M^{(n-2)}(L_{f}+\beta^{1/2}L_{\sigma})^{2}\sum_{q=1}^{M^{(n-3)}}\Bigl{[}|\tilde{\mu}^{(n-3)}_{q,t}({\bm{x}}^{(s:n-3)}|{\bm{z}}^{(s-1)})-\tilde{\mu}^{(n-3)}_{q,t}({\bm{x}}^{(s+1:n-3)}|{\bm{z}}^{(s)})|\Bigr{]}$
(C.117) $\displaystyle\leq$ (C.118) $\displaystyle\vdots$ (C.119)
$\displaystyle\leq
2\beta^{1/2}L_{\sigma}M_{\text{prod}}(L_{f}+\beta^{1/2}L_{\sigma}+1)^{N-2}$
(C.120)
$\displaystyle\quad\cdot\sum_{p=0}^{n-s-2}\sum_{i=1}^{M^{(n-1-p)}}\Bigl{[}\sigma^{(n-1-p)}_{i,t}\Bigl{(}\tilde{\bm{\mu}}^{(n-2-p)}_{t}({\bm{x}}^{(s:n-2-p)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n-1-p)})\Bigr{]}$
(C.121)
$\displaystyle\quad+2M_{\text{prod}}\beta^{1/2}L_{\sigma}(L_{f}+\beta^{1/2}L_{\sigma}+1)^{N-2}\sum_{q=1}^{M^{(s)}}\sigma^{(s)}_{q,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})$
(C.122) $\displaystyle\leq
2M_{\text{prod}}(L_{f}+\beta^{1/2}L_{\sigma}+1)^{N-1}\sum_{p=0}^{n-s-1}\sum_{i=1}^{M^{(n-1-p)}}\Bigl{[}\sigma^{(n-1-p)}_{i,t}(\tilde{\bm{\mu}}^{(n-2-p)}_{t}({\bm{x}}^{(s:n-2-p)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n-1-p)})\Bigr{]}$
(C.123) $\displaystyle\leq
2M_{\text{prod}}C^{N-1}_{0}\sum_{p=0}^{n-s-1}\sum_{i=1}^{M^{(n-1-p)}}\Bigl{[}\sigma^{(n-1-p)}_{i,t}\bigl{(}\tilde{\bm{\mu}}^{(n-2-p)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(n-2-p)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(n-1-p)}\bigr{)}\Bigr{]}.$
(C.124)

∎

######  Lemma C.12.

Assume that the same condition as in Theorem C.10 holds. Let
$s\in\\{1,\ldots,N-1\\}$, and let $j\geq 0$ be an integer with $s+j\leq N$.
Then, for any iteration $t\geq 1$, element $m\in[M^{(n)}]$ and input
${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}$, the following inequality holds:

$\displaystyle\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)})$
$\displaystyle\leq\tilde{C}_{2}\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s)})+\tilde{C}_{2}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})$
(C.125)
$\displaystyle\quad+\tilde{C}_{2}\tilde{\sigma}^{(N-j-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j-1)}|{\bm{z}}^{(s-1)}),$
(C.126)

where

$\displaystyle\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)})$
(C.127)
$\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{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-p)})\Bigr{]}$
(C.128)

and $\tilde{C}_{2}=4NM^{2}_{\text{prod}}M_{\text{sum}}C^{2N-2}_{0}C^{N}_{1}$.

###### Proof.

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

$\displaystyle\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)})$
(C.129)
$\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{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-p)})\Bigr{]}$
(C.130) $\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{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-p)})\Bigr{]}$
(C.131)
$\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{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(N-p)})\Bigr{]}$
(C.132)
$\displaystyle+M_{\text{prod}}C^{N-1}_{0}\sum_{p=j}^{N-s-1}\sum_{i=1}^{M^{(N-p)}}\left(\sigma^{(N-p)}_{i,t}(\tilde{\bm{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-p)})\right.$
(C.133)
$\displaystyle\left.\quad-\sigma^{(N-p)}_{i,t}(\tilde{\bm{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}),{\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{x}}^{(s)}).$
(C.134)

Thus, from Lemma C.11 we get

$\displaystyle|\sigma^{(N-p)}_{i,t}(\tilde{\bm{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-p)})$
(C.135)
$\displaystyle\qquad-\sigma^{(N-p)}_{i,t}(\tilde{\bm{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(N-p)})|$
(C.136) $\displaystyle\leq 2M_{\text{prod}}C^{N-1}_{0}\sum_{r=0}^{N-p-s-1}$
(C.137)
$\displaystyle\quad\cdot\sum_{j=1}^{M^{(N-p-1-r)}}\Bigl{[}\sigma^{(N-p-1-r)}_{j,t}\Bigl{(}\tilde{\bm{\mu}}^{(N-p-2-r)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-p-2-r)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-p-1-r)}\Bigr{)}\Bigr{]}.$
(C.138)

By using this,
$\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)})$
can be written as

$\displaystyle\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)})$
(C.139) $\displaystyle\leq
M_{\text{prod}}C^{N-2}_{0}\sum_{p=j}^{N-s-1}\sum_{i=1}^{M^{(N-p)}}\sigma^{(N-p)}_{i,t}\Bigl{(}\tilde{\bm{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(N-p)}\Bigr{)}$
(C.140)
$\displaystyle\quad+M_{\text{prod}}C^{N-2}_{0}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})+2M^{2}_{\text{prod}}C^{2N-2}_{0}M_{\text{sum}}$
(C.141)
$\displaystyle\quad\cdot\sum_{p=j}^{N-s-1}\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{\mu}}^{(N-p-2-r)}_{t}({\bm{x}}^{(s:N-p-2-r)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-p-1-r)}\Bigr{)}\Bigr{]}.$
(C.142)

Here, we set $v=p+r$. Then, noting that $|\\{(p,r)\mid p+r=a\\}|\leq 2a$, we
obtain

$\displaystyle\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s-1)})$
(C.143) $\displaystyle\leq
M_{\text{prod}}C^{N-2}_{0}\sum_{p=j}^{N-s-1}\sum_{i=1}^{M^{(N-p)}}\sigma^{(N-p)}_{i,t}\Bigl{(}\tilde{\bm{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(N-p)}\Bigr{)}$
(C.144)
$\displaystyle+2M^{2}_{\text{prod}}C^{2N-2}_{0}M_{\text{sum}}\sum_{v=j}^{N-s-1}2N\sum_{j=1}^{M^{(N-v-1)}}\sigma^{(N-v-1)}_{j,t}\Bigl{(}\tilde{\bm{\mu}}^{(N-v-2)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-v-2)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-v-1)}\Bigr{)}$
(C.145)
$\displaystyle+M_{\text{prod}}C^{N-2}_{0}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})$
(C.146) $\displaystyle\leq
4NM^{2}_{\text{prod}}C^{2N-2}_{0}M_{\text{sum}}\sum_{p=j}^{N-s-1}\sum_{i=1}^{M^{(N-p)}}\sigma^{(N-p)}_{i,t}\Bigl{(}\tilde{\bm{\mu}}^{(N-p-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-p-1)}|{\bm{z}}^{(s)}),{\bm{x}}^{(N-p)}\Bigr{)}$
(C.147)
$\displaystyle+4NM^{2}_{\text{prod}}C^{2N-2}_{0}M_{\text{sum}}\sum_{v=j}^{N-s-1}\sum_{j=1}^{M^{(N-v-1)}}\sigma^{(N-v-1)}_{j,t}\Bigl{(}\tilde{\bm{\mu}}^{(N-v-2)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-v-2)}|{\bm{z}}^{(s-1)}),{\bm{x}}^{(N-v-1)}\Bigr{)}$
(C.148)
$\displaystyle+4NM^{2}_{\text{prod}}C^{2N-2}_{0}M_{\text{sum}}C^{N}_{1}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})$
(C.149)
$\displaystyle\leq\tilde{C}_{2}\tilde{\sigma}^{(N-j)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-j)}|{\bm{z}}^{(s)})+\tilde{C}_{2}\tilde{\sigma}^{(N-j-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-j-1)}|{\bm{z}}^{(s-1)})$
(C.150)
$\displaystyle\quad+\tilde{C}_{2}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)}).$
(C.151)

∎

######  Lemma C.13.

Assume that the same condition as in Theorem C.10 holds. Let
$s\in\\{1,\ldots,N-1\\}$ and $n\in\\{s+1,\ldots,N\\}$. Then, for any iteration
$t\geq 1$, element $m\in[M^{(n)}]$ and input
${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}$, the following inequality holds:

$\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(s:N)}|{\bm{z}}^{(s-1)})\leq
C_{3}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(s+1:N)}|{\bm{z}}^{(s)})+C_{3}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)}).$
(C.152)

###### Proof.

By repeatedly using Lemma C.12, we obtain

$\displaystyle\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}^{(s-1)})$
(C.153)
$\displaystyle=\tilde{\sigma}^{(N-0)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-0)}|{\bm{z}}^{(s-1)})$
(C.154)
$\displaystyle\leq\tilde{C}_{2}\tilde{\sigma}^{(N-0)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-0)}|{\bm{z}}^{(s)})+\tilde{C}_{2}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})+\tilde{C}_{2}\tilde{\sigma}^{(N-1)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-1)}|{\bm{z}}^{(s-1)})$
(C.155)
$\displaystyle\leq\tilde{C}_{2}\tilde{\sigma}^{(N-0)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-0)}|{\bm{z}}^{(s)})+\tilde{C}_{2}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})+\tilde{C}^{2}_{2}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})$
(C.156)
$\displaystyle\quad+\tilde{C}^{2}_{2}\tilde{\sigma}^{(N-1)}_{t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N-1)}|{\bm{z}}^{(s)})+\tilde{C}^{2}_{2}\tilde{\sigma}^{(N-2)}_{t}({\bm{x}}^{(s)},\ldots,{\bm{x}}^{(N-2)}|{\bm{z}}^{(s-1)})$
(C.157) $\displaystyle\leq$ (C.158) $\displaystyle\vdots$ (C.159)
$\displaystyle\leq(\tilde{C}_{2}+\tilde{C}^{2}_{2}+\cdots+\tilde{C}^{N-1}_{2})\tilde{\sigma}^{(N-0)}_{t}({\bm{x}}^{(s+1:N-0)}|{\bm{z}}^{(s)})+(\tilde{C}_{2}+\tilde{C}^{2}_{2}+\cdots+\tilde{C}^{N-1}_{2})\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)})$
(C.160)
$\displaystyle\leq(N-1)\tilde{C}^{N-1}_{2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(s+1)},\ldots,{\bm{x}}^{(N)}|{\bm{z}}^{(s)})+(N-1)\tilde{C}^{N-1}_{2}\sum_{i=1}^{M^{(s)}}\sigma^{(s)}_{i,t}({\bm{z}}^{(s-1)},{\bm{x}}^{(s)}).$
(C.161)

In addition, $(N-1)\tilde{C}^{N-1}_{2}$ can be bounded by

$\displaystyle(N-1)\tilde{C}^{N-1}_{2}$ $\displaystyle\leq
N\tilde{C}^{N-1}_{2}$ (C.162)
$\displaystyle=N(4NM^{2}_{\text{prod}}M_{\text{sum}}C^{2N-2}_{0}C^{N}_{1})^{N-1}$
(C.163) $\displaystyle\leq
N(4NM^{2}_{\text{prod}}M_{\text{sum}}C^{N}_{1})^{N}C^{2N^{2}-4N+2}_{0}$
(C.164) $\displaystyle\leq
N(4NM^{2}_{\text{prod}}M_{\text{sum}}C^{N}_{1})^{N}C^{2N^{2}-4N+N}_{0}$
(C.165)
$\displaystyle=N(4NM^{2}_{\text{prod}}M_{\text{sum}}C_{0}^{2N-3}C^{N}_{1})^{N}$
(C.166) $\displaystyle=NC^{N}_{2}=C_{3},$ (C.167)

we get Lemma C.13. ∎

######  Lemma C.14.

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

$\displaystyle\eta_{t}b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$
$\displaystyle\leq c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$ (C.168)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}).$
(C.169)

###### Proof.

From the definition of $c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$, it is
clear that $\eta_{t}b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\leq
c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$. On the other hand, from the
definition of $\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$,
letting

$(\tilde{\bm{x}}^{(n+1)},\ldots,\tilde{\bm{x}}^{(N)})=\operatorname*{arg\,max}_{({\bm{x}}^{(n+1)},\ldots,{\bm{x}}^{(N)})}\Bigl{(}\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(n:N)}|{\bm{y}}^{(n-1)})+\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(n:N)}|{\bm{y}}^{(n-1)}\Bigr{)}$
(C.170)

we obtain

$\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})=\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(n)},\tilde{\bm{x}}^{(n+1)}\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})+\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(n)},\tilde{\bm{x}}^{(n+1)},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)}).$
(C.171)

Similarly, $\mathrm{LCB}^{(F)}_{t}({\bm{y}}^{(n-1)})$ can be bounded as
follows:

$\mathrm{LCB}^{(F)}_{t}({\bm{y}}^{(n-1)})\geq\tilde{\mu}^{(N)}_{1,t}({\bm{x}}^{(n)},\tilde{\bm{x}}^{(n+1)}\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})-\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(n)},\tilde{\bm{x}}^{(n+1)},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)}).$
(C.172)

Hence, from the definition of $a^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$
and $b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$, we get

$\displaystyle a^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$
$\displaystyle\leq\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})-\mathrm{LCB}^{(F)}_{t}({\bm{y}}^{(n-1)})$
(C.173) $\displaystyle\leq
2\beta^{1/2}\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(n)},\tilde{\bm{x}}^{(n+1)},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(n-1)})$
(C.174) $\displaystyle\leq
2\beta^{1/2}b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}).$ (C.175)

Therefore, $c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$ can be written as

$\displaystyle c^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})$
$\displaystyle=\max\\{a^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}),\eta_{t}b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\\}$
(C.176)
$\displaystyle\leq\max\\{2\beta^{1/2}b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}),\eta_{t}b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)})\\}$
(C.177)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})b^{(n)}_{t}({\bm{x}}^{(n)}|{\bm{y}}^{(n-1)}).$
(C.178)

∎

By using these lemmas, we prove Theorem C.10.

###### Proof.

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

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

Thus, by combining C.180 and C.13,
$c^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$ can be bounded as follows:

$\displaystyle c^{(1)}_{t}$ $\displaystyle({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
(C.181)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})C_{3}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}+\eta_{t})C_{3}\tilde{\sigma}^{(N)}_{1,t}(\tilde{\bm{x}}^{(2)},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(1)})$
(C.182)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})C_{3}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}+\eta_{t})C_{3}b^{(2)}_{t}(\tilde{\bm{x}}^{(2)}|{\bm{y}}^{(1)})$
(C.183)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})C_{3}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}+\eta_{t})C_{3}\eta^{-1}_{t}c^{(2)}_{t}(\tilde{\bm{x}}^{(2)}|{\bm{y}}^{(1)})$
(C.184)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})C_{3}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}+\eta_{t})C_{3}\eta^{-1}_{t}c^{(2)}_{t}({\bm{x}}^{(2)}_{t+2}|{\bm{y}}^{(1)})$
(C.185)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})C_{3}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}+\eta_{t})^{2}C_{3}\eta^{-1}_{t}b^{(2)}_{t}({\bm{x}}^{(2)}_{t+2}|{\bm{y}}^{(1)})$
(C.186)
$\displaystyle\leq(2\beta^{1/2}+\eta_{t})C_{3}\sum_{i=1}^{M^{(1)}}\sigma^{(1)}_{i,t}({\bm{0}},{\bm{x}}^{(1)}_{t+1})+(2\beta^{1/2}+\eta_{t})^{2}C_{3}\eta^{-1}_{t}\cdot\tilde{\sigma}^{(N)}_{1,t}({\bm{x}}^{(2)}_{t+2},\tilde{\bm{x}}^{(3)},\ldots,\tilde{\bm{x}}^{(N)}|{\bm{y}}^{(1)}).$
(C.187)

Hence, by using Lemma C.13 again, we have

$\displaystyle c^{(1)}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$
$\displaystyle\leq(2\beta^{1/2}+\eta_{t}+1)^{N}C^{N}_{3}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})$
(C.188)
$\displaystyle\leq(2\beta^{1/2}+1+1)^{N}C^{N}_{3}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})$
(C.189)
$\displaystyle=C_{4}\eta^{-N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)}_{i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n}).$
(C.190)

This implies that

$c^{(1)2}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})\leq
C^{2}_{4}M_{\text{sum}}\eta^{-2N}_{t}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sigma^{(n)2}_{i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n}),$
(C.191)

where the inequality is given by the Cauchy–Schwarz inequality. Next, let
$T\in N\mathbb{Z}_{\geq 0}$ and $K=T/N$. Then, the following inequality holds:

$\displaystyle\sum_{t\in N\mathbb{Z}_{\geq
0}}^{KN}c^{(1)2}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$ $\displaystyle\leq
C^{2}_{4}M_{\text{sum}}\eta^{-2N}_{T}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\sum_{t\in
N\mathbb{Z}_{\geq
0}}^{T}\sigma^{(n)2}_{i,t}({\bm{y}}^{(n-1)},{\bm{x}}^{(n)}_{t+n})$ (C.192)
$\displaystyle\leq\frac{2}{\log(1+\sigma^{-2})}C^{2}_{4}M_{\text{sum}}\eta^{-2N}_{T}\sum_{n=1}^{N}\sum_{i=1}^{M^{(n)}}\gamma_{T}$
(C.193)
$\displaystyle=\frac{2C^{2}_{4}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\gamma_{T}\eta^{-2N}_{T}.$
(C.194)

Similarly, let $T^{\ast}=\operatorname*{arg\,min}_{t\in N\mathbb{Z}_{\geq
0},t\leq T}c^{(1)2}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$. Then, we obtain

$\displaystyle Kc^{(1)2}_{T^{\ast}}({\bm{x}}^{(1)}_{T^{\ast}+1}|{\bm{0}})$
$\displaystyle\leq\sum_{t\in N\mathbb{Z}_{\geq
0}}^{KN}c^{(1)2}_{t}({\bm{x}}^{(1)}_{t+1}|{\bm{0}})$ (C.195)
$\displaystyle\leq\frac{2C^{2}_{4}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\gamma_{T}\eta^{-2N}_{T}.$
(C.196)

This implies that

$\displaystyle
c^{(1)}_{T^{\ast}}({\bm{x}}^{(1)}_{T^{\ast}+1}|{\bm{0}})\leq\sqrt{\frac{2C^{2}_{4}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\gamma_{T}\eta^{-2N}_{T}K^{-1}}.$
(C.197)

Furthermore, from the property of CIs and the definition of the estimated
solution, the following inequalities hold:

$\displaystyle F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
$\displaystyle\leq\min_{t\in N\mathbb{Z}_{\geq 0},t\leq
T}\mathrm{UCB}^{(F)}_{t}({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
$\displaystyle\leq\mathrm{UCB}^{(F)}_{T^{\ast}}({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast}),$
(C.198) $\displaystyle
F(\hat{\bm{x}}^{(1)}_{T},\ldots,\hat{\bm{x}}^{(N)}_{T})$
$\displaystyle\geq\max_{t\in N\mathbb{Z}_{\geq 0},t\leq
T}\mathrm{LCB}^{(F)}_{t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
$\displaystyle\geq\mathrm{LCB}^{(F)}_{T^{\ast}}({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast}).$
(C.199)

This implies that

$\displaystyle
F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{T},\ldots,\hat{\bm{x}}^{(N)}_{T})$
$\displaystyle\leq
2\beta^{1/2}\tilde{\sigma}^{(N)}_{1,T^{\ast}}({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})$
(C.200) $\displaystyle\leq
2\beta^{1/2}b^{(1)}_{T^{\ast}}({\bm{x}}^{(1)}_{\ast}|{\bm{0}})$ (C.201)
$\displaystyle\leq
2{\beta}^{1/2}\eta^{-1}_{T^{\ast}}c^{(1)}_{T^{\ast}}({\bm{x}}^{(1)}_{\ast}|{\bm{0}})\leq
2{\beta}^{1/2}\eta^{-1}_{T}c^{(1)}_{T^{\ast}}({\bm{x}}^{(1)}_{T^{\ast}+1}|{\bm{0}}).$
(C.202)

Finally, noting that $K=T/N$, from C.197 we obtain

$\displaystyle
F({\bm{x}}^{(1)}_{\ast},\ldots,{\bm{x}}^{(N)}_{\ast})-F(\hat{\bm{x}}^{(1)}_{T},\ldots,\hat{\bm{x}}^{(N)}_{T})$
$\displaystyle\leq
2\beta^{1/2}\eta^{-1}_{T}\sqrt{\frac{2C^{2}_{4}M^{2}_{\text{sum}}}{\log(1+\sigma^{-2})}\gamma_{T}\eta^{-2N}_{T}K^{-1}}$
(C.203) $\displaystyle=\sqrt{\frac{8\beta
C^{2}_{4}M^{2}_{\text{sum}}N}{\log(1+\sigma^{-2})}\gamma_{T}\eta^{-2N-2}_{T}T^{-1}}$
(C.204) $\displaystyle<\sqrt{\xi^{2}}=\xi.$ (C.205)

∎

##  D Cascade Process Optimization Using CI-based AFs under Noisy Setting

In this section, we consider CI-based cascade process optimization methods
with observation noise. Hereafter, we assume that the observation noise
$\epsilon^{(n)}_{m}$ is a random variable with
$\mathbb{E}[\epsilon^{(n)}_{m}]=0$ and $-A\leq\epsilon^{(n)}_{m}\leq A$, where
$A$ is some positive constant. In addition, we assume that
$\epsilon^{(1)}_{1},\ldots,\epsilon^{(N)}_{M^{(N)}}$ are mutually independent,
and the distribution of the noise vector
${\bm{\epsilon}}=(\epsilon^{(1)}_{1},\ldots,\epsilon^{(N)}_{M^{(N)}})^{\top}$
is known. Finally, we also assume that noise vectors with respect to iteration
$t$, ${\bm{\epsilon}}_{1},\ldots,{\bm{\epsilon}}_{t}$, are independent and
identically distributed random variables having the same distribution of
${\bm{\epsilon}}$.

Next, we define several notations. For each $n\in[N]$, let
$\tilde{\mathcal{Y}}^{(n)}(\supset\mathcal{Y}^{(n)})$ be a set satisfying

$\forall{\bm{w}}\in\tilde{\mathcal{Y}}^{(n-1)},\forall{\bm{x}}\in\mathcal{X}^{(n)},f^{(n)}({\bm{w}},{\bm{x}})+{\bm{\epsilon}}^{(n)}\in\tilde{\mathcal{Y}}^{(n)},$
(D.1)

where $\tilde{\mathcal{Y}}^{(0)}=\\{{\bm{0}}\\}$ and
${\bm{\epsilon}}^{(n)}=(\epsilon^{(n)}_{1},\ldots,{\epsilon}^{(n)}_{M^{(n)}})^{\top}$.
Note that
${\bm{z}}^{(n)}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})\in\mathcal{Y}^{(n)}\subset\tilde{\mathcal{Y}}^{(n)}$.
In addition, for any realization ${\bm{\epsilon}}$ and input
${\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)}$, we define
${\bm{z}}^{(n)}_{{\bm{\epsilon}}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$ as

${\bm{z}}^{(n)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})=\begin{cases}{\bm{f}}^{(1)}({\bm{0}},{\bm{x}}^{(1)})+{\bm{\epsilon}}^{(1)}&(n=1),\\\
{\bm{f}}^{(n)}({\bm{z}}^{(n-1)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n-1)}),{\bm{x}}^{(n)})+{\bm{\epsilon}}^{(n)}&(n\geq
2).\end{cases}$ (D.2)

Furthermore, we define the function $G({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$
as

$G({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})=\mathbb{E}_{\bm{\epsilon}}[{\bm{z}}^{(N)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})].$
(D.3)

The function $G({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$ is the expected value
of the final-stage output with respect to ${\bm{\epsilon}}$ when
$({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$ is used. We emphasize that
$F({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\neq
G({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$ in general. Similarly, we define the
optimal solution of each function as

$\displaystyle({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})$
$\displaystyle=\operatorname*{arg\,max}_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X}}F({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}),$
(D.4) $\displaystyle({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})$
$\displaystyle=\operatorname*{arg\,max}_{({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})\in\mathcal{X}}G({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)}).$
(D.5)

By using these, for the selected input
${\bm{x}}^{(1)}_{t},\ldots,{\bm{x}}^{(N)}_{t}$ at iteration $t$, we define the
expected regret $r_{G,t}$, cumulative expected regret $R_{G,T}$ and simple
expected regret $r^{(\text{S})}_{G,T}$ as

$\displaystyle
r_{G,t}=G({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})-G({\bm{x}}^{(1)}_{t},\ldots,{\bm{x}}^{(N)}_{t}),$
(D.6) $\displaystyle R_{G,t}=\sum_{t=1}^{T}r_{G_{t}},\quad
r^{(\text{S})}_{G,T}=\min_{1\leq t\leq T}r_{G,t}.$ (D.7)

We also define the regret $r_{F,t}$, cumulative regret $R_{F,T}$ and simple
regret $r^{(\text{S})}_{F,T}$ as

$\displaystyle
r_{F,t}=F({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})-F({\bm{x}}^{(1)}_{t},\ldots,{\bm{x}}^{(N)}_{t}),$
(D.8) $\displaystyle R_{F,t}=\sum_{t=1}^{T}r_{F_{t}},\quad
r^{(\text{S})}_{F,T}=\min_{1\leq t\leq T}r_{F,t}.$ (D.9)

Finally, let $(\hat{\bm{x}}^{(1)}_{F,t},\ldots,\hat{\bm{x}}^{(N)}_{F,t})$ and
$(\hat{\bm{x}}^{(1)}_{G,t},\ldots,\hat{\bm{x}}^{(N)}_{G,t})$ be respectively
estimated solutions of
$({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})$ and
$({\bm{x}}^{(1)}_{G,\ast},\ldots,{\bm{x}}^{(N)}_{G,\ast})$ at iteration $t$.
Then, we define the regrets for estimated solutions, $\hat{r}_{F,t}$ and
$\hat{r}_{G,t}$, as

$\displaystyle\hat{r}_{F,t}$
$\displaystyle=F({\bm{x}}^{(1)}_{F,\ast},\ldots,{\bm{x}}^{(N)}_{F,\ast})-F(\hat{\bm{x}}^{(1)}_{F,t},\ldots,\hat{\bm{x}}^{(N)}_{F,t}),$
(D.10) $\displaystyle\hat{r}_{G,t}$
$\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}).$
(D.11)

###  D.1 Credible Interval

In this section, we construct a valid CI under the noisy setting. First, we
introduce the following regularity assumption instead of Assumption C.1.

######  Assumption D.1 (Regularity assumption under noisy setting).

For each $n\in[N]$, let $\tilde{\mathcal{Y}}^{(n-1)}\times\mathcal{X}^{(n)}$
be a compact set, and let $\mathcal{H}_{k^{(n)}}$ be an RKHS corresponding to
the kernel $k^{(n)}$. In addition, for each $n\in[N]$ and $m\in[M^{(n)}]$,
assume that $f^{(n)}_{m}\in\mathcal{H}_{k^{(n)}}$ with
$\|f^{(n)}_{m}\|_{{k^{(n)}}}\leq B$, where $B>0$ is some constant.
Furthermore, assume that the observation noise $\epsilon^{(n)}_{m}$ is a
random variable with $\mathbb{E}[\epsilon^{(n)}_{m}]=0$ and
$-A\leq\epsilon^{(n)}_{m}\leq A$, where $A$ is some positive constant. All
elements of
${\bm{\epsilon}}=(\epsilon^{(1)}_{1},\ldots,\epsilon^{(N)}_{M^{(N)}})$ are
mutually independent, and ${\bm{\epsilon}}_{1},{\bm{\epsilon}}_{2},\ldots$ are
i.i.d. random variables having the same distribution of ${\bm{\epsilon}}$.

Then, the following lemma holds under the noisy setting.

######  Lemma D.2 (Abbasi-Yadkori, 2012, Theorem 3.11).

Assume that Assumption D.1 holds. Let $\delta\in(0,1)$, and define

$\beta^{(n)}_{t}=\Bigl{(}B+\frac{A}{\sigma}\sqrt{\log\operatorname{det}\left(\bm{I}_{L_{t}^{(n)}}+\sigma^{-2}\bm{K}^{(n)}_{t}\right)+2\log(1/\delta)}\Bigr{)}^{2}.$
(D.12)

Then, for any $n\in[N]$ and $m\in[M^{(n)}]$, the following inequality holds
with probability at least $1-\delta$:

$\left|f^{(n)}_{m}(\bm{w},\bm{x})-\mu^{(n)}_{m,t}(\bm{w},\bm{x})\right|\leq(\beta_{t}^{(n)})^{1/2}\sigma^{(n)}_{m,t}(\bm{w},\bm{x}),\;\forall\bm{w}\in\tilde{\mathcal{Y}}^{(n-1)},\;\forall\bm{x}\in\mathcal{X}^{(n)},\;\forall
t\geq 1.$ (D.13)

###### Proof.

From Theorem 3.11 of Abbasi-Yadkori, (2012), it is sufficient to show that
$\epsilon^{(n)}_{m}$ has $A$-sub-Gaussian property, i.e.,

$\mathbb{E}[\exp(\lambda\epsilon^{(n)}_{m})]\leq\exp(\lambda^{2}A^{2}/2)\quad\forall\lambda\in\mathbb{R}.$
(D.14)

Noting that $\epsilon^{(n)}_{m}$ is a zero mean and bounded random variable,
using Hoeffding’s lemma Massart, (2007) we have

$\displaystyle\mathbb{E}[\exp(\lambda\epsilon^{(n)}_{m})]$
$\displaystyle\leq\exp(\lambda^{2}(A-(-A))^{2}/8)$ (D.15)
$\displaystyle=\exp(\lambda^{2}A^{2}/2)\quad\forall\lambda\in\mathbb{R}.$
(D.16)

Thus, $\epsilon^{(n)}_{m}$ has $A$-sub-Gaussian property D.14. ∎

From D.13, we have the following uniform bound.

######  Corollary D.3.

Assume that Assumption D.1 holds. Let $\delta\in(0,1)$, and define

$\displaystyle\beta^{(n)}_{t}$
$\displaystyle=\Bigl{(}B+\frac{A}{\sigma}\sqrt{\log\operatorname{det}\left(\bm{I}_{L_{t}^{(n)}}+\sigma^{-2}\bm{K}^{(n)}_{t}\right)+2\log(M_{\text{sum}}/\delta)}\Bigr{)}^{2},$
(D.17) $\displaystyle\beta_{t}$ $\displaystyle=\max_{1\leq n\leq
N,1\leq\tilde{t}\leq t}\beta^{(n)}_{\tilde{t}}.$ (D.18)

Then, for any $n\in[N]$ and $m\in[M^{(n)}],$ the following inequality holds
with probability at least $1-\delta$:

$\left|f^{(n)}_{m}(\bm{w},\bm{x})-\mu^{(n)}_{m,t}(\bm{w},\bm{x})\right|\leq\beta_{t}^{1/2}\sigma^{(n)}_{m,t}(\bm{w},\bm{x}),\;\forall\bm{w}\in\tilde{\mathcal{Y}}^{(n-1)},\;\forall\bm{x}\in\mathcal{X}^{(n)},\;\forall
t\geq 1.$ (D.19)

From Corollary D.3, we can also construct a valid CI for the $N$-stage cascade
process under the noisy setting. First, we construct CIs for
${\bm{z}}^{(n)}_{\bm{\epsilon}}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$ and
$G({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(N)})$. For any iteration $t\geq 1$,
realization ${\bm{\epsilon}}$ and input
$({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$, we define
$\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
as

$\displaystyle\tilde{\bm{z}}^{(n)}_{{\bm{\epsilon}},t}({\bm{x}}^{(1)},\ldots,{\bm{x}}^{(n)})$
$\displaystyle=\begin{cases}{\bm{\epsilon}}^{(1)}+{\bm{\mu}}^{(1)}_{t}({\bm{0}},{\bm{x}}^{(1)})&(n=1),\\\