Time in Cartesian Frames
post by Scott Garrabrant · 2020-11-11T20:25:19.400Z · LW · GW · 16 commentsContents
1. Partial Observability 2. Partitions as Time 3. Nested Subagents 4. Controllables Decrease and Observables Increase Over Time 5. Directions for Future Work None 16 comments
This is the twelfth and final post in the Cartesian Frames sequence. Read the first post here [LW · GW].
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 .
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, is a Cartesian frame over .
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 , , and of representing the first, second and third digits respectively. , where , , , , , and .
Clearly, by the definition of observables [LW · GW], is not observable in . But there is still a sense in which this does not tell the whole story. Yosef can observe for the purpose of deciding the third digit, but can't observe 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: can observe .
Indeed, we have
.
It may seem counter-intuitive that when you externalize [LW · GW] , 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 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 is observable in .
This gives us a generic way to define a type of partial observability:
Definition: Given a Cartesian frame over , and partitions and of , we say is observable in after time if is observable in .
2. Partitions as Time
Built into the above definition is the fact that we are thinking of (at least some) partitions of as representing time. This makes a lot of sense when we think of 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 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 [? · GW] 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 be a fixed Cartesian frame over a world . Let be a sequence of nested partitions of , with , , and a refinement of .
This gives a nested sequence of multiplicative superagents , where , which follows from the lemma below.
Lemma: Given a Cartesian frame over , if and are partitions of and is a refinement of , then .
Proof: Let , and let and send each element of to their part in and respectively. Let , where . Similarly, let, where . Let and send each element of to its part in and respectively.
Since is a refinement of , there exists a , such that . Further, we have that is a refinement of , so there exists a such that
It suffices to show there exist three sets , , and , and a function such that and , where and are given by and .
We will take to be and to be . We define to be the set of all right inverses to , . We will let .
First, we show
We define
and
as follows. Let and be the identity on , and let be given by . Finally, let be chosen to satisfy , where is such that , and for , is chosen arbitrarily to be any preimage of under .
We have that is a morphism, because for all and ,
Similarly, is a morphism, because for all and , we have
where is as given in the definition of . Since and are both the identity, we have that and are both homotopic to the identity, so .
Next, we show
We define
and
as follows. Let and be the identity on , and let be given by . To see that is in , we need to verify that is the identity on . Indeed,
which is the identity on . Let be given by , where is chosen such that for all , , and for not in the image of , . We can do this simultaneously for all inputs of the form , since is injective, since it has a left inverse, .
We have that is a morphism, because for all and , we have
where is as in the definition of . Similarly, is a morphism, because for all and , we have
Since and are both the identity, we have that and are both homotopic to the identity, so , completing the proof.
The sequence represents the agent persisting across time, but each subagent does not really represent a single time-slice of the agent. Instead, represents an agent persisting across time starting at the time .
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 is a multiplicative subagent of , must have a sister in , so we could consider the sequence .
4. Controllables Decrease and Observables Increase Over Time
An interesting fact about these sequences is that controllables decrease and observables increase over time, so for we have and (and and ), which follows directly from the following two lemmas.
Lemma: Given a Cartesian frame over , if and are partitions of and is a refinement of , then .
Proof: Let , and let . We will actually only need to use the fact that , and that both and have nonempty agents. and do in fact have nonempty agent, because, as we have shown, externalizing a partition of always produces nonempty agents.
It suffices to establish that , and the result for follows trivially.
Since , there exist , , , and such that and , where and are given by and . Let , and let . Observe that and are nonempty.
Since is preserved by biextensional equivalence, it suffices to show that . Let . Thus, there exists some , such that for all , . Since is nonempty, we can take an arbitrary , and observe that for all , . Thus, .
Lemma: Given a Cartesian frame over , if and are partitions of and is a refinement of , then .
Proof: Let , and let and send each element of to their part in and respectively. Let , where . Similarly, let, where . Let and send each element of to its part in and respectively.
Since is a refinement of , there exists a , such that . Further, we have that is a refinement of , so there exists a such that
Let Thus, for every pair , there exists a such that . Thus, we can define an such that for all , .
Our goal is to show that . For this, it suffices to show that for any , there exists a such that .
Let be arbitrary. Given an arbitrary , let be any element that satisfies . This is possible because . It does not matter what does on other inputs. Let be such that for all , .
To complete the proof, we need to show that and .
To show that , we need that for all , . Let be arbitrary. Since , by the definition of , it suffices to show that for all , . Further, since , we already have that for all , . Thus, it suffices to show that for all , either or . Indeed, if , then
and similarly, if , then . Thus, we have that for all , , so for our arbitrary , , so .
Let be such that . We want to show that . Indeed,
Symmetrically, if is such that , we have . Thus .
Thus, since and were arbitrary, we have that , 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 [LW · GW], 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 [LW(p) · GW(p)]
- generalizing observability [LW(p) · GW(p)]
- preferences and goals [LW(p) · GW(p)]
- subagents [LW(p) · GW(p)]
- logical time [LW(p) · GW(p)]
- logical uncertainty [LW(p) · GW(p)]
- formalizing time [LW(p) · GW(p)]
- computational complexity [LW(p) · GW(p)]
- time and coarse world models [LW(p) · GW(p)]
- category-theory-first approaches [LW(p) · GW(p)]
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 [LW · GW].
16 comments
Comments sorted by top scores.
comment by Scott Garrabrant · 2020-11-11T20:32:18.871Z · LW(p) · GW(p)
Preferences and goals
It might be interesting to put on top of this theory something that is dealing more with utilities, or something similar. Since this theory is basically a calculus of what agents could do, it seems likely that we could say interesting things by putting on top of it analysis of what agents should do.
Replies from: adamShimi↑ comment by adamShimi · 2020-11-12T00:35:13.435Z · LW(p) · GW(p)
I don't think that's what you had in mind, but one reason I am interested in learning more about Cartesian Frames is that I think that they might prove useful for formalizing the locality of goals [AF · GW]. Basically, the idea is to capture whether the goal followed by a system is really about its inputs, or if it is about the state of the world.
One way to understand this distinction is through wireheading. For example, I consider my own goals as about the world, because I wouldn't want to wirehead to believe that I accomplished them. Whereas having the goal of always being happy means being completely okay with wireheading, and so having a goal about my input instead of what truly happens in the world.
Intuitively, this distinction seem to depend on how the boundaries are drawn between the system/agent and the environment, as well as the interface. Which is where I draw a possible connection with Cartesian Frames. But I'm not sure if it is possible to use them for that purpose.
comment by Scott Garrabrant · 2020-11-11T20:34:19.106Z · LW(p) · GW(p)
Category-theory-first approaches
I am in general not especially proficient in category theory, and I think that the whole framework could be rewritten from the ground up by someone who is more proficient in category theory than me, and be made much better in the process.
comment by Scott Garrabrant · 2020-11-11T20:33:13.377Z · LW(p) · GW(p)
Logical uncertainty
There is a sense in which Cartesian frames is a very updateless ontology, and thus I am concerned about how to make it play nicely with logical uncertainty. Indeed, Cartesian frames are basically assuming that we have a set of possible worlds, which is assuming that we have objects that are the possible world that are not realized. Logical uncertainty does not do well with this assumption. Extending Cartesian frames to connect up with logical uncertainty is a major open problem.
comment by Scott Garrabrant · 2020-11-11T20:33:29.153Z · LW(p) · GW(p)
Formalizing time
I think that much of the meat of what I want Cartesian frames to do is connected to time, and I have only really touched the surface of that. I think that there is a lot more to say about time, and I think there are options we have about how to think about time in Cartesian frames. The one I presented is my favorite at the moment, but I am uncertain.
For example, one might want to think about an agent, and the collection of pairs of partitions and of , such that the agent has a (multiplicative?) subagent that could choose , while observing . This collection of pairs is closed under coarsening in both arguments, and so one could talk about a sort of Pareto frontier of how refined you can make given or vice versa. I think this Pareto frontier looks a lot like time.
Replies from: ramana-kumar↑ comment by Ramana Kumar (ramana-kumar) · 2021-03-29T18:26:37.508Z · LW(p) · GW(p)
"subagent [] that could choose " -- do you mean or or neither of these? Since is not closed under unions, I don't think the controllables version of "could choose" is closed under coarsening the partition. (I can prove that the ensurables version is closed; but it would have been nice if the controllables version worked.)
ETA: Actually controllables do work out if I ignore the degenerate case of a singleton partition of the world. This is because, when considering partitions of the world, ensurables and controllables are almost the same thing.
comment by Scott Garrabrant · 2020-11-11T20:34:02.377Z · LW(p) · GW(p)
Time and coarse world models
I feel like the partial observability I get from taking a coarsening of the world and saying an agent has observations in that coarsening is similar to the partial observability I get when saying an agent learns something at a specific time. In particular, these two things seem similar enough to me that one might be able to unify the two definitions, and in the process reveal new things about them.
Replies from: ramana-kumar↑ comment by Ramana Kumar (ramana-kumar) · 2021-02-22T11:46:55.536Z · LW(p) · GW(p)
I have something suggestive of a negative result in this direction:
Let be the prime-detector situation from Section 2.1 of the coarse worlds post [? · GW], and let be the (non-surjective) function that "heats" the outcome (changes any "C" to an "H"). The frame is clearly in some sense equivalent to the one from the example (which deletes the temperature from the outcome) -- I am using my version just to stay within the same category when comparing frames. As a reminder, primality is not observable in but is observable in .
Claim: No frame of the form is biextensionally equivalent to
Proof Idea:
The kind of additional observability we get from coarsening the world seems in this case to be very different from the kind that comes from externalising part of the agent's decision.
comment by Scott Garrabrant · 2020-11-11T20:33:45.509Z · LW(p) · GW(p)
Computational complexity
A random open question I am curious about, but doesn't seem that important: Is the existence of a morphism between Cartesian frames NP-complete?
comment by Scott Garrabrant · 2020-11-11T20:32:55.991Z · LW(p) · GW(p)
Logical time
In agent simulates predictor, I am given a proof that I output a certain action, and then I must make a choice. In making this choice, I am determining whether or not I am given that proof in the first place. Further, the proof must in some sense compress my deliberation, or I would not be able to comprehend it. Thus, I feel that there are some details of the proof that are not "true inputs" for me.
I want to say that my deciding what I would do if I saw a proof is "earlier" than the proof according to some generalized notion of causality, or earlier in "logical time." I want to say that the only way to make the agent-simulates-predictor set-up make sense is to have the full proof itself not be a true input for me. I think that Cartesian frames is a step towards making continuous the notion of inputs and outputs, and so could help our thinking around this problem.
comment by Scott Garrabrant · 2020-11-11T20:32:37.131Z · LW(p) · GW(p)
Subagents
I think that our current ability to talk about agents contained within other agents is pretty limited, and Cartesian frames is a significant step forward on that. It would not surprise me if this could help with fixing our ontology around subsystem alignment. It could also help with our ontology around reasoning about committees, subcommittees, and members.
comment by Scott Garrabrant · 2020-11-11T20:31:58.549Z · LW(p) · GW(p)
Generalizing observability
Observables can clearly be extended to infinite partitions, and maybe further to a sigma algebra or something similar. One might want to also think of and as sigma algebras.
Observables can also be extended to talk about separating two subsets of , rather than separating a subset of from its complement. One could also talk about observables that don't allow for arbitrary functions from the observed to , but instead allow for some restricted class such as continuous or Kakutani functions.
Such restricted classes might make more sense when using this more general notion of observables, or it might be possible to entirely construct these classes from this notion of observables.
This could allow the theory to encompass game theory, since you could have two agents which choose a probabilistic strategy, while knowing the probabilistic strategy chosen by the other player.
comment by Scott Garrabrant · 2020-11-11T20:31:36.174Z · LW(p) · GW(p)
Frames that are partitions into rectangles
I think that there might be significantly more that can be said about Cartesian frames that are a "partition into rectangles" than can be said about Cartesian frames in general.
By a "partition into rectangles," I mean a Cartesian frame such that if , then . In particular, this assumption is saying something to the effect of "the level of description of this world is refined enough to play nicely with the factorization into and ."
comment by Ramana Kumar (ramana-kumar) · 2021-02-04T08:41:56.604Z · LW(p) · GW(p)
It suffices to establish that
I think the and here are supposed to be and
comment by DanielFilan · 2020-11-12T02:37:35.896Z · LW(p) · GW(p)
Yosef can observe for the purpose of deciding the first digit, but can't observe for the purpose of deciding the third digit.
Am I missing something, or should this be the other way around? Intuitively, I'd think that it makes sense that Yosef can observe the second digit when choosing the third, but not when choosing the first.
Replies from: Scott Garrabrant↑ comment by Scott Garrabrant · 2020-11-12T06:03:55.180Z · LW(p) · GW(p)
Fixed, thanks.