Published as a conference paper at ICLR 2024
ROBUST AGENTS LEARN CAUSAL WORLD MODELS
Jonathan Richens∗
Google DeepMind
Tom Everitt
Google DeepMind
ABSTRACT
It has long been hypothesised that causal reasoning plays a fundamental role in
robust and general intelligence. However, it is not known if agents must learn
causal models in order to generalise to new domains, or if other inductive biases are
sufficient. We answer this question, showing that any agent capable of satisfying a
regret bound for a large set of distributional shifts must have learned an approximate
causal model of the data generating process, which converges to the true causal
model for optimal agents. We discuss the implications of this result for several
research areas including transfer learning and causal inference.
1 I NTRODUCTION
What capabilities are necessary for general intelligence (Legg & Hutter, 2007)? One candidate is
causal reasoning, which plays a foundational role in human cognition (Gopnik et al., 2007; Sloman &
Lagnado, 2015). It has even been argued that human-level AI is impossible without causal reasoning
(Pearl, 2018). However, recent years have seen the development of agents that do not explicitly learn
or reason on causal models, but nonetheless are capable of adapting to a wide range of environments
and tasks (Reed et al., 2022; Team et al., 2023; Brown et al., 2020).
This raises the question, do agents have to learn causal models in order to adapt to new domains, or
are other inductive biases sufficient? To answer this question, we have to be careful not to assume that
agents use causal assumptions a priori. For example, transportability theory determines what causal
knowledge is necessary for transfer learning when all assumptions on the data generating process
(inductive biases) can be expressed as constraints on causal structure (Bareinboim & Pearl, 2016).
However, deep learning algorithms can exploit a much larger set of inductive biases (Neyshabur et al.,
2014; Battaglia et al., 2018; Rahaman et al., 2019; Goyal & Bengio, 2022) which in many real-world
tasks may be sufficient to identify low regret policies without requiring causal knowledge.
The main result of this paper is to answer this question by showing that,
Any agent capable of adapting to a sufficiently large set of distributional shifts
must have learned a causal model of the data generating process.
Here, adapting to a distributional shift means learning a policy that satisfies a regret bound following
an intervention on the data generating process—for example, changing the distribution of features or
latent variables. It is known that a causal model of the data generating process can be used to identify
regret-bounded policies following a distributional shift (sufficiency), with more accurate models
allowing lower regret policies to be found. We prove the converse (necessity)—given regret-bounded
policies for a large set of distributional shifts, we can learn an approximate causal model of the data
generating process, with the approximation becoming exact for optimal policies. Hence, learning a
causal model of the data generating process is necessary for robust adaptation.
This has consequences for a number of fields and questions. For one, it implies that causal identi-
fication laws also constrain domain adaptation. For example, we show that adapting to covariate
and label shifts is only possible if the causal relations between features and labels can be identified
from the training data—a non-trivial causal discovery problem. This provides further theoretical
justification for causal representation learning (Schölkopf et al., 2021), showing that learning causal
representations is necessary for achieving strong robustness guarantees. Our result also implies that
we can learn causal models from adaptive agents. We demonstrate this by solving a causal discovery
∗jonrichens@deepmind.com
1

Published as a conference paper at ICLR 2024
task on synthetic data by observing the policy of a regret-bounded agent under distributional shifts.
More speculatively, our results suggest that causal models could play a role in emergent capabilities.
Agents trained to minimise a loss function across many domains are incentivized to learn a causal
world model, which could enable them to solve a much larger set of decision tasks they were not
explicitly trained on.
Outline of paper. In Section 2 we introduce concepts from causality and decision theory used to
derive our results. We present our main theoretical results in Section 3 and discuss their interpretation
in terms of adaptive agents, transfer learning and causal inference. In Section 4 we discuss limitations,
as well as implications for a number of fields and open questions. In section 5 we discuss related work
including transportability (Bareinboim & Pearl, 2016) and the causal hierarchy theorem (Bareinboim
et al., 2022), and recent empirical work on emergent world models. In Appendix B we describe
experiments applying our theoretical results to causal discovery problems.
2 P RELIMINARIES
2.1 C AUSAL MODELS
We use capital letters for random variables V , and lower case for their values v∈ dom(V ). For
simplicity, we assume each variable has a finite number of possible values,|dom(V )|<∞. Bold
face denotes sets of variablesV ={V1,...,V n}, and their valuesv∈ dom(V ) =×idom(Vi). A
probabilistic model specifies the joint distributionP (V ) over a set of variablesV . These models
can support associative queries, for example P (Y =y|X =x) forX,Y ⊆V . Interventions
describe external changes to the data generating process (and hence changing the joint distribution),
for example a hard intervention do(X =x) describes forcing the set of variablesX⊆V to take
valuex. This generates a new distribution P (V | do(X = x)) = P (Vx) whereVx refers to the
variablesV following this intervention. The power of causal models is that they specify not only
P (V ) but also the distribution ofV under all interventions, and hence these models can be used to
evaluate both associative and interventional queries e.g.P (Y =y| do(X =x)).
For the derivation of our results we focus on a specific class of causal models—causal Bayesian
networks (CBNs). There are several alternative models and formalisms that are studied in the
literature, including structural equation models (Pearl, 2009) and the Neyman-Rubin causal models
(Rubin, 2005), and results can be straightforwardly adapted to these.
Definition 1 (Bayesian networks). A Bayesian networkM = (G,P ) over a set of variablesV =
{V1,...,V n} is a joint probability distributionP (V ) that factors according to a directed acyclic
graph (DAG)G, i.e.P (V1,...,V n) =Qn
i=1P (Vi| PaVi), where PaVi are the parents ofVi inG.
A Bayesian network is causal if the graphG captures the causal relationships between the variables
or, formally, if the result of any intervention do(X =x) forX⊆V can be computed from the
truncated factorisation formula:
P (v| do(x)) =
(Q
i:vi̸∈xP (vi| pavi) ifv consistent withx
0 otherwise.
More generally, a soft interventionσvi =P′(Vi| Pa∗
i ) replaces the conditional probability distribu-
tion forVi with a new distributionP′(Vi| Pa∗
i ), possibly resulting in a new parent set Pa∗
i̸= Pai
as long as no cycles are introduced in the graph. We refer to σvi as a domain indicator (Correa &
Bareinboim, 2020) (it has also been called an environment index, Arjovsky et al., 2019). The updated
distribution is denotedP (v;σv′) =Q
i:vi∈v′P′(vi| pa∗
vi)Q
i:vi̸∈v′P (vi| pavi).
In general, soft interventions cannot be defined without knowledge of G. For example, the soft
interventionσY =P′(y|x) is incompatible with the causal structureY →X as it would induce a
causal cycle. As our results are concerned with learning causal models (and hence causal structure),
we focus our theoretical analysis on a subset of the soft interventions, local interventions, that are
compatible with all causal structures and so can be used without tacitly assuming knowledge ofG.
2

Published as a conference paper at ICLR 2024
Definition 2 (Local interventions). Local intervention σ onVi∈ V involves applying a map to
the states of Vi that is not conditional on any other endogenous variables, vi7→ f(vi). We use
the notationσ = do(Vi =f(vi)) (variableVi is assigned the statef(vi)). Formally, this is a soft
intervention onVi that transforms the conditional probability distribution as,
P (vi| pai;σ) =
X
v′
i:f(v′
i)=vi
P (v′
i| pai) (1)
Example: Hard interventions do(Vi =v′
i) are local interventions wheref(vi) is a constant function.
Example: Translations are local interventions as do(Vi = vi + k) = do(Vi = f(vi)) where
f(vi) =vi +k. Examples include changing the position of objects in RL environments (Shah et al.,
2022) and images (Engstrom et al., 2019).
Example: Logical NOT operationX7→¬X for BooleanX is a local intervention.
We also consider stochastic interventions, noting that mixtures of local interventions can also be
defined without knowledge ofG. For example, adding noise to a variableX =X +ϵ,ϵ∼N (0, 1),
is a soft intervention onX described by a mixture over local interventions (translations).
Definition 3 (Mixtures of interventions). A mixed interventionσ∗ =P
ipiσi forPpi = 1 performs
interventionσi with probabilitypi. Formally,P (v|σ∗) =P
ipiP (v|σi).
2.2 D ECISION TASKS
Decision tasks involve a decision maker (agent) choosing a policy so as to optimise an objective
function (utility). To give a causal description of decision tasks we use the causal influence diagram
(CID) formalism (Howard & Matheson, 2005; Everitt et al., 2021), which extend a CBN of the
environment (chance) variables by introducing decision and utility nodes (see Figure 1 for examples).
For simplicity we focus on tasks involving a single decision and a single utility function.
Definition 4 (Causal influence diagram). A (single-decision, single-utility) causal influence diagram
(CID) is a CBNM = (G,P ) where the variablesV are partitioned into decision, utility, and chance
variables,V = ({D},{U},C). The utility variable is a real-valued function of its parents,U(paU).
Single-decision single-utility CIDs can represent most decision tasks such as classification and
regression as they specify what decision should be made (d∈D), based on what information (paD),
with objective (E[U]). They can also describe some multi-decision tasks such as Markov decision
processes1. The utility is any real-valued function including standard loss and reward functions.
We assume that the environment is described by a set of random variablesC that interact via causal
mechanisms2, and whereC satisfies causal sufficiency (Pearl, 2009) (includes all common causes),
noting that such a choice ofC always exists. We refer to the CBN overC as the ‘true’ or ‘underlying’
CBN. Note we do not assume the agent has any knowledge of the underling CBN, nor do we assume
which variables inC are observed or unobserved by the agent, beyond that the agent can observe
PaD⊆C. We also assume knowledge of the utility functionU(PaU).
The conditional probability distribution for the decision nodeπ(d| paD) (the policy) is not a fixed
parameter of the model but is set by the agent so as to maximise its expected utility, which for a policy
π is Eπ[U] = E[U| do(D =π(paD))]. A policy π∗ is optimal if it maximises Eπ∗
[U]. Typically,
agents do not behave optimally and incur some regretδ, which is the decrease in expected utility
compared to an optimal policyδ := Eπ∗
[U]− Eπ[U].
To simplify our theoretical analysis, we focus on a widely studied class of decision tasks where the
agents decision does not causally influence the environment (e.g. Figure 1).
Assumption 1 (Unmediated decision task). DescD∩ AncU =∅.
In unmediated decision tasks, the agent is provided some (partial) observations of the environment
and chooses a policy, which is then evaluated using the utility function which is a function of the
1Note Markov decision processes can be formulated as a single-decision single-utility CID, by modelling the
choice of policy as a single decision and the cumulative discounted reward as a single utility variable.
2This assumption follows from Reichenbach (1956), and we discuss further in Appendix A.3
3

Published as a conference paper at ICLR 2024
UD
YX
(a) training
UD
YX
(b) testing
UD
YX
(c) known domain shift
Figure 1: CID for a supervised learning task during (a) training and (b) testing following a distribu-
tional (covariate) shift (unsupervised domain adaptation, Wilson & Cook, 2020). The agent chooses
a label prediction D = ˆY given featuresX, with the goal of minimising loss U =−Loss(Y, ˆY ).
Decision variables are depicted as square nodes, chance variables as circular nodes and utilities as
diamond nodes. Information edges (dashed) show the variables the agent conditions their policy on.
In this example the labels cause the featuresY →X (for examples where features cause labels see
Castro et al., 2020; Schölkopf et al., 2012). The black square (‘regime node’ (Correa & Bareinboim,
2020)) in (b) and (c) denotes a distributional shift induced by an intervention on X. Diagram (c)
depicts the idealised case where the agent knows what domain shift has occurred. By theorem 1,
if the agent can return an optimal decision boundary for known covariate and label shifts, then it
must have learned the CBN overC ={X,Y}. Note that even if the agent has sufficient training data
to learnP (X,Y ), the causal structureY →X is in general non-identifiable givenP (X,Y ) and so
domain adaptation requires that the agent solves a non-trivial causal discovery problem.
environment state and the agent’s decision. Examples of unmediated decision tasks include prediction
tasks such as classification and regression, whereas examples of mediated decision tasks that are
not covered by our theorems include Markov decision processes where the agent’s decision (action)
influences the utility via the environment state.
2.3 D ISTRIBUTIONAL SHIFTS
We focus on generalisation that goes beyond the iid assumption, where agents are evaluated in
domains that are distributionally shifted from the training environment. Distributional shifts can
be changes to the environment (domain shifts), as in domain adaptation and domain generalisation
(Farahani et al., 2021; Wilson & Cook, 2020), or changes to the objective (task shifts) as in zero shot
learning (Xian et al., 2018), in-context learning (Brown et al., 2020) and multi-task reinforcement
learning (Reed et al., 2022). Our analysis focuses on domain shifts that involve changes to the causal
data generating process, and hence can be modelled as interventions (Schölkopf et al., 2021). This
does not assume that all shifts an agent will encounter can be modelled as interventions, but requires
that the agent is at least capable of adapting to these shifts.
Examples of interventionally generated shifts include translating objects in images (Engstrom et al.,
2019), noising inputs and adversarial robustness (Hendrycks & Dietterich, 2019), and changes to the
initial conditions or transition function in Markov decision processes (Peng et al., 2018). Examples
of shifts that are not naturally represented as interventions include changing the set of environment
variablesC, and introducing selection biases (Shen et al., 2018). See Appendix A.3 for discussion.
Our main results restrict to local domain shifts, which correspond to local interventions on the chance
variablesC. We do not consider shifts that change the agent’s decisionD, although we include shifts
that drop inputs to the policy PaD→ Pa′
D⊆ PaD (e.g. masking) as local interventions. We do not
consider task shifts i.e. changing the utility function.
As we are interested in determining the capabilities necessary for domain adaptation, we restrict
our attention to decision tasks where domain adaptation is non-trivial, i.e. where the optimal policy
depends on the environment distributionP (C =c).
Assumption 2 (Domain dependence). There existsP (C =c) andP′(C =c) compatible withM
such thatπ∗ = arg maxπ Eπ
P [U] impliesπ∗̸= arg maxπ Eπ
P′[U].
Assumption 2 implies the existence of domain shifts that change the optimal policy.
4

Published as a conference paper at ICLR 2024
3 C AUSAL MODELS ARE NECESSARY FOR ROBUST ADAPTATION
We now present our results, showing that learning the underlying CBN is necessary and sufficient for
learning regret bounded policies under a large set of domain shifts. In Section 3.2 we interpret these
results by considering their consequences for transfer learning, causal inference and adaptive agents.
First we focus on the idealised case where we assume optimality. We show for almost all decision
tasks the underlying CBN can be reconstructed given optimal policies for a large set of domain shifts.
Theorem 1. For almost all CIDs M = (G,P ) satisfying Assumptions 1 and 2, we can identify
the directed acyclic graphG and joint distributionP over all ancestors of the utility AncU given
{π∗
σ(d| paD)}σ∈Σ whereπ∗
σ(d| paD) is an optimal policy in the domainσ and Σ is the set of all
mixtures of local interventions. Proof in Appendix C.
The parameters P (vi | pai), U(paU) of the underlying CBN define a parameter space and the
condition for almost all CIDs means that the subset of the parameter space for which the Theorem 1
does not hold is Lebesgue measure zero (see Appendix A.2 for discussion). This condition is
necessary because there exist finely-tuned environments for which the CBN cannot be identified given
the agent’s policy due to variablesX∈ AncU that do not affect the expected utility. For example
considerX→ Y → U,Y =N (0,x ) andU = D +Y , then changing X can only change the
variance ofU while leaving its expected value (and hence the optimal policy) constant. However, this
only occurs for very specific choices of the parametersP andU.
In Appendix B we give a simplified overview of the proof with a worked example. We assume access
to an oracle for optimal policiesπ∗
σ for any given local intervention onC. Note, this assumes the
agent is robust to distributional shifts on a causally sufficient set of variablesC, not that the set of
variables the agent observes is causally sufficient. We devise an algorithm that queries this oracle with
different mixtures of local interventions and identifies the mixtures for which the optimal policies
changes. We then show that these critical mixtures identify the parameters of the CBN, specifying
both the graphG(AncU) and the joint distributionP (AncU).
3.1 R ELAXING THE ASSUMPTION OF OPTIMALITY
We now relax the assumption of optimality, considering the case where the policies πσ satisfy a
regret bound Eπσ[U]≥ Eπ∗
σ[U]−δ. We show that forδ >0 we can recover an approximation of the
environment CBN, with error that grows linearly inδ forδ≪ Eπ∗
[U].
Theorem 2. For almost all CIDs M = (G,P ) satisfying Assumptions 1 and 2, we can iden-
tify an approximate causal model M′ = (P′,G′) given{πσ(d | paD)}σ∈Σ where Eπσ[U] ≥
Eπ∗
σ[U]−δ and Σ is the set of mixtures of local interventions. The parameters of M′ satisfy
|P′(vi| pai)−P (vi| pai)|≤ γ(δ)∀Vi∈ V whereγ(0) = 0 andγ(δ) grows linearly in δ for
small regretδ≪ Eπ∗
[U]. Proof in Appendix D.
The worst-case error boundsγ(δ) for the parameter errors are detailed in Appendix D. Forδ >0 it
may not be possible to identifyG perfectly as some weak causal relations cannot be resolved due
to these error bounds. We describe in Appendix D how we can learn a sub-graphG′⊆G that may
exclude directed edges corresponding to weak causal relations.
Theorem 2 shows that we can learn a (sparse) approximate causal models of the data generating
process from regret bounded policies under domain shifts, where the approximation becoming exact
asδ→ 0. In Appendix F we demonstrate learning the underlying CBN from regret-bounded policies
using simulated data for randomly generated CIDs similar to Figure 1, and explore how the accuracy
of the approximate CBN scales with the regret bound (Figure 3).
Finally, we prove sufficiency, i.e. that having an (approximate) causal model of the data generating
process is sufficient to identify regret-bounded policies. The result is well-known for the non-
approximate case (Bareinboim & Pearl, 2016).
Theorem 3. Given the CBNM = (P,G ) that is causally sufficient we can identify optimal policies
π∗
σ(d| paD) for any givenU where PaU⊆C and for all soft interventionsσ. Given an approximate
causal model M′ = (P′,G′) for which|P′(vi| pai)−P (vi| pai)| ≤ϵ≪ 1, we can identify
regret-bounded policies where the regretδ grows linearly inϵ. Proof in Appendix E.
5

Published as a conference paper at ICLR 2024
(a) Error rate for learned DAG v.s. regret bound
 (b) Mean error forP (x,y ) v.s. regret bound
Figure 3: Comparing the model-average error rates for a) the learned DAGG′ and b) learned joint
distributionP′(x,y ), v.s. the (normalised) regret boundδ/


