Online Reinforcement Learning for Mixed Policy Scopes
Authors: Junzhe Zhang
Elias Bareinboim
Venue: NeurIPS 2022 Accept (2022)
Keywords: Causal inference
Reinforcement Learning
Graphical Models

Abstract: Combination therapy refers to the use of multiple treatments -- such as surgery, medication, and behavioral therapy - to cure a single disease, and has become a cornerstone for treating various conditions including cancer, HIV, and depression. All possible combinations of treatments lead to a collection of treatment regimens (i.e., policies) with mixed scopes, or what physicians could observe and which actions they should take depending on the context. In this paper, we investigate the online reinforcement learning setting for optimizing the policy space with mixed scopes. In particular, we develop novel online algorithms that achieve sublinear regret compared to an optimal agent deployed in the environment. The regret bound has a dependency on the maximal cardinality of the induced state-action space associated with mixed scopes. We further introduce a canonical representation for an arbitrary subset of interventional distributions given a causal diagram, which leads to a non-trivial, minimal representation of the model parameters.

Online Reinforcement Learning for Mixed Policy Scopes
Junzhe Zhang
Elias Bareinboim CausalAI Lab Columbia University eb@cs. columbia edu
CausalAI Lab Columbia University j columbia.
Abstract
Combination therapy refers to the use of multiple treatments such surgery, medication, and behavioral therapy to cure a single disease, and has become a comeestone for treating various conditions including cancer, HIV, and depression. All possible combinations treatments lead to a collection of treatment regimens (i.e., policies) with mixed scopes, or what physicians could observe and which actions they should take depending on the context. In this paper, we investigate the online reinforcement learning setting for optimizing the policy space with mixed scopes. In particular, we develop novel online algorithms that achieve sublinear regret compared an optimal agent deployed in the environment. The regret bound has a dependency on the maximal cardinality of the induced state-action space associated with mixed scopes. We further introduce canonical representation for an arbitrary subset of interventional distributions given causal diagram, which leads non -riviil minimal representation of the model parameters.
Introduction
The problem of policy learning is concerned with choosing actions based on the state the environ- ment with the goal of optimizing certain measure of performance. Existing policy learning methods could be generally categorized into online learning and offline learning. Online reinforcement learning (RL) learns optimal policies by conducting sequential experimentation, while repeatedly adjusting the policy that currently deployed based on the observed outcomes up to a certain point in time. Effective online algorithms have been developed for various canonical environments, including multi-armed bandits
[26. [3] 14, Markov decision processes (MDPs) [30] [ 34, and partially
observable MDP 9 3
On the other hand, off-policy learning focuses on the offline setting with
the goal of evaluating the effectiveness candidate policies from history data collected following
different behavior policy 24 32 33 More generally, the discipline of causal inference (CI) offers
focuses a compelling set of tools and formal language for offline learning. It allows the agent to draw conclusions about new policies from combination of observations and knowledge about the data-generating mechanisms. Several methods and graphical criteria have been proposed [23]
By and large, almost all methods described above concerns optimizing over a parametric space of policies with a fixed state-action space, which are called the policy scope. That is, the set of actions and observed states are pre-specified priori. However, in many practical applications, this possibly somewhat stringent, and the agent has to optimize over candidate policies with varying state-action spaces; these are called mixed scopes. For concreteness, consider the causal model in Fig. [a that describes possible treatments for alcohol use disorder [19] Based on the condition of alcohol dependant patients Z, the physician may prescribe medication X; to maximize the total days abstinence Y. An alternative treatment is to prescribe a behavioral therapy X2, which alters the social environment W of the patient, and, in turn, changes the pattern of alcohol use. The goal
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

m2
U1
U1
U:
U2
U2
U2
U2
(a) g
(b) Gs.
(c) Os.
(d) Gs.
Figure 1: (a causal diagram G: <b policy-induced diagrams obtained from 9 associated with scopes S {(X1, [ S2 {x2g, {2}}} and S1,2 {X1,, (2)), (2),12)) Red nodes represent actions, blue nodes represent the reward, and red arrows for functional dependencies induced by interventions; are policy indicators, which will be left implicit throughout the paper.
of the analysis is to assess the effect of prescribing a combination treatment of both medication and
behavioral therapy (i.e., a policy = { (X, Z). T2 m2 (X2 2)}. compared to effects of prescribing each treatment separately (i.e., policy π = { (Xi 2)} or (m2(X2 Z)}). In this example, the action scope for all three treatment regimens are different, corresponding to (X1, X2). ). (X1), }.
and (X2). respectively. The physician has to determine the optimal set of actions to intervene in order to find the optimal policy so as to maximizing the days of abstinence.
There exists a growing literature concerned with the problem of optimizing mixed policies under various assumptions about the underlying environment. For instance, the case of multi-armed bandits with linear reward functions, effective online algorithms exist for determining an optimal subset of actions so that intervening on them maximizes the expected reward [6] (). More recently, there exists new developments for policy optimization based on structural constraints in causal models. Non-parametric knowledge of causal relationships has been exploited to refine the space of policies with mixed scopes in increasingly relaxed scenarios [16 17 18] In particular, there are now graphical conditions under which one could (1) identify necessary states for set of actions, and (2) determine a partial ordering rewards (optimality). These results allow an agent to detect and remove suboptimal and inefficient scopes, and focus its attention the possibly optimal actions, accelerating the learning processes.
policy scopes with regard to their maximum achievable expected
Despite of the the substantive progress achieved so far, an effective online algorithms for learning optimal policies with mixed scopes in an arbitrary causal system is still missing. In terms of graphical characterization, is also highly non-trivial, and still unknown how the refinement of the candidate policy space affects the agent's performance. The goal of this paper is to address these challenges. We will investigate the online learning of optimal policies with mixed scopes, provided with a causal diagram associated with the underlying structural causal model (SCM) (23] Ch. 7]. In particular, our contributions are summarized as follows. (1) We develop a novel online learning algorithm that
identifies an optimal policy with mixed scopes in unknown SCM, and show that it achieves sublinear cumulative regret. (2) We introduce a novel parametrization for SCMs with finite latent states, which can represent an arbitrary subset of interventional distributions through minimal collection of c-components. (3) Leveraging these results, we develop an alternative online algorithm that is more computational efficient, while achieving the same asympotic bound over the cumulative regret. Given the space constraints, all proofs are provided in the technical report 42 Appendix A].
1.1 Preliminaries
In this section, we introduce the basic notations and definitions used throughout the paper. We use capital letters to denote random variables (X), small letters for their values (x)) and Ωx for the domain of X. For an arbitrary set X. let X be its cardinality. We denote by P P(X) represents a probability distribution over variables X. Similarly, P(Y X) represents set of conditional We will consistently use P(xx) as abbreviations
distributions P(Y X æ²) for all realizations
for probabilities P(X- = .r) so does P(Y = y X = x) = P(y æ²). Finally, 1 (Z 2) is an indicator function that returns if event Z holds true; otherwise, it returns 0.

---

The basic semantical framework of our analysis rests on structural causal models (SCMs) 23 4 An SCM M is a tuple (V.U, VV P(U)), (FU)), where V is set of endogenous variables and U a set of exogenous variables. F is set of functions s.t. each fv E F decides values of an endogenous variable V E V taking as argument combination of other variables in the system. That is, V (PAy, Uv), PAv C V Uv C U. Exogenous variables U E U are mutually independent, values of which are drawn from the exogenous distribution P(U). Naturally, M induces a joint distribution P(V) over endogenous variables V, called the observational distribution.
policy π over a subset X C V is a sequence of decision rules {=(X Sx)) where every T (xx) is probability distribution mapping from domains of set of covariates Sx C V the domain of an action X. An intervention following a policy т over variables X, denoted by do(r), is an operation which sets values of every X X to be decided by policy X ~ =(X Sx) [37], replacing the functions fx = {ffx : vX E } that would normally determine their values. For an SCM M. let My be a submodel of M induced by intervention do(r). For a set Y C V, the interventional distribution P(Y )) is defined as the distribution over Y in the submodel Mx, i... Par (Ylddoo)) & Par,(Y) Subscript M is left implicit when it is obvious from the context.
Each SCM M is also associated with causal diagram & (e.g.. Fig. Tap, which is directed acyclic graph (DAG) where solid nodes represent endogenous variables V, empty nodes represent exogenous variables U, and arrows represent the arguments PAv, Uv of each structural function fv. We will use standard graph-thcoretic family abbreviations to represent graphical relationships such as parents, children, descendants, and ancestors. For example, the set of parent nodes of X in G is denoted by pa gx))) = Ux ex expa(XX pa(X)g; ch, de and an are similarly defined. Capitalized versions Pa. Ch, De, An include the argument as well, e.g. Pa(X),
pa g X. For a subset X S V. G[X] is a vertex vertex-induee induced subgraph from G, which contains nodes X and edges among them.
For convenience, define bidirected arrow V, <> V, between endogenous nodes Vi, V2 E V as a sequence of arrows Vi2 + U2= + Vi where Us E U is an exogenous parent shared by Vi, Vj- A bi-directed path is consecutive sequence of bi-directed arrows. We will utilize special type of clustering of nodes in the diagram G. called the c-component (38). Formally, a subset C' S V is a c-component in causal diagram G if any pair VG, V2, E C' is connected by bi-directed path in G. For instance, there exist bidirected paths X1 ++ X2 ++ Y and Z <+ W in the causal diagram G in Fig. Ta G thus contains e-components {X1;
(),(Z, W). On the other hand, the diagram Gs. in Fig. 1b contains c-components {X1}, (X2, Y). (Z, W), since bi-directed artows X1 + X2 and Y X1 are removed. For a detailed survey on SCMs, we refer readers to 23 Ch. 7].
2 Optimizing Mixed Policy Spaces
We are concerned with the decision decision-making setting where agent interacts with SCM to optimize a reward Y. The agent could intervene on an arbitrary subset of actions X, called intervenable variables. A policy scope S is collections of pairs Sx) where X E X and covariates
Sx C V s (Y). Let X(S)= = (X) (x.S)) denote the subset of actions in scope S similarly, S(S) = (x, Sx. For instance, for scope S = {(X1, { in Fig. lb X (S,) = {X1}
and S(S)) = {2). Formally, policy associated with scope S is sequence of decision rules The collection of such policies " define a policy space IIs. All policies in IIs share the same scope S: they intervene on all actions in X (S) based on observed values of covariates S(S). Policy space IIs models a general class of decision rules and treatment regimens in many classic sequential decision making settings, including policies in Markov decision processes 255, strategy profiles in influence diagrams [12]. and dynamic treatment regimes (20).
{I (X [
This paper investigates a more general space of policies that are not restricted to a single scope S. A mixed policy scope is a combinatorial set of policy scopes over intervenable variables X. Formally,
Definition 1. A mixed policy scope S is collection of policy scopes S such that X(S) C X.
A policy space 1Ig with regard to a mixed policy scope S is the set of all policies compatible with every scope in S, i.e., Ilg Useslls. Henceforth, we will consistently refer to IIs as a mixed policy space [18] Our goal is to learn an optimal policy in Ig that maximize reward Y in an SCM M, i.c.,
n²" = arg max EM [Y] d)(
(1)
rElls
3

---

The agent does not have access to the parametrization of the underlying SCM M. Instead, the agent can observe endogenous variables V, the mixed policy space IIg, and the causal diagram 9 represent- ing qualitative knowledge encoded about M. Throughout this paper, we assume that endogenous variables V are discrete and finite, while exogenous variables U could take any (continuous) value. Distributions P(V) and P(V do(r)) are thus categorical probability measures.
2.1 A Causal Upper Confidence Bound Algorithm
A typical online algorithm evaluates the effectiveness of candidate policies т IIs by directly deploying policies in the actual environment (SCM M) through repeated rounds of interventions For each round I, the algorithm selects policy क, É [īs, performs intervention
1= .,2,...,7 T. do (Te)) and receives a subsequent reward y,, The cumulative regret for an online algorithm in an
SCM M after T rounds of interventions is defined as R(T, .M > ME [Y do(x")] -Y).. In words, R(T, M) measures the cumulative loss incurred since the online algorithm does not always selects the optimal policy π². A reasonable, or desirable property for an online algorithm is to have sublinear regret for any SCM M. i.... lim R(T, M) /T = O. If the regret is sublinear, the agent is known to be selecting the optimal policy almost all of the time as T goes to infinity.
We will introduce a novel online algorithm that optimizes the mixed policy space while achieving a sublinear regret. It follows the well-celebrated principle of optimism in the face of uncertainty. That is, for each episode, the agent picks a policy based on upper confidence bounds (UCB) | 40 41) which evaluate the effectiveness of candidate policies in the most optimistic models, compatible with past observations, that induces the maximal expected reward. One innovation of our approach is to leverage the invariances embedded in the causal structure G, which allows us to evaluate candidate policy using samples induced by other policies with different scopes.
Formally, let C(G) denote c-collection containing all (maximal) e-components in a causal diagram G | Consequently, C(g) forms a partition (Ci...., C..) over nodes in G where there is not bi-directed arrow between every pair C; and Cj whenever * j. Consider again the causal diagram G in Fig. Tal c-collection C(g) contains c-components C [X,, YJ. C2 = {Z, W). which forms
partition over nodes in G. For an arbitrary subset C' C V. the c- QiC] is function defined as (+) = (c do (v \ c)) [38], where do(u e) is an atomic intervention setting values of V C to a constant v \ (23). For convenience, we often omit input v and write Q[C]. Fix a policy
scope E S. For any policy क E IIs, let set Z = An(Y))) XS). The interventional distribution P(Y dT)) could be decomposed over e-components in subgraph G[Z] as follows:
P(y do(=)) = Σ II = XEX(S)
8x) II Q(C),
(2)
CECs
where the c-collection Cs = C(giZ)) contains all c-components in GlZ]. Let a c-collection C UseSCs. Among quantities in the above equation, decision rules <(x 8x) are fixed. To evaluate
effects P(Y | do(x)) (T) )) of candidate policies in Ilg, it is thus sufficient to learn parameters of Q[C) for components C' C. Consider again the causal diagram G in Fig. Ta the mixed policy scope S
contains elements S = {(X1, {2)) J. S2 = (X2, {2}}} and Sn = T(1, {Z}), (X2, {X1, }
For policy Tı (I1|²) |2) characterized with scope S (X1, {2}) P(Y do(T))) decomposes
P(y | do(m))) =
Σ
ক(ा I 2))[X,, W]]
(3)
21,22,0.00
The c-collection Cs, ([2,, Y), (Z,W)). Similarly, enumerating e-components associated with every scope S E S gives a c-collection C= (1Z, W), (X,, Y), For any C E C, let S(C) be subset of scopes S $ such that C Cs. Our online algorithm evaluates Q[C] by directly performing intervention do( in the actual SCM M.
Lemma 1. For a causal diagram G, let C E C be c-component in g. Then, e-factor C factorizes over a topological ordering X in G as follows:
QIC] = II q (ppt) VEC
(6)
where extended parents PA = Pa(Cv) \ {V}; ; Cy is the c-component containing V in GKVV" e C V' x VH]. Moreover, q (V) PAT) = P (V PA do(x)) for any policy E Is(C))
'Geeraally, c-collection C is collection of c-components C contain in a causal diagram G.

