# Budgeted and Non-budgeted Causal Bandits

Vineet Nair
Technion Israel Institute of Technology
<EMAIL_ADDRESS>Vishakha Patil111These authors have made equal
contribution and their names are alphabetically ordered.
Indian Institute of Science
<EMAIL_ADDRESS>Gaurav Sinha††footnotemark:
Adobe Research
<EMAIL_ADDRESS>
###### Abstract

Learning good interventions in a causal graph can be modelled as a stochastic
multi-armed bandit problem with side-information. First, we study this problem
when interventions are more expensive than observations and a budget is
specified. If there are no backdoor paths from an _intervenable_ node to the
reward node then we propose an algorithm to minimize simple regret that
optimally trades-off observations and interventions based on the cost of
intervention. We also propose an algorithm that accounts for the cost of
interventions, utilizes causal side-information, and minimizes the expected
cumulative regret without exceeding the budget. Our cumulative-regret
minimization algorithm performs better than standard algorithms that do not
take side-information into account. Finally, we study the problem of learning
best interventions without budget constraint in general graphs and give an
algorithm that achieves constant expected cumulative regret in terms of the
instance parameters when the parent distribution of the reward variable for
each intervention is known. Our results are experimentally validated and
compared to the best-known bounds in the current literature.

##  1 Introduction

Causal Bayesian Networks (CBN) [Pea09] have become the popular choice to model
causal relationships in many real-world systems such as online advertising,
gene interaction networks, brain functional connectivity, etc. The underlying
directed acyclic graph (DAG) of a CBN is called its _causal graph_. The nodes
of this graph are labeled by random variables222The joint distribution of
these random variables factorizes over the graph. representing the underlying
system, and edges between these variables capture direct causal relationships.
Once the causal graph is known, any external manipulations on the system that
forcibly fixes some target variables can be modeled via an operation called
_intervention_. An intervention simulates the effect of such a manipulation of
the target variables on other system variables by disconnecting the target
variables from their parents333A process known as _causal surgery_. and
setting them to the desired value.

Two key questions in causal learning are: 1) learning the causal graph itself,
and 2) finding the intervention that optimizes some variable of interest
(often called _reward_ variable) assuming that the causal graph is known. In
this work, we focus on the second question by modeling the causal learning
problem as an extension of the Stochastic Multi-armed Bandit Problem (mab)
[Rob52]. The Mab problem is a popular model used to capture decision-making in
uncertain environments where a decision-maker is faced with $k$ choices
(called _arms_) and at each time step the decision-maker has to choose one out
of the $k$ arms (_pull an arm_). The arm that is pulled gives a reward drawn
from an underlying distribution which is unknown to the decision-maker
beforehand.

We study the Mab problem with dependencies between the arms modelled via a
causal graph. This model, called _causal bandits_ , was studied in the recent
works of [BFP15, LLR16, SSDS17, SSK+17, LB18, YHS+18, LB19, LMTY20], where the
interventions are modelled as the arms of the bandit and the influence of the
arms on the reward is assumed to conform to a known causal graph. In addition
to the possible interventions allowed, the set of arms also contains the empty
intervention called the observational arm, where the algorithm does not
perform any intervention on the causal graph. The goal of a causal bandit
algorithm is to learn the intervention that maximizes the reward.

Figure 1: Causal Graph - Product Marketing

We explain the causal bandit problem with a motivating example from the
marketing domain for which a simple causal graph is shown in Figure 1. An
e-commerce company sells a product online and makes a profit whenever a
customer purchases their product. This corresponds to the green (reward) node
labeled _Purchase_ in the causal graph. On every new customer visit, the
product webpage is rendered using some values of the blue (intervenable)
nodes, chosen from an underlying distribution. For example, a customer might
see a large image, small description, no promotions, and comparison with a
competing brand. The red nodes capture actions taken by the customer before
they make any purchase decision. For example, based on the rendered product
page, a customer might want to get more information from the reviews before
deciding to add the product to their shopping cart. Note that, while the blue
nodes are actionable and can be manipulated to increase the chances of
purchase, the red nodes are not directly manipulable and can only be passively
observed for any given values of the blue nodes. For example, the company
might take an action by always offering a promotion, seeing which customers
might decide to skip going through the reviews and directly add the product to
their shopping cart. The objective here is to learn the intervention (on blue
nodes) that maximizes the chances of the product being purchased.

However, in many situations, interventions are costly [KDV17, KSB17, LKDV18,
AKMM20]. Consider the marketing example above where observational data from
this graph can be collected via independent customer visits whereas to get an
interventional sample, one needs to render a specific page configuration that
would require additional expenditure. But recent works suggest that in many
scenarios the effect of interventions can be efficiently estimated using
observational samples [TP02, BGK+20, Pea09]. Hence, in the causal bandit
framework, for a fixed budget, there is a trade-off between the more
economical observational arm and the high-cost interventional arm. This is
because the observational arm, though less rewarding, aids in the exploration
of the possibly high rewarding interventional arms. This motivates the study
of observation/intervention trade-off in the budgeted bandit setting.

###  1.1 Our Contributions

We study the problem of finding the best intervention in a causal graph in two
settings: with and without budget constraints. Further, we study these
problems with two objectives that are common in the Mab literature: simple
regret minimization and cumulative regret minimization.

Budgeted Setting: In Sections 3 and 4 we consider a class of causal graphs
that we call _no-backdoor graphs_ (see Section 3 for the definition). A
special instance of the no-backdoor graph class is the parallel graph model
defined in [LLR16]: $\mathcal{G}$ consists of $M+1$ nodes,
$\mathcal{X}=\\{Y,X_{1},\ldots,X_{M}\\}$, and the only edges in $\mathcal{G}$
are from each $X_{i}$ to $Y$. For this, [LLR16] propose an algorithm called
the _parallel bandit_ algorithm (PB-ALG henceforth). We observe that PB-ALG in
fact works for the more general class of no-backdoor graphs.

We study the causal bandit problem for no-backdoor graphs in the budgeted
bandit setting [TTCRJ12], where a budget $B$ is specified and the ratio of the
cost of the intervention to the cost of observation is $\gamma\geq 1$. The
goal of an algorithm is to find the best intervention such that the total cost
of arm pulls does not exceed $B$. In Section 3, we first study this problem
with the goal of minimizing simple regret. Note that PB-ALG does not take into
account the cost of interventions and is only optimal in the non-budgeted
setting. We show that when $\gamma$ is higher than a threshold (unknown to the
algorithm), the simple algorithm OBS-ALG that plays the observational arm
every time achieves better simple regret in terms of $B$ than PB-ALG. Next, we
propose $\gamma$-NB-ALG (Algorithm 1) which determines this unknown threshold
online and successfully manages to trade-off interventions with observations
for a specified budget.

In Section 4, we study the cumulative regret minimization (CRM) problem in the
above setting and give the CRM-NB-ALG algorithm. CRM-NB-ALG is based on the
$\mathtt{Fractional-KUBE}$ algorithm ($\mathtt{F-KUBE}$ henceforth) given in
[TTCRJ12] for budgeted bandits with no side-information. CRM-NB-ALG achieves
constant regret if the observational arm is the optimal arm and otherwise
achieves logarithmic regret which is better than that of $\mathtt{F-KUBE}$ in
terms of instance-specific constants.

Non-Budgeted Setting: In Section 5, we study the problem of minimizing the
cumulative regret for general causal graphs in the non-budgeted setting. We
assume that the distribution of parents of the reward variable for each
intervention is known to the algorithm. This assumption though limiting in the
practical setting is also made in the recent work of [LMTY20] (which studies
the same problem) as well as in the work of [LLR16]. [LMTY20] proposed an
algorithm called C-UCB which has a worst-case regret guarantee of
$O(\sqrt{k^{n}T)}$ where $k$ is the number of distinct values that each of the
$n$ parents of the reward variable can take. For the same problem, we propose
C-UCB-2 (Algorithm 3) and show it has constant expected cumulative regret in
terms of instance parameters which is a significant improvement.

##  2 Model and Notations

A CBN is a directed acyclic graph $\mathcal{G}$ whose nodes are labelled by
random variables $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$, and a joint
probability distribution $\mathbb{P}$ over $\mathcal{X}$ that factorizes over
$\mathcal{G}$. For each $i\in[n]$, the range of $X_{i}$ is a finite subset of
$\mathbb{R}$. A node $X_{j}$ is called a parent of node $X_{i}$ if there is an
edge from $X_{j}$ to $X_{i}$ in $\mathcal{G}$, i.e., changes in $X_{j}$
directly affect $X_{i}$. The set of parents of $X_{i}$ is denoted as
$Pa(X_{i})$. An intervention of size $m$ corresponds to
$\mathbf{X}\subset\mathcal{X}$ such that $|\mathbf{X}|=m$, where the variables
in $\mathbf{X}$ are set to $\mathbf{x}=(x_{1},\ldots,x_{m})$, and this
intervention is denoted as $do(\mathbf{X}=\mathbf{x})$. For each
$X_{i}\in\mathbf{X}$, the intervention also removes all the edges from
$Pa(X_{i})$ to $X_{i}$, and the resulting graph defines a probability
distribution $\mathbb{P}(\mathbf{X}^{c}|do(\mathbf{X}=\mathbf{x}))$ over
$\mathbf{X}^{c}=\mathcal{X}\setminus\mathbf{X}$. The empty intervention, also
called _observation_ , corresponding to $\mathbf{X}=\phi$ is denoted as
$do()$. A causal bandit algorithm is given as input a causal graph
$\mathcal{G}$, the set of allowed interventions $\mathcal{A}$ (which
corresponds to the set of arms), and a designated reward variable
$Y\in\mathcal{X}$ where $Y\in\\{0,1\\}$. The distribution $\mathbb{P}$ is
unknown to the algorithm.

An algorithm for this problem is a sequential decision-making process that at
each time $t$ performs an intervention $a_{t}\in\mathcal{A}$ and observes
reward $Y_{t}\in\\{0,1\\}$. For each intervention $a\in\mathcal{A}$, where
$a=do(\mathbf{X}=\mathbf{x})$, the expected reward of $a$ is denoted
$\mu_{a}=E[Y\mid do(\mathbf{X}=\mathbf{x})]$. We study a budgeted as well as a
non-budgeted variant of this problem.

###  2.1 Budgeted Causal Bandits

In the budgeted variant of our problem, we associate a cost $\gamma>1$ with
each arm pull of a non-empty intervention
$a\in\mathcal{A}\setminus\\{do()\\}$, whereas the cost of pulling the
observation arm $do()$ is one. Hence, $\gamma$ is the ratio of the cost of a
non-empty intervention to the cost of the observational arm. The algorithm, in
addition to $\mathcal{G}$ and $\mathcal{A}$, is specified a budget
$B\in\mathbb{R}_{+}$. This model is similar to the budget limited bandit model
considered in [TCdC+10, TTCRJ12] where each arm has an associated cost per
pull. Different cost models such as the linear cost model [LKDV18] and
identity cost model [AKMM20] have been studied in the causal discovery
literature. The identity cost model is equivalent to considering a uniform
cost $\gamma$ across all interventions. In this work, we are interested in the
trade-off between observations and interventions which is more perceptible in
the identity cost model. Moreover, the algorithm presented for the budgeted
setting in this paper can be extended with a bit of effort to different cost
models. We study this problem from the perspective of two objectives:
minimization of simple regret and cumulative regret, both being well-studied
in the bandit community.

Simple regret: Let $\mathtt{ALG}$ be an algorithm for the above problem that
outputs arm $a_{B}$ when the budget given is $B$. Then the simple regret of
$\mathtt{ALG}$ with budget $B$, denoted $r(B)$, is

$r_{\mathtt{ALG}}(B)=\text{max}_{a\in\mathcal{A}}\mu_{a}-\mu_{a_{B}}$ (1)

An algorithm whose objective is to minimize the simple regret is a pure-
exploration algorithm and its goal is to identify the best arm without having
to restrict the number of times a sub-optimal arm may be played using the
budget $B$. In many applications, we may require that a sub-optimal arm should
not be pulled too many times right from the start. This motivates the
definition of cumulative regret.

Cumulative regret: Let $G_{\mathtt{ALG}}(B)$ be the expected reward
accumulated by algorithm $\mathtt{ALG}$ with budget $B$, and let
$G_{B}=\max_{\mathtt{ALG}}G_{\mathtt{ALG}}(B)$. Then, the cumulative regret of
an algorithm $\mathtt{ALG}$ with budget $B$, denoted $R_{\mathtt{ALG}}(B)$, is

$R_{\mathtt{ALG}}(B)=G_{B}-G_{\mathtt{ALG}}(B)$ (2)

An algorithm for cumulative regret minimization has to carefully trade-off
between exploration vs. exploitation. Hence, an algorithm with good simple
regret guarantees may not have good cumulative regret guarantees and vice-
versa.

###  2.2 Non-budgeted Causal Bandits

In the non-budgeted variant of the problem, the cost associated with every
intervention is the same, i.e., we can assume $\gamma=1$ for all
$a\in\mathcal{A}$. In Section 5, we study this problem with the objective of
minimizing the expected cumulative regret when the time horizon $T$ is unknown
but finite. The regret notion is defined as in Equation 2 with $B=T$. Observe
that $G_{T}=T\cdot\max_{a\in\mathcal{A}}\mu_{a}$. The cumulative regret of an
algorithm $\mathtt{ALG}$ after $T$ rounds, denoted $R_{\mathtt{ALG}}(T)$, is
then defined as

$R_{\mathtt{ALG}}(T)=T\cdot\max_{a\in\mathcal{A}}\mu_{a}-\sum_{t\in[T]}\mu_{a_{t}}~{}.$
(3)

The goal of any algorithm for such a setting is to minimize the expected
cumulative regret $E[R_{\mathtt{ALG}}(T)]$ where the expectation is taken over
the randomness in the rewards as well as in the algorithm.

##  3 Budgeted mab: No-backdoor Graphs

In this section and Section 4, we assume that the interventions are of size
$1$. Formally, let $\\{X_{1},\ldots,$ $X_{M}\\}$ $\subseteq\mathcal{X}$ be the
set of intervenable nodes such that $X_{i}\in\\{0,1\\}$ for all $i\in[M]$. An
intervention in this setting is defined as explicitly setting the value of a
single node $X_{i}$ as either $0$ or $1$. When not intervened upon,
$X_{i}\sim\text{Bernoulli}(p_{i})$. Hence, we have $2M+1$ interventions in
total: $2M$ interventions correspond to setting each of the $M$ variables
$X_{i}$ to either $0$ or $1$, denoted $do(X_{i}=0)$ and $do(X_{i}=1)$
respectively, and the last intervention corresponds to the empty intervention,
$do()$. Moreover, we assume that there are no backdoor paths from $X_{i}$ to
the reward variable. This implies $E[Y\mid do(X_{i}=x)]=E[Y\mid
X_{i}=x]=\mu_{i,x}$ (see Section 3.3.1 [Pea00]). We call a causal graph
$\mathcal{G}$ satisfying this property as a _no-backdoor graph_ (
$\mathtt{NB}$-graph).

For ease of notation, we denote the intervention $do(X_{i}=x)$ by $a_{i,x}$
where $i\in[M]$ and $x\in\\{0,1\\}$, and the empty intervention as $a_{0}$.
The set of interventions is then $\mathcal{A}=\\{a_{i,x}\mid
i\in[M],x\in\\{0,1\\}\\}\uplus\\{a_{0}\\}$. The expected reward for the
intervention $a_{i,x}$ and $a_{0}$ are $\mu_{i,x}=E[Y\mid X_{i}=x]$ and
$\mu_{0}=E[Y]$ respectively. Throughout Sections 3 and 4, $i\in[M]$ and
$x\in\\{0,1\\}$. Also, we use $a$ to denote an intervention in $\mathcal{A}$
when we do not differentiate between $a_{i,x}$ and $a_{0}$. We study the
budgeted causal bandit problem for no-backdoor graphs. As stated in Section 2,
an algorithm for this problem is given as input the graph $\mathcal{G}$, the
set of intervenable nodes $\\{X_{1},\ldots,X_{M}\\}$, a budget $B$, and
$\gamma$ which is the cost for pulling an arm $a_{i,x}$. The algorithm does
not know $p_{i}$ for any $i$. Note that if $\gamma\geq B$ then trivially the
algorithm can only make observations.