E[u|D = 1]− E[u|D = 0]


. Average
error taken over 1000 randomly generated environments with binary decisionD and two binary latent
variablesX,Y . Comparison to error rate for random guess (green) See Appendix F for details.
Together, Theorems 2 and 3 imply that learning an approximate causal model of the data generating
process is necessary and sufficient for learning regret-bounded policies under local interventions.
3.2 I NTERPRETATION
We interpret Theorems 1 to 3 through three lenses; agents, transfer learning and causal inference.
Agents are adaptive goal-directed systems (Dennett, 1989), meaning they choose actions they expect
to achieve some desired outcome, and would adapt their behaviour if they knew the consequences of
their actions had changed. For example, a firm sets prices to maximise profit, and adapts pricing to
changes to supply and demand (Kenton et al., 2023).
Consider an agent capable of zero-shot generalisation under domain shifts (Kirk et al., 2023). First,
consider the case where the agent has perfect knowledge of the domain shift, i.e. the policy conditions
on the domain indicator3πσ =π(d| paD,σ ). By Theorem 2 ifπσ satisfies a tight regret bound for
all local shiftsσ, we can reconstruct the underlying CBN from the agent’s policy alone (following the
procedure in Appendix C). Therefore, any agent capable of generalising under known local domain
shifts must have learned the underling CBN. Precisely, the agent has learned the policyπ(d| paD,σ ),
which is functionally equivalent to learning the underlying CBN, as any associative or causal query
that can be identified using the CBN can also be identified usingπ(d| paD,σ ). Ifσ is unknown and
has to be inferred by the agent, the underlying CBN can similarly reconstructed from the agent’s
policy as long as it satisfies a tight regret bound4.
Example: Doctors are agents expected to make low regret decisions under a wide range of known
distributional shifts, without re-training in the shifted environment. For example, consider the task of
risk-stratifying patients based on their signs and medical history. The doctor may be transferred to a
new ward where patients have received a treatment (known distributional shift) that has a stochastic
effect on latent variables (mixed intervention) such as curing diseases and causing side effects. The
doctor cannot re-train in this new domain, e.g. taking random decisions and observing outcomes. To
be capable of this, Theorem 2 implies the doctor must have learned the causal relations between the
relevant latent variables—how the treatment affects diseases, how these diseases and their symptoms
are causally related, and so on. Likewise, any medical AI that hopes to replicate this capability must
have learned a similarly accurate causal model, and the better the agent’s performance the more
accurate its causal model must be.
3equivalently an environment index for (in-context) invariant risk minimization (Gupta et al., 2023; Arjovsky
et al., 2019), or the context variable for zero-shot reinforcement learning (Kirk et al., 2023)
4Trivially, any agent capable of returning a regret-bounded policy without inputσ can do so givenσ simply
by discardingσ. If the agent adapts by conditioning their policy on an inferredσ′ (see Kirk et al. (2023) for a
review of implementations), and this policy satisfies a regret bound, it can be used in Theorems 1 and 2.
6

Published as a conference paper at ICLR 2024
Transfer learning. In transfer learning (Zhuang et al., 2020), models are trained on a set of source
domains and evaluated on held-out target domains where i) the data distribution differs from the source
domains, and ii) the data available for training is restricted compared to the source domains (Wang
et al., 2022). For example, in unsupervised domain adaptation the learner is restricted to samples
of the input features from the target domains paD∼P (PaD;σ), whereas in domain generalisation
typically no data from the target domain is available during training (Farahani et al., 2021).
LetDS denote the training data from the source domains andDσ denote the training data available
from a given target domainσ. Let there exist a transfer learning algorithm that returns a policyπσ
satisfying a regret bound for a given target domainσ, provided this training data. Asπσ is a function
of the training data, then by Theorems 1 and 2 the existence of this algorithm implies that we can
identify the underlying CBN fromDS∪{Dσ}σ∈Σ. To see that this imparts non-trivial constraints on
the existence of the transfer learning algorithm, we can consider the following simple example.
Example: Consider the CID for the supervised learning task depicted in Figure 1. Let DS =
{(xi,yi)∼ P (X,Y )}n
i=1, so for sufficiently large n the agent can learn the P (X,Y ) fromDS.
However,Y →X must also be identifiable from the training dataDS∪{Dσ}σ∈Σ. In other words,
the transfer learning problem contains a hidden causal discovery problem. IfDσ =∅ thenY →X
must be identifiable fromP (x,y ) alone, which is impossible unless the causal data generating process
obeys additional assumptions (see for example Hoyer et al., 2008). If unlabelled features from the
target domain are included in the training dataDσ ={xi∼P (X;σ)}nσ
i=1,Y →X can in principle
be identified asP (X;σY )̸=P (X).
Causal inference. Theorem 1 can also be interpreted purely in terms of causal inference. We can
compare to the causal hierarchy theorem (CHT) (Bareinboim et al., 2022), which states that an oracle
for L1 queries (observational) is almost always insufficient to evaluate all L2 queries (interventional).
Our Theorem 1 can be stated in an analogous way; an oracle for optimal policies under mixtures of
local interventions Π∗
Σ :σ7→π∗(σ), can evaluate all L2 queries, which follows from the fact that the
oracle identifies the underlying CBN which in turn identifies all L2 queries. Note Π∗
Σ is a strict subset
of L2, and we describe a subset of L2 as being L2-complete if evaluating these queries is sufficient to
evaluate all L2 queries. Hence Theorem 1 can be summarised as Π∗
Σ is L2-complete. It would be
interesting in future work to determine what other strict subsets of L2 are L2-complete, as identifying
these queries is sufficient to identify all interventional queries.
Why is this surprising? Firstly, we may expect the optimal policies to encode a relatively small
number of causal relations, as they can be computed from E[u| d, paD;σ], which describes the
response of a single variable U to intervention σ. However, Theorem 1 shows that the optimal
policies encode all causal and associative relations in AncU , including causal relations between latent
variables, for exampleP (Yx) for anyX,Y ⊆ AncU . Secondly, Theorems 2 and 3 combined imply
that learning to generalise under domain shifts is equivalent to learning a causal model of the data
generating process—problems that on the surface are conceptually distinct.
Figure 4: The set L2 (Bareinboim et al., 2022) contains all casual queries including the set of optimal
policies under domain π∗
C and task shifts π∗
U . We show that π∗
C also contains L2, i.e. learning
optimal policies under all shifts for a single utilityU is sufficient to identify L2
7

Published as a conference paper at ICLR 2024
4 D ISCUSSION
Here we discuss the consequences for several fields and open questions, as well as limitations.
Causal representation learning. Causal representation learning (CRL) aims to learn representations
of data that capture unknown causal structure (Schölkopf et al., 2021), with the aim of exploiting
causal invariances to achieve better generalisation across domains. Theorems 1 and 2 show that any
method that enables generalisation across many domains necessarily involves learning an (approxi-
mate) causal model of the data generating process—i.e. a causal representation. Hence, our results
provide theoretical justification for CRL by showing it is necessary for strong robustness guarantees.
Causal bounds on transfer learning. As described in Section 3.2, Theorems 1 and 2 imply
fundamental causal constraints on certain transfer learning tasks. For example in the supervised
learning task depicted in Figure 1, identifying regret-bounded policies under covariate and label
shifts requires learning the causal relations between features and labels. Causal discovery problems
such as this are well understood in many settings (V owels et al., 2022), and in general identifying
this causal structure (e.g. that Y → X in Figure 5 a)) is impossible without interventional data
and/or additional assumptions. This connection allows us to convert (im)possibility results for causal
discovery to (im)possibility results for transfer learning. Future work could explore this for smaller
sets of distributional shifts and derive more general causal bounds on transfer learning.
Good regulator theorem. The good regulator theorem is often interpreted as saying that any good
controller of a system must have a model of that system (Conant & Ross Ashby, 1970). However,
some imagination is needed to take this lesson from the actual theorem, which technically only states
that there exists an optimal regulator that is a deterministic function of the state of the system (which
could be trivial, Wentworth (2021)). Our theorem less ambiguously states that any robust agent must
have learned an (approximate) causal model of the environment, as described in Section 3.2. It can
therefore be interpreted as a more precise, causal good regulator theorem.
Emergent capabilities. Causal models enable a kind of general competency—an agent can use a
causal model of its environment to optimise for any given objective functionU(PaU⊆V ) without
additional data (Theorem 3). This could explain how general competence can arise from narrow
training objectives (Brown et al., 2020; Silver et al., 2021). By Theorems 1 and 2, agents trained
to maximise reward across many environments are incentivized to learn a causal world model (as
they cannot generalise without one), which can in turn be used to solve any other decision task in the
same environment. This incentive does not imply that training an agent with a simple reward signal is
sufficient to learn causal world models. E.g. it will still be impossible for an agent to learn a causal
model (and therefore to generalise) if the model is not identifiable from its training data. The question
is then if current methods and training schemes are sufficient for learning causal world models.
Early results suggest that transformer models can learn world models capable of out-of-distribution
prediction (Li et al., 2022, see Section 6 for discussion). While foundation models are capable of
achieving state of the art accuracy on causal reasoning benchmarks (Kıcıman et al., 2023), how they
achieve this (and if it constitutes bona fide causal reasoning) is debated (Zeˇcevi´c et al., 2023).
Causal discovery. Theorems 1 and 2 involve learning the causal structure of the environment
by observing the agent’s policy under interventions. It is perhaps surprising that the response of
this single variable to interventions is sufficient to identify all associative and causal relations in
AncU . Typically, causal discovery algorithms involve measuring the response of many variables to
interventions (V owels et al., 2022). Also, many causal discovery algorithms assume independent
causal mechanisms (Schölkopf et al., 2021), which is equivalent to assuming no agents are present in
the data generating process (Kenton et al., 2023). However, our results suggest that agents could be
powerful resources for causal discovery. In Appendix B we use the proof of Theorem 2 to derive a
causal discovery algorithm for learning causal structure over latents, and test it on synthetic data.
Applicability of causal methods. Causal models have been used to formally define concepts such as
intent (Halpern & Kleiman-Weiner, 2018; Ward et al., 2024), harm (Richens et al., 2022), deception
(Ward et al., 2023b), manipulation (Ward et al., 2023a) and incentives (Everitt et al., 2021), and are
required for approaches to explainability (Wachter et al., 2017) and fairness (Kusner et al., 2017).
Methods for designing safe and ethical AI systems that build on these definitions require causal
models of the data generating process, which are typically hard to learn, leading some to doubt their
practicality (Fawkes et al., 2022; Rahmattalabi & Xiang, 2022). However, our results show that
learning a causal model of the data generating process is necessary for training robust agents, and
8

