Combinatorial Pure Exploration of Causal Bandits
Authors: Nuoya Xiong
Wei Chen
Venue: ICLR 2023 poster (2023)
Keywords: Bandit
causal bandit
pure exploration

Abstract: The combinatorial pure exploration of causal bandits is the following online learning task: given a causal graph with unknown causal inference distributions, in each round we choose a subset of variables to intervene or do no intervention, and observe the random outcomes of all random variables, with the goal that using as few rounds as possible, we can output an intervention that gives the best (or almost best) expected outcome on the reward variable $Y$ with probability at least $1-\delta$, where $\delta$ is a given confidence level. We provide the first gap-dependent and fully adaptive pure exploration algorithms on two types of causal models --- the binary generalized linear model (BGLM) and general graphs. For BGLM, our algorithm is the first to be designed specifically for this setting and achieves polynomial sample complexity, while all existing algorithms for general graphs have either sample complexity exponential to the graph size or some unreasonable assumptions. For general graphs, our algorithm provides a significant improvement on sample complexity, and it nearly matches the lower bound we prove. Our algorithms achieve such improvement by a novel integration of prior causal bandit algorithms and prior adaptive pure exploration algorithms, the former of which utilize the rich observational feedback in causal bandits but are not adaptive to reward gaps, while the latter of which have the issue in reverse.

Published as a conference paper at ICLR 2023
COMBINATORIAL PURE EXPLORATION OF CAUSAL BANDITS
Nuoya Xiong
Institute for Interdisciplinary Information Sciences, Tsinghua University Beijing, China
xi kiongnyy2@mailn i 1s. w....tinnghaa leigghaaadd....o edu.cn
Wei Chen
Microsoft Research
Beijing, China
wei cemi crosoft.com
ABSTRACT
The combinatorial pure exploration causal bandits is the following online learn- ing task: given causal graph with unknown causal inference distributions. in each round we choose a subset variables to intervene or do no intervention, and observe the random outcomes of all random variables, with the goal that using few rounds as possible, we can output an intervention that gives the best (or almost best) expected outcome the reward variable Y with probability at least 1 - 6, where is a given confidence level. We provide the first gap-dependent and fully adaptive pure exploration algorithms generalized linear model (BGLM) and general graphs. For BGLM, our algorithm is the first to be designed specifically for this setting and achieves polynomial sample complexity, while all existing algorithms for general graphs have either sample complexity exponential to the graph size or some unreasonable assumptions. For general graphs, our algorithm provides significant improvement on sample complexity, and nearly matches the lower bound we prove. Our algorithms achieve such improvement by novel integration of prior causal bandit algorithms and prior adaptive pure exploration algorithms, the former of which utilize the rich observational feedback in causal bandits but are not adaptive to reward gaps, while the latter which have the issue in reverse.
types of causal models the binary
INTRODUCTION
Stochastic multi-armed bandits (MAB) is a classical framework in sequential decision making (Robbins, 1952). In each round, learner selects one based on the reward feedback from the previous rounds. and receives a random reward of the selected arm sampled from an unknown distribution, with the goal of accumulating as much rewards as possible. Pure exploration is an important variant of the multi-armed bandit problem, where the goal is not accumulate reward but identify the best arm through possibly adaptive explorations of arms.
Causal bandits, first introduced by Lattimore et al. (2016), integrates causal inference (Pearl, 2009) with multi-armed bandits. In causal bandits, we have a causal graph structure = (X U(YYUU, E). where X U {Y) are observable causal variables with Y being special reward variable, U are unobserved hidden variables, and E the set of causal edges between pairs of variables. For simplicity, we consider binary variables in this paper. The arms the interventions variables S together with the choice of null intervention (natural observation), i.c. the action set is A C {a- = do S = 8) S C X, 8 E {0, 1| with do() E A, where do(S = 8) is the standard notation for intervening the causal graph by setting S to (Pearl, 2009). and do() means null intervention. The reward of an action is the random outcome of Y. and thus the expected reward is E|Y do(S s)]. In each round, one action in A is played, and the random outcomes of all variables in X U {Y) are observed. Given the causal graph but without knowing the distributions among nodes, the task of combinatorial pure exploration (CPE) of causal bandits is select actions

---

Published as a conference paper at ICLR 2023
in each round, observe the feedback from all observable random variables, so that in the end the learner can identify the best or nearly best actions. Causal bandits are useful in many real scenarios. In drug testing, the physicians wants to adjust the dosage of some particular drugs to treat the patient. In policy design, the policy-makers select different actions to reduce the spread of disease.
Existing studies on CPE of causal bandits either requires the knowledge of P(Pa(Y) aa) for all action a or only consider causal graphs without hidden variables, and the algorithms proposed are not fully adaptive to reward gaps (Lattimore et al., 2016; Yabe et al., 2018). In this paper, we study fully adaptive pure exploration algorithms and analyze their gap-dependent sample complexity bounds in the fixed-cofiieence setting. More specifically, given a confidence bound 8 E (0. 1) and an error bound E, we aim at designing adaptive algorithms that ouiput an action such that with probability at least 1 - 6, the expected reward difference between the output and the optimal action is most e. The algorithms should be fully adaptive in the follow two senses. First, it should adapt to the reward gaps between suboptimal and optimal actions similar to existing adaptive pure exploration bandit algorithms, such that actions with larger gaps should be explored less. Second, it should adapt the observational data from causal bandit feedback, such that actions with enough observations already do not need further interventional rounds for exploration, similar to existing causal bandit algorithms. We are able to integrate both types of adaptivity into one algorithmic framework, and with interaction between the two aspects, we achieve better adaptivity than either of them alone.
First we introduce a particular term named gap-dependent observation threshold, which is a non- trivial gap-dependent extension for similar term in Lattimore et al. (2016). Then we provide two algorithms, one for the binary generalized linear model (BGLM) and one for the general model with hidden variables. The sample complexity of both algorithms contains the gap-dependent observation threshold that we introduced, which shows significant improvement comparing to the prior work. In particular, our algorithm for BGLM achieves a sample complexity polynomial to the graph size, while all prior algorithms for general graphs have exponential sample complexity: and our algorithm for general graphs match a lower bound we prove in the paper. To our best knowledge, our paper is the first work considering a CPF algorithm specifically designed for BGLM, and the first work considering CPE on graphs with hidden variables, while all prior studics either assume no hidden variables or assume knowing distribution P(P) a) for the parents of reward variable PY(Y) and all action a, which is not a reasonable assumption.
To summarize, our contribution is propose the first set of CPE algorithms causal graphs with hidden variables and fully adaptive to both the reward gaps and the observational causal data. The algorithm on BGLM is the first to achieve gap-dependent sample complexity polynomial to the graph size, while the algorithm for general graphs improves significantly on sample complexity and matches lower bound. Due to the space constraint, further materials including experimental results, an algorithm for the fixed-budget setting, and all proofs are moved to the appendix.
Related Work. Causal bandit is proposed by Lattimore et al. (2016), who discuss the simple regret for parallel graphs and general graphs with known probability distributions P(Pa(Y) a). Nair et al. (2021) extend algorithms on parallel graphs to graphs without back-door paths. and Maiti al. (2021) extend the results to the general graphs. All of them either regard P PY) Q) as prior knowledge, or consider only atomic intervention. The study by Yabe et al. (2018) is the only one considering the general graphs with combinatorial action set, but their algorithm cannot work on causal graphs with hidden variables. All the above pure exploration studies consider simple regret criteria that is not gap-dependent. Cumulative regret is considered in (Lu et al., 2020; Nair et al., 2021; Maiti et al., 2021). To our best knowledge, Sen et al. (2017) is the only one discussing gap-dependent bound for pure exploration of causal bandits for the fixed- fixed-budget setting, but it only considers the soft interventions (changing conditional distribution P(X) P Pa(X)) on one single node, which is different from causal bandits defined in Lattimore al. (2016).
Pure exploration of multi-armed bandit has been extensively studied in the fixed-confidence or fixed- budget setting (Audibert et al., 2010; Kalyanakrishnan et al., 2012; Jamieson al., 2013; Jamieson & Nowak, 2014). PAC pure exploration is a generalized setting aiming to find the e-optimal arm instead of exactly optimal arm (Even-Dar et al., 2002; Mannor & Tsitsiklis, 2004). In this paper, we utilize the adaptive LUCB algorithm in (Kalyanakrishnan et al., 2012). CPE has also been studied for multi-armed bandits and linear bandits, etc. (Karnin et al. (2013b): Chen et al. (2014); Du et al. (2021)), but the feedback model in these studies either have feedback at the base arm level or have full or partial bandit feedback, which are all different from the causal bandit feedback.
2