As stated above, $X_{i}\sim\text{Bernoulli}(p_{i})$. Let
$p_{i,1}=\mathbb{P}(X_{i}=1)=p_{i}$ and $p_{i,0}=1-p_{i,1}$. We assume
$p=\min_{(i,x)}\\{p_{i,x}\\}>0$, which is reasonable in situations where the
best arm is observable, and if the best arm is not observable then
observational samples are not useful. Also let $\mathbf{p}=(p_{1}\ldots
p_{M})$. PB-ALG, the algorithm by [LLR16] minimizes the expected simple regret
for the parallel graph model in the non-budgeted setting. We observe that PB-
ALG works for any no-backdoor graph model. In particular, PB-ALG when applied
to the budget setting plays the observational arm $a_{0}$ for the first
$\frac{B}{(1+\gamma)}$ rounds and in the remaining $\frac{B}{(1+\gamma)}$
rounds plays the interventional arms that were observed fewer times during the
arm pulls of $a_{0}$ (because the probability of observing them when $a_{0}$
is pulled is low). The simple regret guarantee of PB-ALG depends on the
quantity $m(\mathbf{p})$ which captures the number of $X_{i}$’s such that
$\text{min}(p_{i},1-p_{i})\ll 1/2$, (i.e. the number of arms that would be
observed fewer number of times when the arm $a_{0}$ is pulled in the initial
rounds). Formally, for $\tau\in[2,M]$ let
$I_{\tau}=\big{\\{}i\mid\min_{x}\\{p_{i,x}\\}<\frac{1}{\tau}\big{\\}}$. Then
$m(\mathbf{p})=\min\\{\tau\mid|I_{\tau}|\leq\tau\\}$ and the simple regret of
the PB-ALG algorithm is $O\Big{(}\sqrt{\frac{\gamma
m(\mathbf{p})}{B}\log(\frac{MB}{\gamma m})}\Big{)}$.

In Section 3.1, we show that for $\gamma=\Omega(\frac{1}{p\cdot
m(\mathbf{p})})$ the simple algorithm that plays the observation arm for $B$
rounds achieves better expected simple regret than PB-ALG. Since $p_{i}$ for
all $i$ is unknown, the threshold $\frac{1}{p\cdot m(\mathbf{p})}$ is a priori
unknown to an algorithm. Hence, in Section 3.2 we propose an algorithm that
estimates this threshold online, and trades-off between interventions and
observations dependent on $\gamma$ and the threshold to minimize the expected
simple regret.

###  3.1 The observational algorithm

Here, we analyze the simple-regret of the observational algorithm (OBS-ALG)
which plays the arm $a_{0}$ for all the rounds, and at the end of $B$ rounds
outputs the arm $a\in\mathcal{A}$ with the highest empirical mean estimate.
The empirical estimate of $\mu_{i,x}$ is computed as the average of the
rewards accrued in those rounds where $X_{i}$ was sampled as $x$. Theorem 1
shows the dependence of the expected simple regret of OBS-ALG on $p$.

######  Theorem 1.

The expected simple regret of OBS-ALG with budget $B$ is
$O\left(\sqrt{\frac{1}{pB}\log(pMB)}\right)$.

The proof of Theorem 1 is in Section 8.2. Theorem 1 is proved by crucially
leveraging the fact that the arm $a_{0}$ aides in the exploration of all the
other $2M$ arms, which is the side-information available in
$\mathtt{NB}$-graphs. Observe that the guarantee of observational algorithm is
better than that of PB-ALG in [LLR16] if $\gamma=\Omega(\frac{1}{p\cdot
m(\mathbf{p})})$.

###  3.2 Observation-Intervention Trade-off

$\gamma$-NB-ALG (Algorithm 1) trades-off between observations and
interventions depending on the value of $\gamma$ to minimize the expected
simple regret. The idea behind $\gamma$-NB-ALG is that if $\gamma$ is larger
than the threshold $\frac{1}{p\cdot m(\mathbf{p})}$ then performing only
observations gives a better regret (as stated at the end of Section 3.1),
whereas if $\gamma$ is less than this threshold then the algorithm follows the
strategy of PB-ALG by playing the interventions in set $A$ (see step 11 of
$\gamma$-NB-ALG ) for an equal number of times in the remaining rounds. At
steps 13-14, the empirical estimates of only the arms in $A$ are updated.
Since $\mathbf{p}$ and $p$ are not known a priory, the algorithm has to
estimate the threshold online as done in Step 6 of $\gamma$-NB-ALG. Note that
at step 6, $\widehat{\mathbf{p}}=(\widehat{p}_{1}\ldots\widehat{p}_{M})$,
where $\widehat{p}_{i}=\widehat{p}_{i,1}$, and $m(\widehat{\mathbf{p}})$ is
defined similar to $m(\mathbf{p})$.

Algorithm 1 $\gamma$-NB-ALG

INPUT: $\mathcal{G}$, $B$, and $\gamma$.

1:Play arm $a_{0}$ for the first $B/2$ rounds.

2:For each $a\in\mathcal{A}$, compute

3:
$\widehat{\mu}_{i,x}=\frac{\sum_{t=1}^{B/2}Y_{t}\cdot\mathbb{1}\\{X_{i}=x\\}}{\sum_{t=1}^{B/2}\mathbb{1}\\{X_{i}=x\\}}$,
$\widehat{\mu}_{0}=\frac{2\sum_{t=1}^{B/2}Y_{t}}{B}$

4:For each $(i,x)$, compute

5: $\widehat{p}_{i,x}=\frac{2}{B}\sum_{t=1}^{B/2}\mathbb{1}\\{X_{i}=x\\}$, and
$\widehat{p}=\min_{i,x}\widehat{p}_{i,x}$

6:if $\widehat{p}\cdot m(\widehat{\mathbf{p}})\geq\frac{1}{\gamma}$ then

7: Play arm $a_{0}$ for the remaining $B/2$ rounds.

8: For each $a\in\mathcal{A}$, compute

9:
$\widehat{\mu}_{i,x}=\frac{\sum_{t=1}^{B}Y_{t}\cdot\mathbb{1}\\{X_{i}=x\\}}{\sum_{t=1}^{B}\mathbb{1}\\{X_{i}=x\\}}$,
$\widehat{\mu}_{0}=\frac{\sum_{t=1}^{T}Y_{t}}{B}$

10:else

11: Compute
$A=\\{a_{i,x}\mid\widehat{p}_{i,x}<\frac{1}{m(\widehat{\mathbf{p}})}\\}$.

12: Play each arm $a_{i,x}\in A$, for $\frac{B}{2\gamma|A|}$ rounds.

13: For each $a_{i,x}\in A$, set

14:
$\widehat{\mu}_{i,x}=\frac{2\gamma|A|}{B}\sum_{t=\frac{B}{2}+1}^{\frac{B}{2}+\frac{B}{2\gamma}}Y_{t}\cdot\mathbb{1}\\{a_{t}=a_{i,x}\\}$.

15:end if

16:Output $\arg\max_{a\in\mathcal{A}}\widehat{\mu}_{a}$.

In Theorem 2, we bound the expected simple regret of $\gamma$-NB-ALG which
depends upon $\gamma$ and the value of the threshold.

######  Theorem 2.

If $\gamma\geq\frac{1}{p\cdot m(\mathbf{p})}$ then the expected simple regret
of $\gamma$-NB-ALG is $O\left(\sqrt{\frac{1}{pB}\log(pMB)}\right)$, and if
$\gamma\leq\frac{1}{p\cdot m(\mathbf{p})}$ then it is
$O\left(\sqrt{\frac{\gamma\cdot m(\mathbf{p})}{B}\log\frac{MB}{\gamma\cdot
m(\mathbf{p})}}\right)$.

The proof of Theorem 2 is in Section 8.3. Observe that the expected simple
regret of $\gamma$-NB-ALG is equal to that of PB-ALG if
$\gamma\leq\frac{1}{p\cdot m(\mathbf{p})}$, and is equal to the that of OBS-
ALG if $\gamma>\frac{1}{p\cdot m(\mathbf{p})}$. For $\gamma=O(\frac{1}{p\cdot
m(\mathbf{p})})$ the optimality of the regret up to log factors follows from
Theorem 2 in [LLR16] where they show a $\Omega\left(\sqrt{\frac{\gamma
m}{B}}\right)$ lower bound on the expected simple regret.444The lower bound is
shown in non-budgeted setting, which translates to
$\Omega\left(\sqrt{\frac{\gamma m}{B}}\right)$ lower bound in our setting if
$\gamma=O(\frac{1}{p\cdot m(\mathbf{p})})$. The experiment 2 in Section 6
shows that the performance of $\gamma$-NB-ALG matches or is better than the
performance of PB-ALG for all values of $\gamma$, which validates our
theoretical claim.

##  4 Cumulative-Regret in No-backdoor Graphs with Budget

In this section, we give the algorithm CRM-NB-ALG (Algorithm 2) that minimizes
the cumulative regret for the model in Section 3. CRM-NB-ALG is based on
$\mathtt{Fractional-KUBE}$ ($\mathtt{F-KUBE}$, [TTCRJ12]), which is a budget-
limited version of Upper Confidence Bound ($\mathtt{UCB}$, [ACBF02]) but
without side-information. In our setting, since arm $a_{0}$ aides in the
exploration of all other $2M$ arms and has a unit cost, CRM-NB-ALG unlike
$\mathtt{F-KUBE}$ ensures that arm $a_{0}$ is pulled sufficiently many times.
Also importantly, in CRM-NB-ALG the estimate for an arm $a_{i,x}$ is made
using the effective number of pulls of the arm $a_{i,x}$, which is equal to
the number of pulls of the arm $a_{i,x}$ plus the number of pulls of arm
$a_{0}$ where $X_{i}$ was sampled as $x$. Formally, let $N^{i,x}_{t}$ and
$N^{0}_{t}$ denote the number of pulls of arm $a_{i,x}$ and $a_{0}$
respectively after $t$ rounds, and let $a_{t}$ denote the arm pulled at round
$t$. The effective number of arm pulls of $a_{i,x}$ after $t$ rounds is equal
to
$E^{i,x}_{t}=N^{i,x}_{t}+\sum_{s=1}^{t}\mathbb{1}\\{a_{s}=a_{0}\text{~{}and~{}}X_{i}=x\\}$.

At the end of $t$ rounds CRM-NB-ALG computes $\widehat{\mu}_{i,x}(t)$ and
$\widehat{\mu}_{0}(t)$ which are empirical estimates of $\mu_{i,x}$ and
$\mu_{0}$ respectively, as follows:

$\widehat{\mu}_{i,x}(t)=\frac{\sum_{s=1}^{t}Y_{s}\cdot\mathbb{1}\\{(a_{s}=a_{i,x})\text{\,or\,}(a_{s}=a_{0}\text{~{}and~{}}X_{i}=x)\\}}{E^{i,x}_{t}}$
$\widehat{\mu}_{0}(t)=\frac{1}{N^{0}_{t}}\sum_{s=1}^{t}Y_{s}\cdot\mathbb{1}\\{a_{s}=a_{0}\\}\big{)}$

Based on this estimates the CRM-NB-ALG computes the weighted UCB estimate
$\overline{\mu}_{i,x}(t)$ and $\overline{\mu}_{0}(t)$ for the arms $a_{i,x}$
and $a_{0}$ as follows:

$\overline{\mu}_{i,x}(t)=\frac{1}{\gamma}\bigg{(}\widehat{\mu}_{i,x}(t)+\sqrt{\frac{8\log
t}{E^{i,x}_{t}}}\bigg{)}$
$\overline{\mu}_{0}(t)=\widehat{\mu}_{0}(t)+\sqrt{\frac{8\log t}{N^{0}_{t}}}$

In each round CRM-NB-ALG first ensures arm $a_{0}$ is pulled at least
$\beta^{2}\log T$ times (steps 4-5), where $\beta$ is set as in steps 11-14
and otherwise pulls the arm with the highest weighted UCB estimate (steps
6-8). Ensuring the arm $a_{0}$ is pulled at least $\beta^{2}\log T$ times at
the end of $T$ rounds delicately balances the exploration-exploit trade-off:
the causal side-information by pulling the arm $a_{0}$ ensuring free
exploration of the other $2M$ interventions and the loss experienced in
pulling the arm $a_{0}$ (if $a_{0}$ is the sub-optimal arm). The reason for
setting $\beta$ as in steps 11-14 is explained after Theorem 3, which bounds
the expected cumulative regret of CRM-NB-ALG. Observe that CRM-NB-ALG halts
once it has exhausted its entire budget $B$. Crucially though, the decisions
of CRM-NB-ALG do not depend on the budget, i.e., it is budget oblivious. But
note that the decisions of the algorithm do take into account the cost of an
intervention, i.e., the algorithm is not cost-oblivious.

Algorithm 2 CRM-NB-ALG

INPUT: $\mathcal{G}$, Set of nodes $\\{X_{1},\ldots,X_{M}\\}$, $B$, $\gamma$

1:Pull each arm once and set $t=2M+2$

2:Update $B_{t-1}=B-2\gamma M-1$ and let $\beta=1$.

3:while $B_{t}\geq 1$ do

4: if $N^{0}_{t-1}<\beta^{2}\log t$ or $B_{t}<\gamma$ then

5: Pull $a_{t}=a_{0}$

6: else

7: Pull $a_{t}=\arg\max_{a\in\mathcal{A}}\overline{\mu}_{a}(t-1)$

8: end if

9: Update $N^{a}_{t}=N^{a}_{t-1}+\mathbb{1}\\{a_{t}=a\\}$

10: Update $E^{a}_{t}$, $\widehat{\mu}_{a}(t)$ and $\overline{\mu}_{a}(t)$ for
all $a\in\mathcal{A}$.

11: Let $\widehat{\mu}^{*}=\text{max}_{i,x}\widehat{\mu}_{i,x}(t)$.

12: if $\widehat{\mu}_{0}(t)<\frac{\widehat{\mu}^{*}}{\gamma}$ then

13: Update
$\beta=\min(\frac{2\sqrt{2}}{\widehat{\mu}^{*}/\gamma-\widehat{\mu}_{0}(t)},\sqrt{\log
t})$

14: end if

15: Update $B_{t+1}=\begin{cases}B_{t}-1&\text{if~{}}a_{t}=a_{0}\\\
B_{t}-\gamma&\text{if~{}}a_{t}\neq a_{0}\\\ \end{cases}$

16: Set $t=t+1$

17:end while

Before stating Theorem 3, we introduce a few more notations which are used in
the theorem. Let $v_{i,x}=\frac{\mu_{i,x}}{\gamma}$, and $v_{0}=\mu_{0}$, and
$a^{*}=\arg\max_{a\in\mathcal{A}}\\{v_{a}\\}$. Further, let
$\Delta_{a}=\mu_{a^{*}}-\mu_{a}$ and $d_{a}=v_{a^{*}}-v_{a}$ for each
$a\in\mathcal{A}$. Note that there could be $a\in\mathcal{A}$ such that
$\Delta_{a}<0$.

######  Theorem 3.

If $a^{*}=a_{0}$ then the expected cumulative regret of the algorithm is
$O(1)$ and otherwise the expected cumulative regret of the algorithm is of
order $\sum_{\Delta_{i,x}>0}\Delta_{i,x}\left(\text{max}\left(0,1+8\ln
B\left(\frac{1}{d_{i,x}^{2}}-\frac{p_{i,x}}{3d_{0}^{2}}\right)\right)+\frac{\pi^{2}}{3}\right)+\Delta_{0}\left(\frac{50\ln
B}{d_{0}^{2}}+1+\frac{\pi^{2}}{3}\right)$.

