Approximate Allocation Matching for Structural Causal Bandits with Unobserved Confounders
Authors: Lai Wei
Muhammad Qasim Elahi
Mahsa Ghasemi
Murat Kocaoglu
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-armed bandits
causal Inference
sequential decision-making

Abstract: Structural causal bandit provides a framework for online decision-making problems when causal information is available. It models the stochastic environment with a structural causal model (SCM) that governs the causal relations between random variables. In each round, an agent applies an intervention (or no intervention) by setting certain variables to some constants and receives a stochastic reward from a non-manipulable variable. Though the causal structure is given, the observational and interventional distributions of these random variables are unknown beforehand, and they can only be learned through interactions with the environment. Therefore, to maximize the expected cumulative reward, it is critical to balance the explore-versus-exploit tradeoff. We assume each random variable takes a finite number of distinct values, and consider a semi-Markovian setting, where random variables are affected by unobserved confounders. Using the canonical SCM formulation to discretize the domains of unobserved variables, we efficiently integrate samples to reduce model uncertainty. This gives the decision maker a natural advantage over those in a classical multi-armed bandit setup. We provide a logarithmic asymptotic regret lower bound for the structural causal bandit problem. Inspired by the lower bound, we design an algorithm that can utilize the causal structure to accelerate the learning process and take informative and rewarding interventions. We establish that our algorithm achieves a logarithmic regret and demonstrate that it outperforms the existing methods via simulations.

