Introduction to Cartesian Frames

post by Scott Garrabrant · 2020-10-22T13:00:00.000Z · LW · GW · 32 comments

Contents

  1. Definition
  2. Normal-Form Games
    2.1. Coarse World Models
    2.2. Symmetry
    2.3. Relation to Extensive-Form Games
  3. Controllables
    3.1. Closure Properties
    3.2. Examples of Controllables
  4. Observables
    4.1. Closure Properties
    4.2. Examples of Observables
  5. Controllables and Observables Are Disjoint
    5.1. Properties That Are Both Observable and Ensurable Are Inevitable
    5.2. Controllables and Observables in Degenerate Frames
    5.3. A Suggestion of Time
  6. Why Cartesian Frames?
    6.1. Cybernetic Agent Model
    6.2. Deriving Functional Structure
    6.3. Contents
  Footnotes
None
32 comments

This is the first post in a sequence on Cartesian frames, a new way of modeling agency that has recently shaped my thinking a lot.

Traditional models of agency have some problems, like:

• They treat the "agent" and "environment" as primitives with a simple, stable input-output relation. (See "Embedded Agency [? · GW].")
• They assume a particular way of carving up the world into variables, and don't allow for switching between different carvings or different levels of description.

Cartesian frames are a way to add a first-person perspective (with choices, uncertainty, etc.) on top of a third-person "here is the set of all possible worlds," in such a way that many of these problems either disappear or become easier to address.

The idea of Cartesian frames is that we take as our basic building block a binary function which combines a choice from the agent with a choice from the environment to produce a world history.

We don't think of the agent as having inputs and outputs, and we don't assume that the agent is an object persisting over time. Instead, we only think about a set of possible choices of the agent, a set of possible environments, and a function that encodes what happens when we combine these two.

This basic object is called a Cartesian frame. As with dualistic agents [? · GW], we are given a way to separate out an “agent” from an “environment." But rather than being a basic feature of the world, this is a “frame” — a particular way of conceptually carving up the world.

We will use the combinatorial properties of a given Cartesian frame to derive versions of inputs, outputs and time. One goal here is that by making these notions derived rather than basic, we can make them more amenable to approximation and thus less dependent on exactly how one draws the Cartesian boundary. Cartesian frames also make it much more natural to think about the world at multiple levels of description, and to model agents as having subagents.

Mathematically, Cartesian frames are exactly Chu spaces. I give them a new name because of my specific interpretation about agency, which also highlights different mathematical questions.

Using Chu spaces, we can express many different relationships between Cartesian frames. For example, given two agents, we could talk about their sum ($\oplus$), which can choose from any of the choices available to either agent, or we could talk about their tensor ($\otimes$), which can accomplish anything that the two agents could accomplish together as a team.

Cartesian frames also have duals (${-}^{\ast }$) which you can get by swapping the agent with the environment, and $\oplus$ and $\otimes$ have De Morgan duals ($\&$ and $⅋$ respectively), which represent taking a sum or tensor of the environments. The category also has an internal hom, $⊸$, where $C⊸D$ can be thought of as "$D$ with a $C$-shaped hole in it." These operations are very directly analogous to those used in linear logic.

 

1. Definition

Let $W$ be a set of possible worlds. A Cartesian frame $C$ over $W$ is a triple $C=(A,E,\cdot )$, where $A$ represents a set of possible ways the agent can be, $E$ represents a set of possible ways the environment can be, and $\cdot :A\times E\to W$ is an evaluation function that returns a possible world given an element of $A$ and an element of $E$.

We will refer to $A$ as the agent, the elements of $A$ as possible agents, $E$ as the environment, the elements of $E$ as possible environments, $W$ as the world, and elements of $W$ as possible worlds.

Definition: A Cartesian frame $C$ over a set $W$ is a triple $(A,E,\cdot )$, where $A$ and $E$ are sets and $\cdot :A\times E\to W$. If $C=(A,E,\cdot )$ is a Cartesian frame over $W$, we say $\text{Agent}\left(C\right)=A$, $\text{Env}\left(C\right)=E$, $\text{World}\left(C\right)=W$, and $\text{Eval}\left(C\right)=\cdot$.

A finite Cartesian frame is easily visualized as a matrix, where the rows of the matrix represent possible agents, the columns of the matrix represent possible environments, and the entries of the matrix are possible worlds:

$\begin{array}{ccc}& & \begin{array}{ccc}& E& \\ e_1& e_2& e_3\end{array}\\ A& \begin{array}{c}{a}_1\\ a_2\\ a_3\end{array}& \left(\begin{array}{ccc}{w}_1& w_2& w_3\\ w_4& w_5& w_6\\ w_7& w_8& w_9\end{array}\right)\end{array}$.

E.g., this matrix tells us that if the agent selects $a_3$ and the environment selects $e_1$, then we will end up in the possible world $w_7$.

Because we're discussing an agent that has the freedom to choose between multiple possibilities, the language in the definition above is a bit overloaded. You can think of $A$ as representing the agent before it chooses, while a particular $a\in A$ represents the agent's state after making a choice.

Note that I'm specifically not referring to the elements of $A$ as "actions" or "outputs"; rather, the elements of $A$ are possible ways the agent can choose to be.

Since we're interpreting Cartesian frames as first-person perspectives tacked onto sets of possible worlds, we'll also often phrase things in ways that identify a Cartesian frame $C$ with its agent. E.g., we will say "$C_0$ is a subagent of $C_1$" as a shorthand for "$C_0$'s agent is a subagent of $C_1$'s agent."

We can think of the environment $E$ as representing the agent's uncertainty about the set of counterfactuals, or about the game that it's playing, or about "what the world is as a function of my behavior."

A Cartesian frame is effectively a way of factoring the space of possible world histories into an agent and an environment. Many different Cartesian frames can be put on the same set of possible worlds, representing different ways of doing this factoring. Sometimes, a Cartesian frame will look like a subagent of another Cartesian frame. Other times, the Cartesian frames may look more like independent agents playing a game with each other, or like agents in more complicated relationships.

 

2. Normal-Form Games