The optimal arm $a^{*}$ is equal to $a_{0}$ if the ratio of the expected
reward of any intervention to expected reward of $a_{0}$ is at most $\gamma$.
In particular, if $\frac{\text{max}_{i,x}\mu_{i,x}}{\mu_{0}}\leq\gamma$ then
$a^{*}=a_{0}$ and in this case the expected cumulative regret of CRM-NB-ALG is
bounded by a _constant_. The proof of Theorem 3 is given in Section 8.4. For
the value of $\beta$ set as in steps 11-14, we show that if $a^{*}\neq a_{0}$
then $\frac{8}{9d_{0}^{2}}\leq E[\beta^{2}]\leq\frac{50}{d_{0}^{2}}$ (see
Lemma 8.6 in Section 8.4). This in particular ensures that if $a^{*}\neq
a_{0}$ then the expected number of pulls of a sub-optimal arm $a_{i,x}$ is at
most $\text{max}\left(0,1+8\ln
B\left(\frac{1}{d_{i,x}^{2}}-\frac{p_{i,x}}{3d_{0}^{2}}\right)\right)+\frac{\pi^{2}}{3}$.
Hence note that, if $\frac{1}{d_{i,x}^{2}}\geq\frac{p_{i,x}}{3d_{0}^{2}}$ then
this sub-optimal arm is pulled at most a constant number of times. In Section
6, we show via simulation that CRM-NB-ALG performs much better than
$\mathtt{F-KUBE}$ even for small values of $\gamma$. Note that
$\mathtt{F-KUBE}$ does not take side information into account.

##  5 Cumulative Regret in General Graphs

In this section, we study the non-budgeted version of the causal bandit
problem for general graphs (see Section 2.2) with the goal of minimizing the
expected cumulative regret. This problem was studied in the recent work of
[LMTY20] who gave a UCB based algorithm, called C-UCB, which has a worst-case
regret bound of $\sqrt{k^{n}T}$ when each of the $n$ parent nodes of $Y$ (the
reward variable) in the graph can take one of $k$ values. For the same
problem, we propose an algorithm called C-UCB-2 , which has constant regret in
terms of instance-parameters. Additionally, C-UCB in [LMTY20] takes the time
horizon $T$ as input, but our algorithm C-UCB-2 works for any _unknown_ (but
finite) time horizon.

Let $Y_{1},\ldots,Y_{n}$ be the parents of $Y$, hence we have $|Pa(Y)|=n$.
Further, let $S\subset\mathbb{R}$ and $|S|=k$ be the set of values that a
parents node of $Y$ can take. We denote the realization of $Y_{i}=y_{i}$,
where $y_{i}\in S$ for each $i\in[n]$, as $Pa(Y)=\mathbf{y}$ where
$\mathbf{y}=(y_{1}\ldots y_{n})\in S^{n}$. We assume the following: (a) the
algorithm receives as input $\mathbb{P}(Pa(Y)=\mathbf{y}|do(a))$ for all $a$,
and (b) the distributions $\mathbb{P}(Pa(Y)=\mathbf{y}|do(a))$ for all $a$
have the same non-zero support. Assumption (a) is also made in [LMTY20, LLR16]
whereas Assumption (b) is made in other existing literature on causal bandits
(see [SSDS17]). Let
$c_{\mathbf{y}}=\text{min}_{a}(\mathbb{P}(Pa(Y)=\mathbf{y}\mid do(a))$.
Observe that the expected reward $\mu_{a}$ of any intervention
$a\in\mathcal{A}$ satisfies

$\mu_{a}=\sum_{\mathbf{y}\in S^{n}}E[Y\mid
Pa(Y)=\mathbf{y}]\cdot\mathbb{P}(Pa(Y)=\mathbf{y}\mid do(a))~{}.$

We denote $E[Y\mid Pa(Y)=\mathbf{y}]$ as $\mu_{\mathbf{y}}$. In C-UCB-2
(Algorithm 3),
$\zeta_{a}=\sum_{c_{\mathbf{y}}>0}\frac{\mathbb{P}(Pa(Y)=\mathbf{y}\mid
do(a))}{c_{\mathbf{y}}}$ for each $a$, and $N_{\mathbf{y},t}$ denotes the
number of times $Pa(Y)$ have been sampled as $\mathbf{y}$ in $t$ rounds. Let
$Pa_{t}(Y)$ denote the realization of $Pa(Y)$ at time $t$. Then,
$N_{\mathbf{y},t}=\sum_{s=1}^{t}\mathbb{1}\\{Pa_{s}(Y)=\mathbf{y}\\}$ and
$\widehat{\mu}_{\mathbf{y}}(t)$ is the empirical estimate of
$\mu_{\mathbf{y}}$ at the end of $t$ rounds defined as,

$\widehat{\mu}_{\mathbf{y}}(t)=\frac{1}{N_{\mathbf{y},t}}\sum_{s=1}^{t}Y_{s}\cdot\mathbb{1}\\{Pa_{s}(Y)=\mathbf{y}\\}.$

if $N_{\mathbf{y},t}\geq 1$ and otherwise $\widehat{\mu}_{\mathbf{y}}(t)=0$.
The algorithm also computes the empirical estimate $\widehat{\mu}_{a}(t)$ and
the UCB estimate $\overline{\mu}_{a}(t)$ for all $a$ using
$\widehat{\mu}_{\mathbf{y}}(t)$ at the end of every round as follows:

$\widehat{\mu}_{a}(t)=\sum_{\mathbf{y}\in
S^{n}}\widehat{\mu}_{\mathbf{y}}(t)\cdot\mathbb{P}(Pa(Y)=\mathbf{y}|do(a)),\text{~{}~{}and}$
$\overline{\mu}_{a}(t)=\widehat{\mu}_{a}(t)+\sqrt{\frac{\log(k^{n}t^{2}/2)}{t}}\zeta_{a}~{}.$

The quantity $\sqrt{\frac{\log(k^{n}t^{2}/2)}{t}}\zeta_{a}$ is called the
upper confidence radius around the empirical estimate $\widehat{\mu}_{a}(t)$
at the end of $t$ rounds. We remark here that the difference between our
algorithm C-UCB-2 and C-UCB by [LMTY20] is that C-UCB maintains a UCB estimate
for each parent value tuple $\mathbf{y}$, whereas C-UCB-2 maintains a UCB
estimate for each intervention $a\in\mathcal{A}$.

Algorithm 3 C-UCB-2

INPUT: $\mathcal{G}$, $\mathbb{P}(Pa(Y)=\mathbf{y}|do(a))$ for all
$a\in\mathcal{A}$.

1:Play each intervention in round robin and for $t=|A|$ update
$N_{\mathbf{y},t},\widehat{\mu}_{\mathbf{y}}(t),\widehat{\mu}_{a}(t),\overline{\mu}_{a}(t)$.

2:Set $t=|A|+1$

3:loop

4: Play $a_{t}=\arg\max_{a\in A}\overline{\mu}_{a}$.

5: Update
$N_{\mathbf{y},t},\widehat{\mu}_{\mathbf{y}}(t),\widehat{\mu}_{a}(t),\overline{\mu}_{a}(t)$.

6: $t=t+1$

7:end loop

Theorem 4 bounds the expected cumulative regret of C-UCB-2 . In Theorem 4,
$\Delta_{a}=\max_{b\in\mathcal{A}}\mu_{b}-\mu_{a}$.

######  Theorem 4.

Let $\delta=\min_{\mathbf{y}\in S^{n}}\\{c_{\mathbf{y}}>0\\}$,
$L_{1}=\min\Big{\\{}t\in\mathbb{N}\mid
t\geq\frac{2\log(k^{n}t^{2})}{\delta^{2}}\Big{\\}}$,
$L_{2,a}=\min\Big{\\{}t\in\mathbb{N}\mid
t\geq\frac{4\log(k^{n}t^{2}/2)}{\Delta_{a}^{2}}\zeta_{a}^{2}\Big{\\}}$ for all
$a\in\mathcal{A}$, and $L_{a}=\text{max}\\{L_{1},L_{2,a}\\}$. Then the
expected cumulative regret of C-UCB-2 after $T$ rounds is at most
$\sum_{a\in\mathcal{A}}\Delta_{a}\Big{(}L_{a}+\frac{2\pi^{2}}{3}\Big{)}.$

Observe that in Theorem 4, $L_{a}$ is a constant based on problem instance
parameters, and hence Theorem 4 proves that C-UCB-2 achieves instance
dependent constant regret. Theorem 4 is proved by showing that the expected
number of pulls of a sub-optimal arm $a\in\mathcal{A}$ after time $L_{a}$ is
at most $\frac{2\pi^{2}}{3}$ (proof in Section 8.5). In Section 6, we show via
simulations that the expected cumulative regret of C-UCB-2 is better than that
of C-UCB, and the experiment also validates that the regret of C-UCB-2 is a
constant.

##  6 Algorithm Simulations

Figure 2: OBS-ALG vs PB-ALG

Figure 3: $\gamma$-NB-ALG vs. PB-ALG (part a)

Experiment $1$ (OBS-ALG vs. PB-ALG ): This experiment compares the performance
of OBS-ALG with PB-ALG for a fixed budget on a parallel graph with $M=50$, i.e
the reward variable $Y$ has $50$ parents $X_{1},\ldots,X_{50}$: $X_{i}\sim
Bernoulli(p_{i})$ for $i\in[50]$. The rewards variable $Y$ depends on
$X_{i}$’s as follows (unknown to both the algorithms): if $X_{1}=1$ then
$Y\sim Bernoulli(0.5+\epsilon)$ and otherwise $Y\sim
Bernoulli(0.5-\epsilon^{\prime})$, where $\epsilon=0.3$, and
$\epsilon^{\prime}=\frac{p_{1}\epsilon}{1-p_{1}}\sim 0.006$. The chosen causal
graph structure is the same as in the experiments of [LLR16]. Throughout the
experiment $p_{i}=0.5$ for $i\in[3,50]$, and $p_{1}=p_{2}$ is the minimum
probability $p$. The value of $p_{1}$ and $p_{2}$, i.e. the minimum
probability $p$ is increased from $0.02$ to $0.3$. Figure 3 plots the simple
regret of these algorithms with respect to minimum probability. The regret is
computed by averaging it over $1000$ independent runs. The budget $B$ is fixed
to a moderate value of $100$ and the cost of intervention $\gamma$ to $1$. The
plot in Figure 3 shows an inverse relationship between simple regret of OBS-
ALG and $p$ as proved in Theorem 1, whereas the simple regret of PB-ALG does
not depend on $p$. Recall that the expected simple regret of PB-ALG depends on
$m(\mathbf{p})$ (and not on $p$) and for the $p_{i}$’s as stated before, the
quantity $m({\bf p})=2$, does not change. Note that the performance of
$\gamma$-NB-ALG is best for $\gamma=1$ and $m({\bf p})=2$. Finally, also
observe that after a threshold value of $p$, OBS-ALG starts performing much
better than PB-ALG as can be seen from the plot.

Figure 4: $\gamma$-NB-ALG vs. PB-ALG (part b)

Figure 5: $\gamma=1$

Experiment $2$ ($\gamma$-NB-ALG vs. PB-ALG): This experiment compares the
performance of $\gamma$-NB-ALG and PB-ALG on a parallel graph with $M=50$, i.e
the reward variable $Y$ has $50$ parents $X_{1},\ldots,X_{50}$: $X_{i}\sim
Bernoulli(p_{i})$ for $i\in[50]$, $p_{1}=p_{2}=0.02$, and $p_{i}=0.5$ for
$i\in[3,50]$. For this choice of $p_{i}$’s the PB-ALG algorithm asymptotically
achieves its best regret. The rewards variable $Y$ depends on $X_{i}$’s as
follows (unknown to both the algorithms): if $X_{1}=1$ then $Y\sim
Bernoulli(0.5+\epsilon)$ and otherwise $Y\sim
Bernoulli(0.5-\epsilon^{\prime})$, where $\epsilon=0.3$, and
$\epsilon^{\prime}=\frac{p_{1}\epsilon}{1-p_{1}}\sim 0.006$. Under these
settings, [LLR16] demonstrated a faster exponential decay of simple regret
compared to the non-causal algorithms. Since in this experiment we compare
$\gamma$-NB-ALG to PB-ALG (adapted to the budgeted version), we choose the
same causal graph and distribution. The part a of this experiment in Figure 3
compares the simple regret of the two algorithms when $\gamma=60$ and the
budget is increased to $3000$. The regret is computed by averaging it over
$1000$ independent runs. The part b of this experiment in Figure 5 illustrates
the effect on the simple regret of the algorithms as $\gamma$ increases from
$1$ to $75$. In Figure 5, observe that till a threshold value of $\gamma$ both
algorithms have very close simple regret and post the threshold, $\gamma$-NB-
ALG trades off between observations and interventions to yield a much better
simple regret.

Figure 6: $\gamma=1.1$

Figure 7: $\gamma=1.5$

Experiment $3$ ($\mathtt{F-KUBE}$ vs. CRM-NB-ALG): This experiment compares
the performance of $\mathtt{F-KUBE}$ and CRM-NB-ALG . The model is as in
Experiment 2, except $\epsilon=0.5$, i.e. the best arm has reward $1$. If the
reward distribution is the same as in experiment $1$ the cumulative regret of
CRM-NB-ALG even with $\gamma=1.1$ converges very quickly to a small constant.
This is attributed to the fact that the observation arm is closer to being
optimal (i.e. $d_{0}$ is smaller). Even though this validates the better
performance of our algorithm, for a better visual description we set the
expected reward of the best arm to $1$. Even with this reward distribution,
the performance of CRM-NB-ALG is much better than $\mathtt{F-KUBE}$. Figures
5, 7, and 7 illustrate the cumulative regrets of both the algorithms for
$\gamma$ equal to $1,1.1$ and $1.5$ respectively as the budget is increased.
The regret is computed by averaging over $50$ independent runs. Notice that
CRM-NB-ALG yields a much better regret in all three cases and its regret is
constant for $\gamma=1.5$.

Figure 8: General Graphs

Figure 9: C-UCB-2 vs. C-UCB

Experiment $4$ (C-UCB vs. C-UCB-2): This experiment compares the performance
of C-UCB and C-UCB-2 . The causal graph used in this experiment is as shown in
figure 9. Notice that this graph has a backdoor path from $X_{2}$ to $Y$ and
therefore algorithms such as PB-ALG , $\gamma$-NB-ALG and CRM-NB-ALG , which
are for no-backdoor graphs, cannot be used. Our conditional probabilities for
nodes ($P(\text{node}|Pa(\text{node}))$) are given in Table 1.

Conditional Variable | Probability
---|---
$X_{1}=0$ | $0.45$
$X_{1}=1$ | $0.55$
$X_{2}=0|X_{1}=0$ | $0.55$
$X_{2}=1|X_{1}=0$ | $0.45$
$X_{2}=0|X_{1}=1$ | $0.45$
$X_{2}=1|X_{1}=1$ | $0.55$
$W_{1}=0|X_{1}=0$ | $0.46$
$W_{1}=1|X_{1}=0$ | $0.54$
$W_{1}=0|X_{1}=1$ | $0.54$
$W_{1}=1|X_{1}=1$ | $0.46$
$W_{2}=0|X_{2}=0$ | $0.52$
$W_{2}=1|X_{2}=0$ | $0.48$
$W_{2}=0|X_{2}=1$ | $0.48$
$W_{2}=1|X_{2}=1$ | $0.52$
Table 1: Conditional Probability Distributions

The conditional distribution of the reward variable $Y$ was chosen as
$Y|w_{1},w_{2}=\theta_{1}X_{1}+\theta_{2}X_{2}+\epsilon$, where $\theta_{1}$
and $\theta_{2}$ are fixed to $0.25$ (similar to that in [LMTY20]) and
$\epsilon$ is distributed as $\mathcal{N}(0,0.01)$. Here $\mathcal{N}(0,0.01)$
denotes the normal distribution with mean $0$ and standard deviation $0.01$.
The conditional probabilities in the above table are chosen to be close to
each other in order to ensure that the expected rewards for all the arms are
competitive and the algorithm takes longer to distinguish between them. The
expected reward of the four arms $do(X_{i}=x),i\in[2],x\in\\{0,1\\}$ are given
in the Table 2.

Arm | Expected Reward
---|---
$do(X_{1}=0)$ | $0.2595$
$do(X_{1}=1)$ | $0.2405$
$do(X_{2}=0)$ | $0.244$
$do(X_{2}=1)$ | $0.254$
Table 2: Expected Reward of the Arms

Figure 9 shows a comparison between the cumulative regret incurred by both
algorithms for values of $T$ in the range $[5,100]$. The regret is computed by
averaging over $500$ independent runs. Notice that the regret of C-UCB is much
higher than C-UCB-2 and also grows with time. Moreover, the regret of C-UCB-2
grows a little initially and then becomes constant as proved in Theorem 4.

##  7 Discussion and Future Work

The Mab problem can be used to model several real-world scenarios where
additional information besides the reward of the pulled arms is available and
hence the study of the Mab problem with side-information has been an area of
significant interest in the research community. One of the most prominent
models with side-information is the contextual Mab problem where the algorithm
receives extra information (called _context_) before each arm pull [LPP10]. A
class of bandit problems where the side-information obtained conforms to a
feedback graph has also been studied in the literature [ACBDK15]. The special
case of parallel causal graphs studied in [LLR16] and in this work is in fact
captured by such a model, but as shown by [LLR16] their regret bounds are not
optimal in this setting.

In this work, we study the the causal bandit problem for no-backdoor graphs in
the budgeted bandit framework. In this setting, observations are cheaper
compared to interventions, which is practically well-motivated. In Sections 3
and 4 we provided two algorithms, $\gamma$-NB-ALG and CRM-NB-ALG , that
minimized the expected simple regret and expected cumulative regret
respectively. [SSDS17] also studies the best intervention identification
problem via importance sampling under budget constraint. But in contrast to
our work, they consider soft interventions on a single node $V$, and also
assume that the interventional distributions and the marginals of the parent
distribution of the node $V$ are known. This is incomparable with hard
interventions on no-backdoor graphs, where interventions can be performed on
different variables and the parent distributions of the intervened nodes are
not known. Also their setting is parameterized by $B^{\prime}$ and $T$, where
$B^{\prime}$ is the upper bound on the average cost of sampling and $T$ is the
total number of samples that the algorithm draws. This can be mapped to our
setting by setting the budget to be $B^{\prime}T$. In our budgeted setting $T$
is not given as input to the algorithm, and this is important for the trade-
off between observations and interventions.

In the non-budgeted setting, we showed that our algorithm C-UCB-2 has constant
expected cumulative regret in terms of instance-parameters. We conjecture that
the worst-case regret bound of our algorithm matches that in [LMTY20], and
resolving that remains open. The work by [SB17] studies a similar problem as
that in our work and experimentally show the effectiveness of Thompson
Sampling but do not provide any theoretical guarantees.

Finally, many of the works in the literature such as those of [LMTY20] and
[LLR16] assume that the parent distribution for each intervention is known to
the algorithm. We only make this assumption in Section 5. This assumption is
limiting in practice and showing a non-trivial regret guarantee for settings
without this assumption remains an important open direction.

##  8 Proofs of Theorems

###  8.1 Theoretical Preliminaries

We require the following two versions of the Chernoff-Hoeffeding inequality in
our proof.

######  Lemma 8.1 (Chernoff-Hoeffeding inequality).

Suppose $X_{1},\ldots,X_{T}$ are independent random variables taking values in
the interval $[0,1]$, and let $X=\sum_{t\in[T]}X_{t}$ and
$\overline{X}=\frac{\sum_{t\in[T]}X_{t}}{T}$. Then for any $\varepsilon\geq 0$
the following holds:

$a)~{}~{}\mathbb{P}\\{X-E[X]\geq\varepsilon\\}\leq
e^{\frac{-2\varepsilon^{2}}{T}},$
$b)~{}~{}\mathbb{P}\\{\overline{X}-E[\overline{X}]\geq\varepsilon\\}\leq
e^{-2\varepsilon^{2}T}~{}.$

