Robust agents learn causal world models — part 7/8

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

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

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

1− 1−ξ
˜q

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

1− 1 +ξ
˜q

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

1− 1−ξ
1 +ξ
1
qcrit

(52)
=
1−ξ
1 +ξ

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

1− 1 +ξ
1−ξ
1
qcrit

(54)
=
1 +ξ
1−ξ

Q− 2δ
1−ξ (55)
25

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



 ˜Q−Q



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


 ˜Q−Q



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

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

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