---

Algorithm 1 CAUSAL-UCB*
Input: Causal diagram G. policy space IIg, failure tolerance å E (0, for all episodes = =, 2.... do
2: For every C E C, compute an empirical estimate Qc[C] following Eq. 18
3: Let Mr be set of all SCMs M associated with G such that each c-factor [ is close to
its estimate [c[C] in Eq. 8 That is, for every V E C, for any pay.
6 6/9vv In (2]9pat ((C))//))
l papppa) de (|pattll
(
S
(4)
max (na (pat).
4: Find the optimistic policy n. such that
arg max max EM do(x)) retly ME.R.
(5)
5:
Perform do (T;) and observe V
As an example, consider again the causal diagram 9 and policy scopes S1, S2, S1.2 descrihed in Fig.
For c-component C33 (X2, Y) Cs, this implies the policy scope S1 S(C3). Observe that Cy (X2, Y), Cx, = {X2] and extended parents PAy {X2, Z, W), PA X, {Z}. Lem. implies Q[Cs] is computable from the sampling process following any policy
1
IIs, i.c.
Q[X,, = Ply I2, 2, w, do)
Details of our proposed algorithm, CAUSAL-UCB* are provided in Alg. [ interacts with the underlying SCM through policies in 1ls in repeated episodes f = I...., T. At episode t, it computes an empirical estimate of c-factor Q[C] for each c-component C E C. More specifically, the empirical estimate of c-factor (C) prior to episode & given by:
The (v. pa
(+) = II de (v pat), where qe (v paa) max {ne (pat) ,
(8)
VEC
Among quantities in the above equation, ne (v, paï) the event count for observing V v, p = p after deploying policy π E lIs(c) prior to episode t. That is, ne (v, pat)) E 1 VV+ = (PAt), pay, nI, E IIs(c)) } and n, (pat) CAUSAL-UCB maintains confidence set set. Mr of all possible SCM compatible with g using convex intervals centered around each estimate Q.[C]. It then finds the optimal policy for the most optimistic instance M, from Mr that induces the maximal expected reward IE[Y do(r)) (Step 4). Finally, Step 7 performs do(T)) throughout episode and collect new samples V. Let V(C) be union UCeC C. It is possible to derive a regret bound of CAUSAL-UCB after T >> episodes.
E, ny (v, pa,)). At Step 3,
Theorem 1. For causal diagram G and mixed policy scope S, fix a ô E (0, 1). With probability least 1 - 8, it holds for any > 1, the regret of CAUSAL-UCB # is bounded by
R(T, M) < 19 8)
S Th ((V())77)))
where function A( maxses (G) and AG S) = Evevics) / ViQUPA
Thm. implies that CAUSAL-UCB * is able to achieve sublinear regret; therefore, policy me eventually converges to an optimal policy as episode t - cc. For example, in the causal diagram G and the mixed policy scope $ (S1, 82, 2 described in of Fig. applying Thm. [ gives regret Evaluating (G with the cardinality 10x,1 |2x, gives
bound O (A (GG.S))Tln Sn
AGG = AGG, / Qr Xv. + (xxxz + //w.z.x. + Pz)-
(10)
In comparison, applying standard UCB with deterministic polices in IIg arms leads to regret bound O Th where [[[]] = 12x, |Axi + |2x,]| |Aal + [2x, [02l x [2x,] [02z, dominated by that of CAUSAL-UCB * as the number of endogenous states increases.
|Axx| which is
5

---

Accelerate Learning Processes In the regret bound of Thm. T function (G) can be seen as a measure evaluating the difficulty of the learning task. It has a dependency on the maximal cardinality of the state-action space associated with policy scopes S in S. There exist general characterization of the mixed scope with respect to properties that allow the agent to detect redundant and suboptimal policy scopes [8]. Doing so, we obtain a refinement of the agent's s candidate policy scopes that it converges to the optimal strategy faster and more robustly. For instance, consider the causal diagram ç
U
U2
Figure? 2
described in Fig. 2 We are interested in evaluating policies with mixed scope S = {S2, S2, S1,2]
where S = { (X1, })} S2 = (X2,, 0) } and S1.2 = { 0), (X2, (X1)) ). It is possible to show that S1.2 is redundant since there always exists an optimal policy with scope S or S2. Removing S1 leads to more refined mixes scope S* = (Si, S2 Since A(g,S*) = max (g, Si), AGG, S max AG Si), AG Si), S1G = AG S), applying CAUSAL-UCBB with the refined scope S* achieve a smaller regret than that with S, thus accelerating the online learning process.
Optimistic Planning over Mixed Policy Scopes
The optimization problem entailed by CAUSAL-UCB in the algorithm discussed earlier (Eq. (5) requires the learner to search over all possible SCMs compatible with the causal diagram and experimental data. In principle, this entails challenging task since one does not have access to the parametric forms of the underlying structural functions JF nor the exogenous distribution P(U). Consequently, it is not clear how the existing optimization procedures can be used.
When domains of endogenous variables are discrete and finite, there exists canonical family of SCMs that parametrizes all observational and interventional distributions in any causal diagram using finite number of exogenous states [4 27 A c-component C' C is said to cover an exogenous variable U E U if U E Uv. Let C(U) denote the set of c-components in C covering U. Consider again the causal diagram Fig. la For the c-collection C = {12, W W. {X1, YJ. (X2, {Y}), exoge- nous node U2 is covered by C(U)) = [[X1, }}, {X2, Y). {Y}}; similarly, C(U1) = WZ.W). Next we present a novel finite-state decomposition representing e-factors in any e-collection C.
Theorem 2. For any SCM M = (V, U. A P(U)), let C be an arbitrary c-collection. For any CE E C, c-factor Q|C| decomposes as follows:
Q[C](0)= = = Σ E
Σ
II 1(Iv(pay, uv) = b} II P(u)
(11)
UEU uo VEC
UEU
where for every exogenous U E U, P(U) is a discrete distribution over a finite domain {1, with cardinality du = E [Ara(cy): C(U) S C are c-components covering U.
du
Henceforth, will refer to the family of SCMs with finite cxogenous domain defined in Thm. 2 as C-canonical SCMs. For concreteness, consider the causal diagram in Fig. La with X2, Y. Z, E
(0, 1). Recall that for C = {1Z, W), (X,, Y), (X2, YJ, (Y)), C(U,) (1Z, and C(U2) {[Xi, YJ, (X2, (Y}). The cardinality of U, in C-canonical SCMs is di [P
[0..x..wl= = 8. Similarly, the cardinality of U/ in C-canonical SCMs is given by:
d2 = |Spaçxx,))) + [P + [Ppa(r))
2 + 2 + 2 = 64.
(12)
Thm. 2 implies that Q1Z, W], Q[x2, Y] in the diagram of Fig. la could be written as:
QIz, [] = Σ 111 = (f 21. un) = P(un)
(13)
Mi 1
Q]
Σ
11fx 12) 11f 2, u2) = y) P(uz)
(14)
lg==.....d
where P(U1), P(U2) are distributions over finite domains {l...., d {I..... d2), respectively.
Following the decomposition in Eq. (3). for any policy тi E ils, the interventional distribution P(Y d)))))) is a function of c-factors Q YJ, Q[2, W] and given by:
Pvy do(m))) = Σ ((]|z)
Σ
[[Z(mn) = (
I==l.....h
(15)
Σ
12fx)(z, =
= = p(22)

---

Observe in Thm. 2 cardinalities of exogenous domains rely on the total number of c-components in C. Next we introduce an effective method to reduce the model complexity of canonical SCMs by exploring identifiabl relationships among c-factors Q[C] contained in C.
Definition 2. For a causal diagram G and a c-collection C, c-factor Q[C], VC E C. identifiable Q[C] is uniquely computable from other c-factors Q[C") in C) (C). That is, QM, [C] = Qar, [C] for every pair of SCMs MI, M2 with 9M, = Gar, = G. and Qus, = Qus, [C") for any C' E (C))
In words, Q[C] is identifiable w.r.t. (G, (G,C) if it could be written as a function of c-factors in the remainder of the collection C' C [C). For instance, consider the the causal diagram of Fig. Ta and the c-collection C = { W), [.)]{. (X1,))),,..... [Xg, y). [Y}}) [36, Lem. 10] implies that c-factor Q[Y] identifiable from Q[ Y] and is given by Q
E., Q[X1, Y). For every pair of SCMs that generates the same set of c-factors in C' {[Z, W). (X,, Y), (X2, Y}}, they must also coincide in parameters of Q[Y]. It is thus sufficient to focus on representing parameters of c-factors in the subset C', which we call reduction of the original c-collection C.
Definition 3. For causal diagram G and a c-collection C, subset C' S C is said to be a reduction of C if obtained by successive removals of identifiable e-component C.
reduction C' is minimal if there exists no proper subset C" C' such that C" is a re- duction of C. To reduce the model complexity of candidate SCMs, it is always preferable to
Algorithm 2 MINCOLLECT
Input: Causal diagram G. c-collection C.
function MINCOLLECTÚ, C) 2: while C = FINDID C) ب do
1:
present c-components in a minimal reduction. Next we describe systematic procedure ob- tain a minimal reduction of c-collection C in a causal diagram G. Details of our algorithm, MINCOLLECT, are described in Alg. 2 edly removes identifiable c-factors Q (CC) from
3:
Let C = C (C).
4:
return C.
5:
function FINDID C)
repeat-
6:
for every pair C, C" E C.t. CC C" do if IDENTIPY(CC, C", ()) + FAIL then return C.
7:
collection C. The subroutine IDENTIFY [36] is
8:
a complete algorithm in determining the identi- fiability of Q[C] from another c-factor QIC"| such that C' C C². In particular, IDENTIFY returns formula estimating Q[C] from Q[C*] if the target query is identifiabl;; otherwise, returns "FAIL". It is possible to show that the greedy procedure in Alg. 2 always returns minimal reduction of C. Proposition 1. For a causal diagram G and a c-collection C, MINCOLLECT(C, C) returns a minimal reduction C* of C.
natural question arising at this point whether the order of removing c-components C could affect the output of MINCOLLECT. Fortunately, the next proposition shows that this is not the case. Proposition For a causal diagram 9, any c-collection C has a unique minimal reduction.
Consider again the c-collection C = {[Z.W), (X1, Y), (X2, Y}, (Y}) in the causal diagram of Fig. Ta Applying procedure MINCOLLECT 9) gives minimal reduction C* {1Z, W) YY {X2,Y) Therefore, it is sufficient to consider -cn-canonccal SCMs compatible wtih G when computing the optimistic policy in Eq. (5). Compared with C-canonical SCMs, the cardinality of U1 in a -a-cnnnncall SCM remains the same and equates to d1 |Spa(z,w) = 8. On the other hand, C* (U2) = ((x,, Y), (X2, Y}} and the cardinality of U2 is given by
(16) which is smaller than the cardinalty of U2 in C-canonical SCMs given by Eq. 12 One could then obtain an optimistic policy in Eq. (5) by solving a series of equivalent polynomial programs. For a more detailed survey on canonical SCMs and related work, refer readers to the complete technical Appendix CJ.
d2 [P x + (S
2 = 48
report 42
3.1 Thompson Sampling
The canonical representation of c- c-factors allows the optimization problem in Eq. (5) to be reducible to a series of equivalent polynomial programs. Nevertheless, solving polynomial optimization is NP-hard in general [ which means that applying CAUSAL-UCB* is still computationally challenging. This section introduces an alternative online algorithm that is computationally feasible, while achieving a similar asymptotic bound on the cumulative regret.
7

---

Our algorithm is based on the heuristics of Thompson sampling (TS) B3, 31 21 It maintains a prior distribution p(M over all possible SCMs M compatible with the causal diagram G. One may surmise that it is challenging to define such prior p since the agent does not have access to the parametric forms of the underlying SCM. Fortunately, it follows from the decomposition assume the exogenous domain to be discrete and finite without loss of generality. Particularly, we will consider a family of C -canonical SCMs where C* is a minimal reduction of c-collection C in G. The cardinality of domain of every U U is given by du = Ecec-(t) (t)) [Paa(C)l. We assume that probabilities of P(U) are drawn from uninformative Dirichlet priors; and J are drawn uniformly from the finite class of possible structural functions. That is, for every U E U and every V E V.
Thm.21the we could
P(U) Dir (a1,.... (01),..., Addy)
fv Unif (ΩPAY x Buy H Qv),
(17)
where 01
ade 1; SPAy x auv, + Gy class containing all functions mapping from finite domains of PAv. Uv to V, which must also contain only a finite number of elements.
Details of our algorithm, CAUSAL-TS**
Algorithm 3 CAUSAL-TS"
are described in Alg. 3 At each episode
updates the posterior distribution p(M V,) from collected samples V. (V,,..., V prior to episode t, and draws an estimate M, from the updated posteriors. Similar Bayesian causal in- ference approaches 7 43), we will obtain
1: Input: Causal diagram G. policy space ITg, prior p.
2: for all episodes / = 1, 1,2,.... do
3: Sample an SCM M, p (M Vi).
4: Compute an optimal policy n. such that
Te arg max E,, [Y] do(z)] *ells
(18)
a posterior sample M p(M] V.)) using Gibbs sampling [10]. In Step 4, CAUSAL- 5: Perform do (TT) and observe (t).
TS* computes an optimistic policy mi that
maximizes the expected outcome TE[Y do(z)] induced by the sampled SCM M. Finally, the agent exccutes Ne throughout episode t and new samples V, are collected.
Following previous work 128] 21 22). we will assess the performance of TS using the Bayesian cumulative regret up episode T. i.e., R(T, p) EE [R[T, M) M p(M)], where the expectation is taken with respect to the prior distribution over M. There exists a general relationship between TS and UCB algorithms many model classes [28]. This allows one convert regret bounds developed for CAUSAL- UCB into Bayesian regret bounds for CAUSAL-TS* Formally,
Theorem 3. Given causal diagram G, a mixed policy scope 3, and prior distribution p. it holds for any > 1, the regret of CAUSAL-TS* is bounded by
R(T.P) S 26A(G.
(19)
Compared with Thm. 1 the above regret bound implies that CAUSAL-TS* achieves similar asymptotic performance as CAUSAL-UCB Particularly, Alg. requires one only has to find an optimal policy ne in a specific SCM Mr. while in Alg. []] parameters of M, are imprecise, bounded in the hypothesis class Mr. There exist effective planning algorithms in finding optimal policies in structured environment provided with detailed parameterization of the underlying SCM [15 This implies that CAUSAL-TS* is more computationally feasible compared to CAUSAL-UCB*
4 Simulations
In this section, we evaluate the performance of our algorithms on randomly generated SCMs in various types of causal diagrams. After all, our algorithms can consistently find the corresponding optimal policies with mixed scopes. Further leveraging causal relationships in the underlying environment accelerates the convergence rate of online learners. In all experiments, we evaluate the novel CAUSAL-TS* with uninformative Dirichlet priors over exogenous probabilities and uniform priors over structural functions, which we label c-ts*, As baseline, we also include randomized trials (ret) allocating treatments in all possible scopes uniformly at random, standard Thompson sampling algorithm (1s) using all deterministic policies arms, and Thompson sampling over simplified mixed scope (Is*), which is obtained by applying graphical conditions in [18]. For all algorithms, we measure their cumulative regrets over T = 1.1 x 10 episodes. We refer readers to the technical report 42 Appendix B] for a more detailed discussion on the experimental set-up.
8