When viewed as a matrix, a Cartesian frame looks much like the normal form of a game, but with possible worlds rather than pairs of utilities as entries.

In fact, given a Cartesian frame over $W$, and a function from $W$ to a set $V$, we can construct a Cartesian frame over $V$ by composing them in the obvious way. Thus, if we had a Cartesian frame $(A,E,\cdot )$ and a pair of utility functions $U_A:W\to R$ and $U_E:W\to R$, we could construct a Cartesian frame over $R^2$, given by $(A,E,\star )$, where $a\star e:=\left(U_A\right(a\cdot e),U_E(a\cdot e\left)\right)$. This Cartesian frame will look exactly like the normal form of a game. (Although it is a bit weird to think of the environment set as having a utility function.)

We can use this connection with normal-form games to illustrate three features of the ways in which we will use Cartesian frames.

 

2.1. Coarse World Models

First, note that we can talk about a Cartesian frame over $R^2$, even though one would not normally think of $R^2$ as a set of possible worlds.

In general, we will often want to talk about Cartesian frames over "coarse" models of the world, models that leave out some details. We might have a world model $W$ that fully specifies the universe at the subatomic level, while also wanting to talk about Cartesian frames over a set $V$ of high-level descriptions of the world.

We will construct Cartesian frames over $V$ by composing Cartesian frames over $W$ with the function from $W$ to $V$ that sends more refined, detailed descriptions of the universe to coarser descriptions of the same universe.

In this way, we can think of an element of $(r_1,r_2)\in R^2$ as the coarse, high-level possible world given by "Those possible worlds for which $U_A=r_1$ and $U_E=r_2$."

Definition: Given a Cartesian frame $C=(A,E,\cdot )$ over $W$, and a function $f:W\to V$, let $f^{\circ }\left(C\right)$ denote the Cartesian frame over $V$, $f^{\circ }\left(C\right)=(A,E,\star )$, where $a\star e=f(a\cdot e)$.

 

2.2. Symmetry

Second, normal-form games highlight the symmetry between the players.

We do not normally think about this symmetry in agent-environment interactions, but this symmetry will be a key aspect of Cartesian frames. Every Cartesian frame $C=(A,E,\cdot )$ has a dual which swaps $A$ and $E$ and transposes the matrix.

 

2.3. Relation to Extensive-Form Games

Third, much of what we'll be doing with Cartesian frames in this sequence can be summarized as "trying to infer extensive-form games from normal-form games" (ignoring the "games" interpretation and just looking at what this would entail formally).

Consider the ultimatum game. We can represent this game in extensive form:

Given any game in extensive form, we can then convert it to a game in normal form. In this case:

$\begin{array}{ccc}& Offer6& Offer3\\ Accept6,Accept3& 6,6& 9,3\\ Accept6,Reject3& 6,6& 0,0\\ Reject6,Accept3& 0,0& 9,3\\ Reject6,Reject3& 0,0& 0,0\end{array}$

The strategies in the normal-form game are the policies in the extensive-form game.

If we then delete the labels [LW · GW], so now we just have a bunch of combinatorial structure about which things send you to the same place, I want to know when we can infer properties of the original extensive-form game, like time and information states.

Although we've used games to note some features of Cartesian frames, we should be clear that Cartesian frames aren't about utilities or game-theoretic rationality. We are not trying to talk about what the agent does, or what the agent should do. In fact, we are effectively taking as our most fundamental building block that an agent can freely choose from a set of available actions.

The theory of Cartesian frames is trying to understand what agents' options are. Utility functions and facts about what the agent actually does can possibly later be placed on top of the Cartesian frame framework, but for now we will be focusing on building up a calculus of what the agent could do.

 

3. Controllables

We would like to use Cartesian frames to reconstruct ideas like "an agent persisting over time," inputs (or "what the agent can learn"), and outputs (or "what the agent can do"), by taking as basic:

1. an agent's ability to "freely choose" between options;
2. a collection of possible ways those options can correspond to world histories; and
3. a notion of when world histories are considered the same in some coarse world model.

In this way, we hope to find new ways of thinking about partial and approximate versions of these concepts.

Instead of thinking of the agent as an object with outputs, I expect a more embedded view to think of all the facts about the world that the agent can force to be true or false.

This includes facts of the form "I output foo," but it also includes facts that are downstream from immediate outputs. Since we're working with "what can I make happen?" rather than "what is my output?", the theory becomes less dependent on precisely answering questions like "Is my output the way I move my mouth, or is it the words that I say?"

We will call the analogue of outputs in Cartesian frames controllables. The types of our versions of "outputs" and "inputs" are going to be subsets of $W$, which we can think of as properties of the world. E.g., $S$ might be the set of worlds in which woolly mammoths exist; we could then think of "controlling $S$" as "controlling whether or not mammoths exist."

We'll define what an agent can control as follows. First, given a Cartesian frame $C=(A,E,\cdot )$ over $W$, and a subset $S$ of $W$, we say that $S$ is ensurable in $C$ if there exists an $a\in A$ such that for all $e\in E$, we have $a\cdot e\in S$. Equivalently, we say that $S$ is ensurable in $C$ if at least one of the rows in the matrix only contains elements of $S$.

Definition: $\text{Ensure}\left(C\right)=\{S\subseteq W|\exists a\in A,\forall e\in E,a\cdot e\in S\}$.

If an agent can ensure $S$, then regardless of what the environment does — and even if the agent doesn't know what the environment does, or its behavior isn't a function of what the environment does — the agent has some strategy which makes sure that the world ends up in $S$. (In the degenerate case where the agent is empty, the set of ensurables is empty.)

Similarly, we say that $S$ is preventable in $C$ if at least one of the rows in the matrix contains no elements of $S$.

Definition: $\text{Prevent}\left(C\right)=\{S\subseteq W|\exists a\in A,\forall e\in E,a\cdot e\notin S\}$.

If $S$ is both ensurable and preventable in $C$, we say that $S$ is controllable in $C$.

Definition: $\text{Ctrl}\left(C\right)=\text{Ensure}\left(C\right)\cap \text{Prevent}\left(C\right)$.

 

3.1. Closure Properties

