# Optimal Observation-Intervention Trade-Off
in Optimisation Problems with Causal Structure

Kim Hammar
KTH Royal Institute of Technology
Stockholm, Sweden
<EMAIL_ADDRESS>&Neil Dhir22footnotemark: 2
Siemens Technology
Berkeley, California, USA
<EMAIL_ADDRESS>Equal contribution.

###### Abstract

We consider the problem of optimising an expensive-to-evaluate grey-box
objective function, within a finite budget, where known side-information
exists in the form of the causal structure between the design variables.
Standard black-box optimisation ignores the causal structure, often making it
inefficient and expensive. The few existing methods that consider the causal
structure are myopic and do not fully accommodate the observation-intervention
trade-off that emerges when estimating causal effects. In this paper, we show
that the observation-intervention trade-off can be formulated as a non-myopic
optimal stopping problem which permits an efficient solution. We give
theoretical results detailing the structure of the optimal stopping times and
demonstrate the generality of our approach by showing that it can be
integrated with existing causal Bayesian optimisation algorithms. Experimental
results show that our formulation can enhance existing algorithms on real and
synthetic benchmarks.

##  1 Introduction

This paper studies global optimisation of an expensive-to-evaluate _grey-box_
[5] objective function with known causal structure in the form of a causal
diagram (making it grey-box rather than ‘black-box’). In this setting, inputs
to the objective function correspond to interventions and outputs correspond
to causal effects. We assume that the objective function can be evaluated
(possibly with noise) at a finite number of inputs, either by measurement or
some estimation procedure. Each evaluation is associated with a cost and a
finite budget of total evaluations is prescribed. Since no known functional
form of the objective function is available, our goal is to find an input that
optimises the objective function by estimating the causal effects of a
sequence of interventions. This estimation can be done in two ways: i) by
intervening and conducting controlled experiments; and ii) by passively
observing and using the causal graph to estimate the causal effects (vis-à-vis
the do-calculus [45]). In choosing between these two options, an observation-
intervention trade-off emerges. On the one hand, interventions are costly but
allow us to reliably estimate causal effects. On the other hand, observations
are (usually) cheap to collect but may not always be sufficient to identify
causal effects. We show that this trade-off can be formulated as an optimal
stopping problem that permits an efficient solution [66, 54, 16].

Two principal algorithmic frameworks have been developed to solve optimisation
problems of the type described above: i) causal Bayesian optimisation (cbo)
algorithms [2, 3, 60, 15], which assume that the objective function is defined
over a continuous domain; and ii) causal multi-armed bandit (mab) algorithms
[31, 9, 37, 29, 35], which assume that the objective function is defined over
a discrete set of inputs. To our knowledge, no hybrid approach exists.
Compared to standard Bayesian optimisation (bo) and mabs, which ignore the
causal structure of the problem, cbo and causal mabs are able to exploit the
causal structure to improve sample efficiency. A drawback of the existing
causal approaches, however, is that they are myopic in the sense that they do
not consider more than one step into the future when deciding on
interventions. Another limitation is that the existing approaches rely on
heuristics to balance the observation-intervention trade-off and do not
quantify the cost of observing. Specifically, in the cbo setting, an
$\epsilon$-greedy strategy is adopted by Aglietti et al. [2] and a myopic
exploration approach is adopted by Sussex et al. [60] and the trade-off is
ignored in [3, 15]. In the causal mab setting, a heuristic approach is used by
Lattimore et al. [31] and the work in [9, 37, 29, 35] uses myopic exploration
approaches similar to Sussex et al. [60]. Moreover, all of the approaches
referenced above assume a) that an arbitrary number of observations can be
collected; and b) that there are no costs associated with collecting
observations. These assumptions are not realistic in many scenarios: to test
for high cholesterol in the US, a blood-test (observation) is required which
costs on average $51 [21] and the requisite intervention (statins) costs $139
[27]. Similarly, a prostate-specific antigen test to screen for prostate
cancer (observation) costs on average $40 [1] and the cost of a radical
prostatectomy procedure (intervention) is on average $34,720 [43, 26].

Main contributions. Motivated by the above shortcomings in existing work, we
present a general approach to extend existing cbo algorithms (the results are
fully extendable to the causal mab setting) to balance the intervention-
observation trade-off in an optimal and _non-myopic_ way, while taking
observation costs into account. From hereon, for brevity, we refer to our
approach as _Optimal Stopping for Causal Optimisation_ (osco). Our main
contributions are:

  * •

We formulate the observation-intervention trade-off as an optimal stopping
problem whose solution determines whether a given intervention should be
carried out or if it is more cost-effective to collect observational data.

  * •

We prove that the solution to the optimal stopping problem can be computed
efficiently and show that it can enhance existing cbo (and causal mab)
algorithms.

  * •

We characterise a set of variables called the _minimal observation set_ (mos),
which is the minimal set of variables that need to be observed to estimate the
causal effect of an intervention.

##  2 Theoretical background

This section covers notations and theoretical background on structural causal
models. The models and definitions introduced here provide a foundation for
the subsequent section where we describe our problem statement. A table of
notations is available in Appendix A. Finally, to ensure that the narrative
remains fluid we also introduce the mos in this section.

###  2.1 Structural causal models

#### Structural causal models.

A Structural Causal Model (scm) [45, Ch. 7, Def 7.1.1] is a semantic framework
to model the causal mechanisms of a system. Let $\mathscr{M}$ be a scm
parametrised by the quadruple
$\left\langle\mathbf{U},\mathbf{V},\mathbf{F},P\\!\left(\mathbf{U}\right)\right\rangle$.
Here $\mathbf{U}$ is a set of exogenous variables which follow a joint
distribution $P\\!\left(\mathbf{U}\right)$ and $\mathbf{V}$ is a set of
endogenous (observed) variables. Within $\mathbf{V}$ we distinguish between
three types of variables: manipulative
$\mathbf{X}\subseteq\mathbf{V}\setminus\mathbf{Y}\setminus\mathbf{N}$; non-
manipulative $\mathbf{N}\subseteq\mathbf{V}\setminus\mathbf{X}$ and targets
(outcome variables) $\mathbf{Y}\subseteq\mathbf{N}$.

Graphically, each scm induces a causal diagram (a directed acyclic graph, dag
for short) $\mathcal{G}=\left\langle\mathbf{V},\mathbf{E}\right\rangle$. Each
vertex in the graph corresponds to a variable and the directed arcs point from
members of $\mathrm{pa}(V_{i})_{\mathcal{G}}$ and $U_{i}$ toward $V_{i}$,
where $\mathrm{pa}(V_{i})_{\mathcal{G}}$ denotes the parent nodes of $V_{i}$
in $\mathcal{G}$ [45, Ch. 7]. The arcs represent a set of functions
$\mathbf{F}\triangleq\\{f_{i}\\}_{V_{i}\in\mathbf{V}}$ [36, §1]. Each function
$f_{i}$ is a mapping from (the respective domains of
$U_{i}\cup\mathrm{pa}(V_{i})_{\mathcal{G}}$ to $V_{i}$ – where
$U_{i}\subseteq\mathbf{U}$ and
$\mathrm{pa}(V_{i})_{\mathcal{G}}\subseteq\mathbf{V}\setminus V_{i}$. A
bidirected arc between $V_{i}$ and $V_{j}$ occurs if they share an unobserved
confounder, i.e. if $\mathbf{U}_{i}\cap\mathbf{U}_{j}\neq\varnothing$ [34]. If
each function $f_{i}\in\mathbf{F}$ is independent of time, the scm is said to
be stationary and if both $\mathbf{U}$ and $\mathbf{V}$ are finite the scm is
said to be finite. For a more incisive discussion on the properties of scms we
refer the reader to [45, 7].

#### Causal effects of interventions.

The do-operator $\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)$
represents the causal effect of an intervention that fixes a set of endogenous
variable(s) $\mathbf{X}$ to constant value(s) $\mathbf{x}$ irrespective of
their original mechanisms $\mathbf{F}$. This operation can be represented
graphically by removing the incoming arcs to $\mathbf{X}$ in $\mathcal{G}$. We
denote by $\mathcal{G}_{\overline{\mathbf{X}}}$ the mutilated graph obtained
by deleting from $\mathcal{G}$ all arcs pointing to nodes in $\mathbf{X}$.
Examples of mutilated graphs are shown in Fig. 1.

$X$$Z$$Y$

(a) $\mathcal{G}$.

$X$$Z$$Y$

(b) $\mathcal{G}_{\overline{Z}}$.

$X$$Z$$Y$

(c) $\mathcal{G}_{\overline{X}}$.

$X$$Z$$Y$

(d) $\mathcal{G}_{\overline{Z,X}}$.

Figure 1: Mutilated causal diagrams; nodes represent variables in an scm;
solid edges represent causal relations and dashed edges represent unobserved
confounding; the diagrams represent post-intervention worlds where a specific
intervention has been implemented, from left to right, these are:
$\text{do}\\!\left(\varnothing\right),\text{do}\\!\left(Z\right),\text{do}\\!\left(X\right)$
and $\text{do}\\!\left(X,Z\right)$; interventions are graphically represented
with the incoming arcs onto the intervention removed.

#### Estimating causal effects.

The goal of causal inference is to generate probabilistic formulas for the
effects of interventions in terms of observation probabilities. In this work
we accomplish this by employing Pearl [45]’s do-calculus, which is an
axiomatic system for replacing probability formulas containing the do-operator
with ordinary conditional probabilities. Application of the do-calculus
requires the interventions to be uniquely determined from $P(\mathbf{V})$ and
$\mathcal{G}$. Determining if this is the case is known as the _problem of
identification_ and has received considerable attention in the causal
inference literature [46, 45, 56, 57, 63, 62], formally:

######  Definition 1.

Causal effect identifiability [6, Def. 1]. Let $\mathbf{X},\mathbf{Y}$ be two
sets of disjoint variables and let $\mathcal{G}$ be the causal diagram. The
causal effect of an intervention
$\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)$ on a set of variables
$\mathbf{Y}$ is said to be identifiable from $P$ in $\mathcal{G}$ if
$P\\!\left(\mathbf{Y}\mid\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)\right)$
is _uniquely_ computable from $P(\mathbf{V})$ in any causal model that induces
$\mathcal{G}$.

###  2.2 Sets of endogenous variables

#### Intervention sets.

Given a causal graph $\mathcal{G}$ of an scm
$\mathscr{M}\triangleq\left\langle\mathbf{U},\mathbf{V},\mathbf{F},P\\!\left(\mathbf{U}\right)\right\rangle$
with a set of manipulative variables $\mathbf{X}$ and a target variable $Y$,
we can define _minimal intervention sets_ , which represent non-redundant
intervention sets for achieving an effect on $Y$:

######  Definition 2.

Minimal intervention set (mis) [35, Def. 2]. A set of manipulative variables
$\mathbf{X}\subseteq\mathbf{V}\setminus\\{Y\\}\setminus\mathbf{N}$ is said to
be a mis for $Y$ if there is no $\mathbf{X}^{\prime}\subset\mathbf{X}$ such
that
$\mathbb{E}{\left[Y\mid\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)\right]}=\mathbb{E}{\left[Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right)\right]}$
for every scm induced by $\mathcal{G}$. Denote by
$\mathbf{M}^{\mathbf{V}}_{\mathcal{G},Y}$ a set of miss given the scm
$\mathscr{M}$.

A subset of the set of miss can lead to the minimal value of $Y$:

######  Definition 3.

Possibly optimal minimal intervention set (pomis) [35, Def. 3].
$\mathbf{X}\in\mathbf{M}_{\mathcal{G},Y}^{\mathbf{V}}$ is a pomis if there
exists an scm induced by $\mathcal{G}$ such that
$\mathbb{E}{\left[Y\mid\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}^{*}\right)\right]}<\mathbb{E}{\left[Y\mid\operatorname{do}\\!\left(\mathbf{W}=\mathbf{w}^{*}\right)\right]}\
\forall\mathbf{W}\in\mathbf{M}_{\mathcal{G},Y}^{\mathbf{V}}\setminus\mathbf{X}$.
Denote by $\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}}$ a set of pomiss given the
scm $\mathscr{M}$.

#### Observation sets.

The solution to the _identification problem_ [57] tells us under what
conditions the effect of a given intervention can be computed from
$P\\!\left(\mathbf{V}\right)$ and the causal diagram $\mathcal{G}$. A number
of sound and complete algorithms exist which solve this problem [55, 57, 61,
25]. The solution, if it exists as per Def. 1, returns an expression
$Q^{\mathbf{X}}_{Y}$ which only contains observational measures. The set of
variables $\mathbf{Z}\subseteq\mathbf{V}$ occurring in $Q^{\mathbf{X}}_{Y}$ is
the _minimal observation set_ , which we introduce and formally define as

######  Definition 4.

Minimal observation set (mos). If
$P\\!\left(Y\mid\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)\right)$
is identifiable as per Def. 1 then $\exists Q^{\mathbf{X}}_{Y}$. If a)
$Q^{\mathbf{X}}_{Y}$ can be estimated by observing
$\mathbf{Z}\subseteq\mathbf{V}$ and b)
$\nexists\mathbf{Z}^{\prime}\subset\mathbf{Z}$ that allows us to estimate
$Q^{\mathbf{X}}_{Y}$, then $\mathbf{Z}$ is a mos. The mos which follows
$Q^{\mathbf{X}}_{Y}$ is denoted by $\mathbf{O}^{\mathbf{X}}_{\mathcal{G},Y}$.

$S$$W$$Y$$X$$Z$$B$

(a) $\mathcal{G}$.

$S$$W$$Y$$X$$Z$$B$

(b) $\mathcal{G}_{\overline{B}}$; see 1.

$S$$W$$Y$$X$$Z$$B$

(c) $\mathcal{G}_{\overline{B,W}}$; see 2.

Figure 2: Causal diagram $\mathcal{G}$ shown in Fig. 2(a) with two post-
intervention worlds in Fig. 2(b) and Fig. 2(c). Blue node colour indicates the
minimal set of variables which need to be measured to estimate the
identifiable causal effect.

We demonstrate Def. 4 by considering the causal diagrams in Fig. 2. Applying
the rules of do-calculus we can express the interventional distributions in
terms of observational mass functions:

$\displaystyle P\\!\left(Y\mid\operatorname{do}\\!\left(B=b\right)\right)$
$\displaystyle=\sum_{S}{P\\!\left(Y\mid
B,S\right)P\\!\left(S\right)}=Q^{\\{B\\}}_{Y}$ (1) $\displaystyle
P\\!\left(Y\mid\operatorname{do}\\!\left(B=b\right),\operatorname{do}\\!\left(W=w\right)\right)$
$\displaystyle=\sum_{S}{P\\!\left(Y\mid
B,W,S\right)P\\!\left(S\right)}=Q^{\\{B,W\\}}_{Y}$ (2)

The mos relative to $Q^{\\{B\\}}_{Y}$, shown on the right-hand-side (rhs) in 1
is $\mathbf{O}^{\\{B\\}}_{\mathcal{G},Y}=\\{Y,B,S\\}$ with the mutilated
causal diagram shown in Fig. 2(b). Similarly for Fig. 2(c) the mos is given by
$\mathbf{O}^{\\{B,W\\}}_{\mathcal{G},Y}=\\{Y,B,W,S\\}$, with
$Q^{\\{B,W\\}}_{Y}$ given on the rhs in 2.

##  3 Problem statement

Consider a causal graph $\mathcal{G}$ that encodes the causal relationship
among a finite set of variables $\mathbf{V}$ in a stationary scm
$\mathscr{M}=\left\langle\mathbf{U},\mathbf{V},\mathbf{F},P\\!\left(\mathbf{U}\right)\right\rangle$.
We are interested in manipulating $\mathbf{X}\subseteq\mathbf{V}$ to minimise
a target variable $Y\in\mathbf{V}\setminus\mathbf{X}$, which we assume is
bounded, i.e. $|y|\leq M<\infty$ for some $M\in\mathbb{R}$ and all
$y\in\text{dom}(Y)$. This objective is formally expressed as

