Eight Definitions of Observability

post by Scott Garrabrant · 2020-11-10T23:37:07.827Z · LW · GW · 26 comments

Contents

  1. Definition from Subsets
    1.1. Example
  2. Conditional Policies Definition
    2.1. Example
  3. Additive Definitions
    3.1. Example
  4. Multiplicative Definitions
    4.1. Powerless Outside of a Subset
    4.2. Multiplicative Definitions of Observables
    4.3. Example
    4.4. Updatelessness
  5. Internalizing-Externalizing Definitions
    5.1. Example
None
26 comments

This is the eleventh post in the Cartesian frames [LW · GW] sequence. Here, we compare eight equivalent definitions of observables, which emphasize different philosophical interpretations.

Throughout this post, we let  be a Cartesian frame over a nonempty set , we let  be a finite partition of , and we let  send each element of  to its part in .

The condition that  is finite is an important one. Many of the definitions below can be extended to infinite partitions, and the theory of observability for infinite partitions is probably nice, but we are not discussing it here. The condition that  is nonempty is just ruling out some degenerate cases

 

1. Definition from Subsets

The definitions in this post will talk about when a finite partition  of  is observable in . This will make some of the definitions more elegant, and it is easy to translate back and forth between the new definitions of the observability of a finite partition and the old definitions of the observability of a subset. 

Definition: We say 's agent can observe a finite partition  of  if for all parts . We let  denote the set of all finite partitions of  that are observable in .

Claim: For any nonempty strict subset 's agent can observe  if and only if agent can observe .

Proof: If 's agent can observe , then clearly 's agent can observe . If agent can observe , then since observability is closed under complements, 's agent can observe , and so can observe 

 

1.1. Example

In "Introduction to Cartesian Frames [LW · GW]," we gave the example of an agent that can choose between unconditionally carrying an umbrella, unconditionally carrying no umbrella, carrying an umbrella iff it's raining, and carrying an umbrella iff it's sunny:

Here, , so the partition  is observable in , where  and .

As we go through the definitions in this post, we will repeatedly return to  and show how to understand 's observables in terms of our new definitions.

Before presenting fundamentally new definitions, we will modify our two old definitions to be about finite partitions instead of subsets.

 

2. Conditional Policies Definition

Definition: We say that 's agent can observe a finite partition  of  if for all functions , there exists an element  such that for all .

Claim: This definition is equivalent to the definition from subsets.

Proof: We work by induction on the number of parts in . Since  is nonempty,  has at least one part. If  has one part, we clearly have that 's agent can observe  under the definition from subsets. For the conditional policies definition, we also have that 's agent can observe , since we can take , and thus, for all ,

If  has  parts, consider the partition  which unions together the first two parts  and  of . Let  send each element of  to its part in .

First, assume that 's agent can observe  according to the definition from subsets. Then, since observability of subsets is closed under unions, 's agent can also observe  under the definition from subsets, and thus also under the conditional policies definition.

Given a function , let  be given by , and  on all other inputs. Since 's agent can observe  under the conditional policies definition, we can let  be such that for all .

Choose an  such that , which we can do because  is observable in . Observe that for all , we have that if , then

if , we have , and thus

and finally if  for some , we still have have , and thus

Thus, 's agent can observe  according to the conditional policies definition.

Conversely, if 's agent can observe  according to the conditional policies definition, then to show that 's agent can observe  according to the definition from subsets, it suffices to show that the agent can observe  for all . Thus, we need to show that for any , there exists an  with .

Indeed, if we let  send  to , and send all other inputs to , then we can take an  such that for all . But then, if , then

and otherwise,

Thus, 's agent can observe  according to the definition from subsets. 

 

2.1. Example

Let  be defined as in the §1.1 example, with , and  .

 is a four-element set, and  is a two-element set, so there are sixteen functions . For each function, there is a possible agent  that satisfies  for all . We can illustrate the sixteen functions and the corresponding  in a sixteen-row table:

Since there is an  for each function, 's agent can observe  according to the conditional policies definition.

 

3. Additive Definitions

Next, we give an additive definition of observables. This is a version of our categorical definition of observables from "Controllables and Observables, Revisited [LW · GW]," modified to be about finite partitions.

Definition: We say 's agent can observe a finite partition  of  if there exist , Cartesian frames over , with  such that .

This can also be strengthened to a constructive version of the additive definition, which we will call the assuming definition.

Definition: We say 's agent can observe a finite partition  of  if .

Claim: These definitions are equivalent to each other and the definitions above.

Proof: We assume that , and that  is nonempty. The case where  and the case where  are trivial.

If 's agent can observe  according to the assuming definition of observables, then it can also clearly observe  according to the additive definition, since 

Next, assume that 's agent can observe  according to the additive definition. We will show that 's agent can observe . Consider the pair of Cartesian frames  and . Observe that  and that , and that . Thus,  is observable in . Symmetrically,  is observable in  for all , and thus  is observable in  according to the definition from subsets.

Finally, assume that 's agent can observe  according to the conditional policies definition (and also the definition from subsets). We will show that , where .

We have , where , and  is given by , where .

First observe that for every , there is a unique  such that . This is because there exists an , and from the definition from subsets, 's agent can observe each , and so given an , if , it must be the case that for all  . Thus, we have that that .

We construct  and  which compose to something homotopic to the identity in each order. Let   be the diagonal, given by . Let  and  be the identity on . Let  be given by , where  is given by , and  satisfies  for all , which is possible by the conditional policies definition.

To see that  is a morphism, observe that for all  and ,

To see that  is a morphism, observe that for all , and , if we let  be given by , we have

where  is such that . The fact that  and  compose to something homotopic to the identity in both orders follows from the fact that  and  are the identity on . Thus, , and so  is observable in  according to the assuming definition. 

 

3.1. Example

Let  be defined as in the previous examples, with  and . By the assuming definition, there exist two frames

and

such that .

This example both illustrates the idea behind the additive definitions, and shows the construction used in the assuming definition. This is also the same example we provided to illustrate products of Cartesian frames in "Additive Operations on Cartesian Frames [LW · GW]."

Another way of thinking about the additive definition of observables: Recall "Committing, Assuming, Externalizing, and Internalizing" §3.2 (Committing and Assuming Can Be Defined Using Lollipop and Tensor [LW · GW]), where we saw that . This means that (up to isomorphism) we can restate   as , i.e.,

.

This (equivalent) framing makes it easier to keep track of what "assuming" is doing categorically, so that we can see what interfaces between frames we are relying on when we say that something is "observable" using an additive definition.

 

4. Multiplicative Definitions

Our multiplicative definitions will depend on a notion of agents being powerless outside of a subset.

 

4.1. Powerless Outside of a Subset

Definition: Given a subset  of , we say that 's agent is powerless outside  if for all , and all , if , then .

To say that 's agent is powerless outside  is to say that the if the world is at all dependent on 's agent, then the world must be in .

Here are some lemmas about being powerless outside of a subset, which we will use later.

Lemma: If 's agent is powerless outside  and , then 's agent is powerless outside .

Proof: Trivial. 

Lemma: If  and 's agents are both powerless outside , then 's agent is powerless outside .

Proof: Let , and let . Consider some  and . We will use the fact that if  then , and the fact that if  then . Observe that if , then

Now, we are ready for our first truly new definition of the observability of a finite partition.

 

4.2. Multiplicative Definitions of Observables

Definition: We say that 's agent can observe a finite partition  of  if , where each 's agent is powerless outside .

Again, we also have a constructive version of this definition:

Definition: We say that 's agent can observe a finite partition  of  if , where , where .

Claim: These definitions are equivalent to each other and equivalent to the definitions above.

Proof: First, observe that if 's agent can observe  according to the constructive version of the multiplicative definition, it can also observe  according to the nonconstructive version of the multiplicative definition, since the agent of  is clearly powerless outside .

Next, we show that if 's agent can observe  according to the nonconstructive multiplicative definition, it can also observe  according to the definition from subsets. Let , where each 's agent is powerless outside . It suffices to show that 's agent can observe , since the definition from subsets is equivalent to the additive definition, and thus closed under biextensional equivalence. Thus, it suffices to show that 's agent can observe  for all . We will show that 's agent can observe , and the rest will follows by symmetry. 

Let , and let . We start by showing that 's agent is powerless outside . We have that the agents of  are all powerless outside , since being powerless outside something is closed under supersets. Thus we have that 's agent is powerless outside , since being powerless outside  is closed under tensor.

Thus, we have , with 's agent powerless outside  and 's agent powerless outside . Given an arbitrary  , we will show that , and thus show that 's agent can observe .

It suffices to show that for all , if  , then , and if  , then . Indeed, if , then, since 's agent is powerless outside , we have

Similarly, if , then, since 's agent is powerless outside , we have

Thus, 's agent can observe , so 's agent can observe  according to the definition from subsets.

Finally, we assume that 's agent can observe  according to the assuming definition, and show that 's agent can observe  according to the constructive version of the multiplicative definition.

We work by induction on , the number of parts. The case where  is trivial. Let . Thus, we also have that , and so by induction, we have that , where  and  are as in the constructive multiplicative definition. Thus, it suffices to show that

First, observe that we have , where (C), , and . Let . Let .

Observe that , and , and observe that . Thus it suffices to show that .

Let , let , and let  where , and  are all given by  if  if , and  otherwise.

Let . Let ), where

Observe that for any , there is a , given by  and . This is clearly a morphism, since

Similarly, for any , there is a morphism  given by   and . Finally, for any , there is a morphism , given by , which is also clearly a morphism. 

We show that these are in fact all of the morphisms in . Indeed, let  be a morphism in , let  be an element of , and let  be an element of . Let

If , then , so given any ,

 , and so

Similarly, for any  and so .

If , then , and . Let . Given any 

, so

Given any ,

 , and so

Thus, .

Finally, if , we similarly have , where .

We construct a pair of morphisms

and

by letting  and  be the identity on , letting  be given by  as above. Since we have shown that  is surjective, we let  be any right inverse to . It is easy to show that both of these are morphisms by the construction of , and they compose to something homotopic to the identity in both orders since  and  are the identity of .

Thus , so 's agent can observe  according to the constructive multiplicative definition, completing the proof. 

You may have noticed that the last part of the proof would have been much simpler if  distributed over , but  does not in general distribute over . ( distributes over  and  distributes over .)

In this case, however,  does distribute over . I do not plan on going over it now, but there is actually an interesting relationship between observables and cases where  distributes over .

 

4.3. Example

Let  be defined as in the previous examples, with  and . Let , so that  and . By the multiplicative definitions of observables, there then exist two frames

and

such that .

Here,  is an agent that treats the "makes decisions when it's sunny" part of itself as though it were an external process. Similarly,  externalizes its ability to make decisions when it's rainy.

This example illustrates both multiplicative definitions, and also shows the construction used in the constructive multiplicative definition.

Appealing again to the fact that , we also have the option of restating  here as . In words, this says that  is (biextensionally equivalent to) a team consisting of:

  1. that very agent, picking an action after the environment either (a) gives it a promise it will rain or (b) makes it powerless and doesn't rain; and
  2. that very agent, picking an action after the environment either (a) gives it a promise it won't rain or (b) makes it powerless and rains.

 

4.4. Updatelessness

The relationship between observables' additive and multiplicative definitions is interesting. You can think of the additive definition as updateful, while the multiplicative definition is updateless.

The  in the additive definition are basically given a promise that the world will end up in . The  in the multiplicative definition, however, are instead given a promise that their choices have no effect on worlds outside of .

I think the updateless factorization is better, and thus prefer the multiplicative definition in spite of the fact that it is more complicated. 

When an updateless agent observes something, it becomes the version of itself that only affects the worlds in which it makes that observation. When an updateful agent observes something, we assume that all the worlds in which it does not make that observation do not exist. The fact that the additive and multiplicative definitions above are equivalent illustrates the equivalence of the updateful and updateless views in the simple cases where there is true observation. However, they diverge as soon as you want to try to approximate observation. The updateless view approximates better, as it makes sense to think of a subagent that has only a very small effect on worlds in which it does not make the observation that it makes.

Also, note that the  in the additive definition are not subagents of , but they are additive sub-environments. The  in the multiplicative definition are multiplicative subagents of .

 

5. Internalizing-Externalizing Definitions

Next, we have the nonconstructive internalizing-externalizing definition of observables.

Definition: We say that 's agent can observe a finite partition  of  if either  or  is biextensionally equivalent to something in the image of .

Again, we have a constructive version of this definition.

Definition: We say that 's agent can observe a finite partition  of  if either  or .

Claim: These definitions are equivalent to each other and to the definitions above.

Proof: The case where  is trivial, so we assume that  is nonempty. Clearly if 's agent can observe  under the constructive internalizing-externalizing definition, then  is also observable in  under the non-constructive version.

Next, assume that  is in the image of  (up to biextensional equivalence). Recall that the image of  up to biextensional equivalence is exactly those Cartesian frames  such then  is nonempty and for all  and  we have . Thus,  , where  is of this form. Let  send each element  to the unique  such that  for all , and let  be the image of . Then, , where , and 

Let , and let . Then, we clearly have that , where . But this is clearly isomorphic to , where , where . Thus, 's agent can observe  according to the nonconstructive additive definition of observables.

Finally, we assume that 's agent can observe  according to the nonconstructive additive definition of observables, and we show that 's agent can observe  according to the constructive internalizing-externalizing definition. Let , where . Let , and without loss of generality, let , where  and .

First, we show that . Let . Observe that (since  is nonempty), , where , where 

We construct

and

as follows. Let . Let , where , and  is chosen arbitrarily for . Let , and , where . Clearly,  and  are inverses.

To see that  is a morphism, observe that for all  and , we have

where .

To see that  is a morphism, observe that for all , and for all , we have

It is clear that  and  are both homotopic to the identity, since  and  are both the identity.

Now, we have that , and so we also have dually that . Thus, 

The thing that is going on here is that when  internalizes , the agent of  then has the full ability to choose how  goes (among ways of  going that were possible in ).  might have other choices than just choosing how  goes. If it does, then it can freely entangle those other choices with the choice of  however it wants.

When  then externalizes , it loses all control over . However, it preserves the ability to entangle all of its other choices with the way that  goes. This ability for the agent to entangle its choices with  is exactly what it means to say " is observable."

 

5.1. Example

Let  be defined as in the previous examples, with . By the internalizing-externalizing definitions, there exists a frame

,

which is biextensionally equivalent to

.

We then have that

,

which is isomorphic to .

This example illustrates both internalizing-externalizing definitions, and also shows the construction used in the constructive definition.

 

In our next post, we'll conclude the sequence by showing how to formalize agents that learn and act over time using Cartesian frames.

26 comments

Comments sorted by top scores.

comment by Ramana Kumar (ramana-kumar) · 2021-02-05T09:55:33.395Z · LW(p) · GW(p)

How is this supposed to work (focusing on the  claim specifically)?

and so

Thus, .

Earlier,  was defined as follows:

given by  and 

but there is no reason to suppose  above.

Replies from: rohinmshah
comment by Rohin Shah (rohinmshah) · 2021-02-10T17:04:24.876Z · LW(p) · GW(p)

The problem is a bit earlier actually:

This isn't true, because  doesn't just ignore  here (since ). I think the route is to say "Let  . Then  must treat  and  identically, meaning that either they are equal, or the frame is biextensionally equivalent to one where they are equal."

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-02-11T08:25:29.721Z · LW(p) · GW(p)

Using the idea we talked about offline, I was able to fix the proof - thanks Rohin!
Summary of the fix:
When  and  are defined, additionally assume they are biextensional (take their biextensional collapse), which is fine since we are trying to prove a biextensional equivalence. (By the way this is why we can't take , since we might have  after biextensional collapse.) Then to prove , observe that for all  which means , hence  since a biextensional frame has no duplicate columns.

comment by Ramana Kumar (ramana-kumar) · 2021-01-29T19:23:42.718Z · LW(p) · GW(p)

this is clearly isomorphic to , where , where . Thus, 's agent can observe  according to the nonconstructive additive definition of observables.

I think this is only true if  partitions , or, equivalently, if  is surjective. This isn't shown in the proof. Is it supposed to be obvious?

EDIT: may be able to fix this by assigning any  that is not in  to the frame  so it is harmless in the product of s -- I will try this.

 

comment by Ramana Kumar (ramana-kumar) · 2021-01-26T18:53:34.223Z · LW(p) · GW(p)

and observe that 

This cannot be true. I can prove in general  whenever  by observing that the agent cardinalities on each side differ.

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-01-27T08:09:31.556Z · LW(p) · GW(p)

Yep, changed it to .

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-01-28T12:40:18.696Z · LW(p) · GW(p)

I haven't yet figured out why it's true under  - I'll keep trying, but let me know if there's a quick argument for why this holds. (Default next step for me would be to see if I can restrict attention to the world  then do something similar to my other comment [LW(p) · GW(p)].)

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-01-28T23:24:01.157Z · LW(p) · GW(p)

I am confused, why is it not identical to your other comment?

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-01-29T08:26:06.384Z · LW(p) · GW(p)

Because  and  are not a partition of the world here.

EDIT: but what we actually need in the proof is  where the  do result in a partition, so I think this will work out the same as the other comment. I'm still not convinced about biextensional equivalence between the frames without the rest of the product.

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-01-29T10:52:33.342Z · LW(p) · GW(p)

And it seems we do actually need  in the proof to justify:

Thus it suffices to show that .

Without it, we have to show  instead.

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-01-30T00:12:52.641Z · LW(p) · GW(p)

UPDATE: I was able to prove  in general whenever  and  are disjoint and both in , with help from Rohin Shah, following the "restrict attention to world " approach I hinted at earlier.
 

comment by Ramana Kumar (ramana-kumar) · 2021-01-26T18:22:36.405Z · LW(p) · GW(p)

where (C), 

Presumably two of those indices should be 

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-01-27T08:10:59.596Z · LW(p) · GW(p)

Fixed, thanks.

comment by Ramana Kumar (ramana-kumar) · 2021-01-26T14:19:37.813Z · LW(p) · GW(p)

Let . Thus, we also have that 

I'm not seeing why this follows. I'll look for a counterexample, but in the meantime maybe there's a simple explanation for why we can combine the product of two assumes as an assume of the union? (I think the only relevant assumption in this context is that the s partition the world; but I might be missing some other important assumption.)

EDIT: I can see how maybe this will follow from the definition of observability of a partition from subsets (which we are also assuming) and the fact that  is closed under union... will try to figure that out. -- Yep I think this works out. Sorry for the confusion.

comment by Ramana Kumar (ramana-kumar) · 2021-01-26T10:44:59.899Z · LW(p) · GW(p)

Let , and let 

Is  supposed to be  here, rather than including ?

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-01-27T08:13:27.442Z · LW(p) · GW(p)

Fixed, thanks.

comment by Ramana Kumar (ramana-kumar) · 2021-01-24T15:50:51.452Z · LW(p) · GW(p)

Next, assume that 's agent can observe  according to the additive definition. We will show that 's agent can observe .

I might be misunderstanding this, but the proof suggests you're actually assuming the assuming definition here, not the additive definition. In which case we may be missing the proof of implication of any of the other definitions from the additive definition.

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-01-27T08:46:37.001Z · LW(p) · GW(p)

I think I fixed it. Thanks.

comment by Ramana Kumar (ramana-kumar) · 2021-01-24T08:11:29.386Z · LW(p) · GW(p)

Definition: We say that 's agent can observe a finite partition  of  if for all functions , there exists an element  such that for all .

Claim: This definition is equivalent to the definition from subsets.

This doesn't hold in the degenerate case , since then we have an empty function  but no elements of . (But the definition from subsets holds trivially.)

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2021-01-27T08:27:45.524Z · LW(p) · GW(p)

This was annoying to fix, so I just made  nonempty in the intro to the post.

comment by adamShimi · 2020-11-11T19:51:48.497Z · LW(p) · GW(p)

This is the first post in the sequence that I fully read since the Introduction. So I'm not going to be able to say anything really useful about the proofs. Still, I was curious about the philosophical aspects of these definitions, so I read this post anyway.

That being said, I still think that I understood some part of the definitions, after checking terms from previous posts. My handwavy understanding of your definitions is

  • The definitions about subset and conditional policy just rephrase that an observable is something on which the agent can condition it's own policy. So the agent can observe the partition if it can condition policy on the set of the partition in which it finds itself.
  • The additive definitions say that that the agent can observe the partition if the cartesian frame can be decomposed into mutually exclusive cartesian frames, one for each set of the partition, in which the agent acts as if it is in a world of this set.
  • The multiplicative definitions say that the agent can observe the partition if the cartesian frame can be decomposed into a product of cartesian frames, one for each subset of the partition, such that the agent is unable to impact the world if it is outside its subset of the partition. The interpretation of the product is that there's a supervisor agent that control all agents at the same time, and so here, it controls all of them until the observation, after which he morally only controls the one in the observed set (because the other are powerless).
  • The internalizing-externalizing definitions say the agent can observe the partition if the cartesian frame can be decomposed into the composition of making the agent able to choose in which set of V it is, but then removing this choice from it, which amount to letting it condition on V, without actually giving it the power to do so.

Is there something really wrong here?

Also, I'm curious if you have an interpretation of the differences between internalizing-externalizing definitions and the others, just like your section on updatelessness compared additive and multiplicative definitions. (Really cool section philosophically, by the way!)

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2020-11-11T20:29:33.970Z · LW(p) · GW(p)

Seems right, except I don't use the word "product" for the multiplicative definition. 

I don't have much to say about the internalizing-externalizing definition philosophically. One thing to say is that I think the condition that  observes  is a weaker notion of observability, that might actually agree with philosophical intuition more, and the internalizing-externalizing definition might be easier to interpret if you are thinking in terms of this condition.

comment by Ramana Kumar (ramana-kumar) · 2021-01-30T09:21:39.636Z · LW(p) · GW(p)

Let 

nit:  should be  here

and let  be an element of .

and the second  should be . I think for these  and  to exist you might need to deal with the  case separately (as in Section 5). (Also couldn't you just use the same  twice?)

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-01-30T13:50:57.192Z · LW(p) · GW(p)

Indeed I think the  case may be the basis of a counterexample to the claim in 4.2. I can prove for any (finite)  with  that there is a finite partition  of  such that 's agent observes  according to the assuming definition but does not observe  according to the constructive multiplicative definition, if I take 

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-02-05T10:59:31.881Z · LW(p) · GW(p)

I presume the fix here will be to add an explicit  escape clause to the multiplicative definitions. I haven't been able to confirm this works out yet (trying to work around this [LW(p) · GW(p)]), but it at least removes the  counterexample.

Replies from: ramana-kumar
comment by Ramana Kumar (ramana-kumar) · 2021-02-11T08:29:17.053Z · LW(p) · GW(p)

With the other problem resolved, I can confirm that adding an  escape clause to the multiplicative definitions works out.