Ensurability and preventability, and therefore also controllability, are closed under adding possible agents to $A$ and removing possible environments from $E$.

Claim: If $A^{\prime }\supseteq A$ and $E^{\prime }\subseteq E$, and if for all $a\in A$ and $e\in E^{\prime }$ we have $a\star e=a\cdot e$, then $\text{Ctrl}(A^{\prime },E^{\prime },\star )\supseteq \text{Ctrl}(A,E,\cdot )$.

Proof: Trivial. $\square$

Ensurables are also trivially closed under supersets. If I can ensure some set of worlds, then I can ensure some larger set of worlds representing a weaker property (like "mammoths exist or cave bears exist").

Claim: If $S_1\subseteq S_2\subseteq W$, and $S_1\in \text{Ensure}\left(C\right)$, then $S_2\in \text{Ensure}\left(C\right)$.

Proof: Trivial. $\square$

$\text{Prevent}\left(C\right)$ is similarly closed under subsets. $\text{Ctrl}\left(C\right)$ need not be closed under subsets or supersets.

Since $\text{Ensure}\left(C\right)$ and $\text{Prevent}\left(C\right)$ will often be large, we will sometimes write them using a minimal set of generators.

Definition: Let $⟨S_1,\dots ,S_n{⟩}_{\supset }$ denote the the closure of $\{S_1,\dots ,S_n\}$ under supersets. Let $⟨S_1,\dots ,S_n{⟩}_{\subset }$ denote the closure of $\{S_1,\dots ,S_n\}$ under subsets.

 

3.2. Examples of Controllables

Let us look at some simple examples. Consider the case where there are two possible environments, $r$ for rain, and $s$ for sun. The agent independently chooses between two options, $u$ for umbrella, and $n$ for no umbrella. $A=\{u,n\}$ and $E=\{r,s\}$. There are four possible worlds, $W=\{ur,us,nr,ns\}$. We interpret $ur$ as the world where the agent has an umbrella and it is raining, and similarly for the other worlds. The Cartesian frame, $C_1$, looks like this:

$C_1=\begin{array}{cc}& \begin{array}{cc}r& s\end{array}\\ \begin{array}{c}u\\ n\end{array}& \left(\begin{array}{cc}ur& us\\ nr& ns\end{array}\right)\end{array}$.

$\text{Ensure}\left(C_1\right)=⟨\{ur,us\},\{nr,ns\}{⟩}_{\supset }$, or

$$\left\{\right\{ur,us\},\{nr,ns\},\{ur,us,nr\},\{ur,us,ns\},\{nr,ns,ur\},\{nr,ns,us\},W\},$$

and $\text{Prevent}\left(C_1\right)=⟨\{ur,us\},\{nr,ns\}{⟩}_{\subset }$, or

$$\left\{\right\{ur,us\},\{nr,ns\},\{ur\},\{us\},\{nr\},\{ns\},\{\left\}\right\}.$$

Therefore $\text{Ctrl}\left(C_1\right)=\left\{\right\{ur,us\},\{nr,ns\left\}\right\}$.

The elements of $\text{Ctrl}\left(C_1\right)$ are not actions, but subsets of $W$: rather than assuming a distinction between "actions" and other events, we just say that the agent can guarantee that the actual world is drawn from the set of possible worlds in which it has an umbrella ($\{ur,us\}$), and it can guarantee that the actual world is drawn from the set of possible worlds in which it doesn't have an umbrella ($\{nr,ns\}$).

Next, let's modify the example to let the agent see whether or not it is raining before choosing whether or not to carry an umbrella. The Cartesian frame will now look like this:

$C_2=\begin{array}{cc}& \begin{array}{cc}r& s\end{array}\\ \begin{array}{c}u\\ n\\ u\leftrightarrow r\\ u\leftrightarrow s\end{array}& \left(\begin{array}{cc}ur& us\\ nr& ns\\ ur& ns\\ nr& us\end{array}\right)\end{array}$.

The agent is now larger, as there are two new possibilities: it can carry the umbrella if and only if it rains, or it can carry the umbrella if and only if it is sunny. $\text{Ctrl}\left(C_2\right)$ will also be larger than $\text{Ctrl}\left(C_1\right)$. $\text{Ctrl}\left(C_2\right)=\left\{\right\{ur,us\},\{nr,ns\},\{ur,ns\},\{nr,us\left\}\right\}$.

Under one interpretation, the new options $u\leftrightarrow r$ and $u\leftrightarrow s$ feel different from the old ones $u$ and $n$. It feels like the agent's basic options are to either carry an umbrella or not, and the new options are just incorporating $u$ and $n$ into more complicated policies.

However, we could instead view the agent's "basic options" as a choice between "I want my umbrella-carrying to match when it rains" and "I want my umbrella-carrying to match when it's sunny." This makes $u$ and $n$ feel like the conditional policies, while $u\leftrightarrow r$ and $u\leftrightarrow s$ feel like the more basic outputs. Part of the point of the Cartesian frame framework is that we are not privileging either interpretation.

Consider now a third example, where there is a third possible environment, $m$, for meteor. In this case, a meteor hits the earth before the agent is even born, and there isn't a question about whether the agent has an umbrella. There is a new possible world, which we will also call $m$, in which the meteor strikes. The Cartesian frame will look like this:

$C_3=\begin{array}{cc}& \begin{array}{ccc}r& s& m\end{array}\\ \begin{array}{c}u\\ n\\ u\leftrightarrow r\\ u\leftrightarrow s\end{array}& \left(\begin{array}{ccc}ur& us& m\\ nr& ns& m\\ ur& ns& m\\ nr& us& m\end{array}\right)\end{array}$.

$\text{Ensure}\left(C_3\right)=⟨\{ur,us,m\},\{nr,ns,m\},\{ur,ns,m\},\{nr,us,m\}{⟩}_{\supset }$, and  $\text{Prevent}\left(C_3\right)=⟨\{ur,us\},\{nr,ns\},\{ur,ns\},\{nr,us\}{⟩}_{\subset }$. As a consequence, $\text{Ctrl}\left(C_3\right)=\left\{\right\}$.

This example illustrates that nontrivial agents may be unable to control the world's state. Because the agent can't prevent the meteor, the agent in this case has no controllables.

This example also illustrates that agents may be able to ensure or prevent some things, even if there are possible worlds in which the agent was never born. While the agent of $C_3$ cannot ensure that it exists, the agent can ensure that if there is no meteor, then it carries an umbrella ($\{ur,us,m\}$).

If we wanted to, we could instead consider the agent's ensurables (or its ensurables and preventables) its "outputs." This lets us avoid the counter-intuitive result that agents have no outputs in worlds where their existence is contingent.

I put the emphasis on controllables because they have other nice features; and as we'll see later, there is an operation called "assume" which we can use to say: "The agent, under the assumption that there's no meteor, has controllables."

 

4. Observables

The analogue of inputs in the Cartesian frame model is observables. Observables can be thought of as a closure property on the agent. If an agent is able to observe $S$, then the agent can take policies that have different effects depending on $S$.

Formally, let $S$ be a subset of $W$. We say that the agent of a Cartesian frame $C=(A,E,\cdot )$ is able to observe whether $S$ if for every pair $a_0,a_1\in A$, there exists a single element $a\in A$ which implements the conditional policy that copies $a_0$ in possible worlds in $S$ (i.e., for every $e\in E$, if $a\cdot e\in S$, then $a\cdot e=a_0\cdot e$) and copies $a_1$ in possible worlds outside of $S$.

When $a$ implements the conditional policy "if $S$ then do $a_0$, and if not $S$ then do $a_1$" in this way, we will say that $a$ is in the set $\text{if}(S,a_0,a_1)$.

Definition: Given $C=(A,E,\cdot )$, a Cartesian frame over $W$, $S$ a subset of $W$, and $a_0,a_1\in A$, let $\text{if}(S,a_0,a_1)$ denote the set of all $a\in A$ such that for all $e\in E$, $(a\cdot e\in S)\to (a\cdot e=a_0\cdot e)$ and$(a\cdot e\notin S)\to (a\cdot e=a_1\cdot e)$.

Agents in this setting observe events, which are true or false, not variables in full generality. We will say that $C$'s observables, $\text{Obs}\left(C\right)$, are the set of all $S$ such that  $C$'s agent can observe whether $S$.

Definition: $\text{Obs}\left(C\right)=\{S\subseteq W|\forall a_0,a_1\in A,\exists a\in A,a\in \text{if}(S,a_0,a_1\left)\right\}$.

Another option for talking about what the agent can observe would be to talk about when $C$'s agent can distinguish between two disjoint subsets $S$ and $T$. Here, we would say that the agent of $C=(A,E,\cdot )$ can distinguish between $S$ and $T$ if for all $a_0,a_1\in A$, there exists an $a\in A$ such that for all $e\in E$, either $a\cdot e=a_0\cdot e$ or $a\cdot e=a_1\cdot e$, and whenever $a\cdot e\in S$, $a\cdot e=a_0\cdot e$, and whenever $a\cdot e\in T$, $a\cdot e=a_1\cdot e$. This more general definition would treat our observables as the special case $T=W\setminus S$. Perhaps at some point we will want to use this more general notion, but in this sequence, we will stick with the simpler version.

 

4.1. Closure Properties

Claim: Observability is closed under Boolean combinations, so if $S,T\in \text{Obs}\left(C\right)$ then $W\setminus S$, $S\cup T$, and $S\cap T$ are also in $\text{Obs}\left(C\right)$.

Proof: Assume $S,T\in \text{Obs}\left(C\right)$. We can see easily that $W\setminus S\in \text{Obs}\left(C\right)$ by swapping $a_0$ and $a_1$. It suffices to show that $S\cup T\in \text{Obs}\left(C\right)$, since an intersection can be constructed with complements and union.

Given $a_0$ and $a_1$, since $S\in \text{Obs}\left(C\right)$, there exists an $a_2\in A$ such that for all $e\in E$, we have $a_2\in \text{if}(S,a_0,a_1)$. Then, since $T\in \text{Obs}\left(C\right)$, there exists an $a_3\in A$ such that for all $e\in E$, we have $a_3\in \text{if}(T,a_0,a_2)$. Unpacking and combining these, we get for all $e\in E$, $a_3\in \text{if}(S\cup T,a_0,a_1)$. Since we could construct such an $a_3$ from an arbitrary $a_0,a_1\in A$, we know that $S\cup T\in \text{Obs}\left(C\right)$. $\square$

This highlights a key difference between our version of "inputs" and the standard version. Agent models typically draw a strong distinction between the agent's immediate sensory data, and other things the agent might know. Observables, on the other hand, include all of the information that logically follows from the agent's observations.

Similarly, agent models typically draw a strong distinction between the agent's immediate motor outputs, and everything else the agent can control. In contrast, if an agent can ensure an event $S$, it can also ensure everything that logically follows from $S$.

Since $\text{Obs}\left(C\right)$ will often be large, we will sometimes write it using a minimal set of generators under union. Since $\text{Obs}\left(C\right)$ is closed under Boolean combinations, such a minimal set of generators will be a partition of $W$ (assuming $W$ is finite).

Definition: Let $⟨S_1,\dots ,S_n{⟩}_{\cup }$ denote the the closure of $\{S_1,\dots ,S_n\}$ under union (including $\left\{\right\}$, the empty union).

Just like what's controllable, what's observable is closed under removing possible environments.

Claim: If $E^{\prime }\subseteq E$, and if for all $a\in A$ and $e\in E^{\prime }$ we have $a\star e=a\cdot e$, then $\text{Obs}(A,E^{\prime },\star )\supseteq \text{Obs}(A,E,\cdot )$.

Proof: Trivial. $\square$

It is interesting to note, however, that what's observable is not closed under adding possible agents to $A$.

 

4.2. Examples of Observables

Let's look back at our three examples from earlier. The first example, $C_1$, looked like this:

$C_1=\begin{array}{cc}& \begin{array}{cc}r& s\end{array}\\ \begin{array}{c}u\\ n\end{array}& \left(\begin{array}{cc}ur& us\\ nr& ns\end{array}\right)\end{array}$.

