This is the twelfth and final post in the Cartesian Frames sequence. Read the first post here.
Up until now, we have (in the examples) mostly considered agents making a single choice, rather than acting repeatedly over time.
The actions, environments, and worlds we’ve considered might be extended over time. For example, imagine a prisoner’s dilemma where “cooperating” requires pushing a button every day for five years.
However, our way of discussing Cartesian frames so far would treat “push the button every day for five years” as an atomic action, a single element a∈A.
Now, will begin discussing how to use Cartesian frames to explicitly represent agents passing through time. Let us start with a basic example.
1. Partial Observability
Consider a process where two players, Yosef and Zoe, collaboratively choose a three-digit binary number. Yosef first chooses the first digit, then Zoe chooses the second digit, then Yosef chooses the third digit. The world will be represented by the three-digit number. The Cartesian frame from the perspective of Yosef looks like this:
Here, C0=(A0,E0,⋅0) is a Cartesian frame over W0={000,001,010,011,100,101,110,111}.
The four possible environments from left to right represent Zoe choosing 0, Zoe choosing 1, Zoe copying the first digit, and Zoe negating the first digit.
The eight possible agents can be broken up into two groups of four. In the top four possible agents, Yosef chooses 0 for the first digit, while in the bottom four, he chooses 1. Within each group, the four possible agents represent Yosef choosing 0 for the third digit, choosing 1 for the third digit, copying the second digit, and negating the second digit.
Consider the three partitions W1, W2, and W3 of W0 representing the first, second and third digits respectively. Wi={w0i,w1i}, where w01={000,001,010,011}, w11={100,101,110,111}, w02={000,001,100,101}, w12={010,011,110,111}, w03={000,010,100,110}, and w13={001,011,101,111}.
Clearly, by the definition of observables, W2 is not observable in C0. But there is still a sense in which this does not tell the whole story. Yosef can observe W2 for the purpose of deciding the third digit, but can’t observe W2 for the purpose of deciding the first digit.
There are actually many ways to express this fact, but I want to draw attention to one specific way to express this partial observability: ExternalW1(C0) can observe W2.
It may seem counter-intuitive that when you externalizeW1, and thus take some control out of the hands of the agent, you actually end up with more possible agents. This is because the agent now has to specify what the third digit is, not only as a function of the second digit, but also as a function of the first digit. The agent could have specified the third digit as a function of the first digit before, but some of the policies would have been identical to each other.
The four possible environments of C1 specify the first two digits, while the 16 possible agents represent all of the ways to have the third digit be a function of those first two digits. It is clear that W2 is observable in C1.
This gives us a generic way to define a type of partial observability:
Definition: Given a Cartesian frame C over W, and partitions V and T of W, we say V is observable in C after time T if V is observable in ExternalT(C).
2. Partitions as Time
Built into the above definition is the fact that we are thinking of (at least some) partitions of W as representing time. This makes a lot of sense when we think of W as a set of possible complete world histories. For any given time, this gives a partition where world histories are in the same subset if they agree on the world history up to that point in time.
For example, the above partition W1 was the partition that we got by considering a time after Yosef chooses the first digit, but before Zoe chooses the second digit.
Further, this gives us a sequence of nested partitions, since the partition associated with one time is always a refinement of the partition associated with an earlier time.
Note that this is a multiplicative/updateless view of time. There is also an additive/updateful view of time, in which time is a nested sequence of subsets. In the additive view, possible worlds are eliminated as you pass through time. In the multiplicative view, possible worlds are distinguished from each other as you pass through time. We will focus on the multiplicative view, which I consider better-motivated.
3. Nested Subagents
Let C=(A,E,⋅) be a fixed Cartesian frame over a world W. Let T0,⋯,Tn be a sequence of nested partitions of W, with T0={W}, Tn={{w}|w∈W}, and Ti+1 a refinement of Ti.
This gives a nested sequence of multiplicative superagents CTn◃×⋯◃×CT0, where CTi=ExternalTi(C), which follows from the lemma below.
Lemma: Given a Cartesian frame C over W, if U and V are partitions of W and U is a refinement of V, then ExternalU(C)◃×ExternalV(C).
Proof: Let C=(A,E,⋅), and let u:W→U and v:W→V send each element of W to their part in U and V respectively. Let ExternalU(C)=(A/BU,BU×E,⋅U), where BU={{a′∈A|∀e∈E,u(a′⋅e)=u(a⋅e)}|a∈A}. Similarly, letExternalV(C)=(A/BV,BV×E,⋅V), where BV={{a′∈A|∀e∈E,v(a′⋅e)=v(a⋅e)}|a∈A}. Let bU:A→BU and bV:A→BV send each element of A to its part in BU and BV respectively.
Since U is a refinement of V, there exists a v′:U→V, such that v′∘u=v. Further, we have that BU is a refinement of BV, so there exists a b′V:BU→BV such that b′V∘bU=bV.
It suffices to show there exist three sets X, Y, and Z, and a function f:X×Y×Z→W such that ExternalU(C)≃(X,Y×Z,⋄) and ExternalV(C)≃(X×Y,Z,∙), where ⋄ and ∙ are given by x⋄(y,z)=f(x,y,z) and (x,y)∙z=f(x,y,z).
We will take X to be A/BU and Z to be BV×E. We define Y to be the set of all right inverses to b′V, Y={y:BV→BU|∀b∈BU,b′V(y(b))=b}. We will let f(x,y,(b,e))=x(y(b))⋅e.
First, we show
ExternalU(C)=(A/BU,BU×E,⋅U)≃(X,Y×Z,⋄).
We define
(g0,h0):(A/BU,BU×E,⋅U)→(X,Y×Z,⋄)
and
(g1,h1):(X,Y×Z,⋄)→(A/BU,BU×E,⋅U)
as follows. Let g0 and g1 be the identity on X=A/BU, and let h0:Y×Z→BU×E be given by h0(y,(b,e))=(y(b),e). Finally, let h1:BU×E→Y×Z be chosen to satisfy h1(b,e)=(y,(b′V(b),e)), where y is such that y(b′V(b))=b, and for b′≠b′V(b), y(b′) is chosen arbitrarily to be any preimage of b′ under b′V.
We have that (g0,h0) is a morphism, because for all x∈A/BU and (y,(b,e))∈Y×Z,
where y is as given in the definition of h1. Since g0∘g1 and g1∘g0 are both the identity, we have that (g0,h0)∘(g1,h1) and (g1,h1)∘(g0,h0) are both homotopic to the identity, so ExternalU(C)≃(X,Y×Z,⋄).
Next, we show
ExternalV(C)=(A/BV,BV×E,⋅V)≃(X×Y,Z,∙).
We define
(g2,h2):(A/BV,BV×E,⋅V)→(X×Y,Z,∙)
and
(g3,h3):(X×Y,Z,∙)→(A/BV,BV×E,⋅V)
as follows. Let h2 and h3 be the identity on Z=BV×E, and let g3:X×Y→A/BV be given by g3(x,y)=x∘y. To see that x∘y is in A/BV, we need to verify that bV∘x∘y is the identity on BV. Indeed,
bV∘x∘y=b′V∘bU∘x∘y=b′V∘y,
which is the identity on BV. Let g2:A/BV→X×Y be given by g2(q)=(q′,bU∘q), where q′∈A/BU is chosen such that for all b∈BV, q′(bU(q(b)))=q(b), and for b′ not in the image of bU∘q, q′(b′)∈b′. We can do this simultaneously for all inputs of the form bU(q(b)), since bU∘q is injective, since it has a left inverse, b′V.
We have that (g2,h2) is a morphism, because for all q∈A/BV and (b,e)∈Z, we have
Since h3∘h2 and h2∘h3 are both the identity, we have that (g2,h2)∘(g3,h3) and (g3,h3)∘(g2,h2) are both homotopic to the identity, so ExternalV(C)≃(X×Y,Z,∙), completing the proof. □
The sequence CT0,…,CTn represents the agent persisting across time, but each subagent CTi does not really represent a single time-slice of the agent. Instead, CTi represents an agent persisting across time starting at the time Ti.
I think that this is actually the more natural notion. However, if we want to think about an agent persisting across times as a sequence of single times-slices of the agent, we could also do that. Since CTi+1 is a multiplicative subagent of CTi, CTi+1 must have a sister DTi+1 in CTi, so we could consider the sequence DT1,…,DTn.
4. Controllables Decrease and Observables Increase Over Time
An interesting fact about these sequences CT0,…,CTn is that controllables decrease and observables increase over time, so for i≤j we have Obs(CTi)⊆Obs(CTj) and Ctrl(CTi)⊇Ctrl(CTj) (and Ensure(CTi)⊇Ensure(CTj) and Prevent(CTi)⊇Prevent(CTj)), which follows directly from the following two lemmas.
Lemma: Given a Cartesian frame C over W, if U and V are partitions of W and U is a refinement of V, then Ctrl(ExternalV(C))⊇Ctrl(ExternalU(C)).
Proof: Let CV=ExternalV(C), and let CU=ExternalV(C). We will actually only need to use the fact that CU◃×CV, and that both CU and CV have nonempty agents.CU and CV do in fact have nonempty agent, because, as we have shown, externalizing a partition of W always produces nonempty agents.
It suffices to establish that Ensure(CTi)⊇Ensure(CTj), and the result for Ctrl follows trivially.
Since CU◃×CV, there exist X, Y, Z, and f:X×Y×Z→W such that CU≃(X,Y×Z,⋄) and CV≃(X×Y,Z,∙), where ⋄ and ∙ are given by x⋄(y,z)=f(x,y,z) and (x,y)∙z=f(x,y,z). Let C′U=(X,Y×Z,⋄), and let C′V≃(X×Y,Z,∙). Observe that X and Y are nonempty.
Since Ensure is preserved by biextensional equivalence, it suffices to show that Ensure(C′V)⊇Ensure(C′U). Let S∈Ensure(C′U). Thus, there exists some x0∈X, such that for all (y,z)∈Y×Z, x0⋄(y,z)=f(x0,y,z)∈S. Since Y is nonempty, we can take an arbitrary y0∈Y, and observe that for all z∈S, (x0,y0)∙z=f(x0,y0,z)∈S. Thus, S∈Ensure(C′V). □
Lemma: Given a Cartesian frame C over W, if U and V are partitions of W and U is a refinement of V, then Obs(ExternalV(C))⊆Obs(ExternalU(C)).
Proof: Let C=(A,E,⋅), and let u:W→U and v:W→V send each element of W to their part in U and V respectively. Let ExternalU(C)=(A/BU,BU×E,⋅U), where BU={{a′∈A|∀e∈E,u(a′⋅e)=u(a⋅e)}|a∈A}. Similarly, letExternalU(C)=(A/BV,BV×E,⋅V), where BV={{a′∈A|∀e∈E,v(a′⋅e)=v(a⋅e)}|a∈A}. Let bU:A→BU and bV:A→BV send each element of A to its part in BU and BV respectively.
Since U is a refinement of V, there exists a v′:U→V, such that v′∘u=v. Further, we have that BU is a refinement of BV, so there exists a b′V:BU→BV such that b′V∘bU=bV.
Let S∈Obs(ExternalV(C)). Thus, for every pair q0,q1∈A/BV, there exists a q2∈A/BV such that q2∈if(S,q0,q1). Thus, we can define an f:A/BV×A/BV→A/BV such that for all q0,q1∈A/BV, f(q0,q1)∈if(S,q0,q1).
Our goal is to show that S∈Obs(ExternalU(C)). For this, it suffices to show that for any q0,q1∈A/BU, there exists a q2∈A/BU such that q2∈if(S,q0,q1).
Let q0,q1∈A/BU be arbitrary. Given an arbitrary b∈BU, let qbi∈A/BV be any element that satisfies qbi(b′V(b))=qi(b). This is possible because qi(b)∈b⊆b′V(b). It does not matter what qbi does on other inputs. Let q2:BU→A be such that for all b∈BU, q2(b)=f(qb0,qb1)(b′V(b)).
To complete the proof, we need to show that q2∈A/BU and q2∈if(S,q0,q1).
To show that q2∈A/BU, we need that for all b∈BU, q2(b)∈b. Let b∈BU be arbitrary. Since q0(b)∈b, by the definition of BU, it suffices to show that for all e∈E, u(q2(b)⋅e)=u(q0(b)⋅e). Further, since q1(b)∈b, we already have that for all e∈E, u(q1(b)⋅e)=u(q0(b)⋅e). Thus, it suffices to show that for all e∈E, either q2(b)⋅e=q0(b)⋅e or q2(b)⋅e=q1(b)⋅e. Indeed, if q2(b)⋅e∈S, then
and similarly, if q2(b)⋅e∉S, then q2(b)⋅e=q1(b)⋅e. Thus, we have that for all e∈E, u(q2(b)⋅e)=u(q0(b)⋅e), so for our arbitrary b∈BU, q0(b)∈b, so q2∈A/BU.
Let (b,e)∈BU×E be such that q2⋅U(b,e)∈S. We want to show that q2⋅U(b,e)=q0⋅U(b,e). Indeed,
Symmetrically, if (b,e)∈BU×E is such that q2⋅U(b,e)∉S, we have q2⋅U(b,e)=q1⋅U(b,e). Thus q2∈if(S,q0,q1).
Thus, since q0 and q1 were arbitrary, we have that S∈Obs(ExternalU(C)), completing the proof. □
This result allows us to think of time as a sort of ritual in which control of the world is sacrificed in exchange for ability to condition on the world.
5. Directions for Future Work
As I noted at the start of this sequence, Cartesian frames take their motivation from Hutter, attempting to improve on the cybernetic agent model; they take their angle of attack from Pearl, using combinatorics to infer functional structure from relational structure; and they take their structure from game theory, working with base objects that look similar to normal-form games.
Building up from very simple foundations, we have found that Cartesian frames yield elegant notions of agents making choices and observations, of agents acting over time, and of subagent relations. At the same time, Cartesian frames allow us to switch between different levels of description of the world and consider many different ways of factorizing the world into variables.
I suspect that this is the last post I will write on Cartesian frames for a while, but I am excited about the framework, and would really like to get more people working on it.
To help with that, I’ve commented below with various directions for future work: ways that I think the framework could be extended, made better, or applied.
I’ve erred on the side of inclusion in these comments: some may point to dead ends, or may be based on false assumptions.
If you have questions or want to discuss Cartesian frames, I’ll be hosting a fourth and final office hours / discussion section this Sunday at 2pm PT on GatherTown.
Time in Cartesian Frames
This is the twelfth and final post in the Cartesian Frames sequence. Read the first post here.
Up until now, we have (in the examples) mostly considered agents making a single choice, rather than acting repeatedly over time.
The actions, environments, and worlds we’ve considered might be extended over time. For example, imagine a prisoner’s dilemma where “cooperating” requires pushing a button every day for five years.
However, our way of discussing Cartesian frames so far would treat “push the button every day for five years” as an atomic action, a single element a∈A.
Now, will begin discussing how to use Cartesian frames to explicitly represent agents passing through time. Let us start with a basic example.
1. Partial Observability
Consider a process where two players, Yosef and Zoe, collaboratively choose a three-digit binary number. Yosef first chooses the first digit, then Zoe chooses the second digit, then Yosef chooses the third digit. The world will be represented by the three-digit number. The Cartesian frame from the perspective of Yosef looks like this:
C0=⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝000010000010001011001011000011000011001010001010100110110100101111111101100111111100101110110101⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠.
Here, C0=(A0,E0,⋅0) is a Cartesian frame over W0={000, 001, 010, 011, 100, 101, 110, 111}.
The four possible environments from left to right represent Zoe choosing 0, Zoe choosing 1, Zoe copying the first digit, and Zoe negating the first digit.
The eight possible agents can be broken up into two groups of four. In the top four possible agents, Yosef chooses 0 for the first digit, while in the bottom four, he chooses 1. Within each group, the four possible agents represent Yosef choosing 0 for the third digit, choosing 1 for the third digit, copying the second digit, and negating the second digit.
Consider the three partitions W1, W2, and W3 of W0 representing the first, second and third digits respectively. Wi={w0i,w1i}, where w01={000, 001, 010, 011}, w11={100, 101, 110, 111}, w02={000, 001, 100, 101}, w12={010, 011, 110, 111}, w03={000, 010, 100, 110}, and w13={001, 011, 101, 111}.
Clearly, by the definition of observables, W2 is not observable in C0. But there is still a sense in which this does not tell the whole story. Yosef can observe W2 for the purpose of deciding the third digit, but can’t observe W2 for the purpose of deciding the first digit.
There are actually many ways to express this fact, but I want to draw attention to one specific way to express this partial observability: ExternalW1(C0) can observe W2.
Indeed, we have
ExternalW1(C0)≃C1=⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝000010100110000010100111000010101110000010101111000011100110000011100111000011101110000011101111001010100110001010100111001010101110001010101111001011100110001011100111001011101110001011101111⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠.
It may seem counter-intuitive that when you externalize W1, and thus take some control out of the hands of the agent, you actually end up with more possible agents. This is because the agent now has to specify what the third digit is, not only as a function of the second digit, but also as a function of the first digit. The agent could have specified the third digit as a function of the first digit before, but some of the policies would have been identical to each other.
The four possible environments of C1 specify the first two digits, while the 16 possible agents represent all of the ways to have the third digit be a function of those first two digits. It is clear that W2 is observable in C1.
This gives us a generic way to define a type of partial observability:
Definition: Given a Cartesian frame C over W, and partitions V and T of W, we say V is observable in C after time T if V is observable in ExternalT(C).
2. Partitions as Time
Built into the above definition is the fact that we are thinking of (at least some) partitions of W as representing time. This makes a lot of sense when we think of W as a set of possible complete world histories. For any given time, this gives a partition where world histories are in the same subset if they agree on the world history up to that point in time.
For example, the above partition W1 was the partition that we got by considering a time after Yosef chooses the first digit, but before Zoe chooses the second digit.
Further, this gives us a sequence of nested partitions, since the partition associated with one time is always a refinement of the partition associated with an earlier time.
Note that this is a multiplicative/updateless view of time. There is also an additive/updateful view of time, in which time is a nested sequence of subsets. In the additive view, possible worlds are eliminated as you pass through time. In the multiplicative view, possible worlds are distinguished from each other as you pass through time. We will focus on the multiplicative view, which I consider better-motivated.
3. Nested Subagents
Let C=(A,E,⋅) be a fixed Cartesian frame over a world W. Let T0,⋯,Tn be a sequence of nested partitions of W, with T0={W}, Tn={{w} | w∈W}, and Ti+1 a refinement of Ti.
This gives a nested sequence of multiplicative superagents CTn◃×⋯◃×CT0, where CTi=ExternalTi(C), which follows from the lemma below.
Lemma: Given a Cartesian frame C over W, if U and V are partitions of W and U is a refinement of V, then ExternalU(C)◃×ExternalV(C).
Proof: Let C=(A,E,⋅), and let u:W→U and v:W→V send each element of W to their part in U and V respectively. Let ExternalU(C)=(A/BU,BU×E,⋅U), where BU={{a′∈A | ∀e∈E,u(a′⋅e)=u(a⋅e)} | a∈A}. Similarly, letExternalV(C)=(A/BV,BV×E,⋅V), where BV={{a′∈A | ∀e∈E,v(a′⋅e)=v(a⋅e)} | a∈A}. Let bU:A→BU and bV:A→BV send each element of A to its part in BU and BV respectively.
Since U is a refinement of V, there exists a v′:U→V, such that v′∘u=v. Further, we have that BU is a refinement of BV, so there exists a b′V:BU→BV such that b′V∘bU=bV.
It suffices to show there exist three sets X, Y, and Z, and a function f:X×Y×Z→W such that ExternalU(C)≃(X,Y×Z,⋄) and ExternalV(C)≃(X×Y,Z,∙), where ⋄ and ∙ are given by x⋄(y,z)=f(x,y,z) and (x,y)∙z=f(x,y,z).
We will take X to be A/BU and Z to be BV×E. We define Y to be the set of all right inverses to b′V, Y={y:BV→BU | ∀b∈BU, b′V(y(b))=b}. We will let f(x,y,(b,e))=x(y(b))⋅e.
First, we show
ExternalU(C)=(A/BU,BU×E,⋅U)≃(X,Y×Z,⋄).We define
(g0,h0):(A/BU,BU×E,⋅U)→(X,Y×Z,⋄)and
(g1,h1):(X,Y×Z,⋄)→(A/BU,BU×E,⋅U)as follows. Let g0 and g1 be the identity on X=A/BU, and let h0:Y×Z→BU×E be given by h0(y,(b,e))=(y(b),e). Finally, let h1:BU×E→Y×Z be chosen to satisfy h1(b,e)=(y,(b′V(b),e)), where y is such that y(b′V(b))=b, and for b′≠b′V(b), y(b′) is chosen arbitrarily to be any preimage of b′ under b′V.
We have that (g0,h0) is a morphism, because for all x∈A/BU and (y,(b,e))∈Y×Z,
g0(x)⋄(y,(b,e))=f(x,y,(b,e))=x(y(b))⋅e=x⋅U(y(b),e)=x⋅Uh0(y,(b,e)).Similarly, (g1,h1) is a morphism, because for all x∈X and (b,e)∈BU×E, we have
g1(x)⋅U(b,e)=x⋅U(b,e)=x(b)⋅e=x(y(b′V(b)))⋅e=f(x,y,(b′V(b),e))=x⋄(y,(b′V(b),e))=x⋄h1(b,e),where y is as given in the definition of h1. Since g0∘g1 and g1∘g0 are both the identity, we have that (g0,h0)∘(g1,h1) and (g1,h1)∘(g0,h0) are both homotopic to the identity, so ExternalU(C)≃(X,Y×Z,⋄).
Next, we show
ExternalV(C)=(A/BV,BV×E,⋅V)≃(X×Y,Z,∙).We define
(g2,h2):(A/BV,BV×E,⋅V)→(X×Y,Z,∙)and
(g3,h3):(X×Y,Z,∙)→(A/BV,BV×E,⋅V)as follows. Let h2 and h3 be the identity on Z=BV×E, and let g3:X×Y→A/BV be given by g3(x,y)=x∘y. To see that x∘y is in A/BV, we need to verify that bV∘x∘y is the identity on BV. Indeed,
bV∘x∘y=b′V∘bU∘x∘y=b′V∘y,which is the identity on BV. Let g2:A/BV→X×Y be given by g2(q)=(q′,bU∘q), where q′∈A/BU is chosen such that for all b∈BV, q′(bU(q(b)))=q(b), and for b′ not in the image of bU∘q, q′(b′)∈b′. We can do this simultaneously for all inputs of the form bU(q(b)), since bU∘q is injective, since it has a left inverse, b′V.
We have that (g2,h2) is a morphism, because for all q∈A/BV and (b,e)∈Z, we have
g2(q)∙(b,e)=(q′,bU∘q)∙(b,e)=f(q′,bU∘q,(b,e))=q′(bU(q(b)))⋅e=q(b)⋅e=q⋅V(b,e)=h2(q)⋅V(b,e),where q′ is as in the definition of g2. Similarly, (g3,h3) is a morphism, because for all (x,y)∈X×Y and (b,e)∈BV×E, we have
g3(x,y)⋅V(b,e)=x∘y⋅V(b,e)=x(y(b))⋅e=f(x,y,(b,e))=(x,y)∙(b,e)=(x,y)∙h3(b,e).Since h3∘h2 and h2∘h3 are both the identity, we have that (g2,h2)∘(g3,h3) and (g3,h3)∘(g2,h2) are both homotopic to the identity, so ExternalV(C)≃(X×Y,Z,∙), completing the proof. □
The sequence CT0,…,CTn represents the agent persisting across time, but each subagent CTi does not really represent a single time-slice of the agent. Instead, CTi represents an agent persisting across time starting at the time Ti.
I think that this is actually the more natural notion. However, if we want to think about an agent persisting across times as a sequence of single times-slices of the agent, we could also do that. Since CTi+1 is a multiplicative subagent of CTi, CTi+1 must have a sister DTi+1 in CTi, so we could consider the sequence DT1,…,DTn.
4. Controllables Decrease and Observables Increase Over Time
An interesting fact about these sequences CT0,…,CTn is that controllables decrease and observables increase over time, so for i≤j we have Obs(CTi)⊆Obs(CTj) and Ctrl(CTi)⊇Ctrl(CTj) (and Ensure(CTi)⊇Ensure(CTj) and Prevent(CTi)⊇Prevent(CTj)), which follows directly from the following two lemmas.
Lemma: Given a Cartesian frame C over W, if U and V are partitions of W and U is a refinement of V, then Ctrl(ExternalV(C))⊇Ctrl(ExternalU(C)).
Proof: Let CV=ExternalV(C), and let CU=ExternalV(C). We will actually only need to use the fact that CU◃×CV, and that both CU and CV have nonempty agents.CU and CV do in fact have nonempty agent, because, as we have shown, externalizing a partition of W always produces nonempty agents.
It suffices to establish that Ensure(CTi)⊇Ensure(CTj), and the result for Ctrl follows trivially.
Since CU◃×CV, there exist X, Y, Z, and f:X×Y×Z→W such that CU≃(X,Y×Z,⋄) and CV≃(X×Y,Z,∙), where ⋄ and ∙ are given by x⋄(y,z)=f(x,y,z) and (x,y)∙z=f(x,y,z). Let C′U=(X,Y×Z,⋄), and let C′V≃(X×Y,Z,∙). Observe that X and Y are nonempty.
Since Ensure is preserved by biextensional equivalence, it suffices to show that Ensure(C′V)⊇Ensure(C′U). Let S∈Ensure(C′U). Thus, there exists some x0∈X, such that for all (y,z)∈Y×Z, x0⋄(y,z)=f(x0,y,z)∈S. Since Y is nonempty, we can take an arbitrary y0∈Y, and observe that for all z∈S, (x0,y0)∙z=f(x0,y0,z)∈S. Thus, S∈Ensure(C′V). □
Lemma: Given a Cartesian frame C over W, if U and V are partitions of W and U is a refinement of V, then Obs(ExternalV(C))⊆Obs(ExternalU(C)).
Proof: Let C=(A,E,⋅), and let u:W→U and v:W→V send each element of W to their part in U and V respectively. Let ExternalU(C)=(A/BU,BU×E,⋅U), where BU={{a′∈A | ∀e∈E,u(a′⋅e)=u(a⋅e)} | a∈A}. Similarly, letExternalU(C)=(A/BV,BV×E,⋅V), where BV={{a′∈A | ∀e∈E,v(a′⋅e)=v(a⋅e)} | a∈A}. Let bU:A→BU and bV:A→BV send each element of A to its part in BU and BV respectively.
Since U is a refinement of V, there exists a v′:U→V, such that v′∘u=v. Further, we have that BU is a refinement of BV, so there exists a b′V:BU→BV such that b′V∘bU=bV.
Let S∈Obs(ExternalV(C)). Thus, for every pair q0,q1∈A/BV, there exists a q2∈A/BV such that q2∈if(S,q0,q1). Thus, we can define an f:A/BV×A/BV→A/BV such that for all q0,q1∈A/BV, f(q0,q1)∈if(S,q0,q1).
Our goal is to show that S∈Obs(ExternalU(C)). For this, it suffices to show that for any q0,q1∈A/BU, there exists a q2∈A/BU such that q2∈if(S,q0,q1).
Let q0,q1∈A/BU be arbitrary. Given an arbitrary b∈BU, let qbi∈A/BV be any element that satisfies qbi(b′V(b))=qi(b). This is possible because qi(b)∈b⊆b′V(b). It does not matter what qbi does on other inputs. Let q2:BU→A be such that for all b∈BU, q2(b)=f(qb0,qb1)(b′V(b)).
To complete the proof, we need to show that q2∈A/BU and q2∈if(S,q0,q1).
To show that q2∈A/BU, we need that for all b∈BU, q2(b)∈b. Let b∈BU be arbitrary. Since q0(b)∈b, by the definition of BU, it suffices to show that for all e∈E, u(q2(b)⋅e)=u(q0(b)⋅e). Further, since q1(b)∈b, we already have that for all e∈E, u(q1(b)⋅e)=u(q0(b)⋅e). Thus, it suffices to show that for all e∈E, either q2(b)⋅e=q0(b)⋅e or q2(b)⋅e=q1(b)⋅e. Indeed, if q2(b)⋅e∈S, then
q2(b)⋅e=f(qb0,qb1)(b′V(b))⋅e=qb0(b′V(b))⋅e=q0(b)⋅e,and similarly, if q2(b)⋅e∉S, then q2(b)⋅e=q1(b)⋅e. Thus, we have that for all e∈E, u(q2(b)⋅e)=u(q0(b)⋅e), so for our arbitrary b∈BU, q0(b)∈b, so q2∈A/BU.
Let (b,e)∈BU×E be such that q2⋅U(b,e)∈S. We want to show that q2⋅U(b,e)=q0⋅U(b,e). Indeed,
q2⋅U(b,e)=q2(b)⋅e=f(qb0,qb1)(b′V(b))⋅e=f(qb0,qb1)⋅V(b′V(b),e)=qb0⋅V(b′V(b),e)=qb0(b′V(b))⋅e=q0(b)⋅e=q0⋅U(b,e).Symmetrically, if (b,e)∈BU×E is such that q2⋅U(b,e)∉S, we have q2⋅U(b,e)=q1⋅U(b,e). Thus q2∈if(S,q0,q1).
Thus, since q0 and q1 were arbitrary, we have that S∈Obs(ExternalU(C)), completing the proof. □
This result allows us to think of time as a sort of ritual in which control of the world is sacrificed in exchange for ability to condition on the world.
5. Directions for Future Work
As I noted at the start of this sequence, Cartesian frames take their motivation from Hutter, attempting to improve on the cybernetic agent model; they take their angle of attack from Pearl, using combinatorics to infer functional structure from relational structure; and they take their structure from game theory, working with base objects that look similar to normal-form games.
Building up from very simple foundations, we have found that Cartesian frames yield elegant notions of agents making choices and observations, of agents acting over time, and of subagent relations. At the same time, Cartesian frames allow us to switch between different levels of description of the world and consider many different ways of factorizing the world into variables.
I suspect that this is the last post I will write on Cartesian frames for a while, but I am excited about the framework, and would really like to get more people working on it.
To help with that, I’ve commented below with various directions for future work: ways that I think the framework could be extended, made better, or applied.
frames that are partitions into rectangles
generalizing observability
preferences and goals
subagents
logical time
logical uncertainty
formalizing time
computational complexity
time and coarse world models
category-theory-first approaches
I’ve erred on the side of inclusion in these comments: some may point to dead ends, or may be based on false assumptions.
If you have questions or want to discuss Cartesian frames, I’ll be hosting a fourth and final office hours / discussion section this Sunday at 2pm PT on GatherTown.