Published as a conference paper at ICLR 2024
demonstrate that these models can be elicited from these agents. These models could in turn be used
to support causal methods for aligning agents.
Limitations. Theorems 1 and 2 require agents to be robust to a large set of domain shifts (local
interventions on all environment variables). Theorem 2 shows that loosening regret bounds results
in some causal relations being unidentifiable from the agent’s policy. Hence, we expect it is still
possible to learn some casual knowledge of the environment from agents that are robust to a smaller
set of domain shifts, albeit less complete that the full underlying CBN. Finally, our results only apply
to unmediated decision tasks (Assumption 1). We expect Theorems 1 and 2 can be extended to active
decision tasks, as Assumption 1 does not play a major role beyond simplifying the proofs.
5 R ELATED WORK
Several recent empirical works have explored if deep learning models learn ‘surface statistics’ (e.g.
correlations between inputs and outputs) or learn internal representations of the world (McGrath
et al., 2022; Abdou et al., 2021; Li et al., 2022; Gurnee & Tegmark, 2023). Our results offer some
theoretical clarity to this discussion, tying an agents performance to the fidelity its world model,
and that going beyond ‘surface statistics’ to learning causal relations is fundamentally necessary
for robustness. One study in particular (Li et al., 2022) found that a GPT model trained to predict
legal next moves in the board game Othello learned a linear representation of the board state (Nanda,
2023). Further, this internal representation of the board state could be changed by intervening on
the intermediate activations, with the model updating its predictions consistent with the intervention,
including interventions that take the board state outside of the training distribution. This indicates
that the network is learning and utilising a representation of the data generating process that can
support out-of-distribution generalisation under interventions—much like a causal model.
The problem of evaluating policies under distributional shifts has been studied extensively in causal
transportability (CT) theory (Bareinboim & Pearl, 2016; Bellot & Bareinboim, 2022). CT aims to
provide necessary and sufficient conditions for policy evaluation under known domain shifts when all
assumptions on the data generating process (i.e. inductive biases) can be expressed as constraints
on causal structure (Bareinboim & Pearl, 2016). However, deep learning algorithms can exploit a
much larger set of inductive biases (Neyshabur et al., 2014; Battaglia et al., 2018; Rahaman et al.,
2019; Goyal & Bengio, 2022) which in many real-world tasks may be sufficient to identify low regret
policies without requiring causal knowledge. Thus, CT does not imply that agents must learn causal
models in order to generalise unless we assume agents only use causal assumptions to begin with,
which would be proof by assumption. See Appendix G for further discussion.
A similar result to Theorems 1 and 2 is the causal hierarchy theorem (CHT) (Bareinboim et al.,
2022; Ibeling & Icard, 2021), which shows that observational data is almost always insufficient for
identifying all causal relations between environment variables, whereas our results state that the set of
optimal policies is almost always sufficient to identify all causal relations. In Section 3.2 we discuss
the similarities between these theorems, and in Appendix G we discuss their differences.
6 C ONCLUSION
Causal reasoning is foundational to human intelligence, and has been conjectured to be necessary for
achieving human level AI (Pearl, 2019). In recent years, this conjecture has been challenged by the
development of artificial agents capable of generalising to new tasks and domains without explicitly
learning or reasoning on causal models. And while the necessity of causal models for solving causal
inference tasks has been established (Bareinboim et al., 2022), their role in decision tasks such as
classification and reinforcement learning is less clear.
We have resolved this conjecture in a model-independent way, showing that any agent capable of
robustly solving a decision task must have learned a causal model of the data generating process,
regardless of how the agent is trained or the details of its architecture. This hints at an even deeper
connection between causality and general intelligence, as this causal model can be used to find
policies that optimise any given objective function over the environment variables. By establishing a
formal connection between causality and generalisation, our results show that causal world models
are a necessary ingredient for robust and general AI.
9

Published as a conference paper at ICLR 2024
Acknowledgements. We would like to thank Alexis Bellot, Damiano Fornasiere, Pietro Greiner,
James Fox, Matt MacDermott, David Reber, David Watson and Philip Bachman for their helpful
discussions and comments on the manuscript.
REFERENCES
Mostafa Abdou, Artur Kulmizev, Daniel Hershcovich, Stella Frank, Ellie Pavlick, and Anders
Søgaard. Can language models encode perceptual structure without grounding? a case study in
color. arXiv preprint arXiv:2109.06129, 2021.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization.
arXiv preprint arXiv:1907.02893, 2019.
Elias Bareinboim and Judea Pearl. Controlling selection bias in causal inference. In Artificial
Intelligence and Statistics, pp. 100–108. PMLR, 2012a.
Elias Bareinboim and Judea Pearl. Transportability of causal effects: Completeness results. In
Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 698–704, 2012b.
Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the
National Academy of Sciences, 113(27):7345–7352, 2016.
Elias Bareinboim, Juan D Correa, Duligur Ibeling, and Thomas Icard. On pearl’s hierarchy and the
foundations of causal inference. In Probabilistic and Causal Inference: The Works of Judea Pearl,
pp. 507–556. 2022.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi,
Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al.
Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261,
2018.
Alexis Bellot and Elias Bareinboim. Partial transportability for domain generalization. 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are
few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020.
Daniel C Castro, Ian Walker, and Ben Glocker. Causality matters in medical imaging. Nature
Communications, 11(1):3673, 2020.
Taco Cohen and Max Welling. Group equivariant convolutional networks. InInternational conference
on machine learning, pp. 2990–2999. PMLR, 2016.
Roger C Conant and W Ross Ashby. Every good regulator of a system must be a model of that
system. International journal of systems science, 1(2):89–97, 1970.
Juan Correa and Elias Bareinboim. A calculus for stochastic interventions: Causal effect identification
and surrogate experiments. In Proceedings of the AAAI conference on artificial intelligence ,
volume 34, pp. 10093–10100, 2020.
A P Dawid. Influence diagrams for causal modelling and inference. International Statistical Review /
Revue Internationale de Statistique, 70:161–189, 2002.
Daniel C Dennett. The intentional stance. MIT press, 1989.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. Exploring
the landscape of spatial robustness. In International conference on machine learning, pp. 1802–
1811. PMLR, 2019.
Tom Everitt, Ryan Carey, Eric D Langlois, Pedro A Ortega, and Shane Legg. Agent incentives: A
causal perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35,
pp. 11487–11495, 2021.
10

Published as a conference paper at ICLR 2024
Abolfazl Farahani, Sahar V oghoei, Khaled Rasheed, and Hamid R Arabnia. A brief review of domain
adaptation. Advances in Data Science and Information Engineering: Proceedings from ICDATA
2020 and IKE 2020, pp. 877–894, 2021.
Jake Fawkes, Robin Evans, and Dino Sejdinovic. Selection, ignorability and challenges with causal
fairness. In Conference on Causal Learning and Reasoning, pp. 275–289. PMLR, 2022.
Alison Gopnik, Laura Schulz, and Laura Elizabeth Schulz. Causal learning: Psychology, philosophy,
and computation. Oxford University Press, 2007.
Anirudh Goyal and Yoshua Bengio. Inductive biases for deep learning of higher-level cognition.
Proceedings of the Royal Society A, 478(2266):20210068, 2022.
Sharut Gupta, Stefanie Jegelka, David Lopez-Paz, and Kartik Ahuja. Context is environment, 2023.
Wes Gurnee and Max Tegmark. Language models represent space and time. arXiv preprint
arXiv:2310.02207, 2023.
Joseph Halpern and Max Kleiman-Weiner. Towards formal definitions of blameworthiness, intention,
and moral responsibility. In Proceedings of the AAAI Conference on Artificial Intelligence ,
volume 32, 2018.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common
corruptions and perturbations. arXiv preprint arXiv:1903.12261, 2019.
Ronald A Howard and James E Matheson. Influence diagrams. Decision Analysis, 2(3):127–143,
2005.
Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear
causal discovery with additive noise models. Advances in neural information processing systems,
21, 2008.
Duligur Ibeling and Thomas Icard. A topological perspective on causal inference. Advances in
Neural Information Processing Systems, 34:5608–5619, 2021.
Zachary Kenton, Ramana Kumar, Sebastian Farquhar, Jonathan Richens, Matt MacDermott, and Tom
Everitt. Discovering agents. Artificial Intelligence, pp. 103963, 2023.
Emre Kıcıman, Robert Ness, Amit Sharma, and Chenhao Tan. Causal reasoning and large language
models: Opening a new frontier for causality. arXiv preprint arXiv:2305.00050, 2023.
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A survey of zero-shot
generalisation in deep reinforcement learning. Journal of Artificial Intelligence Research , 76:
201–264, 2023.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in
neural information processing systems, 30, 2017.
Shane Legg and Marcus Hutter. Universal intelligence: A definition of machine intelligence. Minds
and machines, 17:391–444, 2007.
Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Watten-
berg. Emergent world representations: Exploring a sequence model trained on a synthetic task.
arXiv preprint arXiv:2210.13382, 2022.
Thomas McGrath, Andrei Kapishnikov, Nenad Tomašev, Adam Pearce, Martin Wattenberg, Demis
Hassabis, Been Kim, Ulrich Paquet, and Vladimir Kramnik. Acquisition of chess knowledge in
AlphaZero. Proceedings of the National Academy of Sciences, 119(47):e2206625119, 2022.
Christopher Meek. Strong completeness and faithfulness in bayesian networks. arXiv preprint
arXiv:1302.4973, 2013.
Nicolai Meinshausen. Causality from a distributional robustness point of view. In 2018 IEEE Data
Science Workshop (DSW), pp. 6–10. IEEE, 2018.
11

Published as a conference paper at ICLR 2024
Jovana Mitrovic, Dino Sejdinovic, and Yee Whye Teh. Causal inference via kernel deviance measures.
Advances in neural information processing systems, 31, 2018.
Joris M Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Bernhard Schölkopf. Distin-
guishing cause from effect using observational data: methods and benchmarks. The Journal of
Machine Learning Research, 17(1):1103–1204, 2016.
Neel Nanda. Actually, othello-gpt has a linear emergent world model, Mar 2023. URL <https:
//neelnanda.io/mechanistic-interpretability/othello>.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the
role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614, 2014.
Masashi Okamoto. Distinctness of the eigenvalues of a quadratic form in a multivariate sample. The
Annals of Statistics, pp. 763–765, 1973.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2 edition
edition, 2009. ISBN 9780521895606.
Judea Pearl. Theoretical impediments to machine learning with seven sparks from the causal
revolution. arXiv preprint arXiv:1801.04016, 2018.
Judea Pearl. The seven tools of causal inference, with reflections on machine learning. Communica-
tions of the ACM, 62(3):54–60, 2019.
Judea Pearl and Elias Bareinboim. Transportability of causal and statistical relations: A formal
approach. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 25, pp.
247–254, 2011.
Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of
robotic control with dynamics randomization. In 2018 IEEE international conference on robotics
and automation (ICRA), pp. 3803–3810. IEEE, 2018.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua
Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference
on Machine Learning, pp. 5301–5310. PMLR, 2019.
Aida Rahmattalabi and Alice Xiang. Promises and challenges of causality for ethical machine
learning. arXiv preprint arXiv:2201.10683, 2022.
Scott Reed, Konrad Zolna, Emilio Parisotto, Sergio Gomez Colmenarejo, Alexander Novikov, Gabriel
Barth-Maron, Mai Gimenez, Yury Sulsky, Jackie Kay, Jost Tobias Springenberg, et al. A generalist
agent. arXiv preprint arXiv:2205.06175, 2022.
Hans Reichenbach. The direction of time, volume 65. Univ of California Press, 1956.
Jonathan Richens, Rory Beard, and Daniel H Thompson. Counterfactual harm. Advances in Neural
Information Processing Systems, 35:36350–36365, 2022.
Donald B Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal
of the American Statistical Association, 100(469):322–331, 2005.
Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij.
On causal and anticausal learning. arXiv preprint arXiv:1206.6471, 2012.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner,
Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the
IEEE, 109(5):612–634, 2021.
Rohin Shah, Vikrant Varma, Ramana Kumar, Mary Phuong, Victoria Krakovna, Jonathan Uesato,
and Zac Kenton. Goal misgeneralization: Why correct specifications aren’t enough for correct
goals. arXiv preprint arXiv:2210.01790, 2022.
12