###  8.2 Proof of Theorem 1

For $B\in\mathbb{N}$, let $\varepsilon=\sqrt{\frac{2}{pB}\log(16pMB)}$. Also,
let $L=\min_{t\in\mathbb{N}}\\{2\sqrt{\frac{1}{t}\log 16pMt}\leq p\\}$. Note
that $L$ is a _finite_ constant dependent on $p$ and $M$, and that for all
$B\geq L$

$\varepsilon\leq\sqrt{p/2}~{}.$ (4)

In this proof, $i$ indexes the set $[M]$, and $x$ indexes the set $\\{0,1\\}$.
Recall $p_{i,x}=\mathbb{P}\\{X_{i}=x\\}$ and $p_{i}=p_{i,1}$. Also note that
OBS-ALG plays the arm $a_{0}$ for $B$ rounds. For $i\in[M]$, let $X_{i}(t)$ be
the value of $X_{i}$ sampled in round $t\in[B]$. For all $(i,x)$, let

$\widehat{p}_{i,x}=\frac{\sum_{t\in[B]}\mathbb{1}\\{X_{i}(t)=x\\}}{B}~{},~{}~{}\text{and}$
$\widehat{\mu}_{i,x}=\frac{\sum_{t\in[B]}Y_{t}\cdot\mathbb{1}\\{X_{i}(t)=x\\}}{\sum_{t\in[B]}\mathbb{1}\\{X_{i}(t)=x\\}}~{},$

where $Y_{t}$ is value of $Y$ sampled in round $t$. Notice that
$\widehat{\mu}_{i,x}$ is the empirical estimate of $\mu_{i,x}$ computed by
OBS-ALG at the end of $B$ rounds. Similarly the empirical estimate of
$\mu_{0}$, denoted $\widehat{\mu}_{0}$, is computed by OBS-ALG at the end of
$B$ rounds as follows:

$\widehat{\mu}_{0}=\frac{\sum_{t\in[B]}Y_{t}}{B}~{}.$

Finally, also let $\widehat{p}_{i}=\widehat{p}_{i,1}$. The proof of the
theorem is completed using the following lemma.

######  Lemma 8.2.

At the end of $B$ rounds played by OBS-ALG the following hold:

$\displaystyle 1.~{}~{}~{}$
$\displaystyle\mathbb{P}\\{|\widehat{\mu}_{0}-\mu_{0}|\geq\varepsilon\\}\leq
2e^{-2\varepsilon^{2}B}\leq 4e^{-\varepsilon^{2}pB}~{},$ $\displaystyle
2.~{}~{}~{}$ $\displaystyle\text{For any fixed
}(i,x)~{}~{}~{}\mathbb{P}\Big{\\{}\widehat{p}_{i,x}B\leq\frac{pB}{2}\Big{\\}}\leq
2e^{-\varepsilon^{2}pB}~{},$ $\displaystyle 3.~{}~{}~{}$
$\displaystyle\text{For any fixed
}(i,x)~{}~{}~{}\mathbb{P}\\{|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\\}\leq
4e^{-\varepsilon^{2}pB}~{}.$

###### Proof.

1) Part 1 directly follows from Lemma 8.1.

2) Observe that $E[\widehat{p}_{i}]=p_{i}$, and hence from Lemma 8.1, for an
$i\in[M]$ at the end of $B$ rounds we have

$\mathbb{P}\left\\{|(\widehat{p}_{i}-p_{i})B|\geq\varepsilon
B\sqrt{\frac{p}{2}}\right\\}\leq 2e^{-\varepsilon^{2}pB}~{}.$ (5)

Since $\varepsilon\leq\sqrt{p/2}$ (from Equation 4), $\varepsilon
B\sqrt{\frac{p}{2}}\leq\frac{pB}{2}$. This implies

$\frac{pB}{2}\leq pB-\varepsilon B\sqrt{\frac{p}{2}}~{}.$ (6)

Hence from Equations 5 and 6, for a fixed $(i,x)$ the following holds:

$\mathbb{P}\Big{\\{}\widehat{p}_{i,x}B\leq\frac{pB}{2}\Big{\\}}\leq
2e^{-\varepsilon^{2}pB}~{}.$

3) Notice that $\widehat{p}_{i,x}B$ is the number of times $X_{i}$ was sampled
as $x$ in $B$ rounds. In particular, part 2 of Lemma 8.2 bounds the
probability that the number of times $X_{i}$ was sampled as $x$ is small. We
use this to prove part 3. First observe that from Lemma 8.1 we have

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\Big{|}\widehat{p}_{i,x}B>\frac{pB}{2}\Big{\\}}\leq
2e^{-\varepsilon^{2}pB}~{}.$ (7)

In particular, Equation 7 bounds the error probability of estimating
$\widehat{\mu}_{i,x}$ conditioned on the event that $X_{i}$ has been sampled
as $x$ sufficiently many times. Next by law of total probability, for any
fixed $(i,x)$,

$\displaystyle\mathbb{P}\\{|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\\}$
$\displaystyle=\mathbb{P}\Big{\\{}|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\Big{|}\widehat{p}_{i,x}B>\frac{pB}{2}\Big{\\}}\cdot\mathbb{P}\Big{\\{}\widehat{p}_{i,x}B>\frac{pB}{2}\Big{\\}}$
$\displaystyle~{}~{}~{}~{}+\mathbb{P}\Big{\\{}|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\Big{|}\widehat{p}_{i,x}B\leq\frac{pB}{2}\Big{\\}}\cdot\mathbb{P}\Big{\\{}\widehat{p}_{i,x}B\leq\frac{pB}{2}\Big{\\}}$
$\displaystyle\mathbb{P}\\{|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\\}$
$\displaystyle\leq\mathbb{P}\Big{\\{}|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\Big{|}\widehat{p}_{i,x}B>\frac{pB}{2}\Big{\\}}+\mathbb{P}\Big{\\{}\widehat{p}_{i,x}B\leq\frac{pB}{2}\Big{\\}}~{}.$

Hence, from Equation 7 and part 2 of Lemma 8.2 we have

$\mathbb{P}\\{|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\\}\leq
4e^{-\varepsilon^{2}pB}~{}.$

∎

Let $U_{0}$ be the event that $|\widehat{\mu}_{0}-\mu_{0}|\leq\varepsilon$,
and for any $i,x$ let $U_{i,x}$ be the event
$|\widehat{\mu}_{i,x}-\mu_{i,x}|\leq\varepsilon$. Also let
$U=(\cap_{i,x}U_{i,x})\cap U_{0}$, $\overline{U}$ denote the compliment of
$U$. Then applying union bound on the events in part 1 and 3 in Lemma 8.2, we
have that

$\mathbb{P}\\{\overline{U}\\}\leq(2M+1)\cdot 4e^{-\varepsilon^{2}pB}$

Hence, we have that

$\mathbb{P}\\{U\\}\geq 1-(8M+4)e^{-\varepsilon^{2}pB}\geq
1-16Me^{-\varepsilon^{2}pB}.$

Let $a^{*}=\arg\max_{a\in\mathcal{A}}(\mu_{a})$. Note that if event
$\overline{U}$ holds then the simple regret of OBS-ALG , $r_{\text{{OBS-ALG}
}}(B)\leq 1$. On the other hand, if the event $U$ holds, and $a_{B}$ is the
arm output by the algorithm, then $r_{\text{{OBS-ALG}
}}(B)=\mu_{a^{*}}-\mu_{a_{B}}\leq 2\varepsilon$. Setting
$\delta=16Me^{-\varepsilon^{2}pB}$, and substituting the value of
$\varepsilon$, we have $\delta=\frac{1}{16Mp^{2}B^{2}}$. Hence, the expected
simple regret is at most:

$\delta+\sqrt{\frac{8}{pB}\log(16pMB)}=\frac{1}{16Mp^{2}B^{2}}+\sqrt{\frac{8}{pB}\log(16pMB)}=O\Bigg{(}\sqrt{\frac{1}{pB}\log(pMB)}\Bigg{)}~{}.$
(8)

###  8.3 Proof of Theorem 2

For convenience, we denote $m(\mathbf{p})$ and $m(\widehat{\mathbf{p}})$ as
$m$ and $\widehat{m}$ respectively. Throughout the proof we assume that $B$ is
such that: a) $B\geq\max(\gamma m,pM)$ and b)
$B\geq\max(\frac{16}{p^{2}}\log\frac{2MB}{\gamma m},\frac{16}{p^{2}}\log
2pMB)$. Note that the two constraints hold for sufficiently large $B$. To
begin with observe that if $\gamma=\theta(\frac{1}{p\cdot m(\mathbf{p})})$
then $O\left(\sqrt{\frac{1}{pB}\log(pMB)}\right)=O\left(\sqrt{\frac{\gamma
m}{B}\log\frac{MB}{\gamma m}}\right)$. Hence, it is sufficient to show that if
$\gamma\leq\frac{1}{5p\cdot m(\mathbf{p})}$ then the expected simple regret of
$\gamma$-NB-ALG is $O\left(\sqrt{\frac{\gamma m}{B}\log\frac{MB}{\gamma
m}}\right)$ and if $\gamma\geq\frac{5}{p\cdot m(\mathbf{p})}$ then the
expected simple regret of $\gamma$-NB-ALG is
$O\left(\sqrt{\frac{1}{pB}\log(pMB)}\right)$. Theorem 2 is proved using Lemmas
8.3 and 8.4.

######  Lemma 8.3.

Let $\widehat{p}_{i,1}=\widehat{p}_{i}$ and $F=\mathbb{1}\\{\text{At the end
of }B/2\text{ rounds there is an }i\in[M]\text{ such that
}|\widehat{p}_{i}-p_{i}|\geq\frac{p}{4}\\}$. Then $\mathbb{P}\\{F=1\\}\leq
2Me^{-\frac{p^{2}}{16}B}$.

###### Proof.

Let $F_{i}=\mathbb{1}\\{\text{At the end of }B/2\text{ rounds
}|\widehat{p}_{i}-p_{i}|\geq\frac{p}{4}\\}$. Then from Lemma 8.1,

$\mathbb{P}\\{F_{i}=1\\}\leq 2e^{-\frac{p^{2}}{16}B}~{}.$

Taking union bound over $F_{i}=1$ for $i\in[M]$, we have
$\mathbb{P}\\{F=1\\}\leq 2Me^{-\frac{p^{2}}{16}B}$. ∎

The following lemma is similar to Lemma 8 in [LLR16].

######  Lemma 8.4.

Let $F$ be as in Lemma 8.3, and let $I=\mathbb{1}\\{\text{At the end of
}B/2\text{ rounds }~{}\frac{2m(\mathbf{p})}{5}\leq m(\widehat{\mathbf{p}})\leq
2m(\mathbf{p})\\}$. Then $F=0$ implies $I=1$, and in particular,
$\mathbb{P}\\{I=1\\}\geq 1-2Me^{-\frac{p^{2}}{16}B}.$

###### Proof.