$\displaystyle\operatorname*{minimise}_{\begin{subarray}{c}\mathbf{X}^{\prime}\in\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}};\\\
\mathbf{x}^{\prime}\in\text{dom}(\mathbf{X}^{\prime})\end{subarray}}\mu(\mathbf{X}^{\prime},\mathbf{x}^{\prime})$
$\displaystyle\triangleq\mathbb{E}[Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right)]$
(3)

We assume that interventions are atomic (also known as ‘hard’ [60] or
‘perfect’) as modelled by the do-operator [45]. ‘Soft’ or ‘stochastic’ [17]
intervention settings are left for future work. We further assume that the
functional relationships in $\mathscr{M}$ (i.e. $\mathbf{F}$) are unknown (but
$\mathcal{G}$ is assumed known), which means that minimising 3 requires
estimating
$\mathbb{E}{\left[Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right)\right]}$
from data. This estimation can be done in two ways: i) by intervening and
conducting a controlled experiment, which yields samples from the
interventional distribution
$P(Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right))$;
and ii) by passively observing
$\mathbf{O}^{\mathbf{X}^{\prime}}_{\mathcal{G},Y}$ (see Def. 4) and using
$\mathcal{G}$ to estimate the causal effect through the do-calculus [44]
(given that the causal effect is identifiable, otherwise the causal effect has
to be estimated by intervening). Both estimation procedures are perturbed by
additive Gaussian noise $\epsilon_{t}\sim\mathcal{N}(0,\sigma^{2})$ and
involve costs. Denote with $c(\mathbf{X}^{\prime},e_{t}=\mathfrak{I})$ the
cost of estimating
$\mathbb{E}[Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right)]$
by intervening and denote with $c(\mathbf{X}^{\prime},e_{t}=\mathfrak{O})$ the
cost of estimating the same expression by observing. The problem, then, is to
design a sequence of interventions
$(\operatorname{do}\\!\left(\mathbf{X}^{\prime}_{t}=\mathbf{x}^{\prime}_{t}\right))_{t\in\\{1,\ldots,T\\}}$
and a sequence of estimation procedures $(e_{t})_{t\in\\{1,\ldots,T\\}}$ to
find an intervention that minimises 3 while keeping the cumulative cost below
a maximum cost $K$. This problem can be formally stated as

$\displaystyle\operatorname*{minimise}_{\begin{subarray}{c}l_{t},\mathbf{X}^{\prime}_{t},\mathbf{x}^{\prime}_{t}\\\
t\in\\{1,\ldots,T\\}\end{subarray}}\quad$
$\displaystyle\left\\{\min_{t\in\\{1,\ldots,T\\}}\mu(\mathbf{X}^{\prime}_{t},\mathbf{x}^{\prime}_{t})-\mu(\mathbf{X}^{*},\mathbf{x}^{*})\right\\}$
(4a) subject to
$\displaystyle\sum_{t=1}^{T}c(\mathbf{X}^{\prime}_{t},e_{t})<K,\quad\text{
}\mathbf{X}^{\prime}_{t}\in\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}},\quad\text{}\mathbf{x}^{\prime}_{t}\in\text{dom}(\mathbf{X}_{t}^{\prime})$
$\displaystyle\forall t\in\\{1,\ldots,T\\}$ (4b) $\displaystyle
e_{t}\in\begin{dcases}\\{\mathfrak{I},\mathfrak{O}\\}&\text{if
}P(Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}_{t}=\mathbf{x}_{t}^{\prime}\right))\text{
is identifiable}\\\ \\{\mathfrak{I}\\}&\text{otherwise}\end{dcases}$
$\displaystyle\forall t\in\\{1,\ldots,T\\}$ (4c)

where ($\mathbf{X}^{*},\mathbf{x}^{*}$) denotes the minimiser of 3 and the
expression inside the brackets of 4a is the simple regret metric [22].
Further, 4b – 4c define the cost and domain constraints. The time-horizon $T$
is defined as the largest $t\in\mathbb{N}$ for which 4b is satisfied.

The above problem is challenging for two reasons. First, to select the optimal
intervention
$\operatorname{do}\\!\left(\mathbf{X}^{\prime}_{t}=\mathbf{x}^{\prime}_{t}\right)$
to evaluate at each stage $t\in\\{1,\ldots,T\\}$, it is necessary to take into
account both exploration (evaluating the causal effects in regions of high
uncertainty) and exploitation (evaluating the causal effects in regions deemed
promising based on previous evaluations). Second, in selecting the evaluation
procedures $(e_{t})_{t\in\\{1,\ldots,T\\}}$, it is necessary to balance the
trade-off between intervening (estimating causal effects through controlled
experimental evaluations) and observing (estimating causal effects through the
do-calculus).

The exploration-exploitation trade-off is well-studied in the statistical
learning literature (see textbooks [22, 33]) and numerous acquisition
functions that balance this trade-off have been proposed [59, 22, 33]. In
contrast, the observation-intervention trade-off, which is the focus of this
paper, is still relatively unexplored. In the following sections, we formulate
this trade-off as an optimal stopping problem and present our main solution
approach – _Optimal Stopping for Causal Optimisation_.

##  4 Optimal stopping formulation of the observation-intervention trade-off

Figure 3: Optimal Stopping for Causal Optimisation (osco) to balance the
intervention-observation trade-off; an optimisation policy $\pi_{O}$ decides
on a sequence of interventions
$(\operatorname{do}\\!\left(\mathbf{X}_{t}=\mathbf{x}_{t}\right))_{t\in\\{1,\ldots,T\\}}$
to evaluate in an scm $\mathscr{M}$ and the procedures to evaluate these
interventions are decided by solving optimal stopping problems
$(\mathcal{M}_{t})_{t\in\\{1,\ldots,T\\}}$.

We formulate the problem of designing the sequence of estimation procedures
$(e_{t})_{t\in\\{1,\ldots,T\\}}$ as a series of optimal stopping problems [66,
54, 47, 16]. In this formulation, we assume that an optimisation policy
$\pi_{\mathrm{O}}$ that inspects the available data and selects the
intervention
$\operatorname{do}\\!\left(\mathbf{X}^{\prime}_{t}=\mathbf{x}^{\prime}_{t}\right)$
to evaluate at each stage $t$, is given. We place no restrictions on how this
policy is obtained or implemented. It may, for example, be derived from an
acquisition function that balances the exploration-exploitation trade-off, as
is done in e.g. cbo [2]. We further assume that the objective function $\mu$ 3
and the functions $\mathbf{F}$ of the underlying scm are estimated by the
probabilistic models $\widehat{\mu}_{\mathbf{D}_{t}}$ and
$\widehat{\mathbf{F}}_{\mathbf{D}_{t}}$, respectively. Here $\mathbf{D}_{t}$
represents the available data at stage $t$ of the optimisation and as
$|\mathbf{D}_{t}|\rightarrow\infty$,
$\widehat{\mu}_{\mathbf{D}_{t}}\rightarrow\mu$ and
$\widehat{\mathbf{F}}_{\mathbf{D}_{t}}\rightarrow\mathbf{F}$.

The models $\widehat{\mu}$ and $\widehat{\mathbf{F}}$ allow us to guide the
optimisation process and quantify the expected value and uncertainty in
different regions of the interventional space 3. Specifically,
$\widehat{\mathbf{F}}_{\mathbf{D}_{t}}$ allows us to estimate causal effects
through the do-calculus and $\widehat{\mu}_{\mathbf{D}_{t}}$ represents the
current knowledge of the causal effects, allowing the optimisation policy
$\pi_{\mathrm{O}}$ to make informed decisions about which intervention to
evaluate at each stage.

Given the optimisation policy and the probabilistic models defined above, we
seek to design the sequence $(e_{t})_{t\in\\{1,\ldots,T\\}}$ to optimally
allocate the available evaluation budget between intervening and observing so
as to minimise 4a. This task can be formally expressed as a series of
Markovian and stationary optimal stopping problems
$\mathcal{M}_{1},\ldots,\mathcal{M}_{T}$ (see Fig. 3). To see this, note that,
at any stage $t$ of the optimisation, the models
$\widehat{\mu}_{\mathbf{D}_{t}}$ and $\widehat{\mathbf{F}}_{\mathbf{D}_{t}}$
allow us to simulate the growth of the dataset $\mathbf{D}_{t}$ and plan ahead
when deciding between intervening and observing. This look-ahead planning
involves two well-known challenges: i) the possibly mis-specified models
$\widehat{\mu}_{\mathbf{D}_{t}}$ and $\widehat{\mathbf{F}}_{\mathbf{D}_{t}}$
may lead to error-propagation when simulating many steps into the future [68];
and ii) the number of possible simulation trajectories of $\mathbf{D}_{t}$ is
infinite, which means that the planning problem corresponds to solving an
intractable Markov Decision Process (mdp) [49, 67]. Most existing algorithms
deal with these problems by truncating the planning horizon to one step [22,
2, 3, 60]. We propose to instead truncate the planning horizon to the next
intervention, which may involve simulating many observation steps. This means
that the growth of the dataset $\mathbf{D}_{t}$ follows a stationary Markov
process governed by the probability law

$\displaystyle\mathbf{S}_{1}$
$\displaystyle\triangleq\mathbf{D}_{t},\quad\mathbf{S}_{T+1}\triangleq\bot,\quad\mathbf{S}_{k+1}\triangleq\mathbf{S}_{k}\cup\\{\mathbf{o}_{k+1},k+1\\}\text{
}(k<T),\quad\mathbf{o}_{k<T}\sim\widehat{\mathbf{F}}_{\mathbf{D}_{t}}\left(\mathbf{O}^{\mathbf{X}_{t}}_{\mathcal{G},Y}\right)$
(5)

where $\mathbf{S}_{k}\in\mathbf{S}$ denotes the state of the process at time-
step $k$ and $\bot$ is an absorbing terminal state. At each time-step $k>1$ of
this process, a new observation $\mathbf{o}_{k}$ is sampled from
$\widehat{\mathbf{F}}_{\mathbf{D}_{t}}$ and added to the dataset
$\mathbf{D}_{t}\cup\\{\mathbf{o}_{2},\ldots,\mathbf{o}_{k-1}\\}$, which
results in a new state $\mathbf{S}_{k+1}$. The process is stopped whenever an
intervention ($e_{t}=\mathfrak{I}$) is carried out. Thus the problem of
deciding between intervening and observing becomes one of optimal stopping,
where the goal is to find an optimal stopping time $\mathcal{T}^{*}$:

$\displaystyle\mathcal{T}^{*}\in\operatorname*{argmax}_{\mathcal{T}\in\\{1,\ldots,T\\}}\left\\{\gamma^{\mathcal{T}-1}r(\mathbf{S}_{\mathcal{T}})-\sum_{k=1}^{\mathcal{T}-1}\gamma^{k-1}c(\mathbf{X}^{\prime}_{t},\mathfrak{O})\right\\}$
subject to 4b – 4c (6)

where $\mathcal{T}=\inf\\{t:t\geq 1,\text{ }e_{t}=\mathfrak{I}\\}$ and
$r(\mathbf{S}_{\mathcal{T}})$ denotes the reward of intervening (stopping) at
time $\mathcal{T}$. Note that if the observation process has not been stopped
at time $k=T-1$, the cost constraint in 4b forces it to stop at time $T$, even
if no intervention is carried out. We refer the reader to Appendix I for
background on optimal stopping theory.

Due to the Markov property, the stopping problem can equivalently be
formulated as an mdp and any stopping time that satisfies 6 is also a solution
to the following Bellman equation [16, Thm. 3.2]

$\displaystyle\max_{e_{t}\in\\{\mathfrak{I},\mathfrak{O}\\}}\left\\{r(\mathbf{S}_{k}),\int\ldots\int_{\text{dom}(\mathbf{O}^{\mathbf{X}_{t}}_{\mathcal{G},Y})}P_{\widehat{\mathbf{F}_{\mathbf{D}_{t}}}}(\mathbf{o}_{k})V^{*}(\mathbf{S}_{k}\cup\\{\mathbf{o}_{k+1}\\})\operatorname{d}\mathbf{O}^{\mathbf{X}_{t}}_{\mathcal{G},Y}-c(\mathbf{X}^{\prime}_{t},\mathfrak{O})\right\\}$
(7)

subject to 4b – 4c and 5.

By solving 6, we obtain the optimal stopping time $\mathcal{T}^{*}$, which
decides the next evaluation procedure $e_{t}$. In particular, if
$\mathcal{T}^{*}=1$, the causal effect is estimated by intervening
($e_{t}=\mathfrak{I}$) and otherwise the causal effect is estimated by
observing ($e_{t}=\mathfrak{O}$). In either case, the resulting samples are
used to update the probabilistic models $\widehat{\mu}_{\mathbf{D}_{t}}$ and
$\widehat{\mathbf{F}}_{\mathbf{D}_{t}}$ and proceed to the next stage of the
optimisation, wherein the next stopping problem $\mathcal{M}_{t+1}$ is
defined. Note that a solution to 6 always exists since $\mathcal{T}$ is
restricted to the finite set $\\{1,\ldots,T\\}$, where $T<\infty$ [16, Thm.
3.2].

#### The stopping reward.

A key issue in the design of the above stopping problem is the stopping reward
$r(\mathbf{S}_{\mathcal{T}})$, which models how beneficial it is to intervene
given the state $\mathbf{S}_{\mathcal{T}}$. An intervention can be beneficial
to the optimisation in two ways. First, it can improve the current estimate of
the optimum. Second, it can reduce the uncertainty in the objective function
$\mu$. We model these two benefits with $\widehat{\mu}_{\mathbf{S}_{k}}$ and
the information gain measure $I$ [18], respectively:

$\displaystyle r(\mathbf{S}_{T})$ $\displaystyle\triangleq\eta
I(\mathbf{S}_{k};\mu)\text{ and }r(\mathbf{S}_{k<T})\triangleq\eta
I(\mathbf{S}_{k};\mu)-\kappa\widehat{\mu}_{\mathbf{S}_{k}}(\mathbf{X}_{k}^{\prime},\mathbf{x}_{k}^{\prime})-\tau\frac{\text{Vol}(\mathbf{V})}{\text{Vol}(\mathbf{S}_{k})}-c(\mathbf{X}^{\prime}_{k},\mathfrak{I})$
(8)

Here $r(\bot)\triangleq 0$ and $\eta,\tau$ and $\kappa$ are scalar constants.
The information gain
$I(\mathbf{S}_{k};\mu)=H(\mathbf{S}_{k})-H(\mathbf{S}_{k}|\mu)$ quantifies the
reduction in uncertainty about $\mu$ from revealing the dataset
$\mathbf{S}_{k}$, where $H$ is the differential entropy function [18, 59]. The
terms
$\widehat{\mu}_{\mathbf{S}_{k}}(\mathbf{X}_{k}^{\prime},\mathbf{x}_{k}^{\prime})$
and $c(\mathbf{X}^{\prime}_{k},\mathfrak{I})$ quantify the expected value and
the cost of the intervention, respectively. Finally,
$\frac{\text{Vol}(\mathbf{V})}{\text{Vol}(\mathbf{S}_{k})}$ denotes the convex
hull of the interventional domain of $\mathbf{V}$ divided by the convex hull
of the observations in $\mathbf{S}_{k}$. The purpose of this term is to
incentivise collection of observations in the beginning of the optimisation
when $|\mathbf{D}_{t}|$ is small and it is not possible to plan ahead using
the models $\widehat{\mu}$ and $\widehat{\mathbf{F}}$ (a similar term is used
in [2]).

###  4.1 Efficient computation of the optimal stopping time

Equation 7 implies that it is optimal to intervene (stop) whenever
$r(\mathbf{S}_{k})\geq\alpha_{\mathbf{S}_{k}}$, where
$\alpha_{\mathbf{S}_{k}}$ denotes the second expression inside the
maximisation in 7. This means that we can divide the state space into two
subsets defined by

$\displaystyle\mathscr{S}_{T-k}\triangleq\\{\mathbf{S}_{k}\mid\mathbf{S}_{k}\in\mathbf{S},r(\mathbf{S}_{k})\geq\alpha_{\mathbf{S}_{k}}\\}\quad\text{and}\quad\mathscr{C}_{T-k}\triangleq\\{\mathbf{S}_{k}\mid\mathbf{S}_{k}\in\mathbf{S},r(\mathbf{S}_{k})<\alpha_{\mathbf{S}_{k}}\\}$
(9)

where $\mathscr{S}_{l}$ and $\mathscr{C}_{l}$ are the stopping and
continuation sets with $l$ time-steps remaining, respectively. These sets
cannot overlap and their union $\mathscr{S}_{l}\cup\mathscr{C}_{l}$ covers the
state space $\mathbf{S}$. Since the set of admissible stopping times in 6
decreases as $l\rightarrow 1$, the stopping sets form an increasing sequence
$\mathscr{S}_{l}\subseteq\mathscr{S}_{l-1}\subseteq\ldots\subseteq\mathscr{S}_{1}$
and similarly the continuation sets form a decreasing sequence
$\mathscr{C}_{l}\supseteq\mathscr{C}_{l-1}\supseteq\ldots\supseteq\mathscr{C}_{1}$.
Using these sets, the optimal stopping time can be expressed as

$\displaystyle\mathcal{T}^{*}$ $\displaystyle=\min\left\\{k\mid
k\in\mathbb{N},\text{ }\mathbf{S}_{T-k}\in\mathscr{S}_{k}\right\\}$ (10)

Based on 9-10 we state the following structural result regarding the optimal
stopping times for the stopping problem defined in 6.

######  Theorem 1.

Given the stopping problem in 6, if a) the optimisation policy
$\pi_{\mathrm{O}}$ is such that
$\widehat{\mu}_{\mathbf{S}}(\pi_{\mathrm{O}}(\mathbf{S}))$ is supermodular and
$c(\pi_{\mathrm{O}}(\mathbf{S}),\mathfrak{I})$ is non-increasing in
$|\mathbf{S}|$; and b) $I(\mathbf{S}_{k};\mu)$ is submodular, then
$\mathscr{S}_{1}$ is closed. That is,
$P(\mathbf{S}_{k+1}=\mathbf{s}_{k+1}\mid\mathbf{S}_{k}=\mathbf{s}_{k})=0$ if
$\mathbf{s}_{k}\in\mathscr{S}_{1}$ and
$\mathbf{s}_{k+1}\not\in\mathscr{S}_{1}$.

###### Proof.

See Appendix D. ∎

Informally, Theorem 1 states that if a state $\mathbf{s}_{k}$ is encountered
for which it is better to intervene than to collect one more observation and
then intervene, then no matter the next observation, the next state will
always satisfy the same property. This result hinges on two assumptions.
Assumption a) states, informally, that as the uncertainty about $\mu$ is
reduced, the optimisation policy $\pi_{\mathrm{O}}$ explores less and instead
prefers exploiting regions of the interventional space that are deemed
promising based on $\widehat{\mu}_{\mathbf{S}}$. This assumption is for
example satisfied by an $\epsilon$-greedy optimisation policy with decaying
$\epsilon$. Similarly, the informal interpretation of assumption b) is that
the gain of collecting observations reduces with the number of observations.
The conditions for b) to hold are given in [28, Prop. 2] and are true in
general. They hold for example if $\widehat{\mu}_{\mathbf{S}}$ is a Gaussian
process (gp) [59].

A direct consequence of Theorem 1 is that the optimal stopping time can be
obtained from a simple rule that is efficient to implement in practice, as
stated in the following corollary.

######  Corollary 1.

If assumptions a) and b) in Theorem 1 hold, then the optimal stopping time is
given by

$\displaystyle\mathcal{T}^{*}$ $\displaystyle=\min\left\\{k\mid
k\in\mathbb{N},\text{
}r(\mathbf{S}_{k})\geq\mathbb{E}_{\mathbf{o}_{k+1}}\left[r(\mathbf{S}_{k}\cup\\{\mathbf{o}_{k+1}\\})\right]-c(\mathbf{X}^{\prime}_{t},\mathfrak{O})\right\\}$
(11)

and the stopping sets are all equal, i.e.
$\mathscr{S}_{1}=\mathscr{S}_{2}=\ldots=\mathscr{S}_{T-1}$.

###### Proof.

See Appendix E. ∎

Corollary 1 states that the stopping problem in 6, which characterises the
observation-intervention trade-off for the optimisation problem in 4, permits
an optimal solution that is efficient to implement in practical algorithms. In
the following sections, we compare this solution to existing approaches and
explain how it can be integrated with existing algorithms for optimisation
problems with causal structure (e.g. cbo and causal mab algorithms). The
pseudo-code for integrating the optimal stopping problem with the existing
algorithms is listed in Algorithm 1 in Appendix H.

##  5 Related work

Problems of optimising decision variables arise in many settings, ranging from
the control of physical and computer systems to managing entire economies [49,
48]. Depending on the characteristics of the optimisation problem, different
solution methods are appropriate (e.g. convex optimisation [14], dynamic
programming [13] and black-box optimisation [33, 22]). We limit the following
discussion to related work that studies grey-box optimisation problems with
known causal structure. This line of research can be divided into two main
approaches: causal bo and causal mabs.

#### Causal Bayesian optimisation.

The literature on bo [30, 41] is extensive (see textbook [22] and survey
[53]). Most of the prior work on bo is focused on the black-box setting and
ignores prior knowledge about the objective function (see the recent tutorial
paper by Astudillo & Frazier [5] for examples of prior knowledge). bo problems
with known causal structure are usually studied under the aegis of the scm
framework, as is the case in this paper and in [2, 3, 60, 15, 4]. Astudillo &
Frazier [5] departs from this idea by instead leveraging function networks in
place of scms. Another design choice which differ among existing works is the
intervention model. This paper studies the hard intervention model, which is
consistent with [2, 3, 15], but differ from [5, 60], which study the soft
intervention model. Further, all of the existing works (including this paper)
except [15, 4] have in common that they assume the causal structure to be
known. Branchini et al. [15] and Alabed & Yoneki [4] do not make this
assumption and instead explore techniques that combine causal discovery with
causal bo.

This work differs from the previous research on causal bo in two main ways.
First, we propose a solution to balance the observation-intervention trade-off
that emerges in grey-box optimisation problems with causal structure. Existing
works either ignore this trade-off or rely on heuristics to balance it.
Second, we quantify the costs associated with collecting observations and
estimating causal effects via the do-calculus, which previous works do not
(they generally assume that observations can be collected without cost).

#### Causal multi-armed bandits.

Non-trivial dependencies amongst bandit arms are typically listed under
_structured_ bandits. When that structure is explicitly causal the namesake
follows [34, 42, 38]. The literature on causal bandits is richer than that of
causal bo. Bareinboim et al. [8] were the first to explore the connection
between causal reasoning and mab algorithms. Lattimore et al. [32] and Sen et
al. [52] introduced methods for best-arm identification and non-trivial
challenges that arise when unobserved confounders (ucs) are present in the
scm, which is explored in [34, 36] where the authors introduce the notion of
pomiss for graphs with and without non-manipulative variables respectively.
More recently in [64] the authors prove regret bounds for causal mabs with
linear scms, binary intervention domains and soft interventions. In the listed
works thus far, the graph is assumed known. This assumption is relaxed in
[39]. Another direction is _budgeted_ mabs [40] where pulling an arm comes as
a fixed cost and the agent has a finite budget which she has to spend
judiciously to find the best arm subject to that limitation.

Similar to the existing work in causal bo, the main differences between this
paper and the previous work on causal mab are a) that we propose a solution to
the observation-intervention trade-off; and b) we quantify the costs
associated with collecting observations. Further, to our knowledge, ours is
the first study that combines the structured and the budgeted mab approaches.

$X$$Z$$Y$

(a) Chain.

$X$$Z$$Y$

(b) Chain w. uc.

AgeBMIAsp.Stat.Can.PSA

(c) PSA level.

$S$$W$$Y$$X$$Z$$B$

(d) Synthetic.

Figure 4: Causal diagrams for the scms in the experimental evaluation; non-
manipulative variables $\mathbf{N}\setminus\\{Y\\}$ are shaded and the outcome
variable in each diagram is $Y\in\mathbf{N}$ apart from Fig. 4(c) where the
outcome variable is the PSA node.

##  6 Experimental evaluation

We integrate osco with state-of-the-art algorithms for optimisation problems
with causal structure and evaluate these on a variety of synthetic and real-
world scms with dags given in Fig. 4.

#### Baselines.

Several algorithms for solving optimisation problems of the type defined in 3
(i.e. optimisation problems with causal structure) have emerged in recent
years. These algorithms include cbo [2, Alg. 1], mcbo [60, Alg. 2], dcbo [3,
Alg. 1], ceo [15, Alg. 1], the parallel bandit algorithm [31, Alg. 1], causal
Thompson sampling [9, 29, Alg. 1], c-ucb [37, Alg.1 ] and kl-ucb [35, Alg. 3].
Among these algorithms, we choose to integrate our solution (osco) with cbo
[2, Alg. 1], mcbo [60, Alg. 2] and c-ucb [37, Alg.1 ] as those algorithms are
most consistent with our problem setting and assumptions. We leave the
integration of osco with other algorithms to future work. We also compare osco
against three heuristic baselines: a) intervene, b) observe and c) random,
which correspond to policies that a) always intervene, b) always observe and
c) selects between intervening and observing randomly. These latter results
can be found in the appendices.

(a) cbo with $\epsilon$-greedy (as used in [2]).

(b) cbo with osco.

Figure 5: Collected data and estimated models from running cbo with and
without osco to solve 3 for the chain scm [2, Fig. 3] (see Fig. 4(a)); the
blue curves and the shaded blue areas show the mean and standard deviation of
the estimated models $\widehat{\mathbf{F}}$ and $\widehat{\mu}$; the red and
orange dots show observations and interventions respectively; the black lines
show the scm functions $\mathbf{F}$ and the causal effects $\mu$.

Figure 6: Convergence curves and computational overhead for cbo, mcbo and
c-ucb with and without osco for different scms and causal mabs; the curves
indicate the mean and standard deviation ($\pm\frac{\sigma}{\sqrt[]{3}}$) over
three evaluations with different random seeds; the columns from left to right
on the first row relate to the scms in Fig. 4(a), Fig. 4(b), Fig. 4(c) and
Fig. 4(d) respectively; the first two columns on the second row show
convergence curves for different observation costs (all other curves are based
on the observation cost $c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})=2^{-2}$) and
the right-most column concerns the bandit version of the synthetic scm in Fig.
4(d).

#### Experiment setup.

We run all experiments with three different random seeds and show the
convergence curves of the simple regret metric
$\operatorname*{arg\,min}_{k\in\\{1,\ldots,t\\}}\mu(\mathbf{X}_{k},\mathbf{x}_{k})-\mu(\mathbf{X}^{*},\mathbf{x}^{*}_{k})$
3 for $t=1,\ldots,T$ [22] (this is consistent with the metric reported in [2]
but differs from [60, 37] which reports the cumulative regret metric [33]).
Hyperparameters are listed in Appendix G and were chosen based on cross-
validation. Throughout, we assume that the dataset at the start of the
optimisation is empty ($\mathbf{D}_{1}=\varnothing$). This contrasts with [2]
and [60], which assume $|\mathbf{D}_{1}|>0$ in all experiments. When we
compare against cbo we utilise mos (Def. 4) to reduce the observation costs.
We do not utilise mos when we compare against mcbo as mcbo relies on complete
observations. Further, we only evaluate mcbo on the scms available in the
official implementation [60], namely the chain scm and the PSA scm. In all
implementations of osco, we implement the stopping rule implied in Corollary 1
(even in cases when the assumptions of the corollary do not hold, in which
case it provides an approximation of the optimal stopping time). Complete
experimental details can be found in the appendix.

#### Results discussion.

Figure 5 shows the estimated probabilistic models $\widehat{\mu}$ and
$\widehat{\mathbf{F}}$ when running cbo with two different policies for
balancing the intervention-observation trade-off: i) the $\epsilon$-greedy
policy used in [2]; and ii) the osco approach described in Section 4. We note
in the lowest plots that the optimal intervention is
$\operatorname{do}\\!\left(Z=-3.20\right)$ (with target value $Y=-2.17$) and
that this intervention is found in both cases. We further note that cbo with
osco is able to accurately estimate the interventional distributions through
the do-calculus. The main differences between cbo with $\epsilon$-greedy and
cbo with osco are a) cbo with $\epsilon$-greedy collects only $3$
observations, spending most of the evaluation budget on interventions, whereas
cbo with osco uses most of the evaluation budget to collect observations; and
b) that cbo with $\epsilon$-greedy observes all endogenous variables whereas
cbo with osco only observes the mos
$\mathbf{O}^{Z}_{\mathcal{G},Y}=\\{Z,Y\\}$. That cbo uses most of the
evaluation budget on intervening whereas cbo with osco uses most of the budget
on observations can be explained by two main reasons. First, the definition of
$\epsilon$ in [2, Eq. 6] implies that the probability of observing in cbo with
$\epsilon$-greedy is close to $0$ when the number of previously collected
observations is low. Second, the optimal stopping formulation in 11 implies
that cbo with osco will observe rather than intervene when it is more cost-
effective.

Figure 6 compares osco with baselines. The first row in Fig. 6 shows
convergence curves of cbo and mcbo with and without osco for the chain scm
(Fig. 4(a) and Fig. 4(b) – with and without an uc respectively), the synthetic
scm (Fig. 4(d)) and the PSA scm (Fig. 4(c)). An ablation study for different
observation costs is shown in the two left-most plots of the second row of
Fig. 6. The right-most plots in the second row of Fig. 6 show a) converge
curves of c-ucb with and without osco for the bandit version of the synthetic
scm (Fig. 4(d)); and b) the computational overhead of osco. We note that cbo
with osco outperforms cbo and finds the optimal intervention for all scms
within the prescribed evaluation budget. Similarly, we observe that c-ucb with
osco is more cost-efficient than c-ucb without osco for the synthetic scm. We
explain the efficient convergence of osco by its design, which a) uses look-
ahead-planning to decide between observing and intervening based on what is
most cost effective; and b) utilises mos (Def. 4) to limit the variables that
need to be observed. We further note that mcbo with osco outperforms mcbo on
the chain and PSA scms. Moreover, we observe that the performance of cbo is
better than that of mcbo on average, which is consistent with the results
reported in [60]. This result can be explained by the design of mcbo, which is
optimised for the cumulative regret metric rather than the simple regret.
Finally, we observe that the computational overhead of osco per iteration is
less than a factor of $2$. Extended evaluation results can be found in
Appendix F.

##  7 Conclusion

Figure 7: Execution times per iteration with and without osco for some of the
example scms. The height of each bar indicates the mean execution time from
$100$ measurements and the error bars indicate the standard deviations.

We have formally defined the observation-intervention trade-off that emerges
in optimisation problems with causal structure and have shown that this trade-
off can be formulated as a non-myopic optimal stopping problem whose solution
determines when a causal effect should be estimated by intervening and when it
is more cost-effective to collect observational data. We have also
characterised the minimal set of variables that need to be observed to
estimate the causal effect – the minimal observation set (mos). Extensive
evaluation results on real and synthetic scms show that the optimal stopping
formulation can enhance existing algorithms and that the computational
overhead is manageable. This paper opens up several directions for future
research. One direction is to extend our model to include soft interventions
and longer planning horizons. Another direction is to evaluate different
reward functions in the optimal stopping problem.

## References

  * ABIM Foundation [2014] ABIM Foundation.  PSA Blood Test for Prostate Cancer.  https://www.choosingwisely.org/patient-resources/psa-test-for-prostate-cancer/, 2014\.  Accessed: 2023-03-23.
  * Aglietti et al. [2020] Aglietti, V., Lu, X., Paleyes, A., and González, J.  Causal Bayesian Optimization.  In _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pp. 3155–3164. PMLR, 26–28 Aug 2020.
  * Aglietti et al. [2021] Aglietti, V., Dhir, N., González, J., and Damoulas, T.  Dynamic Causal Bayesian Optimization.  In _Advances in Neural Information Processing Systems_ , volume 35, 2021.
  * Alabed & Yoneki [2022] Alabed, S. and Yoneki, E.  Bograph: Structured bayesian optimization from logs for expensive systems with many parameters.  In _Proceedings of the 2nd European Workshop on Machine Learning and Systems_ , EuroMLSys ’22, pp. 45–53, New York, NY, USA, 2022. Association for Computing Machinery.  ISBN 9781450392549.  doi: 10.1145/3517207.3526977.
  * Astudillo & Frazier [2021] Astudillo, R. and Frazier, P. I.  Thinking inside the box: A tutorial on grey-box bayesian optimization.  In _2021 Winter Simulation Conference (WSC)_ , pp. 1–15. IEEE, 2021\.
  * Bareinboim & Pearl [2012] Bareinboim, E. and Pearl, J.  Causal inference by surrogate experiments: z-identifiability.  _arXiv preprint arXiv:1210.4842_ , 2012.
  * Bareinboim & Pearl [2016] Bareinboim, E. and Pearl, J.  Causal inference and the data-fusion problem.  _Proceedings of the National Academy of Sciences_ , 113(27):7345–7352, 2016.
  * Bareinboim et al. [2015a] Bareinboim, E., Forney, A., and Pearl, J.  Bandits with unobserved confounders: A causal approach.  _Advances in Neural Information Processing Systems_ , 28:1342–1350, 2015a.
  * Bareinboim et al. [2015b] Bareinboim, E., Forney, A., and Pearl, J.  Bandits with unobserved confounders: A causal approach.  In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015b.
  * Bather [2000] Bather, J.  _Decision Theory: An Introduction to Dynamic Programming and Sequential Decisions_.  John Wiley and Sons, Inc., USA, 2000.  ISBN 0471976490.
  * Bellman [1957a] Bellman, R.  A markovian decision process.  _Journal of Mathematics and Mechanics_ , 6(5):679–684, 1957a.
  * Bellman [1957b] Bellman, R.  _Dynamic Programming_.  Dover Publications, 1957b.  ISBN 9780486428093.
  * Bertsekas [2005] Bertsekas, D. P.  _Dynamic Programming and Optimal Control_ , volume I.  Athena Scientific, Belmont, MA, USA, 3rd edition, 2005.
  * Boyd & Vandenberghe [2004] Boyd, S. and Vandenberghe, L.  _Convex Optimization_.  Cambridge University Press, March 2004.  ISBN 0521833787.
  * Branchini et al. [2023] Branchini, N., Aglietti, V., Dhir, N., and Damoulas, T.  Causal entropy optimization.  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , volume 206 of _Proceedings of Machine Learning Research_ , pp. 8586–8605. PMLR, 25–27 Apr 2023.
  * Chow et al. [1971] Chow, Y., Robbins, H., and Siegmund, D.  Great expectations: The theory of optimal stopping.  In _Journal of the Royal Statistical Society_ , 1971.
  * Correa & Bareinboim [2020] Correa, J. and Bareinboim, E.  A calculus for stochastic interventions: Causal effect identification and surrogate experiments.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pp. 10093–10100, 2020.
  * Cover & Thomas [2006] Cover, T. M. and Thomas, J. A.  _Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing)_.  Wiley-Interscience, July 2006.  ISBN 0471241954.
  * Evans et al. [2000] Evans, M., Swartz, T., and Swartz, A.  _Approximating Integrals Via Monte Carlo and Deterministic Methods_.  Oxford statistical science series. Oxford University Press, 2000.  ISBN 9780198502784.
  * Ferro et al. [2015] Ferro, A., Pina, F., Severo, M., Dias, P., Botelho, F., and Lunet, N.  Use of statins and serum levels of prostate specific antigen.  _Acta Urológica Portuguesa_ , 32(2):71–77, 2015.
  * Frank DiVincenzo, k-health [2022] Frank DiVincenzo, k-health.  How much does blood work cost in 2022?  https://khealth.com/learn/healthcare/how-much-does-bloodwork-cost/, 2022\.  Accessed: 2023-04-17.
  * Garnett [2023] Garnett, R.  _Bayesian Optimization_.  Cambridge University Press, 2023.  to appear.
  * GPyOpt [2016] GPyOpt.  Gpyopt: A bayesian optimization framework in python.  http://github.com/SheffieldML/GPyOpt, 2016.
  * Hammar & Stadler [2022] Hammar, K. and Stadler, R.  Intrusion prevention through optimal stopping.  _IEEE Transactions on Network and Service Management_ , 19(3):2333–2348, 2022.  doi: 10.1109/TNSM.2022.3176781.
  * Huang & Valtorta [2006] Huang, Y. and Valtorta, M.  Identifiability in causal bayesian networks: A sound and complete algorithm.  In _AAAI_ , pp. 1149–1154, 2006.
  * Imber et al. [2020] Imber, B. S., Varghese, M., Ehdaie, B., and Gorovets, D.  Financial toxicity associated with treatment of localized prostate cancer.  _Nature Reviews Urology_ , 17(1):28–40, 2020\.
  * Jacqueline Slobin, TalktoMira [2022-08-22] Jacqueline Slobin, TalktoMira.  What’s the Least Expensive Cholesterol Medication in 2021?  https://www.talktomira.com/post/how-much-do-statins-cost-without-insurance, 2022-08-22.  Accessed: 2023-04-17.
  * Krause & Guestrin [2005] Krause, A. and Guestrin, C.  Near-optimal nonmyopic value of information in graphical models.  In _UAI_ , pp. 324–331. AUAI Press, 2005.  ISBN 0-9749039-1-4.
  * Kroon et al. [2022] Kroon, A. D., Mooij, J., and Belgrave, D.  Causal bandits without prior knowledge using separating sets.  In Schölkopf, B., Uhler, C., and Zhang, K. (eds.), _Proceedings of the First Conference on Causal Learning and Reasoning_ , volume 177 of _Proceedings of Machine Learning Research_ , pp. 407–427. PMLR, 11–13 Apr 2022.
  * Kushner [1962] Kushner, H. J.  A versatile stochastic model of a function of unknown and time varying form.  _Journal of Mathematical Analysis and Applications_ , 5(1):150–167, 1962.  ISSN 0022-247X.  doi: https://doi.org/10.1016/0022-247X(62)90011-2.
  * Lattimore et al. [2016a] Lattimore, F., Lattimore, T., and Reid, M. D.  Causal bandits: Learning good interventions via causal inference.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , NIPS’16, pp. 1189–1197, Red Hook, NY, USA, 2016a. Curran Associates Inc.  ISBN 9781510838819.
  * Lattimore et al. [2016b] Lattimore, F., Lattimore, T., and Reid, M. D.  Causal bandits: Learning good interventions via causal inference.  In _Advances in Neural Information Processing Systems_ , pp. 1181–1189, 2016b.
  * Lattimore & Szepesvári [2020] Lattimore, T. and Szepesvári, C.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lee & Bareinboim [2018] Lee, S. and Bareinboim, E.  Structural causal bandits: where to intervene?  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Lee & Bareinboim [2019] Lee, S. and Bareinboim, E.  Structural causal bandits with non-manipulable variables.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):4164–4172, Jul. 2019.  doi: 10.1609/aaai.v33i01.33014164.
  * Lee & Bareinboim [2020] Lee, S. and Bareinboim, E.  Characterizing optimal mixed policies: Where to intervene and what to observe.  _Advances in neural information processing systems_ , 33, 2020.
  * Lu et al. [2020a] Lu, Y., Meisami, A., Tewari, A., and Yan, W.  Regret analysis of bandit problems with causal background knowledge.  In Peters, J. and Sontag, D. (eds.), _Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)_ , volume 124 of _Proceedings of Machine Learning Research_ , pp. 141–150. PMLR, 03–06 Aug 2020a.
  * Lu et al. [2020b] Lu, Y., Meisami, A., Tewari, A., and Yan, W.  Regret analysis of bandit problems with causal background knowledge.  In _Conference on Uncertainty in Artificial Intelligence_ , pp. 141–150. PMLR, 2020b.
  * Lu et al. [2021] Lu, Y., Meisami, A., and Tewari, A.  Causal bandits with unknown graph structure.  _Advances in Neural Information Processing Systems_ , 34:24817–24828, 2021.
  * Madani et al. [2004] Madani, O., Lizotte, D. J., and Greiner, R.  The budgeted multi-armed bandit problem.  In _International Conference on Computational Learning Theory_ , pp. 643–645. Springer, 2004.
  * Močkus [1975] Močkus, J.  On bayesian methods for seeking the extremum.  In Marchuk, G. I. (ed.), _Optimization Techniques IFIP Technical Conference Novosibirsk, July 1–7, 1974_ , pp. 400–404, Berlin, Heidelberg, 1975\. Springer Berlin Heidelberg.  ISBN 978-3-540-37497-8.
  * Nair et al. [2021] Nair, V., Patil, V., and Sinha, G.  Budgeted and non-budgeted causal bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2017–2025. PMLR, 2021.
  * Pate et al. [2014] Pate, S. C., Uhlman, M. A., Rosenthal, J. A., Cram, P., and Erickson, B. A.  Variations in the open market costs for prostate cancer surgery: a survey of US hospitals.  _Urology_ , 83(3):626–631, 2014.
  * Pearl [2009a] Pearl, J.  _Causality: Models, Reasoning and Inference_.  Cambridge University Press, USA, 2nd edition, 2009a.
  * Pearl [2009b] Pearl, J.  _Causality: models, reasoning and inference_.  Cambridge university press, 2009b.
  * Pearl & Robins [1995] Pearl, J. and Robins, J. M.  Probabilistic evaluation of sequential plans from causal models with hidden variables.  In _UAI_ , volume 95, pp. 444–453. Citeseer, 1995.
  * Peskir & Shiryaev [2006] Peskir, G. and Shiryaev, A.  _Optimal stopping and free-boundary problems_.  Lectures in mathematics (ETH Zürich). Springer, 2006.
  * Powell [2011] Powell, W. B.  _Approximate Dynamic Programming: Solving the Curses of Dimensionality_.  Wiley Series in Probability and Statistics. Wiley, Hoboken, NJ, USA, 2nd edition, 2011.
  * Puterman [1994] Puterman, M. L.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley and Sons, Inc., USA, 1st edition, 1994.  ISBN 0471619779.
  * Ross [1983] Ross, S. M.  _Introduction to Stochastic Dynamic Programming: Probability and Mathematical_.  Academic Press, Inc., USA, 1983.  ISBN 0125984200.
  * Rubinstein & Kroese [2016] Rubinstein, R. Y. and Kroese, D. P.  _Simulation and the Monte Carlo Method_.  Wiley Publishing, 3rd edition, 2016.  ISBN 1118632168.
  * Sen et al. [2017] Sen, R., Shanmugam, K., Dimakis, A. G., and Shakkottai, S.  Identifying best interventions through online importance sampling.  In _International Conference on Machine Learning_ , pp. 3057–3066. PMLR, 2017.
  * Shahriari et al. [2015] Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and De Freitas, N.  Taking the human out of the loop: A review of bayesian optimization.  _Proceedings of the IEEE_ , 104(1):148–175, 2015\.
  * Shirayev [2007] Shirayev, A. N.  _Optimal Stopping Rules_.  Springer-Verlag Berlin, 2007.  Reprint of russian edition from 1969.
  * Shpitser & Pearl [2006a] Shpitser, I. and Pearl, J.  Identification of conditional interventional distributions.  In _Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence_ , pp. 437–444, Arlington, Virginia, USA, 2006a. AUAI Press.
  * Shpitser & Pearl [2006b] Shpitser, I. and Pearl, J.  Identification of joint interventional distributions in recursive semi-markovian causal models.  In _Proceedings of the 21st National Conference on Artificial Intelligence_ , volume 2, pp. 1219–1226. AAAI Press, 2006b.
  * Shpitser & Pearl [2008] Shpitser, I. and Pearl, J.  Complete identification methods for the causal hierarchy.  _Journal of Machine Learning Research_ , 9(9), 2008.
  * Snell [1952] Snell, J. L.  Applications of martingale system theorems.  _Transactions of the American Mathematical Society_ , 73:293–312, 1952.
  * Srinivas et al. [2012] Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. W.  Information-theoretic regret bounds for gaussian process optimization in the bandit setting.  _IEEE Transactions on Information Theory_ , 58(5):3250–3265, 2012.
  * Sussex et al. [2022] Sussex, S., Makarova, A., and Krause, A.  Model-based causal bayesian optimization, 2022.
  * Tian & Pearl [2002] Tian, J. and Pearl, J.  A general identification condition for causal effects.  In _Eighteenth National Conference on Artificial Intelligence_ , volume 18, pp. 567–573, 2002.
  * Tikka & Karvanen [2018] Tikka, S. and Karvanen, J.  Identifying causal effects with the r package causaleffect.  _arXiv preprint arXiv:1806.07161_ , 2018.
  * Tikka et al. [2021] Tikka, S., Hyttinen, A., and Karvanen, J.  Causal effect identification from multiple incomplete data sources: A general search-based approach.  _Journal of Statistical Software_ , 99(5):1–40, 2021.
  * Varici et al. [2022] Varici, B., Shanmugam, K., Sattigeri, P., and Tajer, A.  Causal bandits for linear structural equation models.  _arXiv preprint arXiv:2208.12764_ , 2022.
  * Vives [1990] Vives, X.  Nash equilibrium with strategic complementarities.  _Journal of Mathematical Economics_ , 19(3):305–321, 1990.  ISSN 0304-4068.  doi: https://doi.org/10.1016/0304-4068(90)90005-T.  URL https://www.sciencedirect.com/science/article/pii/030440689090005T.
  * Wald [1947] Wald, A.  _Sequential Analysis_.  Wiley and Sons, New York, 1947.
  * Wu & Frazier [2019] Wu, J. and Frazier, P.  Practical two-step lookahead bayesian optimization.  In Wallach, H., Larochelle, H., Beygelzimer, A., d Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Yue & Kontar [2020] Yue, X. and Kontar, R. A.  Why non-myopic bayesian optimization is promising and how far should we look-ahead? a study via rollout.  In Chiappa, S. and Calandra, R. (eds.), _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pp. 2808–2818. PMLR, 26–28 Aug 2020.

###### Contents

  1. 1 Introduction
  2. 2 Theoretical background
    1. 2.1 Structural causal models
    2. 2.2 Sets of endogenous variables
  3. 3 Problem statement
  4. 4 Optimal stopping formulation of the observation-intervention trade-off
    1. 4.1 Efficient computation of the optimal stopping time
  5. 5 Related work
  6. 6 Experimental evaluation
  7. 7 Conclusion
  8. A Notation
  9. B Modelling assumptions
  10. C Causal-effect derivation
  11. D Proof of Theorem 1
  12. E Proof of Corollary 1
  13. F Additional evaluation results
    1. F.1 Chain scm
    2. F.2 Chain scm with an unobserved confounder
    3. F.3 PSA scm
    4. F.4 Synthetic scm
  14. G Hyperparameters
    1. G.1 Hyperparameters for the chain scm
    2. G.2 Hyperparameters for the chain scm with an unobserved confounder
    3. G.3 Hyperparameters for the synthetic example scm
    4. G.4 Hyperparameters for the PSA scm
    5. G.5 Synthetic causal mab
  15. H Pseudocode and implementation of osco
  16. I Background on Markovian optimal stopping problems
    1. I.1 Markov decision processes
    2. I.2 Markovian optimal stopping problems