Published as a conference paper at ICLR 2024
Zheyan Shen, Peng Cui, Kun Kuang, Bo Li, and Peixuan Chen. Causally regularized learning
with agnostic data selection bias. In Proceedings of the 26th ACM international conference on
Multimedia, pp. 411–419, 2018.
David Silver, Satinder Singh, Doina Precup, and Richard S Sutton. Reward is enough. Artificial
Intelligence, 299:103535, 2021.
Steven A Sloman and David Lagnado. Causality in thought. Annual review of psychology , 66:
223–247, 2015.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction,
and search. MIT press, 2000.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu
Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: a family of highly capable
multimodal models. arXiv preprint arXiv:2312.11805, 2023.
Matthew J V owels, Necati Cihan Camgoz, and Richard Bowden. D’ya like dags? a survey on
structure learning and causal discovery. ACM Computing Surveys, 55(4):1–36, 2022.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening
the black box: Automated decisions and the GDPR. Harv. JL & Tech., 31:841, 2017.
Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun
Zeng, and Philip Yu. Generalizing to unseen domains: A survey on domain generalization. IEEE
Transactions on Knowledge and Data Engineering, 2022.
Francis Rhys Ward, Tom Everitt, Francesco Belardinelli, and Francesca Toni. Honesty is the best
policy: defining and mitigating AI deception. In Thirty-seventh Conference on Neural Information
Processing Systems, 2023a.
Francis Rhys Ward, Francesca Toni, and Francesco Belardinelli. Defining deception in structural
causal games. In Proceedings of the 2023 International Conference on Autonomous Agents and
Multiagent Systems, pp. 2902–2904, 2023b.
Francis Rhys Ward, Matt MacDermott, Francesco Belardinelli, Francesca Toni, and Tom Everitt. The
reasons that agents act: Intention and instrumental goals. arXiv preprint arXiv:2402.07221, 2024.
John Wentworth. Fixing the good regulator theorem. https://www.alignmentforum.org/
posts/Dx9LoqsEh3gHNJMDk/fixing-the-good-regulator-theorem , 2021. Ac-
cessed: 2023-10-17.
Garrett Wilson and Diane J Cook. A survey of unsupervised deep domain adaptation. ACM
Transactions on Intelligent Systems and Technology (TIST), 11(5):1–46, 2020.
Yongqin Xian, Christoph H Lampert, Bernt Schiele, and Zeynep Akata. Zero-shot learning—a
comprehensive evaluation of the good, the bad and the ugly. IEEE transactions on pattern analysis
and machine intelligence, 41(9):2251–2265, 2018.
Matej Zeˇcevi´c, Moritz Willig, Devendra Singh Dhami, and Kristian Kersting. Causal parrots: Large
language models may talk causality but are not causal. arXiv preprint arXiv:2308.13067, 2023.
Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and
Qing He. A comprehensive survey on transfer learning. Proceedings of the IEEE, 109(1):43–76,
2020.
13

Published as a conference paper at ICLR 2024
A P RELIMINARIES
A.1 S ETUP AND ASSUMPTIONS
The environment is described by a set of random variables C = {C1,C 2,...,C N}, which in
combination with the decision D and utility nodes U define the state space for the CID V =
C∪{D,U}. In out notation individual variablesCi∈C are given indexes, whereas set of variables
are indexless and bold, and we useV =v as short hand for the joint state of the variables in a set
C. The joint probability distribution P (C =c,D = d,U = u) describes the statistical relations
between environment variables. Bayesian networks factorise joint probability distributions according
to a graphG (Pearl, 2009).
Definition 1 (Bayesian networks). A Bayesian networkM = (G,P ) over a set of variablesV =
{V1,...,V n} is a joint probability distributionP (V ) that factors according to a directed acyclic
graph (DAG)G, i.e.P (V1,...,V n) =Qn
i=1P (Vi| PaVi), where PaVi are the parents ofVi inG.
The distributions and statistical relationships between variables may change as a result of external
interventions applied to a system. Hard interventions set a subset C′ ⊆ C of the variables to
particular values c′, denoted do(C′ = c′) or do(c′). Naively, one joint probability distribution
Pdo(c′) would be needed to describe the updated relationship under each possible intervention do(c′).
Fortunately, all interventional distributions can be derived from a single Bayesian network, if G
matches the causal structure of the environment (i.e. has an edgeVi→Vj whenever an intervention
onVi directly influences the value of another variableY , and lacks unmodeled confounders; Spirtes
et al., 2000; Pearl, 2009). When this holds, we call the Bayesian network causal andG a causal
graph. With respect to the causal graphG we denote the direct causes (parents) ofVi as Pai, the set of
all causes (ancestors) Anci, and the variables thatVi directly causes (children) Chi and descendants
Desci as the set of all downstream variables. Note in particular that Anci and Desci refer to proper
ancestors and descendants, i.e. Vi̸∈ Anci andVi̸∈ Desci. We denote a causal Bayesian network
(CBN) asM = (P,G ) whereP is the joint andG is the directed acyclic graph (DAG) describing the
causal structure of the environment. Further, the interventional distributionPdo(v′) is given by the
truncated factorisation
Pdo(v′)(v) =
(Q
i:vi̸∈v′P (vi| pavi) ifv consistent withv′
0 otherwise.
Equivalently, the effect of interventions can be computed by adding an extra node ˆX and edge
ˆVi→ Vi for each node Vi∈ V (Correa & Bareinboim, 2020; Dawid, 2002). Intervening on Vi
then corresponds to conditioning on ˆVi in the extended graph. More general, soft interventions
σ = P′(Vi| Pa∗
i ) replace the conditional probability distribution for Vi with a new one, possibly
using a new parent set Pa∗
o as long as no cycles are introduced in the graph (Correa & Bareinboim,
2020). The modified environment is denotedM(σ).
General soft interventions cannot be defined without prior knowledge of the causal graph G. For
example, the soft interventionσY =P′(y|x) is incompatible with the causal structureY →X as it
would introduce a causal cycle, and so an agent’s policy may not be well defined with respect to this
intervention. We therefore focus our theoretical analysis on a subset of the soft interventions, local
interventions, that can be implemented without assuming knowledge ofG.
Definition 2 (Local interventions). Local intervention σ onVi∈ V involves applying a map to
the states of Vi that is not conditional on any other endogenous variables, vi7→ f(vi). We use
the notationσ = do(Vi =f(vi)) (variableVi is assigned the statef(vi)). Formally, this is a soft
intervention onVi that transforms the conditional probability distribution as,
P (vi| pai;σ) =
X
v′
i:f(v′
i)=vi
P (v′
i| pai) (1)
Example: Fixing the value of a variable (hard intervention) is a local intervention as do(Vi =v′
i) =
do(Vi =f(vi)) wheref(vi) =v′
i.
Example: Translations are local interventions as do(Vi = vi +k) = do(Vi = f(vi)) where
f(vi) = vi +k. This includes changing the position of objects in RL environments (Shah et al.,
2022).
14

Published as a conference paper at ICLR 2024
Example: Logical NOT operationX→¬X for BooleanX
We also consider mixtures of interventions, which can also be described without knowledge ofG.
Definition 3 (Mixtures of interventions). A mixed interventionσ∗ =P
ipiσi forPpi = 1 performs
interventionσi with probabilitypi. Formally,P (v|σ∗) =P
ipiP (v|σi).
Example: Adding Gaussian noise is a mixture over local operations (translations) σϵ = do(X =
X +ϵ) whereϵ∼N (0, 1).
In common to most decision making tasks such as prediction, classification, and reinforcement
learning, is that a decision should be outputted based on some information to optimise some objective.
The exact terms vary: decisions are sometimes called outputs, actions, predictions, or classifications;
information is sometimes called features, context, or state; and objectives are sometimes called
utility functions or loss functions. However, all of these setups can be described within the causal
influence diagram (CID) framework (Howard & Matheson, 2005; Everitt et al., 2021). CIDs are
causal Bayesian networks where the variables are divided into decision D, utility U, and chance
variablesV , and no conditional probability distribution is specified for the decision variables. The
task of the agent is to select the distributionπ =P (D =d| PaD = paD), also known as the policy
or decision rule. An optimal policyπ∗ is defined as a policyπ∗ that maximizes the expected value of
the utility Eπ∗[U].
Definition 4 (Causal influence diagram). A (single-decision, single-utility) causal influence diagram
(CID) is a CBNM = (G,P ) where the variablesV are partitioned into decision, utility, and chance
variables,V = ({D},{U},C). The utility variable is a real-valued function of its parents,U(paU).
By convention, decision nodes are drawn square, utility nodes diamond, and chance nodes round. The
parents ofD, PaD, can be interpreted as the information the decision is allowed to depend on, and
are depicted as dashed lines. See Figure 5 for an example. In the following we restrict our attention
to a class of CIDs we refer to as ‘unmediated decision tasks’, where where the agent’s decision does
not causally influence any chance variables that go on to influence the utility. This simplifies our
theoretical analysis, although it is likely that our results extend to the general case.
Assumption 1 (Unmediated decision task). DescD∩ AncU =∅.
Examples of unmediated decision tasks include all standard classification and regression tasks, and
generative AI tasks where the output is not included in the training set. For example, in classification
typically the choice of label does not influence the data generating process. Problems that are
mediated rather than unmediated decision tasks includes most control and reinforcement learning
tasks, where the agent’s decision is an action that influences the state of the environment. Furthermore,
we will focus on non-trivial unmediated decision tasks i.e. whereU∈ ChD, as the case ChD =∅
describes trivial decision tasks (the agent’s action does not influence the utility). Figure 5 is an
example of a non-trivial unmediated decision task.
In transfer learning we are typically interested in problems where generalising from the source
to target domain(s) is non-trivial, and in the trivial case we cannot expect agents to have to learn
anything about their environments in order to generalise. If this is not the case, then generalising
under distributional shifts is trivial. Therefore we restrict our attention to decision tasks where the
distribution of the environment is relevant to the agent when determining its policy. Specifically, we
say that a decision task is domain independent if there exists a single policy that is optimal for all
choices of environment distributionP (C =c).
Assumption 2 (Domain dependence). There existsP (C =c) andP′(C =c) compatible withM
such thatπ∗ = arg maxπ Eπ
P [U] impliesπ∗̸= arg maxπ Eπ
P′[U].
Lemma 1. Domain dependence implies that;
i) There exists no d∈ dom(D) such thatd∈ arg maxdU(d,c )∀c∈ dom(C).
ii) PaD ⊊ AncU
iii) D∈ PaU
Proof. i) For any P′ we have EP′[U | do(D = d), paD] = P
cP′(Cd = c | paD)U(d,c)
= P
cP′(C = c| paD)U(d,c ) where we have used DescD∩ AncU =∅. Therefore if ∃ d∗
15