We are interested in the quantity $\min_{x\in\\{0,1\\}}p_{i,x}$ for each
$i\in[M]$. Without loss of generality, let us assume
$\min_{x\in\\{0,1\\}}p_{i,x}=p_{i,1}=p_{i}$ for each $i\in[M]$, and also
$p_{1}\leq p_{2}\leq\ldots\leq p_{M}\leq\frac{1}{2}$. Note that $F=0$ implies
after $B/2$ rounds for all $i\in[M]$ $|\widehat{p}_{i}-p_{i}|\leq\frac{p}{4}$.
Now, from the definition of $m(\mathbf{p})$ we know that there is an $\ell\leq
m$ such that the following is true: for $i>\ell$, $p_{i}\geq\frac{1}{m}$.
Further, we can also conclude that $p\leq\frac{1}{m-1}$ (otherwise
$m(\mathbf{p})=m-1$). Hence, $\widehat{p}_{i}\geq
p_{i}-\frac{p}{4}\geq\frac{1}{m}-\frac{1}{4(m-1)}$. Hence for $i>\ell$,
$\widehat{p}_{i}\geq\frac{3m-4}{4m(m-1)}\geq\frac{1}{2m}$ (since $m\geq 2$).
Since $\ell\leq m$, we have $|\\{j\mid\widehat{p}_{j}<\frac{1}{2m}\\}|\leq
2m$. This implies $\widehat{m}\leq 2m$. To prove the other inequality, observe
that for each $i\leq m$, we have $p_{i}\leq\frac{1}{m-1}$ (otherwise,
$m(\mathbf{p})\leq m-1$). Then, $\widehat{p}_{i}\leq
p_{i}+\frac{p}{4}\leq\frac{1}{m-1}+\frac{1}{4(m-1)}\leq\frac{5}{4(m-1)}\leq\frac{5}{2m}$.
Hence for $i\leq m$, $\widehat{p}_{i}\leq\frac{5}{2m}$. This implies
$\widehat{m}\geq\frac{2m}{5}$.∎

From Lemmas 8.3 and 8.4 it follows that if $F=0$ then at the end of $B/2$
rounds the following holds:

$\frac{p}{2}\leq\widehat{p}\leq\frac{3p}{2}~{}~{}~{}\text{and}~{}~{}~{}\frac{2m}{5}\leq\widehat{m}\leq
2m$

This implies that if $F=0$ then at then end of $B/2$ rounds the following
holds:

$\frac{p\cdot m}{5}\leq\widehat{p}\cdot\widehat{m}\leq 5p\cdot m$ (9)

Case a ($\gamma<\frac{1}{5p\cdot m}$): We condition on $F=0$. Hence, from the
argument above it follows that Equation 9 holds. Hence,
$\gamma<\frac{1}{5p\cdot m}\leq\frac{1}{\widehat{p}\cdot\widehat{m}}$. This
implies at step 6 in $\gamma$-NB-ALG ,
$\widehat{p}\cdot\widehat{m}<\frac{1}{\gamma}$, and $\gamma$-NB-ALG executes
steps 11-14. That is $\gamma$-NB-ALG makes $\frac{B}{4\gamma}$ interventions
in the remaining rounds. The algorithm constructs set
$A=\\{a_{i,x}\mid\widehat{p}_{i,x}\leq\frac{1}{\widehat{m}}\\}$. Now for arms
in $A$, $\widehat{\mu}_{i,x}$ is computed as in step 14 of $\gamma$-NB-ALG,
i.e for $a_{i,x}\in A$

$\widehat{\mu}_{i,x}=\frac{2\gamma|A|}{B}\sum_{t=B/2+1}^{B/2\gamma}Y_{t}\cdot\mathbb{1}\\{a_{t}=a_{i,x}\\}~{}.$

Notice that $|A|\leq\widehat{m}$ (from the definition of
$m(\widehat{\mathbf{p}})$). Hence

$\frac{B}{2\gamma\cdot|A|}\geq\frac{B}{2\gamma\cdot\widehat{m}}\geq\frac{B}{4\gamma\cdot
m}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(from Lemma \ref{lemma: bounding m}}).$

Thus from Lemma 8.1 for each arm $a_{i,x}\in A$ and any $\varepsilon>0$

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\Big{|}F=0\Big{\\}}\leq
2e^{-\varepsilon^{2}\frac{B}{2\gamma m}}$ (10)

Also for arms not in $A$, $\widehat{\mu}_{i,x}$ is computed as in step 3 of
$\gamma$-NB-ALG, i.e. for $a_{i,x}\notin A$

$\widehat{\mu}_{i,x}=\frac{\sum_{t=1}^{B/2}Y_{t}\cdot\mathbb{1}\\{X_{i}=x\\}}{\sum_{t=1}^{B/2}\mathbb{1}\\{X_{i}=x\\}}~{}.$

Moreover, if $a_{i,x}\notin A$ then
$\widehat{p}_{i,x}\geq\frac{1}{\widehat{m}}\geq\frac{1}{2m}$. Since
$\widehat{p}_{i,x}=\frac{2}{B}\sum_{t=1}^{B/2}\mathbb{1}\\{X_{i}=x\\}$, this
implies if $a_{i,x}\notin A$ then
$\sum_{t=1}^{B/2}\mathbb{1}\\{X_{i}=x\\}\geq\frac{B}{4m}$. Hence from Lemma
8.1, for each arm $a_{i,x}\notin A$ and any $\varepsilon>0$,

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{i,x}-\mu_{i,x}|\geq\varepsilon\Big{|}F=0\Big{\\}}\leq
2e^{-\varepsilon^{2}\frac{B}{2m}}\leq 2e^{-\varepsilon^{2}\frac{B}{2\gamma
m}}$ (11)

The last inequality holds since $\gamma\geq 1$. Using Equations 10 and 11 we
have for any arm $a\in\mathcal{A}$,

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{a}-\mu_{a}|\geq\varepsilon\Big{|}F=0\Big{\\}}\leq
2e^{-\varepsilon^{2}\frac{B}{2\gamma m}}~{}.$

Hence, applying union bound we have

$\mathbb{P}\Big{\\{}\text{there is an }a\in\mathcal{A}\text{ such that
}|\widehat{\mu}_{a}-\mu_{a}|\geq\varepsilon\Big{|}F=0\Big{\\}}\leq(4M+2)e^{-\varepsilon^{2}\frac{B}{2\gamma
m}}\leq 8Me^{-\varepsilon^{2}\frac{B}{2\gamma m}}~{}.$

Substituting $\varepsilon=\sqrt{\frac{8\gamma m}{B}\log\frac{MB}{\gamma m}}$
we have

$E[r_{\text{{$\gamma$-NB-ALG}}}(B)|F=0]\leq\sqrt{\frac{8\gamma
m}{B}\log\frac{MB}{\gamma m}}+\frac{8}{M^{3}}\left(\frac{\gamma
m}{B}\right)^{4}\leq\sqrt{\frac{32\gamma m}{B}\log\frac{MB}{\gamma m}}~{}.$
(12)

To get the last inequality, we use that $\frac{8}{M^{3}}\left(\frac{\gamma
m}{B}\right)^{4}\leq\sqrt{\frac{8\gamma m}{B}\log\frac{MB}{\gamma m}}$, as
$M\geq 1$ and $B\geq\gamma m$. Finally, we use Equation 12 and Lemma 8.3 to
bound the expected simple regret of $\gamma$-NB-ALG in this case as follows:

$\displaystyle E[r_{\text{{$\gamma$-NB-ALG}}}(B)]$
$\displaystyle=E[r_{\text{{$\gamma$-NB-
ALG}}}(B)|Y=0]Pr\\{Y=0\\}+E[r(B)|Y=1]Pr\\{Y=1\\}$ $\displaystyle\leq
E[r_{\text{{$\gamma$-NB-ALG}}}(B)|Y=0]+Pr\\{Y=1\\}\ $
$\displaystyle\leq\sqrt{\frac{32\gamma m}{B}\log\frac{MB}{\gamma
m}}+2Me^{-\frac{p^{2}}{16}B}$ $\displaystyle=O\Bigg{(}\sqrt{\frac{\gamma
m}{B}\log\frac{MB}{\gamma m}}\Bigg{)}~{}.$

In last but one line of the above equation, we use that $B$ satisfies
$B\geq\frac{4}{p^{2}}\log\frac{2MB}{\gamma m}$ and $B\geq\gamma m$ implying
$2Me^{-\frac{p^{2}}{16}B}$ is at most $\sqrt{\frac{32\gamma
m}{B}\log\frac{MB}{\gamma m}}$.

Case b ($\gamma\geq\frac{5}{p\cdot m(\mathbf{p})}$): Again we condition on
$F=0$, and hence Equation 9 holds. Hence, $\gamma\geq\frac{5}{p\cdot
m(\mathbf{p})}\geq\frac{1}{\widehat{p}\cdot m(\widehat{\mathbf{p}})}$. This
implies at step 6 in $\gamma$-NB-ALG , $\widehat{p}\cdot
m(\widehat{\mathbf{p}})\geq\frac{1}{\gamma}$, and $\gamma$-NB-ALG executes
steps 7-9. That is it plays the arm $a_{0}$ for $B$ rounds. Thus, from the
analysis of Theorem 1 we have that (see Equation 8)

$E[r_{\text{{$\gamma$-NB-
ALG}}}(B)|Y=0]\leq\sqrt{\frac{1}{pB}}+\sqrt{\frac{8}{pB}\log(16pMB)}~{}.$ (13)

We use Equation 13 and Lemma 8.3 to bound the expected simple regret of
$\gamma$-NB-ALG in this case as follows:

$\displaystyle E[r_{\text{{$\gamma$-NB-ALG}}}(B)]$
$\displaystyle=E[r_{\text{{$\gamma$-NB-
ALG}}}(B)|Y=0]Pr\\{Y=0\\}+E[r_{\text{{$\gamma$-NB-ALG}}}(B)|Y=1]Pr\\{Y=1\\}$
$\displaystyle\leq E[r_{\text{{$\gamma$-NB-ALG}}}(B)|Y=0]+Pr\\{Y=1\\}\ $
$\displaystyle\leq\sqrt{\frac{1}{pB}}+\sqrt{\frac{8}{pB}\log(16pMB)}+2Me^{-\frac{p^{2}}{16}B}$
$\displaystyle=O\Bigg{(}\sqrt{\frac{1}{pB}\log(16pMB)}\Bigg{)}$

Again in the last but one line of the above equation, we use that $\frac{4\log
MB}{p^{2}B}\leq 1$ and hence $2Me^{-\frac{p^{2}}{16}B}$ is at most
$\sqrt{\frac{8}{pB}\log(16pMB)}$.

###  8.4 Proof of Theorem 3

The proof of Theorem 3 requires the the following lemmas.

######  Lemma 8.5.

For any $T\in\mathbb{N}$, at the end of $T$ rounds the following hold:

  1. 1.

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{0}(T)-\mu_{0}|\geq\frac{d_{0}}{4}\Big{\\}}\leq\frac{2}{T^{\frac{d_{0}^{2}}{8}}}$
,

  2. 2.

Let
$\widehat{p}_{i,x}=\frac{\sum_{t=1}^{T}\mathbb{1}\\{a_{t}=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}}{N^{0}_{T}}$.
Then $\mathbb{P}\\{\widehat{p}_{i,x}\geq\frac{p}{2}\\}\geq
1-\frac{1}{T^{\frac{p^{2}}{2}}}$ ,

  3. 3.

$\mathbb{P}\Big{\\{}\Big{|}\frac{\widehat{\mu}_{i,x}(T)}{\gamma}-\frac{\mu_{i,x}}{\gamma}\Big{|}\geq\frac{d_{0}}{4}\Big{\\}}\leq\frac{2}{T^{\frac{d_{0}^{2}p\gamma^{2}}{16}}}+\frac{1}{T^{\frac{p^{2}}{2}}}~{}.$

###### Proof.

1\. Since $\beta\geq 1$, at the end of $T$ rounds arm $a_{0}$ is pulled by
CRM-NB-ALG at least $(\ln T)^{2}$ times. Hence, $N^{0}_{T}\geq(\ln T)$, and
from Lemma 8.1 we have

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{0}(T)-\mu_{0}|\geq\frac{d_{0}}{4}\Big{\\}}\leq
2e^{-\frac{d_{0}^{2}}{8}\ln T}=\frac{2}{T^{\frac{d_{0}^{2}}{8}}}$ (14)

2\. Observe that for any $(i,x)$, $p_{i,x}\geq p$, and
$\mathbb{E}[\widehat{p}_{i,x}]=p_{i,x}$. Using Lemma 8.1 and that
$N^{0}_{T}\geq\ln T$, for a fixed $(i,x)$ we have

$\mathbb{P}\\{\widehat{p}_{i,x}\geq p_{i,x}-\frac{p}{2}\geq\frac{p}{2}\\}\geq
1-e^{-\frac{p^{2}}{2}\ln T}=1-\frac{1}{T^{\frac{p^{2}}{2}}}~{}~{}.$

3\. Recall that the effective number of arm pulls of arm $a_{i,x}$ at the end
of $T$ rounds is

$E^{i,x}_{T}=N^{i,x}_{T}+\sum_{t=1}^{T}\mathbb{1}\\{a_{t}=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}~{}~{}.$

Hence, $E^{i,x}_{T}=N^{i,x}_{T}+\widehat{p}_{i,x}N^{0}_{T}$, where
$\widehat{p}_{i,x}$ is as defined in part two of this lemma. Hence for any
$i,x$ at the end of $T$ rounds if $\widehat{p}_{i,x}\geq\frac{p}{2}$ then
$E^{i,x}_{T}\geq\frac{pN^{0}_{T}}{2}$. Further, as $N^{0}_{T}\geq\ln T$, it
follows that at the end of $T$ rounds if $\widehat{p}_{i,x}\geq\frac{p}{2}$
then $E^{i,x}_{T}\geq\frac{p\ln T}{2}$. Hence, from the definition of
$\widehat{\mu}_{i,x}(T)$ and Lemma 8.1, at the end of $T$ rounds we have for
any fixed $i,x$:

$\mathbb{P}\Big{\\{}\Big{|}\frac{\widehat{\mu}_{i,x}(T)}{\gamma}-\frac{\mu_{i,x}}{\gamma}\Big{|}\geq\frac{d_{0}}{4}\Big{|}\widehat{p}_{i,x}\geq\frac{p}{2}\Big{\\}}\leq
2e^{-\frac{\gamma^{2}d_{0}^{2}}{16}p\ln
T}=\frac{2}{T^{\frac{p\gamma^{2}d_{0}^{2}}{16}}}~{}.$ (15)

Finally by law of total probability,

$\displaystyle\mathbb{P}\Big{\\{}\Big{|}\frac{\widehat{\mu}_{i,x}(T)}{\gamma}-\frac{\mu_{i,x}}{\gamma}\Big{|}\geq\frac{d_{0}}{4}\Big{\\}}$
$\displaystyle=\mathbb{P}\Big{\\{}\Big{|}\frac{\widehat{\mu}_{i,x}(T)}{\gamma}-\frac{\mu_{i,x}}{\gamma}\Big{|}\geq\frac{d_{0}}{4}\Big{|}\widehat{p}_{i,x}\geq\frac{p}{2}\Big{\\}}\mathbb{P}\\{\widehat{p}_{i,x}\geq\frac{p}{2}\\}$
$\displaystyle~{}~{}~{}~{}+\mathbb{P}\Big{\\{}\Big{|}\frac{\widehat{\mu}_{i,x}(T)}{\gamma}-\frac{\mu_{i,x}}{\gamma}\Big{|}\geq\frac{d_{0}}{4}\Big{|}\widehat{p}_{i,x}\leq\frac{p}{2}\Big{\\}}\mathbb{P}\\{\widehat{p}_{i,x}\leq\frac{p}{2}\\}$
$\displaystyle\leq\mathbb{P}\Big{\\{}\Big{|}\frac{\widehat{\mu}_{i,x}(T)}{\gamma}-\frac{\mu_{i,x}}{\gamma}\Big{|}\geq\frac{d_{0}}{4}\Big{|}\widehat{p}_{i,x}\geq\frac{p}{2}\Big{\\}}+\mathbb{P}\\{\widehat{p}_{i,x}\leq\frac{p}{2}\\}$
$\displaystyle\leq\frac{2}{T^{\frac{p\gamma^{2}d_{0}^{2}}{16}}}+\frac{1}{T^{\frac{p^{2}}{2}}}~{}.$

