Towards
Causal Reinforcement Learning(CRL)
Elias Bareinboim
Causal Artificial Intelligence Lab
Columbia University(@eliasbareinboim)

Slides: https://crl.causalai.net

ICML, 2020

JOINT WORK WITH
CAUSAL AI LAB & COLLABORATORS
Yotam Alexander (Columbia) Judea Pearl (UCLA)
Juan Correa (Columbia)

Carlos Cinelli (UCLA)

Kai-Zhan Lee (Columbia)

Andrew Forney (UCLA)

Sanghack Lee (Columbia)

Brian Chen (Brex)Adele Ribeiro (Columbia)

Jin Tian (Iowa State)

Kevin Xia (Columbia)

Duligur Ibeling (Stanford)

Junzhe Zhang (Columbia)

Thomas Icard (Stanford)

Amin Jaber (Purdue)

Murat Kocaoglu (IBM)

Chris Jeong (Purdue)

Karthikeyan Shanmugam (IBM)Yonghan Jung (Purdue)

Jiji Zhang (Lingnan University)

Daniel Kumor (Purdue)

Paul Hünermund (Copenhagen)CausalAI Lab
Structural Causal Models
1. Explainability

2. Decision-Making(Effect identificationand decomposition,
Bias Analysis andFairness, Robustness
and Generalizability)(Reinforcement Learning,
Randomized Controlled Trials,
Personalized Decision-Making)

3. Applications, Education, Software
Data Science:Principled (“scientific”) inferencesfrom large data collections.

AI-ML:
Principles and tools for designingrobust and adaptable learning systems.
3What is Causal RL?
• Reinforcement Learning (RL) is awesome at handlingsample complexity and credit assignment.
• Causal Inference (CI) is great at leveraging structuralinvariances across settings and conditions.
• Can we have the best of both worlds? Yes!
Simple solution:

Causal RL = CI + RL

Our goal: Provide a cohesive framework that takes advantageof the capabilities of both formalisms (from first principles), andthat allows us to develop the next generation of AI systems.
4Outline(60’)• Part 1. Foundations of CRL• Intro to Structural Causal Models, Pearl Causal
Hierarchy (PCH), Causal Hierarchy Theorem (CHT)• Current RL & CI methods through CRL Lens
• Part 2. New Challenges and Opportunities of
Causal Reinforcement Learning(60’)

Goal: Introduce the main ideas, principles, and tasks.
Not focused on the implementation details.
For a more detailed discussion, see: NeurIPS’15,
PNAS’16, ICML’17, IJCAI’17, NeurIPS-18, AAAI-19,
UAI-19, NeurIPS-19, ICML-20 … + new CRL survey.

Resources: https://crl.causalai.net

5PRELUDE:

REINFORCEMENT LEARNING

6

What’s Reinforcement Learning?
• Goal-oriented learning -- how to
maximize a numerical reward signal.
• Learning about, from, and whileinteracting with an external environment.
• Adaptive learning -- each action is
tailored for the evolving covariates andactions’ history.
(Learning without having a full specification of
the system; versus planning/programming)

7

RL - Big Picture
Parameters
about the env.

Agent
Θ, G

context / state

actionEnvironment

reward88

RL - Big Picture
Parameters
about the env.

Agent
Θ, G

context / state

actionEnvironment

reward• Receive feedback in the form of rewards.
• Agent’s utility is defined by the reward function.
• Must (learn to) act so as to maximize expected rewards. 88

Causal RL - Big Picture
context / state

Agent
Θ, G

actionEnvironmentMrewardCausal Graph

Structural Causal Model
99

Causal RL - Big Picture
context / state

Agent
Θ, G

‘action’EnvironmentMrewardCausal Diagram

Structural Causal Modelobservational, interventional, counterfactual1111

Two keyRL
observations(RL → CRL):
Causal- Big Picture

1. The environment and the agent will betied thr. the pair SCM M & causal graph G.
context / state

2. We’ll define diﬀerent types of “actions”, orinteractions, to avoid ambiguity (PCH).

Agent
Θ, G

‘action’EnvironmentMrewardCausal Diagram

Structural Causal Modelobservational, interventional, counterfactual1111

Two keyRL
observations(RL → CRL):
Causal- Big Picture

1. The environment and the agent will betied thr. the pair SCM M & causal graph G.
context / state

2. We’ll define diﬀerent types of “actions”, orinteractions, to avoid ambiguity (PCH).
‘action’and understandLet’sdefineAgentEnvironment(1) G
the pair <M, G>, and (2)Θ,Mthe PCH.
rewardCausal Diagram

Structural Causal Modelobservational, interventional, counterfactual1111

STRUCTURAL CAUSAL MODELS& CAUSAL GRAPHS

12

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes
Drug ← fD (Age, UD)
Headache ← fH(Drug, Age, UH)G=

Z (Age)X(Drug)Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes
Drug ← fD (Age, UD)
Headache ← fH(Drug, Age, UH)G=• Intervention
Drug ← Yes

Z (Age)X(Drug)Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)X(Drug)Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

rand()
Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)X(Drug)Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention(Age)
Drug ← fD (Age, UD)
Drug ← ∏Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)X(Drug)Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention(Age)
Drug ← fD (Age, UD)
Drug ← ∏Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)X(Drug)

σ-calculus (Correa& Bareinboim 2020)

Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention(Age)
Drug ← fD (Age, UD)
Drug ← ∏Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)X(Drug)Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)X(Drug)Y(Headache)P(Z, X, Y)(observational)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Gdo(X) =Z (Age)Z (Age)Yes
X(Drug)Y(Headache)P(Z, X, Y)(observational)

X(Drug)Y(Headache)P(Zx=yes, Yx=yes) = P(Z, Y | do(X = Yes))(interventional)(counterfactuals)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)Gdo(X) =Z (Age)Yes
X(Drug)Y(Headache)P(Z, X, Y)(observational)

X(Drug)Y(Headache)P(Z, Y | do(X = Yes))(interventional)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)Features
X(Drug)

DecisionY(Headache)P(Z, X, Y)(observational)

OutcomeGdo(X) =Z (Age)Yes
X(Drug)Y(Headache)P(Z, Y | do(X = Yes))(interventional)
13

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)Features
X(Drug)

DecisionY(Headache)P(Z, X, Y)(observational)

OutcomeGdo(X) =Z (Age)Yes
X(Drug)Y(Headache)P(Z, Y | do(X = Yes))(interventional)

14

SCM -- REPRESENTINGTHE DATA GENERATING MODEL• Processes• Intervention

Drug ← fD (Age, UD)
Drug ← Yes
Headache ← fH(Drug, Age, UH) Headache ← fH (Drug, Age, UH)G=

Z (Age)Features
X(Drug)

DecisionY(Headache)P(Z, X, Y)

Seeing(observational)

OutcomeGdo(X) =Z (Age)Yes
X(Drug)Y(Headache)P(Z, Y | do(X = Yes))

Doing(interventional)

14

STRUCTURAL CAUSAL MODELS
Definition: A structural causal model M (or, data
generating model) is a tuple (V, U, F, P(u)), where• V = {V1,...,Vn} are endogenous variables,• U = {U1,...,Um} are exogenous variables,• F = {f1,..., fn} are functions determining V,
for each Vi, Vi ← fi(Pai, Ui), where Pai ⊂ V, Ui ⊂ U.
• P(u) is a distribution over U.
(Axiomatic characterization [Halpern, Galles, Pearl, 1998].)

Prop. SCM M implies Pearl Causal Hierarchy (PCH).
15

PEARL CAUSAL HIERARCHY (PCH)16

PEARL CAUSAL HIERARCHY (PCH)(LADDER OF CAUSATION)

16

SCM → PEARL CAUSAL HIERARCHY (PCH)
Layer (Symbol)

P(y | x)QuestionDoing

P(y | do(x), c) ML - Reinforcement

What if?
What if I do X?

Causal BN, MDP

P(yx | x’, y’)ExamplesWhat does asymptom tell us
about thedisease?
What if I takeaspirin, will myheadache be
cured?

Was it theaspirin that
acted differently? stopped myheadache?
Structural Causal Model

L3 Counterfactual!

Activity

Seeing

L2 Interventional"

TypicalWhat is?
ML - (Un)Supervised How would
seeing X change
DT, Bayes net,
my belief in Y?
Regression, NN

L1 Associational#

TypicalImagination, Why?
Introspection What if I had

18

SCM → PEARL CAUSAL HIERARCHY (PCH)
L1

Layer (Symbol)

QuestionDoing

P(y | do(x), c) ML - Reinforcement

What if?
What if I do X?

Causal BN, MDP

P(yx | x’, y’)Imagination, Why?
Introspection What if I had

L3

Examplesless aWhat does
detailed
symptomtell usabout thedisease?
What if I takeaspirin, will myheadache be
cured?