Published as a conference paper at ICLR 2024
C1
C2
C3C4
C5 C6
D U
Figure 5: The CID for an unmediated decision task, where D has no causal influence on the
environment stateC. Our main theorem implies that an agent that is robust to distributional shifts
onC must learn the CBN over AncU ={C1,C 2,C 3,C 4,C 6}, noting that C5̸∈ AncU . C4 is an
example of a variable that is only an ancestor ofU viaD and so has no direct causal effect on the
utility, but is still relevant to the decision task as it is a proxy for C1 which is a cause of U. C6 is
a cause of U but not of D, and naively one might assume that distributional shifts on C6 cannot
influence the agent’s decision. However, the optimal policy can change under distributional shifts on
C6 as these effect the utility, and hence the agent will have to learn a CBN includingC6 if it is to be
robust to shifts onC6.
s.t. d∗ = arg maxdU(d,c)∀ C = c then EP′[U | do(D = d∗), paD] ≥ P
cP′(C = c |
paD)U(d′,c)EP′[U| do(D =d), paD]∀d̸=d∗, and soD =d∗ is optimal for allP′(C =c) and
we violate domain dependence.
ii) AsD∈ PaU (iii), then PaU⊆ AncU . If AncU = PaD then EP [u|d, paD] =U(d, paD) which
is independent of P (C =c), and hence there is a single optimal policy for all P and we violate
domain dependence.
iii) IfD̸∈ AncU then the CID is trivial, in the sense that E[U| do(D =d)] = E[U], and hence all
decisions are optimal for all distributionsP (C), which violates domain dependence (Assumption 2).
ThereforeD∈ AncU which with DescD∩ AncU =∅ impliesD∈ PaU .
A.2 P ARAMETERISATION OF CID S
The joint distributionP is defined for all environment variablesC, and the CID is defined by the
parameters forP (C) andU(PaU). We restrict our attention toC that are categorical, and without loss
of generality we label statesci = 0, 1,..., dimi−1 where dimi is the dimension of variableCi. Firstly,
the jointP (C) is parameterised by the conditional probability distributions (CPDs) in the Markov
factorization with respect to G,θP ={P (ci| pai)∀ci∈{ 0,..., dimi− 2}, pai∈ Pai, Ci∈C.
Note that the CPDsp(Ci = dimi− 1| pai) are not included inθP as they are fully constrained by
normalizationP (Ci = dimi− 1| pai) = 1−Pdimi−1
j=0 P (ci| pai). Secondly, the utility function is
simply parameterised by its value given the state of its parentsθU ={U(paU)∀ PaU = paU}. For
simplicity we work with the normalized utility function,
U(paU)→
U(paU)− minpa′
U
U(PaU = pa′
U)
maxpa′
U
U(PaU = pa′
U)− minpa′
U
U(PaU = pa′
U) (2)
with values between 0 and 1. Noting that as this is a positive affine transformation of the utility
function the set of optimal policies invariant, and we can re-scale regret bounds accordingly. LetθM
denote the set of all parameters for the CID,θM =θP∪θU , and note that the elements ofθM in the
[0, 1] interval and are logically independent, i.e. we can independently choose any [0, 1] value for
each parameter and this defines a valid parameterization of the CID for the baseline environment. In
the following when we refer to ‘the parametersP,U ’ we are referring toθM .
We follow the method outlined in (Meek, 2013) to prove that certain constraints onP,U hold ‘for
almost allP,U ’ and hence for almost all decision tasks. This involves converting a given constraint
into polynomial equations overθM and applying the following Lemma,
Lemma 2 (Okamoto, 1973). The solutions to a (nontrivial) polynomial are Lebesgue measure zero
over the space of the parameters of the polynomial.
16

Published as a conference paper at ICLR 2024
A polynomial inn variables is non-trivial (not an identity) if not all instantiations of then variables
are solutions of the polynomial. For example, the equation poly(θM) = 0 is trivial if and only if all
coefficients of the polynomial expression poly(θM) are zero. Therefore, any constraint onP,U that
can be converted into a polynomial equation overθM must either hold for allθM or for a Lebesgue
measure zero subset of instantiations ofθM .
Operationally, this means that if we have any smooth distribution over the parameter space (for
example, describing the distribution of environments we expect to encounter), the probability of
drawing an environment from this distribution for which the condition does not hold is 0.
A.3 D ISTRIBUTIONAL SHIFTS & POLICY ORACLES
In the derivation of our results we restrict out attention to distributional shifts that can be modelled
as (soft) interventions on the data generating process. We note that by Reichenbach’s principle
(Reichenbach, 1956), which states that all statistical associations are due to underlying causal
structures, we can assume the existence of a causal data generating process that can be described
in terms of a CBN M = (P,G ). Therefore there is a causal factorization of the joint P (C =
c) =Q
iP (ci| Pai). By allowing for mixtures of interventions, we can reach any distribution over
C, which can be seen trivially by noting that we can perform a soft intervention to achieve any
deterministic distributionP (C =c) =δ(C =c′), and then take a mixture over these deterministic
distributions to achieve an arbitrary distribution over C. The set of distributions that cannot be
generated by interventions include those that change the set of variablesV including the decision and
utility variables, and introducing selection biases (which are causally represented with the introduction
of additional nodes that are conditioned on Bareinboim & Pearl, 2012a). For further discussions on
the relation between distributional shifts and interventions see Schölkopf et al. (2021); Meinshausen
(2018).
In the following proofs we use policy oracles to formalise knowledge of regret-bounded behaviour
under distributional shifts.
Definition 5 (Policy oracle). A policy oracle for a set of interventions Σ is a map Πδ
Σ :σ7→πσ(d|
paD)∀σ∈ Σ where Σ is a set of domains. It isδ-optimal ifπσ(d| paD) achieves an expected utility
Eπσ[U]≥ Eπ∗
[U]−δ in the CIDM(σ) whereδ≥ 0.
Hereδ is the regret upper bound, which is satisfied under all distributional shiftsσ∈ Σ. We refer
toδ-optimal policy oracles for δ = 0 as optimal policy oracles. For the proof of our main result
we restrict our attention to policy oracles with Σ that includes mixtures over all local interventions
(def. 2).
Note that the policy oracle specifies only what policy the agent returns in a distributionally shifted
environmentM(σ). It does not specify how this policy is generated, which will depend on the
specific setup. For example, in domain generalisation that agent typically receives no additional data
from the target domains, and is expected to produce a policy (decision boundary) that achieves a low
regret across all target domains. On the other hand in domain adaptation and few shot learning, the
agent is provided with some new data from each target domain with which to adjust its policy. As we
hope to accommodate all of these perspectives we specify only the agent’s policy, not the data used
to generate it. This is discussed further in Section 3.2.
What distributional shifts do we consider? In our proofs, we assume the agent is robust to any
domain shifts that can be described as a mixture of local interventions on the environment variables
C. We do not consider interventions that change the utilityU or the agent’s decisionD, though we
do include dropping inputs to the policy (masking) PaD→ Pa′
D⊆ PaD as local interventions.
B A PPENDIX : S IMPLIFIED PROOF
In this section we outline the proof of Theorem 1 for a simple binary decision task with binary
latent variables. As mentioned in Section 4, the method used to identify the CBN in Theorem 1 can
be viewed as an algorithm for learning the CBN over latent variables by observing the policy of a
regret-bounded agent under various distributional shifts. To demonstrate this, in Appendix F we use
an implementation of the algorithm on randomly generated CIDs, showing empirically that we can
17

Published as a conference paper at ICLR 2024
learn the underlying CBN in this way, and explore how the agent’s regret bound affects the accuracy
of the learned CBN.
Consider the CID in Figure 6, describing a binary decision taskD∈{ 0, 1} with two binary latent
variablesX,Y ∈ PaU .
U
X Y
D
Figure 6: Example CID describing a context-free mutli-armed bandit with binary latent variables
X,Y .
Consider an agent that selects a policyπD such that it maximises the expected utility. That is, the
CID describes a context-free bandit problem, whereX,Y are latent variables that influence the arm
values E[u|d] =P
x,yP (x,y )U(x,y,d ).
Our aim is to learn this CID given only knowledge of the agent’s policy under distributional shifts,
and knowledge that it satisfies a regret bound. We assume knowledge of i) the set of chance variables
C ={X,Y}, ii) the utility functionU(d,x,y ), and iii) the policyπD(σ) under distributional shifts
σ (other variables (U,X,Y ) are unobserved). To learn the CID the aim is therefore to learn the
parameters of the joint distribution over latentsP (x,y ) and the unknown causal structure. As we know
the utility function we knowD,X,Y ∈ PaU , and by assuming the CID is unmediated (Assumption 1)
we knowX,Y ̸∈ DescD. Likewise the decision task is context free hence D̸∈ DescX∪ DescY .
Hence the only unknown causal structure is the DAG over the latent variablesC ={X,Y}.
The expected utility difference betweenD = 0 andD = 1 following a hard intervention onX is
given by
E[u|D = 0; do(X = 0)]− E[u|D = 1; do(X = 0)] =
X
y
P (YX=0 =y)[U(0, 0,y )−U(1, 0,y )]
(3)
=P (YX=0 = 0)[U(0, 0,Y = 0)−U(1, 0, 0)] + (1−P (YX=0 = 0))[U(0, 0, 1)−U(1, 0, 1)]
(4)
As we know U(d,x,y ) we can therefore identify P (YX=0 = 0) if we can identify this expected
utility difference. We do this using the agent’s policy under distributional shifts, and in this simple
case we can restrict our attention to hard interventions. Following the steps outlined in Lemma 4,
domain dependence insures that we can identify a hard interventionσ2 = do(X =x′,Y =y′) that
results in a different optimal policy to the optimal policy under σ1 = do(X = 0). For a mixture
of these two interventions σ3 = qσ1 + (1−q)σ2 the expected utility is E[u| d,σ 3] = qE[u|
d,σ 1] + (1−q)E[u|d,σ 2]. This is a linear function with respect to q, and forq = 1 the optimal
decision (d1) is different than forq = 0 (d2̸=d1). Therefore, there is a single indifference pointqcrit
for which both decisions are optimal. It is simple to show that this indifference point is given by,
qcrit =

1− E[u|D =d1; do(X = 0)]− E[u|D =d2; do(X = 0)]
U(d1,x′,y′)−U(d2,x′,y′)
−1
(5)
D =d1 is optimal forq≤qcrit andD =d2 is optimal forq≥qcrit. We can estimateqcrit by randomly
sampling values ofq uniformly over [0, 1] and observing the optimal decision under the resulting
mixed intervention (Algorithm 1). That is, qcrit is the probability that D = d1 is returned by the
policy oracle for a randomly sampledq. In this way we learnqcrit and as we knowU(d,x,y ) we can
identify the expected utility difference under do(X = 0) in the numerator of Equation (5) and so
identifyP (YX=0 = 0).
Similarly we identify P (YX=1 = 0),P (XY =0 = 0) and P (XY =1 = 0) , which encode both
the causal relation between X and Y (e.g. there is a directed path from X to Y if and only if
P (YX=0)̸=P (YX=1) for almost all CBNs), and determine the parameters of the CBN asP (Ci =
ci| do(C\Ci)) =P (Ci =ci| Pai = pai).
18

Published as a conference paper at ICLR 2024
C P ROOF OF THEOREM 1
In this appendix we prove Theorem 1. For an informal overview of the proof see Appendix B.
First, we show that for a given distributional shift σ, for almost all P,U there is a single optimal
decision. While this is not necessary for our proof, it simplifies our analysis. And as our main
theorem holds for almost allP,U , we can include any finite number of independent conditions that
hold for almost allP,U without strengthening this condition, as the union of Lebesgue measure zero
sets is Lebesgue measure zero.
Lemma 3. For any given local interventionσ there is a single deterministic optimal policy for almost
allP,U .
Proof. Following interventionσ two decisionsd,d′ are simultaneously optimal in context paD if,
E[u| paD, do(D =d);σ] = E[u| paD, do(D =d′);σ] (6)
LetZ = [AncU\ PaD] andX = PaU\{D}. Noting that
E[u| paD, do(D =d);σ] =
X
z
U(d,x)P (z, paD| do(D =d);σ)/P (paD| do(D =d);σ) (7)
and that P (paD| do(D = d);σ) = P (paD;σ) andP (z, paD| do(D = d);σ) = P (z, paD;σ)
which follows from DescD∩ AncU =∅, we can multiple both sides of equation 6 withP (paD;σ)
giving, X
z
U(d,x)P (z, paD;σ) =
X
z
U(d′,x)P (z, paD;σ) (8)
and X
z
[U(d,x)−U(d′,x)]P (z, paD;σ) = 0 (9)
Let σ = do(v1 = f1(v1),...,v N = fN(vN)). The joint P (z, paD;σ) = Q
iP (ci | pai;σ)
is polynomial, and the local interventions P (ci | pai;σ) = P
c′
i:fi(c′
i)=ciP (c′
i | pai) keep it
polynomial. Therefore equation 9 is a polynomial equation over the model parameters, and is certain
to be non-trivial asd̸=d′. Therefore by Lemma 2 for almost all P,U equation 9 is not satisfied, and
as there are a finite number of decisions this implies that for almost allP,U there is a single optimal
decision for a givenσ, paD and hence a single optimal policy.
Next, we detail how a policy oracle can be used to identify a specific causal query in the shifted
environmentM(σ), that we will later use to identify the model parameters.
Lemma 4. Using an optimal policy oracleΠ∗
Σ where Σ includes all mixtures of local interventions on
C including masking inputs Pa′
D⊆ PaD, then for any given Pa′
D = pa′
D such that Pa′
D∩ PaU =∅
we can identifyP
zP (C =c;σ)[U(d,c)−U(d′,c)], ford andd′ whered̸=d′ andZ =C\ Pa′
D.
Proof. By Lemma 3 for almost allP,U there is a single optimal decision following the shiftσ. Let
d1 = arg maxd E[u| do(D =d), pa′
D;σ] whered1 =π∗(σ). We can identifyd1 by querying the
policy oracle withσ.
Consider a hard intervention on all Ci∈C,σ′ := do(c′
1,c′
2,...,c ′
N) where for allCi∈ Pa′
D we
setCi = ci to be the same state as in observation Pa′
D = pa′
D. The expected utility under this
intervention is E[u| do(D = d), pa′
D;σ′] = U(d,x′) whereX = PaU\{D} (and we have that
D∈ PaU from Lemma 1 iii)).
Next we show that there is a choice of hard interventionσ′ such that the policy oracle must return
different optimal decisions in the context Pa′
D = pa′
D forσ′ andσ. As Pa′
D∩ PaU =∅ then we are
free to choose anyX =x′ and the resultingσ′ will be compatible with the evidence Pa′
D = pa′
D.
Note that by Lemma 1 i) ∃X =x′ s.t. d1̸= arg maxdU(d,x′), else D = d1 is optimal for all
X =x which violates domain dependence. We can determine thisX =x′ given the utility function
andd1. Letd2 = arg maxdU(d,x′) andσ′ = do(c′
1,c′
2,...,c ′
N) be the hard intervention for which
X =x′ and Pa′
D = pa′
D.
19

Published as a conference paper at ICLR 2024
Consider the joint distribution overC under the mixed local intervention ˜σ(q) =qσ + (1−q)σ′,
P (C =c| do(D =d); ˜σ(q)) =P (C =c; ˜σ(q)) (10)
=qP (C =c;σ) + (1−q)P (C =c;σ′) (11)
where in the first line we have usedChD ={U} to drop the intervention. Note thatZ =C\PaD̸=∅
by Lemma 1 i). The expected utility is given by,
E[u| paD, do(D =d); ˜σ(q)] =
X
z
P (Z =z| paD, do(D =d); ˜σ(q))U(d,x) (12)
=
X
z
P (C =c| do(D =d); ˜σ(q))
P (paD| do(D =d); ˜σ(q)) U(d,x) (13)
= 1
P (paD; ˜σ(q))
X
z
P (C =c; ˜σ(q))U(d,x) (14)
= 1
P (paD; ˜σ(q))
X
z
qP (C =c;σ)U(d,x) + (1−q)P (C =c;σ′)U(d,x′) (15)
Note that forq = 1 the optimal decision isd1 and forq = 0 the optimal decision returned by the policy
oracle belongs to the set{d s.t.d = arg maxdU(d,x′)} which does not containd1. Furthermore,
the argmax of equation 15 with respect to d is a piecewise linear function with domain q∈ [0, 1].
Therefore there must be someq =qcrit that is the smallest value ofq such that forq <qcrit the policy
oracle returns an optimal decision in the set {d s.t.d = arg maxdU(d,x′)} and for q≥ qcrit the
optimal decision is not in this set. The value ofqcrit is given by E[u| paD, do(D =d); ˜σ(qcrit)] = 0,
which by equation 15 is,
qcrit
X
z
P (C =c;σ)[U(d2,x)−U(d3,x)] + (1−qcrit)[U(d2,x′)−U(d3,x′)] = 0 (16)
whered2∈{d s.t.d = arg maxdU(d,x′)} andd3̸∈{d s.t.d = arg maxdU(d,x′)}. This yields
the following expression forqcrit,
qcrit =

1−
P
z
P (C =c;σ)[U(d2,x)−U(d3,x)]
U(d2,x′)−U(d3,x′)