The last line in the above inequality follows from Equation 15 and part 2 of
this lemma. ∎

######  Lemma 8.6.

Let $L=\arg\min_{t\in\mathbb{N}}\\{\frac{t^{\frac{p^{2}d_{0}^{2}}{16}}}{\ln
t}\geq 15M\\}$, and suppose CRM-NB-ALG pulls arms for $T$ rounds, where
$T\geq\max(L,e^{\frac{50}{d_{0}^{2}}})$, and let $a^{*}\neq a_{0}$. Then at
the end of $T$ rounds $\frac{8}{9d_{0}^{2}}\leq
E[\beta^{2}]\leq\frac{50}{d_{0}^{2}}$. (Note that
$\max(L,e^{\frac{50}{d_{0}^{2}}})$ is a finite constant dependent on instance
constants $p,d_{0}$, and $M$.)

###### Proof.

Recall that $\beta$ is set as in steps 11-14 in CRM-NB-ALG . We begin by
making the following easy to see observations.

######  Observation 8.1.

  1. 1.

If $a^{*}\neq a_{0}$ then $d_{0}=\frac{\mu_{a^{*}}}{\gamma}-\mu_{0}$.

  2. 2.

Let $\widehat{\mu}^{*}=\max_{i,x}(\widehat{\mu}_{i,x}(T))$ (as computed in
step 11 of CRM-NB-ALG ). If
$|\widehat{\mu}_{0}(T)-\mu_{0}|\leq\frac{d_{0}}{4}$ and
$|\frac{\widehat{\mu}_{i,x}(T)}{\gamma}-\frac{\mu_{i,x}}{\gamma}|\leq\frac{d_{0}}{4}$
for all $(i,x)$ then
$\frac{d_{0}}{2}\leq\frac{\widehat{\mu}^{*}}{\gamma}-\widehat{\mu}_{0}(T)\leq\frac{3d_{0}}{2}$,
and $\frac{32}{9d_{0}^{2}}\leq\beta^{2}\leq\frac{32}{d_{0}^{2}}$. Notice that
since $T\geq e^{\frac{50}{d_{0}^{2}}}$, $\frac{32}{d_{0}^{2}}\leq\ln T$.

Let $U_{0}$ be the event that
$|\widehat{\mu}_{0}-\mu_{0}|\leq\frac{d_{0}}{4}$, and for any $i,x$ let
$U_{i,x}$ be the event
$|\frac{\widehat{\mu}_{i,x}}{\gamma}-\frac{\mu_{i,x}}{\gamma}|\leq\frac{d_{0}}{4}$.
Also let $U=(\cap_{i,x}U_{i,x})\cap U_{0}$, and let $\overline{U}_{0}$,
$\overline{U}_{i,x}$, and $\overline{U}$ denote the compliment of the events
$U_{0},U_{i,x}$, and $\overline{U}$ respectively. From parts 1 and 3 of Lemma
8.5, we have

$\mathbb{P}\Big{\\{}\overline{U}_{0}\Big{\\}}\leq\frac{2}{T^{\frac{d_{0}^{2}\ln
T}{8}}}~{},\text{~{}and}$ $\text{for a fixed
}(i,x)~{}~{}~{}\mathbb{P}\Big{\\{}\overline{U}_{i,x}\Big{\\}}\leq\frac{2}{T^{\frac{p\gamma^{2}d_{0}^{2}}{16}}}+\frac{1}{T^{\frac{p^{2}}{2}}}~{}.$

Hence applying union bound,

$\displaystyle\mathbb{P}\\{\overline{U}\\}$ $\displaystyle\leq
4M\left(\frac{1}{T^{\frac{p\gamma^{2}d_{0}^{2}}{16}}}+\frac{1}{T^{\frac{p^{2}}{2}}}\right)+\frac{2}{T^{\frac{d_{0}^{2}}{8}}}$
$\displaystyle\leq
4M\left(\frac{1}{T^{\frac{p^{2}d_{0}^{2}}{16}}}+\frac{1}{T^{\frac{p^{2}d_{0}^{2}}{16}}}\right)+\frac{2M}{T^{\frac{p^{2}d_{0}^{2}}{16}}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{as
}~{}\gamma\geq 1,p\leq 1,d_{0}\leq 1$
$\displaystyle\leq\frac{10M}{T^{\frac{p^{2}d_{0}^{2}}{16}}}=\delta~{}.$

We will use the above arguments to first show that
$E[\beta^{2}]\geq\frac{8}{d_{0}^{2}}$. From part 2 of Observation 8.1 we have
that the event $U$ implies $\beta^{2}\geq\frac{32}{9d_{0}^{2}}$. Since
$\mathbb{P}\\{U\\}\geq 1-\delta$,

$E[\beta^{2}]\geq\frac{32}{9d_{0}^{2}}(1-\delta)=\frac{32}{9d_{0}^{2}}-\frac{32\delta}{9d_{0}^{2}}$

Since $T$ satisfies $\frac{T^{\frac{p^{2}d_{0}^{2}}{16}}}{\ln T}\geq 15M$,
this implies $\frac{32\delta}{9d_{0}^{2}}\leq\frac{24}{9d_{0}^{2}}$, and hence
$E[\beta^{2}]\geq\frac{8}{9d_{0}^{2}}$. Similarly, from part 2 of Observation
8.1 we have that the event $U$ implies $\beta^{2}\leq\frac{32}{d_{0}^{2}}$.
Here, we use that if $U$ does not hold then $\beta^{2}\leq\ln T$. Hence

$E[\beta^{2}]\leq\frac{32}{d_{0}^{2}}(1-\delta)+\delta\ln
T\leq\frac{32}{d_{0}^{2}}+\delta\ln T~{}.$

Since $T$ satisfies $\frac{T^{\frac{p^{2}d_{0}^{2}}{16}}}{\ln T}\geq 15M$, we
have $\delta\ln T\leq\frac{18}{d_{0}^{2}}$, and hence
$E[\beta^{2}]\leq\frac{50}{d_{0}^{2}}$. ∎

######  Lemma 8.7.

Suppose the algorithm pulls the arms for $T$ rounds and if $a^{*}\neq
a_{i,x}$. Then

$E[N^{i,x}_{T}|T]\leq\max\left(0,\frac{8\ln
T}{d_{i,x}^{2}}+1-p_{i,x}E[N^{0}_{t}]\right)+\frac{\pi^{2}}{3}~{}.$

Further if $a^{*}\neq a_{0}$ then

$E[N_{0,t}|T]\leq\max\Big{(}E[\beta^{2}]\ln T,~{}\frac{8\ln
T}{d_{0}^{2}}+1\Big{)}+\frac{\pi^{2}}{3},~{}.$

###### Proof.

For ease of notation we denote $E[N^{i,x}_{T}|T]$ as $E[N^{i,x}_{T}]$. Observe
that

$N^{i,x}_{T}=\sum_{t\in T}\mathbb{1}\\{a(t)=a_{i,x}\\}~{}.$ (16)

Since
$E^{i,x}_{T}=N^{i,x}_{T}+\sum_{t\in[T]}\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}$,
if $E^{i,x}_{T}=\ell$ then
$N^{i,x}_{T}=\max(0,\ell-\sum_{t\in[T]}\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\})$.
We use this to rewrite Equation 16 as follows

$N^{i,x}_{T}\leq\text{max}(0,\ell-\sum_{t\in[T]}\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\})+\sum_{t\in
T}\mathbb{1}\\{a(t)=a_{i,x},E^{i,x}_{t}\geq\ell\\}~{}.$ (17)

We require the following observation which is easy to prove.

######  Observation 8.2.

$\sum_{t\in[T]}E[\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}]=p_{i,x}E[N^{0}_{T}]$
.

###### Proof.

Observe that

$E[\sum_{t\in[T]}\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}]=\sum_{t\in[T]}E[\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}]=\sum_{t\in[T]}\mathbb{P}\\{\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}\\}$

Also observe that

$\mathbb{P}\\{\mathbb{1}\\{a(t)=a_{0}~{}~{}\text{and}~{}~{}X_{i}=x\\}=\mathbb{P}\\{\mathbb{1}\\{X_{i}=x\\}\mid
a(t)=a_{0}\\}\\}\cdot\mathbb{P}\\{a(t)=a_{0}\\}=p_{i,x}\mathbb{P}\\{a(t)=a_{0}\\}~{}.$

∎

We continue by taking expectation on both sides of Equation 17 and use
Observation 8.2,

$E[N^{i,x}_{T}]\leq\text{max}\left(0,\ell-
p_{i,x}E[N^{0}_{t}]\right)+\sum_{t\in[\ell+1,T]}\mathbb{P}\\{a(t)=a_{i,x},E^{i,x}_{t}\geq\ell\\}~{}.$
(18)

Now we bound
$\sum_{t\in[\ell+1,T]}\mathbb{P}\\{a(t)=a_{i,x},E^{i,x}_{t}\geq\ell\\}$, and
assuming $a^{*}\neq a_{0}$. The proof for $a^{*}=a_{0}$ is similar. Before
proceeding we make a note of few notations. We use $E^{a^{*}}_{T}$ to denote
the effective number of pulls of $a^{*}$ at the end of $T$ rounds. Also, for
better clarity in the arguments below, we use
$\widehat{\mu}_{i,x}(E^{i,x}_{T},T)$ (instead of $\widehat{\mu}_{i,x}(T)$) and
$\widehat{\mu}_{0}(N^{0}_{T},T)$ (instead of $\widehat{\mu}_{0}(T)$) to denote
the empirical estimates of $\mu_{i,x}$ and $\mu_{0}$ computed by CRM-NB-ALG at
the end of $T$ rounds using $E^{i,x}_{T}$ and $N^{0}_{T}$ samples
respectively. Let
$C=\sum_{t\in[\ell+1,T]}\mathbb{P}\\{a(t)=a_{i,x},E^{i,x}_{t}\geq\ell\\}$ for
convenience. Then

$\displaystyle C$
$\displaystyle=\sum_{t\in[\ell,T-1]}\mathbb{P}\Bigg{\\{}\frac{\widehat{\mu}_{a^{*}}(E^{a^{*}}_{t},t)}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}E^{a^{*}}_{t}}}\leq\frac{\widehat{\mu}_{i,x}(E^{i,x}_{t},t)}{\gamma}+\sqrt{\frac{2\ln(t)}{\gamma^{2}E^{i,x}_{t}}},~{}~{}E^{i,x}_{t}\geq\ell\Bigg{\\}}$
$\displaystyle\leq\sum_{t\in[0,T-1]}\mathbb{P}\Bigg{\\{}\text{min}_{s\in[0,t]}\frac{\widehat{\mu}_{a^{*}}(s,t)}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s}}\leq\text{max}_{s_{j}\in[\ell-1,t]}\frac{\widehat{\mu}_{i,x}(s_{j},t)}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s_{j}}}\Bigg{\\}}$ $\displaystyle\leq\sum_{t\in
T}\sum_{s\in[0,t-1]}\sum_{s_{j}\in[\ell-1,t]}\mathbb{P}\Bigg{\\{}\frac{\widehat{\mu}_{a^{*}}(s,t)}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s}}\leq\frac{\widehat{\mu}_{i,x}(s_{j},t)}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s_{j}}}\Bigg{\\}}$

If $\frac{\widehat{\mu}_{a^{*}}(s,t)}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s}}\leq\frac{\widehat{\mu}_{i,x}(s_{j},t)}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s_{j}}}$ is true then at least one of the following events is
true

$\displaystyle\frac{\widehat{\mu}_{a^{*}}(s,t)}{\gamma}$
$\displaystyle\leq\frac{\mu_{a^{*}}}{\gamma}-\sqrt{\frac{2\ln
t}{\gamma^{2}s}}~{},$ (19a)
$\displaystyle\frac{\widehat{\mu}_{i,x}(s_{j},t)}{\gamma}$
$\displaystyle\geq\frac{\mu_{i,x}}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s_{j}}}~{},$ (19b) $\displaystyle\frac{\mu_{a^{*}}}{\gamma}$
$\displaystyle\leq\frac{\mu_{i,x}}{\gamma}+2\sqrt{\frac{2\ln
t}{\gamma^{2}s_{j}}}~{}.$ (19c)

The probability of the events in Equations 19a and 19b can be bounded using
Lemma 8.1,

$\mathbb{P}\Bigg{\\{}\frac{\widehat{\mu}_{a^{*}}(s,t)}{\gamma}\leq\frac{\mu_{a^{*}}}{\gamma}-\sqrt{\frac{2\ln
t}{\gamma^{2}s}}\Bigg{\\}}\leq t^{-4}~{},$
$\mathbb{P}\Bigg{\\{}\frac{\widehat{\mu}_{i,x}(s_{j},t)}{\gamma}\geq\frac{\mu_{i,x}}{\gamma}+\sqrt{\frac{2\ln
t}{\gamma^{2}s_{j}}}\Bigg{\\}}\leq t^{-4}~{}.$

Also if $\ell\geq\lceil\frac{8\ln T}{d_{i,x}^{2}}\rceil$ then the event in
Equation 19c is false, i.e.
$\frac{\mu_{a^{*}}}{\gamma}>\frac{\mu_{i,x}}{\gamma}+2\sqrt{\frac{2\ln
t}{\gamma^{2}s_{j}}}$ (as $\gamma\geq 1$). Thus we set $\ell=\frac{8\ln
T}{d_{i,x}^{2}}+1\geq\lceil\frac{8\ln T}{d_{i,x}^{2}}\rceil$, which implies

$\sum_{t\in
T}\mathbb{P}\\{a(t)=a_{i,x},E^{i,x}_{t}\geq\ell\\}\leq\sum_{t\in[T]}\sum_{s\in[T]}\sum_{s_{j}\in[\ell,T]}2t^{-4}\leq\frac{\pi^{2}}{3}$
(20)

If $a^{*}=a_{0}$ then using the exact arguments as above we can show that
Equation 20 still holds. Hence, using Equations 18 and 20 we have if
$a^{*}\neq a_{i,x}$ then

$E[N^{i,x}_{T}]\leq\text{max}\left(0,\frac{8\ln
T}{d_{i,x}^{2}}+1-p_{i,x}E[N^{0}_{t}]\right)+\frac{\pi^{2}}{3}~{}.$

The arguments used to bound $E[N^{0}_{T}|T]$ (denoted $E[N^{0}_{T}]$ for
convenience), when $a^{*}\neq a_{0}$ is similar. In this case the equation
corresponding to Equation 18 is

$E[N^{0}_{T}]\leq\text{max}\Big{(}E[\beta^{2}]\ln
T,~{}\ell\Big{)}+\sum_{t\in[\ell+1,T]}\mathbb{P}\\{a(t)=a_{0},N^{0}_{t}\geq\ell\\}~{}.$
(21)

Also the same arguments as above can be used to show that for $\ell=\frac{8\ln
T}{d_{0}^{2}}+1$,

$\sum_{t\in
T}\mathbb{P}\\{a(t)=a_{0},N^{0}_{t}\geq\ell\\}\leq\frac{\pi^{2}}{3}~{}.$ (22)

Finally using Equations 21 and 22, we have

$E[N^{0}_{T}]\leq\text{max}\left(E[\beta^{2}]\ln T,~{}\frac{8\ln
T}{d_{0}^{2}}+1\right)+\frac{\pi^{2}}{3}~{}.$

∎

######  Lemma 8.8.

If $a^{*}=a_{0}$ and suppose the algorithm pulls the arms for $T$ rounds then

$E[N^{0}_{T}|T]\geq T-\left(2M(1+\frac{\pi^{2}}{3})\sum_{i,x}\frac{8\ln
T}{d_{i,x}^{2}}\right)~{}.$

###### Proof.