Was it theaspirin that
acted differently? stopped mymoreheadache?
Structural Causal Modeldetailed

description of environment

P(y | x)L3 Counterfactual!

Activity

Seeing

L2 Interventional"

TypicalWhat is?
ML - (Un)Supervised How would
seeing X change
DT, Bayes net,
my belief in Y?
Regression, NN

L1 Associational#

Typical

L2

18

CAUSAL HIERARCHY THEOREM

LL[Bareinboim, Correa, Ibeling, Icard, 2020]

Given that an SCM M → PCH, we can show the following:
Theorem (CHT). With respect to Lebesgue measureover (a suitable encoding of L3-equivalence classesof) SCMs, the subset in which any PCH ‘collapse’ ismeasure zero.
Informally, for almost any SCM (i.e., almost any possible
environment), the PCH does not collapse, i.e., the layersof the hierarchy remains distinct.
collapse
L1

L2 L3

L1,L2,L3

Corollary. To answer question at Layer i (about a certain
interaction), one needs knowledge at layer i or higher. 19

WHY IS CAUSAL INFERENCE “NON-TRIVIAL”?
SCMs ARE ALMOST NEVER OBSERVED
SCM M
X ← fx(Uy)Y ← fy(X, Uy)
P(Ux, Uy)

20

WHY IS CAUSAL INFERENCE “NON-TRIVIAL”?
SCMs ARE ALMOST NEVER OBSERVED
SCM M
X ← fx(Uy)Y ← fy(X, Uy)
P(Ux, Uy)

L1

P(y, x)L2

P(y | do(x))

L3P(yx | x’, y’)
20WHY IS CAUSAL INFERENCE “NON-TRIVIAL”?
SCMs ARE ALMOST NEVER OBSERVED
SCM M
X ← fx(Uy)Y ← fy(X, Uy)
P(Ux, Uy)

L1

P(y, x)L2

P(y | do(x))

L3P(yx | x’, y’)
20WHY IS CAUSAL INFERENCE “NON-TRIVIAL”?
SCMs ARE ALMOST NEVER OBSERVED
SCM M
X ← fx(Uy)Y ← fy(X, Uy)
P(Ux, Uy)

L1

P(y, x)L2

P(y | do(x))

Exceptions:- Physics- Chemistry- Biology

L3

P(yx | x’, y’)
20WHY IS CAUSAL INFERENCE “NON-TRIVIAL”?
SCMs ARE ALMOST NEVER OBSERVED
SCM M
X ← fx(Uy)Y ← fy(X, Uy)
P(Ux, Uy)

L1

P(y, x)L2

P(y | do(x))

L3P(yx | x’, y’)
20WHY IS CAUSAL INFERENCE “NON-TRIVIAL”?
SCMs ARE ALMOST NEVER OBSERVED
SCM M
X ← fx(Uy)Y ← fy(X, Uy)
P(Ux, Uy)

L2

L1

P(y, x)SeeingP(y | do(x))

?

Doing

L3

P(yx | x’, y’)
20WHY IS CAUSAL INFERENCE “NON-TRIVIAL”?
SCMs ARE ALMOST NEVER OBSERVED
SCM M
X ← fx(Uy)Y ← fy(X, Uy)

Unobserved
EnvironmentP(Ux, Uy)

L1

L2

P(y, x)P(y | do(x))

SeeingDoing

L3

P(yx | x’, y’)Interactions/ Views
20

ENCODING STRUCTURAL CONSTRAINTS— CLASSES OF CAUSAL GRAPHS
SCM M
X ← fx(Uy)Y ← fy(X, Uy)
P(Ux, Uy)

L1

L2

P(y, x)P(y | do(x))

SeeingDoing

L3

P(yx | x’, y’)21

ENCODING STRUCTURAL CONSTRAINTS— CLASSES OF CAUSAL GRAPHSSCM M

Causal Graph G(Strucutral Constraints)

X ← fx(Uy)Y ← fy(X, Uy)

1. Templates (MAB, MDP)

P(Ux, Uy)
2. Knowledge Engineering

3. Causal Discovery

L1

L2

P(y, x)P(y | do(x))

SeeingDoing

L3

P(yx | x’, y’)21

KEY POINTS (SO FAR)•

The environment (mechanisms) can be modeled as an SCM• SCM M (specific environment) is rarely observable•

Still, each SCM M can be probed through qualitatively different
types of interactions (distributions) -- the PCH -- i.e.:! L1: Observational! L2: Interventional! L3: Counterfactual

CHT (Causal Hierarchy Thm.): For almost any SCM, lower
layers (say, Li) underdetermines higher layers (Li+1).
• This delimits what an agent can infer based on the different
types of interactions (and data) it has with the environment;• For instance, from passively observing the environment (L1),
it cannot infer how to act (L2).
• From intervening in the environment (L2), it can’t infer how
things would have been had she acted differently (L3).
• Causal Graph G is a surrogate of the invariances of the SCM M.
•

22

CURRENT METHODS IN RL & CI
THROUGH CRL LENS

23

REINFORCEMENT LEARNING
AND CAUSAL INFERENCE
Goal: Learn a policy ∏ s.t. sequence of actions ∏(.) =(X1, X2…, Xn) maximizes reward E∏[Y | do(X)].
Current strategies found in the literature (circa 2020):
1. Online learning• Agent performs experiments herself• Input: experiments {(do(Xi), Yi)}; Learned: P(Y | do(X))

Offline2. Off-policy learning• Agent learns from other agents’ actions• Input: samples {(do(Xi), Yi)}; Learned: P(Y | do(X))

3. Do-calculus learning• Agent observes other agents acting• Input: samples {(Xi, Yi)}, G; Learned: P(Y | do(X))

24

REINFORCEMENT LEARNING
AND CAUSAL INFERENCE
Goal: Learn a policy ∏ s.t. sequence of actions ∏(.) =(X1, X2…, Xn) maximizes reward E∏[Y | do(X)].
Current strategies found in the literature (circa 2020):