$\text{Obs}\left(C_1\right)=⟨W{⟩}_{\cup }=\left\{\right\{\},W\}$. This is the smallest set of observables possible. The agent can act, but it can't change its behavior based on knowledge about the world.

The second example looked like:

$C_2=\begin{array}{cc}& \begin{array}{cc}r& s\end{array}\\ \begin{array}{c}u\\ n\\ u\leftrightarrow r\\ u\leftrightarrow s\end{array}& \left(\begin{array}{cc}ur& us\\ nr& ns\\ ur& ns\\ nr& us\end{array}\right)\end{array}$.

Here, $\text{Obs}\left(C_2\right)=⟨\{ur,nr\},\{us,ns\}{⟩}_{\cup }=\left\{\right\{\},\{ur,nr\},\{us,ns\},W\}$. The agent can observe whether or not it's raining. One can verify that for any pair of rows, there is a third row (possibly equal to one or both of the first two) that equals the first if it is $ur$ or $nr$, and equals the second otherwise.

The third example looked like:

$C_3=\begin{array}{cc}& \begin{array}{ccc}r& s& m\end{array}\\ \begin{array}{c}u\\ n\\ u\leftrightarrow r\\ u\leftrightarrow s\end{array}& \left(\begin{array}{ccc}ur& us& m\\ nr& ns& m\\ ur& ns& m\\ nr& us& m\end{array}\right)\end{array}$.

Here, $\text{Obs}\left(C_3\right)=⟨\{ur,nr\},\{us,ns\},\left\{m\right\}{⟩}_{\cup }$, which is

$$\left\{\right\{\},\{ur,nr\},\{us,ns\},\{m\},\{ur,nr,us,ns\},\{ur,nr,m\},\{us,ns,m\},W\}.$$

This example has an odd feature: the agent is said to be able to "observe" whether the meteor strikes, even though the agent is never instantiated in worlds in which it strikes. Since the agent has no control when the meteor strikes, the agent can vacuously implement conditional policies.

Let's look at two more examples. First, let's modify $C_1$ to represent the point of view of a powerless bystander:

$C_4=\begin{array}{cc}& \begin{array}{cccc}ur& nr& us& ns\end{array}\\ \begin{array}{c}1\end{array}& \left(\begin{array}{cccc}ur& nr& us& ns\end{array}\right)\end{array}$.

Here, the agent has no decisions, and everything is in the hands of the environment.

Alternatively, we can modify $C_1$ to represent the point of view of the agent from $C_1$ and environment from $C_1$ together. The resulting frame looks like this:

$C_5=\begin{array}{cc}& \begin{array}{c}1\end{array}\\ \begin{array}{c}ur\\ nr\\ us\\ ns\end{array}& \left(\begin{array}{c}ur\\ nr\\ us\\ ns\end{array}\right)\end{array}$.

$\text{Ensure}\left(C_4\right)=⟨W{⟩}_{\supset }$ and $\text{Prevent}\left(C_4\right)=⟨\left\{\right\}{⟩}_{\subset }$, so $\text{Ctrl}\left(C_4\right)=\left\{\right\}$. Meanwhile, $\text{Obs}\left(C_4\right)=⟨\left\{ur\right\},\left\{nr\right\},\left\{us\right\},\left\{ns\right\}{⟩}_{\cup }$.

On the other hand, $\text{Obs}\left(C_5\right)=⟨W{⟩}_{\cup }$, $\text{Ensure}\left(C_5\right)$ and $\text{Prevent}\left(C_5\right)$ are the closure of $\left\{\right\{ur\},\{nr\},\{us\},\{ns\left\}\right\}$ under supersets and subsets respectively, and $\text{Ctrl}\left(C_5\right)=2^W\setminus \left\{\right\{\},W\}$.

In the first case, the agent's ability to observe the world is maximal and its ability to control the world is minimal; while in the second case, observability is minimal and controllability is maximal. An agent with full control over what happens will not be able to observe anything, while an agent that can observe everything can change nothing.

This is perhaps counter-intuitive. If $S\in \text{Obs}\left(C\right)$ meant "I can go look at something to check whether we're in an $S$ world," then one might look at $C_5$ and say: "This agent is all-powerful. It can do anything. Shouldn't we then think of it as all-seeing and all-knowing, rather than saying it 'can't observe anything'?" Similarly, one might look at $C_4$ and say: "This agent's choices can't change the world at all. But then it seems bizarre to say that everything is 'observable' to the agent. Shouldn't we rather say that this agent is powerless and blind?"

The short answer is that, when working with Cartesian frames, we are in a very "What choices can you make?" paradigm, and in that kind of paradigm, the thing closest to an "input" is "What can I condition my choices on?" (Which is a closure property on the agent, rather than a discrete action like "turning on the Weather Channel.")

In that context, an agent with only one option automatically has maximal "inputs" or "knowledge," since it can vacuously implement every conditional policy. At the same time, an agent with too many options can't have any "inputs," since it could then use its high level of control to diagonalize against the observables it is conditioning on and make them false.

 

5. Controllables and Observables Are Disjoint

A maximally observable frame has minimal controllables, and vice versa. This turns out to be a special case of our first interesting result about Cartesian frames: an agent can't observe what it controls, and can't control what it observes.

To see this, first consider the following frame:

$C_6=\begin{array}{cc}& \begin{array}{c}1\end{array}\\ \begin{array}{c}{a}_0\\ a_1\end{array}& \left(\begin{array}{c}{w}_0\\ w_1\end{array}\right)\end{array}$.

Here, if $a\in \text{if}\left(\right\{w_1\},a_0,a_1)$, then $a\cdot 1$ would not be able to be either $w_0$ or $w_1$. If it were $w_1$, then it would have to copy $a_0$, and $a_0\cdot 1=w_0$. But if it were $w_0$, then it would have to copy $a_1$, and $a_1\cdot 1=w_1$. So $\text{if}(S,a_0,a_1)$ is empty in this case.

Notice that in this example, $\text{if}(S,a_0,a_1)$ isn't empty merely because our $A$ lacks the right $a$ to implement the conditional policy. Rather, the conditional policy is impossible to implement even in principle.