##  Appendix A Notation

Random variables are denoted by upper-case letters (e.g. $X$) and their values
by lower-case letters (e.g. $x$). The probability mass or density of a random
variable $X$ is denoted by $P\\!\left(X\right)$. We use $x\sim
P\\!\left(X\right)$ to denote that $x$ was sampled from $P\\!\left(X\right)$.
The expectation of a function $f$ with respect to a random variable $X$ is
denoted by $\mathbb{E}_{X}[f]$. Sets of variables and their values are noted
by bold upper-case and lower-case letters respectively (e.g. $\mathbf{x}$ and
$\mathbf{X}$). Operators, function spaces and tuples are represented with
upper case calligraphic letters (e.g. $\mathcal{M}$). The power set of a set
$\mathbf{X}$ is denoted with $\mathcal{P}(\mathbf{X})$. The set of all
probability distributions over a set $\mathbf{X}$ (i.e. the
$(|\mathbf{X}|-1)$-dimensional unit simplex) is denoted with
$\Delta(\mathbf{X})$. We make extensive use of the do-calculus (for details
see [45, §3.4]). The domain of a variable is denoted by $\text{dom}(\cdot)$
where e.g. $x\in\text{dom}(X)$ and $\mathbf{x}\in\text{dom}(\mathbf{X})\equiv
x_{1}\times x_{2}\times\ldots\times
x_{|\mathbf{x}|}\in\text{dom}(X_{1})\times\text{dom}(X_{2})\times\ldots\times\text{dom}(X_{|\mathbf{x}|})$.
The set of real numbers and the set of $n$-dimensional real vectors are
denoted with $\mathbb{R}$ and $\mathbb{R}^{n}$ respectively. We adopt family
relationships
$\mathrm{pa(X)_{\mathcal{G}},ch(X)_{\mathcal{G}},an(X)_{\mathcal{G}}}$ and
$\mathrm{de(X)}_{\mathcal{G}}$ to denote parents, children, ancestors and
descendants of a given variable $X$ in a graph $\mathcal{G}$;
$\mathrm{Pa,Ch,An}$ and $\mathrm{De}$ extends $\mathrm{pa,ch,an}$ and
$\mathrm{de}$ by including the argument as the result. For example
$\mathrm{Pa}(X)_{\mathcal{G}}=\mathrm{pa}(X)_{\mathcal{G}}\cup\\{X\\}$. With a
set of variables as argument,
$\mathrm{pa}(\mathbf{X})_{\mathcal{G}}=\bigcup_{X\in\mathbf{X}}\mathrm{pa}(X)_{\mathcal{G}}$
and similarly defined for other relations.

Table 1: Notation used throughout the paper. Notation(s) | Description
---|---
$\mathscr{M}$ | quadruple defining an scm $\mathscr{M}=\left\langle\mathbf{U},\mathbf{V},\mathbf{F},P\\!\left(\mathbf{U}\right)\right\rangle$
$\mathbf{V}$ | set of endogeneous variables in an scm
$\mathbf{U}$ | set of exogeneous variables in an scm
$\mathbf{Y}$ | set of target variables in an scm
$\mathbf{X}$ | set of manipulative variables in an scm
$\mathbf{N}$ | set of non-manipulative variables in an scm
$\mathbf{F}$ | structural equation model of an scm
$\mathcal{G}$ | causal diagram (dag) of an scm (with nodes $\mathbf{V}$)
$\mathbf{E}$ | edges of $\mathcal{G}$
$\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)$ | the do-operator [45]
$\mathcal{G}_{\overline{\mathbf{X}}}$ | the mutilated graph obtained by deleting from $\mathcal{G}$ all arcs pointing to nodes in $\mathbf{X}$
$\mathbf{M}^{\mathbf{V}}_{\mathcal{G},Y}$ | set of miss (Def. 2) for an scm with endogeneous variables $\mathbf{V}$ and target variable $Y$
$\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}}$ | set of pomiss (Def. 3) for an scm with endogeneous variables $\mathbf{V}$ and target variable $Y$
$\mathbf{O}^{\mathbf{X}}_{\mathcal{G},Y}$ |  mos (Def. 4) for an identifiable intervention $P\\!\left(Y\mid\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)\right)$
$Q_{Y}^{\mathbf{X}}$ | do-calculus expression to estimate $P\\!\left(Y\mid\operatorname{do}\\!\left(\mathbf{X}=\mathbf{x}\right)\right)$ from $P(\mathbf{V})$
$\mu(\mathbf{X}^{{}^{\prime}},\mathbf{x}^{{}^{\prime}})$ | shorthand for $\mathbb{E}[Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right)]$
$\mathbf{X}^{*},\mathbf{x}^{*}$ | optimal intervention set $\mathbf{X}^{*}$ and intervention levels $\mathbf{x}^{*}$
$e$ | estimation procedure, $e\in\\{\mathfrak{I},\mathfrak{O}\\}$
$\mathfrak{I}$ | estimation by intervention
$\mathfrak{O}$ | estimation by observation
$c(\mathbf{X}^{{}^{\prime}},e)$ | cost of estimating $\mathbb{E}[Y\mid\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right)]$ using procedure $e\in\\{\mathfrak{I},\mathfrak{O}\\}$
$T$ | time horizon of the optimisation
$K$ | maximum evaluation cost
$\mathbf{D}_{t}$ | dataset of measured observations and interventions at stage $t$ of the optimisation
$\widehat{\mu}_{\mathbf{D}_{t}}$ | probabilistic model of $\mu$ based on $\mathbf{D}_{t}$
$\widehat{\mathbf{F}}_{\mathbf{D}_{t}}$ | probabilistic model of $\mathbf{F}$ based on $\mathbf{D}_{t}$
$\mathcal{M}_{t}$ | stopping problem at stage $t$ of the optimisation
$\mathbf{S}_{k},\mathbf{o}_{k}$ | state and observation at stage $k$ of an optimal stopping problem
$\bot$ | terminal state of an optimal stopping problem
$r(\mathbf{S}_{k})$ | stopping reward at stage $k$ of an optimal stopping problem
$\mathcal{T}$ | stopping time
$\gamma$ | discount factor for an optimal stopping problem
$\mathscr{S},\mathscr{C}$ | stopping and continuation sets for an optimal stopping problem

##  Appendix B Modelling assumptions

This sections contains two tables which detail our modelling assumptions on
the causal inference and optimal stopping sides respectively.

Table 2: Causal inference assumptions. Assumption | Description
---|---
$|\mathbf{V}|<\infty$ | the set of endogenous variables is finite
univariate target $Y\in\mathbf{V}$ | we do not consider multivariate targets $\mathbf{Y}\subset\mathbf{V}$, $|\mathbf{Y}|>1$
target $Y\in\mathbf{V}$ is bounded |  $|y|\leq M<\infty$ for some $M\in\mathbb{R}$ and all $y\in\text{dom}(Y)$
atomic interventions | interventions $\operatorname{do}\\!\left(\mathbf{X}^{\prime}=\mathbf{x}^{\prime}\right)$ in 3 are atomic [17]
stationary dag topology | the dag topology is independent of time $t$
stationary $\mathbf{F}$ | the functions $f_{i}\in\mathbf{F}$ are independent of time $t$
$\mathcal{G}$ is a dag | causal diagrams are free of cycles
identifiability methods | methods based on $P(\mathbf{V})$ only (i.e. non-experimental [63, Table 1])
Table 3: Optimal stopping assumptions. Assumption | Description
---|---
$c(\mathbf{L},\mathfrak{O})>0\text{ }\forall\mathbf{L}\in\mathcal{P}(\mathbf{V})$ | positive observation costs
$c(\mathbf{M},\mathfrak{I})>0\text{ }\forall\mathbf{M}\in\mathcal{P}(\mathbf{V})$ | positive intervention costs
$c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})<M<\infty\text{ }\forall\mathbf{L}\in\mathcal{P}(\mathbf{V})$ | bounded observation costs ($M\in\mathbb{R}$)
$c(\mathbf{X}^{{}^{\prime}},\mathfrak{I})<M<\infty\text{ }\forall\mathbf{M}\in\mathcal{P}(\mathbf{X})$ | bounded intervention costs ($M\in\mathbb{R}$)
$T<\infty$ | finite time horizon $\implies$ $\mathcal{T}^{*}<\infty$ 6

##  Appendix C Causal-effect derivation

Derivation [7] for estimating the causal effect of $X$ on $Y$ in Fig. 1(a). We
use the shorthand $P_{X}(Y)$ here to denote the interventional distribution
$P\\!\left(Y\mid\operatorname{do}\\!\left(X=x\right)\right)$. See [45, Thm.
3.4.1] for the three rules of do-calculus.

###### Proof.

Summing over $Z$ gives

$P_{X}\left(Y\right)=\sum_{Z}{P_{X}\left(Y,Z\right)}$ (12)

By C-component factorisation, we have

$=\sum_{Z}{P_{X,Y}\left(Z\right)P_{X,Z}\left(Y\right)}$ (13)

Task 1: Compute $P_{X,Y}\left(Z\right)$

The third rule of do-calculus can be applied using the independence
$\left(Y\perp Z|X\right)_{\mathcal{G}_{\overline{X,Y}}}$ (see Fig. 1).

$P_{X,Y}\left(Z\right)={{P_{X}\left(Z\right)}}$ (14)

The second rule of do-calculus can be applied using the independence
$\left(X\perp Z\right)_{\mathcal{G}_{\overline{}\underline{X}}}$ (see Fig. 1).

$={{P\left(Z\middle|X\right)}}$ (15)

Task 2: Compute $P_{X,Z}\left(Y\right)$

The third rule of do-calculus can be applied using the independence
$\left(X\perp Y|Z\right)_{\mathcal{G}_{\overline{X,Z}}}$ (see Fig. 1).

$P_{X,Z}\left(Y\right)=P_{Z}\left(Y\right)$ (16)

Summing over $X^{\prime}$ gives

$=\sum_{X^{\prime}}{P_{Z}\left(X^{\prime},Y\right)}$ (17)

Task 2.1: Compute $P_{Z}\left(X^{\prime},Y\right)$

We compute the effect inside the sum. By the chain rule, we have

$P_{Z}\left(X^{\prime},Y\right)=P_{Z}\left(Y\middle|X^{\prime}\right)P_{Z}\left(X^{\prime}\right)$
(18)

The third rule of do-calculus can be applied using the independence
$\left(Z\perp X^{\prime}\right)_{\mathcal{G}_{\overline{Z}}}$ (see Fig. 1).

$=P_{Z}\left(Y\middle|X^{\prime}\right){{P\left(X^{\prime}\right)}}$ (19)

The second rule of do-calculus can be applied using the independence
$\left(Z\perp Y|X^{\prime}\right)_{\mathcal{G}_{\overline{}\underline{Z}}}$
(refer to Fig. 1).

$={{P\left(Y\middle|X^{\prime},Z\right)}}P\left(X^{\prime}\right)$ (20)

Substituting 15 and 20 back into 13, we get

$\displaystyle
P_{X}\left(Y\right)=\sum_{Z}{P\left(Z\middle|X\right)\sum_{X^{\prime}}{P\left(Y\middle|X^{\prime},Z\right)P\left(X^{\prime}\right)}}$
(21)

∎

##  Appendix D Proof of Theorem 1

###### Proof.

For ease of notation, let $\mu_{\mathbf{S}_{k}}$, $c_{\mathfrak{O}}$, and
$V_{\mathbf{S}_{k}}$ be a shorthands for
$\mu_{\mathbf{S}_{k}}(\mathbf{X}_{k}^{\prime},\mathbf{x}_{k}^{\prime})$,
$c(\mathbf{X}^{\prime}_{t},\mathfrak{O})$, and
$\frac{\text{Vol}(\mathbf{V})}{\text{Vol}(\mathbf{S}_{k})}$, respectively.

$\displaystyle\mathbf{S}_{k}\in\mathscr{S}_{1}$ (22) $\displaystyle\implies
r(\mathbf{S}_{k})\geq\mathbb{E}_{\mathbf{o}_{k+1}}\left[r(\mathbf{S}_{k}\cup\\{\mathbf{o}_{k+1}\\})\right]-c_{\mathfrak{O}}$
(23) $\displaystyle\iff\eta
I(\mathbf{S}_{k};\mu)-\kappa\widehat{\mu}_{\mathbf{S}_{k}}-\tau
V_{\mathbf{S}_{k}}\geq\mathbb{E}_{\mathbf{o}_{k+1}}\left[\eta
I(\mathbf{S}_{k+1};\mu)-\kappa\widehat{\mu}_{\mathbf{S}_{k+1}}-\tau
V_{\mathbf{S}_{k+1}}\right]-c_{\mathfrak{O}}$ (24) $\displaystyle\implies\eta
I(\mathbf{S}_{k};\mu)-\kappa\widehat{\mu}_{\mathbf{S}_{k}}\geq\mathbb{E}_{\mathbf{o}_{k+1}}\left[\eta
I(\mathbf{S}_{k+1};\mu)-\kappa\widehat{\mu}_{\mathbf{S}_{k+1}}\right]-c_{\mathfrak{O}}$
(25)
$\displaystyle\implies\kappa\left(\mathbb{E}_{\mathbf{o}_{k+1}}\left[\widehat{\mu}_{\mathbf{S}_{k+1}}\right]-\widehat{\mu}_{\mathbf{S}_{k}}\right)\geq\eta\left(\mathbb{E}_{\mathbf{o}_{k+1}}\left[I(\mathbf{S}_{k+1};\mu)\right]-I(\mathbf{S}_{k};\mu)\right)-c_{\mathfrak{O}}$
(26)
$\displaystyle\implies\kappa\left(\mathbb{E}_{\mathbf{o}_{k+2}}\left[\widehat{\mu}_{\mathbf{S}_{k+1}}\right]-\widehat{\mu}_{\mathbf{S}_{k}}\right)\geq\eta\left(\mathbb{E}_{\mathbf{o}_{k+1}}\left[I(\mathbf{S}_{k+1};\mu)\right]-I(\mathbf{S}_{k};\mu)\right)-c_{\mathfrak{O}}$
(27)
$\displaystyle\implies\kappa\left(\mathbb{E}_{\mathbf{o}_{k+2}}\left[\widehat{\mu}_{\mathbf{S}_{k+2}}\right]-\widehat{\mu}_{\mathbf{S}_{k+1}}\right)\geq\eta\left(\mathbb{E}_{\mathbf{o}_{k+1}}\left[I(\mathbf{S}_{k+1};\mu)\right]-I(\mathbf{S}_{k};\mu)\right)-c_{\mathfrak{O}}$
(28)
$\displaystyle\implies\kappa\left(\mathbb{E}_{\mathbf{o}_{k+2}}\left[\widehat{\mu}_{\mathbf{S}_{k+2}}\right]-\widehat{\mu}_{\mathbf{S}_{k+1}}\right)\geq\eta\left(\mathbb{E}_{\mathbf{o}_{k+2}}\left[I(\mathbf{S}_{k+1};\mu)\right]-I(\mathbf{S}_{k};\mu)\right)-c_{\mathfrak{O}}$
(29)
$\displaystyle\implies\kappa\left(\mathbb{E}_{\mathbf{o}_{k+2}}\left[\widehat{\mu}_{\mathbf{S}_{k+2}}\right]-\widehat{\mu}_{\mathbf{S}_{k+1}}\right)\geq\eta\left(\mathbb{E}_{\mathbf{o}_{k+2}}\left[I(\mathbf{S}_{k+2};\mu)\right]-I(\mathbf{S}_{k+1};\mu)\right)-c_{\mathfrak{O}}$
(30) $\displaystyle\implies\mathbf{S}_{k+1}\in\mathscr{S}_{1}$ (31)