Offline"1. Online learning (→ do(x))• Agent performs experiments herself• Input: experiments {(do(Xi), Yi)}; Learned: P(Y | do(X))"
2. Off-policy learning (do(x)" → do(x))• Agent learns from other agents’ actions• Input: samples {(do(Xi), Yi)}; Learned: P(Y | do(X))"# → do(x))
3. Do-calculus learning (see(v)• Agent observes other agents acting• Input: samples {(Xi, Yi)}, G; Learned: P(Y | do(X))

24

REINFORCEMENT LEARNING
AND CAUSAL INFERENCE
Goal: Learn a policy ∏ s.t. sequence of actions ∏(.) =(X1, X2…, Xn) maximizes reward E∏[Y | do(X)].
Current strategies found in the literature (circa 2020):

Offline1. Online learning (→ do(x))• Agent performs experiments herself• Input: experiments {(do(Xi), Yi)}; Learned: P(Y | do(X))
2. Off-policy learning (do(x) → do(x))• Agent learns from other agents’ actions• Input: samples {(do(Xi), Yi)}; Learned: P(Y | do(X))

3. Do-calculus learning (see(v) → do(x))• Agent observes other agents acting• Input: samples {(Xi, Yi)}, G; Learned: P(Y | do(X))

24

1. ONLINE LEARNING• Finding x* is immediate once E[Y | do(X)] is learned.
• E[Y | do(X)] can be estimated through randomized
experiments or adaptive strategies.
• Pros: Robust against unobserved confounders (UCs)• Cons: Experiments can be expensive or impossible
U

U
∏

X

Y

Pre-randomization(passive world)

experimentfollowing ∏XYPost-randomization(active)25

1. ONLINE LEARNING• Finding x* is immediate once E[Y | do(X)] is learned.
• E[Y | do(X)] can be estimated through randomized
experiments or adaptive strategies.
• Pros: Robust against unobserved confounders (UCs)• Cons: Experiments can be expensive or impossible
U

U
∏

X

Y

Pre-randomization(passive world)

experimentfollowing ∏XYPost-randomization(active)* More details: [Fisher, 1936; Auer et al., 2002; Jaksch et al., 2010; Lattimore et al., 2016]. 25

1. ONLINE LEARNING(interventional learning)
U

U
Π

X

Y

Pre-randomizationworld (passive)

X
experimentfollowing ∏Yunder do(X)Agentno dataEx~π[Y | do(x)]do(x0) do(x1) …

* Online learning can be improved thr. causal machinery [ZB, ICML’20].

do(x0)
26

NOTE: COVARIATE-SPECIFICCAUSAL EFFECTS (CONTEXTUAL)• Model can be augmented to accommodate set ofobserved covariates C (also known as context); U is
the set of (remaining) unobserved confounders (UCs).
U» Challenge:
high-dimensional C
Y (reward)(decision) X

Deep learningC• Goal: learn a policy ∏(c) so as to optimize based on
the c-specific causal effect, P(Y | do(X), C = c).
27

2. OFF-POLICY LEARNING• E[Y | do(X)] can be estimated through experiments
conducted by other agents and different policies.
• Pros: no experiments need to be conducted• Cons: rely on assumptions that (a1) same variables
were randomized and (a2) context matches (e.g., C = {}).
U

U
∏’

∏

X

Y

(a)

IPW
∏’ → ∏XY(b)* More details: [Watkins & Dayan, 1992; Dudik et al., 2011; Jiang & Li, 2016].

28

2. OFF-POLICY LEARNING
U

U

Π’

Π
X

Y

X

under do(X)under do(X)PΠ(x | c)PΠ(y | do(x)) =P (y, x, c)∑ Π′PΠ′(x | c)x,cOther agent with π’
Ex~π’[Y | do(x)]do(x0) do(x1) …

Y

do(x0)IPW

A lot of work here
since the variance
may blow up…

Agent
Ex~π[Y | do(x)]293. DO-CALCULUS LEARNING *• E[Y | do(X)] can be estimated from non-experimental
data (also called natural / behavioral regime)• Pros: estimation is feasible even when context is unknown
and experimental variables do not match (i.e., off-policy
assumptions are violated).
• Cons: Results are contingent on the model; for weakmodels, effect is not uniquely computable (not ID).
U

U
∏

X

Z

Passive-world
data-collection

do-calc
Y inference

X

Z

Y

Do-world(Post-interventional)* For details, see data-fusion survey [Bareinboim & Pearl, PNAS’2016].

30

3. DO-CALCULUS LEARNING
U

U
Π

X

Ζ

Causal Graph G

Y

X

Ζ
Y

under hypotheticaldo(X)ΣzP(z|x)Σx’P(y|x’,z)P(x’)
do-calc
inferenceengineObservation
P(Z,X,Y)Agent
Ex~π[Y | do(x)]obs, obs, …

obs

do(z), obs …

do(w)* For a more general treatment, see (LCB, UAI’19)

31

SUMMARY RL-CAUSAL (CIRCA 2020)
UU∏

1. Online(→ doπ(x))

X

Y

∏

X

Y
U

U
∏

∏’

2. Off-policy(doπ’(x) → doπ(x))

XYU(see(.) → doπ(x))

Z

X

Y

U

∏

3. Do-calculus
X

IPW

Y

Do-calcX

Do these strategies always work?

Z

Y

$
32

IS LEARNING IN INTERACTIVESYSTEMS ESSENTIALLY DONE?
IF NOT, WHAT IS MISSING?

33

TOWARDS
CAUSAL REINFORCEMENT LEARNING%
34

CRL NEW CHALLENGES& LEARNING OPPORTUNITIES (I)
Task 1 (IJCAI’17, NeurIPS’19, ICML’20)
Generalized Policy Learning(combining online + offline learning)

Task 2 (NeurIPS’18, AAAI’19)
When and where to intervene?
(refining the policy space)

Task 3 (NeurIPS’15, ICML’17)
Counterfactual Decision-Making(changing optimization function based on
intentionality, free will, and autonomy)

35

CRL NEW CHALLENGES& LEARNING OPPORTUNITIES (II)Task 4 (NeurIPS’14, PNAS’16, UAI’19, AAAI’20)
Generalizability & robustness of causal claims(transportability & structural invariances)
Task 5 (NeurIPS’17, ICML’18, NeurIPS’19)
Learning causal model by combining
observations (L1) and experiments (L2)
Task 6 (R-66 CausalAI)
Causal Imitation Learning@

36

TASK 1.
GENERALIZED POLICY LEARNING(Combining Online and Offline Learning)TASK 1.
GENERALIZED POLICY LEARNING(Combining Online and Offline Learning)Junzhe Zhang

CRL-TASK 1.
GENERALIZED POLICY LEARNING (GPL)• Online learning is usually undesirable due tofinancial, technical, or ethical constraints. In
general, one wants to leverage data collectedunder different conditions to speed up learning,
without having to start from scratch.
• On the other hand, the conditions required byoffline learning are not always satisfied in many
practical, real world settings.
• In this task, we move towards realistic learning
scenarios where these modalities come together,including when the most traditional, and provably
necessary, assumptions do not hold.
38

GENERALIZED POLICY LEARNING
Task 1. Input: P(x, y), learn: P(y | do(x)).

- Off-policy a2 ❌
- Do-calc ID ❌
- Online❓

- Robotics: learning by demonstration when the teacher
can observe a richer context (e.g., more accurate sensors).
- Medical: optimal experimental design from observational data.
FDA

Physician

U
X

U
Y

learning
task

X

Y

39

GENERALIZED POLICY LEARNING
Task 1. Input: P(x, y), learn: P(y | do(x)).

- Off-policy a2 ❌
- Do-calc ID ❌
- Online❓

- Robotics: learning by demonstration when the teacher
can observe a richer context (e.g., more accurate sensors).
- Medical: optimal experimental design from observational data.
FDA

Physician

U
X

U
Y

learningtask

X

Let’s ignore their differences, andpretend that physician and FDA areexchangeable — call “naive TS”.
In other words, “naive TS” attempts
to use observational data as prior.
Traditional TS means ignoring theobservational data.

Y

39

GENERALIZED POLICY LEARNING
Task 1. Input: P(x, y), learn: P(y | do(x)).

- Off-policy a2 ❌
- Do-calc ID ❌
- Online❓

- Robotics: learning by demonstration when the teacher
can observe a richer context (e.g., more accurate sensors).
- Medical: optimal experimental design from observational data.
FDA

Physician

U
X

U
Y

learningtask

X

Let’s ignore their differences, andpretend that physician and FDA areexchangeable — call “naive TS”.
In other words, “naive TS” attempts
to use observational data as prior.
Traditional TS means ignoring theobservational data.

Y

How could this be happening?!
Could more data be hurting?
39

GENERALIZED POLICY LEARNING
Task 1. Input: P(x, y), learn: P(y | do(x)).

- Off-policy a2 ❌
- Do-calc ID ❌
- Online❓

- Robotics: learning by demonstration when the teacher
can observe a richer context (e.g., more accurate sensors).
- Medical: optimal experimental design from observational data.
FDA

Physician

U
X

U
Y

learningtask

X

Let’s ignore their differences, andpretend that physician and FDA areexchangeable — call “naive TS”.
In other words, “naive TS” attempts
to use observational data as prior.
Traditional TS means ignoring theobservational data.

Y*

How could this be happening?!
Could more data be hurting?
39

E(Y | X = 0)
< E(Y | X = 1)
E(Y | do(X = 0)) > E(Y | do(X = 1))

Naive TS POLICY LEARNING
GENERALIZED- do-calc ID
Task 1a. Input: P(x, y), learn: P(y | do(x)).
Why is naive-TS- off-policy a2- Robotics: learning by demonstration when the teacher
can observe a richer context (e.g., more accurate sensors)- Medical: optimal experimental design from observational data.

doing so badly?

FDA-Chef

Master-ChefU

Utask 1

X

Traditional TS
X
YLet’s ignore their differences, andpretend that physician and FDA areexchangeable — call “naive TS”.
In other words, “naive TS” attempts
to use observational data as prior.
Traditional TS means ignoring theobservational data.

Y*

How could this be happening?!
Could more data be hurting?
40

Naive TS POLICY LEARNING
GENERALIZED- do-calc ID
Task 1a. Input: P(x, y), learn: P(y | do(x)).
Why is naive-TS- Robotics: learning by demonstration when the teacher - off-policy a2
can observe a richer context (e.g., more accurate sensors)- Medical: optimal experimental design from observational data.

doing so badly?

FDA-Chef

Master-ChefU

Can we do better?

Utask 1X

Y

X

Y

Let’s ignore their differences, pretendingthat student-and master-chef robots areinterchangeable — call “naive TS”.

n = 250

150
How200could this be happening?!
Could more data be hurting?

100
41Structural Explanation for Naive-TS’s behavior-- The Challenge of Non-Identifiability• SCM M (Unobserved)

X=U
P(U=0)=0.3• Causal Graph G

P[Y|X,U]

U=0

U=1

X=0

0.1

0.9

X=1

0.5

0.3

• Distributions

U

X

Y

E(Y | X = 0)
< E(Y | X = 1)
E(Y | do(X = 0)) > E(Y | do(X = 1))

E[Y|do(X)]

E[Y|X]

X=0

0.66

0.1

X=1

0.36

0.3

L2

L1

42

Structural Explanation for Naive-TS’s behavior-- The Challenge of Non-Identifiability• SCM M (Unobserved)

X=U
P(U=0)=0.3• Causal Graph G

P[Y|X,U]

U=0

U=1

X=0

0.1

0.9

X=1

0.5

0.3

• Distributions

U

X

Y

E(Y | X = 0)
< E(Y | X = 1)
E(Y | do(X = 0)) > E(Y | do(X = 1))

E[Y|do(X)]

E[Y|X]

X=0

0.66

0.1

X=1

0.36

0.3

L2

L1

42

Structural Explanation for Naive-TS’s behavior-- The Challenge of Non-Identifiability• SCM M (Unobserved)

X=U
P(U=0)=0.3• Causal Graph G

P[Y|X,U]

U=0

U=1

X=0

0.1

0.9

X=1

0.5

U

+

X=1 0.3
is looking
quite YX
good, should I do() it?

• Distributions

E(Y | X = 0)
< E(Y | X = 1)
E(Y | do(X = 0)) > E(Y | do(X = 1))

E[Y|do(X)]

E[Y|X]

X=0

0.66

0.1

X=1

0.36

0.3

L2

L1

42

Structural Explanation for Naive-TS’s behavior-- The Challenge of Non-Identifiability• SCM M (Unobserved)$• Causal Graph G

X=U
E[Y|X,U]
U=0
Questions(more general):
Y=U
0.1
X=0

U

U=1

0.9

X=1 is not
0.5present
0.3 in my X
know
:(Y
Don’t
know!
1. HowP(U=0)=0.3
do I know this pattern
data? Don’t
2. Does this then imply that I should throw away all the data not
Hopefullynot!
not…
collected by me (the agent) and learn from scratch?HopefullyYes!
3. Afterall, is there any useful information in the obs. data?Yes!
• DataE[Y|X]
Let’s try to understandE[Y|do(X)]how to leverage confounded
data…
X=0

0.66

0.1

X=1

0.36

0.39

L2

L1

43

Step 1. Extracting Causal Informationfrom Confounded Observations
Solution: Bounding E[Y | do(x)] from observations P(x,y).

Theorem. Given observations coming from any
distribution P(x,y), the average causal effect E[Y | do(x)]is bounded in [lx, hx], wherelx = E[Y | x] P(x) and hx = lx + 1 - P(x).
• Linear Program formulation in other causal graphs (nonparametric SCMs): [Balke & Pearl, 1996;
Zhang and Bareinboim, IJCAI’17]• Incorporating parametric knowledge:[Kallus & Zhou, 2018; Namkoong et al., 2020]• Sequential treatments in longitudinal settings:[Zhang & Bareinboim, NeurIPS’19; ICML’20]

44

Step 2. Incorporating Bounds into Learning(e.g., Causal Thompson Sampling)
Input: prior parameters 𝛂, β,causal bounds [lx, hx] for each arm x. /* [lx, hx] arecomputed from
Initialization: Sx=0, Fx=0 for each arm x
confounded
observations */For t = 1, …, T do
For each x do
Repeat/* Causal
bounds are
Draw θx ~ Beta(Sx+𝛂, Fx+ β).

Until θx ϵ [lx, hx]
EndPlay do(xt) where Xt = argmaxx θx.
Observed Yt and update Fxt and Sxt.

ascertained thr.
a rejection
procedure. */End
45

Naive TS POLICY LEARNING
GENERALIZED

Task 1a. Input: P(x, y), learn: P(y | do(x)).

- do-calc ID- off-policy a2- Robotics: learning by demonstration whentheweteacherCan
do better using
can observe a richer context (e.g., more accurate sensors)thecausal bounds?
- Medical: optimal experimental design fromobservational
data.
FDA-Chef

Master-ChefU

Utask 1

X

Traditional TS
XYY

Let’s ignore their differences, pretendingthat student-and master-chef robots areinterchangeable — call “naive TS”.
How could this be happening?!
Could more data be hurting?

46

Causal TS POLICY LEARNING
GENERALIZED

Task 1. Input: P(x, y), learn: P(y | do(x)).

- do-calc ID- off-policy a2- Robotics: learning by demonstration whentheweteacherCan
do better using
can observe a richer context (e.g., more accurate sensors)thecausal bounds?
- Medical: optimal experimental design fromobservational
data.
FDA

Master-ChefU

Utask 1

X

Traditional TS
XYY

Let’s ignore their differences, pretendingthat student-and master-chef robots are
Step 3interchangeable — call “naive TS”.
Orders of magnitudeimprovement can be achieved inpractice, and can be proved in
How could this be happening?!
general settings (ZB, IJCAI’17).
More data is hurting …
47

GENERALIZED POLICY LEARNING-- BIG PICTURE
U

U
Π
Y

X

Causal graph G
Observation

under do(X)AgentGPL-bounding

P(x, y)obs, obs …

YX

Eπ[Y | do(x)]obs

do(x0) do(x1) …
48

do(x0)
48

GENERALIZED POLICY LEARNING-- BIG PICTURE
U SUMMARY (GPL Template):UΠ
1. If policy is identifiable from offline methods,
returnoptimal one throughDo-calculus/IPW.
YYXX
2. Extract causal information from obs. data,
Causal graph G
underbaseddo(X)on theand compose causal bounds
available structural assumptions (on G & M).
3. Offline + Online: Incorporate causal bounds
GPL-bounding
Observation
Agent
into online allocation procedure.
4. Prove regret bounds (Theory).

P(x, y)obs, obs …

Eπ[Y | do(x)]obs

do(x0) do(x1) …
48

do(x0)
48

NEW RESULT: GPL FOR
DYNAMIC TREATMENT REGIMES• DTRs is a popular model for sequential treatment inmedical domains [Murphy, 2003; Moodie et al., 2007]:
𝑆2

𝑆1
𝑋1

𝑋2

Y

𝑋1

𝑈

𝑋2
𝑈

Observational

GPLbounding

Other agent with π𝑃(𝑥, 𝑦, 𝑐)obs, obs, …

𝑆2

𝑆1

Y

𝑑𝑜(𝑥1 𝑠1), 𝑑𝑜(𝑥2 | 𝑥1, 𝑠1, 𝑠2)
Agent
E[Y | do(π)]
do(π0) …

obs
49

do(π1)
49

NEW RESULT: GPL FOR
DYNAMIC TREATMENT REGIMES• DTRs is a popular model for sequential treatment inmedical domains [Murphy, 2003; Moodie et al., 2007]:
𝑆2

𝑆1
𝑋1

𝑆2

𝑆1

Y
𝑋2

𝑋1

𝑈

𝑋2
𝑈

Observational

GPLbounding

Other agent with π𝑑𝑜(𝑥1 𝑠1), 𝑑𝑜(𝑥2 | 𝑥1, 𝑠1, 𝑠2)
Agent𝑃(𝑥, 𝑦, 𝑐)obs, obs, …

Y

E[Y | do(π)]
do(π0) …

obs
49* For details, see [Zhang & Bareinboim, NeurIPS’19; ICML’20].

do(π1)49TASK 2.
WHEN AND WHERE TO INTERVENE?
(Refining the policy space)

Sanghack Lee

CRL-TASK 2.
WHEN AND WHERE TO INTERVENE?
• In general, it’s assumed throughout the literature apolicy space such that actions are fixed a priori(e.g., a set X = {X1, …, Xk}), and intervening is
usually assumed to lead to positive outcomes.
• Our goal here is to understand when interventions
when
are required, or if they may lead to unintended/ ifconsequences (e.g., side effects).
• In the case interventions may be needed, we would
like to understand what should be changed in thewhere
underlying environment so as to bring a desired
state of affairs about (e.g., maybe do(X1, X3, X7)
instead of do(X1, X2, X3, …, X7)).
51

UNDERSTANDING THE POLICY SPACE• Consider the causal graph of a bandit model:
UXY• Our goal is to optimize Y (e.g., keep it high as much as
possible), and we are not a priori committed to intervening
on any specific variable, or intervening at all.
• Consider now the 3-var causal graph:
U

Z

{}

no intervention

{Z}

{X}

intervention

XY

causal graph G{X, Z}

policy space

52

UNDERSTANDING THE POLICY SPACE• Our goal is to optimize Y (e.g., keep it high as much as
possible), and we are not a priori committed to intervening
on any specific variable, or intervening at all.
• Consider now the 3-var causal graph:
U

Z
X

{}

{Z}

{X}

Y

causal graph G{X, Z}

policy space• Causal-insensitive strategy: Ignore the causal structure G,
take {X, Z} as one larger variable, and search based onargmaxxz E[Y | do(X = x, Z = z)]

53

UNDERSTANDING
THE POLICY SPACE
Agent’smodel:Key observations:G’:
1. Note that the implicit causal graph in
U is to optimize Y (e.g.,• Our goal
keep it high as much as
the agent’s mind (G’ ), which follows
Z possible), and we are not a fromprioristandard
committed
to intervening
optimization
procedure,
on any specific
atG.
all.
is different thanY variable, or intervening
X{}• Consider now the 3-var causal
graph:
2. Thetrue causal model G encodes
Z

U

constraints of the underlying
environment (SCM M).
{Z}
{X}

$

Question -- Despite what is in theYXagent’s mind (orfunction),{X, optimizationZ}
it’s still the case that it will be
evaluatedpolicyby the space
SCM M. Is then being
causal graph G
oblivious to the pair <G, M> okay?
• Causal-insensitive strategy:Can’t
Ignorethedo
causalstructure G,
we justmore interventions?

take {X, Z} as one larger variable,
searchon
Meaning,and
more
do(X=x,based
Z=z), andthings will eventually converge?

argmaxxz E[Y | do(X = x, Z = z)]

53

THE CAUSAL STRUCTURE CANNOT BE DISMISSED• SCM M (Unobserved)

Z ← UzX←Z⨁UY←X⨁U• Causal Graph G

U

Z
X

Y

P(U=1) = P(Uz=1) = 0.5

54THE CAUSAL STRUCTURE CANNOT BE DISMISSED• SCM M (Unobserved)

Z ← UzX←Z⨁UY←X⨁U• Causal Graph G

U

Z
X

Y

P(U=1) = P(Uz=1) = 0.5

E[Y| do(X)] = E[Y| do(X,Z)] = 0.5

E[Y| do(Z)] = (Z ⨁ U) ⨁ U = Z
So, if do(Z=1),
E[Y | do(Z = 1)] = 1

55

THE CAUSAL STRUCTURE CANNOT BE DISMISSED• SCM M (Unobserved)

Z ← UzX←Z⨁UY←X⨁U• Causal Graph G

U

Z
X

Y

P(U=1) = P(Uz=1) = 0.5• A causal insensitive strategy (i.e., “all-at-once”, do(X,Z)) will
E[Y| do(X)]= E[Y|= 0.5
not pickup do(X,Z)]
the do(Z)-intervention,
and will never converge!

,• A naive,
works since it includes do(Z=1)
E[Y| do(Z)]= (Z “all-subsets”⨁ U) ⨁ U =strategy
ZSo, if do(Z=1),
E[Y | do(Z = 1)] = 1

55

THE CAUSAL STRUCTURE CANNOT BE DISMISSED• SCM M (Unobserved)

Z ← UzX←Z⨁UY←X⨁U• Causal Graph G

U

Z
X

Y

P(U=1) = P(Uz=1) = 0.5• A causal insensitive strategy (i.e., “all-at-once”, do(X,Z)) will
E[Y| do(X)]= E[Y|= 0.5
not pickup do(X,Z)]
the do(Z)-intervention,
and will never converge!

,• A naive,
works since it includes do(Z=1)
E[Y| do(Z)]= (Z “all-subsets”⨁ U) ⨁ U =strategy
ZSo, if do(Z=1),
E[Y | do(Z = 1)] = 1

55

THE CAUSAL STRUCTURE CANNOT BE DISMISSED• SCM M (Unobserved)

Z ← UzX←Z⨁UY←X⨁U• Causal Graph G

U

Z
X

Y

P(U=1) = P(Uz=1) = 0.5• A causal insensitive strategy (i.e., “all-at-once”, do(X,Z)) will
E[Y| do(X)]= E[Y|= 0.5
not pickup do(X,Z)]
the do(Z)-intervention,
and will never converge!

,• A naive,
works since it includes do(Z=1)
E[Y| do(Z)]= (Z “all-subsets”⨁ U) ⨁ U =strategy
ZSo, if do(Z=1),
Can we do better than these two naive strategies?
E[Y | do(Z = 1)] = 1

55

POLICY SPACE (EXAMPLE)
Intervention
Sets (IS)Actions

{}

do()

Y

do(X)

Policy space{}do(X=0)do(X=1)do(Z)do(Z=0)do(Z=1)do(X,Z)

do(X=0,Z=0)
do(X=0,Z=1)
do(X=1,Z=0)
do(X=1,Z=1)

Causal graph G
U

Z
X

{X}

{Z}
{X, Z}

56

POLICY SPACE (EXAMPLE)
Intervention
Sets (IS)Actions

{}

do()

Y

do(X)

Policy space{}do(X=0)do(X=1)do(Z)do(Z=0)do(Z=1)

Causal graph G
U

Z
X

{X}

{Z}

do(X,Z)

do(X=0,Z=0)
do(X=0,Z=1)
We’ll study properties of the policydo(X=1,Z=0)
space with respect{X,toZ}the the topological constraints imposed by M in G.
do(X=1,Z=1)
56

PROPERTY 1:
INTERVENTIONAL EQUIVALENCE
U

Z
X

Y

E[ Y | do(x,z) ] = E[ Y | do(x) ]∵ (Y⟂Z | X) in G X, Z (Rule 3 of do-calculus)
Implication: prefer playing do(X) to playing do(X, Z).
Definition (Minimal Intervention Set, MIS)
Given <G,Y>, a set of variables X ⊆V \ {Y} is said to be a minimal
intervention set if there is no X’⊂X such that E[Y | do(x’)] = E[Y | do(x)]for every SCM conforming to G where x’ is consistent with x.
57

PROPERTY 1: MIS (EXAMPLE)
Causal graph G
U

Z

Y

X

Policy space
{}
{X}

{Z}
{X, Z}

Intervention
Sets (IS)Actions

{}

do()

do(X)

do(X=0)do(X=1)do(Z)do(Z=0)do(Z=1)do(X,Z)

do(X=0,Z=0)
do(X=0,Z=1)
do(X=1,Z=0)
do(X=1,Z=1)

MIS

58

PROPERTY 1: MIS (EXAMPLE)
Causal graph G
U

Z

Y

X

Policy space
{}
{X}

{Z}
{X, Z}

Intervention
Sets (IS)Actions

MIS

{}

do()

✔

do(X)

do(X=0)do(X=1)✔

do(Z)do(Z=0)do(Z=1)✔

do(X,Z)

do(X=0,Z=0)
do(X=0,Z=1)
do(X=1,Z=0)
do(X=1,Z=1)✗
58

PROPERTY 2:
PARTIAL-ORDEREDNESS
E[Y] = ∑z E[Y|do(z)] P(z)≤ ∑z E[Y|do(z*)] P(z)

U

Z
X

Y

= E[Y|do(z*)]

z* ≡ argmaxz E[Y|do(z)]∴ E[Y] ≤ E[Y|do(z*)]
Implication: playing do(Z) should be preferred to playing do().
Definition (Possibly-Optimal MIS, POMIS)
Given <G,Y>, let X∈MISs. X is said to be a possibly-optimal MIS if
there exists a SCM M conforming to G such thatmax x E[Y | do(X=x)] > max W∈MIS \ {X} E[Y | do(W=w)]
59

PROPERTY 2:
PARTIAL-ORDEREDNESS
E[Y] = ∑z E[Y|do(z)] P(z)UZX

≤ ∑z E[Y|do(z*)] P(z)z* ≡ argmaxz E[Y|do(z)]= E[Y|do(z*)]
Y
We provide
a complete characterization∴&
E[Y]≤ E[Y|do(z*)]
of POMIS
algorithm
that enumerates
all POMISs given a causal graph G.

Implication: playing do(Z) should be preferred to playing do().
Definition (Possibly-Optimal MIS, POMIS)
Given <G,Y>, let X∈MISs. X is said to be a possibly-optimal MIS if
there exists a SCM M conforming to G such thatmax x E[Y | do(X=x)] > max W∈MIS \ {X} E[Y | do(W=w)]

59

PROPERTY 2: POMIS (EXAMPLE)
Causal graph G
U

Z

Y

X

intervention
sets

actions

{}

do()

✔

do(X)

do(X=0)do(X=1)✔

do(Z)do(Z=0)do(Z=1)✔

do(X,Z)

do(X=0,Z=0)
do(X=0,Z=1)
do(X=1,Z=0)
do(X=1,Z=1)✗

MIS POMIS

Policy space
{}
{X}

{Z}
{X, Z}

60

PROPERTY 2: POMIS (EXAMPLE)
Causal graph G
U

Z

Y

X

intervention
sets

actions

{}

do()

✔

✗

do(X)

do(X=0)do(X=1)

✔

✔

do(Z)

do(Z=0)do(Z=1)✔

✔

do(X,Z)

do(X=0,Z=0)
do(X=0,Z=1)
do(X=1,Z=0)
do(X=1,Z=1)✗✗

MIS POMIS

Policy space
{}
{X}

{Z}
{X, Z}

60

PROPERTY 2: POMIS (EXAMPLE)
Causal graph G
U

Z

Y

X

intervention
sets

actions

{}

do()

✔

✗

do(X)

do(X=0)do(X=1)

✔

✔

do(Z)

do(Z=0)do(Z=1)✔

✔

MIS POMIS

Policy space{}{X}

do(X=0,Z=0)
do(X=0,Z=1)✗(SCM)✗POMIS share the reward
mechanism
do(X=1,Z=0)& POMIS’ armsdo(X=1,Z=1)
are dependent.
{X, Z}{Z}

do(X,Z)

60

PROPERTY 3:
Structural
Property3:
Quantitave
ARMS’ QUANTITATIVE RELATIONSHIPS

Relationships Across Arms

• Goal: infer an arm’s expected reward from other arms’ data,B

P(y|do(x)) ← { P(V | do(Z)) }Z∈POMIS\{X}• New ID algorithm (z2ID) to findCa matching POMIS, that canborrow some additional data.
A• Example

Y

B

C

POMISsare ;,{},{B},Given
POMISs{B},andand{C}.
{C}:
P(y) =Pb (y) =Pc (y) =Pc (y) =PP
P
P

a,b,c Pb (c|a)Pc (a, b, y)
a,c P(c|a, b)

P

b0

A

Y

P(y |a, b0 , c)P(a, b0 )a,b P(y|a, b, c)P(a, b)
a Pb (y|a, c)Pb (a)61PROPERTY 3:
ARMS’
QUANTITATIVERELATIONSHIPS
Structural Property 3: Minimum Variance

—..

—....

(b)

Dc=0

Dc=1

—..

(b)

Db=1

Dc=0

—....

—

—......

(b)

Db=0

Db=1

—

(b)

D;

Db=0
—......

Bootstrap Samples
D(b)

D;

—...

SamplesD—...

• Make the most of data
— Minimum Variance Weighting
Weighting

(b)

Dc=1
⇥ number ofbootstraps

Bootstrap Estimates

Weighted Estimates
✓ˆ;

✓ˆb=0

✓ˆb=1

✓ˆc=0

✓ˆc=1
62

WHEN AND WHERE TO INTERVENE -ALGORITHMS & EXPERIMENTS• We embed these results into TS/UCB solvers:• z2-TS: posterior distributions for expected rewards → adjust‘posterior distributions’ reflecting all used data
• z2-kl-UCB: upper confidence bounds for expected rewards →adjust ‘upper bounds’ by taking account samples from other arms

Cumulative Regret• Performance: POMIS+ ≥ POMIS ≥ MIS ≥ Brute-force
600

POMIS+
POMIS
MIS
BF

400
200
0

0

5k

Trials10k
63

WHEN & WHERE TO INTERVENE -BIG PICTURE
B

B
C

Π

?

C
?

Y

A

Causal Graph GYA

POMIS,
formulasunder do(x)Agentno dataEx~π[Y | do(x)]?
obs(), do(b), ….
64

do(c)
64

NEW RESULT:
WHERE TO INTERVENE & WHAT TO SEE• In addition to deciding where to intervene, agents also needto decide where to look…
X1
C
Causal Graph G

X1

Π

C

X2

Y

Additional Context C

do(x1|c), do(x2|x1)
X1

C

Π’
X2

* both C and X1 can become a context
65

Y

…

…

X2

do(x2|c)Y
65

WHERE TO INTERVENE &WHAT TO SEE — POLICY SPACE
X1

C
Causal Graph G

X2

Y

{}
do()

{X2}
do(x2){X1}

do(x2|c)do(x2|x1)

do(x2|c,x1){X1, X2}

do(x1)

do(x1),
do(x2)

do(x1),
do(x2|c)do(x1),
do(x2|x1)

do(x1),
do(x2|c,x1)

do(x1|c)do(x1|c),do(x2)

do(x1|c),do(x2|c)do(x1|c),do(x2|x1)

do(x1|c),do(x2|c,x1)

66

WHERE TO INTERVENE &WHAT TO SEE — POLICY SPACE
X1

C

X2

do()

do(x1)

Policies with the same
maximum expected rewardsYdo(x2)

do(x2|x1)

do(x1),
do(x2)

do(x1), do(x1),do(x2|c) do(x2|c,x1)

do(x1|c),do(x2)
do(x1|c)do(x2|c) do(x2|c,x1)

do(x1|c),do(x2|x1)

do(x1),
do(x2|x1)67

do(x1|c), do(x1|c),do(x2|c) do(x2|c,x1)

67

WHERE TO INTERVENE &WHAT TO SEE — POLICY SPACE
X1

X2

do()

1. minimal policy among
reward-equivalent policiesC

do(x1)

Ydo(x2)
do(x2|x1)

do(x1),
do(x2)

do(x1), do(x1),do(x2|c) do(x2|c,x1)

do(x1|c),do(x2)
do(x1|c)do(x2|c) do(x2|c,x1)

do(x1|c),do(x2|x1)

do(x1),
do(x2|x1)67

do(x1|c), do(x1|c),do(x2|c) do(x2|c,x1)

67

WHERE TO INTERVENE &WHAT TO SEE — POLICY SPACE
X1

C

X2

do()

do(x1)

Ydo(x2)

1. minimal policy among
reward-equivalent policies
Partial-orders among policies wrt
maximum expected rewards≤
do(x2|x1)

do(x1),
do(x2)

do(x1), do(x1),do(x2|c) do(x2|c,x1)

do(x1|c),do(x2)
do(x1|c)do(x2|c) do(x2|c,x1)

do(x1|c),do(x2|x1)

do(x1),
do(x2|x1)67

do(x1|c), do(x1|c),do(x2|c) do(x2|c,x1)

67

WHERE TO INTERVENE &WHAT TO SEE — POLICY SPACE
X1

X2

do()

1. minimal policy among
reward-equivalent policiesC

do(x1)

2. possibly-optimal policies
among min. policies.

Ydo(x2)≤
do(x2|x1)

do(x1),
do(x2)

do(x1), do(x1),do(x2|c) do(x2|c,x1)

do(x1|c),do(x2)
do(x1|c)do(x1|c),do(x2|x1)

do(x1),
do(x2|x1)* For details, see [R-63 @CausalAI].

do(x2|c) do(x2|c,x1)

67

do(x1|c), do(x1|c),do(x2|c) do(x2|c,x1)

67

TASK 3.
COUNTERFACTUAL DECISION-MAKING(Intentionality, Free Will, Autonomy)
Andrew Forney

Judea PearlCRL-TASK 3.
COUNTERFACTUAL DECISION-MAKING• Agents act in a reflexive manner, without
considering the reasons (or causes) for behaving
in a particular way. Whenever this is the case,they can be exploited without never realizing.
• This is a general phenomenon in online learning
whenever the agent optimizes by Fisherian rand./the do-distribution (incl. all known RL settings).
• Our goal is to endow agents with the capability of
performing counterfactual reasoning (taking theirown intent into account), which leads to a morerefined notion of regret & a new OPT function.
69

COUNTERFACTUAL DECISION-MAKING
Question:
How should one select the treatment (x*) to a particular
unit U=u so as to maximize expected reward (Y)?
What if we have observational data? Experimental data?
U

Applications:X

Y» Robotics» Medical Treatment» Job Training Program70

GREEDY CASINO.
INDIVIDUAL VERSUS POPULATION-LEVEL DECISIONS
Goal: Find a strategy (∏) so as to minimize cumulative regret.
{B, D}XY

X = type of the machine (x0, x1)
Y = reward (y0, y1)
B = blinking machine (b0, b1)
D = drunkenness level (d0, d1)• Regulations: payout has to be ≥ 0.3.
• Casino learns how customers operates and decides to set
the payout structure as follows (using ML):E [y1 |
X, B, D]X = x1
X = x0

D=0
B=0
B=1
0.10
0.50
0.50
0.10

D=1
B=0
B=1
0.40
0.20
0.20
0.40

71

GREEDY CASINO.
INDIVIDUAL VERSUS POPULATION-LEVEL DECISIONS• Casino’s model: fX(B, D), P(B), P(D),E [y1 |
X, B, D]

D=0
B=0

B=1

B=0

B=1

X = x1

0.10

0.50

0.40

0.20

X = x0

0.50

0.10

0.20

0.40

{B, D}
X

D=1

Y

randomsample(L1)

D1 E(y1 | X = x0) = 0.15
E(y1 | X = x1) = 0.15
72

GREEDY CASINO.
INDIVIDUAL VERSUS POPULATION-LEVEL DECISIONS• Casino’s model: fX(B, D), P(B), P(D),E [y1 |
X, B, D]

D=0
B=0

B=1

B=0

B=1

X = x1

0.10

0.50

0.40

0.20

X = x0

0.50

0.10

0.20

0.40

{B, D}
X

D=1

Y

randomsamplerandomexperiment

∏

(L1)

(L2)

X

{B, D}Y

D1 E(y1 | X = x0) = 0.15

D2 E(y1 | do(X = x0)) = 0.30

E(y1 | X = x1) = 0.15

E(y1 | do(X = x1)) = 0.30
72

GREEDY CASINO.
INDIVIDUAL VERSUS POPULATION-LEVEL DECISIONS• Attempt 1. ML (𝛜-greedy, Thompson Sampling, UCB, EXP3).

* Bandits minimize short-term regret based on the do()-distribution.

GREEDY CASINO: CAN WE DO BETTER?

74

GREEDY CASINO: CAN WE DO BETTER?
• Attempt 2. Counterfactual randomization• RDC (Regret Decision Criterion):
X* = arg maxx E(YX = x1 | X = x0)
X* = arg maxx E(Y | do(X = x))• This should be read as the counterfactual sentence:“Expected value of Y had X been x1, given that X = x0?”
(Also known as Effect of Treatment on the Treated. )74

GREEDY CASINO: CAN WE DO BETTER?
*Also called• Attempt 2. Counterfactual randomization
counterfactual, but too• RDC (Regret Decision Criterion):
weak (L2), we’ll
X* = arg maxx E(YX = x1 | X = x0) just call do().

X* = arg maxx E(Y | do(X = x)) = E(YX = x)
• This should be read as the counterfactual sentence:“Expected value of Y had X been x1, given that X = x0?”
(Also known as Effect of Treatment on the Treated. )74

GREEDY CASINO: CAN WE DO BETTER?
• Attempt 2. Counterfactual randomization• RDC (Regret Decision Criterion):
X* = arg maxx E(YX = x1 | X = x0)• This should be read as the counterfactual sentence:“Expected value of Y had X been x1, given that X = x0?”
(Also known as Effect of Treatment on the Treated. )• General counterfactuals are difficult (or impossible) to
evaluate from data (even experimentally), except for somespecial conditions (e.g., binary treatment, backdoor
admissibility, unconfoundedness) (Pearl, 2000, Ch. 9).
74

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.

75

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.
– Pause, interrupting decision flow, and wonder:“I am about to play x0, would I be better off goingwith my intuition (x0) or against it (x1)?”

75

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.
– Pause, interrupting decision flow, and wonder:“I am about to play x0, would I be better off goingwith my intuition (x0) or against it (x1)?”
Note. If at step 2, we …

75

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.
– Pause, interrupting decision flow, and wonder:“I am about to play x0, would I be better off goingwith my intuition (x0) or against it (x1)?”
Note. If at step 2, we …
• do not interrupt, allowing X = x0 → P(x0, y).

75

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.
– Pause, interrupting decision flow, and wonder:“I am about to play x0, would I be better off goingwith my intuition (x0) or against it (x1)?”
Note. If at step 2, we …
• do not interrupt, allowing X = x0 → P(x0, y).
• do interrupt and make X = rand() = x1 → P(y | do(x1)).
75

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.
– Pause, interrupting decision flow, and wonder:“I am about to play x0, would I be better off goingwith my intuition (x0) or against it (x1)?”
Note. If at step 2, we …
• do not interrupt, allowing X = x0 → P(x0, y).
• do interrupt and make X = rand() = x1 → P(y | do(x1)).
75

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.
– Pause, interrupting decision flow, and wonder:“I am about to play x0, would I be better off goingwith my intuition (x0) or against it (x1)?”
Note. If at step 2, we …
• do not interrupt, allowing X = x0 → P(x0, y).
• do interrupt and make X = rand() = x1 → P(y | do(x1)).
• do interrupt and make X = rand() = x1 | x0 → P(Yx1 | x0).
75

COUNTERFACTUAL DECISION-MAKING• RDC (Regret Decision Criterion):
X* = argmaxx E(YX = x1 | X = x0)• Evaluating RDC-type expressions:– Note that the agent is about to play machine x0,
which means that (the unknown) fX(b, d) evaluated to x0.
– Pause, interrupting decision flow, and wonder:“I am about to play x0, would I be better off goingwith my intuition (x0) or against it (x1)?”
Note. If at step 2, we …
• do not interrupt, allowing X = x0 → P(x0, y).
• do interrupt and make X = rand() = x1 → P(y | do(x1)).

EDT
CDT

• do interrupt and make X = rand() = x1 | x0 → P(Yx1 | x0). RDT
75

REGRET DECISION CRITERION:
EXPERIMENTAL RESULTS• Greedy Casino Parametrization

76

REGRET DECISION CRITERION:
EXPERIMENTAL RESULTS• What if the experimental distribution is available (4-arm case)?

77

TASK 3. COUNTERFACTUAL LEARNING
U

U

Π
X

Y

the environment

X’

X

Y

under ctf. randomization
Agent

no dataEx~π[Yx | x’ ]?
Yx0|x1, Yx1|x1, …, Yx1|x0
78
78

APPLICATION: HUMAN-AI COLLABORATION(CAN HUMANS BE OUT OF THE LOOP?*)• Observation from the RDC, if E[Yx|x’] = E[Y|do(x)] → thehuman's intuition has no value of information.
• In words, the human expert could be replaced without
sacrificing the performance of the system, at least in
principle full autonomy can be achieved.
• Contribution: New Markovian properties (L2, L3) that
establishes whether an agent can be autonomous.

* For details, see [R-64 @CausalAI].

79
79

APPLICATION: HUMAN-AI COLLABORATION(CAN HUMANS BE OUT OF THE LOOP?*)• Observation from the RDC, if E[Yx|x’] = E[Y|do(x)] → thehuman's intuition has no value of information.
• In words, the human expert could be replaced without
sacrificing the performance of the system, at least in
principle full autonomy can be achieved.
• Contribution: New Markovian properties (L2, L3) that
establishes whether an agent can be autonomous.

* For details, see [R-64 @CausalAI].

79
79

SUMMARY CRL TASKSCRL CAPABILITIES (I)
1. Generalized Policy Learning (on+offline)#+"• Online learning is too costly and learningfrom scratch is usually impractical. Still, the assumptionsof offline learning are rarely satisfied in practice.
• Goal: Move towards more realistic learning scenarios
where the two modalities come together, extracting as
much causal information as possible from confounded
data, and using it in the most efficient way.

2. When and where to intervene?

& →"• Agents usually have a fixed policy space (actions), andintervening is usually assumed as beneficial.
• Goal: Understand when interventions are needed andwhenever this is the case, what should be changed in
the system to bring about the desired outcome.
81

CRL CAPABILITIES (II)
3. Counterfactual Decision-Making(intentionality, regret & free will)!+*• Agents act in a reflexive manner, without considering
the reasons (causes) for behaving in a certain way.
• Goal: Endow agents with the capability of taken theirown intent into account, which will lead to a new notionof regret based on counterfactual randomization.

4. Generalizable and Robust Decision-Making(transportability & structural invariances) - →• The knowledge acquired by an agent is usually
circumscribed to the domain where it was deployed.

• Goal: Allow agents to extrapolate knowledge, making
more robust and generalizable claims by leveraging thecausal invariances shared across environments.
82

CRL CAPABILITIES (III)
5. Learning Causal Models by Combining
2+1
Observations & Experimentation• Agents have a fixed causal model, constructed from
templates or from background knowledge.
• Goal: Allow agents to systematically combine theobservations and interventions it’s already collecting
to construct an equivalence class of causal models.

6. Causal Imitation Learning

3 →4• Mimicking is one of the common ways of learning.
Whenever the demonstrator has a different causal
model, imitating may lead to disastrous side effects.
• Goal: Understand the conditions so that imitation by
behavioral cloning is valid and leads to faster learning.
Otherwise, introduce more refined imitation modalities.83

CRL CAPABILITIES (III)CRL (CHEAT SHEET)

5. Learning
Causal Models by Combining
1. Generalized Policy Learning (on+offline)+
1
2
Observations&
Experimentation
Combining L1 + L2 interactions to learn policy ∏.
• Agents
havea fixedcausal model, constructed from
2. Whenand where
to intervene?
Identifyingor
subsetL2 and optimize thepolicy space.
templates
fromof backgroundknowledge.
3. CounterfactualDecision-Making• Goal:Allow agentsto systematically combine theOptimization function based on L3 counterfactual & random.
observations
and interventions it’s already collecting
4. Generalizability
and Robustness class of causal models.
to construct
an equivalence
Generalizing from training environment (SCM M) to SCM M*.

6. Causal
Imitation
Learning
5. Learning
Causal ModelG

3 →4

Combining+ L2 interactions
to learn G ways(of M). of learning.
• Mimicking
isL1oneof the common
6. Causal Imitation
Learning
Wheneverthe demonstrator
has a different causal
Learning
L2 -policymay
basedleadon partiallyobservable L1-data
model,
imitatingto disastrousside(expert).
effects.
• Goal: Understand the conditions so that imitation by
behavioral cloning is valid and leads to faster learning.
Otherwise, introduce more refined imitation modalities.83

CONCLUSIONS• CI & RL are fundamentally intertwined and novel learning
opportunities emerge when this connection is fully realized.
• The structural invariances encoded in the causal graph(w.r.t. SCM M) can be leveraged and combined with RL
allocation procedures leading to robust learning.
• Still, failure to acknowledge distinct invariances of theenvironment (M) almost always leads to poor decision-making.

• CRL opens up a new family of learning problems that wereneither acknowledged nor understood before, including the
combination of online & offline learning (GPL), when/where tointervene, counterfactual decision-making, generalizability
across environments, to cite a few.
• Program: Develop a principled framework for designingcausal AI systems integrating [observational, experimental,
counterfactual] data, modes of reasoning, knowledge.
• Leads to a natural treatment to human-like
explainability and rational decision-making.
84

CONCLUSIONS• CI & RL are fundamentally intertwined and novel learning
opportunities emerge when this connection is fully realized.
• The structural invariances encoded in the causal graph(w.r.t. SCM M) can be leveraged and combined with RL
allocation procedures leading to robust learning.
• Still, failure to acknowledge distinct invariances of theenvironment (M) almost always leads to poor decision-making.

• CRL opens up a new family of learning problems that wereneither acknowledged nor understood before, including the
Resources:
combinationof online &https://crl.causalai.net
offline learning (GPL), when/where tointervene, counterfactual decision-making, generalizability
across environments, to cite a few.
• Program: Develop a principled framework for designingcausal AI systems integrating [observational, experimental,
counterfactual] data, modes of reasoning, knowledge.
• Leads to a natural treatment to human-like
THANK
explainability and rational decision-making.
84
YOU!

$

REFERENCES[F 1935] Fisher, R. A. The Design of Experiments. Oliver and Boyd 1935.
[WD 1992] Watkins, C., Dayan, P. Q-Learning. Machine Learning volume 8. 1992.
[BP 1994] Balke, A., Pearl, J. Counterfactual Probabilities: Computational Methods,
Bounds, and Applications In Proceedings of the Conference on Uncertainty in Artificial
Intelligence 1994.
[SB 1998] R. Sutton, A. Barto. Reinforcement Learning: An Introduction. MIT Press,
1998.
[P 2000] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge Press,
2000.
[ACF 2002] Auer, P., Cesa-Bianchi, N., Fischer, P. Finite-time Analysis of theMultiarmed Bandit Problem Machine Learning volume 47. 2002.
[JOA 2010] Jaksch, T., Ortner, R., Auer, P. Near-optimal Regret Bounds for
Reinforcement Learning. Journal of Machine Learning Research 11. 2010.
[DLL 2011] Dudik, M., Langford, J., Li, L. Doubly robust policy evaluation andlearning. In Proceedings of 28th International Conference on Machine Learning. 2011.
[BP 2014] E. Bareinboim, J. Pearl. Transportability from Multiple Environments with
Limited Experiments: Completeness Results. In Proceedings of the 27th Annual
Conference on Neural Information Processing Systems, 2014.

REFERENCES[BFP 2015] E. Bareinboim, A. Forney, J. Pearl. Bandits with Unobserved
Confounders: A Causal Approach. In Proceedings of the 28th Annual Conference on
Neural Information Processing Systems, 2015.
[BP 2016] E. Bareinboim, J. Pearl. Causal inference and the data-fusion problem.
Proceedings of the National Academy of Sciences, v. 113 (27), pp. 7345-7352, 2016.
[JL 2016] Jiang, N., Li, L. Doubly robust off-policy value evaluation for reinforcement
learning. In Proceedings of the 33rd International Conference on Machine Learning.
2016.
[ZB 2016] J. Zhang, E. Bareinboim. Markov Decision Processes with Unobserved
Confounders: A Causal Approach. CausalAI Lab, Technical Report (R-23), 2016.
[FPB 2017] A. Forney, J. Pearl, E. Bareinboim. Counterfactual Data-Fusion for Online
Reinforcement Learners. In Proceedings of the 34th International Conference on
Machine Learning, 2017.
[KSB 2017] M. Kocaoglu, K. Shanmugam, E. Bareinboim. Experimental Design for
Learning Causal Graphs with Latent Variables. In Proceedings of the 31st Annual
Conference on Neural Information Processing Systems, 2017.
[ZB 2017] J. Zhang, E. Bareinboim. Transfer Learning in Multi-Armed Bandits: A
Causal Approach. In Proceedings of the 26th International Joint Conference on
Artificial Intelligence, 2017.

REFERENCES[GSKB 2018] Ghassami, A., Salehkaleybar, S., Kiyavash, N., Bareinboim, E.
Budgeted Experiment Design for Causal Structure Learning. In Proceedings of the35th International Conference on Machine Learning. 2018.
[KZ 2018] Kallus, N., Zhou, A. Confounding-robust policy improvement. In Advancesin Neural Information Processing Systems 2018.
[LB 2018] S. Lee, E. Bareinboim. Structural Causal Bandits: Where to Intervene? In
Proceedings of the 32nd Annual Conference on Neural Information Processing
Systems, 2018.
[PM 2018] J. Pearl, D. Mackenzie. The book of why: The new science of causal andeffect. Basic Books, 2018.
[FB 2019] A. Forney, E. Bareinboim. Counterfactual Randomization: Rescuing
Experimental Studies from Obscured Confounding. In Proceedings of the 33rd AAAI
Conference on Artificial Intelligence, 2019.
[KJSB 2019] Kocaoglu, M., Jaber, A., Shanmugam, K., Bareinboim, E.
Characterization and Learning of Causal Graphs with Latent Variables from SoftInterventions. In Proceedings of the 33rd Annual Conference on Neural Information
Processing Systems. 2019.
[LB 2019] S. Lee, E. Bareinboim. Structural Causal Bandits with Non-manipulable
Variables. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019.

REFERENCES[LCB 2019] S. Lee, J. Correa, E. Bareinboim. General Identifiability with Arbitrary
Surrogate Experiments In Proceedings of the 35th Conference on Uncertainty in
Artificial Intelligence, 2019.
[ZB 2019] Zhang, J., Bareinboim, E. Near-Optimal Reinforcement Learning in
Dynamic Treatment Regimes. In Advances in Neural Information Processing Systems
2019.
[BCII 2020] Bareinboim, E, Correa, J, Ibeling, D, Icard, T. On Pearl’s Hierarchy andthe Foundations of Causal Inference. In "Probabilistic and Causal Inference: The
Works of Judea Pearl" (ACM Special Turing Series). 2020.
[BLZ 2020] Bareinboim, E, Lee, S, Zhang, J. An Introduction to Causal Reinforcement
Learning. Columbia CausalAI Laboratory, Technical Report (R-65). 2020.
[CB 2020] Correa, J, Bareinboim, E. Transportability of Soft Effects: CompletenessResults. Columbia CausalAI Laboratory, Technical Report (R-68). 2020.
[JKSB 2020] Jaber, A, Kocaoglu, M, Shanmugam, K, Bareinboim, E. Causal
Discovery from Soft Interventions with Unknown Targets: Characterization & Learning.
Columbia CausalAI Laboratory, Technical Report (R-67). 2020.
[JTB 2020] Jung, Y, Tian, J, Bareinboim, E. Learning Causal Effects via Empirical
Risk Minimization. Columbia CausalAI Laboratory, Technical Report (R-62). 2020.

REFERENCES[LB 2020] Lee, S, Bareinboim, E. Characterizing Optimal Mixed Policies: Where to
Intervene, What to Observe. Columbia CausalAI Laboratory, Technical Report (R-63).
2020.
[NKYB 2020] Namkoong, H., Keramati, R.,Yadlowsky, S., Brunskill, E. Off-policy
Policy Evaluation For Sequential Decisions Under Unobserved Confounding.
arXiv:2003.05623. 2020.
[ZB 2020a] Zhang, J., Bareinboim, E. Designing Optimal Dynamic Treatment
Regimes: A Causal Reinforcement Learning Approach. In Proceedings of the 37th
International Conference on Machine Learning. 2020.
[ZB 2020b] Zhang, J, Bareinboim, E. Bounding Causal Effects on Continuous
Outcomes. Columbia CausalAI Laboratory, Technical Report (R-61). 2020.
[ZB 2020c] Zhang, J, Bareinboim, E. Can Humans Be Out of the Loop? Columbia
CausalAI Laboratory, Technical Report (R-64). 2020.
[ZKB 2020] Zhang, J, Kumor, D, Bareinboim, E. Causal Imitation Learning with
Unobserved Confounders. Columbia CausalAI Laboratory, Technical Report (R-66).
2020.