Fortunately, before checking whether $C$'s agent can observe $S$, we can perform a simpler check to rule out these problematic cases. It turns out that if $S\in \text{Obs}\left(C\right)$, then every column in $C$ consists either entirely of elements of $S$ or entirely of elements outside of $S$. (This is a necessary condition for being observable, not a sufficient one.)

Definition: Given a Cartesian frame $C=(A,E,\cdot )$ over $W$, and a subset $S$ of $W$, let $E_S$ denote the subset $\{e\in E|\forall a\in A,e\cdot a\in S\}$.

Lemma: If $S\in \text{Obs}\left(\right(A,E,\cdot \left)\right)$, then for all $e\in E$, it is either the case that $e\in E_S$ or $e\in E_{W\setminus S}$.

Proof: Take $S\in \text{Obs}\left(\right(A,E,\cdot \left)\right)$, and assume for contradiction that there exists an $e\in E$ in neither $E_S$ nor $E_{W\setminus S}$. Thus, there exists an $a_0\in A$ such that $a_0\cdot e\notin S$ and an $a_1\in A$ such that $a_1\cdot e\in S$. Since $S\in \text{Obs}\left(\right(A,E,\cdot \left)\right)$, there must exist an $a\in A$ such that $a\in \text{if}(S,a_0,a_1)$. Consider whether or not $a\cdot e\in S$. If $a\cdot e\in S$, then $a\cdot e=a_0\cdot e\notin S$. However, if $a\cdot e\notin S$, then $a\cdot e=a_1\cdot e\in S$. Either way, this is a contradiction. $\square$

This lemma immediately gives us the following theorem showing that in nontrivial Cartesian frames, observables and controllables are disjoint.

Theorem: Let $C$ be a Cartesian frame over $W$, with $\text{Env}\left(C\right)$ nonempty. Then,$\text{Ctrl}\left(C\right)\cap \text{Obs}\left(C\right)=\left\{\right\}$.

Proof: Let $e\in \text{Env}\left(C\right)$, and suppose for contradiction that $S\in \text{Ctrl}\left(C\right)\cap \text{Obs}\left(C\right)$. Since $S\in \text{Prevent}\left(C\right)$, there exists an $a_0\in A$ such that $a_0\cdot e\notin S$. Since $S\in \text{Ensure}\left(C\right)$, there exists an $a_1\in A$ such that $a_1\cdot e\in S$. This contradicts our lemma above. $\square$

 

5.1. Properties That Are Both Observable and Ensurable Are Inevitable

We also have a one-sided result showing that if $S$ is both observable and ensurable in $C$, then $S$ must be inevitable — i.e., the entire matrix must be contained in $S$.

We'll first define a Cartesian frame's image, which is the subset of $W$ containing every possible world that is actually hit by the evaluation function — the set of worlds that show up in the matrix.

Definition: $\text{Image}\left(C\right)=\{w\in W|\exists a\in A,\exists e\in E\text{s.t.}a\cdot e=w\}$.

$\text{Image}\left(C\right)\subseteq S$ can be thought of as a degenerate form of either $S\in \text{Ensure}\left(C\right)$ or $S\in \text{Obs}\left(C\right)$, where in the first case, the agent must make it the case that $S$, and in the second case the agent can do conditional policies because the $a\cdot e\notin S$ condition is never realized.¹ [LW(p) · GW(p)] Conversely, if an agent can both observe and ensure $S$, then the observability and the ensurability must both be degenerate.

Theorem: $S\in \text{Ensure}\left(C\right)\cap \text{Obs}\left(C\right)$ if and only if $\text{Image}\left(C\right)\subseteq S$ and $\text{Agent}\left(C\right)$ is nonempty.

Proof: Let $C=(A,E,\cdot )$ be a Cartesian frame over $W$. First, if $\text{Image}\left(C\right)\subseteq S$, then $S\in \text{Obs}\left(C\right)$, since $a_0\in \text{if}(S,a_0,a_1)$ for all $a_0,a_1\in A$. If $A$ is also nonempty, then $S\in \text{Ensure}\left(C\right)$, there exists an $a\in A$, and for all $e\in E$, $a\cdot e\in S$.

Conversely, if $A$ is empty, $\text{Ensure}\left(C\right)$ is empty, so $S\notin \text{Ensure}\left(C\right)\cap \text{Obs}\left(C\right)$. If $\text{Image}\left(C\right)⊈S$ , then there exist $a_0\in A$ and $e\in E$ such that $a_0\cdot e\notin S$. Then $S\notin \text{Ensure}\left(C\right)\cap \text{Obs}\left(C\right)$, since if $S\in \text{Ensure}\left(C\right)$, there exists an $a_1$ such that in particular $a_1\cdot e\in S$, so $e$ is in neither $E_S$ nor $E_{W\setminus S}$, which implies $S\notin \text{Obs}\left(C\right)$. $\square$

Corollary: If $\text{Agent}\left(C\right)$ is nonempty, $\text{Ensure}\left(C\right)\cap \text{Obs}\left(C\right)=⟨\text{Image}\left(C\right){⟩}_{\supset }$.

Proof: Trivial. $\square$

 

5.2. Controllables and Observables in Degenerate Frames

All of the results so far have shown that an agent's observables and controllables cannot simultaneously be too large. We also have some results that in some extreme cases, $\text{Obs}\left(C\right)$ and $\text{Ctrl}\left(C\right)$ cannot be too small. In particular, if there are few possible agents, observables must be large, and if there are few possible environments, controllables must be large.

Claim: If $|\text{Agent}\left(C\right)|\le 1$, $\text{Obs}\left(C\right)=2^W$.

Proof: If $\text{Agent}\left(C\right)$ is empty, $S\in \text{Obs}\left(C\right)$ for all $S\subseteq W$ vacuously. If $\text{Agent}\left(C\right)=\left\{a\right\}$ is a singleton, then $S\in \text{Obs}\left(C\right)$ for all $S\subseteq W$, because $a\in \text{if}(S,a,a)$. $\square$