---

Published as a conference paper at ICLR 2023
The binary generalized linear model (BGLM) is studied in (Li al., 2017: Feng & Chen, 2022) for cunulative regret MAB problems. We borrow the maximum likelihood estimation method and its result in (Li et al., 2017: Feng & Chen, 2022) for our BGLM part, but its integration with our adaptive sampling algorithm for the pure exploration setting is new.
2 MODEL AND PRELIMINARIES
Causal Models. From Pearl (2009), a causal graph G (X UUU E)) is a directed acyelic graph (DAG) with a set of observed random variables X [Y} and a set of hidden random variables U. where = {XI,... ..)) U = {UI,... ]Uk] are two set of variables and Y is the special reward variable without outgoing edges. In this paper, for simplicity, we only consider that X, 's and Y are binary random variables with support {0. 1). For any node V in G, we denote the set of its parents in G' as (V)).. The set of values for (X(X) ) is denoted by pa(X). The causal influence is represented by P(V) Pa(()), modeling the fact that the probability distribution of a node V's value is determined by the value of its parents. Henceforth, when we refer causal graph, we mean both its graph structure (X U {Y) SUUUUUU U, E3) and its causal inference distributions
P(V) Pa)))) E) E) is a special class of causal graphs Y..... Xn + Y}. An intervention do S s) in the causal graph G means that we set the values of a set of nodes S S X to s, while other nodes still follow the P(V PV(V)) distributions. An atomic intervention means that |S| 1.
for all V E X (Y) U. A parallel graph G = (X (Y,,
with X = [X1,
}. U = 0 and E = {X1 Y, -
When 0, do(S 8) the null intervention denoted as do(), which means we do not set any node to any value and just observe all nodes' values.
In this paper, we also study a parameterized model with no hidden variables: the binary generalized linear model (BGLM). Specifically, in BGLM, we have U 0, and P(X 1 Pa(X) pa (0x px)) + ex. where fx is strictly increasing function, 0x E Pa()) is the unknown parameter vector for X, ex is a zero-mean bounded noise variable that guarantees the resulting probability to be within [0, 1]. To represent the intrinsic randomness of node X not caused by its parents, we denote X1 = as a global variable, which is a parent of all nodes.
Combinatorial Pure Exploration of Causal Bandits. Combinatorial pure exploration (CPE) of causal bandits describes the following setting and the online learning task. The causal graph structure is known but the distributions P[V) (V())) are unknown. The action (arm) space A is subset of possible interventions on combinatorial sets of variables, plus the null intervention, that is, A C (So = s) | S C X, s E N4a E do s)] to be the expected reward of action do(S s). Let μ²" max A Ma-
[0.1)1s1} and {do()) E A. For action a = do(S = s), define
In each round t. the learning agent plays one action a E A, observes the sample values X, X .x,.) and Y, of all observed variables. The goal of the agent is to interact with the causal model with as small number of rounds as possible to find an action with the maximum expected reward μ². More precisely, we mainly focus on the following PAC pure exploration with the gap-dependent bound in the fixed-confidence setting. In this setting, we are given a confidence parameter ó E (0, 1) and an error parameter [0, 1), and we want to adaptively play actions over rounds based on past observations, terminate at certain round and output an action a" to guarantee that μ Ma S E with probability at least 1-& 5. The metric for this setting sample complexity. which is the number of rounds needed to output proper action a". Note that when O, the PAC setting is reduced to the classical pure exploration setting. We also consider the fixed budget setting in the appendix, where given exploration round budget T and an error parameter E [0, 1). the agent is trying to adaptively play actions and output an action a at the end of round T, so that the error probability Pr[Mu μ² - ) is as small possible.
We study the gap-dependent bounds, meaning that the performance measure is related to the reward gap between the optimal and suboptimal actions, as defined below. Let a" be one of the optimal arms. For each arm a, we define the gap of a as
{
Pa max A ((a')
a = a* a + a.
Aa =
Pa. - Pa:
We further sort the gaps A 's for all arms and assume (1) & A ... S AlA)), where A (1) is also denoted as Amin-
3

---

Published as a conference paper at ICLR 2023
3 GAP-DEPENDENT OBSERVATION THRESHOLD
In this section, we introduce the key concept of gap-dependent observation threshold, which is instrumental to the fix-confidence algorithms in the next two sections. Intuitively, it describes for any action a whether we can derive its reward from pure observations of the causal model.
We assume that X,'s are binary random variables. First, we describe terms 4a E [0, 1] for each action a E A, which can have different definitions in different settings. Intuitively, how easily the action is to be estimated by observation. For example, in Lattimore et al. (2016),
represents
for parallel graph with action set A {do(X; x) 1 S i S n, E (0, 1)] action do X; x), Qu P(X; x) represents the probability for action do(X: x) to be observed, since in parallel graph we have P(Y X; z) P(Y do(X; = x)). Thus, when easier estimate P(Y do(X, x)) by observation. We will qa = P(X; x) is larger,
}} U {do(), for
instantiate qa s for BGLM and general graphs in later sections. For a = do(), we always set qu 1.
Then, for set qa a E A we define the observation thershold follows:
Definition 1 (Observation threshold Lattimore et al. (2016)). For given causal graph G and its associated {4o a E A}, the observation threshold is defined as:
m min ( E [|A|] 1a A 9a < 1/)
(2)
The observation threshold can be equivalently defined as follows: When we sort {qu a E A} as g(1) < g(2) S ... I q/A|, m = min(r g(++1) 2 }}. Note that m I |A| always holds since (do() = 1. In some cases, << ||]. For example, in parallel graph, when P(X, = P(X, 0) = for all Intuitively, when we collect passive observation data without intervention, arms corresponding to (()) with j S m are under observed while arms corresponding to -00) with j > m are sufficiently observed and can be estimated accurately. Thus, for convenience we name m as the observation threshold (the term is not given a name in Lattimore et al. (2016)).
[n]. (do(X.=1) Odo(X;=0) 1.2 Ido() 1.Then m. 2 < 2n + |A|.
In this paper, we improve the definition of make it gap-dependent, which would lead to better adaptive pure exploration algorithm and sample complexity bound. Before introducing the definition, we first define the term H,, Sort the arm as qa, A S qa2 max A e/2]² <
I Aa|Ai max (A e/223 then H, is defined by
H
33)
e/2}2'
Definition (Gap-dependent observation threshold). For given causal graph G and its associated qa 's and Ag 's, the gap-dependent observation threshold me,s is defined as:
{
m A min E [|A]]: a A qa max [An5e/2]
ST
(4)
H
The Gap-dependent observation threshold can be regarded as a generalization of the observation threshold. Intuitively, when considering the gaps, qa max e/2) represents how easily the action a would to be distinguished from the optimal arm. To show the relationship between m.,A and m. we provide the following lemma. The proof of Lemma is in the supplementary material.
Lemma 1. & - 2m.
Lemma 1 shows that m,,s (m). In many real scenarios, m,,4 might be much smaller than m. Consider some integer n with 4
A 1/n, Ga for E AA {do()) and qdo() 1. Then m n. Now we consider A.; Aaz J, while other arms have A. 1. Then H, 2 n² for all r 2 Then for a e a1 02 we have Qa max
An. H.* which implies that M 2. This lemma will be used to show that our result improves previous causal bandit algorithm in Lattimore et al. (2016).
4 COMBINATORIAL PURE EXPLORATION FOR BGLM
In this section, we discuss the pure exploration for BGLM, a general class causal graphs with linear number of parameters, as defined in Section 2. In this section, assume U 0. Let
4