Equation 23 follows from the Bellman equation 7 and 24 follows because
$c(\pi_{\mathrm{O}}(\mathbf{S}),\mathfrak{I})$ is non-increasing in
$|\mathbf{S}|$, which is implied by assumption a). Equation 25 holds because
$\frac{\text{Vol}(\mathbf{V})}{\text{Vol}(\mathbf{S}_{k})}\geq\frac{\text{Vol}(\mathbf{V})}{\text{Vol}(\mathbf{S}_{k+1})}$
by definition. Equation (26) follows from linearity of $\mathbb{E}$. Equation
(27) follows from stationarity of the observation distribution
$\widehat{P}_{\mathbf{S}_{t}}$. Equation 28 follows from supermodularity of
$\widehat{\mu}_{\mathbf{S}}$ (which is preserved by integration [65]), i.e.
$\widehat{\mu}_{\mathbf{S}_{k}\cup{\mathbf{o}_{k+2}}}-\widehat{\mu}_{\mathbf{S}_{k}}\leq\widehat{\mu}_{\mathbf{S}_{k+1}\cup{\mathbf{o}_{k+2}}}-\widehat{\mu}_{\mathbf{S}_{k+1}}$,
which is implied by assumption a) and $\mathbf{S}_{k}\subset\mathbf{S}_{k+1}$.
Similarly, 29 and 30 follows from stationarity of
$\widehat{P}_{\mathbf{S}_{t}}$ and submodularity of $I$, respectively. More
specifically, 30 holds because $\mathbf{S}_{k}\subset\mathbf{S}_{k+1}$ and
$I(\mathbf{S}_{k}\cup\\{\mathbf{o}_{k+2}\\};\mu)-I(\mathbf{S}_{k};\mu)\geq
I(\mathbf{S}_{k+1}\cup\\{\mathbf{o}_{k+2}\\};\mu)-I(\mathbf{S}_{k+1};\mu)$,
which is implied by assumption b). Finally, 31 follows from 7. ∎

##  Appendix E Proof of Corollary 1

###### Proof.

The corollary follows from a well-known result in optimal stopping theory (see
[13, pp. 147-149] and [10, Prop. 7.3]). The rule in 11 is known as a one-step
lookahead policy. To prove 11 we note that, by definition of
$\mathscr{S}_{1}$, 11 holds if $k=T-1$. Assume by induction that 11 holds for
some integer $n+1<T-1$ and consider a state
$\mathbf{S}_{n}\in\mathscr{S}_{1}$. Then

$\displaystyle\mathcal{T}^{*}=n\iff r(\mathbf{S}_{n})$
$\displaystyle\geq\mathbb{E}_{\mathbf{o}_{n+1}}[V^{*}(\mathbf{S}_{n+1})]-c(\mathbf{X}^{\prime}_{t},\mathfrak{O})$
(32)
$\displaystyle=\mathbb{E}_{\mathbf{o}_{n+1}}[r(\mathbf{S}_{n+1})]-c(\mathbf{X}^{\prime}_{t},\mathfrak{O})$
(33) $\displaystyle\leq r(\mathbf{S}_{n})$ (34)
$\displaystyle\implies\mathbf{S}_{n}$ $\displaystyle\in\mathscr{S}_{n}$ (35)

where 32 follows from the Bellman equation (7) and 33 follows from Theorem 1
and the fact that $\mathscr{S}_{1}$ is closed. We then have, by induction and
by 35, that
$\mathbf{S}^{\prime}\in\mathscr{S}_{1}\implies\mathbf{S}^{\prime}\in\mathbf{S}_{l}$,
for all $l\in\\{1,\ldots,T-1\\}$. Then, since
$\mathscr{S}_{l}\subseteq\mathscr{S}_{l-1}\subseteq\ldots\subseteq\mathscr{S}_{1}$
by definition, we have that
$\mathscr{S}_{1}=\mathscr{S}_{2}=\ldots=\mathscr{S}_{T-1}$, which directly
implies 11. ∎

##  Appendix F Additional evaluation results

This appendix contains additional evaluation results, complementing those in
the main body of the paper. Section F.1 contains results for the chain scm
(see Fig. 4(a)); Section F.2 contains results for the chain scm with an
unobserved confounder (see Fig. 4(b)); Section F.3 contains results for the
PSA scm (see Fig. 4(c)); and Section F.4 contains results for the synthetic
scm with causal graph in Fig. 2.

To re-emphasise, in all experiments, we only explore the pomiss for each scm –
for a complete pseudo-algorithm see Algorithm 1.

###  F.1 Chain scm

The chain scm (see Fig. 4(a)) is a synthetic scm that is benchmarked in both
[2] and [60]. Figure 5 and Fig. 8 show the estimated probabilistic models
$\widehat{\mu}$ and $\widehat{\mathbf{F}}$ when running cbo with four
different policies for balancing the intervention-observation trade-off: i)
the $\epsilon$-greedy policy used in [2]; ii) the osco approach described in
Section 4; iii) the observe baseline (which always observes); and iv) the
random baseline, which selects between intervening and observing uniformly at
random.

(a) cbo observe.

(b) cbo random.

Figure 8: Collected data and estimated models from running cbo to solve 3 for
the chain scm [2, Fig. 3] (see Fig. 4(a)); the left plot (Fig. 8(a)) shows
results when using a policy that always observes and the right plot (Fig.
8(b)) shows results when using a policy that selects randomly between
observing and intervening; the blue curves and the shaded blue areas show the
mean and standard deviation of the estimated models $\widehat{\mathbf{F}}$ and
$\widehat{\mu}$; the red and orange dots show observations and interventions;
the black lines show the scm functions $\mathbf{F}$ and the causal effects
$\mu$.

We note in the lowest plots that the optimal intervention is
$\operatorname{do}\\!\left(Z=-3.20\right)$ (with target value $Y=-2.17$) and
that this intervention is found in all cases except for the observe baseline
(Fig. 8(a)). That the observe baseline does not find the optimal intervention
is expected as the probability of observing the optimal configuration without
intervening is low. We further note that all policies that collect
observations are able to accurately estimate the interventional distributions
through the do-calculus (see e.g. Fig. 8(a) and Fig. 5(b)). The main
differences between cbo with $\epsilon$-greedy and cbo with osco (see Fig. 5)
are a) cbo with $\epsilon$-greedy collects only $3$ observations, spending
most of the evaluation budget on interventions, whereas cbo with osco uses
most of the evaluation budget to collect observations; and b) that cbo with
$\epsilon$-greedy observes all endogeneous variables whereas cbo with osco
only observes the mos $\mathbf{O}^{Z}_{\mathcal{G},Y}=\\{Z,Y\\}$. That cbo
uses most of the evaluation budget on intervening whereas cbo with osco uses
most of the budget on observations can be explained by two main reasons.
First, the definition of $\epsilon$ in [2, Eq. 6] implies that the probability
of observing in cbo with $\epsilon$-greedy is close to $0$ when the number of
previously collected observations is low. Second, the optimal stopping
formulation in 11 implies that cbo with osco will observe rather than
intervene when it is more cost-effective.

Figure 9: Convergence curves for cbo with different policies for balancing the
intervention-observation trade-off when solving 3 for the chain scm (Fig.
4(a)); the columns relate to evaluations with different observation costs
$c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})$; the top row shows the objective
value against the evaluation cost; the middle and bottom rows show the number
of interventions ($e_{t}=\mathfrak{I}$) and observations
($e_{t}=\mathfrak{O}$) at different stages of the optimisation; the curves
indicate the mean and standard deviation ($\pm\frac{\sigma}{\sqrt[]{3}}$) over
three evaluations with different random seeds.

Figure 9 shows convergence curves of cbo with osco and the baselines
introduced above for different observation costs $c(\mathbf{X},\mathfrak{O})$.
We note that the observe and random baselines do not always converge to the
optimum within the prescribed evaluation budget (see Appendix G for the list
of hyperparameters). We further observe that cbo with osco on average reaches
the optimum at a lower cost than all baselines.

We also compare the performance of osco on the chain scm with the performance
of mcbo [60]. Figure 10 shows convergence curves of mcbo with osco and the
baselines introduced in Section 6 for different observation costs
$c(\mathbf{X},\mathfrak{O})$. We note that none of the mcbo policies find the
optimum. This is consistent with the findings in [60, Fig. 6] and can be
explained by the design of mcbo, which is optimised for minimising the
cumulative regret rather than than the simple regret. We further note that the
measured benefit of adding osco to mcbo for the chain scm is lower than that
of cbo (cf. Fig. 10). More specifically, when the observation cost is low (see
e.g. the right plot in Fig. 10), mcbo with osco yields better results than
plain mcbo. When the observation costs are high however (see e.g. the left
plot in Fig. 10), mcbo with osco leads to slower convergence. One reason why
osco works better with cbo than mcbo is that it can utilise mos (Def. 4) to
limit the number of observations (see Section 6 for details). We speculate
that another reason is the different way of integrating observational data in
the probabilistic models $\widehat{\mu}$ and $\widehat{\mathbf{F}}$. In cbo,
the observational data is integrated with the interventional data by using a
causal prior on the interventional distributions whereas in mcbo the functions
$\widehat{\mathbf{F}}$ are fitted directly based on both observational and
interventional data.

Figure 10: Convergence curves for mcbo with different policies for balancing
the intervention-observation trade-off when solving 3 for the chain scm (Fig.
5); the columns relate to evaluations with different observation costs
$c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})$; the top row shows the objective
value against the evaluation cost; the middle and bottom rows show the number
of interventions ($e_{t}=\mathfrak{I}$) and observations
($e_{t}=\mathfrak{O}$) at different stages of the optimisation; the curves
indicate the mean and standard deviation ($\pm\frac{\sigma}{\sqrt[]{3}}$) over
three evaluations with different random seeds.

###  F.2 Chain scm with an unobserved confounder

Figure 11 and Fig. 12 show convergence curves of cbo and mcbo with different
policies for balancing the intervention-observation trade-off for the chain
scm with an unobserved confounder (see Fig. 4(b)). We observe that cbo with
osco performs best on average and that the results resemble those obtained for
the chain scm without the unobserved confounder (see Section F.1). Looking at
the second and third rows in the figures, we see that cbo and mcbo with osco
focuses on collecting observations in the beginning of the optimisation and
then successively increases the frequency of interventions. This contrasts
with cbo and mcbo without osco, which almost exclusively intervenes.

Figure 11: Convergence curves for cbo with different policies for balancing
the intervention-observation trade-off when solving 3 for the chain scm with
an unobserved confounder (Fig. 1(a)); the columns relate to evaluations with
different observation costs $c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})$; the
top row shows the objective value against the evaluation cost; the middle and
bottom rows show the number of interventions ($e_{t}=\mathfrak{I}$) and
observations ($e_{t}=\mathfrak{O}$) at different stages of the optimisation;
the curves indicate the mean and standard deviation
($\pm\frac{\sigma}{\sqrt[]{3}}$) over three evaluations with different random
seeds.

Figure 12: Convergence curves for mcbo with different policies for balancing
the intervention-observation trade-off when solving 3 for the chain scm with
an unobserved confounder (Fig. 1(a)); the columns relate to evaluations with
different observation costs $c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})$; the
top row shows the objective value against the evaluation cost; the middle and
bottom rows show the number of interventions ($e_{t}=\mathfrak{I}$) and
observations ($e_{t}=\mathfrak{O}$) at different stages of the optimisation;
the curves indicate the mean and standard deviation
($\pm\frac{\sigma}{\sqrt[]{3}}$) over three evaluations with different random
seeds.

###  F.3 PSA scm

The PSA scm (see Fig. 4(c)) is based on a real healthcare setting [20] where
interventions correspond to dosage prescriptions of statins and/or aspirin to
control Prostate-Specific Antingen (PSA) levels, which should be minimised.
This scm is benchmarked in both [2] and [60].

Figure 13: Convergence curves for cbo with different policies for balancing
the intervention-observation trade-off when solving 3 for the PSA scm (Fig.
4(c)); the columns relate to evaluations with different observation costs
$c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})$; the top row shows the objective
value against the evaluation cost; the middle and bottom rows show the number
of interventions ($e_{t}=\mathfrak{I}$) and observations
($e_{t}=\mathfrak{O}$) at different stages of the optimisation; the curves
indicate the mean and standard deviation ($\pm\frac{\sigma}{\sqrt[]{3}}$) over
three evaluations with different random seeds.

Figure 13 and Fig. 14 show convergence curves of cbo and mcbo with osco and
the baselines introduced in Section 6 for different observation costs
$c(\mathbf{X},\mathfrak{O})$. We note that the only policies that consistently
find the optimum are cbo, cbo with osco, mcbo, and mcbo with osco. We also
note that osco performs, on average, better than cbo and mcbo. The differences
are however relatively small. We believe that the reason why the differences
are relatively small is that both cbo and mcbo finds the optimum in the chain
scm after only a couple of interventions, diminishing the need to utilise
observational data. This is because the optimal intervention in the PSA scm is
at the endpoints of the domains, i.e.
$(\mathbf{X}^{*},\mathbf{x}^{*})=(\\{\text{aspirin},\text{statin}\\},(0,1))$,
which is easy to find.

Figure 14: Convergence curves for mcbo with different policies for balancing
the intervention-observation trade-off when solving 3 for the PSA scm (Fig.
4(c)); the columns relate to evaluations with different observation costs
$c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})$; the top row shows the objective
value against the evaluation cost; the middle and bottom rows show the number
of interventions ($e_{t}=\mathfrak{I}$) and observations
($e_{t}=\mathfrak{O}$) at different stages of the optimisation; the curves
indicate the mean and standard deviation ($\pm\frac{\sigma}{\sqrt[]{3}}$) over
three evaluations with different random seeds.

###  F.4 Synthetic scm

Figure 15 shows convergence curves of cbo with different policies for
balancing the intervention-observation trade-off for the synthetic scm with
the causal graph in Fig. 2(a). We observe that both the policy that always
observes and cbo with osco performs best on average. This result suggests to
us that the most cost-effective way to find the optimal intervention for this
scm is to collect observations and estimate the causal effects via the do-
calculus.

Figure 15: Convergence curves for cbo with different policies for balancing
the intervention-observation trade-off when solving 3 for the synthetic scm in
Fig. 2(a); the columns relate to evaluations with different observation costs
$c(\mathbf{X}^{{}^{\prime}},\mathfrak{O})$; the top row shows the objective
value against the evaluation cost; the middle and bottom rows show the number
of interventions ($e_{t}=\mathfrak{I}$) and observations
($e_{t}=\mathfrak{O}$) at different stages of the optimisation; the curves
indicate the mean and standard deviation ($\pm\frac{\sigma}{\sqrt[]{3}}$) over
three evaluations with different random seeds.

##  Appendix G Hyperparameters

Herein we provide the hyperparameters used for all the experiments. See Fig.
16 for the relevant dags and their corresponding hyperparameter tables.

$X$$Z$$Y$

(a) Table 4.

$X$$Z$$Y$

(b) Table 4 and Section G.2.

$S$$W$$Y$$X$$Z$$B$

(c) Table 5.

AgeBMIAsp.Stat.Can.PSA

(d) Table 6.

Figure 16: dags used for the experimental section of this paper. Each dag is
associated with a table of experimental hyperparameters, found in the caption
of each figure. The causal mab experiment uses the dag in sub-figure (c) with
a different scm.

###  G.1 Hyperparameters for the chain scm