For convenience, we denote $E[N^{i,x}_{T}|T]$ and $E[N^{0}_{T}|T]$ as
$E[N^{i,x}_{T}]$ and $E[N^{0}_{T}]$ respectively. At the end of $T$ rounds we
have

$N^{0}_{T}+\sum_{i,x}N^{i,x}_{T}=T~{}.$

Taking expectation on both sides of the above equation and rearranging the
terms we have,

$E[N^{0}_{T}]=T-\sum_{i,x}E[N^{i,x}_{T}]~{}.$

Now we use Lemma 8.7 to conclude that

$E[N^{0}_{T}]\geq T-\left(2M(1+\frac{\pi^{2}}{3})\sum_{i,x}\frac{8\log
T}{d_{i,x}^{2}}\right)~{}.$

∎

Before we bound the regret of the algorithm we make the following observation
regarding $T$, which is the number of rounds CRM-NB-ALG pulls the arms before
exhausting the budget $B$:

$\frac{B}{\gamma}\leq T\leq B~{}~{}\Rightarrow~{}~{}\frac{B}{\gamma}\leq
E_{T}[T]\leq B~{}.$ (23)

Now are ready to bound the expected cumulative regret of CRM-NB-ALG for the
two cases:

Case a ($a^{*}=a_{0}$): In this case we bound the expected cumulative regret
of CRM-NB-ALG for $B$ satisfying

$\frac{B}{\gamma}\geq\frac{1}{p_{i,x}}(1+\frac{8\ln
B}{d_{i,x}^{2}})+\left(2M(1+\frac{\pi^{2}}{3})\sum_{i,x}\frac{8\ln
B}{d_{i,x}^{2}}\right)~{}.$ (24)

Observe that the constraint on $B$ in Equation 24 is satisfied for any large
$B$. We begin by making the following observation which shows that in this
case the expected number of pulls of a sub-optimal arm is bounded by a
constant for any large $B$. Observe that the constraint on $B$ in Observation
8.3 is satisfied for any large $B$.

######  Observation 8.3.

Let $a^{*}=a_{0}$, and $T$ be the number of rounds CRM-NB-ALG pulls the arms
before the budget $B$ is exhausted, where $B$ satisfies the constraint in
Equation 24. Then $E_{T}[N^{i,x}_{T}]\leq\frac{\pi^{2}}{3}$.

###### Proof.

From Lemmas 8.7 and 8.8 for any $T$ satisfying

$T\geq\frac{1}{p_{i,x}}(1+\frac{8\ln
T}{d_{i,x}^{2}})+\left(2M(1+\frac{\pi^{2}}{3})\sum_{i,x}\frac{8\ln
T}{d_{i,x}^{2}}\right)$ (25)

we have $E[N^{i,x}_{T}|T]\leq\frac{\pi^{2}}{3}$. Notice that the constraint on
$T$ in Equation 25 is the same as the constraint on $\frac{B}{\gamma}$ in
Equation 24. Moreover, observe that if $\frac{B}{\gamma}$ satisfies the
constraint in Equation 24 then $T\geq\frac{B}{\gamma}$ satisfies Equation 25
with probability $1$. Hence, $E_{T}[N^{i,x}_{T}|T]\leq\frac{\pi^{2}}{3}$. ∎

Next observe that in this case $G_{B}$ (see Equation 2) is $B\mu_{0}$, i.e the
optimal solution is to play arm $a_{0}$ in all the rounds. We require the
following observation which lower bounds $E_{T}[T]$ in terms of $B$, which is
the total number of rounds played by the optimal solution.

######  Observation 8.4.

Let $a^{*}=a_{0}$, and $T$ be the number of rounds CRM-NB-ALG pulls the arms
before the budget $B$ is exhausted, where $B$ satisfies the constraint in
Equation 24. Then $E_{T}[T]\geq B-1-\frac{2M\pi^{2}(\gamma-1)}{3}$.

###### Proof.

Let $c_{a_{t}}$ denote the cost of arm $a_{t}$ pulled at time $t\leq T$. That
is $c_{a_{t}}=\gamma$ if $a_{t}=a_{i,x}$ and $c_{a_{t}}=1$ if $a_{t}=a_{0}$.
Then the following is always true, as CRM-NB-ALG pulls arms till the budget is
the exhausted:

$B-1\leq\sum_{t\in[T]}c_{a_{t}}~{}.$ (26)

Taking expectation over $T$ and the sequence of arm pulls $\\{a_{t}\\}$ made
by CRM-NB-ALG , on both sides of the above equation, we have

$\displaystyle B-1$ $\displaystyle\leq
E_{T,\\{a_{t}\\}}\Big{[}\sum_{t\in[T]}c_{a_{t}}\Big{]}$ $\displaystyle\leq
E_{T}\Big{[}E_{\\{a_{t}\\}}[\sum_{t\in[T]}c_{a_{t}}]\Big{]}$
$\displaystyle\leq
E_{T}\Big{[}\sum_{t\in[T]}\Big{(}\mathbb{P}\\{a_{t}=a_{0}\\}+\gamma(\sum_{i,x}\mathbb{P}\\{a_{t}=a_{i,x}\\}\Big{)}\Big{]}$
$\displaystyle\leq
E_{T}\Big{[}T+\sum_{t\in[T]}(\gamma-1)(\sum_{i,x}\mathbb{P}\\{a_{t}=a_{i,x}\\})\Big{]}$
$\displaystyle\leq
E_{T}[T]+E_{T}\Big{[}\sum_{i,x}(\gamma-1)(\sum_{t\in[T]}\mathbb{P}\\{a_{t}=a_{i,x}\\})\Big{]}$
$\displaystyle\leq
E_{T}[T]+E_{T}\Big{[}\sum_{i,x}(\gamma-1)E[N^{i,x}_{T}|T]\Big{]}~{}.$

The third line in the above set of equations follows by using
$\mathbb{P}\\{a_{t}=a_{0}\\}=1-\sum_{i,x}\mathbb{P}\\{a_{t}=a_{i,x}\\}$.
Finally from Observation 8.3, we have $E[N^{i,x}_{T}]\leq\frac{\pi^{2}}{3}$.
Substituting this in the last line of the above equation, we have
$E_{T}[T]\geq B-1-\frac{2M\pi^{2}(\gamma-1)}{3}$. ∎

Finally we bound the expected cumulative regret of CRM-NB-ALG when
$a^{*}=a_{0}$ as follows:

$\displaystyle E[R_{\texttt{CRM-NB-ALG}}(B)]~{}\leq$ $\displaystyle
G_{B}-E_{T,\\{a_{t}\\}}\left[\sum_{t\in[T]}\mu_{a_{t}}\right]$
$\displaystyle~{}\leq$ $\displaystyle
B\mu_{0}-E_{T}\left[\sum_{t=1}^{T}E_{\\{a_{t}\\}}[\mu_{a_{t}}]\right]$
$\displaystyle~{}\leq$ $\displaystyle
E_{T}\left[B\mu_{0}-\sum_{t=1}^{T}E_{\\{a_{t}\\}}[\mu_{a_{t}}]\right]$
$\displaystyle~{}\leq$ $\displaystyle
E_{T}\left[B\mu_{0}-\sum_{t=1}^{T}\sum_{a\in\mathcal{A}}\mu_{a}\mathbb{P}\\{a_{t}=a\\}\right]$
$\displaystyle~{}\leq$ $\displaystyle
E_{T}\left[(B-T)\mu_{0}+\sum_{t=1}^{T}(\mu_{0}-\sum_{a\in\mathcal{A}}\mu_{a}\mathbb{P}\\{a_{t}=a\\})\right]$
$\displaystyle~{}\leq$ $\displaystyle
E_{T}\left[(B-T)\mu_{0}\right]+E_{T}\left[\sum_{t=1}^{T}\sum_{\Delta_{a}>0}\Delta_{a}\mathbb{P}\\{a_{t}=a\\})\right]~{}.$

Thus, from Observations 8.3 and 8.4, we have

$E[R_{\texttt{CRM-NB-ALG}}(B)]\leq
1+\frac{2M\pi^{2}(\gamma-1)}{3}+\sum_{\Delta_{a}>0}\Delta_{a}\frac{\pi^{2}}{3}~{}.$

Observe that the expected regret of CRM-NB-ALG is bounded by a constant for
large $B$ and hence $O(1)$.

Case b ($a^{*}\neq a_{0}$): In this case we bound the expected cumulative
regret of CRM-NB-ALG for $B$ satisfying
$B\geq\max(L,e^{\frac{50}{d_{0}^{2}}})$, where $L$ is as in Lemma 8.6. Observe
that the constraint is satisfied for any large $B$. Let $T$ be the number of
rounds CRM-NB-ALG pulls the arms before exhausting the budget $B$. Then from
Equation 25, we have $T\geq\max(L,e^{\frac{50}{d_{0}^{2}}})$. Hence, from
Lemmas 8.6 and 8.7, and as $T\leq B$ (from Equation 23), we have for
$a^{*}\neq a_{i,x}$

$E_{T}\left[E[N^{i,x}_{T}|T]\right]\leq\max\left(0,1+8\ln
B\left(\frac{1}{d_{i,x}^{2}}-\frac{p_{i,x}}{9d_{0}^{2}}\right)\right)+\frac{\pi^{2}}{3}~{},$
(27) $\text{and}~{}~{}~{}~{}E_{T}\left[E[N^{0}_{T}|T]\right]\leq\frac{50\ln
B}{d_{0}^{2}}+\frac{\pi^{2}}{3}~{}~{}.$ (28)

Also observe that in this case $G_{B}$ is at most
$\frac{B\mu_{a^{*}}}{\gamma}$. Below we bound the expected cumulative regret
of CRM-NB-ALG when $a^{*}\neq a_{0}$

$\displaystyle E[R_{\texttt{CRM-NB-ALG}}(B)]~{}\leq$
$\displaystyle\frac{B\mu_{a^{*}}}{\gamma}-E_{T,\\{a_{t}\\}}\left[\sum_{t\in[T]}\mu_{a_{t}}\right]$
$\displaystyle~{}\leq$
$\displaystyle~{}\frac{B\mu_{a^{*}}}{\gamma}-E_{T}\left[\sum_{t=1}^{T}E_{\\{a_{t}\\}}[\mu_{a_{t}}]\right]$
$\displaystyle~{}\leq$
$\displaystyle~{}E_{T}\left[\frac{B\mu_{a^{*}}}{\gamma}-\sum_{t=1}^{T}E_{\\{a_{t}\\}}[\mu_{a_{t}}]\right]$
$\displaystyle~{}\leq$
$\displaystyle~{}E_{T}\left[\frac{B\mu_{a^{*}}}{\gamma}-\sum_{t=1}^{T}\sum_{a\in\mathcal{A}}\mu_{a}\mathbb{P}\\{a_{t}=a|T\\}\right]$
$\displaystyle~{}\leq$
$\displaystyle~{}E_{T}\left[\Big{(}\frac{B}{\gamma}-T\Big{)}\mu_{a^{*}}+\sum_{t=1}^{T}(\mu_{a^{*}}-\sum_{a\in\mathcal{A}}\mu_{a}\mathbb{P}\\{a_{t}=a|T\\})\right]$
$\displaystyle~{}\leq$
$\displaystyle~{}E_{T}\left[\Big{(}\frac{B}{\gamma}-T\Big{)}\mu_{a^{*}}\right]+E_{T}\left[\sum_{t=1}^{T}\sum_{\Delta_{a}>0}\Delta_{a}\mathbb{P}\\{a_{t}=a|T\\})\right]~{}.$

Now observe that as $T\geq\frac{B}{\gamma}$,
$E_{T}[(\frac{B}{\gamma}-T)\mu_{a^{*}}]\leq 0$. Also note that
$E_{T}[\sum_{t=1}^{T}\mathbb{P}\\{a_{t}=a|T\\}]=E_{T}[N^{a}_{T}|T]$. Using
this and Equations 27 and 28, we have our result as follows:

$\displaystyle E[R_{\texttt{CRM-NB-ALG}}(B)]~{}\leq$
$\displaystyle~{}\Delta_{0}E_{T}\left[E[N^{0}_{T}|T]\right]+\sum_{\Delta_{i,x}>0}\Delta_{i,x}E_{T}\left[E[N^{i,x}_{T}|T]\right]$
$\displaystyle~{}\leq$ $\displaystyle~{}\Delta_{0}\Big{(}\frac{50\ln
B}{d_{0}^{2}}+\frac{\pi^{2}}{3}\Big{)}+\sum_{\Delta_{i,x}>0}\Delta_{i,x}\max\left(0,1+8\ln
B\left(\frac{1}{d_{i,x}^{2}}-\frac{p_{i,x}}{9d_{0}^{2}}\right)\right)+\frac{\pi^{2}}{3}~{}.$

Hence, we have that the expected cumulative regret of CRM-NB-ALG is:

$E[R_{\texttt{CRM-NB-
ALG}}(B)]\leq\begin{cases}1+\frac{2M\pi^{2}(\gamma-1)}{3}+\sum_{\Delta_{a}>0}\Delta_{a}\frac{\pi^{2}}{3}\hskip
202.01474pt\text{when~{}}a^{*}=a_{0}\\\ \Delta_{0}\Big{(}\frac{50\ln
B}{d_{0}^{2}}+\frac{\pi^{2}}{3}\Big{)}+\sum_{\Delta_{i,x}>0}\Delta_{i,x}\max\left(0,1+8\ln
B\left(\frac{1}{d_{i,x}^{2}}-\frac{p_{i,x}}{9d_{0}^{2}}\right)\right)+\frac{\pi^{2}}{3}\hskip
14.22636pt\text{when~{}}a^{*}\neq a_{0}\end{cases}$

###  8.5 Proof of Theorem 4

Throughout this proof $a$ and $\mathbf{y}$ indexes the sets $\mathcal{A}$ and
$S^{n}$ respectively. Let $\delta$, $L_{1}$, $L_{2,a}$ and $L_{a}$ for all
$a$, be as in the theorem statement. Let $a^{*}=\arg\max_{a}(\mu_{a})$. As is
standard in MAB literature, we assume without loss of generality that $a^{*}$
is unique. Further, let $\Delta_{a}=\mu_{a^{*}}-\mu_{a}$. The regret upper
bound is proved using Lemmas 8.9 and 8.10.

######  Lemma 8.9.

Let $T$ be the number of rounds C-UCB 2 has pulled the arms. Then for $T\geq
L_{1}$ the following holds:

  1. 1.

For all $\mathbf{y}$ such that $c_{\mathbf{y}}>0$,
$\mathbb{P}\big{\\{}N_{\mathbf{y},T}\leq\frac{E[N_{\mathbf{y},T}]}{2}\big{\\}}\leq
e^{-\frac{E[N_{\mathbf{y},T}]^{2}}{2T}}$ ,

  2. 2.

For all $\mathbf{y}$ such that $c_{\mathbf{y}}>0$ and for any
$\varepsilon_{\mathbf{y}}\geq 0$,
$\mathbb{P}\\{|\widehat{\mu}_{\mathbf{y}}(T)-\mu_{\mathbf{y}}|\geq\varepsilon_{\mathbf{y}}\\}\leq
2e^{-c_{\mathbf{y}}^{2}T\varepsilon_{\mathbf{y}}^{2}}+e^{-\frac{c_{\mathbf{y}}^{2}T}{2}}$
,

  3. 3.

For all $a$,
$\mathbb{P}\Big{(}|\widehat{\mu}_{a}(T)-\mu_{a}|\geq\sqrt{\frac{\log(k^{n}T^{2}/2)}{T}}\zeta_{a}\Big{)}\leq\frac{2}{T^{2}}$
.

###### Proof.

1\. Part 1 of the lemma follows from Lemma 8.1.

