Budgeted and Non-budgeted Causal Bandits

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 variables The 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 parents A 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.

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.

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.

Model and Notations

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.

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

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

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 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

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.

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.

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.

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$.

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})})$.

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})$.

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

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. The 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.

Cumulative-Regret in No-backdoor Graphs with Budget

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:

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:

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.

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$.

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.

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.

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:

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}$.

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}$.

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.

Algorithm Simulations

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$. 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$, 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.

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$, $p_{1}=p_{2}=0.02$, and $p_{i}=0.5$ for $i\in$. 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.

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$.

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.

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,x\in\{0,1\}$ are given in the Table 2.

Figure 9 shows a comparison between the cumulative regret incurred by both algorithms for values of $T$ in the range $$. 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.

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.

Proofs of Theorems

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

Suppose $X_{1},\ldots,X_{T}$ are independent random variables taking values in the interval $$, 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:

2 Proof of Theorem 1

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:

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

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

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

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

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

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

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)$,

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

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

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:

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.

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

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

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

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$

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

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

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$

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

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

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:

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)

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

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)}$.

4 Proof of Theorem 3

The proof of Theorem 3 requires the the following lemmas.

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

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

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$:

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

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

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

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

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

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}}$. ∎

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

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

We require the following observation which is easy to prove.

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

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

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

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

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

Finally using Equations 21 and 22, we have

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

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

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

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$:

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

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$.

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}$.

From Lemmas 8.7 and 8.8 for any $T$ satisfying

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.

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}$.

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:

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

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

Thus, from Observations 8.3 and 8.4, we have

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}$

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}$

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

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.

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

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$,

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

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$

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

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}$.

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,

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

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

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:

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

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

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