Table 4: Hyperparameters for the chain scm in Fig. 4(a). Parameter | Description | Value
---|---|---
$\mathbf{U}$ | set of exogenous variables | $\\{\epsilon_{X},\epsilon_{Z},\epsilon_{Y}\\}$
$\mathbf{V}$ | set of endogenous variables | $\\{X,Y,Z\\}$
$\mathbf{X}$ | set of manipulative variables | $\\{X,Z\\}$
$\mathbf{Y}$ | set of target variables | $\\{Y\\}$
$\mathbf{N}$ | set of non-manipulative variables | $\\{Y\\}$
$\mathbf{F}$ | set of functions in the scm | $\\{f_{X},f_{Z},f_{Y}\\}$
$\text{dom}(X)$ | domain of the random variable $X$ | $[-5,5]\subset\mathbb{R}$
$\text{dom}(Z)$ | domain of the random variable $Z$ | $[-5,20]\subset\mathbb{R}$
$\text{dom}(Y)$ | domain of the random variable $Y$ | $[-5,5]\subset\mathbb{R}$
$f_{X}$ | function in the scm | $f_{X}\colon X=\epsilon_{X}$
$f_{Z}$ | function in the scm | $f_{Z}\colon Z=e^{-X}+\epsilon_{Z}$
$f_{Y}$ | function in the scm | $f_{Y}\colon Y=\cos(Z)-e^{-\frac{Z}{20}}+\epsilon_{y}$
$\epsilon_{X}$ | Gaussian noise term in $f_{X}$ | $\epsilon_{X}\sim\mathcal{N}(\mu=0,\sigma=1)$
$\epsilon_{Z}$ | Gaussian noise term in $f_{Z}$ | $\epsilon_{Z}\sim\mathcal{N}(\mu=0,\sigma=0.5)$
$\epsilon_{Y}$ | Gaussian noise term in $f_{Y}$ | $\epsilon_{Y}\sim\mathcal{N}(\mu=0,\sigma=0.1)$
$K$ | evaluation budget in 4 | $300$
$\mathbf{D}_{1}$ | initial dataset of observations and interventions | $\varnothing$
$\widehat{\mu}$ | probabilistic model of $\mu$, see 3 | Gaussian process (gp)
$\widehat{\mathbf{F}}$ | probabilistic model of $\mathbf{F}$ | gp
gp kernel | kernel for $\widehat{\mu}$ and $\widehat{\mathbf{F}}$ | causal rbf kernel [2]
rbf length-scale | parameter for the causal rbf kernel | $1$
gp variance | parameter for the gp in [23] | $e^{-5}$
acquisition function | acquisition function for cbo |  cei [2]
$\eta$ | weighting factor in 8 | $2$
$\kappa$ | weighting factor in 8 | $1$
$\tau$ | weighting factor in 8 | $5$
$\mathbf{M}_{\mathcal{G},Y}^{\mathbf{V}}$ | set of miss (Def. 2) | $\\{\\{Z\\},\\{X,Z\\}\\}$
$\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}}$ | set of pomiss (Def. 3) | $\\{\\{Z\\}\\}$
$\mathbf{O}^{X}_{\mathcal{G},Y}$ |  mos (Def. 4) for $P\\!\left(Y\mid\operatorname{do}\\!\left(X=x\right)\right)$ | $\\{X,Z,Y\\}$
$\mathbf{O}^{Z}_{\mathcal{G},Y}$ |  mos (Def. 4) for $P\\!\left(Y\mid\operatorname{do}\\!\left(Z=z\right)\right)$ | $\\{Z,Y\\}$
$c(\cdot,\mathfrak{O})$ | observation costs | $c(\mathbf{L},\mathfrak{O})=|\mathbf{L}|2^{-2}\quad\forall\mathbf{L}\in\mathcal{P}(\mathbf{V})$
$c(\cdot,\mathfrak{I})$ | intervention costs | $c(\mathbf{L},\mathfrak{I})=|\mathbf{L}|2^{4}\quad\quad\forall\mathbf{L}\in\mathcal{P}(\mathbf{X})$
$\gamma$ | discount factor for the stopping problem | $1$
mcbo batch size | batch size for $\pi_{\mathrm{O}}$ in mcbo | $32$
mcbo $\beta$ | exploration-exploitation parameter in mcbo | $0.5$

###  G.2 Hyperparameters for the chain scm with an unobserved confounder

The scm in Fig. 1(a) uses the same hyperparameters as Fig. 4(a) listed in
Table 4, with the differences that a) there is an unobserved confounder
$\epsilon_{XY}\sim\mathcal{N}(\mu=0,\sigma=1)$ in both $f_{Y}$ and $f_{X}$; b)
the set of pomiss is
$\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}}=\\{\varnothing,\\{Z\\}\\}$; c) the
mos for $P\\!\left(Y\mid\operatorname{do}\\!\left(Z=z\right)\right)$ is
$\mathbf{O}^{Z}_{\mathcal{G},Y}=\\{X,Z,Y\\}$; and d)
$\epsilon_{Z}\sim\mathcal{N}(\mu=-1,\sigma=0.5)$.

###  G.3 Hyperparameters for the synthetic example scm

The functions $(\mathbf{F})$ for the synthetic example scm in Fig. 2(a),
adapted from [2], are given by

$\displaystyle U_{SY}$ $\displaystyle=\epsilon_{SY}$ (unobserved confounder
between $S$ and $Y$) (36) $\displaystyle U_{ZY}$ $\displaystyle=\epsilon_{ZY}$
(unobserved confounder between $Z$ and $Y$) $\displaystyle f_{S}\colon S$
$\displaystyle=U_{SY}+\epsilon_{S}$ $\displaystyle f_{B}\colon B$
$\displaystyle=S+\epsilon_{B}$ $\displaystyle f_{Z}\colon Z$
$\displaystyle=e^{-U_{ZY}}+\epsilon_{Z}$ $\displaystyle f_{W}\colon W$
$\displaystyle=\frac{e^{-B}}{10}+\epsilon_{W}$ $\displaystyle f_{X}\colon X$
$\displaystyle=\cos(Z)+\frac{B}{10}+\epsilon_{X}$ $\displaystyle f_{Y}\colon
Y$ $\displaystyle=\cos(W)+\sin(X)+U_{SY}+U_{ZY}\cdot\epsilon_{Y}$

Set of miss

$\displaystyle\\{\varnothing,$
$\displaystyle\\{Z\\},\\{X\\},\\{W\\},\\{B\\},\\{S\\},$
$\displaystyle\\{S,W\\},\\{X,W\\},\\{Z,W\\},\\{B,Z\\},\\{B,X\\},\\{X,S\\},\\{B,W\\},\\{S,Z\\},$
$\displaystyle\\{Z,S,W\\},\\{B,Z,W\\}\\}.$ (37)

Set of pomiss

$\displaystyle\\{\varnothing,$ $\displaystyle\\{X\\},\\{W\\},\\{Z\\},$
$\displaystyle\\{B,W\\},\\{X,W\\},\\{Z,W\\}\\}.$ (38)

Table 5: Hyperparameters for the synthetic scm example in Fig. 2(a). Parameter | Description | Value
---|---|---
$\mathbf{U}$ | set of exogenous variables | $\\{\epsilon_{SY},\epsilon_{ZY},\epsilon,\\{\epsilon_{i}\\}_{i=S,B,Z,W,X}\\}$
$\mathbf{V}$ | set of endogenous variables | $\\{S,B,Z,W,X,Y\\}$
$\mathbf{X}$ | set of manipulative variables | $\\{S,B,Z,W,X\\}$
$\mathbf{Y}$ | set of target variables | $\\{Y\\}$
$\mathbf{N}$ | set of non-manipulative variables | $\varnothing$
$\mathbf{F}$ | set of functions in the scm | $\\{f_{j}\\}_{j=S,B,Z,W,X,Y}$
$\text{dom}(S)$ | domain of the random variable $S$ | $[-5,4]\subset\mathbb{R}$
$\text{dom}(B)$ | domain of the random variable $B$ | $[-5,4]\subset\mathbb{R}$
$\text{dom}(W)$ | domain of the random variable $W$ | $[-5,5]\subset\mathbb{R}$
$\text{dom}(X)$ | domain of the random variable $X$ | $[-6,3]\subset\mathbb{R}$
$\text{dom}(Z)$ | domain of the random variable $Z$ | $[-5,4]\subset\mathbb{R}$
$\\{f_{j}\\}_{j\in\mathbf{V}}$ | functions in the scm | see 36
$\\{\epsilon_{j}\\}_{j\in\mathbf{V}\setminus\\{W,X\\}}$ | Gaussian noise terms | $\epsilon_{j}\sim\mathcal{N}(\mu=0,\sigma=0.1)$
$\epsilon_{W}$ | Gaussian noise term | $\epsilon_{W}\sim\mathcal{N}(\mu=0,\sigma=2)$
$\epsilon_{X}$ | Gaussian noise term | $\epsilon_{W}\sim\mathcal{N}(\mu=0,\sigma=2)$
$\epsilon_{SY}$ | Unobserved confounder term | $\epsilon_{SY}\sim\mathcal{N}(\mu=0,\sigma=0.1)$
$\epsilon_{ZY}$ | Unobserved confounder term | $\epsilon_{ZY}\sim\mathcal{N}(\mu=0,\sigma=0.1)$
$K$ | evaluation budget in 4 | $300$
$\mathbf{D}_{1}$ | initial dataset of observations and interventions | $\varnothing$
$\widehat{\mu}$ | probabilistic model of $\mu$, see 3 | Gaussian process (gp)
$\widehat{\mathbf{F}}$ | probabilistic model of $\mathbf{F}$ | gp
gp kernel | kernel for $\widehat{\mu}$ and $\widehat{\mathbf{F}}$ | causal rbf kernel [2]
rbf length-scale | parameter for the causal rbf kernel | $1$
gp variance | parameter for the gp in [23] | $e^{-5}$
acquisition function | acquisition function for cbo |  cei [2]
$\eta$ | weighting factor in 8 | $2$
$\kappa$ | weighting factor in 8 | $1$
$\tau$ | weighting factor in 8 | $5$
$\mathbf{M}_{\mathcal{G},Y}^{\mathbf{V}}$ |  miss (Def. 2) | see G.3
$\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}}$ |  pomiss (Def. 3) | see G.3
$\mathbf{O}^{\varnothing}_{\mathcal{G},Y}$ |  mos (Def. 4) | $\mathbf{V}$
$\mathbf{O}^{X}_{\mathcal{G},Y}$ |  mos (Def. 4) | $\\{X,B,Z,Y\\}$
$\mathbf{O}^{W}_{\mathcal{G},Y}$ | mos | $\\{B,W,Y\\}$
$\mathbf{O}^{Z}_{\mathcal{G},Y}$ | mos | $\mathbf{V}$
$\mathbf{O}^{\\{B,W\\}}_{\mathcal{G},Y}$ | mos | $\\{B,W,S,Y\\}$
$\mathbf{O}^{\\{X,W\\}}_{\mathcal{G},Y}$ | mos | $\\{W,X,B,Z,Y\\}$
$\mathbf{O}^{\\{Z,W\\}}_{\mathcal{G},Y}$ | mos | $\mathbf{V}$
$c(\cdot,\mathfrak{O})$ | observation costs | $c(\mathbf{L},\mathfrak{O})=|\mathbf{L}|2^{-2}\quad\forall\mathbf{L}\in\mathcal{P}(\mathbf{V})$
$c(\cdot,\mathfrak{I})$ | intervention costs | $c(\mathbf{L},\mathfrak{I})=|\mathbf{L}|2^{4}\quad\quad\forall\mathbf{L}\in\mathcal{P}(\mathbf{X})$
$\gamma$ | discount factor for the stopping problem | $1$

###  G.4 Hyperparameters for the PSA scm

The dag in Fig. 4(c) describes the causal relationships between statin (node
$D$), aspirin (node $C$) and prostate-specific antigen (PSA) level (node $F$),
mediated by a set of non-manipulative variables, adapted from [20]. We use the
same scm as Aglietti et al. [2, Appendix §5].

$\displaystyle f_{A}\ (\text{Age})\colon A$ $\displaystyle=\mathcal{U}(55,75)$
(39) $\displaystyle f_{B}\ (\text{BMI})\colon B$
$\displaystyle=\mathcal{N}(27.0-0.01\cdot A,0.7)$ $\displaystyle f_{C}\
(\text{Aspirin})\colon C$ $\displaystyle=\sigma(-8.0+0.10\cdot A+0.03\cdot B)$
$\displaystyle f_{D}\ (\text{Statin})\colon D$
$\displaystyle=\sigma(-13.0+0.10\cdot A+0.20\cdot B)$ $\displaystyle f_{E}\
(\text{Cancer})\colon E$ $\displaystyle=\sigma(2.2-0.05\cdot A+0.01\cdot
B-0.04\cdot D+0.02\cdot C)$ $\displaystyle f_{F}\ (\text{PSA})\colon F$
$\displaystyle=\mathcal{N}(6.8+0.04\cdot A-0.15\cdot B-0.60\cdot D+0.55\cdot
C+E,0.4)$

In 39, $\mathcal{U}(a,b)$ denotes the continuous uniform distribution on the
interval $[a,b]$, $\mathcal{N}(\mu,\sigma^{2})$ denotes the univariate
Gaussian distribution with mean $\mu$ and variance $\sigma^{2}$ and
$\sigma(x)$ denotes the sigmoid function $\frac{1}{1+e^{-x}}$.

Table 6: Hyperparameters for the PSA level example in Fig. 4(c) .

Parameter | Description | Value
---|---|---
$\mathbf{U}$ | set of exogenous variables | $\varnothing$
$\mathbf{V}$ | set of endogenous variables | $\\{A,B,C,D,E,F\\}$
$\mathbf{X}$ | set of manipulative variables | $\\{D,C\\}$
$\mathbf{N}$ | set of non-manipulative variables | $\\{A,B,E\\}$
$\mathbf{Y}$ | set of target variables | $\\{F\\}$
$\mathbf{F}$ | set of functions in the scm | $\\{f_{A},f_{B},f_{C},f_{D},f_{E},f_{F}\\}$
$\text{dom}(A)$ | domain of the random variable $A$$\ddagger$ | $[55,75]\subset\mathbb{R}$
$\text{dom}(B)$ | domain of the random variable $B$$\dagger$ | $[24.1,28.8]\subset\mathbb{R}$
$\text{dom}(C)$ | domain of the random variable $C$$\ddagger$ | $[0,1]\subset\mathbb{R}$
$\text{dom}(D)$ | domain of the random variable $D$$\ddagger$ | $[0,1]\subset\mathbb{R}$
$\text{dom}(E)$ | domain of the random variable $E$$\ddagger$ | $[0,1]\subset\mathbb{R}$
$\text{dom}(F)$ | domain of the random variable $F$$\dagger$ | $[4.36,7.81]\subset\mathbb{R}$
$\\{f_{i}\\}_{i\in\mathbf{V}}$ | function in the scm | see 39
$K$ | evaluation budget in 4 | $300$
$\mathbf{D}_{1}$ | initial dataset of observations and interventions | $\varnothing$
$\widehat{\mu}$ | probabilistic model for $\mu$, see 3 | gp
$\widehat{\mathbf{F}}$ | probabilistic model for $\mathbf{F}$ | gp
gp kernel | kernel for $\widehat{\mu}$ and $\widehat{\mathbf{F}}$ | causal rbf kernel [2]
rbf length-scale | parameter for the causal rbf kernel | $1$
gp variance | parameter for the gp in [23] | $e^{-5}$
acquisition function | acquisition function for cbo |  cei [2]
$\eta$ | weighting factor in 8 | $2$
$\kappa$ | weighting factor in 8 | $1$
$\tau$ | weighting factor in 8 | $5$
$\mathbf{M}_{\mathcal{G},F}^{\mathbf{V}}$ | set of miss (Def. 2) | $\\{\varnothing,\\{C\\},\\{D\\},\\{C,D\\}\\}$
$\mathbf{P}_{\mathcal{G},F}^{\mathbf{V}}$ | set of pomiss (Def. 3) | $\\{\\{C,D\\}\\}$
$\mathbf{O}^{\\{C,D\\}}_{\mathcal{G},Y}$ |  mos (Def. 4) for $P\\!\left(F\mid\operatorname{do}\\!\left(C=c\right),\operatorname{do}\\!\left(D=d\right)\right)$ | $\\{A,B,C,D,F\\}$
$c(\cdot,\mathfrak{O})$ | observation costs | $c(\mathbf{L},\mathfrak{O})=|\mathbf{L}|2^{-2}\quad\forall\mathbf{L}\in\mathcal{P}(\mathbf{V})$
$c(\cdot,\mathfrak{I})$ | intervention costs | $c(\mathbf{L},\mathfrak{I})=|\mathbf{L}|2^{4}\quad\quad\forall\mathbf{L}\in\mathcal{P}(\mathbf{X})$
$\gamma$ | discount factor for the stopping problem | $1$
mcbo batch size | batch size for $\pi_{\mathrm{O}}$ in mcbo | $32$
mcbo $\beta$ | exploration-exploitation parameter in mcbo | $0.5$

  * $\dagger$

The domains used in this experiment are the 25th and 75th percentiles of the
measured variables, found in [20, Table 1].

  * $\ddagger$

Strictly this is a discrete variable which we have made continuous for
computational reasons.

Where

$P\\!\left(F\mid\operatorname{do}\\!\left(C=c\right),\operatorname{do}\\!\left(D=d\right)\right)=\int
P\\!\left(F\mid A,B,C,D\right)P\\!\left(A,B\right)\mathrm{d}a\mathrm{d}b.$
(40)

###  G.5 Synthetic causal mab

We consider the causal mab setting in which the causal structure is provided
by the scm with dag $\mathcal{G}$ in Fig. 2(a). The two unobserved confounders
follow binary distributions governed by

$\displaystyle P(U_{SY}=1)$ $\displaystyle=0.1$ $\displaystyle P(U_{ZY}=1)$
$\displaystyle=0.05$

and exogenous variables follow binary distributions governed by

$\displaystyle P(U_{S}=1)$ $\displaystyle=0.45$ $\displaystyle P(U_{B}=1)$
$\displaystyle=0.4$ $\displaystyle P(U_{Z}=1)$ $\displaystyle=0.8$
$\displaystyle P(U_{W}=1)$ $\displaystyle=0.3$ $\displaystyle P(U_{X}=1)$
$\displaystyle=0.85$

All variables are binary with domain $\\{0,1\\}$ and with $\mathbf{F}$:

$\displaystyle f_{S}\colon S$ $\displaystyle=U_{SY}\oplus U_{S}$ (41)
$\displaystyle f_{Z}\colon Z$ $\displaystyle=1-U_{ZY}\oplus U_{Z}$
$\displaystyle f_{B}\colon B$ $\displaystyle=S\oplus U_{B}$ $\displaystyle
f_{W}\colon W$ $\displaystyle=B\oplus U_{W}$ $\displaystyle f_{X}\colon X$
$\displaystyle=1-B\oplus Z\oplus U_{X}$ $\displaystyle f_{Y}\colon Y$
$\displaystyle=W\oplus X\oplus U_{SY}\oplus U_{ZY}$

where $\oplus$ is the exclusive-or function. The set of pomiss, the set of
miss and the mos for each intervention can be found in Table 5.

##  Appendix H Pseudocode and implementation of osco

The optimal stopping problem described Section 4 can be integrated with
existing causal optimisation algorithms to balance the intervention-
observation trade-off. More specifically, given an optimisation policy
$\pi_{\mathrm{O}}$ that determines which intervention to evaluate at each
stage of the optimisation, the solution to the optimal stopping problem in 6
determines whether the intervention should be evaluated by intervention or
observation. ($\pi_{\mathrm{O}}$ may for example be implemented by the cbo
algorithm [2, Alg. 1] or the causal mab algorithm in [37, Alg.1 ]) The
pseudocode for integrating the optimal stopping problem with the existing
algorithms is listed in Algorithm 1. The main computational complexity of the
integration is the repeated solving of 11, which requires evaluating a
potentially high-dimensional integral and evaluating the optimisation policy
$\pi_{\mathrm{O}}$ several times. The integral can be evaluated efficiently
using Monte-Carlo methods [51, 19] and the evaluations of $\pi_{\mathrm{O}}$
(which may involve optimisation of an acquisition function as is e.g. the case
in cbo [2]) can be done in parallel. The average execution times per iteration
when running cbo and mcbo with and without osco are shown in Fig. 17.

Algorithm 1 Optimal stopping for Causal Optimisation (osco).

Input: Optimisation policy $\pi_{\mathrm{O}}$ and causal graph $\mathcal{G}$.
Output: Optimised intervention $(\mathbf{X}^{\star},\mathbf{x}^{\star})$.

1:procedure

2: Set $\mathbf{D}_{1}\triangleq\varnothing$ and initialise models
$\widehat{\mu}_{\mathbf{D}_{1}},\widehat{\mathbf{F}}_{\mathbf{D}_{1}}$.

3: Compute set of pomiss $\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}}$.

4: for $t=1,\ldots,T$ do

5: Set
$\mathbf{X}_{t}^{{}^{\prime}},\mathbf{x}^{{}^{\prime}}_{t}\triangleq\pi_{\mathrm{O}}(\widehat{\mu}_{\mathbf{D}_{t}},\widehat{\mathbf{F}}_{\mathbf{D}_{t}},\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}})$.

6: Compute $\mathcal{T}^{*}$ using 11.

7: if $\mathcal{T}^{*}=1$ then

8: Intervene
$\operatorname{do}\\!\left(\mathbf{X}^{{}^{\prime}}_{t}=\mathbf{x}^{{}^{\prime}}_{t}\right)$
& measure $Y$.

9: Set
$\mathbf{D}_{t+1}\triangleq\mathbf{D}_{t}\cup\\{(\operatorname{do}\\!\left(\mathbf{X}^{{}^{\prime}}_{t}=\mathbf{x}^{{}^{\prime}}_{t}\right),Y)\\}$.

10: else

11: Observe $\mathbf{o}_{t}\sim P(\mathbf{O}^{\mathbf{X}}_{\mathcal{G},Y})$.

12: Set $\mathbf{D}_{t+1}\triangleq\mathbf{D}_{t}\cup\\{\mathbf{o}_{t}\\}$.

13: end if

14: Update models $\widehat{\mu}_{\mathbf{D}_{t+1}}$ and
$\widehat{\mathbf{F}}_{\mathbf{D}_{t+1}}$.

15: end for

16: return
$\displaystyle(\mathbf{X}^{\star},\mathbf{x}^{\star})\in\operatorname*{arg\,min}_{\begin{subarray}{c}\mathbf{X}^{\prime}\in\mathbf{P}_{\mathcal{G},Y}^{\mathbf{V}};\\\
\mathbf{x}^{\prime}\in\text{dom}(\mathbf{X}^{\prime})\end{subarray}}\widehat{\mu}(\mathbf{X}^{\prime},\mathbf{x}^{\prime})$

17:end procedure

(a) Causal bo algorithms.

(b) Causal mab algorithms.

Figure 17: Execution times per iteration when running cbo [2], mcbo [60] and
c-ucb [37] with and without osco for the example scms defined in Section 6;
the height of each bar indicates the mean execution time from $100$
measurements and the error bars indicate the standard deviations.

##  Appendix I Background on Markovian optimal stopping problems

This appendix provides a self-contained background on mdps and Markovian
optimal stopping problems. It provides sufficient prerequisite knowledge for a
reader that is not familiar with optimal stopping to follow Section 4 in the
main body of the paper.

###  I.1 Markov decision processes

A Markov Decision Process (mdp) models the control of a discrete-time
dynamical system that evolves in time-steps from $t=1$ to $t=T$ and is defined
by the seven-tuple [11, 49]:

$\displaystyle\mathcal{M}=\langle\mathbf{S},\mathbf{A},P_{\mathcal{M}},r,\gamma,\rho_{1},T\rangle$
(42)

$\mathbf{S}\subseteq\mathbb{R}^{n}$ denotes the set of states,
$\mathbf{A}\subseteq\mathbb{R}^{m}$ denotes the set of actions,
$\gamma\in\left[0,1\right]$ is a discount factor,
$\rho_{1}:\mathbf{S}\rightarrow[0,1]$ is the initial state distribution and
$T$ is the time horizon.
$P_{\mathcal{M}}\left(\mathbf{S}_{t+1}=\mathbf{s}_{t+1}\mid\mathbf{S}_{t}=\mathbf{s}_{t},\mathbf{A}_{t}=a_{t}\right)$
refers to the probability of transitioning from state $\mathbf{s}_{t}$ to
state $\mathbf{s}_{t+1}$ when taking action $\mathbf{a}_{t}$ and satisfies the
Markov property
$P_{\mathcal{M}}\left(\mathbf{S}_{t+1}=\mathbf{s}_{t+1}\mid\mathbf{S}_{t}=\mathbf{s}_{t}\right)=P_{\mathcal{M}}\left(\mathbf{S}_{t+1}=\mathbf{s}_{t+1}\mid\mathbf{S}_{1}=\mathbf{s}_{1},\ldots,\mathbf{S}_{t}=\mathbf{s}_{t}\right)$,
where $\mathbf{s}_{t}\in\mathbf{S}$ and $\mathbf{a}_{t}\in\mathbf{A}$ are
realisations of the random vectors $\mathbf{S}_{t}$ and $\mathbf{A}_{t}$.
Similarly, $r(\mathbf{s}_{t},\mathbf{a}_{t})\in\mathbb{R}$ is the reward when
taking action $\mathbf{a}_{t}$ in state $\mathbf{s}_{t}$, which we assume is
bounded, i.e. $|r(\mathbf{s}_{t},\mathbf{a}_{t})|\leq M<\infty$ for some
$M\in\mathbb{R}$. If $P_{\mathcal{M}}$ and $r(\mathbf{s}_{t},\mathbf{a}_{t})$
are independent of the time-step $t$, the mdp is said to be stationary and if
$\mathbf{S}$ and $\mathbf{A}$ are finite, the mdp is said to be finite.

A policy is a function
$\pi:\\{1,\ldots,T\\}\times\mathbf{S}\rightarrow\Delta(\mathbf{A})$. If a
policy is independent of the time-step $t$ given the current state, it is
called stationary. An optimal policy $\pi^{*}$ maximizes the expected
discounted cumulative reward over the time horizon:

$\displaystyle\pi^{*}$
$\displaystyle\in\operatorname*{argmax}_{\pi\in\mathbf{\Pi}}\mathbb{E}_{\pi}\left[\sum_{t=1}^{T}\gamma^{t-1}R_{t}\right]$
(43)

where $\mathbf{\Pi}$ is the policy space, $R_{t}\in\mathbb{R}$ is a random
variable representing the reward at time $t$ and $\mathbb{E}_{\pi}$ denotes
the expectation of the random vectors and variables
$(\mathbf{S}_{t},R_{t},\mathbf{A}_{t})_{t=1,\ldots,T}$ under policy $\pi$.

Optimal deterministic policies exist for a finite mdp with bounded rewards and
either $T<\infty$ or $\gamma\in[0,1)$ [49, Prop. 4.4.3 & Thm. 6.2.10]. If the
mdp is also stationary and the horizon is either random or infinite with
$\gamma\in[0,1)$, an optimal stationary policy exists [49, Thm. 6.2.10].

The Bellman equations relate any optimal policy $\pi^{*}$ to the two value
functions $V^{*}:\mathbf{S}\rightarrow\mathbb{R}$ and
$Q^{*}:\mathbf{S}\times\mathbf{A}\rightarrow\mathbb{R}$ [12]:

$\displaystyle V^{*}(\mathbf{s}_{t})$
$\displaystyle=\displaystyle\max_{a_{t}\in\mathbf{A}}\mathbb{E}_{\mathbf{S}_{t+1}}\big{[}R_{t+1}+\gamma
V^{*}(\mathbf{S}_{t+1})\mid\mathbf{S}_{t}=\mathbf{s}_{t},\mathbf{A}_{t}=\mathbf{a}_{t}\big{]}$
(44) $\displaystyle Q^{*}(\mathbf{s}_{t},\mathbf{a}_{t})$
$\displaystyle=\mathbb{E}_{\mathbf{S}_{t+1}}\big{[}R_{t+1}+\gamma
V^{*}(\mathbf{S}_{t+1})|\mathbf{S}_{t}=\mathbf{s}_{t},\mathbf{A}_{t}=\mathbf{a}_{t}\big{]}$
(45) $\displaystyle\pi^{*}(\mathbf{s}_{t})$
$\displaystyle\in\operatorname*{argmax}_{\mathbf{a}_{t}\in\mathbf{A}}Q^{*}(\mathbf{s}_{t},\mathbf{a}_{t})$
(46)

where $V^{*}(\mathbf{s}_{t})$ and $Q^{*}(\mathbf{s}_{t},\mathbf{a}_{t})$
denote the expected cumulative discounted reward under $\pi^{*}$ for each
state and state-action pair, respectively. Solving 44 – 45 means computing the
value functions from which an optimal policy can be obtained via 46.

###  I.2 Markovian optimal stopping problems

Optimal stopping is a classical problem domain with a well-developed theory
[66, 54, 47, 16, 13, 10, 49, 24]. Many variants of the optimal stopping
problem have been studied. For example, discrete-time and continuous-time
problems, stationary and non-stationary problems and Markovian and non-
Markovian problems. As a consequence, different solution methods for these
variants have been developed. The most commonly used methods are the
martingale approach [47, 16, 58] and the Markovian approach [54, 13, 49, 50,
10].

In this paper, we focus on a stationary optimal stopping problem with a finite
time horizon $T$, discrete-time progression, a continuous state space
$\mathbf{S}\subset\mathbb{R}^{n}$, bounded rewards and the Markov property. We
use the Markovian solution approach and model the problem as a stationary mdp
$\mathcal{M}$, where the system state evolves as a discrete-time Markov
process $(\mathbf{S}_{t})_{t=1}^{T}$. Here $\mathbf{S}_{t}\in\mathbf{S}$ and
$\mathbf{s}_{t}$ denotes the realization of $\mathbf{S}_{t}$. At each time-
step $t$ of this process, two actions are available: “stop” ($\mathrm{S}$) and
“continue” ($\mathrm{C}$) i.e. $(A_{t}\in\\{\mathrm{S,C}\\})_{t=1,\ldots,T}$.
The stop action yields a reward $r(\mathbf{s}_{t},\mathrm{S})$ and terminates
the process. In contrast, the continue action causes the process to transition
to the next state according to the transition probabilities $P_{\mathcal{M}}$
and yields the reward $r(\mathbf{s}_{t},\mathrm{C})$.

A stopping time is a positive random variable $1\leq\mathcal{T}\leq T$ that is
dependent on $s_{1},\ldots,s_{\mathcal{T}}$ and independent of
$s_{\mathcal{T}+1},\ldots s_{T}$ [47]:

$\displaystyle\mathcal{T}$ $\displaystyle=\inf\\{t:t\geq 1,\text{
}a_{t}=\mathrm{S}\\},$ (47)

The objective is to find a deterministic and stationary stopping policy
$\pi^{*}:\mathbf{S}\rightarrow\\{\mathrm{S},\mathrm{C}\\}$ that maximizes the
expected discounted cumulative reward of the induced stopping time
$\mathcal{T}$:

$\displaystyle\pi^{*}\in\operatorname*{argmax}_{\pi\in\Pi}\mathbb{E}_{\pi}\left\\{\sum_{t=1}^{\mathcal{T}-1}\gamma^{t-1}r(\mathbf{S}_{t},\mathrm{C})+r(\mathbf{S}_{\mathcal{T}},\mathrm{S})\right\\}$
(48)

Due to the Markov property, any policy that satisfies 48 also satisfies the
following Bellman equation:

$\displaystyle\pi^{*}(\mathbf{s})\in\operatorname*{argmax}_{\\{\mathrm{S},\mathrm{C}\\}}\left\\{\underbrace{r(\mathbf{s},\mathrm{S})}_{\text{stop
}(\mathrm{S})},\text{
}\underbrace{\mathbb{E}_{S^{{}^{\prime}}}\left[r(\mathbf{s},\mathrm{C})+\gamma
V^{*}(\mathbf{S}^{\prime})\right]}_{\text{continue }(C)}\right\\}$ (49)

where $V^{*}$ is defined in 44.