Approximate Allocation Matching for Structural Causal Bandits with Unobserved Confounders
Lai Wei Life Sciences Institute University of Michigan weilatim@gmail. com
Muhammad Qasim Elahi
Electrical and Computer Engineering
Purdue University el elah alpurdue edu
Mahsa Ghasemi
Murat Kocaoglu
Electrical and Computer Engineering Purdue University mahsa@purdue. edu
Electrical and Computer Engineering
Purdue University
mbcocaollu@purdue. edu
Abstract
Structural causal bandit provides a framework for decision-making problems when causal information is available. It models the stochastic environment with struc- tural causal model (SCM) that governs the causal relations between random vari- ables. In each round, agent applies setting certain variables to some constants, and receives a stochastic reward from a non mon-manipulable variable. Though the causal structure is given, the observational and interventional distributions these random variables are unknown beforehand, and they can only be learned through interactions with the environment. Therefore, to maximize the expected cumulative reward, it is critical to balance the exploration- versus-exploitation tradeoff. We consider discrete random variables with finite domain and semi-Markovian setting, where random variables are affected by unobserved confounders. Using the canonical SCM formulation discretize the domains of unobserved variables, we efficiently integrate samples to reduce model uncertainty, gaining an advantage over those classical multi-armes bandit setup. We provide logarithmic asymptotic regret lower bound for the structural causal bandit problem. Inspired by the lower bound, we design an algorithm that can utilize the causal structure to accelerate the learning process and take informative and rewarding interventions. We establish that our algorithm achieves a logarithmic regret and demonstrate that it outperforms the existing methods via simulations.
intervention (or intervention) by
Introduction
Sequential pocciiinn-making.. in uncertain environments is one the most fundamental problems across scientific disciplines, including robotics, economics, social science, clinical trials, and agriculture [32]
26 36. 7 3. In almost all these applications, is required implement interventions to control some aspects of the system to optimize an outcome of interest. In economics and political science, the government could use fiscal policy including changing the interest rate and taxation achieve regulation and control of a country's 's economy. In this paper, we deal with designing an adaptive policy an uncertain stochastic environment to learn and apply optimal interventions.
In sequential decision-making problems, it critical to balance the explore-versus-explo tradeoff, which deals with choosing between informative options and empirically more rewarding alternative options. The multi-armed bandit (MAB) (33 30 [8] is a classical problem formulation for achieving such a tradeoff. In MAB, decision-maker sequentially chooses action corresponding pulling
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

an arm from a set of arms, each generating stochastic rewards with probability distribution unknown to the decision-make maker. The objective is to achieve the maximum cumulative reward over a time horizon, or equivalently to minimize the regret, which measures suboptimality in cumulative rewards against selecting the best action all the time. The classic stochastic bandit formulation only considers the connection between an action and its expected reward. However, in real-world applications, an action can affect the entire system in a more complex way, As the agricultural example given in [19], changing the moisture level could affect the lemperature and nutrient absorption, which are also crucial to crop yields. The relations between such factors cannot be characterized by the MAB.
Causal knowledge enables us to model the causal relations between multiple factors in the envi- ronment. In machine learning research, it has been noted that causal models could help improve the generalization performance when data distribution shifts [. and address unstable translation of successful reinforcement learning methods in simulation to real-world problems [2] such as self-driving cars and recommendation systems. The casual bandit models the stochastic environment with a causal graph that connects a set of random variables of interest, and actions are modeled by interventions on different subsets of nodes. It provides a critical interpretation of causal influences among random variables (28) that allows us to reason about what will happen to the environment after certain interventions are made to the data-generating process. Compared to the classic MAB with only reward feedback, the casual bandit represents a more detailed model of real-world problems, including richer feedback from multiple random variables and the causal relations among them. By applying causal reasoning, the learning process can be accelerated and more rewarding interventions can be selected. In applications where the space of intervention is large and explicit experiments are costly, such as social science or economics, it has special value.
pecisiin-maaing
Due to the reasons mentioned above, there has been a recent surge of interest in the research community on causal decision-making. Some early attempts include (6), in which the authors took a causal approach to study how to make final decisions based on natural predilections, and proposed an algorithm by modifying Thompson sampling [3 In [19], the investigators started from parallel causal structure and extended the algorithm to the general causal bandit problem.
Subsequent work (37] took preprocessing steps to get rough estimates of interventional distributions and use them to design efficient experiments to discover the best intervention. In [.] the Bayesian optimization technique is employed to solve the same problem.
The most closely related works focusing on regret minimization in the structural causal bandit with confounders are 22 23) In both works, the authors took a graphical characterization using do-calculus (28) to reduce the large intervention set to the possibly optimal minimal intervention set and run a KL-UCB algorithm [14] within the reduced action space. The later work is an extension of the previous one that includes mon-maaipel variables. Other lines of causal bandit research normally assume additional prior information, such as infinite observational data (39] or marginal interventional distributions (24 8). A general linear model is adopted in [13). which is different from the non -araamemctiicc setup in this paper.
In this paper, we focus on the MAB sequential decision-making problem where the arms correspond to interventions on an arbitrary causal graph, including unobserved confounders affecting multiple pairs of variables (also known in causal terminology as the semi-Markovian setting). We recognize the structural causal bandit falls into the category of structured bandit [10 35). It has been noted the classical upper confidence bound (UCB) algorithm and Thompson sampling may not fully leverage structural information [1 (20). is worth considering the potential limitations of algorithms based on these ideas, such as CRM-AL (25) and generalized Thompson sampling [27). To address this issue
and make systematic use of a known causal structure, we design an algorithm that can meticulously utilize causal structural information. In particular, make the following contributions:
We provide a logarithmic asymptotic regret lower bound for the structural causal bandit problem with latent confounders by leveraging the canonical SCM formulation 40 to create a space of all possible interventional distributions given a causal graph.
Inspired by the lower bound, we extend [22 and apply approximate allocation matching to design an algorithm that can effectively utilize causal information provided by the causal graph to accelerate the learning process and take informative and rewarding interventions.
We analyze the algorithm to provide a problem-dependent logarithmic upper bound on expected regret and compare it with 22 to show it has better theoretical guarantee.

---

We complement the theoretical results by evaluating the proposed approach in variety of experimental settings featuring different causal structures. We show that our algorithm outperforms the existing baselines in terms of empirical regret.
2 Problem Statement and Background
In this section, we present the formulation of the structural causal bandit problem with latent confounders. We follow the convention to represent a random variable and its value a capital letter and lowercase letter respectively. A multivariate random variable is represented in a bold letter.
2.1 Structural Causal Model
Our approach adopts the structural causal model (SCM) (29] to provide a causal perspective on the data-generating process. This allows express the relationship between variables and capture important causal concepts, including unobserved variables, observational distributions, and interventional distributions. For a random variable X, let S(() denote its domain.
Definition (SCM), A structural causal model is 4-tuple (U, V, F, P(U)) where:
1. U is set of unobserved independent background variables (also called exogenous), that determine the randomness of the model.
2. [V; i == 1....,, is the set of observable variables (also called endogenous).
3. IF is set of structural equations J2, [... [n] such that for each V, E J:: Q(U;) x (2Pa,,) - (VV)) defines a mapping, where U, S U and Pa, C V is the parent set of V.
So F as a whole determines a mapping relationship from Q(U) to (VV).
4. P(U) is joint probability distribution over all the exogenous variables.
Each structural causal model is associated with a causal graph G (V, B), where the node set V corresponds to the set of observable variables, & is the set of directed edges and B is the set of bidirected edges. For each V, Pa,, there exists a directed edge in & such that V, + V₁ which indicates functional dependency from Vú to V. Without showing unobserved exogenous variable U explicitly, the confounding effects of U are represented using bidirected edges in B, which connect multiple pairs of observable variables in V. The presence of V; ++ Vú in G represents unmeasured factors (or confounders) that may influence both V, and Vj. In other words, fr and f, share common exogenous variables U, n U, A 0 as input. Let [S2(V) be the cardinality of (2(V).
Assumption 1. We assume each V E V can only take a finite number of values, i.e,, [S((V) is finite.
Within the causal graph, an intervention on subset of random variables S C V denoted by the do-operator do(S s) sets the structural equation for each S, E S to be S₁ 5j. We also refer to as intervention for brevity. If node V; & S. its structural equation remains to be V- = fuU,. Pa.). The empty intervention denoted by do) does not change the structural equation of any random variable, and the distribution of V is also called observational distribution. Let denote the indicator function. An SCM induces interventional distributions: if is consistent with intervention s,
P(v | do = =)) = Σ P(u)
II V.gs
1 = fl u.) = Pv(v).
u
Otherwise, P(v| do(S = =)) = 0. For a more detailed discussion on SCMs, we refer to 29
2.2 Causal Bandit Problem with Confounders
The causal bandit problem with confounders studies the sequential decision-makenn problem with causal information provided by causal graph G = (V, E, B) with confounding effects represented by bidirected edge set B. The causal graph g is given but the exact interventional and observational distributions are unknown. Without loss of generality, we assume the reward is collected from node Vn, which is bounded [0, 1] and can not be intervened on. Let I C (s E R(S) |S C VV Vn) be the space of allowed interventions. The decision-male is required to decide which intervention apply
3

---

at each time step. The expected reward of intervention E is EA, = E (v)). where Ps is defined in ① and Ep means the expectation is computed with probability distribution P.
At each time E {l...., T. the agent follows an adaptive allocation policy π to select an intervention s, E I and observe the causal bandit feedback V, ~ Pa (V), which is a realization of all observable variables after intervention. In fact, policy is a sequence { JeN, where each iT determines the probability distribution of taking intervention S, E I given intervention and observation history (S, $1 Vi...., S Vt-1). Let p., == maX M4 and A = p.. ii denote the optimal mean reward and the expected optimality gap of intervention do(S = s) respectively. Given causal graph G. the objective of the causal bandit problem to design policy π to maximize the expected cumulative reward, or equivalently, to minimize the expected regret:
T Σ
R2 = EE
(p. -
Vine)
Σ (s))(,)) SEI
(2)
where (s) is the total number of times intervention do(S = s) is taken by policy until time horizon till T, and the expectation is computed over different realizations of {S., V Ve) from the interactions between the random policy and the causal bandit model (Pa)=ET. Thus, 127 is the gap between the expected cumulative rewards of selecting the best intervention all the time and that by the policy æ. The regret decomposition in (2) is from [8]] and it expresses the expected regret with products of the expected number of suboptimal action selections and expected reward gaps.
The large action space in causal bandits poses many challenges to the learning problem. It is desirable to reduce the action space without excluding all optimal interventions. The do-calculus introduced in [28) provides a set of guidelines for evaluating invariances across interventions. In this context, our specific focus is on Rule 3, which provides the conditions under which series of interventions have no impact on the outcome variable. For example, Rule 3 implies that Pw z (v)) Pz(y) if we have (Y W Jwrz where Swuz is the subgraph of DAG G with incoming edges to the set W U Z removed. This concept leads to the notion of a minimal intervention set (MIS), which is subset of variables S C V \ Vn such that there is no S' C S for which [s[sr] = Ps holds for every Structural Causal Model (SCM) with a causal graph 9 122] Here, s(S" denotes an intervention on S' "S with values consistent with s. An MIS S is considered a possibly optimal MIS (POMIS) if some intervention s E II(S) can achieve the optimal mean reward in an SCM with a causal graph G. We define I = {s E ((S) S is POMIS).
At an intuitive level, may seem logical that the most effective course of action would be to intervene on the immediate causes (parents) of the reward variable Vn, This approach would provide a higher level of control over V22 within the system. If the reward variable V,, not confounded with any of its ancestors, its parent set Pa,, is the only POMIS. In more general causal graphs where V,, is confounded with any of its ancestors, the paper (2 proves that multiple POMISs exist, which can include variables that are not parents of Vn The paper also provides graphical criteria and an efficient algorithm for constructing a set of all POMISS for given causal graph. For an effective method to search for I, we refer to [22] and rely on their graphical criteria to construct a set of POMISs. This set of POMISs is used to form the set of possible optimal actions I for use in the causal bandit algorithm. We make the following assumption, which we expect to hold in a general scenario (38] except for certain specifically designed SCMs.
Assumption 2. Within interventions on POMISs, there exists a unique optimal intervention S..
3 Response Variables and Space of Interventional Distribution Tuples
The unspecified domain of U makes it inconvenient to be directly applied to the learning problem.
However, it is noted in [29] Ch. 8] that if each variable in V takes finite states, ((U)) can be partitioned and U can be projected to a collection of finite-state response variables. The resulting model is equivalent to the original one with respect to all observational and interventional distributions. Such technique was used to bound the causal and counterfactual effects with observational distribution 22 Ch. 8). We take it to define a parameterized space of interventional distribution tuples.

---

V1
V2
V1
M1
Vi
1/2
1/2
V3
M2
V3
M3
Mi
M2
V4
V4
M4
Vi
V/2
(a) Causal graph
(b) Structural equivalent of (a)
(c) Bow graph
Figure 1: Causal graphs and their structural equivalents
3.1 Response Variables and Canonical Structural Causal Model
In Definition | each structural equation V; = [U, Pa.) connects random variable V; to its parents Pa.. As U; varies along its domain, regardless how complex the variation is, the only effect can have is to switch the relationship between Pa, and V4. Since there are at most [S2(14) (P(Pa)) mapping relationships from Pa, V,, we can decompose as follows,
V = fl (U Pa;) = (M,, Par), M4 = J.(U).
(3)
where M, E {O..... [((V)) (R(Pa)) is random variable corresponds to mapping from 32(Pa;)
to 2(V).. For observable variable without parents, we simply have M; E {0..... [2(V)) - 1). Such random variable M, E M attached to each V; V is called response variable in (5). Treating response variables as exogenous variables, the resulting SCM (M, V, P(M)) is called canonical SCM in [40], where F = ff) f..... f..)
The decomposition of structural equations in equation 3 can be represented graphically by including response variables in M. Since V; f (M,, Pa:). for each Vú there is a directed edge M, + V, We also know that if there exists Vi <> V, in G. both V, and V, are affected by common exogenous variables U, O U, * 0. As result, M; and M, are correlated and they also connected by bidirected edge. For example, the causal graph in Fig. Ta) has a structural equivalent in Fig. Tb).
Given intervention s E I, there exists deterministic relationship from M to V. To further explain the idea, consider the bow graph example in Fig. [c). where V1, 1/2 are binary variables taking value 0 or 1. As illustrated above, the response variables are M1 {0. 13 and M2 {0, 1, 1, and the structural equations for V1 and Vz are as follows:
0
M2 0
Vi
M2
Vi f M1, V/2 ff2(M22 V1)
Vi
M2
M2 =
If do(0) is applied, (V1, 1/2) (0, when (M,, M12 = (0, 2) (0, 3). If do(V1 1) is applied, (Vi, 1/2) = (1.0) when M1 = or and M2 = or 2. It shows that for a given intervention do do(0) or do can only be inferred from V since M is unobservable. Since Mj and M2 are correlated, we define their joint distribution P(M1 M, =
1), there exists deterministic mapping from M to V. Besides, the true value of M
Pij. We further express the observational and interventional probabilities of V with the probability of M as follows,
P(V, = 0, V22 = 0) = Poo + P01.
P(V = 0, V/2 = 1) = P02 + P03+
P(V, 1, V/2 0) P10 P12+
P(V: 1, V/2 1) P11 P13.
(4)
Pao(vi=0) (V2- = 0) = Poo + Po1 + Pio + Pı1, Pdo(vi=o) (V/2 = 1) = Po2 + Pos + P12 + P13+
P (V2- 0) = Poo + Po2 Pro + P12, Pao(vi=1))( (V22 = = Po1 + Pos + P11 + P13-
can be seen these parameters are sufficient for specifying the model Fig. c). Such a parameteri- zation technique can be extended to general causal graphs with latent confounders [40].
5

---

3.2 Space of Interventional Distribution Tuples
In causal graph, a confounded component (c-component) is a maximal set of vertices connected with bidirected edges [34]. Note that a singleton node without bidirected edges is also c-component. For example, there are two e-components in Fig. [a): {V1, V3. }1} and [V2]. In fact for any causal graph 9. its observable variables V can be uniquely partitioned into c-components (V) (V....., V*(()), }. where (g( is the total number of c-components in G. Then M can also be partitioned into (M'. M) where each M contains response variables adjacent to V For example Fig. 1), b), M partitionnd into (M, M3, M and (M2}. Within each M', the response variables are correlated since they are connected by bidirected edges. Besides, M M!...,, ...(())))) are mutually independent since M' and M are not connected with bidirected edges for any * j. As a result,
P(m)=
! P(m'). By concatenating P(m') for each m E S2(M)), we construct vector
Py E (I), where A(()(())) == {p' E RIB(M)) 20
1 =
1} and 1 T is the transpose
of the all-ones vector.
Let the parent set of c-component V be Pay: := (URveevs Pa.) Vd. When taking intervention
do(S = s), the values of V nS is set sV'), which denotes the values of V nS that is consistent
with s. Notice that MD picks the mapping functions from Pa, to V, for all V, V5. Seeing values v², pays and s(V*], there exists a set of configurations of M2, denoted by B vij (v', pay:) S ((M²), that can make this happen. By marking configurations in [g pav:) with 1 and
others to be O, we construct vector (s. pay;) ) E {0, 1) [(M))) With M ,....,,M* MM.(9)
being mutually independent, the interventional distribution can be factorized as
(9)
(x(g)
Pv(v) II P(M' E BBg pay:)) = II
6% s (v', " pay.)py. j=1
(5)
In the bow graph example in Fig. Ic), there is one c-component, and vector bT
S.s (vi, pay.) can
be constructed by referring to (4). where Pı is a concatenation of pi.j The result in 5 generalizes the parameterization for the bow graph general causal graph. Based on it, given a causal graph G. we define the space of interventional distribution tuples as the following.
Definition 2 (Space of Interventional Distribution Tuples). Given a causal graph 9 = (V,E,)) the space of interventional (and observational) distribution tuples P = (Ps)seI is
n.(9)
Mg = {P' p'
Ys IL P((v)= = II
TT (V ,av:) E A((0(M))))
J=1
Space Mg contains all interventional distribution tuples associated with canonical SCMs (M. V,F, P(M)) with arbitrary P(M). Since the space of {PI..... Pm.(o)} is compact and continuous image of compact space compact, .Mg also a compact space.
An Asymptotic Regret Lower Bound
In this section, we present asymptotic information-theorrticc regret lower bound for the causal bandit problem with confounders. quantifies the optimal asymptotic performance of a uniformly good causal bandit policy defined below.
Definition (Uniformly Good Policy). Given a causal graph G = is uniformly good if for any 0, the expected regret of for any interventional distribution tuple setup P E Mgg, denoted by RT (P), satisfies
a causal bandit policy
R7 (P) T-x
lim
policy æ being uniformly good indicates that can achieve subpolynomial regret for any P Mgg The information-theortti regret lower bound sets the limit for the asymptotic regret of all such policies. Let D(P || Q) denote the Kullback-Leibler (KI.) divergence of two probability distributions P and Q and let I_s I (s).

---

Theorem 1. Given a causal graph G = (V. B), let (Pa)SEI E Mg be the true interventional distribution tuple with unique optimal intervention s, E I with mean reward p.. The expected regret for any uniformly good causal bandit policy π satisfies
lim inf (P) 2 C(P.g). T-000
where () is the value of the optimization problem given below,
((P.)) minimize 2220
Σ
MeDs:
(6)
", SET.
U., E {P" e Ms
Σ BEI
D.D l| PT) <1, Ps. (7)
S. t. max SET...
where 1úg is the expected reward of intervention S according probability distribution P
Theorem D can be viewed as an extension of [10 Th. IJ. and we defer its proof to appendices. The optimization problem O(P, Mg) is a semi-infinite program since there are infinite P' in (7). To interpret the lower bound, 6 is minimization of the regret, and its solution indicates an optimal allocation of O T) number of explorations, which 1/2 In T for each s E I_g. as T - xc. In Esez Me (Pp P!) can be viewed as the distance generated between true interventional distribution tuple P and an alternative p" E MMg by an exploration allocation strategy (Nw)sEz... For any P' in (7). /4g = He since P = Ps.. and as result, maXseT 1/g S μa. indicates intervention s, also optimal in p'. So 7 sets a constraint for (Ns)xET. s." : the models allowed to have distance from the true model must also take s. be optimal. Or conversely, (Na)sEI_.. must generate distance 2 1 for any P' E Mg with Pa. Ps. not taking intervention s, be optimal.
Remark The OIn'T) regret lower bound holds only if there exists P' E Mg such that P". Ps.. which is a condition meaning P can not be distinguished from all other interventional distribution tuples in MM by only taking intervention s.. This condition holds for almost all causal bandit prob- lems. Otherwise, constraint (7) is relaxed, and the value of the optimization problem C(P, (Mg) = O. which indicates sub- lobartgrrt regret can be achieved. Following the same line of proof in MI7 Th. 3, it can be shown simple UCB can achieve this sub-logarithmic in fact constant, expected regret.
5 SCM-based Causal Bandit Algorithm
The regret lower bound in Theorem suggests potentially optimal exploration strategy, i.e. to take each intervention E I-s. up to 7/ In T times. However, it requires the ground truth P to solve the optimization problem ((P,6 G). The allocation matching principle [10] essentially replaces the true model with an estimated one to solve the optimization problem, and controls explorations to match with the solution. It is expected that the estimated model converges to the ground truth at a fast enough rate so that the actual explorations match with the optimal exploration strategy. We follow this idea to design a causal bandit policy, whose pseudo-code is shown in Algorithm We call this SCM-based Approximate Allocation Matching (SCM-AAM).
Similar to 22], SCM-AAM only intervenes on POMISS for the purpose of reducing the action space. The algorithm is anytime without requiring the knowledge of horizon length. It takes two tuning parameters& e = (0, 1/ [Z] and 7 > 0 as inputs that control the exploration rate, which affects finite-time performance. At each time t, let (N)ss) be the number of times the intervention do(S s) is taken so far, and let Nv, s) be the number of times we observe v with intervention do(S = s). The algorithm maintains set of empirical interventional distributions (Ps,))ez and empirical mean rewards (Da,)sEz, where Pa,((v)
(v)()s) for each Z.
The main body of the algorithm is composed of two components: exploitation and exploration. At each round f, it first attempts to evaluate if enough information has been collected to determine the optimal action. Inspired by the lower bound, enough distance is generated by the sampling history between (Pst)sez and P' = (Prsee if Exez D((s) P') > (1 + (1) Int. So we can construct a confidence set C. with high probability to contain the true model P. which is defined as
G :== {p' E Ma
Σ (P,,) Il P s (1+ Int]
(8)
7

---

Algorithm 1: SCM-based Approximate Allocation Matching (SCM-AAM)
Input
:Causal graph g (V. E) {s ((S) S POMIS)
Initialization :N; = 0, Vs E I (s(s) =0
Set
:< E (0, 1/ [ and
Output
:Sequence of interventions
Select each intervention s once
for ( = [ 1 to 7 do
Compute empirical distributions and mean rewards (PRt)sSE and (Nx,)sEI
With C2 defined in (8), compute UCB (c,(Ci) = Ever(v) On maxpree, Pi(v), [s..t Ps > (T,(C,)) Vs E I_.., then
L Select S; f- Se,t, and (s.) f Nr(S.) + % exploitation
else if min N2(s) I <Ny then Select S, t arg min (s) % forced exploration Set N f- No + and (S,) t (s( +1
else
Select S. arg max (C,) % exploration with greedy approximation
Set No +- N2 and N..5.) N.(S.)
With Vn, being the reward node, for each E I, the algorithm computes the UCB of the mean reward of taking intervention as (a(C,)) = Even(v) Un maxp'ec, P.(v). If there exists an intervention S., with empirical mean reward Ps... > By (Ct), Ys E I_ we are confident about s., to be the optimal intervention. So the algorithm enters the exploitation phase and selects S, S,,t-
no such Sa, exists, the algorithm needs to explore. According to the allocation principle, one is inclined to solve ((Pa.))sEz 9) defined in Theorem [ and make (s(s) x 7/s In for each s E I. Nevertheless, there is guarantee that this semi-infinie program can be solved efficiently. Therefore, we take a greedy approximation approach. Ideally, to get out of exploration, the algorithm needs to reduce max *. (C.) to a value below fl,, thus selects S, = arg max (C.).. The algorithm maintains a counter of exploration steps Nç. If minsez (s) S eNf, generates forced exploration by selecting the least selected intervention S,. Such a mechanism ensures every action is persistently taken in exploration phases so that (Pa,) converges to the ground truth eventually.
Remark 2.
With factorization in (5, C2 corresponds setting constraint for (PI(.....PP((I))) Pa,(g) as
Ps.c(V) (9) UT S.Niv (v3, pay: )pj.
Ne(s, v) In
S (1 +7)
SEI VEN(V)
where the expression on the left of inequality is convex function of Pi..... ... (G). Define convex C. (.p.....,PP.((E)) pj A([((M)))) Vj (l...., ... n. (9()),, and ( is true). Then the UCB can be derived by maximizing set of concave functions over C. as follows,
nr
(o(Ci) = Σ Un max P.(v)= =
Σ exp
Σ In (bJ.aive) (vl,a))))) j=1
(pp)))
max (PI.....P..ttoo Pne JECT
piec.
VER(V)
VER(V)
We use (C(C instead of (L(C.)) maxprec, Ever(v) Un as UCB since Evenry) Un P((v in general is a non-concave function of .i.....PPP... ...(()) Also, notice that V' I: (C.) 2 (C.))
pure topology-based approach (2), each intervention on POMISs treated independently during the algorithm execution. Whereas SCM-AAM can leverage the canonical SCM to incorporate the sampling results from different interventions together. After each new sample v, with intervention s, is observed, it is used to update the parametric space for interventional distribution tuples C,,

---

Finite Time Regret Analysis
We present finite time problem-dependenn regret upper bound for SCM-AAM in Theorem The complete proof is provided in the appendices. We also give an interpretation of Theorem and compare the regret upper bound with [2 in the setting where the reward node V,, is binary.
Theorem 2. For the causal bandit problem with unobserved confounders, suppose the causal graph g = (V, E, B) is given and Assumptions and are true. For any interventional distribution tuple p E Mg. any K. > O and horizon of length T, the expected regret for SCM-AAM with parameters
e E (0, 10, [Z)) and y > O satisfies
RT
RSCM-AAM (P) = (1+
Σ ((P)(A.
<|z 1- In TC,
+c.
SEI
where is suitably large universal constant depending on P, and tuning parameters and % and
(0.
(0, S ps,
va E :G( max 20 Toe s.t. (n,, P)) 2 Pas otherwise,
in which Cu(Ns, :) = {P' E Mg DD P`) + cn./2 1122xxe ExEL_. D(Px $1)
Theorem 2 indicates the expected number of samples for each I_s. can be approximately bounded by (a(P) (nP))n T. It can be interpreted as follows: when s E T_s. is selected approxi- mately up to (P) In T times, its UCB can be pushed below pax. The presence of terms contain- ing is due to forced exploration. In [22], KL-UCB and Thompson sampling are employed to apply interventions on POMISs. If the reward node Vn E {0, 1}, they enjoys expected regret -SEI_.. (A, ((PTT) Theorem 2 shows that the SCM-AAM enjoys smaller expected regret when we disregard the small constants K, 7 and E. To see it, we express the leading constant for KL-UCB and Thompson as
|| Ps, (V.)) + é for some insignificant e' [14 22. In this situation,
1VD(P,(V.)) || Ps. (Vr,) max 77s S. Aa P(V))) 2 p.: 20
where CT P(V.)) = (VV(V, [0. | D(P((V) II P.(V)) < 1}. Note that CT P(V.)) only sets constraint on (V(V.),, while (T,, P) sets constraints on PV(V). As a result, (n P) (n,, P(V,)). so that (P) 11D((P((V,) (V.)).
7 Experimental Results
We compare the empirical performance of SCM-AAM with existing algorithms. The first baseline algorithm employs the simple UCB algorithm 4 on reduced action set that includes interventions on POMISs. The other two baselines as introduced in (22]. utilize the KL-UCB algorithm and Thomposn sampling (TS) intervene on POMISs. We compare the performance of all the algorithms on three different causal bandit instances shown in Fig. 2 We choose the input parameters of the SCM-AAM algorithm to be ? = 0.1 and = 1/|5Z| in the simulations. We set the horizon 800 for all three tasks and repeat every simulation 100 times. Additionally, we include confidence interval around the mean regret, with the width of the interval set to twice the standard deviation. The structural equations for the three causal bandit instances, as well as experimental details, can be found in the appendices. We plot the mean regret against time, where time in this context corresponds to the number of actions. All the nodes in Fig. take binary values, either 0 or 1.
For task 1, we consider the causal graph shown in Fig. 2(a) with POMISS {Vi) and {V2). For task 2 and task 3, we consider more complex causal graphs, as displayed in Fig. b)) and (c). The POMISS for task include {V1). {V3), and (Vs, V.J. while for task 3, they are (V1, , V4, Vo) and (Vs. Vo). The UCB algorithm has inferior performance compared to other baseline algorithms, especially in the more complicated tasks 2 and 3. The TS algorithm outperforms both UCB and KL-UCB in all three settings; however, it still incurs more regret than our proposed algorithm. The experiments demonstrate that our proposed SCM-AAM algorithm consistently outperforms other baseline algorithms by incurring lower empirical regret across all three tasks. Notably, the performance advantage of SCM-AAM is more significant for tasks 2 and 3, which have a more intricate causal graph structure with higher number of nodes and edges. The results indicate that

---

Vi
V/2
V1
V3
Vi
V33
Va
V4
1/1
1/2
V/3
2/2
V/3
V7
Ve
(a) Task
(b) Task
(c) Task
Figure 2: Causal graphs used in the experiments
100
100
80
RL-ECB
-0- DCB en POMIS:
SCSE AAM
KI-IICh dn POMIS
80
KL--IES PUBEES
DCB POMIS
13 FONES
POSISS
IN PORIIS
40
20
0
0
200
400
600
800
Time
(a) Task
(b) Task
(c) Task 3
Figure 3: Regret versus time for the instances of structural causal bandits shown in Figure
incorporating causal structural information through the SCM-AAM algorithm can significantly reduce expected regret, especially for more complex causal graphs.
The simulations were conducted on a Windows desktop computer featuring a 12th generation Intel Core i7 processor operating at 3.1 GHz and 32 GB of RAM. No GPUs were utilized in the simulations. The runtime for each iteration of the SCM-MAB, involving 800 arm plays, was approximately minutes for both Task 1. However, for Task and Task which encompass larger underlying causal graphs, the runtime for every iteration increased to around 20 minutes. The algorithm code is provided http://hhhhbboooo//aaaaaaaLLLLaa
Conclusion
In this paper, we studied the causal bandit problem with latent confounders. With causal information provided by a causal graph, we present a problem-dependent information- regret lower bound. Leveraging the canonical SCM, take approximate allocation matching strategy to design the SCM-AAM algorithm. By analyzing SCM-AAM, we show it has problem-dependent logarithmic regret upper bound. The analytic result is complemented with numerical illustrations featuring variety of causal structures. It is shown that SCM-AAM exhibits promising performance in comparison with classic baseline algorithms. Since SCM has natural application in counterfactual reasoning, extending the proposed algorithm and theoretical results to counterfactual decision- making setup interesting future direction.
Acknowledgements
This research has been supported in part by NSF CAREER 2239375, Most of the work was completed when Lai Wei postdoctoral researcher at Purdue University.
10

---

References
[1] V. Aglietti, X. Lu, A. Paleyes, and González. Causal bayesian optimization. International Conference Artificial Intelligence and Statistics, pages 3155-3164. PMLR, 2020.
[2] S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[3] J. M. Antle and S. M. Capalbo. Econometric- prociss models for integrated assessment of agricultural production systems, American Journal of Agricultural Economies, 83(2):389-40) 2001.
[4] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning. 47:235-2566 2002.
[5] A. Balke and Pearl. Counterfactual probabilities: Computational methods, bounds and applications. In Uncertainty Proceedings 1994, pages 46-54. Elsevier, 1994.
[6] E. Bareinboim, A. Forney, and J. Pearl. Bandits with unobserved confounders: A causal approach. Advances in Neural Information Processing Systems, 28, 2015.
[7] J. Bartroff, T. L. Lai, and M.-C. Shih. Sequential experimentation in clinical trials: design and analysis, volume 298. Springer Science & Business Media, 2012.
[8] B. Bilodeau, L. Wang. and D. M. Roy. Adaptively exploiting d d-separators with causal bandits. arXiv preprint arXiv:2202.051 000.000500,0. 2022.
[9] R. Combes and A. Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms.
In International Conference on Machine Learning, pages 521-529. PMLR, 2014.
[10] R. Combes, S. Magureanu, and A. Proutiere. Minimal exploration in structured stochastic bandits, Advances in Neural Information Processing Systems, 30, 2017.
[11] A. D'Amur, K. Heller, D. Moldovan, B. Adlam, B. Alipanahi, A. Beutel, C. Chen, J. Deaton, J. Eisenstein, M. Hoffman, al. Underspecification presents challenges for credibility in modern machine learning. The Journal of Machine Learning Research, 23()):12377-1229, 2022.
[12] G. Dulac-Arold, N. Levine, D. J. Mankowitz, Li, C. Paduraru, Gowal, and Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 1009))2419-2468, 2021.
[13] Feng and W. Chen. Combinatorial causal bandits. arXiv preprint arXiv:2206.0199 2022.
[14] A. Garivier and O. Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings. 2011.
[15] T. L.. Graves and T. L. Lai. Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3):715-743, 1997.
[16] A. H. Guide. Infinite dimensional analysis. Springer, 2006.
[17] B. Hao, T. Lattimore, and C. Szepesvari. Adaptive exploration in linear contextual bandit, In International Conference Artificial Intelligence and Statistics, pages 3536-3545. PMLR, 2020.
[18] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, ((1):422) 1985.
[19] F. Lattimore, T. Lattimore, and M. D. Reid. Causal bandits: Learning good interventions via causal inference. Advances in Neural Information Processing Systems, 29, 2016.
[20] Lattimore and C. Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737. PMLR, 2017.

---

[21] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[22] S. Lee and E. Bareinboim. Structural causal bandits: where to intervene? Advances in Neural Information Processing Systems, 31, 2018.
[23] S. Lee and E. Bareinboim. Structural causal bandits with non-manipulable variables, In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4164 4172, 2019.
[24] Y. Lu, A. Meisami, A. Tewari, and W. Yan. Regret analysis of bandit problems with causal background knowledge. In Conference on Uncertainty in Artificial Intelligence, pages 141-150. PMLR, 2020.
[25] A. Maiti, V. Nair, and G. Sinha. A causal bandit approach to learning good atomic interventions in presence of unobserved confounders. In The 38th Conference on Uncertainty Artificial Intelligence, 2022.
[26] J. S. McMullen. Entrepreneurial judgment empathic accuracy: A sequential decision-making approach to entrepreneurial action. Journal of Institutional Economics, 11()):51-681, 2015.
[27] A. Ortega and D. A. Braun. Generalized thompson sampling for sequential decision-making and causal inference. Complex Adaptive Systems Modeling, 2(1):1-23, 2014.
[28] Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-688, 1995.
[29] Pearl. Causality, Cambridge university press, 2009.
[30] H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 5855)5227-535 1952.
[31] D. Russo and B. Van Roy. Learning to optimize via information-directed sampling. Operations Research, 66(1): 36(1):230-22 12330-25,2222 2018.
[32] V. Srivastava, P. Reverdy, and N. F. Leonard. Surveillance an abruptly changing world via multiarmed bandits. In IEEE Conf. on Decision and Control, pages 692-697, Los Angeles, CA. Dec. 2014.
[33] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-29) 1933.
[34] Tian and J. Pearl. A general identification condition causal effects. In Eighteenth national conference on Artificial intelligence, pages 567-573, 2002.
[35] B. P. Van Parys and N. Golrezaei. Optimal learning for structured bandits. arXiv preprint arXiv:2007.07302. 2020.
[36] C. H. Weiss, M. Bucuvalas, and M. Bucuvalas. Social science research and decision-making, Columbia University Press, 1980.
[37] A. Yabe, D. Hatano, Sumita, S. Ito, N. Kakimura, Fukunaga, and K.-i. Kawarabayashi. Causal bandits with propagating inference. In International Conference on Machine Learning, pages 5512-5520. PMLR, 2018.
[38] B. Yale. Geometry and symmetry. Courier Corporation, 2014.
[39] J. Zhang and E. Bareinboim. Transfer learning in multi-armed bandit: a causal approach. In Proceedings of the 16th Conference Autonomous Agents and MultiAgent Systems, pages 1778-1780, 1780, 2017.
[40] J. Zhang, J. Tian, and E. Bareinboim. Partial counterfactual identification from observational and experimental data. In International Conference on Machine Learning, pages 26548-26558. PMLR, 2022.
12

---

Appendices
A Proof of Asymptotic Regret Lower Bound in Theorem I
The lower bound derived following the same strategy in 21 by applying divergence decomposition and Bretagnolle-Huber inequality. For completeness, we reproduce both proofs in this section. Readers familiar with these results can skip them. Besides, note that a more general result on controlled Markov chains is proven in [T]].
Recall that policy т is composed of sequence {TT HENSaa where at each time t {1...., T) Te determines the probability distribution of taking intervention S, E I given intervention and observation history (S, 81, -t....,,-11, Vt-1). So the intervention and observation sequence {S,, Vehoesso is a production of the interactions between the interventional distribution tuple {Ps)ez and policy Let T be the horizon length, we define probability measure IP the sequence of outcomes induced by (Pa)SEz and π such that
P(S1, Vi...., ST, ST, II (e( S1, SL- (v.).
(10)
For fixed policy n, let and P' be the probability measures on the T-round plays of two different
causal bandit instances with different interventional distribution tuples P = (Ps)esz and p'
(P*)sez in space Mgg, which is defined in Definition From (TO), we get the distinction between
and IP' is exclusively due to the separations of P and Pl. As result, ((P || PP') has the following decomposition, which is a standard result in MAB problems [2I] Th. 15.1].
Lemma 3 (Divergence Decomposition), Given causal graph G = (V, E,,,B)), let P= (Pa)sez be the true interventional distribution tuple and let P' = =P*) I.T be different from P. For some fixed policy let IP and TP' be the probability measures the T rounds of causal bandit plays in P and P respectively. Then,
D(P PP)
(s) PP),
SET
where the expectation is computed with probability measure P.
Proof. For a fixed policy æ. from 100
we get
T
P(S V1
ST. VT) = II
(s S1, Vt......S--1.. (.)
As result, n. is reduced and we get
P(S1, V1 ST, VT) log (((S), Vt, ST, VT)
Ps. (v)) log Σ
(11)
8, (v,)
which shows the distinction between P and P' is exclusively due to the separations of Ps and P for each s I. Then we can decompose D(P PP) with (1T) as the following.
P(S1. V Sr. V D(P P²) = E log (S
Ps. (V.)
Ps. (v)
E
log
E
log
V V....., S7, VT)
PS (V.)
p
1=1
Ps,
E
E
log
St
E (Ps, Pb.)]
p
S.
T
Σ
Σ
1(S, = D) P1)
Σ ( || P
Σ
1(S =s}
=
1=1
RET.
Σ
D P.)
=
aEI
which concludes the proof.

---

The other tool to prove the regret lower bound is the Bretagnolle Trebe Huber Inequality.
Lemma (Bretagnolle-Huber Inequality [21] Th. 14.2), Let P and Q be two probability measures on measurable space (St, F), and let E be an arbilrary event. Then
1 P(E) Q(EE((EE) 2 exp(-D(P|) Q)),
where _ = -2' E is complement of E.
Proof with finte Ωt In Assumption] 1 we assume each node in the causal graph can only take finite number of values. So the sample space for the causal bandit problem with horizon length T is finite. We provide proof for the Bretagnolle-
inequality assuming 92 is finite. First, we show
P(E) + Q(F9) = Σ P(w)
Σ Q(w) 2
Σ
Σ min (P()),
+
+
WEE
WEDD
WEB
WEE
Σ
min(P(w), Q(w)) = 2
Σ
min P(w), Q(w) Σ
(P(w) - Q(w))
WER
WER
WEN
IV
min(P(w), Q()) Σ
WES
we
Applying Cauchy-Schwarz inequality, we get
P(E) + Q(EE)
Σ /min(P(w)), max Q(w)} P(W)
1
Σ
VP(W)Q(W))
2
WER
WER
exp
2log
Σ Q(w))(w))
= exp
1
2
Σ
P(w)
Q(w)
2
P(w)
WEn
WEQ
Q(w)
2 exp
2
P(w) log
exp
(-D(P Q)).
P(w)
2
wEn
We conclude our proof.
To prove the regret lower bound, the remaining work regards applying divergence decomposition and substituting (IP || IP)) into the Sretagnolle-Hubee inequality.
Lemma 5. Given a causal graph G = (V, &, B), let P = (Ps)seI E MMg be the true interventional distribution tuple with unique optimal intervention s, I with mean reward p.g The expected regret for any uniformly good causal bandit policy π satisfies
RT HT (P)
lim inf T-000
C(P.9),
I
where C(P,Mg) is the value of the optimization problem given below
(P,
minimize
Σ Ax.
(12)
The 20,
BEI
D(Ps P() 2 1,VP' e (P" e e |s, II)).
(13)
SEI
where I the set of optimal interventions according to P"
Remark 3. To interpret Lemma 5 (12) is minimize of the regret, and its solution indicates
optimal exploration strategy. Each s E I_a. should be selected up to al In' as T - cp. In (13) ExET ((P, P!r) is viewed as the distance generated between true interventional distribution tuple P and alternative PD Mg by exploration strategy (na)seI... So 133 requires
(Ne)sEI... must generate distance 2 for any P' E MM in which intervention S. is not optimal.

---

Proof. For any P' {P" E Mg s, & I. the optimal intervention s, according to ground truth P not optimal in P'. Recall I' is the measures on T-ronnd plays of causal bandit with interventional distribution tuple P Also let μl, be the optimal mean reward and A p/' 1gg. For true causal model P, IP and Ag are defined similarly. For a fixed policy 9, let Rr and R2 be the expected regret from T round plays in P and P respectively. Letting min (As, A J. we get
eT P PNr((()))
T 2
and R' T pp' (Nr(s.) > 7 2
ET
RT
Combining both inequalities, get
(NN(ss)) < T ) 2 +
T = P' (s. 2
2 EI
RT + Ry).
Applying Bretagnolle-HHuber inequality Lemma by substituting event {Nr(ss) < 3 into E,
D(P [| 2 4(R1 + RiT)
(14)
With Lemma 3 we substitute EBET WINT (P's PO) into D(P IP) and rearrange (4)
EBEr (s) Pd) IT
21 In 4 R/y-)/
(15)
In
According to Definition
that for any a > 0, the regret for uniformly good policy x satisfies
RT and
RT
lim
lim T+200
T00 Ta
Ta
follows from
15 that
lim inf Eser
[[Nr(s)) (P& Pa)
E
2 1,
T-200
In
which sets the constraints for ( In as T co. Since Rg = EoEI_.. [) by replacing B In T with 7hs we finish the proof.
Proof of Theorem 7 We finish the proof by showing the equivalence of Ö(P, .M3) in Lemma 5 and
O(P, .M3) in Theorem [ First notice that there is no Tls
(22). Accordingly, Tl. be assigned
to an arbitrarily large value to make >XET 1h D(Pa PS) 2 if # Ps. Therefore, (13) is
equivalent
Σ D& ( 2 1,VP'' E {P" E Mg SEI...
Px. , 8, IN
It means if s. is not optimal in P', then EsEI_, D(P P 2 1. Its contrapositive statement is that if ExETL,, D(P Pt) 1, then s, is also optimal in P'. Putting it into the mathematical
expression, we get
M VP' E {D" Mg
Σ De PP) < 1,, Ps. SEI
max SEI
where we the fact μ.. ul, since Ps, Ps.
The proof is concluded.
B Finite time Regret Analysis of SCM-AAM in Theorem 2
B.1 Guarantee with Forced Exploration
The SCM-AAM algorithm maintains a counter of exploration steps No. In expiration steps, minsez (s(s) < <Nç. the SCM-AAM algorithm generates forced exploration by selecting one of the least selected intervention. Lemma shows that the forced exploration mechanism ensures every intervention is persistently selected in exploration phases.

---

Lemma 6. Let R = {teh22 be the sequence of rounds that SCM-AAM enters the exploration phase. For any time t; R. satisfies that
(s 2 ed
min SEI
2
Proof. We first note that the following two facts are true
minsez (s) is non-decreasing over t.
If minsez N2, (s) v <Ny, then minsez N4 2 min No, (8) + 1.
Since (s) is non-decreasing over I, the first statement is true. The second statement is true since otherwise, S, is selected by forced exploration at least [Z] times without increasing minsez (s). With these two facts, we are ready to provide proof by contradiction. Suppose there exists {l...., [R|] such that
min (s) 2 8EZ
According to the first fact, we have Vj 2 i/2.
min N₂ (s) I min N₁, (s) S <ej.
SET
seT
According to SCM-AAM, c e (0, []). Then apply the second fact,
j
min N2 (s) sEZ
I
2
which creates contradiction.
B.2 Supporting Lemmas (Concentration Inequalities)
The following concentration inequalities are instrumental for regret analysis. For bandit with feedback drawn from arbitrary discrete distributions, a concentration bound on the empirical distribution is presented in 335 Lemma 6]. the structured causal bandit problem with unobserved confounders, the actions space is I. and the discrete support of feedback is !(V). At each time f, for each intervention s E I, recall Ps. is the empirical interventional distribution V and (s)s) is the number of times the intervention do(S = s) is taken till t. For each intervention s E I, the true interventional distribution is Ps.
Lemma 7 (Concentration Inequality for Information Distance Then for any I O,
35
Let 2 ( - 1).
8 + 1/2e
[[(
P
Σ N(ss) 2 LET
<
cxp(1 5).
(12(1)) -
llowing Corollary Bjis a result of Lemma 7
Corollary 8. For any 7 > O, there exists suitably large universal constant such that
2
Σp
Σ Ns(s) PP) 2 (1 + 7)) S.c.
Proof. We select i' such that (1 + In ((()) - 1). We apply Lemma to get
P
N.(s) PA) 2 (1+7) Int In
BEI
<t' +
Nc(s) || 2 (1 + Int
12f
LEEI
<t'
e
(1+7) In (m) 1]
[Z((R(()) -1)
+1
I (19([)]
which remains finite. We conclude our proof.

---

Lemma 9 proposed in [9] Lemma 4.3] extends Hoeffding's inequality to provide an upper bound on the deviation of the empirical mean sampled stopping time. The time SCM-AAM enters the exploration phase is a stopping time, and the time each intervention is selected is also stopping time. will be used in multiple circumstances in regret analysis.
Lemma (Extension of Hoeffding's Inequality (9). Let (EEN be a sequence of independent
random variables with values in [0, 1]. Let Fe be the o-algebra such that a (Z11. (Z1...., Zi) C F. and the
filtration F >Fo Consider E N, and T E Nzo. We define St - Ej(Z; E[2,]), where E {0, 1} is a F5-1 meessuallee random variable. Further define N, = ب Sj- Define
① {l..... T + } F stopping time such that either No 2 s = T + 1. Then we have that
P(Sa 2 Nœ0] S exp((=200))
As a consequence,
PJS 2 N60] S 2 (xx0(=
In Corollary 10 we extend Lemma to bound the L1 deviation of the empirical distribution.
Corollary 10 (L, deviation the empirical distribution). Let A denote finite set (1.....a), .a.. probability distribution Q and Q' on A, let I|Q' - Ql1, = =>i=1 IQ' (k) Q(k) Let X, E A be sequence of independent random variables with common distribution Q. Let J, the o-algebra such that o ((...... Xx) C Fr and the filtration F (Fi)ieN,.- Let Ee {0, 1] is F, J--i--uusurablee random variable. We define
For two
S((i)
N₂
Σ c3, St() = Σ e = =i, and Qx(1) j=1
Vi A. N
1=1
For E N, and T E Nyo, let fl,..., T 1} be F-stopping time such that either No 2 or ④ T + 1. Then we have
P - 2) S (2 - -2) exp (=50²
Proof. is known that for any distribution Q' on A.
|| - Q111 = 2 max
max (Q) Q(A)).
ACA
Then we apply a union bound to get
P p(l Q11, 20) Σ P -Qo(()--((A) 2
ACA
s Σ
P
p(Qc(A)-((AA) Q(()) 2/)
ACA:A#A
s562
$ (2 exp
2
which concludes the proof.
B.3 Supporting Lemmas (Continuity of Upper Confidence Bound)
For constrained optimization problem, Berge's 's maximum theorem imposes additional restrictions on the objective function and constraint set guarantee that the problem's solution varies smoothly with parameters. Specifically, it studies the following optimization problem
(
F(x, 0): ZEG(A)
max
where F: X x θ R the objective function, and G(O) is the set of feasible values for X given 0 defined by the multi-valued correspondence G X. We assume that G(f) C X is compact for all 0 E O.
5

---

Definition 4. The compact valued correspondence G is continuous at 8 E ( if it is both upper and lower hemicontinuous 8. The upper and lower hemicontinuous can be verified as below.
Upper hemicontinuous: the correspondence G is upper hemicontimuous at 0 E θ if G(0)) is nonempty and if. for every sequence {0,} with 03 9 and every sequence {0z} } with 2j
G(O)) for all there exists convergent subsequence { J such that Zj. 7 E G(l).
Lower hemicontinuous: the correspondence G is lower hemicontinuous at 0 E θ G() is nonempty and if. for every x G(O) and every sequence {0₂} such that 02 - 0, there is J Z 1 and sequence {z,} } such that 2j E G(O,) for all 2 J and 2j + x.
The correspondence G is continuous it is continuous every 0 E S2(0).
Lemma 11 (Berge's Maximum Theorem [16, Ch. 17.31]. Let X S R and θ S R Let F θ R. be a continuous f function, and let G θ - X be compact valued and continuous correspondence. Then the maximum value function
V(0)=
max F(x,0) x
is well-defined and continuous, and the optimal correspondence
(0) = f G(0) F(2,
is nonempry. compact valued, and upper hemicontinuous.
We want to leverage Berge's maximum theorem to prove the UCB index ic (Ma, P)) EvER(V) 2n maxprecs (n..P) Pv(v) is continuous with respect to 17 and P. Recall in Theorem for given interventional distribution tuple P E MMg and Ths > 0, Cy P) is the set of feasible interventional distribution tuples P', and is defined as
Ca(11:: P) = =<Dp' MMg the D(Pa PT) + +1///2
D(Px P 11)511 $1 }
Σ
XEI_
Lemma 12. For any E I, the correspondence C. Ryo x Mg Mg is a compacted valued continuous correspondence.
Proof. The space of interventional distribution tuples Mg is compacted has been explained below Definition 2 Besides, for any P E Mg and r/s 2 0, the constrain 7/s D(Ps Pa) + ens/2 ExxI_, P(xx Pt) S 1 defines closed compact set for P' = (Pa) Since the intersection of two compact sets is compact if one them is also closed, C2 P) is compact. remains to show C₂ is both upper hemicontinuous and lower hemicontinuous.
Upper hemicontinuous: Fix arbituary 7/ 2 0 and P MMg, and let {Ta,, Pt))ieNs be sequence such that M/. 2 0, P, E Mg. and (7a... P..) + (Me P). Notice that each C. (Ta... P.) is non-empty since P Cg i P.). Therefore, there is sequence {PiieNss such that P E C2 P.). Since Ns.i - 1/s, there exists a closed and bounded set θ C I220 such that 1/2 E θ, and for some N > 1, Ns.i E è for all 2 N. Moreover, P; and P// are also bounded since every interventional probability tuple in Mg is bounded. Since each (Ma.i, P.,Pi lies in closed and bounded subset for i 2 N, by Jolzano-Weierstrass theorem, the sequence {TT,,,, P,, P/d, )>E has a convergent subsequence (Tlai Pi,, (P)))E with limit point (1), P, P'). Since each element of this sequence satisfies
M(Ta,in Pic P(.) T/ D(Pr.
(P + e/ Σ XEI-.
D(Px,n P ( S 1
the inequality holds at the limit point (m,, P'), i.e.,
h( P, P') = 1/ DPa || Pt) + e7//2
Σ 1 S1 11,
XEI_..
due to that h is a continuous function. We get C2 is upper hemicontinuous.
Lower hemicontinuous:: For arbituary 1/4 > 0 and P E Ms. we fix P' Ca(Tn, P). Let (1 Net be a sequence such that 7s P. = (Pso)xEI E Mg, and (nb.i, P.) + (1/, P).
We show there exists sequence (P')eeNso such that P/ E CalTT.i. P.) for all i, and P p'.

---

Toward this end, for each (7a,,, Pt). if h(M,,i, i, P') S 1, we set P P' so that P/ E CT Pa).
If hMs,,,, Pi, P') 1, we construct P: = (P' x. the following. With Definition there associated with the interventional distribution tuple P;
exist (pi..... P (o) and (p'.....,PP.., and P' respectively. Let p. be associated with
{
c pi P
Gi --1
1 oa Pii
Plucor
(16)
C:
G
so that P/ E EMg. For each s E I and v E 9(V), we have Pa.i(v) In (v.
P (v)
j=
bT
G.alvij pays))p
=Pri(v) In
! S (vS, pav:)) [
[== DJ + p/]
ne(g)
GG)
b (vF, pavx)
S. (v* pay.) )pk
= II
[voj (v', pav.) )p/
G
S (ve,
9 Pk + P/J
i=1
(9)
TT
S (v+ payx 1pk
= Σ
II Jzk
bo V (v', pav: TT
s (v* paya )pí
b
(vt pavx
si= pt - P'k
k=
G.
(a)
5 1 (C( (.)
BT o GGs (v' pays Jp} In V (v*, pay: )
1 -
Ps((v In Ps(v)
Σ
Il
bT / (v pav. P Ci
(V(v)
G
where we apply the log sum inequality to (a). Thus, for any E I, we have
E P3(v) In Pa(v) 1
D(Pa. PA,))=
I D(Ps ||
PA).
(v) C2
VER(V)
As a result, ((T,, Pa, S of h P,, P') = which means P/ Ca(TT,,s Pi).
remains to show P + p' by construction. If h( P, P,P') < 1, in the sequence {( Pe)heN there exist finite instances such that h(T,, P., P') > 1. Otherwise, h(ms, P,P') indicates ci 1, resulting in (66 - {p'...... P'n.(g)) Therefore, P: + P' and Cg is lower hemicontinuous.
With correspondence C₂ being continuous, Lemma 13 gives continuous property of jı, (C, P)). Lemma 13. For any E MM and for any any s I, the UCB index (C,(C P)) is a is continuous monotonically nonincreasing function of 1/s 2 0.
Proof. Since C. compacted valued continuous correspondence, we apply Berge's maximum
theorem in Lemma I1 to get that maxprec, (v(v) is continuous with 7/s- So (C,CC, P)) =
EveRrv) maxp (w.P) P)) Ps(v) is also continuous with 1/.- For any > b > 0, since Ca P) g Ca(b, P), is (Ca(a, P)) < ua (b, P)). Therefore, As (Cs (Na, P)) monotonically nonincreasing with respect to 77--
The SCM-AAM utilizes the empirical interventional distributions to compute UCB and mean reward in exploration steps. Lemma [4 indiicaes that only a small ratio of exploration x is wasted if the gap between empirical distribution and the ground truth is as small 8(k). This fact is the cornerstone of regret analysis since the ground truth is unavailable.
Lemma 14. Given causal graph G EV,,,B B), for any interventional distribution tuple Pt (P')sEz E Mg. let (P())) be the mean reward of each intervention s E I according to P', and define P.. (P') maxser Hs (P'). Let P (Pa) E MM be the true interventional distribution tuple with a unique optimal intervention s, E I. For each E I=... let
(p(P)
max s.t. (Cs (Te, P)) 2 (P), T/e 20
(17)
7

---

= (P' E Mg (PP || P2) + +eee D(Px || Pa) S = For any K > 0, there exists Ö(K) such that for any P = (Pa)SEI MM. if :s E I: ||& - Pall, - 6(6),
in which C= P) P=
Intervention s, is also optimal according to P, i.e, Me, (P) 2 (P))), Vs I_....
For any s E I_s.. (a(P) S ())
Proof. For each s E I. it can be seen that lim, issCss P)) (P( since P' in (Ta. P) is required to be identical to P as 77- For each E I-s., if (O, (O, P)) > (P()), since
iig (Cs(C(11s [1s: P)) a continuous monotonically nonincreasing function of 1/s according to Lemma 13
there exists The > O such that (C,, P)) = p. (P). Setting Ti = max 2 0 [L,C,, P))
u.. (P)). we have ni > 0 and (a()) = Vlg. For any K. > O, Pa (C Kig. P)) < n (P) due to
the definition of n/.. We define
dx(kk) = 2μu (P) 2/ + kng P)) > O.
(18)
From Lemma 12
Cg is continuous correspondence. Since ( PT) + D(Px || P*)
continuous function of P' (Pa) E Mg. follows from Berge's maximum theorem in Lemma Ihhh
D(P& l Pa) + 6/2 max (LL))())))
Σ 1 P
XEI_
is a continuous function of P = (Px)SEI. Thus, there exists (n) > 0 such that if Vs E Pa -Pal1 s (k)).
D(Px Po) +e/2 Σ D(Px || P2)
max P'EC.((1+R) P)
XEI-.
<VI+K
D(Ps || P3) c/2 Σ D(Px P*) S
1
max ()
1 +
XET_..
where the second inequality is due to the definition of Cx((1 + k)),, P). The inequality means for any P' E C5((1 k) P),
( (11+*)DL D(P P2) +
Σ
D(Px 1 P $1
XET
which means Co( kmm P) S Co(1+++ kmg P). Therefore,
[c1 + k)) P)) S (C Ki P)).
(19)
Let (n:) = mi)) (1)), and let 8(k) = mingeI... (x:). Then we set 6(x) = minn4Ainn ((k)), where Amin min (P) (P) Since the reward is bounded by
[0, 1], for any s E I, (P) (P) < | Pall1. If I Ps Pall1 S 8(s).
(P)) Ms. (P) < He (P) - Ms. (s. (P) + 5(k)) S Ms (P) - Ns. (P) + Amin S 0,
which means intervention s, is also optimal according to P. Besides, with (8) and (1)) we have
7 (C,(((1 + k)mE P)) S j. (C= (VI + mni P)) = (_((P)) 8((5)
S/, (P) - 5(k) < Ns. (P) ブ/ PPs. + Pa.ll1 S N4. (P) = u. (P).
Since (Cx(C(()s: P)) is continuous monotonically nonincreasing with 7h and jág (G 2
(P) 2 (C,( + k:) n=) P)), we have
(P)) S (1 + k) (P))
which concludes the proof.
8

---

B.4 Main Proof of Theorem 2
The expected regret is defined as RT RSCM-AMM EEEI... (s)r(s)] in which (s is the total number of times s selected by the SCM-AAM algorithm till T. So the proof is articulated around bounding B, N (s)] for each s T....
Proof. At each time 6, consider the event that the true interventional distribution tuple P = (PR)RET contained by the confidence set = {{p' E Mg ΣsEz Ne(s) ll PD) (1+7) In
Due to Corollary 8 there exists C1 0 irrelevant with T
T
T
P(P Σ
Σ P
Σ SEZ
(((s) P.) 21) Sc,,
(20)
which will only result in finite regret bounded c₁ since reward is in [0. 1]. So by only considering time steps with {P E } to be true, we upper bound the number of times a suboptimal arm s E I.s.. selected in the exploration and exploitation phase separately.
Exploitation phase: When (P E J.} is true, we have
vs E I: (C,) = Σ
Un max Pv(v)
E Pn = Us.
(21)
P'EC.
VER(V)
VER(V)
According to the design, SCM-AAM enters the exploitation phase at time t if Jis.. > i (Cr). Vs e \ [S.). It follows from 21 if S, + s. and E CC,,
uis > is.. (C.) 2 p4.
Thus, we can bound the regret from exploitation steps as the following
=.IS. Σ E A.1(S.=s.Pe. S, u...
(22)
(ET)
=E7/((/)
Let (1x,))221 be the sequence of rounds such that selected by exploitation steps, namely S 8. Considering the warmup step that selects each intervention once, each 4,,i we have N, N..(s) 2 i. Since each i is a stopping time, by applying Lemma 9
we bound the expectation of (22 as
T
E
Σ
Σ
Σ SEI_..
A
P( - Mo > Des S
1=1 SET
12
A
exp(-2iA3
Σ
1
== C2 (23)
24
SET.
21
SET
Exploration phase with inaccurate P;: We define event E, that P. is estimated with sufficient accuracy,
E Ys E I Pr.s Pall, < 8(k)) where (k) > 0 is defined in Lemma 14
(24)
Let R {41121 be the sequence of rounds that SCM-AAM
enters the exploration phase, and each t; is a stopping time. Then we have
Eutte Lite R, E, <
121
From Lemma 6 at ti we have Vs E I: N:(s) 2 ei/2. With Corollary 10 we apply a union bound
T
P t4 IT) <
PP...- - Pall, > 5(k), to S T)
SET 22
121
<(o(k)))
(210(V)1+2 8) I
(((( 2) exp
4
cδ(x)²
C3.
NEI 21
(25)

---

Greedy approximation exploration with accurate P:: For each s E I, let (s(s) be the total
number of times is selected in exploration phases till t. Within time steps such that both E, defined being selected by exploration with greedy
in (24) and {P E Cr) are true, let the last time s E I= s. approximation be
f maxft R S = s, E,, P C+}
true. With L we have VX EIs No (x) 2 ENN. (s)/2, so that
Exer (x)(x) 1I PW)
<N (s) EXEI_, D(Px.7, x.T, Pxx)
N (s) S. PP)) (1+7)
1
(26)
(1+7)
2(1 7) ln
Recall the definition of C, and Ca(1)s P):
G { D' EM
(xx())D(Px (1)
XEI
CT Pi) = {p' EMs naD((Pa 11 Pa) + emaa22 XEZ_
Σ D(Px. P2) $1
With 26 we have C₁2 S Co
(x) (a)
Pt.). and as result,
(1+7)
No (s)
js Co (1+7) P.)) 2 iss (C.).
(27)
By the algorithm design, we have (C, ) 2 Uss.tt since otherwise SCM-AAM does not enter exploration phase. Therefore, it follows from (27) that
jo ( .P..T..)))))))))
No (1+77)
Pr.) 2 =M.
where the inequality holds since when Fiz, happens, Lemma 14 shows s, is also optimal according
Pe. With Lemma 13 Na (11, )) is continuous nonincreasing function of 7/5, then we have
No. (s) S (P (1 + 7) In -
where (Pc,) defined in (7) is the maximum value of ns such that (C, Pt,)) 2 ne (Pt,).
Together with Lemma [4] we have
Σ =. No (s)
+L))
(28)
Forced Exploration: By slightly abusing the notation, at time t. we denote by (S,) as the greedy approximation exploration event and by (S.) the force exploration event. Let the last time s E I be selected by forced exploration be Lg max (1 R S. = =). When SCM-AAM force exploration at f, we have (S, S eNç, resulting in
< 14. - 5)
Σ No. (8) S Σ
N Se
(29)
SEI
We want to provide an upper bound Ny. which is
T
N = Σ
l
<
+ PEC +1 ctt). (30)
1=1
Putting together
29
and 30p.
we get
Σ [(8
T
<
E
Z
(1fte
E. + R, E. +1P e cct)
1-e
T
10

---

Also with 28
we have
T
EL ΣΣ
1[t R. = E,
SEI (1 k1 + +7)
8EI
Then, the expected number forced explorations can be bound as the following,
T
e I
& I- [c] c3 + (1+ Σ [(((,,)l
(31)
sEZ
where C and C3 are defined in (20) and 25 respectively.
Summary: With reward Vn E [0, 1]. we decomposed the expected regret as
T
R&. RSCM-AMM
(P)
SR
Σ
( = s, PEG +
Σ
4
Σ
1(S, s, E,, E cc)
SEI
8EI-..
IER
T
T (PP & Ct),
Σ
1 (S.) t=1
+ Σ P(E)) +
Σ
TER
1=1
where the first three terms present regret from exploitation, exploration with greedy approxima- tion, and forced exploration respectively. So the proof can be concluded the proof by substitut- ing 20
23
28
and 31
into the above incquality.
C Experiment Details and Additional Experimental Results
In the main paper, we conducted experiments in three causal bandit instances. The causal graph corresponding each instance shown Fig, 2 For p [0, 1], let B(p) denote Bernoulli random variable with probability p to be and 1 to be O. The detailed structural equations for each causal bandit instance are described below.
Task1: Uv, = B(0.6), Uv, = B(0.11), Uv,Y, = B(0.51) and Uv, = B(0.15).
Jn (u( ) Uvi
Jv2 (11, u uvovv) = @ uv/ @ uVaVss
fva (12, uvs uvsvs) = 02 @ uvs uyyi3
Task2: Uv, = B(0.45), Uv, = B(0.05), UV..2 B(0.54), Uv, = B(0.07), Uv,Va = B(0.51), Uv,- B(0006) and Uv, B(0.06).
fvi (uv)) = =vV
fvs fvs(uvs: uV6V,) uV22 @ uV3V22
fvs (v1, uVs uvaV,) = 01 O uVs ① uv.4
fva (02, uv, uvsV))
@ U2 1 uv,
fvs (Us, Da, uyy: uvg,)) = 03 @ 04 ① uv, 1 uy,
Task3: Uy, = B(0.5), Uv, B(0.85), Uv, = B(0.85), UV5V = B(0.85). Uv. B(0.14), Uv, ((0.74), Uv. B(0.74), Uv, B(0.54).
fn (uv)) uvi
Svs (wv,) = uV2
fvg (v1, uvg, uvgV;) (V1 @ uuyy
V Unyg
(V2 uv;) -22 A uv4 fv, (v3, U4, uv;) = (V3 @ Buyg) U4
Lva. (w4, uv,) 14 V MVa
Sv, (Us, Vi, uv,, u1,; u1g1,)
((U5 ( vg @ 0 @ (vg1)) Avv;) e us


Reviews:
[{"review_id": "SIN2Nzk2ll", "reviewer": "Reviewer_gxS9", "summary": "This paper considers online learning in a structural causal bandit whose stochastic environment is govened by causal relations represented by an SCM. The paper gives a logarithmic asymptotic regret lower bound characterized by an optimization problem, and inspires on that, provides an algorithm to untilize the causal structure and accelerate learning process. Numerical experiments illustrate that the proposed algorithm outperforms traditional online learning bandit algorithms.", "questions": "See above.", "limitations": "See above.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Writing. The paper has a clear organization of the relative background, concerning Structural Causal Model, Causal Bandit, and Interventional Distribution Tuples in Section 2-3. The presentation is good and easy to follow.\n2. Originality. The paper studies online decision-making algorithms for causal bandits. The lower bound result extends from similar results in the structured bandit [1], and so as corresponding algorithm.\n3. Quality. The writing is of high quality, and theoretical results and experiments are enough to support the algorithm. \n\n[1] R. Combes, S. Magureanu, and A. Proutiere. Minimal exploration in structured stochastic bandits. Advances in Neural Information Processing Systems, 30, 2017.", "weaknesses": "1. The whole paper seems to extend the methodology and algorithm in [1] to causal bandit settings. It is better if the author could highlight extra contributions of this paper.\n\n[1] R. Combes, S. Magureanu, and A. Proutiere. Minimal exploration in structured stochastic bandits. Advances in Neural Information Processing Systems, 30, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first thank the reviewer for valuable feedback and supportive comments.  Please see below for our response. \n\n“highlight extra contributions of this paper”:\n\nThe major contribution of this paper is utilizing a canonical SCM formulation, which partitions the space of causal models, to characterize a parametric space of interventional distributions compatible with a causal graph. Leveraging such a space in the setting of approach in [1], our algorithm is able to effectively utilize sampling history to reduce uncertainty. Note that this connection and leveraging of this canonical SCM formulation in this context, to the best of our knowledge, is new.\n\nAdditionally, in our algorithm, we propose to convert the non-convex infinite program in [1] to a convex program for the causal bandit problem. And due to this new algorithm design, we provide a revised analysis of regret upper bound. In the proof, we give a detailed analysis of the continuity property of the UCB index (related to the canonical SCM formulation) with respect to interventional distributions. And based on it, the expected number of times each suboptimal intervention is selected is bounded.\n\nWe would be happy to answer any further questions the reviewer might have. Thank you once again!\n"}, {"review_id": "aJk4Jhm6Pq", "reviewer": "Reviewer_BoCS", "summary": "The authors present a method for studying structural causal bandits with unobserved confounders. They show that their method, which unlike the baseline (POMIS), includes two tuning parameters, has superior empirical performance on three synthetic experiments (three synthetic SCMs). ", "questions": "## Abstract\n\n- Bandits do not have to be used online, offline usage if common as well. Please consider revising the first line.\n- An SCM does not model random variables as such; it specifies a distribution over the exogenous variables in the model (the noise variables) - but the endogenous variables are not random but are specified by the design and typically user experience.\n- Perhaps it would be better to say that the reward variable (everyone uses Y) returns the stochastic reward instead of the non-manipulable variables, of which there can be many but causal bandit only has one reward variable.\n- It is called the ‘exploration-exploitation’ trade-off, please fix this in your abstract.\n- I would urge the authors to considerably shorten their abstract. It is meant to short summary of your method and main results. I fear that at present length it is eating into valuable space in the paper, space which could be better spent on explaining your method. \n\n## Introduction\n\n- I think a bit more precision is in order in this section, you say on line 54, that “it [causal inference] has special value”. This is true, but perhaps it would be better to explicate on what that value actually constitutes and the utility it has compared alongside purely associative statistics (correlation-based statistics).\n- Lines 63-70 require _a lot_ of background knowledge to be read with any sort of utility. The POMIs, for example, requires an entire paper (Lee and Barenboim) to expose properly or you could just state the main result. But you haven’t instead you had merely mentioned POMIS but without telling the reader what it is order what it does. That is not very helpful particularly since the POMIS is such a powerful concept. Equally you have no adequately exposed the KL-UCB algorithm beyond stating it with its name. That does not do it justice and certainly not in the causal bandit context.\n- On line 69 you say: “A general linear model is adopted in [12], which is different from the non-parametric setup in this paper”  - but _how_ is it different? What is the non-parametric setup in this paper? What is a linear model in this context? You need to be much more precise in order for your readers to follow your line of reasoning.\n- On line 72: how can the arms be related to an arbitrary causal diagram? They are functions of the topology and that in itself is a function of the structural equation models specified in the SCM (under Pearl’s models of causation). The _domains_ of the arms may be arbitrary (though that would be rather odd). Hence, I am not quite what you mean by this sentence. Please do explain.\n\n## Problem Statement and Background \n\n- I am not sure you even need to state assumption 1, it is such a common assumption with causal bandits (indeed most structural bandits) that it is left unsaid and assumed given.\n- I think you mean to say on line 132: “means the expectation is computed with [respect to the] probability distribution P”.\n- Is there a specific reason you name your reward variable $V_n$?\n- Line 150: what are you actually referencing with [36]? Your reference is an entire book but what more precisely are you giving reference to?\n- With assumption two, are you suggesting that there are instances where the POMIS does not contain the optimal set or two or more sets in the POMIS have the same reward? You suggest in the line above the assumption that certain SCMs do not necessarily obey this assumption? Could you please explain further what you mean as this seems to contravene the results by Lee and Barenboim’s work on intervention sets.\n\n## Response Variables and Space of Interventional Distribution Tuples \n\n- Please explain how $V_2$ is a c-component, I do not follow; it is not connected to any bi-directed edges in figure 1(a)\n\n## SCM-based Causal Bandit Algorithm\n\n- SCM-AAM has two tuning parameters compared to the more canonical POMIS selection (merely a function of the topology) - it seems like you are making things more complex by introducing tuning parameters rather than just leveraging the topology of the DAG, as is the case with the MIS and POMIS. Can you please comment on this.\n- I really like how this section is exposed and told. Good job.\n\n## Finite time regret analysis\n\n- Please comment on settings where G does not contain any confounders (dashed edges). Is there any utility by using SCM-AAM then? Or do the results then fall back to those in reference [20]?\n\n## Experimental results\n\n- I think it would be more fair for you to use the Thompson sampling and KL-UCB algorithms instead of vanilla UCB without structural information, that does not sound like a reasonable choice in this setting. Or even the algorithms used by Lattimore and Lattimore in their 2016 paper.\n- Why do you choose those values for your hyperparameters gamma and epsilon? Have you conducted an ablation study for different variable settings?\n- The shape of the purple curve is not particularly surprising since it does not have access to causal information. As noted; this is not a fair comparison and you should leverage other, fairer methods, for comparison just to make it an even ‘fight’. There is very little to learn from the purple curve given that Lee and Barenboim have already shown that algorithms with causal information perform better than vanilla algorithms (Lattimore and Lattimore also commented on this idea).", "limitations": "The main review can be found in the Questions section.\n\nI think the title is a bit misleading; plenty of studies have considered causal bandits with unobserved confounders (Lee and Bareinboim being a pair of authors who have published a number of works in this area). Why do you draw attention to this aspect of your method? Would be interested to hear your thoughts on this.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The main review can be found in the Questions section.", "weaknesses": "The main review can be found in the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and constructive comments. We hope that our responses will address the reviewer's concerns.\n\n\"title is a bit misleading\": Please note that we are not claiming that ours is the first causal bandit algorithm with unobserved confounders. Our goal with the title was to explain that our setting contains unobserved confounders. The emphasis is on the approximate allocation matching solution using structural bandits.\n\n$Abstract: $\n\nWe will shrink the abstract to only deliver the key information about the paper. Besides, we will remove the word ‘online’ and use ‘exploration-exploitation’ instead of ‘explore-versus-exploit’. To be clearer about the reward variable, we mention “the reward variable that is non-manipulable returns the stochastic reward”.\n\n$Introduction:$\n\nThank you for your insightful comment. We will revise line 50-54 as follows: Compared to the classic MAB, casual bandit represents a more detailed model of real-world decision-making problems with richer feedback from multiple random variables, and different actions are interrelated in a causal manner. In applications such as social and economic experiments where the space of actions is large and explicit experimentations are costly, applying causal reasoning gives us the benefit of exploiting the dependecies between actions, so that the learning process can be accelerated and more rewarding interventions can be selected.\n\nWe apologize for not providing sufficient detail about POMIS due to space constraints. We will make sure to add details of the POMIS idea, and KL-UCB with the additional page provided in our camera-ready version. \n\nBy non-parametric we mean no assumptions on the functions of the SCM, whereas in a linear model, the functions are assumed to be linear. We will clarify.\n\nWe agree the current line 72 is imprecise. We mean there is no constraint on the causal graph in the causal bandit problem. For an arbitrary causal bandit with confounders, the theory fits and the algorithm can be applied. We will revise accordingly. \n\n$Problem$ $Statement$ $and$ $Background:$\n\nWe added Assumption 1 to clearly distinguish our setting from some other bandit settings where one might have uncountably many arms such as linear bandits in Y. Abbasi-Yadkori et.al. (2011). \n\n“naming of reward node $V_n$”: This was just a convention. We will clarify this. \n\nWe cite [36] for the concept of general position assumption. We will point to the exact page and theorem.  \n\nAssumption 2 does not contradict with Lee and Bareinboim (2018). Our emphasis was not on the existence but on the uniqueness of the optimum. Yes, the existence is implied by Lee and Bareinboim (2018) but not uniqueness. Note that multiple sets in POMIS can potentially attain the optimum.\n\n\"$V_2$ is a c-component in figure 1(a)\": Please note that a singleton node without bidirected edges is, by definition of c-component in Tian and Pearl (2002), a c-component. We will revise the draft to clarify this.\n\n$SCM-based$ $Causal$ $Bandit$ $Algorithm$:\n\n\"tuning parameters in the algorithm\": We agree that POMIS can help reduce the set of candidate actions at the beginning of a causal bandit algorithm. However, please observe that any such purely topology-based approach would treat each “arm” independently during the algorithm execution. Whereas our structured bandit-based method can incorporate the rewards from these arms together during the execution of the algorithm as new samples are collected by leveraging the canonical SCM-based idea. \n\nAccordingly, the SCM-AAM algorithm employs the allocation matching technique, which requires tuning parameters $\\epsilon$ and $\\gamma$ regarding forced exploration and size of confidence region (see equation (7)).  With a long horizon length, we suggest selecting them to be small. In our experiments, we did not explicitly tune these hyperparameters. Our results show that even without fine-tuning, we outperform existing works. \n\n\n$Finite$ $time$ $regret$ $analysis$:\n\n\"settings where $G$ does not contain any confounders\": As indicated by [20], when G does not contain any confounders, the POMIS will be the parents of the reward node. In this case, the result falls back to those in [20]. This is a great point and we will add this as a remark.\n\n$Experimental$ $results$:\n\nPlease note that Lattimore and Lattimore (2016) is in the pure exploration setting. Thus, we expect it to perform badly for cumulative regret, which is our metric. If the reviewer feels strongly about this comparison, we can add it in camera ready.\n\nWe agree with the reviewer and we will remove the purple line. \n\nWe omitted KL-UCB because we are already comparing against KL-UCB with POMIS [20], which we expect to perform much better. \nIn the camera-ready version, we will add Thompson sampling (TS) with POMIS experimental results, which are shown in the PDF file attached to author rebuttal. We show Thompson sampling on POMIS performs better than KL-UCB on POMIS, while our method outperforms both. \n\nWe hope that our responses will address the reviewer's concerns and increase the overall score. We are also happy to discuss any further questions. Thanks.\n\n$References$\n\nY. Abbasi-Yadkori, Yasin, D. Pál, and C. Szepesvári. \"Improved algorithms for linear stochastic bandits.\" Advances in neural information processing systems 24 (2011).\n\nJ. Tian and J. Pearl. \"A general identification condition for causal effects.\" Aaai/iaai. (2002).\n\nF. Lattimore, T. Lattimore, and MD. Reid. \"Causal bandits: Learning good interventions via causal inference.\" Advances in neural information processing systems 29 (2016)."}, {"review_id": "CCPcqaqvas", "reviewer": "Reviewer_v6qA", "summary": "This paper studies the structural causal bandits in which the causal graph contains latent confounders. The paper contains a lower-bound on attainable regret as well as an algorithm that achieves instance-dependent upper bound.", "questions": "Please see above.", "limitations": "Seems fine.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper studies an established problem, building primarily on [20] and the idea of intervening on POMIS. The paper develops a number of theoretical results on attainable regret.\n", "weaknesses": "The paper is quite dense and could benefit from a more clear exposition on its theoretical contributions. For instance, this may include close-form or approximate values on the various factors listed in L228, L291.\n\nTo underscore the advantage of SCM-AAM and to establish novelty, it seems that one has to establish SCM-AAM is better than the algorithm developed in [20]. The comparison part L293-303 (particularly L298-L301) could benefit from greater clarity on the precise benefit of this paper's algorithm over that of [20].  It would be nice to see a particular factor, say in a particular causal bandit instance where it is clear the algorithm attains better regret. It seems like graphs in Figure 2 are promising candidates, as it is shown empirically that SCM-AAM does better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. Please see our responses below.\n\nIn L228 and L291, the upper and lower bounds depend on the topology of the causal graph. The complicated space of general causal models is not amenable to a closed-form result or an approximated value. Instead, the factors appearing in L228 and L291 are represented as the value of the presented optimization problems. We will add this point in the conclusion as a limitation of our work. \n\nIn [20], applying intervention only on POMISs can help reduce the set of candidate actions at the beginning of a causal bandit algorithm. However, any such purely topology-based approach would treat each “arm” independently during the algorithm execution. Whereas our structured bandit-based method can incorporate the sampling results from these arms together during the execution of the algorithm as new samples are collected by leveraging the canonical SCM-based idea.\n \nIn L293-303, we compare the regret upper bound of the SCM-AAM and [20] to provide theoretical support for the SCM-AAM performing better. In the experiment section, we show SCM-AAM has better empirical performance in 3 different tasks. SCM-AAM can leverage dependencies in the interventional distributions to reduce regret.\n\nWe hope that our responses will address the reviewer's concerns about this paper and increase the overall score. We are also happy to discuss any further questions. Thanks."}, {"review_id": "g4Xtjnsdkw", "reviewer": "Reviewer_EzBh", "summary": "The paper presents two primary contributions for the causal bandit problem with unobserved confounders, general graphs, and discrete RVs.\n1) a lower bound on the regret any algorithm can obtain for this problem. \n2) an upper bound on the regret of a newly proposed algorithm that is able to generalize across interventions (unlike an algorithm such as vanilla UCB) using allocation matching. ", "questions": "- Line 293 onwards compares the regret guarantee to [20]. Is it possible to state exactly that the regret bound of your approach is upper-bounded by theirs? I couldn't directly infer this from the comparison you gave. \n- The algorithm seems to be anytime (doesn't need to know T) but would be great to have this clarified explicitly. \n- Also seems like you can have arbitrary constraints on the interventions and also that multi-target interventions can be used in your algorithm. Is this correct? \n- How computationally efficient is the algorithm? In the computation of the UCB (in algo 1 and remark 2) it looks like you sum over all possible configurations of the variable in the graph, which will explode as the number of nodes gets larger. The graphs in the experiments are also very simple/small so I'm wondering how scalable this method is. \n- Can you clarify what and how many additional hyperparameters the method requires compared to UCB? How do you set these hyperparameters in the experiments of the main paper? Look like you additionally have just $\\epsilon$ and $\\gamma$. \n- Standard UCB can be used without a forced exploration step- why/how does your algorithm break without it? I'm more familiar with regret guarantees that are independent of $\\Delta_s$ (so where regret is on order of sqrt(T)). What happens here as $\\Delta_s$ gets very small or very large?  The forced exploration likely explains why for small time horizons the proposed algorithm is not as good as the baselines on some graphs. ", "limitations": "- In the related work the nonparametric setting studied here is presented as a benefit but it should also be mentioned that the fully discrete setting here can be limiting compared to works that study continuous observations (it is also not really clear that the main ideas described here can be easily extended to those settings). \n- The computational intensity of the algorithm, especially depending on graph size and intervention set size, should be discussed. \n- Line 338 \"it is shown that SCM-AAM has superior empirical performance compared to existing baseline algorithms\". I think this is potentially misleading since the baseline compared to is from one of the earliest casual bandit papers and likely not the strongest among published baselines on the graphs used. I will not insist on comparing against every or any other causal bandit algorithm published since then but I think the claim could be made more moderate, rather than implying that some kind of SOTA empirical performance has been shown. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- This is the first causal bandit algorithm I've seen that has a regret guaratnee for the cumulative regret setting and general graphs (besides [20], which focuses only on reducing the number of arms rather than using structure to generalize across arms). I think the community will find this very interesting. \n- Generally well written prose.\n- There is not much to add regarding the strengths: the paper is generally clearly presented and the result is a novel solution to a open problem that the community has shown a good amount of interest in. I have not gone through the supplementary material so I cannot comment on the correctness of the proofs. ", "weaknesses": "- Experiments are synthetic (fairly common in these causal bandit papers in fairness) but also on extremely small graphs. It would be good to understand how performance varies with graph size and the size of the intervention set. \n- It would be nice to see a discussion in words of how the regret bound scales with various quantities- graph size, intervention set size. The bound as presented is not one of the easiest in terms of extracting this kind of qualitative information. \n- Some prose was clunky and I recall a few typos. The text should be run through Grammarly or a similar tool. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and supportive comments. Your questions will help us improve the clarity and presentation of the paper.  Please see our responses below.\n\n“size of graphs in experiments”: We agree with the reviewer that extending our simulations to larger graphs will help demonstrate the efficacy of our algorithm further. In the camera-ready version, we will test the proposed algorithm on larger graphs and discuss how performance varies with graph quantities, which could potentially include the number of nodes, size of the intervention set, and connectivity.\n\n\"regret bound vs graph quantities\": Due to the complicated space of causal models characterized by the canonical SCM formulation, it is hard to relate the regret bounds to graph quantities. However, our algorithm is designed with the purpose to match the abstract regret lower bound. We also believe the regret bounds have a sublinear relationship with the size of the intervention set since interventions are not treated as independent actions. By applying the canonical SCM model, the dependencies of interventional distributions are exploited to reduce regret.\n\n\"compare the regret guarantee to [20]\": Disregarding the constants $\\gamma$, $\\kappa$, and $\\epsilon$, the regret bound of the proposed algorithm is smaller than that of KL-UCB + POMIS [20]. The reason is that our UCB index is computed from a more constrained space compared with KL-UCB. Please also notice that the constants $\\gamma$, $\\kappa$, and $\\epsilon$ can be arbitrarily small. In the camera-ready version, we will revise line 293 to line 303 to clarify this point.\n\n\"is the algorithm anytime\": Yes, the algorithm is anytime. We will clarify this in the camera-ready version.\n\n\"arbitrary constraints on the interventions\": Multi-target interventions are used in our algorithm and arbitrary constraints can be put on interventions. However, we chose to apply interventions on Possible Optimal Minimal Sets POMIS (POMIS) to reduce the action space. We will clarify this in section 5.\n\n\"computation efficiency of the algorithm\": We report the experimental computation time in Appendix Section C, though the graphs are small. The runtime of SCM-AAM is longer compared with others since it processes more information. The expression in algorithm 1 and remark 2 enumerates all configurations of variables for ease of notation. The algorithm only needs to deal with variables related to the reward node. By only intervening on POMIS, these variables are contained in Unobserved-Confounders’ Territory defined in [20], which can still be many for certain causal graphs. However, in applications where decisions can take time, e.g. policy-making in companies, the proposed algorithm would be valuable. Besides, we believe there exists a trade-off solution with low computation complexity but higher regret which we would like to explore in future extensions of this work.\n\nWe will add additional simulation results on larger graphs and make a detailed discussion about how graph size and intervention set size affect the computational intensity of the algorithm.\n\n\"additional hyperparameters\": Please note that since our algorithm leverages the structured bandit framework, it requires two parameters $\\epsilon$ and $\\gamma$. The $\\epsilon$ corresponds to forced exploration and $\\gamma$ provides a buffer for the confidence region. They will affect short-term performance and the consistency of SCM-AAM.  With a long horizon length, we suggest selecting them to be small. In our experiments, we did not explicitly tune these hyperparameters. Our results show that even without fine-tuning, SCM-AAM still has reasonably good performance.\n\n“why forced exploration?”: To leverage the causal graph to exploit the dependencies among different interventions, our algorithm requires each interventional distribution to converge to the ground truth at a fast enough rate. To achieve it, forced exploration allocates a fair amount of exploration to each intervention. Otherwise, the regret cannot be approximately bounded by $\\sum_{s \\in \\mathcal{I}_{-*}} \\Delta_s \\zeta_s(\\mathcal{P})  \\ln T$ in Theorem 2, where $\\zeta_s(\\mathcal{P})$ is a factor depending on true interventional distributions in $\\mathcal{P}$. \n\nNote that the poor short-term performance is typical for allocation matching-based algorithms, which we agree could be due to forced exploration.\n\n\"logarithmic regret vs $O(\\sqrt{T})$ regret\": Regret on order of $\\sqrt{T}$ corresponds to the works-case regret for a given horizon $T$, as mentioned in JY. Audibert, and S. Bubeck (2009). Say, $\\Delta_s$ is close to $1/\\sqrt{T}$, it is hard to differentiate the optimal action from the suboptimal ones, so the regret will be in the order of $\\sqrt{T}$. If $\\Delta_s$ for each intervention $s$ is much greater than $1/\\sqrt{T}$,  the logarithmic regret better characterizes the performance.\n\n“discrete vs. continuous settings”: We agree that the fully discrete setting in this paper has its limitations and can not be easily extended to the continuous observation setups. \n\nFor minor comments:\n\nWe will revise Line 338 into “SCM-AAM exhibits promising performance in comparison with classic baseline algorithms.” Also, we will carefully check the writing and improve the presentation in the revised draft.\n\nWe would be happy to answer any further questions the reviewer might have. Thank you once again!\n\n$Reference$\n\nJY. Audibert, and S. Bubeck. \"Minimax Policies for Adversarial and Stochastic Bandits.\" COLT. Vol. 7. 2009."}]

Author rebuttal:
We thank the reviewers for their valuable feedback and AC for the assistance during the review process. We address each review’s comments in separate rebuttals. In response to reviewer BoCS, the attached PDF file includes additional experiment results of Thompson Sampling (TS) in comparison with the proposed algorithm in this paper. We observe that TS on POMISs performs better than KL-UCB on POMIS while our method outperforms both. 

Meta-review: The paper studies the structural causal bandit with unobserved confounders. Reviewers are in general positive to the paper, acknowledging that the paper studies an important problem with novel solutions, and it will benefit the research community. The concerns are mostly on the writing of the paper, and the authors mostly address these concerns. I believe a careful revision by the authors will address all the presentational issues raised by the reviewers. Therefore, I would like to recommend acceptance to the paper, while encouraging the authors to do a thorough revision on the paper addressing all the concerns from all the reviewers.
Decision: Accept (poster)