−1
(17)
where we have used P
z
P (C = c;σ′)[U(d2,c)−U(d3,c)] = U(d2,x′)−U(d3,x′). We can
determineP
zP (C =c;σ)[U(d2,x)−U(d3,x)] givenqcrit and the utility functionU(d,x).
Finally, we describe a Algorithm 1 (below) that uses a policy oracle for the Monte Carlo estimation
ofqcrit, which can be used to determineP
zP (C =c;σ)[U(d2,c)−U(d3,c)]) in the asymptotic
limitN→∞ as well as identifyingd2,d 3.
We are now ready to derive Theorem 1.
Theorem 1. For almost all CIDs M = (G,P ) satisfying Assumptions 1 and 2, we can identify
the directed acyclic graphG and joint distributionP over all ancestors of the utility AncU given
{π∗
σ(d| paD)}σ∈Σ whereπ∗
σ(d| paD) is an optimal policy in the domainσ and Σ is the set of all
mixtures of local interventions. Proof in Appendix C.
Proof. We learn the graphG and parametersP (ci| pai) by learning ‘leave-one-out’ interventional
distributionsP (ci| do(c1,...,c i−1,ci+1,...,c N)). Note that under this intervention Ci depends
only on its parent set and henceP (ci| do(c1,...,c i−1,ci+1,...,c N) =P (ci| pai) where Pai =
pai denotes the state of Pai under the leave-one-out intervention. Almost allP are causally faithful
(Meek, 2013). Hence, for almost allP , these interventional distributions can be used to determine
Pai as in the interventional distributionCi̸⊥Cj if and only ifCj∈ Pai. Explicitly, for almost all
environments,Cj∈ Pai if and only if there are two leave-one-out interventions that differ only on
20

Published as a conference paper at ICLR 2024
Algorithm 1 Identifyqcrit,d 2,d 3 using policy oracle. Input: (U, Π∗
Σ,N,σ )
d1← Π∗
Σ(σ)
σ′,d 2← any hard intervention onC s.t.d2 = arg maxdU(d,x)̸=d1
D(q = 1)←{d s.t.d = arg maxdU(d,x′)}
θ = 0
for i← 1 to N do
q∼ Uniform(0, 1)
π∗(d| paD)← Π∗
Σ(σ3(q))
ifd∈D(q = 1) ∀π∗(d| paD)> 0 then
θ←θ + 1
end if
end for
qcrit =θ/N
D(qcrit)← Π∗
Σ(qcritσ + (1−qcrit)σ′)
d3∈D(qcrit),d3̸=d2
returnqcrit,d 2,d 3
Cj withCj = cj andCj = c′
j such that P (ci| do(c1,...,c j,...,c i−1,ci+1,...,c N))̸= P (ci|
do(c1,...,c ′
j,...,c i−1,ci+1,...,c N)). For ease of notation we will useP (ci| pai) interchangeably
withP (ci| do(c1,...,c j,...,c i−1,ci+1,...,c N)).
First we learn the parameters for chance variables that have a directed path toU that does not include
D, i.e. are ancestors ofU in the graphG ˆD where we intervene onD.
Case 1: learning parameters forCi∈ AncU(G ˆD).
Consider a directed pathCk→... →C1 whereC1∈ PaU and all variables are chance nodes (the
path does not include D). Assume we know Pak−1,..., Pa1 and the parameters P (Ci| pai) for
i = k− 1,..., 1. We show that given these parameters we can identify the unknown parameters
P (ck| pak) (and hence Pak). Define Y =C\{Ck,...,C 1} and consider the local intervention
σ = do(y1,...,y N−k,ck =f(ck)) where do(ck =f(ck)) is a local intervention onCk such that,
f(Ck) =
c′
k, Ck =c′
k
c′′
k otherwise (18)
I.e. f(Ck) mapsCk to a 2 dimensional subspace where the image of Ck =c′
k isCk =c′
k and all
other states being mapped toCk =c′′
k, wherec′
k,c′′
k̸=c′
k are arbitrary states ofCk. In the following
we mask all inputs to the policy Pa′
D =∅.
By Lemma 4 we can identify,
X
c
P (C =c;σ)[U(d,c)−U(d′,c)]
=
X
ck
...
X
c1
P (ck| pak;σ)...P (c1| pa1;σ)[U(d,c)−U(d′,c)]
=
X
ck
P (ck| pak;σ)β(ck) (19)
where
β(ck) :=
X
ck−1
...
X
c1
P (ck−1| pak−1;σ)...P (c1| pa1;σ)[U(d,c)−U(d′,c)] (20)
andβ(c1) := [U(d,c)−U(d′,c)]. Note that in equation 19 β(ck) is determined by the known
parametersP (ck−1| pak−1),...,P (c1| pa1) andU(paU), andβ(ck) are non-zero for almost all
P,U asβ(ck) = 0 is a polynomial equation in these parameters it is not satisfied for almost allP,U .
Using the definition of the local intervention in equation 18 we have P (Ck = c′
k | pak;σ) =
P (Ck =c′
k| pak), andP (Ck =c′′
k| pak;σ) = 1−P (Ci =c′
k| pak;σ) = 1−P (Ck =c′
k| pak).
Therefore the right hand side of equation 19 has a single undetermined parameterP (Ck =c′
k| pak)
21

Published as a conference paper at ICLR 2024
and the left hand side can be determined using the policy oracle (Lemma 4), and we can solve
forP (Ck = c′
k| pak). By repeating this procedure with different interventions, varying the hard
intervention do(Y =y) and the choices ofc′
k,c′′
k, we can identifyP (ck| pak) for allck, pak and
hence Pak.
We now learn the parameters for allCi∈ AncU(G ˆD). We know the set PaU as this is the domain of
the utility functionU(PaU) which is known by assumption. We can then proceed iteratively, first
learning the parameters ofP,G that areP (c1| pa1) and Pa1 for someC1∈ PaU . We can do this as
β(c1) =U(d,x)−U(d′,x) withd,d′x returned by Algorithm 1 in Lemma 4 andU(PaU) is known.
We can then determine the parameters for allCj∈ Pa1, and so on until we have traversed Anc1. We
repeat this for allCi∈ PaU until we have covered all AncU(G ˆD).
Case 2: learning parameters forCi∈ AncD,Ci̸∈ AncU(G ˆD).
Consider Ck ∈ AncU for which all directed paths to U are via D, Ck → Ck−1 → ... → C1
whereC1∈ ˜PaD. As before, assume we know Pak−1,..., Pa1 and the parametersP (Ci| pai) for
i =k− 1,..., 1. We now show that given these parameters we can identify the unknown parameters
P (ck| pak) (and hence Pak). DefineY =C\{Ck,...,C 1} and letσ = do(y1,...,y N−k,ck =
f(ck)) where do(ck = f(ck)) is a local intervention defined in equation 18. We now mask all
evidence exceptC1, i.e. Pa′
D ={C1}. Note that asC1̸∈ PaU we can apply Lemma 4, giving (for
k≥ 2)
X
z
P (C =c;σ)[U(d,c)−U(d′,c)]
=
X
ck
...
X
c2
P (ck| pak;σ)...P (c1| pa1)[U(d,c)−U(d′,c)] (21)
=
X
ck
P (ck| pak)α(ck) (22)
whereZ =C\{C1} and,
α(ck) :=
X
ck−1
...
X
c2
P (ck−1| pak−1)...P (c1| pa1)[U(d,c)−U(d′,c)] (23)
and fork = 1 we have,
X
z
P (C =c;σ)[U(d,c)−U(d′,c)] =P (C1 =c1| pa1;σ)α(1) (24)
where α(1) := [ U(d,x)−U(d′,x)]. We can determine α(ck) as we know the parameters for
Ck−1,...,C 1 by assumption, and α(ck)̸= 0 for almost all P,U as the equation α(ck) = 0 is a
polynomial in the model parameters by Lemma 2 it is not satisfied for almost all P,U . Using the
definition of the local intervention equation 18 we haveP (Ck =c′
k| pak;σ) =P (Ck =c′
k| pak),
andP (Ck = c′′
k| pak;σ) = 1−P (Ci = c′
k| pak;σ) = 1−P (Ck = c′
k| pak). Therefore the
right hand side of equation 19 has a single undetermined parameterP (Ck =c′
k| pak) and the left
hand side can be determined using the policy oracle (using Lemma 4, noting Pa′
D ={C1} and
{C1}∩ PaU =∅), and we can solve for P (Ck = c′
k| pak). By repeating this procedure with
different interventions, varying the hard intervention do(Y =y) and the choices ofc′
k,c′′
k, we can
identifyP (ck| pak) for allck, pak and hence Pak.
We now learn the parameters for allCi∈ AncD\ AncU(G ˆD). We know PaD from the domain of
the policy returned by the policy oracle. If the parameters for all variables in PaD have be learned
in the previous set, we are finished. Otherwise, there are variables that are in AncU for which all
directed paths toU are viaD. Let this set of variables by ˜PaD⊆ PaD. For anyC1∈ ˜PaD we can
determineα(c1) = U(d,x)−U(d′,x) withd,d′,x returned by Algorithm 1 in Lemma 4, noting
thatC1̸∈ PaU . We can then determine the parameters for all Cj∈ Pa1, and so on until we have
traversed Anc1, and repeat until we have learned the parameters for allCi∈ AncD\ AncU(G ˆD).
22

Published as a conference paper at ICLR 2024
D P ROOF OF THEOREM 2
In this section we derive a version of Lemma 4 using a δ-optimal policy oracle for δ > 0. The
reason we consider this case is that Theorem 1 assumes optimality, which is a strong assumption that
won’t be satisfied by realistic systems. It is therefore important to determine if our main results are
contingent on this assumption. For example, it may be that we can only identify a causal model from
the agent’s policy forδ = 0, and forδ >0 no causal model can be learned. Instead, what we find is
that realistic agents withδ >0 have to learn approximate causal models, with the fidelity of these
approximations increasing in a reasonable way asδ→ 0.
Low-regret analysis. What is a reasonable way for the approximation errors to change with δ?
Clearly, if an agent has an arbitrarily large regret bound we cannot expect to learn anything about the
environment from its policy. For example, a completely random policy can satisfy a large enough
regret bound, and an agent does not need to learn anything about the environment to learn this policy.
Therefore we must still constrain the regret to be small in our analysis, and the standard way to do
this by an order analysis.
We define ‘small regret’ as δ≪ Eπ∗
[U]. As we work with the normalised utility function (see
Appendix A.1), we have Eπ∗
[U]≤ 1 and so we can define the small regret regime asδ≪ 1. What
we find is that for small δ the order of the error in our estimation of the model parameters grows
linearly with the order of increase in the regret for agents that incur only a small regret. Therefore we
get a linear trade-off between regret and accuracy for smallδ.
First we show that Algorithm 1 allows us to estimate the value ofQ =P
zP (C =c;σ)[U(d,c)−
U(d′,c)] with an approximate value ˜Q, and estimate bounds ˜Q± such that the true value of Q is
guaranteed to satisfy ˜Q−≤Q≤ ˜Q+.
Lemma 5. Using aδ-optimal policy oracle Πδ
Σ where Σ includes all mixtures of local interventions,
including masking inputs Pa′
D⊆ PaD, then for any given Pa′
D = pa′
D such that Pa′
D∩ PaU =∅,
we can determined,d′,x′ whered̸=d′ and a point estimate ˜Q forQ(paD,d,d′) :=P
zP (C =
c;σ)[U(d,x)−U(d′,x)]< 0 and boundsQ∈ [ ˜Q−, ˜Q+] whereZ =C\ PaD,X = PaU\{D}
and,
1
1−ξ (Q−δ)≤ ˜Q≤ 1
1 +ξ (Q +δ) (25)
where
ξ :=δ/(U(d,x′)−U(d′,x′))> 0 (26)
and in the worst case these bounds scale withδ as
˜Q+≤
1−ξ
1 +ξ

Q + 2δ
1 +ξ (27)
˜Q−≥
1 +ξ
1−ξ

Q− 2δ
1−ξ (28)
Proof. By Lemma 3 for almost allP,U there is a single optimal decision following the shiftσ. Let
d1 be the optimal decision returned by the policy oracle in the context Pa′
D = pa′
D, which must
satisfy the bound E[u|d, paD;σ]≤ maxd E[u|d, paD;σ]−δ.
Consider a hard intervention on all Ci∈C,σ′ := do(c′
1,c′
2,...,c ′
N) where for allCi∈ Pa′
D we
setCi = ci to be the same state as in observation Pa′
D = pa′
D. The expected utility under this
intervention is E[u| do(D = d), pa′
D;σ′] = U(d,x′) whereX = PaU\{D} (and we have that
D∈ PaU from Lemma 1 iii)).
Next we show that there is a choice of hard interventionσ′ such that the policy oracle must return
different optimal decisions in the context Pa′
D = pa′
D forσ′ andσ. As Pa′
D∩ PaU =∅ then we are
free to choose anyX =x′ and the resultingσ′ will be compatible with the evidence Pa′
D = pa′
D.
Note that by Lemma 1 i) ∃X =x′ s.t. d1̸= arg maxdU(d,x′), else D = d1 is optimal for all
X =x which violates domain dependence. We can determine thisX =x′ given the utility function
andd1. Letd2 = arg maxdU(d,x′) andσ′ = do(c′
1,c′
2,...,c ′
N) be the hard intervention for which
X = x′ and Pa′
D = pa′
D. Note, we do not use the policy oracle to determine d2 which can be
23

Published as a conference paper at ICLR 2024
determined fromU(PaU) alone, and hence there is no uncertainty ifd2 is in fact optimal underσ′ for
any regret bound, nor thatd1 is not optimal underσ′.
Consider the joint distribution overC under the mixed local intervention ˜σ(q) =qσ + (1−q)σ′,
P (C =c| do(D =d); ˜σ(q)) =P (C =c; ˜σ(q)) (29)
=qP (C =c;σ) + (1−q)P (C =c;σ′) (30)
where in the first line we have usedChD ={U} to drop the intervention. Note thatZ =C\PaD̸=∅
by Lemma 1 i). The expected utility is given by,
E[u| paD, do(D =d); ˜σ(q)] =
X
z
P (Z =z| paD, do(D =d); ˜σ(q))U(d,x) (31)
=
X
z
P (C =c| do(D =d); ˜σ(q))
P (paD| do(D =d); ˜σ(q)) U(d,x) (32)
= 1
P (paD; ˜σ(q))
X
z
P (C =c; ˜σ(q))U(d,x) (33)
= 1
P (paD; ˜σ(q))
X
z
qP (C =c;σ)U(d,x) + (1−q)P (C =c;σ′)U(d,x′) (34)
Note that forq = 1 the optimal decision isd1 and forq = 0 the optimal decision returned by the policy
oracle belongs to the set{d s.t.d = arg maxdU(d,x′)} which does not containd1. Furthermore,
the argmax of equation 34 with respect to d is a piecewise linear function with domain q∈ [0, 1].
Therefore there must be someq =qcrit that is the smallest value ofq such that forq <qcrit the policy
oracle returns an optimal decision in the set {d s.t.d = arg maxdU(d,x′)} and for q≥ qcrit the
optimal decision is not in this set. The value ofqcrit is given by E[u| paD, do(D =d); ˜σ(qcrit)] = 0,
which by equation 34 is,
qcrit
X
z
P (C =c;σ)[U(d2,x)−U(d3,x)] + (1−qcrit)[U(d2,x′)−U(d3,x′)] = 0 (35)
whered2∈{d s.t.d = arg maxdU(d,x′)} andd3̸∈{d s.t.d = arg maxdU(d,x′)}. This yields
the following expression forqcrit,
qcrit =

1−
P
z
P (C =c;σ)[U(d2,x)−U(d3,x)]
U(d2,x′)−U(d3,x′)


−1
(36)
where we have usedP
z
P (C =c;σ′)[U(d2,c)−U(d3,c)] =U(d2,x′)−U(d3,x′).
While Algorithm 1 identifies the smallest value of q such that the optimal policy changes, as we
no longer have an optimal policy oracle, the probability ˜q returned by Algorithm 1 is no longer
necessarily equal toqcrit. Instead, there are minimal and maximal value of ˜q that Algorithm 1 can
return, which are determined by the regret bound (see Figure 7).
Our first aim is to boundqcrit using ˜q returned by the policy oracle. The maximal (minimal) values ˜q
can take while satisfying the regret bound areq±, which are the solutions to the equations
δ≥ E[u| paD, do(D =d2); ˜σ(q+)]− E[u| paD, do(D =d3); ˜σ(q+)] (37)
−δ≤ E[u| paD, do(D =d2); ˜σ(q−)]− E[u| paD, do(D =d3); ˜σ(q−)] (38)
Using equation 34 these simplify to
δP (paD;σ(q+))≥q+X
z
P (C =c;σ)[U(d2,x)−U(d3,x)] + (1−q+)[U(d2,x′)−U(d3,x′)]
(39)
δP (paD;σ(q−))≤q−X
z
P (C =c;σ)[U(d2,x)−U(d3,x)] + (1−q−)[U(d2,x′)−U(d3,x′)]
(40)
24

Published as a conference paper at ICLR 2024
We can relax and simplify these bounds by taking the maximum possible values for the unknown
quantityP (paD;σ(˜q))→ 1 giving,
δ≥q+X
z
P (C =c;σ)[U(d2,x)−U(d3,x)] + (1−q+)[U(d2,x′)−U(d3,x′)] (41)
δ≤q−X
z
P (C =c;σ)[U(d2,x)−U(d3,x)] + (1−q−)[U(d2,x′)−U(d3,x′)] (42)
Let ∆1 := E[u| paD, do(D = d2);σ]− E[u| paD, do(D = d3);σ] and ∆0 := U(d2,x′)−
U(d3,x′). Note that ∆0 > 0 as d2 is optimal under σ′, and ∆1 < 0 as by linearity we have
E[u| paD, do(D =d3); ˜σ(q)]> E[u| paD, do(D =d2); ˜σ(q)] forq >qcrit andqcrit < 1 therefore
E[u| paD, do(D = d3); ˜σ(1)] > E[u| paD, do(D = d2); ˜σ(1)]. We now define q± w.r.t the
(relaxed) bounds equation 41 and equation 42, and simplifying these inequalities using equation 36
gives
˜q≤q+ = min{1,q crit(1 +ξ)} (43)
˜q≥q− = max{0,q crit(1−ξ)} (44)
where
ξ :=δ/∆0 > 0 (45)
We therefore generate bounds onqcrit using equation 44 and equation 43, i.e.
qcrit≤ ˜q/(1−ξ) (46)
qcrit≥ ˜q/(1 +ξ) (47)
We use ˜q in place ofqcrit in equation 36, giving an estimate ˜Q forQ =P
zP (C =c;σ)[U(d2,x)−
U(d3,x)], yielding,
˜Q = ∆0 (1− 1/˜q) (48)
Finally, applying bounds equation 46 and equation 47 gives,
1
1−ξ (∆0−δ)≤ ˜Q≤ 1
1 +ξ (∆0 +δ) (49)
Next, we determine upper and lower boundsQ±(˜q) usingQ = ∆0(1− 1/qcrit) and equation 46 and
equation 47 giving,
Q≤ ˜Q+(˜q) = ∆0

1− 1−ξ
˜q

(50)
Q≥ ˜Q−(˜q) = ∆0

1− 1 +ξ
˜q

(51)
noting that as equation 48 is monotonic inq that the true value ofQ is guaranteed to fall between
these bounds. Finally, we derive expressions for the worst-case bounds in terms of the true value ofQ,
which are given by determining ˜Q± for the max and min values of ˜q which are given by equation 47
and equation 46,
Q+ = max
˜q
˜Q+(˜q) = ∆0

1− 1−ξ
1 +ξ
1
qcrit

(52)
=
1−ξ
1 +ξ

Q + 2δ
1 +ξ (53)
Q− = min
˜q
˜Q−(˜q) = ∆0

1− 1 +ξ
1−ξ
1
qcrit

(54)
=
1 +ξ
1−ξ

Q− 2δ
1−ξ (55)
25

Published as a conference paper at ICLR 2024
Figure 7: Overview of Lemma 5. ∆0 = U(d2,x′)−U(d3,x′) and ∆1 = E[u| paD, do(D =
d2);σ]− E[u| paD, do(D =d3);σ]. Using an optimal policy oracle we can identifyqcrit precisely
as detailed in Lemma 4. Forδ >0 instead of returningqcrit Algorithm 1 returns ˜q, as the agent can
incur regret and so the value ofq for which the policy changes is no longer constrained to be qcrit.
We use ˜q in place toqcrit to calculate an approximate value of the target query, in the same way as in
Lemma 4. The maximum and minimum values of ˜q can take areq± which result in maximal regretδ,
˜q≥q− =qcrit(1−δ/∆0) and ˜q≤q+ =qcrit(1 +δ/∆0). We can therefore bound the amount that
˜Q deviates from the value of the target queryQ.
Lemma 6. Forδ≪ Eπ∗
[U], ˜Q and ˜Q± (as defined in Lemma 5) satisfy bounds,



 ˜Q−Q



≤δ(1− Q
∆0
) +O(δ2) (56)
and
˜Q+−Q≤ 2δ(1− Q
∆0
) +O(δ2) (57)
Q− ˜Q−≥− 2δ(1− Q
∆0
) +O(δ2) (58)
Proof. As we work with the normalised utility function (see Appendix A.1), we have Eπ∗
[U]≤ 1
and so we can define the small regret regime asδ≪ 1. We can Taylor expand the bounds on ˜Q, ˜Q±
aboutδ = 0 giving,
Q−δ(1− Q
∆0
) +O(δ2)≤ ˜Q≤Q +δ(1− Q
∆0
) +O(δ2) (59)
and therefore, 


 ˜Q−Q



≤δ(1− Q
∆0
) +O(δ2) (60)
and
˜Q+−Q≤ 2δ(1− Q
∆0
) +O(δ2) (61)
Q− ˜Q−≥− 2δ(1− Q
∆0
) +O(δ2) (62)
therefore for smallδ the worst case error on our estimate ˜Q grows linearly inδ, and our upper and
lower bounds for ˜Q also grow linearly.
Theorem 2. For almost all CIDs M = (G,P ) satisfying Assumptions 1 and 2, we can iden-
tify an approximate causal model M′ = (P′,G′) given{πσ(d | paD)}σ∈Σ where Eπσ[U] ≥
Eπ∗
σ[U]−δ and Σ is the set of mixtures of local interventions. The parameters of M′ satisfy
|P′(vi| pai)−P (vi| pai)|≤ γ(δ)∀Vi∈ V whereγ(0) = 0 andγ(δ) grows linearly in δ for
small regretδ≪ Eπ∗
[U]. Proof in Appendix D.
26

Published as a conference paper at ICLR 2024
Proof. We use theδ−optimal policy oracle to estimate the model parameters following the same
steps as in the proof of Theorem 1 in Appendix C. However, as the policy oracle is no longer optimal,
the parameters estimates will have errors. Here, we show that for the parameters ofP these errors
grow linearly inδ forδ≪ 1, and that we learn a sparse sub-graph ofG.
Estimating parameters ofP .
In the proof of Theorem 1 we estimate the parametersP (ci| pai) in two cases.
Case 1.
Qk =
X
c
P (C =c;σ)[U(d,c)−U(d′,c)] =
X
ck
P (ck| pak;σ)β(ck) (63)
where
β(ck) :=
X
ck−1
...
X
c1
P (ck−1| pak−1;σ)...P (c1| pa1;σ)[U(d,c)−U(d′,c)] (64)
which we rearrange usingP (c′
k| pak;σ) = 1−P (c′′
k| pak;σ) to give,
P (c′
k| pak;σ) = Qk−β(c′′
k)
β(c′
k)−β(c′′
k) (65)
Assume we have approximate values ˆP (c′
k−1 | pak−1;σ),..., ˆP (c′
1 | pa1;σ) where ˆP (c′
k |
pak;σ) = P (c′
k | pak;σ) +O(δ), i.e. errors in our estimates for these parameters grow lin-
early inδ forδ≪ 1. Asβ(ck) is a sum of products of these parameter estimates, then our estimate
ofβ(ck) also has linear error forδ≪ 1, i.e. ˆβ(ck) =β(ck) +O(δ), and likewise,
ˆP (c′
k| pak;σ) = Qk−β(c′′
k) +O(δ)
β(c′
k)−β(c′′
k) +O(δ) =P (c′
k| pak;σ) (1 +O(δ)) (66)
Then fork = 1 we knowβ(c1) =U(d,c)−U(d′,c) precisely, and so
ˆP (c′
1| pa1;σ) = Q1−β(c′′
1) +O(δ)
β(c′
1)−β(c′′
1) =P (c′
1| pa1;σ) (1 +O(δ)) (67)
Which satisfies our assumption ofO(δ) error fork = 1,δ≪ 1. Therefore for all k we have error
that grows linearly inδ forδ≪ 1.
The expressions forQk,α (ck) for case 2 in the proof of Theorem 1 are similar, and it is trivial to
show by the same method that for these parameters the error also grow linearly inδ forδ≪ 1.
Learning graph structure. In Theorem 1 we determine Pak from P (ck | do(C\{ Ck})).
Assuming causal faithfulness, which is satisfied for almost all P (Meek, 2013), Cj∈ Pak if and
only ifP (ck| do(C\{Ck})) differ for someCj = cj,Cj = c′
j. However, as we now only have
estimates ˆP (ck| do(C\{Ck})), any variation with respect toCj =cj may be due to the varying
errors in these estimates rather than variation in the conditional probability itself. However, we
have shown that we can learn any P (ci| pai) within error bounds, and that these bounds scale
linearly with δ forδ≪ 1. Let Cj ∈ Pai+n andθkj = P (ck| do(C\{Ck})), and denote the
corresponding upper and lower bounds from Lemma 6 asθ±
kj. If∃θkj̸=θkj′ and eitherθ+
kj <θ−
kj′
orθ+
kj′ <θ−
kj, non-overlapping bounds forCj =cj andCj =c′
j, then we know with certainty that
Cj∈ Pak. If there are no such non-overlapping bounds for allj, we do not know ifCj∈ Pak and
so exclude it from the set. This approach is guaranteed to identify a sub-graph of G (i.e. no false
positives—directed edges present in the approximate CBN that are not present in the environment).
Further, we only miss a parent if in the true underlying causal model for all Pak = pak intervening
to changeCj gives|P (ck| pak, do(cj))−P (ck| pak, do(c′
j))|<O(δ). Hence forδ≪ 1 we only
fail to learn causal relations that small in magnitude (with respected to the regretδ), i.e. where the
causal effect of the parent on the child isO(δ).
27

Published as a conference paper at ICLR 2024
In Appendix F we explore the relation between the regret bound and the error in the learned causal
graph using simulated data, and find that even agents that incur relatively high regret can be used to
identify causal structure to a high accuracy compared to a random baseline.
E A PPENDIX : PROOF OF THEOREM 3
Theorem 3. Given the CBNM = (P,G ) that is causally sufficient we can identify optimal policies
π∗
σ(d| paD) for any givenU where PaU⊆C and for all soft interventionsσ. Given an approximate
causal model M′ = (P′,G′) for which|P′(vi| pai)−P (vi| pai)| ≤ϵ≪ 1, we can identify
regret-bounded policies where the regretδ grows linearly inϵ. Proof in Appendix E.
Proof. First we consider the case where we know the exact modelM = (P,G ). AsM is causally
sufficient we can identify E[u|d, paD;σ] for any given soft interventions compatible withG and
which involve only variables inG (which includes AncU∪{U}). Our policy oracle is constructed
by i) estimating E[u|d, paD;σ] for the inputσ, ii) calculatingd∗ = arg maxd E[u|d, paD;σ] and
returning anyd∗ satisfying this.
Next, consider the case where we know the approximate model M′ = ( P′,G′), for which
|P′(vi| pai)−P (vi| pai)|≤ ϵ≪ 1 which implies P′(vi | pai) = P (vi | pai) +ciϵ where
|ci|≤ 1. First we show that for any soft intervention σ we can approximate the post-intervention
joint distribution P′(Z = z| do(D = d), PaD = paD;σ) = P (Z = z| do(D = d), PaD =
paD;σ) +kϵ +O(ϵ2) whereZ =C\ PaD andk is a function of the model parameters and constant
inϵ. Letσ =P
jqjσj whereσj are soft interventions.
P′(Z =z| do(D =d), PaD = paD;σ) =
X
j
qj
P′(C =c| do(D =d);σ)
P′(Z =z′, PaD = paD;σj) (68)
=
X
j
qj
Q
i
P′(Ci =ci| do(D =d);σj)
P
z′
Q
i
P′(Ci =c′
i| do(D =d);σj) (69)
=
X
j
qj
Q
i
[P (Ci =ci| do(D =d);σj) +ciϵ]
P
z′
Q
i
[P (Ci =c′
i| do(D =d);σj) +ciϵ] (70)
=
X
j
qj
Q
i
P (Ci =ci| do(D =d);σj)(1 +c′
ijϵ)
P
z′
Q
i
P (Ci =c′
ij| do(D =d);σj)(1 +c′
iϵ) (71)
=P (Z =z| do(D =d), PaD = paD;σ) +ϵf(θ) +O(ϵ2) (72)
wherec′
ij := ci/P (Ci = ci| do(D = d);σj) andf(θ) is a polynomial in the model parameters
θi =P (vi| pai). Therefore the expected utility under interventionσ evaluated usingM′ satisfies,
EP′[U| do(D =d), PaD = paD] =
X
z
P′(Z =z| do(D =d), PaD = paD;σ) (73)
=
′X
z
(Z =z| do(D =d), PaD = paD;σ) +ϵg(θ) +O(ϵ2)
(74)
= E[U| do(D =d), PaD = paD] +ϵg(θ) +O(ϵ2) (75)
whereg(θ) is a polynomial in the model parameters. The decisiond∗ = arg maxd EP′[U| do(D =
d), PaD = paD] incurs at mostϵg(θ) regret, and therefore the regret is linear inϵ.
F E XPERIMENTS
As discussed in Section 4 the proofs of Theorems 1 and 2 can be viewed as causal discovery algorithms
where we assume i) knowledge of the set of environment variablesC, ii) knowledge of the utility
28

Published as a conference paper at ICLR 2024
functionU, iii) the decision task is unmediated and iv) domain dependence. Given these assumptions
we can learn an approximation of the underlying CBN given only the policy of the agentπ(σ) under
interventionsσ, with the approximation being exact whenπ(σ) are optimal.
To demonstrate this theoretical result we take the proof for simple Binary decision tasks outlined in
Appendix B and recast it as a causal discovery algorithm (Algorithm 2 below). We test it on CIDs
of the form shown in Figure 6 where we randomly choose the joint distribution overX,Y and their
causal structureG. Note that Algorithm 2 is significantly simpler than the general method outlined
in the proof of Theorem 1, as it exploits the fact thatD,X,Y are binary variables and that|C| = 2.
This causal discovery algorithm requires that we can intervene on the latent variablesX,Y , but only
requires that we can observe the response of a single variable (the decision) to these interventions. To
motivate this setting, we can imagine situations where the latentsX,Y cannot be directly observed
but can be intervened on.
Example. Many diseases cannot be directly observed in patient physiology, but can only be indirectly
observed through the presence of symptoms. Let X,Y ∈{ 0, 1} be two such diseases, for which
there are treatments, i.e. we can intervene to ‘turn off’X andY but cannot observe them.D∈{ 0, 1}
represents a decision to provide a specific pain relief medication, which results in a change in the
symptom severity (utility). The response to pain relief depends on the presence or absence of the
diseases (e.g pain relief is highly effective for patients withX =T , moderately effective forY =T
and less effective forX = F,Y = F ). The doctor’s goal is to minimise symptom severity while
avoiding unnecessary use of pain medication, e.g.U(d,x,y ) =d[s(x,y )−c] wherec is some cost
associated with pain relief and s(x,y ) is the response to pain relief. Following an intervention σ
(e.g. curing a disease σ = do(X = F )), the doctor adapts their treatment policy in the shifted
population. For example, this adaptation could occur by trial and error, with the doctor choosing
random treatment decisionsD and observing the change in symptom severity—a context-free bandit
problem. Although we cannot directly observe the disease statesX,Y , by intervening on the latent
disease state and observing how the doctor’s policy adapts, we can learn both the joint distribution
P (X,Y ) and the causal graph overX,Y .
Figure 9 shows the average error in the learned parametersP (x,y ) andG whenπ(σ) satisfy different
regret bounds. The results are averaged over 1000 randomly generated CBNs where i) the parameters
of the joint distributionP (x,y ) are chosen at random, ii) the DAGG overX,Y is chosen at random
fromX→ Y andX← Y , iii) the utility function U(d,x,y )∈ [0, 1] is chosen at random (see
Appendix A.2 for description of parameters). To simulate the regret-bounded agent we calculate the
optimal policy for each environment and if the sub-optimal decision satisfies the regret bound we
choose randomly from the two decisions when sampling from the policy oracle in Algorithm 1. We
also compare to a random baseline algorithm which estimatesP (x,y ) = 1/4 and randomly selects
fromX→ Y orX← Y with equal probability. In a small number of cases Algorithm 1 fails to
predictP (x,y )∈ [0, 1] due to finite sample errors, and for these cases we replace the output of the
causal discovery algorithm with a random guess.
From Figure 9 it appears that the error rate grows sub-linearly with regret. Note that the relevant
scale for the regret is the difference in expected utility between the two decisions, hence we plot the
normalised regret bound where we divideδ by this expected utility difference. Note that even for
relatively large regret bounds, representing agents that generalise weakly, we can still identify the
causal structure with a high accuracy. For example when the regret bound is 30% of the expected
utility difference, we can still identify the correct causal structure in∼ 90% of the randomly generated
CIDs. This describes an agent that is guaranteed to incur a regret of at most 30% of the expected
utility difference between the decisions before the domain shift. If the domain shift results in the
expected utility difference being less that 30% of the unshifted expected utility difference, the agent
can return a sub-optimal decision.
G A PPENDIX : TRANSPORTABILITY & PEARL’S CAUSAL HIERARCHY
Transportability. The problem of evaluating policies under distributional shifts has been studied
extensively in transportability theory (Pearl & Bareinboim, 2011; Bareinboim & Pearl, 2016; Bellot
& Bareinboim, 2022). For decision tasks as outlined in Section 2.2, transportability aims to provide
necessary and sufficient conditions for identifying the expected utility following a distributional shift,
R = E[u|d, paD;σ], given (partial) knowledge of i) the jointP , causal graphG and interventional
29

Published as a conference paper at ICLR 2024
(a) Misclassification rate for G scaling with regret
bound
(b) Mean parameter error for P(x, y) scaling with
regret bound
(c) Worst-case error for P(x, y) scaling with regret
bound
Figure 9: Comparing the model-average error rates for a) the learned DAG and b) the mean error
for parameters P (x,y ) and c) the worst-case error for parameters P (x,y ), v.s. the (normalised)
regret boundδ/|E[u|D = 1]− E[u|D = 0]|. Average error taken over 1000 randomly generated
environments with binary decisionD and two binary latent variablesX,Y . Comparison to error rate
for random guess (green). Results appear to show sub-linear growth in error rate with regret bound.
Note that even weakly generalising agents can be used to identify causal structure significantly better
than the random baseline.
30

Published as a conference paper at ICLR 2024
Algorithm 2 Graph Learner for simple CID
1: function GRAPH LEARNER (Πδ
Σ,U,δ,N)
2: d1,d 2,x′,y′,q crit← Algorithm 1(U, Πδ
Σ,N,σ 1 = do(Y = 0)) ▷ Identifyqcrit for
do(Y = 0)
3: Exp. U difference = (U(d2,x′,y′)−U(d1,x′,y′))∗ (1− 1/qcrit)
4: ∆0 =U(0, 0,d 2)−U(0, 0,d 1)
5: ∆1 =U(1, 0,d 2)−U(1, 0,d 1)
6: P (XY =0 = 0) = (Exp. U difference− ∆1)/(∆0− ∆1)
7:
8: d1,d 2,x′,y′,q crit← Algorithm 1(U, Πδ
Σ,N,σ 1 = do(Y = 1)) ▷ Identifyqcrit for
do(Y = 1)
9: Exp. U difference = (U(d2,x′,y′)−U(d1,x′,y′))∗ (1− 1/qcrit)
10: ∆0 =U(0, 1,d 2)−U(0, 1,d 1)
11: ∆1 =U(1, 1,d 2)−U(1, 1,d 1)
12: P (XY =1 = 0) = (Exp. U difference− ∆1)/(∆0− ∆1)
13:
14: d1,d 2,x′,y′,q crit← Algorithm 1(U, Πδ
Σ,N,σ 1 = do(X = 0)) ▷ Identifyqcrit for
do(X = 0)
15: Exp. U difference = (U(d2,x′,y′)−U(d1,x′,y′))∗ (1− 1/qcrit)
16: ∆0 =U(0, 0,d 2)−U(0, 0,d 1)
17: ∆1 =U(0, 1,d 2)−U(0, 1,d 1)
18: P (YX=0 = 0) = (Exp. U difference− ∆1)/(∆0− ∆1)
19:
20: d1,d 2,x′,y′,q crit← Algorithm 1(U, Πδ
Σ,N,σ 1 = do(X = 1)) ▷ Identifyqcrit for
do(X = 1)
21: Exp. U difference = (U(d2,x′,y′)−U(d1,x′,y′))∗ (1− 1/qcrit)
22: ∆0 =U(1, 0,d 2)−U(1, 0,d 1)
23: ∆1 =U(1, 1,d 2)−U(1, 1,d 1)
24: P (YX=1 = 0) = (Exp. U difference− ∆1)/(∆0− ∆1)
25:
26: ifP (YX=0 = 0) =P (YX=1 = 0) then ▷ IdentifyG andP from interventionals
27: ifP (XY =0 = 0) =P (XY =1 = 0) then
28: G← ()
29: P (x,y ) =P (XY =0 =x)P (YX=0 =y)
30: else
31: G← (Y →X)
32: P (x,y ) =P (YX=0 =y)P (XY =y =x)
33: end if
34: else
35: G← (X→Y )
36: P (x,y ) =P (XY =0 =x)P (YX=x =y)
37: end if
38: returnG,P (x,y )
39: end function
31

Published as a conference paper at ICLR 2024
distributionsI in the source domain, and ii) (partial) knowledge of the joint P∗ and causal graph
G∗ in the target domain (Pearl & Bareinboim, 2011; Bareinboim & Pearl, 2012b). Hence, these
results differ from Theorems 1 and 2 in that they restrict to the case where all assumptions on the data
generating process (i.e. inductive biases) can be expressed as (partial) knowledge of the underlying
CBN. For example, Bareinboim & Pearl (2016) claim the problem is essentially solved in the case
where ‘assumptions are expressible in DAG form’. This does not constrain possible approaches to
domain generalisation that make use of non-causal assumptions and heuristics 5, and indeed deep
learning algorithms exploit a much wider set of inductive biases than causal assumptions alone
(Neyshabur et al., 2014; Battaglia et al., 2018; Rahaman et al., 2019; Goyal & Bengio, 2022; Cohen &
Welling, 2016). In many real-world tasks these may be sufficient to identify ‘good enough’ (i.e. regret-
bounded) policies without requiring knowledge of the causal structure of the data generating process.
Our aim has been to establish if learning causal models is necessary for domain generalisation in
general. Hence assuming that agents are restricted to using inductive biases that amount to (partial)
knowledge of the underlying CBN would be begging the question.
Causal hierarchy’s theorem (CHT). The celebrated causal hierarchy theorem (Bareinboim et al.,
2022; Ibeling & Icard, 2021) shows that for almost all environments there are causal relations
between environment variables that cannot be identified from observational data without additional
assumptions. Does this imply that a causal model is necessary for identifying optimal policies?
First, note that the CHT is an insufficiency result, and only implies trivial necessity results. For
example, is a causal model necessary for identifying all causal and associative relations between
environment variables? Yes, but only because this set of observational and interventional distributions
is a causal model. Formally, we can identify the underlying causal model (up to latent confounders) by
assuming causal faithfulness, which holds for almost all causal models (Meek, 2013). The difference
here is that the CHT is concerned with the identifiability of all causal and associative relations
between environment variables. This sets a much higher bar than domain generalisation, which
focuses on identifying a strict subset of these (regret-bounded policies) (Figure 4).
Secondly, the CHT is concerned with the collapse (or lack thereof) of the causal hierarchy. For
example, that observational data is insufficient for identifying all causal queries. We do not restrict
agents to having observational training data—in fact, typically we assume that agents have access to
both observational and interventional data in the online learning setting that we consider (e.g. agents
can intervene to fix the decision nodeD by assumption).
Finally, we can imagine a refinement of the CHT which states that observational data is insufficient
for identifying regret-bounded policies without additional assumptions, bringing it in line with
Theorems 1 and 2. If this was implied by the CHT, it would not imply our results unless we restrict
to the case where all assumptions as constraints on the causal structure (similar to transportability).
Likewise, it is simple to show that Theorem 1 does not imply the CHT. In deriving Theorem 1 we do
not restrict to observational distributions (or make any restrictions on the data available to the agent
when generating its policy).
5Indeed, notable examples of causal assumptions that go beyond those expressible in DAG form include
restricting the classes of structural equations Mooij et al. (2016) and assuming cause-effect asymmetry (Mitrovic
et al., 2018)
32