Claim: If $\text{Agent}\left(C\right)$ is nonempty and $\text{Env}\left(C\right)$ is empty, then $\text{Ctrl}\left(C\right)=\text{Ensure}\left(C\right)=2^W$. If $\text{Agent}\left(C\right)$ is nonempty and $\text{Env}\left(C\right)$ is a singleton, $\text{Ensure}\left(C\right)=\{S\subseteq W|S\cap \text{Image}(C)\ne \{\left\}\right\}$ and $\text{Ctrl}\left(C\right)=\{S\subseteq W|S\cap \text{Image}(C)\ne \{\},W\setminus S\cap \text{Image}(C)\ne \{\left\}\right\}$.

Proof: If $\text{Agent}\left(C\right)$ is nonempty and $\text{Env}\left(C\right)$ is empty, $S\in \text{Ensure}\left(C\right)$ for all $S\subseteq W$ vacuously.

If $\text{Agent}\left(C\right)$ is nonempty and $\text{Env}\left(C\right)=\left\{e\right\}$ is a singleton, every $S\subseteq W$ that intersects $\text{Image}\left(C\right)$ nontrivially is in $\text{Ensure}\left(C\right)$, since if $w\in S\cap \text{Image}\left(C\right)$, there must be some $a\in A$ such that $a\cdot e=w$, this $a$ satisfies $a\cdot e^{\prime }\in S$ for all $e^{\prime }\in E$. Conversely, if $S$ and $\text{Image}\left(C\right)$ are disjoint, no $a\in A$ can satisfy this property. The result for $\text{Ctrl}$ then follows trivially from the result for $\text{Ensure}$. $\square$

 

5.3. A Suggestion of Time

Cartesian frames as we've been discussing them are agnostic about time. Possible agents, environments, and worlds could represent snapshots of a particular moment in time, or they could represent lengthy processes.

The fact that an agent's controllables and observables are disjoint, however, suggests a sort of arrow of time, where facts an agent can observe must be “before” the facts that agent has control over. This hints that we may be able to use Cartesian frames to formally represent temporal relationships.

One reason it would be nice to represent time is that we could model agents that repeatedly learn things, expanding their set of observables. Suppose that in some frame $C,$ $\text{Agent}\left(C\right)$ includes choices the agent makes over an entire calendar year. $\text{Agent}\left(C\right)$'s observables would only include the facts the agent can condition on at the start of the year, when it's first able to act; we haven't defined a way to formally represent the agent learning new facts over the course of the year.

It turns out that this additional temporal structure can be elegantly expressed using Cartesian frames. We will return to this topic in the very last post in this sequence. For now, however, we only have this hint that particular Cartesian frames have something like a "before" and "after."

 

6. Why Cartesian Frames?

The goal of this sequence will be to set up the language for talking about problems using Cartesian frames.

Concretely, I'm writing this sequence because:

• I've recently found that I have a new perspective to bring to a lot of other MIRI researchers' work. This perspective seems to me to be captured in the mathematical structure of Cartesian frames, but it's the new perspective rather than the mathematical structure per se that seems important to me. I want to try sharing this mathematical object and the accompanying philosophical interpretation, to see if it successfully communicates the perspective.
• I want collaborators to work with on Cartesian frames. If you're a math person who finds the things in this sequence exciting, I'd be interested in talking about it more. You can comment, PM, or email me.
• I want help with paradigm-building, but I also want there to be an ecosystem where people do normal science within this paradigm. I would consider it a good outcome if there existed a decent-sized group of people on the AI Alignment Forum and LessWrong for whom it makes just as much sense to pull out the Cartesian frames paradigm as it makes to pull out the cybernetic agent paradigm.

Below, I will say more about the cybernetic agent model and other ideas that helped motivate Cartesian frames, and I will provide an overview of upcoming posts in the  sequence.

 

6.1. Cybernetic Agent Model

The cybernetic agent model describes an agent and an environment interacting over time:

In "Embedded Agency [? · GW]," Abram Demski and I noted that cybernetic agents like Marcus Hutter's AIXI are dualistic, whereas real-world agents will be embedded in their environment. Like a Cartesian soul, AIXI is crisply separated from its environment.

The dualistic model is often useful, but it's clearly a simplification that works better in some contexts than in others. One thing it would be nice to have is a way to capture the useful things about this simplification, while treating it as a high-level approximation with known limitations — rather than treating it as ground truth.

Cartesian frames carve up the world into a separate "agent" and "environment," and thereby adopt the basic conceit of dualistic Hutter-style agents. However, they treat this as a "frame" imposed on a more embedded, naturalistic world.² [LW(p) · GW(p)]

Cartesian frames serve the same sort of intellectual function as the cybernetic agent model, and are intended to supersede this model. Our hope is that a less discrete version of ideas like "agent," "action," and "observation" will be better able to tolerate edge cases. E.g., we want to be able to model weirder, loopier versions of “inputs” that operate across multiple levels of description.

We will also devote special attention in this sequence to subagents, which are very difficult to represent in traditional dualistic models. In game theory, for example, we carve the world into different "agent" and "non-agent" parts, but we can't represent nontrivial agents that intersect other agents. A large part of the theory in this sequence will be giving us a language for talking about subagents.

 

6.2. Deriving Functional Structure

Another way of summarizing this sequence is that we'll be applying reasoning like Pearl's to objects like game theory's, with a motivation like Hutter's.

In Judea Pearl's causal models [LW · GW], you are given a bunch of variables, and an enormous joint distribution over the variables. The joint distribution is a large object that has a relational structure as opposed to a functional structure.

You then deduce something that looks like time and causality out of the combinatorial properties of the joint distribution. This takes the form of causal diagrams, which give you functions and counterfactuals.

This has some similarities to how we'll be using Cartesian frames, even though the formal objects we'll be working with are very different from Pearl's. We want a model that can replace the cybernetic agent model with something more naturalistic, and our plan for doing this will involve deriving things like time from the combinatorial properties of possible worlds.

We can imagine the real world as an enormous static object, and we can imagine zooming in on different levels of the physical world and sometimes seeing things that look like local functions. ("Ah, no matter what the rest of the world looks like, I can compute the state of $Y$ from the state of $X$, relative to my uncertainty.") Switching which part of the world we're looking at, or switching which things we're lumping together versus splitting, can then change which things look like functions.

