Robust agents learn causal world models — part 6/8

Cleaned-text code points [71241, 87049). Bibliography omitted here; source.md includes it.

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

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

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

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

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

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

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