2\. Using Lemma 8.1 again, it follows that for all ${\mathbf{y}}$ such that
$c_{\mathbf{y}}>0$, and for all $\varepsilon_{\mathbf{y}}\geq 0$,

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{\mathbf{y}}(T)-\mu_{\mathbf{y}}\Big{|}\geq\varepsilon_{\mathbf{y}}\mid
N_{\mathbf{y},T}>\frac{E[N_{\mathbf{y},T}]}{2}\Big{\\}}\leq
2e^{-E[N_{\mathbf{y},T}]\varepsilon_{\mathbf{y}}^{2}}~{}.$ (29)

Hence, for all ${\mathbf{y}}$ such that $c_{\mathbf{y}}>0$, using the law of
total probability we have

$\displaystyle\mathbb{P}(|\widehat{\mu}_{\mathbf{y}}(T)-\mu_{\mathbf{y}}|\geq\varepsilon_{\mathbf{y}})$
$\displaystyle=\mathbb{P}\Big{\\{}|\widehat{\mu}_{\mathbf{y}}(T)-\mu_{\mathbf{y}}|\geq\varepsilon_{\mathbf{y}}\Big{|}N_{\mathbf{y},T}>\frac{E[N_{\mathbf{y},T}]}{2}\Big{\\}}\mathbb{P}\Big{\\{}N_{\mathbf{y},T}>\frac{E[N_{\mathbf{y},T}]}{2}\Big{\\}}+$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\mathbb{P}\Big{\\{}|\widehat{\mu}_{\mathbf{y}}(T)-\mu_{\mathbf{y}}|\geq\varepsilon_{\mathbf{y}}\Big{|}N_{\mathbf{y},T}\leq\frac{E[N_{\mathbf{y},T}]}{2}\Big{\\}}\mathbb{P}\Big{\\{}N_{\mathbf{y},T}\leq\frac{E[N_{\mathbf{y},T}]}{2}\Big{\\}}$
$\displaystyle\leq\mathbb{P}\Big{\\{}|\widehat{\mu}_{\mathbf{y}}(T)-\mu_{\mathbf{y}}|\geq\varepsilon_{\mathbf{y}}\Big{|}N_{\mathbf{y},T}>\frac{E[N_{\mathbf{y},T}]}{2}\Big{\\}}+\mathbb{P}\Big{\\{}N_{\mathbf{y},T}\leq\frac{E[N_{\mathbf{y}},T]}{2}\Big{\\}}$
$\displaystyle\leq
2e^{-E[N_{\mathbf{y},T}]\varepsilon_{\mathbf{y}}^{2}}+e^{-\frac{E[N_{\mathbf{y},T}]^{2}}{2T}}$
$\displaystyle\leq
2e^{-c_{\mathbf{y}}T\varepsilon_{\mathbf{y}}^{2}}+e^{-\frac{c_{\mathbf{y}}^{2}T}{2}}$
$\displaystyle\leq
2e^{-c_{\mathbf{y}}^{2}T\varepsilon_{\mathbf{y}}^{2}}+e^{-\frac{c_{\mathbf{y}}^{2}T}{2}}~{}.$

The second line in the above equations follows from Equation 29 and part one
of this lemma. The last two inequalities follow by observing that
$E[N_{\mathbf{y},T}]\geq c_{\mathbf{y}}T\geq c_{\mathbf{y}}^{2}T$. This is
true as for each $\mathbf{y}$,
$c_{\mathbf{y}}=\text{min}_{a}\mathbb{P}\\{Pa(Y)=\mathbf{y}\mid do(a)\\}$, and
hence $0<c_{\mathbf{y}}\leq 1$.

3\. Let
$\varepsilon_{\mathbf{y}}=\sqrt{\frac{\log(k^{n}T^{2}/2)}{c_{\mathbf{y}}^{2}T}}$
if $c_{\mathbf{y}}>0$, and $\varepsilon_{\mathbf{y}}=0$ if $c_{\mathbf{y}}=0$.
Since the parent distributions have the same non-zero support, and as
$\widehat{\mu}_{a}(T)=\sum_{\mathbf{y}}\widehat{\mu}_{\mathbf{y}}(T)\mathbb{P}\\{Pa(Y)=\mathbf{y}|do(a)\\}$,
the event

$|\widehat{\mu}_{a}(T)-\mu_{a}|\geq\sum_{\mathbf{y},c_{\mathbf{y}}>0}\varepsilon_{\mathbf{y}}\mathbb{P}\\{Pa(Y)=\mathbf{y}|do(a)\\}$

implies there is a $\mathbf{y}$ such that $c_{\mathbf{y}}>0$ and
$\\{|\widehat{\mu}_{\mathbf{y}}(T)-\mu_{\mathbf{y}}|\geq\varepsilon_{\mathbf{y}}\\}$.
Hence, using part 2 of this lemma and applying union bound over all
$\mathbf{y}$ such that $c_{\mathbf{y}}>0$, we have for every $a$

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{a}(T)-\mu_{a}|\geq\sum_{\mathbf{y},c_{\mathbf{y}}>0}\varepsilon_{\mathbf{y}}\mathbb{P}\\{Pa(Y)=\mathbf{y}|do(a)\\}\Big{\\}}\leq\sum_{\mathbf{y},c_{\mathbf{y}}>0}\big{(}2e^{-c_{\mathbf{y}}^{2}T\varepsilon_{\mathbf{y}}^{2}}+e^{-\frac{c_{\mathbf{y}}^{2}T}{2}}\big{)}~{}.$

Substituting the values of $\varepsilon_{\mathbf{y}}$ and using
$\zeta_{a}=\sum_{\mathbf{y},c_{\mathbf{y}}>0}\frac{\mathbb{P}\\{Pa(Y)=\mathbf{y}\mid
do(a)\\}}{c_{\mathbf{y}}}$ in the above equation, we have

$\displaystyle\mathbb{P}\Big{\\{}|\widehat{\mu}_{a}(T)-\mu_{a}|\geq\sqrt{\frac{\log(k^{n}T^{2}/2)}{T}}\zeta_{a}\Big{\\}}$
$\displaystyle\leq\frac{1}{T^{2}}+\sum_{\mathbf{y},c_{\mathbf{y}}>0}e^{-\frac{c_{\mathbf{y}}^{2}T}{2}}$
$\displaystyle\leq\frac{1}{T^{2}}+k^{n}e^{-\delta^{2}T/2}$

where $\delta=\min_{c_{\mathbf{y}}>0}c_{\mathbf{y}}$. Since $T\geq L_{1}$,
$T\geq\frac{2\log(k^{n}T^{2})}{\delta^{2}}$. This implies
$k^{n}e^{-\delta^{2}T/2}\leq\frac{1}{T^{2}}$, and

$\mathbb{P}\Big{\\{}|\widehat{\mu}_{a}-\mu_{a}|\geq\sqrt{\frac{\log(k^{n}T^{2}/2)}{T}}\zeta_{a}\Big{\\}}\leq\frac{2}{T^{2}}~{}.$

∎

######  Lemma 8.10.

Let $a\in A$ be a sub-optimal intervention. Then the expected number of times
intervention $a$ is made after $L_{a}=\max\\{L_{1},L_{2,a}\\}$ rounds is at
most $\frac{2\pi^{2}}{3}$.

###### Proof.

For ease of notation, we denote $\sqrt{\frac{\log(k^{n}t^{2}/2)}{t}}\zeta_{a}$
as $c_{a,t}$. Note that $c_{a,t}$ is the confidence radius of intervention $a$
C-UCB-2 maintains at the end of $t$ rounds. Further, let $N^{\prime}_{a,T}$
denote the number of times the algorithm performs intervention $a$ from time
$L_{a}+1$ to time $T\geq L_{a}$, and also let $a_{t}$ denote the intervention
performed at time $t$. Hence,

$N^{\prime}_{a,T}=\sum_{t=L_{a}+1}^{T}\mathbb{1}\Big{\\{}a_{t}=a\Big{\\}}~{}.$
(30)

Note that $a_{t}=a$ implies $\bar{\mu}_{a^{*}}(t-1)\leq\bar{\mu}_{a}(t-1)$
i.e.
$\widehat{\mu}_{a^{*}}(t-1)+c_{a^{*},t-1}\leq\widehat{\mu}_{a}(t-1)+c_{a,t-1}$
. Hence from Equation 30, we have

$N^{\prime}_{a,T}\leq\sum_{t=L_{a}}^{T-1}\mathbb{1}\Big{\\{}\widehat{\mu}_{a^{*}}(t)+c_{a^{*},t}\leq\widehat{\mu}_{a}(t)+c_{a,t}\Big{\\}}~{}.$

The event $\widehat{\mu}_{a^{*},t}+c_{a^{*},t}\leq\widehat{\mu}_{a,t}+c_{a,t}$
implies that at least one of the following events is true

$\displaystyle\big{\\{}\widehat{\mu}_{a^{*}}(t)\leq\mu_{a^{*}}-c_{a^{*},t}\big{\\}}$
(31) $\displaystyle\big{\\{}\widehat{\mu}_{a}(t)\geq\mu_{a}+c_{a,t}\big{\\}}$
(32) $\displaystyle\big{\\{}\mu_{a^{*}}<\mu_{a}+2c_{a,t}\big{\\}}$ (33)

Since $t\geq L_{a}\geq L_{1}$, using Lemma 8.9 the probability of the events
in Equations 31 and 32 can be bounded as:

$\displaystyle\mathbb{P}\big{\\{}\widehat{\mu}_{a^{*}}(t)\leq\mu_{a^{*}}-c_{1,t}\big{\\}}\leq
2t^{-2}~{},$
$\displaystyle\mathbb{P}\big{\\{}\widehat{\mu}_{a}(t)\geq\mu_{a}+c_{a,t}\big{\\}}\leq
2t^{-2}~{}.$

The event in equation 33 $\big{\\{}\mu_{a^{*}}<\mu_{a}+2c_{a,t}\big{\\}}$ can
be written as
$\Big{\\{}\mu_{a^{*}}-\mu_{a}-2\sqrt{\frac{\log(k^{n}t^{2}/2)}{t}}\zeta_{a}<0\Big{\\}}$.
Substituting $\Delta_{a}=\mu_{a^{*}}-\mu_{a}$ and since $t\geq L_{a}\geq
L_{2,a}$, we have

$\displaystyle\mathbb{P}\Bigg{(}\bigg{\\{}\Delta_{a}-2c_{a,t}<0\bigg{\\}}\Bigg{)}=0~{}.$
(34)

Hence,

$E[N^{\prime}_{a,T}]\leq\sum_{t=L}^{T-1}\frac{4}{t^{2}}\leq\sum_{t=1}^{\infty}\frac{4}{t^{2}}\leq\frac{2\pi^{2}}{3}~{}.$

∎

Now we bound the expected cumulative regret of C-UCB-2. From Equation 3 in
Section 2, we have at the end of $T$ rounds

$\displaystyle E[R_{\texttt{C-UCB-2}}(T)]$
$\displaystyle=T\mu_{a^{*}}-\sum_{a\in\mathcal{A}}\mu_{a}E[N_{a,T}]$
$\displaystyle=\sum_{a\in\mathcal{A}}\Delta_{a}E[N_{a,T}]\leq\sum_{a\in\mathcal{A}}\Delta_{a}(L_{a}+\frac{2\pi^{2}}{3})~{}.$

The inequality in the last line of the above equation follows from Lemma 8.10.

## Acknowledgements

Vineet Nair is thankful to be supported by the European Union’s Horizon 2020
research and innovation program under grant agreement No 682203 -ERC-[ Inf-
Speed-Tradeoff]. Vishakha Patil gratefully acknowledges the support of a
Google PhD Fellowship.

## References

  * [ACBDK15] Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren.  Online learning with feedback graphs: Beyond bandits.  In Annual Conference on Learning Theory, 2015, volume 40, 2015.
  * [ACBF02] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2-3):235–256, 2002.
  * [AKMM20] Raghavendra Addanki, Shiva Prasad Kasiviswanathan, Andrew McGregor, and Cameron Musco.  Efficient intervention design for causal discovery with latents.  In International Conference on Machine Learning, 2020, 2020.
  * [BFP15] Elias Bareinboim, Andrew Forney, and Judea Pearl.  Bandits with unobserved confounders: A causal approach.  In Annual Conference on Neural Information Processing Systems, 2015, pages 1342–1350, 2015.
  * [BGK+20] Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, Ashwin Maran, and N. V. Vinodchandran.  Efficiently learning and sampling interventional distributions from observations.  CoRR, abs/2002.04232, 2020.
  * [KDV17] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath.  Cost-optimal learning of causal graphs.  In International Conference on Machine Learning, 2017, pages 1875–1884, 2017.
  * [KSB17] Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim.  Experimental design for learning causal graphs with latent variables.  In Annual Conference on Neural Information Processing Systems, 2017, pages 7018–7028, 2017.
  * [LB18] Sanghack Lee and Elias Bareinboim.  Structural causal bandits: Where to intervene?  In Annual Conference on Neural Information Processing Systems, 2018, pages 2573–2583, 2018.
  * [LB19] Sanghack Lee and Elias Bareinboim.  Structural causal bandits with non-manipulable variables.  In AAAI Conference on Artificial Intelligence, 2019, pages 4164–4172. AAAI Press, 2019.
  * [LKDV18] Erik M. Lindgren, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath.  Experimental design for cost-aware learning of causal graphs.  In Annual Conference on Neural Information Processing Systems, 2018, pages 5284–5294, 2018.
  * [LLR16] Finnian Lattimore, Tor Lattimore, and Mark D. Reid.  Causal bandits: Learning good interventions via causal inference.  In Annual Conference on Neural Information Processing Systems, 2016, pages 1181–1189, 2016.
  * [LMTY20] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan.  Regret analysis of bandit problems with causal background knowledge.  In Conference on Uncertainty in Artificial Intelligence, 2020, pages 141–150. PMLR, 2020.
  * [LPP10] Tyler Lu, Dávid Pál, and Martin Pál.  Contextual multi-armed bandits.  In International Conference on Artificial Intelligence and Statistics, 2010, pages 485–492, 2010.
  * [Pea00] Judea Pearl.  Causality: Models, Reasoning, and Inference.  Cambridge University Press, USA, 2000.
  * [Pea09] Judea Pearl.  Causality.  Cambridge university press, 2009.
  * [Rob52] Herbert Robbins.  Some aspects of the sequential design of experiments.  Bulletin of the American Mathematical Society, 58(5):527–535, 1952\.
  * [SB17] Vin Sachidananda and E Brunskill.  Online learning for causal bandits.  2017\.
  * [SSDS17] Rajat Sen, Karthikeyan Shanmugam, Alexandros G. Dimakis, and Sanjay Shakkottai.  Identifying best interventions through online importance sampling.  In International Conference on Machine Learning, 2017, volume 70 of Proceedings of Machine Learning Research, pages 3057–3066. PMLR, 2017.
  * [SSK+17] Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sanjay Shakkottai.  Contextual bandits with latent confounders: An NMF approach.  In International Conference on Artificial Intelligence and Statistics, 2017, volume 54 of Proceedings of Machine Learning Research, pages 518–527. PMLR, 2017.
  * [TCdC+10] Long Tran-Thanh, Archie C. Chapman, Enrique Munoz de Cote, Alex Rogers, and Nicholas R. Jennings.  Epsilon-first policies for budget-limited multi-armed bandits.  In AAAI Conference on Artificial Intelligence, 2010, 2010.
  * [TP02] Jin Tian and Judea Pearl.  A general identification condition for causal effects.  In National Conference on Artificial Intelligence and Conference on Innovative Applications of Artificial Intelligence, 2002, pages 567–573, 2002\.
  * [TTCRJ12] Long Tran-Thanh, Archie Chapman, Alex Rogers, and Nicholas R Jennings.  Knapsack based optimal policies for budget-limited multi-armed bandits.  In AAAI Conference on Artificial Intelligence, 2012, pages 1134–1140, 2012.
  * [YHS+18] Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, and Ken-ichi Kawarabayashi.  Causal bandits with propagating inference.  In International Conference on Machine Learning, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5508–5516. PMLR, 2018.