Agency itself, as we normally think about it, is functional in this way: there are multiple "possible" inputs, and whichever "option" we pick yields a deterministic result.

We want an approach to agency that treats this functional behavior less like a unique or fundamental feature of the world, and more like a special case of the world's structure in general — and one that may depend on what we're splitting or lumping together.

"We want to apply Pearl-like methods to Cartesian frames" is also another way of saying "we want to do the formal equivalent of inferring extensive-form games from normal-form games," our summary from before. The analogy is:

 

	base information	derived information
causality	joint probability distribution	causal diagram
games	normal-form game	extensive-form game
agency	Cartesian frame	control, observation, subagents, time, etc.

 

The game theory analogy is more relevant formally, while the Pearl analogy better explains why we're interested in this derivation.

Just as notions of time and information state are basic in causal diagrams and extensive-form games, so are they basic in the cybernetic agent model; and we want to make these aspects of the cybernetic agent model derived rather than basic, where it's possible to derive them. We also want to be able to represent things like subagents that are entirely missing from the cybernetic agent model.

Because we aren't treating high-level categories like "action" or "observation" as primitives, we can hope to end up with an agent model that will let us model more edge cases and odd states of the system. A more derived and decomposable notion of time, for example, might let us better handle settings where two agents are both trying to reach a decision based on their model of the other agent's future behavior.

We can also hope to distinguish features of agency that are more description-invariant from features that depend strongly on how we carve up the world.

One philosophical difference between our approach and Pearl's is that we will avoid the assumption that the space of possible worlds factors nicely into variables that are given to the agent. We want to instead just work with a space of possible worlds, and derive the variables for ourselves; or we may want to work in an ontology that lets us reason with multiple incompatible factorizations into variables.³ [LW(p) · GW(p)]

 

6.3. Contents

The rest of the sequence will cover these topics:

2. Additive Operations on Cartesian Frames [LW · GW] - We talk about the category of Chu spaces, and introduce two additive operations one can do on Cartesian frames: sum $\oplus$, and product $\&$. We talk about how to interpret these operations philosophically, in the context of agents making choices to affect the world. We also introduce the small Cartesian frame $0$, and its dual $0^{\ast }=\top$.

3. Biextensional Equivalence [LW · GW] - We define homotopy equivalence $\simeq$ for Cartesian frames, and introduce the small Cartesian frames $\text{null}$, $1_S$, and ${\perp }_S$.

4. Controllables and Observables, Revisited [LW · GW] - We use our new language to redefine controllables and observables.

5. Functors and Coarse Worlds [LW · GW] - We show how to compare frames over a detailed world model $W$ and frames over a coarse version of that world model $V$. We demonstrate that observability is a function not only of the observer and the observed, but of the level of description of the world.

6. Subagents of Cartesian Frames - We introduce the notion of a frame $C$ whose agent is the subagent of a frame $D$, written $C◃D$. A subagent is an agent playing a game whose stakes are another agent's possible choices. This notion turns out to yield elegant descriptions of a variety of properties of agents.

7. Multiplicative Operations on Cartesian Frames - We introduce three new binary operations on Cartesian frames: tensor $\otimes$, par $⅋$, and lollipop $⊸$.

8. Sub-Sums and Sub-Tensors - We discuss spurious environments, and introduce variants of sum, $⊞$, and tensor, $⊠$, that can remove some (but not too many) spurious environments.

9. Additive and Multiplicative Subagents - We discuss the difference between additive subagents, which are like future versions of the agent after making some commitment; and multiplicative subagents, which are like agents acting within a larger agent.

10. Committing, Assuming, Externalizing, and Internalizing - We discuss the additive notion of producing subagents and sub-environments by committing or assuming, and the multiplicative notion of externalizing (moving part of the agent into the environment) and internalizing (moving part of the environment into the agent).

11. Eight Definitions of Observability - We use our new tools to provide additional definitions and interpretations of observables. We talk philosophically about the difference between defining what's observable using product and defining what's observable using tensor, which corresponds to the difference between updateful and updateless observations.

12. Time in Cartesian Frames - We show how to formalize temporal relations with Cartesian frames.

I'll be releasing new posts most non-weekend days between now and November 11.

As Ben noted in his announcement post [LW · GW], I'll be giving talks and holding office hours this Sunday at 12-2pm PT and the following three Sundays at 2-4pm PT, to answer questions and discuss Cartesian frames. Everyone is welcome.

The online talks, covering much of the content of this sequence, will take place this Sunday at 12pm PT (Zoom link added: recording of the talk [LW · GW]) and next Sunday at 2pm PT.

 

This sequence is communicating ideas I have been developing slowly over the last year. Thus, I have gotten a lot of help from conversation with many people. Thanks to Alex Appel, Rob Bensinger, Tsvi Benson-Tilsen, Andrew Critch, Abram Demski, Sam Eisenstat, David Girardo, Evan Hubinger, Edward Kmett, Alexander Gietelink Oldenziel, Steve Rayhawk, Nate Soares, and many others.

---

Footnotes

1. This assumes a non-empty $\text{Agent}\left(C\right)$. Otherwise, $\text{Image}\left(C\right)$ could be empty and therefore a subset of $S$, even though $S$ is not ensurable (because you need an element of $\text{Agent}\left(C\right)$ in order to ensure anything). ↩ [LW · GW]

2. This is one reason for the name "Cartesian frames." Another reason for the name is to note the connection to Cartesian products. In linear algebra, a frame of an inner product space is a generalization of a basis of a vector space to sets that may be linearly dependent. With Cartesian frames, then, we have a Cartesian product that projects onto the world, not necessarily injectively. (Cartesian frames aren't actually "frames" in the linear-algebra sense, so this is only an analogy.) ↩ [LW · GW]

3. This, for example, might let us talk about a high-level description of a computation being "earlier" in some sort of logical time than the exact details of that same computation.

Problems like agent simulates predictor [LW · GW] make me think that we shouldn't treat the world as factorizing into a single "true" set of variables at all, though I won't attempt to justify that claim here. ↩ [LW · GW]

32 comments

Comments sorted by top scores.