---

Published as a conference paper at ICLR 2023
0- = =(xx) e xexurr be the vector of all weights. Since X1 is global variable, we only need to consider the action set A _ {do(S s) C X {X1}, E {00, (0.1). Following Li al. (2017); Feng & Chen (2022), we have three assumptions:
Assumption 1. For any X X (Y), fx is twice differentiable. Its first and second order derivatives can be upper bounded by constant ( and (
Assumption 2. == inf (Ex e 0-0x1151 fx(v- 0) > is positive constant.
Assumption 3. There exists constant 1) 0 such that for any X E X (UUY) and X' E Pa(X), for any E {0, 1 ()(Pa(X)-2) and x E {0, 1, we have
Pr[x'= = x Pa(X) \ x1) = = 21
(5)
Assumptions and 2 are the classical assumptions in generalized linear model Li et al. (2017).
Assumption 3 makes sure that each parent node of X has some freedom to become 0 and with a non-zero probability, even when the values of all other parents of X are fixed, and it is originally given in Feng & Chen (2022) with additional justifications. Henceforth, we use a0, a) to denote the reward Ma on parameter O.
Our main algorithm, Causal Combinatorial Pure Exploration- BGLM (CCPE-BGLM), is given in Algorithm 1. The algorithm follows the LUCB framework Kalyanakrishnan et al. (2012), but has several innovations. In each round f, we play three actions and thus it corresponds to three rounds in the general CPE model. In each round we maintain Hb., and j the estimates of jaa from the observational data and the interventional data, respectively. For each estimate, we maintain its confidence interval, a Lo.al and [L],,. U/,aa respectively.
At the beginning of round I, similar to LUCB, we find two candidate actions, one with the highest empirical mean so far, of 1 and one with the highest UCB among the rest, af If the LCB of dj higher than the UCB of af with an error, then the algorithm could stop and return of of-1 as the best action. However, the second stopping condition in line 5 is new, and it is used to guarantee that the observational estimates A6... are from enough samples. If the stopping condition is not met, we will do three steps. The first step is the novel observation step comparing to LUCB. In this step, we do the null intervention do(). collect observational data, use maximum-likelihown likelihood estimate adapted from Li et al. (2017); Feng & Chen (2022) to obtain parameter estimate Oz, and then use 0, to compute observational estimate ~O.0 = or (f,, a) for all action where (fe, a) means the reward for action a on parameter â.. This can be efficiently done by following the topological order of nodes in G and parameter 0.. From /6... we obtain the confidence interval [''.... U/,al using the bonus term defined later in (8). In the second step, we play the two candidate actions af and ai and update their interventional estimates and confidence intervals, as in LUCB. In the third step, we merge the two estimates together and set the final estimate أ be the mid point of the intersection of two confidence intervals. While the second step follows the LUCB, the first and the third step are new, and they are crucial for utilizing the observational data to obtain quick estimates for many actions at once.
Utilizing observational data has been explored in past causal bandit studies, but they separate the exploration from observations and the interventions into two stages (Lattimore et al., 2016; Nair et al., 2021), and thus their algorithms are not adaptive and cannot provide gap-dependent sample complexity bounds. Our algorithm innovation is in that we interleave the observation step and the intervention step naturally into the adaptive LUCB framework, so that we can achieve an adaptive balance between observation and intervention, achieving the best of both worlds.
To get the confidence bound for BGLM, we use the following lemma from Feng & Chen (2022):
Lemma 2. For an action a = d = s) and any two weight vectors O and 0', we have
|o(0, a) - 00'' a)l S Ee
1VI(0x-00xx0) XENs,
(6)
where Ns,y is the set of all nodes that lie on all possible paths from X1 to Y excluding S, Vx is the value vector of a sample of the parents of X according to parameter 0, M(!) is defined in Assumption 1, and the expectation is taken on the randomness of the noise term e = (ex)xexU()) of causal model under parameter O.
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 CCPE-BGLM(G, A, ()), (M)), ni n7.0)
1: Input:causal general graph G, action set A, parameter e, 6, M(), M(2), KK,7 c Assumptions
1,2, 3 and in Lemma 4 in supplementary material.
2: Initialize Mo.x = 1 for all node X. Na = 0, P2 = 0, La -0, Ua 0o for arms a E A.
3: for 1,2, 1,2. do
4: 0% 1-1
1-1 argmax ar Ma = arggaa Pa-l o
Ud-1
5: if U S - + e and 2 max eD
log at? ( - 3). (D² + log 3nd? 8
)} then
izz 8
"f
-1
6:
return
0/2
7:
end if
8:
1* Step 1. Conduct a passive observation and estimate from the observational data */
9:
Perform action do() and observe X, and Y,. For = do(), Na Na +
10:
8, = BGLLM-estimate( 1, (X,Y))). ".)....
11:
For do(S 8) E A, calculate Po.a. oi0,, S), and (L Ub.al lão,a (8, [1)] (t) is defined in Eq.(8) */
12:
1# Step 2. Do two interventions and estimate from the interventional data */
Perform actions a; and n f-1 get the reward y and Y!!))
13:
14:
Na. N No.-1 + - N₂ a +1
15:
For a E for ,0 1-1 dd()), update the empirical mean
Dr.a E/ N. (IIaa - a "y, +I{a +IKa- of 'y, +I{a do()));) and [ Uj,al lār. (N(N i1,a (r.)N) / (t) is defined in Eq.(8) */
17:
1 Step 3. Merge the observational estimate and the interventional estimate */
18: For a E A, calculate [L UN] 14o,,, Ub n [ Uf,al and pt
1. +U
2
end for
The key idea in the design and analysis of the algorithm divide the actions into two sets the easy actions and the hard actions. Intuitively, easy actions are the ones that can be easily estimated by observational data, while the hard actions require direction playing these actions to get accurate estimates. The quantity ya men- tioned in Section 3 indicates how easy is action a, and it determines the gap-dependent obser- vational threshold m..A (Definition 2), which essentially gives the number of hard actions. In fact, the set of actions in (4) with m..A the set of hard actions and the rest are easy actions. We need to define ja representing the hardness of estimation for each a.
Algorithm 2 BGLM-estimate
1: Input: data pairs
((X1, Y1), (X2, 12). .X,,,....,...... Y.))
2: Construct (V X,) for each X, where
Ve, is the value of parent of X at round f,
X, is the value of X at round t.
3: for X E X {Y
4: Mr.x = M + Ve.VV f,x, cal-
culate δ,x by solving Ei=((x
fx fx(V.xx0, Vxx =0
5: end for
6: return 0,.
(1) as follows. Let D maxxex((M) [Pa(X)]- For node For CCPE-BGLM, define its do S C X, let l |Nsy Then for do(S 8), we define
(L) = D
Intuitively, based on Lemma 2 and fs = |Ns.y large (s means that the right-hand side of Inequality (6) could be large, and thus it is difficult to estimate μaa accurately. Hence the term (L) represents how easy it is to estimate for action a. Note that qe only depends on the graph structure (L) and set S. We can define (1.) and m with respect to qo (1) by Definitions I and 2. We use two confidence radius terms as follows, one from the estimate of the observational data, and the other from the estimate of the interventional data.
(1) a) D1.
3nt2
1
A log (2t)
(L) log
Br(() = =arv log
(8)
K
8
5

---

Published as a conference paper at ICLR 2023
Parameters ao and ai exploration parameters for our algorithm. For theoretical guarantee, we choose ao 6v2 and oz = 2, but more aggressive oo and 0 could be used in experiments. (e.g. Mason et al. (2020), Kaufmann et al. (2016), Jamieson et al. (2013)) The sample complexity of CCPE-BGLM is summarized in the following theorem.
Theorem 1. With probability - 6, our CCPE-BGLM E,E, 6/2) returns an E-optimal arm with sample complexity
|
m
T=
H m.
(2)
log
(9)
(L) H (. are defined Definition and (3.(3) in terms of qu ( 's for a E A (do() where m
defined in E7)
If treat the problem as a naive |Al-arms bandit, the sample complexity of LUCBI is Ö(H) o(En mmx (mx((_..e/3p))) ), which may contain an exponential number of terms. Now note that qa (2) 2
it is easy to show that (L) 2n Hence H mm contains only a polynomial number of terms.
Other causal bandit algorithms also suffer an exponential term, unless they rely strong and unreasonable assumption as describe in the related work. We achieve an exponential speedup by (a) specifically designed algorithm for the BGLM model, and (b) interleaving observation and intervention and making the algorithm fully adaptive.
The idea of the analysis is follows. First, for the me.A hard actions, rely the adaptive LUCB to identify the best, and its sample complexity according to LUCB is O(H m2 log([ (| m /6)).
Next, for easy actions, we rely on the observational data to provide accurate estimates. According to (4), every easy action has the property that qo max/ e e/2 > 1/ a/...... Using this property together with Lemma 2, we would show that the sample complexity for estimating casy action rewards is also O(H m... log(IA] H m (L) /5)). Finally, the interleaving of observations and (z)
interventions keep the samply complexity in the same order.
5
COMBINATORIAL PURE EXPLORATION FOR GENERAL GRAPHS
5.1 CPE ALGORITHM FOR GENERAL GRAPHS
In this section, we apply a similar idea to the general graph setting, which further allows the existence of hidden variables. The first issue is how to estimate the causal effect (or the do effect) E[Y dS s)] in general causal graphs from the observational data. The general concept of identifiability (Pearl, 2009) is difficult for sample complexity analysis. Here we use the concept of admissible sequence (Pearl, 2009) achieve this estimation.
Definition 3 (Admissible sequence). An admissible sequence for general graph G with respect to Y and S (X1, Xx) S X a sequence of sets of variables Zz, Z S X such that
(I) Z; consists of nondescendants of Xit1. (Kk,
(2) (Y IL Xx X1,... .X-1, Zi.... (.....ZZ,),,, x..1 N2 where Gx means graph G without out-edges of X, and G means graph G without in-edges of X.
Zz)Gx
Then, for S (",,-.. "K,,...,,0. .xk.. (-1,-.. ,,,,,
,Ik). we can calculate E do(S 8)] by
B|y do =]]] Σ P(Y =1
Z, 21, i < k)
P(Z =11 P 2 z Z: 2, X; = 21, 1 < k: - 1),
(10)
where z means the value of U Z,, and z; means the projection of on Z₁. For a do
s)
with S k we use ( k= to denote the admissible sequence with respect Y and S and
Zn = - Z. Z, Zaa and Z max, Z,. In this paper, simplify Za Z, if there is no ambiguity.
For any P C X, denote P. X,Ip the projection of X, P. We define
7

---

Published as a conference paper at ICLR 2023
Algorithm 3 CCPE- GCnE--Gee,,, A, E,
1: Input:causal graph G, action set A, parameter E, 6, admissible sequence [Z.)) for each action
A
2: Initialize f 1. Ta 0, 0, = 0, Pa = 0 for all arms E A, = [0,1),, [|]]]
3: for 1, .......... ddo
4: "h 1--1
argmax 10-1 a7 _aa-1= argmax ae (U-
5: if U S 1 then
--1
6: return
7: end if
8: / Step I. Conduct a passive observation and estimate from the observational data */
9: Perform do() operation and observe X₁ and Y,. For do(), No Na +1.
for do(S = E A A {do()} with an admissible sequence and 5 (X1,... [X s
(I .i do
11:
Estimate po.a using (14) and [T...:: is defined in (16), Ta, is defined in (11( and Ta ming Ta,x */
a _g oão a - - 1), Mo + (T)(TT)) (1)
12:
end for
13:
/" Step 2. Do two interventions and estimate from the interventional data */
Perform actions of and 0/ / get the reward y-(1) and y-(h)
15:
No.1 = N No.1 + N 6 N -
16:
For a E {at-- 2/h 1-1 do()), update the empirical mean jı as Line 16 in Algorithm 1.
Update [Ly Ui.al= 11.a=11 - (r(N)), PIaa + Br(NN.), (y((t) defined in Eq. */
18: 1st Step 3. Merge the observational estimate and the interventional estimate */
19: For a E A, calculate
[4 Ui] 1L 1, 1 [LL Uf,al and po.
12 +0
2
20:
end for
Ta. = Σ 11s = -, (Z.), = To,x)) 1
Ta. Σ - (, = xtY,
(11)
(t)) Σ I!(Z)), (X.), =1, 11-11
(12)
f-1
(t) (t))
Σ (((z)), = z1, (Z.), = 2i (Xi)s = 2,, i 51-1)
(13)
where the (t) and (t) are the empirical mean of P(Y | S== Z. = and P(Z 2
Z, = 2;, X; = Fi, i I 1--11 1). Also, we denote T₃ = min, Ta.z- Using the above Eq.(10), we estimate each term of the right- hand side for every z E {0. 1) %. to obtain an estimate for E q as follows:
oo. = Tr.z (t)
(14)
For general graphs, there is no efficient algorithm to determine the existence of the admissible sequence and extract it when it exists. But could rely several methods to find admissible sequences in some special cases. First, we can find the adjustment set, special case of admissible sequences. For causal graph G, Z is an adjustment
for variable Y and set S if and only Z = P(P = z). There is an efficient
P(Y = do(S = x) = Σ= P(Y = S algorithm for deciding the existence of minimal adjustment set with respect to any set S and Y and finding it (van der Zander et al., 2019). Second, for general graphs without hidden variables, the admissible sequence can be easily found by Z, = Pa(X) (Z1 U... Z U X1 ... XX-1) (Theorem 4 in the Appendix). Finally, when the causal graph satisfies certain properties, there exist algorithms to decide and construct admissible sequences Dawid & Didelez (2010).
Algorithm 3 provides the pseudocode of our algorithm CCPE-Genera which has the same framework as Algorithm 1. The main difference is in the first step of updating observational estimates, which rely the do-caleulus formula (10).
8

---

Published as a conference paper at ICLR 2023
(G) meaning that it is For action do(S 8) without admissible sequence, define qa hard to be estimated through observation. Otherwise, define Ya as:
min( where qe P(S 8, Z 2), Vz {0, 1] 13
(15)
Similar to SCPE-BGLME for do(S 8) with |S| = k, we use observational and interventional confidence radius as:
20k A To To (2g(2)) :B,(t) = as log
A log(
(8 t) = 20
log
(16)
n
5
where do and 02 are exploration parameters, and la -22", For theoretical guarantee, we will choose ao =8 and az = 2. Our sample complexity result is given below.
Theorem 2. With probability - 8, CCPE-General(C. A, E, 5/5) returns an e-optimal arm with sample complexity
|
(G) m
==
H
(o) log
(17)
where m,
H are defined in Definitions 2 and 3 in terms of (0) defined in (15). m.
Comparing to LUCBI, since m. < |A], our algorithm is always as good as LUCBI. It is easy to construct cases where our algorithm would perform significantly better than LUCB1. Comparing other causal bandit algorithms,
algorithm also performs significantly better, especially when m < m(C) or the gap A₂ is large relative to E. Some causal graphs with candidate action sets and valid admissible sequence are provided in the Appendix A, and more discussion in the Appendix.
5.2 LOWER BOUND FOR THE GENERAL GRAPH CASE
To show that our CCPE- GePEral algorithm is nearly minimax optimal, we provide the following lower bound, which is based on parallel graphs. We consider the following class of parallel bandit instance with causal graph G (1X1,
Xn, Y), " F): the action set is A (do(X; x) x E (0,
i S n] U {do(). The ga this case is reduced to (G)
[do(X:=2) P(X, = x) and 9dol) = 1. Sort the (G)
(G) action set Yai -max A 8 2/22² < Gas -max Aagz ag 8/2)² < ... S (uzn=1 -max Aaz. 11: e e/2]2. Let Pmin = min [0.1]" P(Y = 1 X x). Pmax = max P(Y = X = x). Let Pmax + 2 + 25 S 0.9, Pmin + Amin 0.1.
(G)
Theorem 3. For the parallel bandit instance class & defined above, any (E. 6 algorithm has expected sample complexity least
(c) max Day; e/2]2 max (200) log )
Ω
H (o)_ min
(18)
Theorem 3 the first gap-dependent lower bound for causal bandits, which needs brand-new construction and technique. Comparing to the upper bound Theorem the main factor H (G)
the same, except that the lower bound subtracts several additive terms. The first term Hm... almost equal to Hm.,a appearing in Eq.(17), except the it omits the last and the smallest additive term Hm.... The second term eliminate one term with minimal A.,, which common in multi-armed bandit. (Lattimore (2018), (2018),amm) Karnin et al. (2013a)) The last term is because do()'s 's reward must be in-between =d)(X.=0) and Pdo(X.=1) and thus cannot be the optimal arm.
FUTURE WORK
There are many interesting directions worth exploring in the future. First, how to improve the computational complexity for CPE of causal bandits is an important direction. Second, one can consider developing efficient pure exploration algorithms for causal graphs with partially unknown graph structures. Lastly, identifying the best intervention may be connected with the markov decision process and studying their interactions is also interesting direction.

---

Published as a conference paper at ICLR 2023
REFERENCES
Jean-Y Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Adam Tauman Kalai and Mehryar Mohri (eds.), COLT 2010 The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pp. 41-53. Omnipress, 2010.
Shouyuan Chen, Tian Lin, Irwin King, Michael Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. In Proceedings of the 27th International Conference on Neural Information Processing Systems- Volume 1, NIPS 14, pp. 379-387, Cambridge, MA, USA, 2014. MIT Press.
Alexander Dawid and Vanessa Didelez. Identifying the consequences of dynamic treatment strategies: A tecision- overview. Statistics Surveys, 4, 10 2010. do10.1211/10-- 1214/10-$S081.
Yihan Du, Yuko Kuroki, and Wei Chen. Combinatorial pure exploration with full- dull-bandit or partial linear feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 35:7262-72777 05 2021. do10. 1e210.16090 16099699iii.... v35i8. 1682..
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and markov decision processes. Jyrki Kivinen and Robert Sloan (eds.), Computational Learning Theory, 15th Annual Conference Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings, volume 2375 of Lecture Notes in Computer Science, pp. 255-270. Springer, 2002. do10. 111110073---4444555--1111
Shi Feng and Wei Chen. Combinatorial Causal Bandits. arXiv e-prints, art. arXiv:2206.01995, June 2022.
Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits the fixed confidence setting. In 2014 48th Anmual Conference on Information Sciences and Systems (CISS), pp. 1-6, 2014. do10. 109/CISS.2014 689409..
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil' ucb An optimal exploration algorithm for multi-armed bandits. Journal of Machine Learning Research, 35, 12 2013.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic aalti-armeddde bandits. Proceedings of the 29th International Conference on Machine Learning, ICML 2012, 1, 01 2012.
Zohar Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. 30th International Conference Machine Learning, ICML 2013, pp. 2275-2283, 01 2013a.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on International Conference on Machine Learning Volume 28, ICML' 13, pp. III-1238 111-1246. JMLR.org, 2013b.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: learning good interventions via
causal inference. In Advances in Neural Information Processing Systems, pp. 1189-1197, 2016.
T. Lattimore. Refining the confidence level for optimistic bandit strategies. Journal of Machine Learning Research, 19:1-32, 07 2018.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit prob- lems with causal background knowledge. In Conference on Uncertainty in Artificial Intelligence, pp. 141-150. PMLR, 2020.
Aurghya Maiti, Vineet Nair, and Gaurav Sinha. Causal bandits on general graphs. arXiv preprint arXiv:2107.02272. 2021.
10

---

Published as a conference paper at ICLR 2023
Shie Mannor and John N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5:623 648, dec 2004. ISSN 1532-4435.
Blake Mason, Lalit Jain, Ardhendu Tripathy, and Robert Nowak. Finding all -good arms in
stochastic bandits. Advances in Neural Information Processing Systems, 33:20707-2077 2020.
Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits. In International Conference on Artificial Intelligence and Statisties, pp. 2017-2025. PMLR, 2021.
Judea Pearl. Causality. Cambridge University Press, 2009. 2nd Edition.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
Rajat Sen, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Identifying best interventions through online importance sampling. International Conference on Machine Learning, pp. 3057-3066. PMLR, 2017.
Benito van der Zander, Maciej Liskiewicz, and Johannes Textor. Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework. Artificial Intelligence, 270:1-40, 2019.
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, pp. 5512-5520. PMLR, 2018.


Reviews:
[{"review_id": "jTyE6St8TE4", "reviewer": "Reviewer_okVv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors extend Lattimore 2016 to obtain a gap-dependent bound (not regret since they operate in the pure exploration setting) bandit for parallel bandit graph, and also extend it to arbitrary graphs, so long as there is an admissable set. For example, if there is a valid back-door adjustment for the actions. ", "summary_of_the_review": "Thank you for your submission. I did enjoy reading it. I have a few comments/questions below.\n\nWhy are the weights in the network always non-negative? Isn't it to very strong assumption that the algorithm always knows that setting values to 1s are the only possible optimal interventions?\n\nThe paper borrows several assumption and even lemmas from Feng & Chen (2022). But this is an unpublished manuscript on arxiv. Specifically for the borrowed lemmas, it would be good to have proofs of them self contained in this submission. I couldn't find these proofs are given in the Appendix either. \n\nSome intuition about the definition of Gap-dependent observation thershold would be nice to have, similar to the baseline m value borrowed from Lattimore.  \n\nPlease add some causal graphs with candidate action sets for which admissable sequences or adjustment sets exist with latent confounders. ", "strength_and_weaknesses": "They propose a solution to a very special case of a very hard problem. I think the results are still interesting. \n\nThe linear setting is a bit restrictive especially when combined with the assumption that all parameters are nonnegative (can this assumption be removed?)\n\nThe general graph case is a bit rushed. For example, how often do we have that all candidate actions have valid admissable sets? What if only some of them do? The algorithm should have been robust to this. Is there a way to incorporate this? Also it would be good to draw some graphs where the assumptions hold. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "a56d6GswzP", "reviewer": "Reviewer_jo8z", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "-Proposes gap-dependent bounds on adaptive pure exploration algorithms. \n\n-Algorithms do not require prior knowledge of causal inference distributions. \n\n-Allows combinatorial interventions.\n\n-Applicable to causal graphs with hidden variables. \n\n-Studies sample complexity in both fixed confidence and fixed budget settings. \n\n-Proposes the gap-dependent observation threshold as an intuitive measure of problem difficulty. \n\n-Proposes adaptive algorithms that interleave observation and intervention for efficient sample learning of optimal interventions.\n", "summary_of_the_review": "A good paper that addresses several important issues in the combinatorial pure exploration of casual bandits with solid theoretical results.", "strength_and_weaknesses": "-Analyses pure exploration of combinatorial casual bandits in a general setting. Extends the results of prior works to general graphs with the possibility of unobserved variables. \n\n-Provides gap-dependent bounds on the sample complexity for the binary generalized linear model (BGLM). Unlike prior works, whose complexity grows exponentially, for BGLM, their sample complexity scales only polynomially in the graph size. Full adaptivity of the algorithm by interleaving exploration and exploitation is a key contributor to this improvement. \n\n-Provides an analysis of the general case where hidden variables exist. \n\n-Shows a lower bound for parallel graphs, establishing the near minimax optimality of the combinatorial casual pure exploration algorithm.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GBWoFGpUp8", "reviewer": "Reviewer_SLrk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the problem of causal bandits with (arbitrary) combinatorial action spaces in both fixed-confidence and fixed-budget pure exploration (simple regret) settings.  The causal graph is assumed to be known and all variables are binary valued.  The authors consider two cases.  For the first, the causal model is parameterized, with which parameters for most actions can be estimated from observational data and the rest are estimated using interventions.  The algorithm is based on the LUCB algorithm.  For the second (more general) case, the causal model is not parameterized and hidden nodes are available; the proposed algorithm overall has a similar structure as in the first case.   The authors also show that the sample complexity of the latter algorithm is nearly minimax optimal.", "summary_of_the_review": "Overall I think the submission is good.  The topic, at the intersection of causal inference and multi-armed bandits can be of interest to multiple communities.  The authors adapt the LUCB algorithm in an interesting way for the causal bandit problem.  I have concerns that the storage and per-round computational complexity of the algorithm may render the algorithm primarily of theoretical interest, but nonetheless think the submission is good.", "strength_and_weaknesses": "### Major strengths\n\n1. The authors showed that for a particular parametric class of models (BGLM with bounded derivatives), since the difficulty of estimating the conditional mean of Y can be characterized by graph properties in such a way that actions can be separated into “easy” and “hard” actions, an LUCB style algorithm can be employed that significantly improves the sample complexity.\n\n2. The authors also generalize that strategy for the more general case with hidden nodes and for which the conditional distributions are not parameterized, and show the sample complexity of that algorithm is nearly minimax optimal.\n\n### Minor strengths\n\n1. The authors propose a fixed-budget pure exploration algorithm and analyze its regret (in supplementary material).\n\n2. The authors include some toy experiments for their methods (in supplementary material).  \n\n### Major weaknesses\n1. The storage and per-round computational complexities can be exponential in $n$ even for parameterized setting with the BGLM model.  Separate statistics are maintained for each action (eg Alg. 1 line 2) and updated (eg Alg. 1 line 11).  The action set is allowed to be an arbitrary subset of the powerset of $X$.  \n\n### Minor weaknesses\n1. The assumptions for the BGLM model used are quite strong – $\\theta$ parameters are non-negative, $f_X$ monotone, so that for any subset of nodes, it is immediate that the best intervention is to set all variables in that subset to value of 1.  Even for the slightly more general BGLM model without the same restrictions on \\theta or $f_X$ (but with bounded derivatives), it seems non-trivial to modify Algorithm 1 short of treating each realization as a separate action, growing the action set (and consequently storage complexity and per-round computational complexities) exponentially.  \n\n2. The readability could be improved by modifying notation or adding more verbal descriptors reminding the reader what notations refer to, especially those used sparingly -- eg $P_{S,Y}$ used to specify nodes along paths but P already used for probabilities; \\sigma introduced on page 5 for expected values and used once in Lemma 2 but already have \\mu notation for that.  The pseudocode of Alg 1 and 3 are heavy with notation and equations – the precise formulas could be discussed in the main text and referenced (or simplified).\n\n3. The storage and per-round computational complexities of the methods were not formally discussed in the main sections.\n\n\n\n### Questions \n1. Pg 3 Can you clarify what the sentence “To represent the native probability, …” means\n\n2. Pg 3 Can you clarify why in the BLGM model the probability mass functions are random?  The X’s would be random even without the $e_X$ term.  More concerning to me is that you have an additive random term, but you are assuming that the sum is constrained in [0,1] to be a valid probability mass.  To me at least, that seems to induce a strange constraint of f_X and $e_X$ since if the terms are independent, then both need to be bounded.  If $e_X$ is bounded, then it is sub-Gaussian.\n\n3. Pg 4 “We assume that Xi’s are Bernoulli random variables when we do not intervene any variables” – What does that assumption mean?  They would have marginal Bernoulli distributions since they are binary valued, but they would have joint dependence.  \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster