Robust agents learn causal world models
Authors: Jonathan Richens
Tom Everitt
Venue: ICLR 2024 oral (2024)
Keywords: causality
generalisation
causal discovery
domain adaptation
out-of-distribution generalization
Primary area: causal reasoning
TL;DR: We prove that agents that are capable of adapting to distributional shifts must have learned a causal model of their environment, establishing a formal equivalence between causality and transfer learning

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.

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 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, if other inductive biases are sufficient. We answer this question, showing that any agent capable of satisfying a regret bound for 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.
INTRODUCTION
What capabilities are necessary for general intelligence (Legg & Hutter 2007?? One candidate is causal reasoning, which plays foundational role in human cogmition (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 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 be careful not 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 201 6). 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 sufficiently large set of distributional shifts must have learned causal model of the data generating process.
Here, adapting to a distributional shift means learning policy that satisfies regret bound following an intervention on the data generating process for example, changing the distribution of features or latent variables. It is known that 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) giien 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 causal model of the data generating process is necessary for robust adaptation.
This has consequences for 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 non-trivial causal discovery problem. This provides further theoretical justification for causal representation learning (Schölkopf et al. (02T), 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

---

Published as a conference paper at ICLR 2024
task on synthetic data by observing the policy of regret-boundess agent under distributional shifts. More speculatively, our results suggest that causal models could play a role in emergent capabilities. Agents trained to minimise loss function across many domains are incentivized to learn 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 we introduce concepts from causality and decision theory used to derive our results. We present our main theoretical results in Section and discuss their interpretation in terms of adaptive agents, transfer learning and causal inference. In Section we discuss limitations, as well as implications for a number of fields and open questions. section 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 we describe
experiments applying our theoretical results to causal discovery problems.
2 PRELIMINARIES
2.1 CAUSAL MODELS
We use capital letters for random variables V, and lower case for their values dVm(V). For simplicity, we assume each variable has finite number of possible values, (do)(V)] < oc. Bold face denotes sets of variables V = (Vi...., V, I. and their values E dom( V) X; A probabilistic model specifies the joint distribution P(V) over a set of variables V. These models can support associative queries, for example P(Y y X x)) for X, Y C V. Interventions describe external changes to the data generating process (and hence changing the joint distribution), for example hard intervention do(X x) describes forcing the of variables X C to take value æ. This generates new distribution P(V | do(XX = x)) P(Vz) where V~ refers to the variables V following this intervention. The power of causal models is that they specify not only P(V) but also the distribution of V 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 specific class of causal networks (CBNs). There are several alternative models and formalisms that are studied in the literature, including structural equation models (Pearl 2009) and the Neyman Rebman-Rubin causal models Rubii 2005), and results can straightforwardly adapted to these.
causall Bayesian
Definition 1 (Baycsian networks). A Bayesian network M = (G, P) over a set of variables = (Vi...., V.) is joint probability distribution P(V) that factors according directed acyelic graph (DAG) G, iee. P(V....... Vv) I[_ P(V. Pay;), where Pay; are the parents of V; in G.
Bayesian network is causal if the graph G captures the causal relationships between the variables or, formally, if the result of any intervention do æ)) for X C can be computed from the truncated factorisation formula:
[ Menge P(u, pa.,) if consistent with
P(v | do(x)))
otherwise.
More generally, soft intervention a.. P'(V; Paç) replaces the conditional probability distribu- tion for Vi with a new distribution (V, Paç). possibly resulting in a new parent set Pa + Pa, as long as no cycles Bareinboim (020) (it has also been called an environment index, [Arjovsky et al. 2019)). The updated distribution is denoted P(0; ).)) = II...e P'(v, pa".) Iese P(vv pa..)
introduced in the graph. We refer o., as a domain indicator (Correa &
In general, soft interventions cannot be defined without knowledge of G. For example, the soft intervention σy = P' x) is incompatible with the causal structure + X as it would induce a causal cycle. As results 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 of G.
2

---

Published as a conference paper at ICLR 2024
Definition 2 (Local interventions). Local intervention on V₁ E V involves applying map to the states of V₂ that is not conditional on any other endogenous variables, v, + f(x)). . We use the notation a do(V; f()))) (variable V, is assigned the state f(,)). Formally, this is a seft intervention on Vi that transforms the conditional probability distribution as,
P(u: pa
P(c/ppay
Example: Hard interventions do(V; = vf) are local interventions where f(us) is constant function.
Example: Translations are local interventions as do(V, = Us + k) do f(::)) where f(e)) = U; + k. Examples include changing the position of objects in RL environments (Shah et al. 2022 and images (Engstrom et al. 2019).
Example: Logical NOT operation X + -X for Boolean X is a local intervention.
We also consider stochastic interventions, noting that mixtures of local interventions can also be defined without knowledge of G. For example, adding noise to variable X = X 6, ~ N( 1), is a soft intervention on X described by a mixture over local interventions (translations).
Definition 3 (Mixtures of interventions). A mixed intervention o² = =,p Σp: performs intervention o, with probability Formally, P(v| o²) = (oolo(o
2.2 DECISION TASKS
Decision tasks involve a decision maker (agent) choosing a policy so as to optimise an objective function (utility). To give causal description of decision tasks we use the causal influence diagram (CID) formalism (Howard & Matheson 2005;; Everitt et al.] [202]). which extend a CBN of the environment (chance) variables by introducing decision and utility nodes (see Figure T for examples). For simplicity we focus on tasks involving a single decision and a single utility function.
Definition (Causal influence diagram). A (single-decision, fingl--utiityy causal influence diagram (CID) is CBN M- = (G, P) where the variables V are partitioned into decision, utility, and chance variables, V = (LD), (U), C). The utility variable is a real-valued function of its parents, gp
Single-decision single-utility CIDs can represent most decision tasks such as classification and regression as they specify what decision should be made (d E D), based on what information (pap). with objective (E[()]). They can also describe some multi-decision tasks such as Markov decision processe The utility is any real-valued function including standard loss and reward functions.
We assume that the environment is described by set of random variables C that interact via causal mechanisms") and where C' satisfies causal sufficiency (Pearl 2009) (includes all common causes), noting that such a choice of C' always exists. We refer the CBN over C' 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 in C' are observed or unobserved by the agent, beyond that the agent can observe Pap C C. We also assume knowledge of the utility function ((Pa.).
The conditional probability distribution for the decision node (d pap) (the policy) is not fixed parameter of the model but is set by the agent as to maximise its expected utility, which for policy
is ET [U] E do(D- = π (pa,))) })]] A policy T' is optimal if it maximises E" [0]. Typically, agents do not behave optimally and incur some regret which is the decrease in expected utility
compared to an optimal policy = "x [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 Tp.
Assumption (Unmediated decision task). Descp Annce = 0.
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 a function of the
I Note Markov decision processes can he formulated as a single-decision single-utility CID, by modelling the choice of policy as single decision and the cumulative discounted reward as single utility variable. This assumption follows from Reichenbach 1956), and we discuss further in Appendix A.3
3

---

Published as a conference paper at ICLR 2024
D
D
(a) training
(b) testing
(c) known domain shift
Figure I: CID for a supervised learning task during (a) training and (b) testing following distribu-
tional (covariate) shift (unsupervised domain adaptation, Wilson & Cook 2020p. The agent chooses
a label prediction D Y given features X, with the goal of minimising loss U -Loss Y). Decision variables are depicted 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 features Y - X (for examples where features cause labels see Castro et al. 2020; Schölkopf et al. 2012). The black square ('regime node' (Correa & Bareinboim 2020g) in (b) and (c) denotes 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 [ return an optimal decision boundary for known covariate and label shifts, then must have learned the CBN over C = {X, Y). Note that even if the agent has sufficient training data to learn P(X,V Y), the causal structure Y X is in general non-identifiable given P(X, Y) and so domain adaptation requires that the agent solves a non-trivial causal discovery problem.
if the agent
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 DISTRIBUTIONAL 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 al. [021 Wilson & Cook 2020), or changes the objective (task shifts) as in zero shot learning (Xian et al., 2018). in-context learning (Brown et al.) (020) 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.) (02T). 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 the initial conditions or transition function in Markov decision processes (Peng et al. 2018). Examples of shifts that not naturally represented interventions include changing the set of environment variables C, 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 the chance variables C. We do not consider shifts that change the agent's 's decision D, although we include shifts that drop inputs to the policy Pap + Pa'p Pap (e.g. masking) as local interventions. We do not consider task shifts i.c. changing the utility function.
As we are interested in determining the capabilities necessary for domain adaptation, restrict our attention to decision tasks where domain adaptation is non-trivial, i.e. where the optimal policy depends on the environment distribution P(C c).
Assumption 2 (Domain dependence). There exists P(C c) and (C c) compatible with M such that π arg max, [T implies मt + arg max, [.T
Assumption 2 implies the existence of domain shifts that change the optimal policy.
4

---

Published as a conference paper at ICLR 2024
3 CAUSAL 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 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 the idealised case where 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 = P) satisfying Assumptions I and 2, we can identify the directed acyelic graph G and joint distribution P over all ancestors of the utility Ancy given { ( pa pap)lees where (d p) is an optimal policy in the domain a and E is the set of all mixtures of local interventions. Proof in Appendix
C
The parameters P(v: pa.), (pay) 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 [T] does not hold is Lebesgue measure zero (see Appendix AA.] for discussion). This condition is
necessary because there exist finely-tuned environments for which the CBN cannot be identified given the agent's 's policy due to variables X E Ancy that do not affect the expected utility. For example consider X Y - U, Y NN, 2) and U = D Y, then changing X can only change the variance of U while leaving its expected value (and hence the optimal policy) constant. However, this only occurs for very specific choices of the parameters P and U.
In Appendix B we give a simplified overview of the proof with a worked example. We assume access to an oracle for optimal policies Th for any given local intervention on C. Note, this assumes the agent is robust to distributional shifts on a causally sufficient set of variables C, 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 graph G(Aney) and the joint distribution P P(Ancy).
3.1 RELAXING THE ASSUMPTION OF OPTIMALITY
We now relax the assumption of optimality, considering the case where the policies Ta satisfy a regret bound E [U] 2 E [U] 8. We show that for 8 > 0 we can recover an approximation of the environment CBN, with error that grows linearly in 8 for 8 < E= [U].
we can iden- rify an approximate causal model M' =P',,') given { pa where E [U] Z EG and Σ, is the set of mixtures of local interventions. The parameters of M' satisfy [P, pa,) P(u. pa,)l & (()) V V, E V where 7(0) = 0 and 7(8) grows linearly in 8 for small regret 6 < E= [U]. Proof in Appendix
Theorem 2. For almost all CIDs M PG. satisfying Assumptions 7 and 2
The worst-case error bounds 7() for the parameter errors are detailed Appendix D For 8 > 0 may not be possible to identify G' perfectly as some weak causal relations cannot be resolved due to these error bounds. We describe in Appendix hoo we can learn a sub-gran -abbph G' S G that may exclude directed edges corresponding to weak causal relations.
Theorem 2 shows that we can learn (sparse) approximate causal models of the data generating process from regret bounded policies under domain shifts, where the approximation becoming exact as + O. In Appendix we demonstrate learning the underlying CBN from regret-bounded policies using simulated data for randomly generated CIDs similar to Figure I and explore how the accuracy of the approximate CBN scales with the regret bound (Figure B
Finally, we prove sufficiency, i.e. that having an (approximate) causal model of the data generating process is sufficient to identify eegret-bounded policies. The result is well-known for the non- approximate case (Bareinboim & Pearl 2016).
Theorem 3. Given the CBN M = (P, G) that is causally sufficient we can identify optimal policies T p)p for any given U where Pay C C and for all soft interventions a. Given an approximate causal model M' = (P', G') for which [P'(v; pa.) - P(u; pa;)) S e < 1, we can identify regret-bounded policies where the regret ê grows linearly in Proof in Appendix P
5

---

Published as a conference paper at ICLR 2024
C' ornor v.. regget
P'
0.5
Model www...ernnggddddooo czEa
Seadd-veragd arres
0339
8300
6875
8.93
0.1
0.2
180
2.85
0:3
0.2
0.25
03
4/ [[]]] =
E/je
[P
(a) Error for learned DAG regret bound
(b) Mean emor for P(z, y) regret bound
Figure 3: Comparing the model-average error rates for a) the learned DAG G' and b) learned joint distribution P' (zz y). v.s. the (normalised) regret bound 6/ [E|u D error taken over 1000 randomly generated environments with binary decision 1) and two binary latent variables X, Y. Comparison to error rate for random guess (green) See Appendix Foro details.
E[u D 0.]. Average
Together, Ahcoremssanne iimply that learning an approximate causal model of the data generating process is necessary and sufficient for learning regret- beunde-bounded policies under local interventions.
3.2 INTERPRETATION
We interpret Theorems to through three lenses; agents, transfer learning and causal inference.
Agents 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. (023).
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 indicator R. = (d pap. or. By Theorem 2 n. satisfies tight regret bound for can reconstruct the underlying CBN from the agent's ' policy alone (following the
all local shifts procedure 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 7[d pap. o), which is functionally equivalent to learning the underlying CBN, as any associative or causal query that can be identified using the CBN also be identified using n (d p) If is unknown and has to be inferred by the agent, the underlying CBN can similarly reconstructed from the agent's policy long it satisfies tight regret bound")
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 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 jinooremmmmiiiesss jiplies the doctor must have learned the causal relations between the relevant latent variables-hov the treatment affects diseases, how these diseases and their symptoms are causally related, and on. Likewise, any medical AI that hopes 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.
eeguivalently environment index for (in context) invariant risk minimization (Gupa et al. 2019), or the context variable for zero-shot reinforcement learning (Kirk al. (2023)
2023
Arjovsky
Trivially, any agent capable of returning regret-boundee policy without input can do so given a simply
by discarding If the agent adapts hy conditioning their policy an inferred a' (see Kirk et al. 2023 for
review of implementations), and this policy satisfies regret bound, can be used in Theorems

---

Published as a conference paper at ICLR 2024
Transfer learning. In transfer learning (Zhuang et al. 2020 models are trained set of source domains and evaluated on held-out target domains where 1) 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 pap ~ P(Pap: rT) whereas in domain generalisation typically no data from the target domain is available during training (Farabani et al. 2021
Let Ds denote the training data from the source domains and D, denote the training data available from a given target domain σ. Let there exist transfer learning algorithm that returns a policy Ta satisfying regret bound for a given target domain o, provided this training data. As Te is function of the training data, then by Theorems and 2 the existence of this algorithm implies that we can identify the underlying CBN from Ds DD axE. 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 [ Let Ds {(x', ./) P(X, Y)}==1 so for sufficiently large the agent can learn the P(X,Y) from Ds. other words,
However, Y + X must also be identifiable from the training data Ds {D, J the transfer learning problem contains hidden causal discovery problem. If 0 then Y - X must be identifiable from P(z, 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 data D be identified P(X; o * P(X).
(X)o)) Y - X can in principle
Causal inference. Theorem can also be interpreted purely in terms causal inference. We can compare the causal hierarchy theorem (CHT) (Bareinboim al. 2022). which states that oracle for Ll queries (observational) is almost always insufficient to evaluate all L2 queries (interventional), Our Theorem can be stated in an analogous way; an oracle for optimal policies under mixtures of local interventions I1g a + T (or) 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 II a strict subset of L2, and we describe a subset of 1.2 as being 1.2-coplette if evaluating these queries is sufficient to evaluate all L.2 queries. Hence Theorem [ can be summarised as IT, L-2complete. would be interesting in future work to determine what other strict subsets of L2 are L2-complete, identifying these queries is sufficient to identify all interventional queries.
Why is this surprising? Firstly, we may expect the optimal policies to encode relatively small number of causal relations, as they can be computed from E(u d, pap: which describes the However, Theorem shows that the optimal
response of single variable U to intervention policies encode all causal and associative relations in Ancy, including causal relations between latent variables, for example P(Y:) for any X, Y C Ancy. Secondly, Theorems 2 and combined imply that learning to generalise under domain shifts is equivalent to learning a causal model of the data generating process-problemm that on the surface are conceptually distinct.
m
m
L2
i L2
m1b
Figure The L2 (Bareinboim et al. 2022)) contains all casual queries including the set of optimal policies under domain Hh and task shifts πū.. We show that Tt also contains L2, i.e. learning optimal policies under all shifts for a single utility U is sufficient to identify L2
7

---

Published as a conference paper at ICLR 2024
4 DISCUSSION
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. (02T). with the aim of exploiting causal invariances to achieve better generalisation across domains. Theorems | and 2 show that any method that enables generalisation across many domains necessarily involves learning mate) causal model of the data generating process-ia i.e. a causal representation. Hence, our results provide theoretical justification for CRL by showing it is necessary for strong robustness guarantees.
(approxi-
Causal bounds on transfer learning. As described in Section 3.2 Theorems ! and imply fundamental causal constraints on certain transfer learning tasks. For example in the supervised learning task depicted in Figure [ identifying -guree-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 (Vowels 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) (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 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 optimal regulator that is a deterministic function of the state of the system (which could be trivial, [Wntworth (202T). 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 causal model of its environment to optimise for any given objective function (Pa S V) without additional data (Theorem 3) This could explain how general competence can arise from narrow training objectives (Brown et al. 22000] Silver et al. 2021). By Theorems [ and 2 agents trained to maximise reward across many environments are incentivized to learn 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. F.g. it will still be impossible for an agent to learn a causal model (and therefore to generalise) 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-o--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 (Kicıman et al.] 2023), how they achieve this (and if it constitutes bona fide causal reasoning) is debated (Zečević et al. 2023).
Causal discovery. Theorems | 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 Ancy. Typically, causal discovery algorithms involve measuring the response of many variables to interventions (Vowels et al. (022). Also, many causal discovery algorithms assume independent causal mechanisms (Schölkopf et al. 202T), which is equivalent 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 Bw 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-Weet Weiner 2018 Ward et al. 2024), harm (Richens et al.] (022). deception (Ward et al. (003bb), manipulation (Ward et al. (2023a) and incentives (Everitt et al. 202 | I), and are required for approaches to explainability (Wachter et al. 2017) and fairness (Kusner et al. 2017). Methods for designing safe and ethical Al systems that build on these definitions require causal models of the data generating process, which are typically hard to learn, leading some doubt their practicality (Fawkes et al. 2022 Rahmattalabi & Xiang 2022). However, our results show that learning causal model of the data generating process 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 I and 2 require agents to be robust large set of domain shifts (local interventions on all environment variables). Theorem Sonooemmshoww 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 | and can be extended to active decision tasks, as Assumption does not play a major role beyond simplifying the proofs.
5 RELATED 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) ctt al. 2022 Abdou al., 2021 Li al. 2022, Gurnee Tegmark/ (023). 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., (022)) found that a GPT model trained to predict legal next moves in the board game Othello learned 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 cittof-diitributionn generalisation under nnterventions-mus like causal model.
The problem of evaluating policies under distributional shifts has been studied extensively in causal transportability (CT) theory (Bareinboim & Pearl 2016 [ellot & Bareinboim] (0022). 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 (016). However, deep learning algorithms can exploit a much larger set of inductive biases (Neyshabur et al., 2014) Battaglaa 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 is the causal hierarchy theorem (CHT) (Bareinboim et al., 2022 Theling & leard 202T), which shows that observational data 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.
CONCLUSION
Causal reasoning is foundational to human intelligence, and has been conjectured to be necessary for achieving human level AI (Pearl) 2019p. 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 model-independeer 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 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 formal connection between causality and generalisation, our results show that causal world models a necessary ingredient for robust and general AI.
way, showing that any agent capable of

---

Published as a conference paper at ICLR 2024
Acknowledgements. We would like to thank Alexis Bellot, Damiano Foraasiere, 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.06122 2021.
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: let::::000000000 0000999,. 2019.
Elias Bareinboim and Judea Pearl. Controlling selection bias in causal inference. In Artificial Intelligence and Statistics, pp. 100-108. PMLR, 2012a.
Elias Barcinboim 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, L13(27):7355-7352 2016.
Elias Bareinboim, Juan D Correa, Duligur lbeling, and Thomas leard. 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.0/261, 2018.
Alexis Bellot and Elias Bareinboim. Partial transportabilityy for domain generalization. 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Mclanie 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, 1(1):33673, 2020.
Taco Cohen and Max Welling, Group equivariant convolutional networks. In International 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 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. 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 Voghoei, 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 fairesss. 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, 47802266):202106888 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 Artificial Intelligence, volume 32, 2018.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. arXiv preprint UrXiv:1903.12200 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 lheling and Thomas Icard. A topological perspective on causal inference. Advances in Neural Information Processing Systems, 34:5608-500 -6108-561..111 2021.
Zachary Kenton, Ramana Kumar, Sebastian Farquhar, Jonathan Richens, Matt MacDermott, and Tom Everitt. Discovering agents. Artificial Intelligence, pp. 103963, 2023.
Emre KIcıaan, Robert Ness, Amit Sharma, and Chenhao Tan. Causal reasoning and large language models: Opening 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 443,, 2007.
Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Watten- berg. Emergent world representations: Exploring sequence model trained on synthetic task. arXiv preprint 10. /3382, 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):e22066251 19, 2022.
Christopher Meek. Strong completeness and faithfulness in bayesian networks. arXiv preprint 102.4433 2013.
Nicolai Meinshausen. Causality from a distributional robustness point of view. In 2018 IEEE Data Science Workshop (DSW), pp. 6-10. IEEE, 2018.

---

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 Berhaard Schölkopf. Distin- guishing cause from effect using observational data: methods and benchmarks. The Journal of Machine Learning Research, 17(1): 103-1204, 2016.
Neel Nanda. othello-gt has a linear emergent world model, Mar 2023. <https otheeooy
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint wrXiv:142..6614 2014.
Masashi Okamoto. Distinctness of the eigenvalues of 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 vrXvv:1801.04066 2018.
Judea Pearl. The seven tools of causal inference, with reflections machine learning. Communica- tions of the ACM, (20)),4-600, 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, Wojeiech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. 20/8 IEEE international conference on roboties and automation (ICRA), pp. 3803-38 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 preprini arXiv:2205.000 000000177 75, 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-3665 -33655,,3,,,,,- 2022.
Donald B Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American Statistical Association. (000446))322-3311 2005.
Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning, arXiv preprint arXiv: (oXXiv:2006.4711 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-334 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:22100017900 2022. 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. 41 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: family of highly capable multimodal models. arXiv preprint arXiv:2312.1 18805, 2023.
Matthew Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? survey on structure learning and causal discovery. ACM Computing Surveys, --64))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 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 Al 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. 2904-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.072211,0000 2024.
John Wentworth. Fixing the good regulator theorem. http::://ww...lgnnennnnfffforor BthpDDDxIoooshhhhhh 3twts///h333//M/// cessed: 2023-10-17.
the rhte--poorreeglllttttteeeeeeee 2021.
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 comprehensive evaluation the good, the bad and the ugly. IEEE transactions on pattern analysis and machine intelligence, 41(9):2251 1265, 2018.
Matej Zečević, Moritz Willig, Devendra Singh Dhami, and Kristian Kersting, Causal parrots: Large language models may talk causality but are not causal. arXiv preprint arXiv:2308, S3V:22308.13067, 2023.
Fuzhen Zhuang. Zhiyuan Qi, Keyu Duan, Dongho 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 PRELIMINARIES
A.1 SETUP AND ASSUMPTIONS
The environment is described by set of random variables C (C1, C2,..., Cn}. which in combination with the decision D and utility nodes U define the state space for the CID V C CD(DU . In out notation individual variables C. E C are given indexes, whereas set of variables are indexless and bold, and we use V = v as short hand for the joint state of the variables in a set C. The joint probability distribution P(C c, d, U u) describes the statistical relations between environment variables. Bayesian networks factorise joint probability distributions according to graph (Pearl 2009).
= (G, P) over set of variables V {Vi....,, Vo} is a joint probability distribution P(V) that factors according to a directed acyelic graph (DAG) G. i.e P(V V.) [TT=IP(M Pav.), where Pay, are the parents of V; in G.
Definition 1 (Bayesian networks). A Bayesian network =
The distributions and statistical relationships between variables may change as a result of external interventions applied to a system. Hard interventions set subset C' C C of the variables to particular values c', denoted do Pao(e') 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 edge V; V3 whenever intervention on VÚ directly influences the value of another variable Y, and lacks unmodeled confounders; Spirtes al. 20000 Pearl, 2009). When this holds, we call the Bayesian network causal and G a causal graph. With respect to the causal graph G we denote the direct causes (parents) of Vi as Pa,. the set of all causes (ancestors) Ane, and the variables that Vú directly causes (children) Ch, and descendants Desc, as the set of all downstream variables. Note in particular that Anc; and Desc; refer to proper ancestors and descendants, i.e. V & Ane; and V- & Desc,- We denote a causal Bayesian network (CBN) as M (P, G¹) where P is the joint and G is the directed acyelic graph (DAG) describing the causal structure of the environment, Further, the interventional distribution Paoter) is given by the truncated factorisation
c') or do(c'). Naively, one joint probability distribution
Pao(er) (v) Him
P(u: pa..) if consistent with e' otherwise.
Equivalently, the effect of interventions can be computed by adding an extra node X and edge V. + Vi for each node V; E V (Correa & Bareinboim 2020 Dawid 2002). Intervening on V; then corresponds to conditioning on Vú in the extended graph. More general, soft interventions P'(V; Paç) replace the conditional probability distribution for V; with new one, possibly using a new parent set Pa as long as no cycles are introduced in the graph (Correa & Bareinboim 2020 The modified environment is denoted (()..
General soft interventions cannot be defined without prior knowledge of the causal graph G. For example, the soft intervention gy P' P'(y x) is incompatible with the causal structure Y -->>> X 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 of G.
Definition 2 (Local interventions). Local intervention on V E V involves applying a map to the states of V: that is not conditional on any other endogenous vuriables, v; + f(v.). We use the notation a do(V; = [(v))) (variable V; is assigned the state f(v)). Formally, this is a soft intervention V; that transforms the conditional probability distribution as,
P(v. ppa;o)=
Σ
P(v((pa;)
(1)
Example: Fixing the value of variable (hard intervention) is local intervention do(V; = v() do(V; = fv.)) where f(;;) = v/.
Example: Translations are local interventions do(V, U/ k) do(V, = -v,)) where f(o.) = 0. + 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 operation X + -X for Boolean X
We also consider mixtures of interventions, which can also be described without knowledge of G. Definition 3 (Mixtures of interventions). A mixed intervention a¹ = PiPi for Σp: performs intervention o, with probability pi. Formally, P(v o²) = Pr P(o oi).
Example: Adding Gaussian noise mixture over local operations (translations) d. do(X X ++ c) where e ~ (N(,,) 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 objectíve. 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] 20055 Everitt et al. 2021). CIDs are causal Bayesian networks where the variables are divided into decision D, utility U. and chance variables V. and no conditional probability distribution is specified for the decision variables. The task of the agent is to select the distribution स = P(D = d Pap pap), also known as the policy or decision rule. An optimal policy x² is defined policy x² that maximizes the expected value of the utility E [U].
Definition (Causal influence diagram). A (single-decision, single-utility) causal influence diagram (CID) is CBN M = (G. P) where the variables V are partitioned into decision, utility, and chance variables, V ((D), (U), C). The utility variable is a real-valued function of parents, U.
By convention, decision nodes drawn square, utility nodes diamond, and chance nodes round. The parents of D, Pap. can be interpreted as the information the decision is allowed to depend on, and depicted dashed lines. See Figure for example. In the following restrict our attention to 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 (Unmediated decision task). Descp Ancu Ø.
Examples of unmediated decision tasks include all standard classification and regression tasks, and generative AI tasks where the output is not included 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 action that influences the state of the environment. Furthermore, we will focus on non-trivial unmediated decision tasks i.e. where U E Chp, as the case Chp = 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 single policy that is optimal for all c). c).
choices of environment distribution P(C
Assumption 2 (Domain dependence). There exists P(C c) and PC c) compatible with M such that π = arg max, E2[U] implies xt + arg max, EP.
Lemma 1. Domain dependence implies that:
i) There exists no d E dom(D) such that d E max, (dd c) Vc E dom(C")
i) Pap CAnco
ii) D E Pay
Proof. i) For any P' we have Ep | do(D = d), papl = E. P'Ca = pap)U
E. (C (dd,) where we have used Desep Aney = 0. Therefore if 3 d'
15

---

Published as a conference paper at ICLR 2024
Co
D
Figure 5: The CID for unmediated decision task, where D has causal influence the environment state C. Our main theorem implics that an agent that is robust to distributional shifts on C' must learn the CBN over Ane; (Ci, C2. C3. Ca, Co), noting that Cs. Aney C4 is an example of a variable that is only an ancestor of via D and so has no direct causal effect on the utility, but is still relevant to the decision task it is proxy for C₁ which is cause of U. Co is a cause of U but not of D, and naively one might assume that distributional shifts on Co cannot influence the agent's decision. However, the optimal policy can change under distributional shifts on Cg as these effect the utility, and hence the agent will have to learn CBN including C. if it is to be robust shifts on Cg.
d' arg max, ((d C then Ep- | do(D papl 2 E. pap) pp [U do(D = d), papl v d & d', and so D = d" is optimal for all P' c) and we violate domain dependence.
ii) As D E Pag (iii), then Pay C Ancy. If Aney = Pap then Ep|u (u d, papl = (d, pap) which independent of P(C c), and hence there is a single optimal policy for all P and we violate domain dependence.
iii) If D & Aney then the CID is trivial, in the sense that EIU do(D d)] EVU) and hence all decisions are optimal for all distributions P(C), which violates domain dependence (Assumption Therefore D E Aney which with Descp Aney implies D e Pag.
A.2 PARAMETERISATION OF CIDS
The joint distribution P is defined for all environment variables C, and the CID is defined by the parameters for P(C) and U (Pay). We restrict our attention to C' that are categorical, and without loss of generality we label states c; = 0, I.... dim, where dim, is the dimension of variable C. Firstly, the joint P(C) is parameterised by the conditional probability distributions (CPDs) in the Markov factorization with respect to G, fp (P(c, pa,) Vc; E {o,.... dim; 2). pa, E Pa;, C₁ E C. Note that the CPDs p(C; = dim, - 1 pa.) are not included in 0p as they are fully constrained by normalization P(C: dim, 1 pa,)
dim, _ P(c: pa,). Secondly, the utility function is simply parameterised by its value given the state of its parents Gu (U(pay) V Paa pay) }. For simplicity we work with the normalized utility function,
U(pay) - milppa, U'Pay = pa(t)
U U(pag) maxpa', UPPa paly) minpai, U U(Pay paly)
(2)
with values between and 1. Noting that as this a positive affine transformation of the utility function the set of optimal policies invariant, and denote the set of all parameters for the CID, 0s = 0p L bv, and note that the elements of Uh in the [0, interval and are logically independent, i.e. each parameter and this defines a valid parameterization of the CID for the baseline environment. In the following when we refer to 'the parameters P, U
re-scale regret bounds accordingly. Let Ox
independently choose any [0. value for
referring to 0y-
We follow the method outlined in (Meek 2013) to prove that certain constraints on P, U hold 'for almost all P, U and hence for almost all decision tasks. This involves converting given constraint into polynomial equations over Os and applying the following Lemma,
Lemma Okamoto 1973). The solutions to a (nontrivial) polynomial are Lebesgue measure zero the space of the parameters of the polynomial.
16

---

Published as a conference paper at ICLR 2024
A polynomial in variables is non-trivial (not an identity) if not all instantiations of the variables are solutions of the polynomial. For example, the equation poly(0ıs) = is trivial if and only all coefficients of the polynomial expression poly(Ox) ) are zero. Therefore, any constraint on P. U that can be converted into a polynomial equation over 0M must either hold for all Oar or for Lehesgue measure zero subset of instantiations of 0xs-
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 O.
A.3 DISTRIBUTIONAL SHIFTS POLICY ORACLES
In the derivation of our results we restrict out attention 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) II, P(q Pa.) 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 distribution P(C = c) 8(C c'), and then take 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 variables V 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 (012a)). For further discussions on the relation between distributional shifts and interventions see Schölkopl et al. (202)): Meinshausen 20188)
In the following proofs we use policy oracles to formalise knowledge of regret- behaviour under distributional shifts.
Definition (Policy oracle). policy oracle for a set of interventions a map T o + n. (d pap) V ooo Σ where E is set of domains. It is 8-optimal if To (d pap) achieves an expected utility E U ET [U] - 8 in the CID ((r) where 8 2 0.
Here 8 is the regret upper bound, which is satisfied under all distributional shifts E. We refer to 5-optimal policy oracles for = 0 as optimal policy oracles. For the proof of our main result restrict our attention policy oracles with E that includes mixtures over all local interventions (def. (2).
Note that the policy oracle specifies only what policy the agent returns in distributionally shifted environment M (a). 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 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? our proofs, we assume the agent robust to any domain shifts that can be described as mixture of local interventions on the environment variables C. We do not consider interventions that change the utility or the agent's decision D, though we do include dropping inputs to the policy (masking) Pap - Pa'p Pap local interventions.
B APPENDIX: SIMPLIFIED PROOF
In this section we outline the proof of Theorem 1 for simple binary decision task with binary latent variables. As mentioned in Section 4 the method used to identify the CBN in Theorem [ can be viewed as algorithm for learning the CBN over latent variables by observing the policy of regret- regret-bounded 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 's regret bound affects the accuracy of the learned CBN.
Consider the CID in Figure describing binary decision task D E {0,1) with two binary latent variables X, Y E Pag.
Y
D
Figure 6: Example CID describing a context-free mutli- aumdi- bandit with binary latent variables X,Y.
Consider an agent that selects a policy TD such that it maximises the expected utility. That is, the CID describes context-free bandit problem, where X, Y are latent variables that influence the arm values [B[u df = En,y P(x, y)U (I, y. d).
Our aim is to learn this CID given only knowledge of the agent's 's policy under distributional shifts, and knowledge that it satisfies a regret bound. We assume knowledge of i) the of chance variables C= {X, J. ii) the utility function U(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 learn the parameters of the joint distribution over latents P(r, y) and the unknown causal structure. As we know the utility function we know D, X, Y E Pac. and by assuming the CID is unmediated (Assumption we know X, Y & Desc Likewise the decision task is context free hence D き Descx U Descy. Hence the only unknown causal structure the DAG over the latent variables = (X,Y).
The expected utility difference between D 0 and D = 1 following hard intervention on X is given by
Elu D = 0; do 0)] - E[u D D= 1: 0]] Σ P(Yx=0 v) (1,00,
(3)
P(Yx=o= 0) -0-00.000000000000000000 (1- P(Yx=0 - -((,0,))
01)
(4)
As we know Udd. x. y) we can therefore identify P(Yx=o = 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 02 do
x'' Y 5²) that
results in a different optimal policy to the optimal policy under = do X = 0). For mixture
of these two interventions 03 q0a + (1 0)0y the expected utility is E'u d. وو) = gE|u d, d ] + (1 B/u | d, o2). This is a linear function with respect to and for 1 the optimal decision (d,) is different than for q = (d2 A d)). Therefore, there is single indifference point Jen for which both decisions are optimal. It is simple to show that this indifference point is given by,
Acrit = -1--Bu)
E[u D D= do X 0) E/u D d2; do = 0)] Udd1, x v1) U x',,
(5)
D= di optimal for q S qent and D dg is optimal for q 2 qen- We can estimate Teπ by randomly sampling values of y uniformly over [0, 1] and observing the optimal decision under the resulting mixed intervention (Algorithm [T. That is, qerit is the probability that D d, is returned by the policy oracle for a randomly sampled q. In this way we learn qait and as we know U U(d x, y) we can identify the expected utility difference under do(X- = 0) in the numerator of Equation ( and so
identify P(Yx=0 0).
Similarly we identify P(Yx=1 = 0), P(Xy=o = 0) and P(Xy=1 = 0), which encode both the causal relation between X and Y (e.g. there is directed path from X to Y if and only if P(Yx=n) * P(Yx=1) for almost all CBNs), and determine the parameters of the CBN as P(C, = Co C.)) = P(C: & Pa; pa.)
18

---

Published as a conference paper at ICLR 2024
C PROOF OF THEOREM 1
In this appendix we prove Theorem 1 For an informal overview of the proof see Appendix
First, we show that for given distributional shift for almost all P. U there is single optimal decision. While this is not necessary for our proof, it simplifies our analysis. And as our main theorem holds for almost all P, U, can include any finite number of independent conditions that hold for almost all P. 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 single deterministic optimal policy for almost all P, U.
Proof. Following intervention a two decisions d, d' are simultaneously optimal in context pap if, B(u pa do D d); = Elu pap, p d));
(6)
Let Z = [Ancy Papl and X = Pau \ {D}. Noting that
E j pa do(D = d); a| = Σ (d, x) P(x, pap do(D = P(pa))
do(D = d); (7)
and that P(pap do(D = d): o) = p(papio) and P(z. Plz.pap do(D = d): P(z. pap 0)
which follows from Desco n Ancy = 0, we multiple both sides of equation 6 with P P(pa giving,
Σ
Σ Uld x( papio)
and
-U(d,)))(((((:))))) [dd', pap:
(9)
Let a = do(u2 fi())....... .(..)).....)) UN = fN(UN)). The joint P(z. papi
II. P(c. pa, o)
is polynomial, and the local interventions P(g 0) = Eeff((e)=a P(c pa,) keep it polynomial. Therefore equation is polynomial equation over the model parameters, and is certain to be non-trivial as d + d'. Therefore by Lemma 2 for almost all P. U equation 9 is not satisfied. and as there are finite number of decisions this implies that for almost all P, U there is single optimal decision for a given σ, pa and hence a single optimal policy.
Next, we detail how a policy oracle can be used identify a specific causal query in the shifted environment M (a), that will later use to identify the model parameters.
Lemma 4. Using an optimal policy oracle 1I3, where E includes all mixtures of local interventions on C including masking inputs Pa'n C Pan, then for any given Pa'n = pa'n such that Pa', n Pay = we can identify Eg P(C = c; σ) (d, c) Udd', c)}, for d and d' where d + d' and Z = C Pan
Proof. By Lemma 3 for almost all P, U there is single optimal decision following the shift a. Let dj = arg max, E(u do(D = d), pa'n: a] where d1 = (o). We can identify dj by querying the policy oracle with σ.
Consider a hard intervention on all C. E C, set C, = G to be the same state as in observation Paj = pa'n- The expected utility under this intervention is Elu do(DD = d), pa'n; o') = Udd x²) where X Pau (D} (and we have that D E Pay from Lemma Iii).
o' = do(c', cg.... ,Cy)) where for all C2 E Pa'p we
Next show that there is choice of hard intervention o' such that the policy oracle must return different optimal decisions in the context Pa'p pa', for o' and a. As Pa', n Par = @ then we are free to choose any X = x' and the resulting o' will be compatible with the evidence Pa', = pa'n. Note that by Lemma i X x' s.t. di f arg max, ('d, x'), else D di is optimal for all X = x which violates domain dependence. We can determine this X = x' given the utility function and d1. Let d2 arg max Udd ax) and o' do(cí, c2, .e,...,cC. c,x) be the hard intervention for which
x x' and Pa'p --ap-
19

---

Published as a conference paper at ICLR 2024
Consider the joint distribution over C under the mixed local intervention ((4) g0 + (1 10-0o'',
P(C = c do = d): = P(C = c; (
(10)
= =qP(C = c; (1-9))(CC=
(11)
where in the first line we have used Chp {U} to drop the intervention. Note that Z C Pap #0 by Lemma ii.. The expected utility is given by,
Elu pap, do(D = d):ō(a)) = Σ P(Z = = pap, do = ())
(12)
= P(C= c do = (9) U(d,z)
(13)
P(pap do(D) = d))((())
Σ -(CC=cā())[(d.)
(14)
P(papio(a))
= P(pap:o(a))
Σ = + (")
(15)
Note that for q the optimal decision is di and for q 0 the optimal decision returned by the policy oracle belongs to the set (dl s.t. d = arg max, Udd, x')} which does not contain d,. Furthermore, the argmax of equation 15| with respect to d is a piecewise linear function with domain q [o. 1]. Therefore there must be some q qerit that is the smallest value of such that for < qent the policy oracle returns an optimal decision in the set {dt.t. optimal decision is not in this set. The value of gen is given by B(u pap, do D d); o (gem)) = 0. which by equation [5 is.
arg max (dd x²)} and for g 2 Gen the
Gerit Σ
- U(ds, .)) + (1 Geni (u (U2,, x²) U (d), = 0
(16)
where d2 E s.t d = arg max, (d, x')) and d3 & sdt... d = arg max, (d, x'}}. This yields the following expression for Gerit.
EP(C=c;))U(( - U (d3, x)]
-1
gcrit =
(17)
U(d2,x') - -Udd,x'))
where we have used Σ P(C = c; (()22))))) U(ds. c)l (d2, - Uds, x'). We can determine Σ, - (;)
U(ds, m²) given qern and the utility function U(d, .:).
Finally, we describe a Algorithm (below) that uses policy oracle for the Monte Carlo estimation of quni which can be used determine Σ. P(C = c: ( c) Udd, c))) in the asymptotic limit N + oo as well as identifying d2, d3.
We are now ready to derive Theorem D
Theorem 1. For almost all CIDs M = (G.P) satisfying Assumptions I and 2, we can identify the directed acyelic graph G and joint distribution P over all ancestors of the utility Aney given ( (d) pap)) pap)r where (dd pap) is an optimal policy in the domain a and E is the set of all mixtures of local interventions. Proof in Appendix C
Proof. We learn the graph G and parameters P(c: pa,) by learning 'leave-one-out' interventional distributions P(c; do(c)...... G-1,, Ci+1,..., CN)). Note that under this intervention C, depends only on its parent set and hence P(c: do(c)..... Ci cN) P(c: pa,) where Pa, pa, denotes the state of Pa; under the leave-one-oue intervention. Almost all P are causally faithful (Meek) 2013). Hence, for almost all P. these interventional distributions can be used to determine Pa; as in the interventional distribution C, 1 C₁ if and only if C₁ E Pa,. Explicitly, for almost all environments, C Pa; if and only if there are two leave-one-one interventions that differ only on
20

---

Published as a conference paper at ICLR 2024
Algorithm Identify geri d2, d3 using policy oracle. Input: (U, I[ N.o.
dj < d
d2 + any hard intervention on C s.t. d2 = arg max, Ud, x) & D(q 1) s.t. d = arg max, (dd x
0=
for i + to N do
<~ Uniform (0, 1)
(d pap) < IT: ())
if d E D(g 1) A x (d pap) > 0 then
O 0+1
end if end for
Gcrit 0/N (qqnn)) t- 11/ (crit + (1 qenn) d3 ((gmu), d3 F d2
return Geni d2, d3
Cj with C== oj and C = cj such that P(c, do(ci...., Cj...., Gi-1, Gi.....,.c.coo cN)) + P(a: do(ci...... ...c.....c,, Cj..., G-11 C+11.... cN)). For ease notation we will use P(c pa,) interchangeably with P(c: do(c),.... .y...., Ci-1 Cxt),
First we learn the parameters for chance variables that have directed path to U that does not include D, i.e are ancestors of U in the graph G where we intervene on D.
Case 1: learning parameters for C₁ Ancy (G
Consider a directed path C - .... - C1 where C1 E Pay and all variables are chance nodes (the path does not include D). Assume we know Pag-1;-... Paj and the parameters P(C; pa,) for i = k- J,...,I. 1. We show that given these parameters we can identify the unknown parameters P(ck pa,)) (and hence Pag). Define Y = \ {Ck,..... Ci} } and consider the local intervention do(y), -N f(cx)) where do(ck = f(x)) is local intervention on Cg such that,
S(C,) [(C))= - otherwise
{ck Cs = c
(18)
Lee. f(Cx) maps Cg to 2 dimensional subspace where the image of C₁ - d is C2 ce and all other states being mapped to C ck where dy cx + de are arbitrary states of Ck. In the following we mask all inputs to the policy Pa = 0.
By Lemma we can identify,
PPCC= U(d
Σ
Σ
P(ck pa P(a -(a U(d,c)
6
Σ
P(ek (aaii))((c))
(19)
a
where
B(cx) = Σ ... Σ
P(ck-1 pa.-i:o)... P(c1 (U -((dd
(20)
and B(ci) =
(d' , c).. Note that equation 19 ((cx) is determined by the known parameters P(ct-1 pa, 1), ... P(g pa,) and U(aa)) and B(ck) non-zero for almost all P.U as ((cx) = is polynomial equation these parameters is not satisfied for almost all P.U.
Using the definition of the local intervention in equation 18 have P(Cs = de pag
P(C₁ = &f p. and P = di pa.io) = - P(C, = c paa; = 1- -PP(C = cg pag) Therefore the right hand side of equation 19 has single undetermined parameter P(Ca- C pa.)
21

---

Published as a conference paper at ICLR 2024
and the left hand side can be determined using the policy oracle (Lemmaa 4. and we solve for P(C+ = <x pa²)). By repeating this procedure with different interventions, varying the hard intervention do Y y and the choices of de. % can identify P(cx pag) for all Ck. pag and hence Pag-
We now learn the parameters for all C E (G We know the set Pay this is the domain of the utility function U (Paa) which known by assumption. We can then proceed iteratively, first learning the parameters of P, G that are P(ci pa,) and Paj for some Ci E Pay. We can do this as 3(cr) = (d, æ) U (d', x)) with d, x returned by Algorithm in Lemma 4nd and U (Pay) is known. We can then determine the parameters for all C₁ E Pai. and so on until we have traversed Ane We repeat this for all C, Pag until we have covered all Ancy (Gp).
Case 2: learning parameters for C AneD, C & Ancu(G
Consider CR E Ancy for which all directed paths to U are via D, C. + CR-1 +... + C where C1 E Pap. As before, assume we know Pak-1,..., Paj and the parameters P(C, pa,) for i= k .....,,. 1. We now show that given these parameters we can identify the unknown parameters P(ck pag) (and hence Paş).. Define Y = C' (Ck...., C1} and let
do (o(yy...... -N-K; O (cx)) where do(c; f((+) is a local intervention defined in equation T8| We now mask all
evidence except C₁, i.e. Pa {. Note that as C1 & Pag we can apply Lemma 4 giving (for
2 2)
Σ P(C = =GC==]])((dc)) U(d',c))
Σ. ... Σ P(ck pagio) ... P(a pa (U(d,c) U(d.c))
(21)
Σ P(ck pa. (((x)
(22)
where = = C. [[C] and,
a(cx)= = Σ
....I P(ck-1 pag_1) 1)... P(c. (dd U(d',))
Σ
(23)
Ch-1
02
and for k =1 we have,
CPCC=
P(C1 = =i pa);ao)(1)
(24)
where a(1) = U(d,z)-U(ddaa) We can determine (<c²) as we know the parameters for Ck Ck-1...., C1 by assumption, and a(c+) * 0 for almost all P, U as the equation ((ck) = 0 is polynomial the model parameters by Lemma
is not satisfied for almost all P. U. Using the definition of the local intervention equation 18 we have P(C₂ cg pa σ) = P(C, = c p..).
and P(C+ = c/' pag;o) =1 P(C; = 2 pa = P(C = & pa.). Therefore the right hand side of equation 19 has single undetermined parameter P(C,. d p and the left
hand side can be determined using the policy oracle (using Lemma 4 noting Pa'p = {Ci) and {C1} Pay 0), and we can solve for P(C,- de paa) By repeating this procedure with different interventions, varying the hard intervention do y) and the choices of c₂ c. we can identify P(cs paa) for all Ck2 Paj and hence Pay.
We now learn the parameters for all C. Anen \ Ancy p). We know Pan from the domain of the policy returned by the policy oracle. If the parameters for all variables in Pap have be learned in the previous set, we are finished. Otherwise, there are variables that are in Aney for which all directed paths to U are via D. Let this set of variables by Pap C Pap- For any C1 Pap can determine (C1) = Udd x) (dd', x) with d, d', x returned by Algorithm I in Lemma 4 noting that C, & Pag. We then determine the parameters for all C, E Paj, and so until have traversed Ancj, and repeat until we have learned the parameters for all C. E Ane \ Ancy (G)).
n
22

---

Published as a conference paper at ICLR 2024
D PROOF OF THEOREM 2
In this section we derive a version of Lemma 4 using a 6-optimal policy oracle for 5 > O. The reason we consider this case is that Theorem assumes optimality, which a strong assumption that won't be satisfied by realistic systems. is therefore important to determine if our main results are contingent on this assumption. For example, may be that we can only identify a causal model from the agent's policy for o = 0, and for 5 >> 0 no causal model can be learned. Instead, what we find is that realistic agents with 5 > 0 have to Iearn approximate causal models, with the fidelity of these approximations increasing in reasonable way as 6 + 0.
Low-regret analysis. What is a reasonable way for the approximation errors to change with d? Clearly, if an agent has an arbitrarily large regret bound 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 8 < 1E" [U]. As we work with the normalised utility function (see Appendix A.I)) we have E" [U] S and so can define the small regret regime as 8 < 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 small regret. Therefore get a linear trade-off between regret and accuracy for small 6.
First we show that Algorithm allows us estimate the value Qf P(C c; (d'', c)] with an approximate value Q, and estimate bounds Q+ such that the true value of Q is guaranteed to satisfy Q- =QSQ" Q
Dalloi
Lemma 5. Using a 5-optimal policy oracle IT' where E includes all mixtures of local interventions, including masking inputs Pa'n Pa then for any given Pa', = pa'n such that Pa Pay 0. we can determine d, d', x' where d & d' and a point estimate for Q(pa d, d') = Σ2 P(C = c; c;o)(U(d, x) - U (d', x]] < 0 and bounds Q E 11², ,Q+] where Z = C Pan. X = PPay \ (D) and.
1 (Q+
1 1- c (Q -) 6) S Q 2
(25)
1+
where
8/U8/UU x') Udd x²))
(26)
and in the worst case these bounds scale with as
O+
<
6
Q +
20
(27)
1+ {
I+
1 +
20
Q 2
Q
(28)
1 1--
1 1-E
Proof. By Lemma 3 for almost all P, U there is single optimal decision following the shift a. Let d2 be the optimal decision returned by the policy oracle in the context Pa'p = pain, which must satisfy the bound Elu d, pap: o] < max; B|u d, pap: o. 8.
Consider a hard intervention on all C. E C, o' == do(c', .g...,, ,,y)) where for all C2 E Pab we set C. = G to be the same state as in observation Pa'p = pa'n- The expected utility under this intervention is Elu do(D = d), pa'p; a') = Ud, x²) where X Pau (D} (and we have that D E Pay from Lemma Iii).
Next we show that there is a choice of hard intervention o' such that the policy oracle must return different optimal decisions in the context Pa'p pa', for o' and a. As Pa', n Par = 0 then we are free to choose any X = x' and the resulting o' will be compatible with the evidence Pa', = pa'y- Note that by Lemma i x x' s.t. di j arg max, ('d, x²), else D di is optimal for all X = x which violates domain dependence. We can determine this X = x' given the utility function and d1. Let d2 = arg max; (dd x²) and o' do(c), cg..,, cxx be the hard intervention for which x x' and Pa'p = pa'n- Note, we do not use the policy oracle to determine d2 which can be
23

---

Published as a conference paper at ICLR 2024
determined from U (Paa) alone, and hence there is no uncertainty if d2 is in fact optimal under of for any regret bound, nor that d1 is not optimal under o'.
Consider the joint distribution over C under the mixed local intervention a(4) go + (1- -1--o'''
P(C = c do D d))) = P(C = c; (
(29)
qP(C - c; (1-
(30)
where in the first line we have used Chy = {U} to drop the intervention. Note that Z C. Pap 7 by Lemma ii. The expected utility is given by,
E pan, do(D = d):
Σ P(Z = pan, do(D =):
(31)
P(C = do(D =o(D=))ãã(0))) d):ā(1)) U(d,a) Ud)
(32)
P(pap do(D = d);ā(g)
= P(papio(a))
- C(C=ccd))((d.))
(33)
Σ (C)(C===o)((d)))((((-() c;o''
(34)
((papio(())
Note that for = the optimal decision is d1 and forq 0 the optimal decision returned by the policy oracle belongs to the set {d s.t. d = arg max, Udd, x')} which does not contain dj. Furthermore, the argmax of equation 34] with respect to d is a piecewise linear function with domain E [0. 1]. Therefore there must be some q = Jen that is the smallest value of q such that for q < qua the policy oracle returns an optimal decision in the set s.t d = arg max, (d, x')} and for 2 aen the optimal decision not in this set. The value of gen is given by E|u pa do D = d): o (gen))
which by equation 34 is.
Gerit P(C==c;
Udd, m²) + (1 - (U a²) U x')] = 0
(35)
where d2 (ds.t. d = arg max, (d, x')} and ds & s.t d = arg max, (d, x')}. This yields the following expression for Gerit.
Σ CPCC=coo
U(ds, m)]
-1
Gerit =
1-
Uld2, x²) - U (dg, x²)
(36)
where we have used Σ
U(ds, c)] U x') U(ds, x').
While Algorithm T 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 no longer necessarily equal to 9cm- Instead, there are minimal and maximal value of that Algorithm can return, which are determined by the regret bound (see 7
Our first aim is to bound fen using returned by the policy oracle. The maximal (minimal) values q can take while satisfying the regret bound are q², which are the solutions to the equations
pa p. do(D = dz); E|u pap, =z) U
(37)
pa p. do D = d2); Elu pap. do (ippdd(DDd):0((1))) dz);ā(q))
(38)
Using equation 34 these simplify to
SP(pap:o )) + Σ P(C =
+ -1- (d3, a')l
(39)
8P(pap:o(g )) 2 Σ P(C c: -(dds + (1 x') U (ds, 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 quantity p(pap: (()) - giving,
8 q-' + Σ P(C c: (U)2, - x]] + (1 q- (UU((, - (d3,,x)))
(41)
i54 q Σ
= [ - U x:) + (1 - (1- x') - U Ud2g x')l
(42)
Let A1 == E/u pap. do(D D = d2): E/u pap, do = dz); oj and An == (d2, x²)
U(d3, x²). Note that 0 > 0 as d2 is optimal under o', and A < 0 as by linearity we have for q > qurit and yeri < 1 therefore a pa pa do = d2); We now define q= w.r.t the
Elu pap, do(D d > E/u pap:
d2); p =
Elu pap: do(D 11)
(relaxed) bounds equation 41 and equation 42 gives
and simplifying these inequalities using equation 36
q $ 9+ = min 1, Jeml (1 + E)} g q- max qeri( (1 {)}
(43)
(44)
where
{ = 5/ > 0
(45)
We therefore generate bounds on Gerit using equation 44 and equation 43 i.e.
Gerit // (1 -
(46)
Jem 2 // (1 +1+
(47)
We use q in place of Zea in equation 36 giving an estimate for Q= P.C c,o))
U Ud3 æ)), yielding.
Q = Do (1-1
(48)
Finally, applying bounds equation 46 and equation 47 gives,
1
1
(Ao 0) I+
(Do 60)
(49)
Next, we determine upper and lower bounds (9( using Q Ao(1 1/9an) and equation 46 and equation 47 giving,
1 1 {
i = Au
(50)
1 + E
Q 2- = Au
(51)
noting that as equation 48 is monotonic in that the true value of Q is guaranteed to fall between these bounds. Finally, we derive expressions for the worst-case bounds in terms of the true value Q.
which are given by determining @+ for the max and min values of q which are given by equation 47
and equation 46)
1-
Q+ max (+()) Do 1
(52)
+ E gerit
(1-5)
(1+ 11-50000
28
Q +
(53)
1 1+
1 1+ 1
Q = min Q (Ø) Au
1
(54)
1 & gerit
1 +
28
Q
(55)
1 1-
25

---

Published as a conference paper at ICLR 2024
o
8
6
A
0
1
19
Gerit
Figure 7: Overview of Lemma Dn U(d2, x²) Ud3,, x²) and A B[u pap: do(D d2);o] - R||u pap, D = a. Using an optimal policy oracle we can identify Genit precisely detailed in Lemma For 8 > instead of returning Yerit [ incur regret and so the value of for which the policy changes is no longer constrained to be Qocit- We use in place to Gerit calculate an approximate value of the target query, in the same way as in Lemma
as the agent can
4 The maximum and minimum values of q can take are qt' which result in maximal regret 5, q 2 q (cmi1 5/Ao) and S qt gent + 5/ Bu). We can therefore bound the amount that
Q deviates from the value of the target query Q.
Lemma 6. For 8 < ET" [U], Q and t (as defined Lemma 5) satisfy bounds,
( Q s 6(1
Q
) + 0
(56)
Ao
and
Q
②+ - S 25(1
+ 0
(57)
Au Q
Q- Q
28(1
0(0²)
(58)
Do
Proof. As work with the normalised utility function (see Appendix A.I have E [4] < 1
and define the small regret regime < We can Taylor expand the bounds on Q, about = 0 giving,
Q ) Ao
Q
Q Ao
2 ) 0
Q - 5(1
<Q=Q 5(1
(59)
and therefore,
Q- < 8(1
Q
)
(60)
Ao
and
Q + 0
δ+ Q 25(1
(61)
A, Q
-
Q - Q 2 26(1
)
(62)
An
therefore for small 8 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 7 and 2
iden- tify an approximate causal model M' = (P',G") given {ma (d pa where ET [U] 2 E [U] and Σ is the set of mixtures of local interventions. The parameters of M' satisfy [P'(u: pa,) P(u. pa,)) S (()) 4 V. V where x00) and 7()) grows linearly in 8 for small regret & E [U]. Proof in Appendix
D
26

---

Published as a conference paper at ICLR 2024
Proof. We the 5 8-optimal policy oracle to estimate the model parameters following the same steps as in the proof of Theorem i Appendix [C] However, as the policy oracle is no longer optimal, the parameters estimates will have errors. Here, show that for the parameters of P these errors grow linearly in for < 1, and that we learn a sparse sub-graph of G.
Estimating parameters of P.
In the proof of Theorem we estimate the parameters P(G pa,) in two cases.
Case 1.
Qk [ U(d',c) P(ex pagio))((x))
(63)
where
B(cx) = Σ ...
Σ P(ck- paz-iio).... P(c) pa (U) U(d
(64)
ck-1
which we rearrange using P(ce paaiio =1 -PP(ch payi 0) to give,
Qk 3(()) P(ch pagio) B(ck) - B(())
(65)
Assume have approximate values P(ck-1 oB).,.)).....P a) = P(ck pa + O(8), i.e. errors in our estimates for these parameters grow lin- early in 8 for < 1. As ((cx) is a sum products of these parameter estimates, then our estimate of ((xx) also has linear error for d < i.e B(cx) = B((x)) + O()), and likewise,
pajio) where P(ck
Qk 3(c)) + 0(6)
P(Ce pa 3(e() 3(()) + (6)
P(ck pa (1 O())
(66)
Then for A: = we know B(e)) = (d, c) U (d', e) precisely, and so
P(d oa = Q1 - B(c)) + (6) P(d pa (1++(0) 0()))
(67)
B(c)) B(c))
Which satisfies assumption of 0(8) error for k 1, < Therefore for all k we have enror that grows linearly for & 1.
The expressions for Qk, a(c;) for case 2 in the proof of Theorem are similar, and it is trivial to show by the same method that for these parameters the error also grow linearly in 5 for 8 << 1.
Learning graph structure. In Theorem
determine Paj, from P(ck do(C ())
Assuming causal faithfulness, which is satistied for almost all P (Meek] 2013). C, E Pag if and only if P(ex do(C' \ (Cx))) differ for some C₁- Cj C2 = cy. However, as now only have estimates P(c+ do(C') {C+))), any variation with respect to Cj c may be due to the varying emrors in these estimates rather than variation in the conditional probability itself. However, we have shown that we can learn any P(e; | pa.) within error bounds, and that these bounds scale linearly with 8 for & Let C E Pay+n and 022 P(ck do(C \ (Cx))), and denote corresponding upper and lower bounds from Lemma as O If 0kş + O2j and either o < O%g or 0 Oyy. non-overlapping bounds for Cj Cj and Cj cy. then we know with certainty that Cj E Pay. If there are no such non-overlapping bounds for all we do not know if Cj E Paş and so exclude it from the set. This approach guaranteed to identify a sub-graph of (i.e. no false positives-directee edges present in the approximate CBN that are not present in the environment). the true underlying causal model for all Pa = pa, intervening
Further, we only miss a parent to change Cj gives P((ck pa,, do(c,)) P(ck pag do(c))) < O()). Hence for 8 < we only fail to learn causal relations that small in magnitude (with respected to the regret 6). i.c. where the causal effect of the parent on the child (())
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 high accuracy compared to a random bascline.
E APPENDIX: PROOF OF THEOREM
Theorem 3. Given the CBN M (P. that is causally sufficient we can identffy optimal policies (d pa for any given U where Pay C C and for all soft interventions a. Given an approximate causal model M' (P', G') for which PP((v pa,)- P(u; pa,)] I & 1, we can identify regret-bounded policies where the regret ō grows linearly in c. Proof in Appendix
Proof. First we consider the case where we know the exact model M = G). As M is causally sufficient we can identify Ef/ | d. pap; a] for any given soft interventions compatible with G and which involve only variables in G (which includes Ancy U {U}). Our policy oracle is constructed by i) estimating E/u d, pa o for the input o, ii) calculating d' arg max Elu d, papi oj and returning any d' satisfying this.
G'), for which [P'(u, pa.) - P(u: pa S é < which implies (( pa,) = P(v, pa.) + c E where approximate the post-intervention joint distribution P' = = do D d). Pan = papio) = P(z = z do( = d), Pa = pa he + (c22) where Z = C \ Pan and l is function of the model parameters and constant in e. Let = E, Ujo where o; are soft interventions.
Next, consider the case where we know the approximate model M'
[al S 1. First we show that for any soft intervention
P'(C c do(D d):o0)
P' z | do(D Pan = papio)
Σ
9i P'(Z = z', Pan = papi o,)
(68)
= d = =);oo)
4 Σ. [[ |
do(D d);o,)
(69)
[I[P(C, = c. do d); + cd
Σ 9 Σ. [[[(C de do(D = d);0,) + +Gc
(70)
I[P(C, = c do(D = (1 + gg)
4 Σ. P[C d,y do(D d);o,) (1 + ct)
(71)
P(Z = do(DD = d)), Pan papipppp00 0) + (0) + O(e))
(72)
where dy = c;/ P(C; ai do(D = d): and (() is polynomial in the model parameters
0: ::P((m pa.). Therefore the expected utility under intervention evaluated using M' satisfies,
Ep U | dD = d), Pap = papl = Σ P'(z = z do = d), Pau = pap:o)
(73)
Σ Z = z doo = d), Pap = pap:o) + cg( + OE?)
(74)
= EU do(D = d), pap + + (
(75)
where g(0) is polynomial in the model parameters. The decision d' arg max, Ep [U do(D d), Pap = pap] incurs at most c0) regret, and therefore the regret is linear in e.
F EXPERIMENTS
As discussed in Section proofs of Theorems D and JandCcan be viewed as causal discovery algorithms where we assume i) knowledge of the set of environment variables C, ii) knowledge of the utility
28

---

Published as a conference paper at ICLR 2024
function U, 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 π ((r) under interventions a, with the approximation being exact when IT (()) are optimal.
To demonstrate this theoretical result we take the proof for simple Binary decision tasks outlined in Appendix [ and recast it as a causal discovery algorithm (Algorithm 2 below). We test it on CIDs of the form shown in Figure O where we randomly choose the joint distribution over X, Y and their causal structure G. Note that Algorithm 2 significantly simpler than the general method outlined in the proof of Theorem 1 as it exploits the fact that D, X, Y are binary variables and that |C] 2. This causal discovery algorithm requires that we can intervene on the latent variables X, X,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 latents X, 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 E {0,1) be two such diseases, for which there are treatments, i.e. we can intervene to 'turn off" X and but cannot observe them. D E {0, 1 represents 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 with X T, moderately effective for Y = T and less effective for X = F, Y = F). The doctor's s goal is to minimise symptom severity while avoiding unnecessary use of pain medication, e.g. U(d, x. y) = dl d[s( - cl where is some cost associated with pain relief and s(x, y) is the response to pain relief. Following an intervention o (e.g. curing a disease o 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 decisions D and observing the change in symptom severity- a context-free bandit problem. Although we cannot directly observe the disease states X, 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) Y) and the causal graph over X, Y.
Figure 9 shows the average error in the learned parameters P(z,, y) and G when π (a) satisfy different regret bounds. The results are averaged over 1000 randomly generated CBNs where i) the parameters of the joint distribution P(x,, 3/) are chosen at random, ii) the DAG G over X, Y is chosen at random from X + Y and X <- Y, iii) the utility function Udd, x, y) [0,1] is chosen at random (see Appendix
(..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 choose randomly from the two decisions when sampling from the policy oracle in Algorithm [ We also compare to random baseline algorithm which estimates P(x, y) 1/4 and randomly selects from X + Y or X + Y with equal probability. In a small number of cases Algorithm fails to predict P(x, v) [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 appears that the error rate grows sub-lineariy 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 5 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 APPENDIX: 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 provide necessary and sufficient conditions for identifying the expected utility following a distributional shift, R = Elu d. pap: v). given (partial) knowledge of i) the joint P, causal graph G and interventional
29

---

Published as a conference paper at ICLR 2024
urroe vok. rigres
P' moan GEEOZ V.4. regret
0335
0333
0.31
Modiel
6.56
0005
0.5
0.25
0.05
0.1
0.55
02
0.2
8/(R 1] Ej. D0 []]
6/[B[a]D 1] E[o[D - 0)
(a) Misclassification rate for G scaling with regret bound
(b) Mean parameter error for P(x. y) scaling with regret bound
P worst-case ector v.s. righet
0.75
0.20
Model
0.35
2/ ElulD 1] ElulD 0)
(c) Worst-case error for P(x, y) scaling with regret bound
Figure 9: Comparing the -vdel-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 5/ [E[u u = 1] E'u D OJl. Average error taken over 1000 randomly generated environments with binary decision D and two binary latent variables X, 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 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
function GRAPH LEARNER(IIS. U. N)
2:
d1. d2. x', , Gerit + Algorithm I(U, S N. = =oo 0))
Identify Gcrit for
do(Y = 0)
3:
Exp. U difference
(U(d2, x', a/.5))
2'1, (1 1/9ens)
4:
Ao U10, 0, d2) U0, 0, d1)
5:
Ai = U(1,0, d2) - (1,10 di)
6:
o = (Exp. U difference Ai)/(Ao -A)
7:
8:
d1, d2, ,',v', 3/,9cm Acrit +- Algorithm I(U, IV, N. = doo(Y 1))
Identify Gerit for
do(Y = 1)
9:
Exp. U difference (U(d2, x/ 1/) U Ud1, x1,,,/11/))) - 1/qmm)
10:
Ao = U(0, 1, 1,))) 1,0,,,d)
Ai (1) -U),,,,di)
12:
P(Xv=1=
(Exp. difference Ai)/(Ao -1)
14:
d1. d2, x','', VV' 9cm +- Algorithm IU. No = doo(X 0)) do(X 0)
Identify Tent for
15:
Exp. U difference = (Ub,, x' 1/) .//1) Ao U100, 0, d2) UO 0, d1)
U (d1, x1,))/ (1 - 1/9mm)
17:
Ai U'0, 1, d2) U,0,1,d)
18:
P(Yx-0= = = (Exp. U difference - A1)/(Ao - A1)
19:
20:
d1. d2, ,', 9en + Algorithm I(U. IU, N. = doo(X = 1))
Iddettffy Jan for
do(X =1)
21:
Exp. U difference = (U(d2, ,.,
1/) - U (di, x²,5/)) (1 - 1/4em)
Ao U(1, 0, d2) U11 0,)
23:
Ai = U d2) - 1,
P(Yx=1= 0) (Exp. U difference An)/(Ao A1)
25:
P(Yx = 0) P(Yx=1 = 0) then if P(Xy 0) P(Xr=1 then
Identify and from interventionals
27:
28:
G+()
29:
P(z,y) P(Xy=0 =x) =))
30:
else
31:
G (Y x) P(x,,) = P(Yx=0 = ())====))((Xx=> p) =
32:
33:
end
if
34: else
35:
G (X + Y)
36:
= = =
end if
38:
return G, P(x,v)
39:
end function
31

---

Published as a conference paper at ICLR 2024
distributions I 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 (012b). Hence, these results differ from Theorems and in that they restrict to the case where all assumptions 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 and indeed deep learning algorithms exploit much wider set of inductive biases than causal assumptions alone (Neyshabur et al.) [2014] |attaglia al. 2018 Rahaman al., 2019 Goyal & Bengio [022] 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 bierarchy's 's theorem (CHT). The celebrated causal hierarchy theorem (Bareinboim et al. 2022, lbeling& & Icard, (02T) shows that for almost all environments there causal relations between environment variables that cannot be identified from observational data without additional assumptions. Does this imply that 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 causal model necessary for identifying all causal and associative relations between environment variables? Yes, but only because this set of observational and interventional distributions a causal model. Formally, we can identify the underlying causal model (up latent confounders) by assuming causal faithfulness, which holds for almost all causal models (Meek 2013). The difference here is that the CHT 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 striet subset of these (regret-boundet 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 node D 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 [ and If this was implied by the CHT, it would not imply our results unless we restrict the causal structure (similar to transportabilityy) Likewise, is simple to show that Theorem | does not imply the CHT. In deriving Theorem [ we do restrict observational distributions (or make any restrictions on the data available the agent when generating its policy).
to the case where all assumptions as constraints
'Indeed, notable examples of causal assumptions that go beyond those expressible in DAG form include restricting the classes of structural equations Mooij et al. (016) and assuming cause-effect asymmetry MMirovic
2018)
32


Reviews:
[{"review_id": "DIlJnd32YJ", "reviewer": "Reviewer_gS4b", "summary": "This paper shows a formal connection between generalizing under distribution shits and learning causal models, a connection that has been expressed as hypothesis before (e.g. in Schölkopf 2021). Specifically, they show that if the agent performs well under distribution shifts (bounded regret), then it must have learned a representation that captures the causal structure of the world - in this case, the conditional independencies and causal relationships in the true causal bayesian network.", "questions": "(apologies for repetition from weaknesses)\n- The implications of the assumptions are not discussed. (e.g. I’d like to see things like, “assumption 2 implies that there exist distribution shifts for which the optimal policies are different”.\n- \"The environment is described by a set of random variables C...\" this sentence belongs to the main text since it you don't explain C random variable although it's heavily used.\n- Although discussed in the appendix, i'd like to see the description of what squares, circles and diamonds mean in the CID\n- In assumption 1 you stated $\\text{Desc}_D \\cap \\text{Anc}_U = \\emptyset$ but this doesn't exclude the trivial setting (which you state in the appendix is not of focus). Can you either extend the assumption or comment in the main text that it's not of interest the trivial setting? (i know it's a nitpick but got me wondered while reading it in the main text and i feel that since you thought about it you could have mentioned it earlier in the text).\n- Definition 6 in the appendix: Shouldn't it be $\\mathbb{E}^{\\pi_\\sigma}$ (subscript on policy)? Also, $\\delta \\geq 0$ is missing.\n- Can you please give a simple sketch of the proof? This would help the readability significantly. Also i feel there is a simple sentence that can be written on each theorem that explains its implications", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper makes an original and significant theoretical contribution by formally establishing a fundamental connection between causal learning and generalisation under distribution shifts.\n## Originality:\n* They provide a proof for showing that an agent that is sufficiently adaptive has learned a causal model of the environment. This is an impressive achievement and a stronger statement than the one stated by good regulator theorem (which as the authors have cited, has been misunderstood and misrepresented in the past)\n## Quality:\n* The theoretical results are technically strong, with detailed proofs provided in the appendices. \n* The assumptions are clearly stated and well-motivated. The analysis meaningfully relaxes the assumption of optimality.\n* The writing is clear, well-structured, and accessible given the technical nature of the work.\n## Clarity:\n* The paper is well written and easy to read.\n## Significance:\n* The results have important implications in safety and robustness under distribution shifts.\n* The proof is non-trivial and provides a great stepping stone for extending to richer settings (e.g. mediated decision tasks)", "weaknesses": "- As the authors acknowledge, the results are mainly theoretical. Even a minimal empirical validation of the key insights would strengthen the paper. For example it would be great even if you turn the informal overview (appendix C) into a simple simulation example rather than remain a thought experiment.\n- The scope is currently limited to unmediated decision tasks. Extending the results to broader RL settings would increase applicability (although I acknowledge that seems significantly more challenging task and out of scope of this work - it’s just a personal curiosity at this point and would be excited to see the next paper already).\n- The proof is still quite challenging to understand and I believe that there a more informal / simplified sketch that can be introduced to help the reader before dive into the more formal proof.\n- On a similar note, the implications of the assumptions are not discussed. (e.g. I’d like to see things like, “assumption 2 implies that there exist distribution shifts for which the optimal policies are different”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tUMhfkMi14", "reviewer": "Reviewer_4TT8", "summary": "The paper presents theoretical results showing that any agent that learns well under distributional shifts, must have learned the causal structure of the environment. Here distributional shifts that are most important are shifts of the latent causal variables. That is, if one can generalize across the set of possible changes in these variables, one has learned the causal structure. The result is both deep and intuitive, and has widespread implications. Although theoretical in important senses, e.g. it assumes some unspecified learning method, the result is no less powerful in arguing that to transfer one must learn causal structure.", "questions": "I would like to hear what changes to the introduction might look like.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is a gem. The theoretical analysis is simple and clear, the implications are broad and powerful.", "weaknesses": "The only weakness, in my opinion, is that the statement of the result in the introduction felt pretty slippery. (See detailed comments below.) All of this was satisfyingly resolved, but I do think the paper would benefit from an effort to sharpen that first section. \n\nDetails comments: \n- Please define these: \n\"distributional shifts\"\n\"distributionally shifted environments\"\n\"target domains\"\n\"causal modelling and transfer learning\"\n- \" used to derive out results\" typo\n- \"Our analysis focuses on distributional shifts that involve changes to the causal data generating process, and hence can be modelled as interventions (Schölkopf et al., 2021)\" This would have been nice in the intro. \n- \"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.\" I don't know that I understand this sentence. \n- \"By cCreftheorem: main,theorem: main approx agents\" typo?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "v7bE5YG9xr", "reviewer": "Reviewer_vFfA", "summary": "This paper proposes some theoretical results about decision making tasks that, if the environment is generated by a Bayesian network, and an agent is able to learn a low regret strategy for all mixture of local interventions on the environment, including hard intervention and randomized experiments on any number of variables, then we can recover the causal structure of the environment from the optimal decision learned by the agent. Therefore, if we want to obtain such an agent, it is necessary to learn the causal structure.", "questions": "see  in Weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. They propose theoretical results connecting decision making and causal structure learning. As suggested by their results, a robust enough agent should always learn the causal structure.\n2. The limitation for learning causal structure can be transferred to limitation of robust decision making by their results.\n3. Their result gives an example about inferring causal structure when only one variable is observed under each intervention.", "weaknesses": "1. They do not conduct an experiment for justifying their results.\n2. Their results can only be applied to a small range of scenarios, where we need to reach small regret for all mixture of local interventions. However, most applicable tasks, such as transfer learning, only consider interventions on a subset of variables.\n3. There are some spelling mistakes in their text, and some usage of notations are unclear in their text and proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UEJtxOTC7A", "reviewer": "Reviewer_VrNg", "summary": "The paper shows that any agent that could effectively \"learn\" the optimal decision under distribution shifts MUST have learned the (approximate) causal model of the data generating process. The implications of this result on the related research areas such as transfer learning and causal inference have been discussed.", "questions": "How to identify and prove the sufficient condition for learning the causal model for learning the optimal decision making under distribution shift?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem considered is fundamental.\n\n2. The idea is cute and clean.", "weaknesses": "Only necessary condition is proved but not the sufficient condition. It will be stronger to prove something like, if the agent has learned some \"approximate\" causal relationship, it can efficiently learn the optimal decision under distribution shift.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)