---

50
50
50
40
40
40
-0
30
30
20
*rct
20
0
"rct
20
0
rct
ets
ets
ts
10
tss
10
tts
ts
cctts
C-ts
08
0
200
400
600
800
1000
200
400
600
800
1000
0
200
400
600
800
1000
(a) Experiment
(b) Experiment 2
(c) Experiment 3
Figure 3: Simulations comparing online learners that are randomized (rct), adaptive (ts), adaptive with simplified policy scopes (t,*), and causally enhances (c-ts *). x--xle represents total episodes and y-axle for the cumulative regret. Figures are rendered in high resolution and can be zoomed in.
Experiment 1 Consider again the causal diagram and policy scopes described in Fig. 1 We ran- domly generate 100 instances of SCMs in Fig. Ia| with binary X1, Xx, Z, W.Y E {0. 1). Exogenous variables UT. U2 are discrete, taking values in finite domains with cardinalities d₁ = 16, d2 = 48 respectively. Thm. 2 and Prop. | implies that this parametric family is sufficient to generate all possible effected reward of candidate policies in Fig. | The cumulative regrets averaging over random SCMs are reported in Fig. 3a Our analysis reveals that c-1s consistently outperforms is and ty since it is able to reuse samples induced by policies with mixed scopes by exploiting underlying causal knowledge. The performance of ts and Is* coincide since none of scopes S1 S2, S1,2 2 is consistently redundant suboptimal. Unsurprisingly, ret performs the worst among all algorithms.
Consider the causal diagram in Fig. 4 where where Y rep- resents cardiovascular disease, W blood pressure, X, taking an antihyper- tensive drug, and X2 the use of an anti-diabetic drug [88. Our goal is to evaluate policies with scopes S = {(1,, }, S2 = (X2, 0)} and S1,2 {(X1, 0), (X2, {X) We randomly generate 100 SCMs in Fig. 4 with bi- nary X2, W. E 13. Exogenous variables U1 U2. U3 are drawn from distributions over finite domains with cardinalities d1 = =8, d2 12,dz 16 respectively. It follows from Thm. such a parametric family is able to gen- crate all expected rewards of policies with scopes S2 S1.2. Simulation results, shown in Fig. [3b reveal that the performance of is and 1s* coincide; the causal approach c-ts* consistently dominates Is and t: and finally, ret performs the worst among all strategies.
Experiment 2
U2
Ua
W
Figure 4
Experiment 3 Consider the causal diagram in Fig. 2 and policy scopes S = {( { S (22, 2. } and S1,2 {(X,, (2)), (X2, {X1, 2}) J. We randomly generate 100 SCMs in Fig. 2 with binary X1,X,, Z,Y E 10. Exogenous variables U1, U2 are drawn from categorical distributions over domains with cardinalities d1 = 2, d2 24 respectively. Fig. [c shows cumulative regrets averaging over random SCMs for all algorithms. Simulation results reveal that c-ts* consis- tently dominates other algorithms; is improves over ts since it does not explore the redundant policy scope S1.2. As expected, rel performs the worst among all learning strategies.
5 Conclusions
This paper investigated the online reinforcement learning for selecting an optimal treatment regimen from a policy space characterized with mixed state-action scopes. We first presented an online algorithm (Alg. [ that achieves sublinear regret but is computationally intractable for any moderated- size instance. We further introduced a novel type of parametrizations for general SCMs (Thm. 2 with finite observed and latent domains, that could represent an arbitrary subset of interventional distributions in a causal diagram using the minimal number of decomposing factors, called c- components. We then developed more computationally efficient online algorithm (Alg. 33. based on the heuristics of Thompson sampling, that identifies an optimal policy with the same sample complexity. today's healthcare, the growing use of combination therapies opens new opportunities in designing effective regimens by combining multiple treatments. The additional degrees of freedom present challenges in comparing different treatment regimens. We believe that our results constitute a significant step towards the development of more principled science of personalized medicine.

---

Acknowledgments and Disclosure of Funding
This research was supported in part by the NSF, ONR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation.
References
[1] Auer, Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2/3):235-222 2002.
[2] P. Auer, T. Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning. In Advances neural information processing systems, pages 89-96, 2009.
[3] K. Azizzadenesheli, A. Lazaric, and A. Anandkumar. Reinforcement learning of pomdp's 's using spectral methods. In COLT, 2016.
[4] E. Barcinboim and J. Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113:7345-7352, 2016.
[5] N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):14441142, 2012.
[6] W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages 151-159, PMLR, 2013.
[7] D. Chickering and J. Pearl. A clinician's 's tool for analyzing non-compliance. Computing Science and Statistics, 29(2):424-443 431, 1997.
[8] M. R. Garey and D. S. Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.
[9] Z. D. Guo. S. Doroudi, and E. Brunskill. A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pages 510-518, 2016.
[10] H. Ishwaran and F. James. Gibbs sampling methods for breckirg priors. Journal of the American Statistical Association, 96(453):611-13,, 2001.
[11] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563 1600, 2010.
[12] D. Koller and Milch. Multi-agent influence diagrams for representing and solving games. Games and economic behavior, 45(1):181-221, 2003.
[13] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[14] Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96-1, 2007.
[15] S. L. Lauritzen and D. Nilsson. Representing and solving decision problems with limited information. Management Science, 47(9):1235-12511 2001.
[16] S. Lee and E. Bareinboim. Structural causal bandits: where to intervene? Advances in Neural 2018.
Information Processing Systems, pages
[17] 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.
[18] Lee and E, Bareinboim. Characterizing optimal mixed policies: Where to intervene and what to observe. Advances in Neural Information Processing Systems, 33, 2020.
[19] M. Magill and L. A. Ray. Dognitive-behavione treatment with adult alcohol and illicit drug users: meta-analysis of randomized controlled trials. Journal of studies on alcohol and drugs, 1064):5 2009.
10

---

[20] S. A. Murphy, M. J. van der Laan, J. M. Robins, and Conduct Problems Prevention Research Group. Marginal Mean Models for Dynamic Regimes. Journal of the American Staristical Association, 96445))1110-1422, Dec. 2001.
[21] I. Osband, D. Russo, and B. Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[22] I. Osband and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Proceedings of the 34th International Conference on Machine Learning-Volie Volume 70, pages 2701-2710. JMLR. org, 2017.
[23] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, 2000.
[24] D. Precup, R. S. Sutton, and S. P. Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the Seventeenth International Conference Machine Learning, pages 759-766, 2000.
[25] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
[26] H. Robbins. Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc., 58(5):527-535, 09 1952.
[27] D. Rosset, N. Gisin, and E. Wolfe. Universal bound the cardinality of local hidden variables in networks. Quantum Information and Computation, 18(1 18(11&12):91000922 2018.
[28] D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 12141132 2014.
[29] P. Spirtes, C. N. Glymour, and R. Scheines. Causation, prediction, and search. MIT press, 2000.
[30] A. Strehl, L. Li, E. Wiewiora, J. Langford, and M. Littman. Pac model-free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pages 881-888. ACM, 2006.
[31] M. Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pages 943-950, 2000.
[32] R. S. Sutton, H. R. Maei, and C. Szepesvári. A convergent (n) femporal-difference algorithm for off-policy learning with linear function approximation. In Advances in neural information processing systems, pages 1609-1616, 2009.
[33] A. Swaminathan and T. Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference Machine Learning, pages 814-823, 2015.
[34] I. Szita and C. Szepesvári. Model- based reinforcement learning with nearly tight exploration complexity bounds. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 1031-1038, 2010.
[35] 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-25 2944, 1933.
[36] J. Tian. Studies in Causal Reasoning and Learning. PhD thesis, Computer Science Department, University of California, Los Angeles, CA, November 2002.
[37] J. Tian. Identifying dynamic sequential plans. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI08, pages 554-561, Arlington, Virginia, United States, 2008, AUAI Press.
[38] J. Tian and J. Pearl. A general identification condition for causal effects. In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), pages 567-573, Menlo Park, CA, 2002. AAAI Press/The MIT Press.

---

[39] J. Zhang and E. Bareinboim. Transfer learning in multi armed bandits: a causal approach. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 1340-1346. AAAI Press, 2017.
[40] J. Zhang and E. Bareinboim. Near-optimal reinforcement learning in dynamic treatment regimes.
In Advances in Neural Information Processing Systems, pages 13401-13411, 2019.
[41] J. Zhang and E. Bareinboim, Designing optimal dynamic treatment regimes: A causal reinforce- ment learning approach. In International Conference on Machine Learning, pages 1011--1022. PMLR, 2020.
[42] J. Zhang and E. Bareinboim. Online reinforcement learning for mixed policy scopes. Number R-84, 2022.
[43] Zhang, T. Jin, and E. Bareinboim. Partial counterfactual identification from observational and experimental data. In Proceedings of the 39th International Conference on Machine Learning (ICML-22), 2022.
12


Reviews:
[{"review_id": "ycgYSr9r4Y_", "reviewer": "Reviewer_CZeJ", "summary": "This paper considers online policy learning with different policy scopes in the context of causal inference. The paper develops online learning algorithms with sub-linear regrets and presents simulation results of the theoretical algorithms. ", "questions": "My only question is regarding the statement that most of the works are based on the offline learning setting. However, I do have an impression that there are many causal learning algorithms (even on the practical RL side) that are online. Is the major difference here primarily about the policy scopes?", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First of all, I have to be frank that I'm only knowledgeable of causal inference as a practical RL person. So most of my comments are from a rough understanding of this draft. \n\nI feel the paper is clearly written with rigorous (possibly textbook-style) formulations and derivations. The motivation is clear, and all the proofs and introduced algorithms look correct. The simulation results also look reasonable as a theoretical paper. Although I cannot confidently judge the novelty of this work, I would still rate it positive for this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "chyi235UtBb", "reviewer": "Reviewer_jKpZ", "summary": "The paper considers regret-minimizing algorithms for selecting an optimal treatment regime from a policy space characterized with mixed state-action scopes. \n\nMore precisely, the authors focus on a structural causal model, motivated by medical applications, where they present two algorithms: a UCB-based one, which however requires intractable planning, and Thompson sampling relaxation, which appears to be “less intractable” (i.e., the computational issue is about finding a near-optimal policy on a fixed MDP).\n\nThey show improvements compared to a naive baseline as well as theoretically over naive UCB.", "questions": "None of relevance, other than the computational tractability discussed above", "limitations": "Discusses above", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert of the model assumed here, so I can only give high-level comments.\nThe authors use some standard technology (e.g., UCB, Thompson sampling) in the structural causal model. To be clear, both UCB and Thompson sampling need to be adapted, so there is some novelty in the work. They provide also a limited empirical evaluation. I suppose that the empirical evaluation needs to be restricted to small works since it might be too expensive to run these algorithm large scale.\nOverall, the work is in an interesting positions, towards a possible application, all the while doing some theoretical contribution.\nHowever, I am not familiar enough with the the causal literature to strongly support the work here.\n\nThe authors should discuss the computational consideration of finding a near-optimal policy on a fixed MDP in a better fashion. As I understand, even the Thomspon sampling-based algorithm could be intractable. This is of course strictly a limitation of planning and not of the proposal here, but it should nonetheless be discussed in more depth.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YU2iyaLCiVp", "reviewer": "Reviewer_NrX5", "summary": "This paper considers the problem of effective *online* learning of optimal policies with mixed scopes (e.g. different types of treatments) in an arbitrary causal system.\nThe authors propose an algorithm (CAUSAL-UCB) to solve the problem and prove that it achieves sublinear regret.\nFurthermore, to improve computational efficiency, the authors introduce a canonical representation for structural casual models and consider minimal reduction of c-components, then propose CAUSAL-TS as an easy-to-implement alternative.\nThe TS algorithm is evaluated on simple causal graphs to demonstrate its advantage over simple baselines.", "questions": "- For Theorem 3, I don't think we can convert UCB regret to TS regret for arbitrary problem instances. Please include exact conditions in the Theorem statement and rigorous proof.\n\n- Is it possible to extend the current algorithm to endogenous variables with possibly infinite support? What would be the difficult part? Or, if this is too much, it is good to at least provide experimental results where the endogenous variables take more than two values.\n\n- Please include a summary of notations in the appendix. It would be great if more intuitive explanations in words can be provided (e.g. what do they mean / why do they matter).", "limitations": "All my concerns are listed in the previous sessions. Please respond to questions and suggestions raised in \"Questions\".\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- Originality\n    - This paper introduces the novel problem of effective *online* learning of optimal policies with mixed scopes in an arbitrary causal system. The authors provide a UCB-based algorithm that solves this problem, as well as new ideas to improve computational efficiency.\n    - Relevant works are cited, and the authors make the contribution clear.\n- Clarity\n    - The paper is overall well-structured, and I can get the main points quickly.\n    - The paper is heavy in notations, but the authors make use of simple examples to explain them.\n- Significance\n    - I think the problem considered in this paper is very important and relevant in practice, and the current paper can motivate more research in online learning and causal inference.\n\n**Weaknesses**\n- Quality\n    - Certain claims (e.g. Theorem 3) do not seem well-supported. Seem Questions session for details.\n    - The instances in the experiments are somewhat over-simple.\n- Clarity\n    - This paper is VERY heavy in notations, and I find it hard to memorize and digest some of these notations when I first read the paper. A summary table is highly recommended.\n- Significance\n    - The algorithm heavily depends on the assumption that endogenous variables have finite supports. But in many practical settings, many endogenous variables are not discreet (especially for contexts), so I'm a bit doubtful about the practicality of the proposed methods.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I5R8HZjEWi", "reviewer": "Reviewer_NFf7", "summary": "The paper provides an algorithm for online learning in causal systems with mixed policy scopes that has sub-linear regret.  Results are presented on (small) simulated domains.", "questions": "- Can you provide more detailed analysis of the space/time analysis for the algorithms CAUSAL-UCB* and the MINCOLLECTs?    The simulation results suggest this is limited to very small number of state/action variables; is this due to learning efficiency (in terms of #samples) or computational efficiency (in terms of memory/#operations)?  Could you include simulation results as a function of different factors (delta, #states/actions)?\n- Considering Experiment 2, only blood pressure is considered as a variable (not even age, gender and other well-known contributing factors).  Is this because the method is limited to such small domain?  Or because it necessitates strong assumptions?   \n", "limitations": "- The paper does not really discuss technical limitations of the work, except where it serves to motivate the proposed approach.\n- There could be a deeper discussion of the ethical aspects of this work, given the proposed application to selecting optimal treatment regime, and the example on patients with cardiovascular disease.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(+)\tThe paper is motivated by real-world practical problem in treatment optimization.\n\n(+)\tThe paper is well grounded in terms of theoretical framework and includes results on sub-linear learning rate for the proposed setting.\n\n(+)\tThe results of sub-linear regret appear sound theoretically and are confirmed by simulations.\n\n(-)\tI wonder how useful & interesting is the proposed setting, grounded in causal learning, compared to more standard MDP settings.  I’m less familiar with this literature (but very familiar with MDP/RL literature), and it made it quite challenging to follow precisely the setting, algorithm and theoretical analysis.\n\n(-)\tThe proposed method appears limited to very small settings (few variables). I do not find the results very convincing given their simplicity.  See specific questions below about Experiment 2.\n\n(-)\tThe empirical results show an improvement for the proposed c-ts* method, compared to Thompson sampling alternatives. However the gap seems relatively small and both approaches seem sub-linear.  How do you know if the improvement of c-ts* is significant?  Is the results really meaningful?  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept