Proofs, Theorems 6-8, Propositions 2,3

post by Diffractor · 2021-12-03T18:46:18.937Z · LW · GW · 0 comments

Contents

No comments

Theorem 6: Causal IPOMDP's: Any infra-POMDP with transition kernel $K:S\times A\stackrel{ik}{\to }O\times S$ which fulfills the niceness conditions and always produces crisp infradistributions, and starting infradistribution $\psi \in \square S$, produces a causal belief function via $\Theta \left(\pi \right):=p{r}_{(A\times O{)}^{\omega }\ast }(\psi ⋉K_{:\infty }^{\pi })$.

So, first up, we can appeal to Theorem 4 on Pseudocausal IPOMDP's, to conclude that all the $K_{:\infty }^{\pi }$ are well-defined, and that this $\Theta$ we defined fulfills all belief function conditions except maybe normalization.

The only things to check are that the resulting $\Theta$ is normalized, and that the resulting $\Theta$ is causal. The second is far more difficult and makes up the bulk of the proof, so we'll just dispose of the first one.

T6.1 First, $K$, since it's crisp by assumption, always has $K(s,a)\left(c\right)=c$ for all constants $c$. The same property extends to all the $K_n^{\pi }$ (they're all crisp too) and then from there to $K_{:\infty }^{\pi }$ by induction. Then we can just use the following argument, where $\pi$ is arbitrary.

$\Theta \left(\pi \right)\left(1\right)=p{r}_{(A\times O{)}^{\omega }\ast }(\psi ⋉K_{:\infty }^{\pi })\left(1\right)=(\psi ⋉K_{:\infty }^{\pi })\left(1\right)=\psi (\lambda s_0.K_{:\infty }^{\pi }(s_0\left)\right(1\left)\right)=\psi \left(1\right)=1$

The last two inequalities were by $K_{:\infty }^{\pi }$ mapping constants to the same constant regardless of $\pi$, and by $\psi$ being normalized since it's an infradistribution. This same proof works if you swap out the 1 with a 0, so we have normalization for $\Theta$. 

T6.2 All that remains is checking the causality condition. We'll be using the alternate rephrasing of causality. We have $\Theta$ defined as

$\Theta \left({\pi }^{\prime }\right):=p{r}_{(A\times O{)}^{\omega }\ast }(\psi ⋉K_{:\infty }^{{\pi }^{\prime }})$

and want to derive our rephrasing of causality, that for any $U$ and ${\pi }^{\prime }$ and $\zeta$ and family $U_{\pi }$, we have

$(\forall e:U({\pi }^{\prime }\cdot e)\ge E_{\pi \sim \zeta }[U_{\pi }(\pi \cdot e)\left]\right)\to \Theta \left({\pi }^{\prime }\right)\left(U\right)\ge E_{\pi \sim \zeta }\left[\Theta \right(\pi \left)\right(U_{\pi }\left)\right]$

Accordingly, we get to fix a $U,{\pi }^{\prime },\zeta$, and family of functions $U_{\pi }$, and assume

$\forall e:U({\pi }^{\prime }\cdot e)\ge E_{\pi \sim \zeta }\left[U_{\pi }\right(\pi \cdot e\left)\right]$

Our proof target is

$\Theta \left({\pi }^{\prime }\right)\left(U\right)\ge E_{\pi \sim \zeta }\left[\Theta \right(\pi \left)\right(U_{\pi }\left)\right]$

Applying our reexpression of $\Theta$ in terms of $\psi$ and $K_{:\infty }^{\pi }$ and projection, we get

$p{r}_{(A\times O{)}^{\omega }\ast }(\psi ⋉K_{:\infty }^{{\pi }^{\prime }})(\lambda a{o}_{1:\infty }.U(a{o}_{1:\infty }\left)\right)\ge E_{\pi \sim \zeta }\left[p{r}_{(A\times O{)}^{\omega }\ast }\right(\psi ⋉K_{:\infty }^{\pi }\left)\right(\lambda a{o}_{1:\infty }.U_{\pi }\left(a{o}_{1:\infty }\right)\left)\right]$

Undoing the projections on both sides, we get

$(\psi ⋉K_{:\infty }^{{\pi }^{\prime }})(\lambda s_0,ao{s}_{1:\infty }.U(a{o}_{1:\infty }\left)\right)\ge E_{\pi \sim \zeta }\left[\right(\psi ⋉K_{:\infty }^{\pi }\left)\right(\lambda s_0,ao{s}_{1:\infty }.U_{\pi }\left(a{o}_{1:\infty }\right)\left)\right]$

Unpacking the semidirect product, we get

$\psi (\lambda s_0.K_{:\infty }^{{\pi }^{\prime }}(s_0\left)\right(\lambda ao{s}_{1:\infty }.U\left(a{o}_{1:\infty }\right)\left)\right)\ge E_{\pi \sim \zeta }\left[\psi \right(\lambda s_0.K_{:\infty }^{\pi }\left(s_0\right)(\lambda ao{s}_{1:\infty }.U_{\pi }(a{o}_{1:\infty }\left)\right)\left)\right]$

Now, we can notice something interesting here. By concavity for infradistributions, we have

$\psi (\lambda s_0.E_{\pi \sim \zeta }[K_{:\infty }^{\pi }\left(s_0\right)(\lambda ao{s}_{1:\infty }.U_{\pi }(a{o}_{1:\infty }\left)\right)\left]\right)\ge E_{\pi \sim \zeta }\left[\psi \right(\lambda s_0.K_{:\infty }^{\pi }\left(s_0\right)(\lambda ao{s}_{1:\infty }.U_{\pi }(a{o}_{1:\infty }\left)\right)\left)\right]$

So, our new proof target becomes

$\psi (\lambda s_0.K_{:\infty }^{{\pi }^{\prime }}(s_0\left)\right(\lambda ao{s}_{1:\infty }.U\left(a{o}_{1:\infty }\right)\left)\right)\ge \psi (\lambda s_0.E_{\pi \sim \zeta }[K_{:\infty }^{\pi }\left(s_0\right)(\lambda ao{s}_{1:\infty }.U_{\pi }(a{o}_{1:\infty }\left)\right)\left]\right)$

Because if we hit that, we can stitch the inequalities together. The obvious move to show this new result is to apply monotonicity of infradistributions. If the inner function on the left hand side was always above the inner function on the right hand side, we'd have our result by infradistribution monotonicity. So, our new proof target becomes

$\forall s_0:K_{:\infty }^{{\pi }^{\prime }}\left(s_0\right)(\lambda ao{s}_{1:\infty }.U(a{o}_{1:\infty }\left)\right)\ge E_{\pi \sim \zeta }\left[K_{:\infty }^{\pi }\right(s_0\left)\right(\lambda ao{s}_{1:\infty }.U_{\pi }\left(a{o}_{1:\infty }\right)\left)\right]$

At this point, now that we've gotten rid of $\psi$, we can use the full power of crisp infradistributions. Crisp infradistributions are just a set of probability distributions! Remember that the semidirect product, $\psi ⋉K$, can be viewed as taking a probability distribution from $\psi$, and for each $x$, picking a conditional probability distribution from $K\left(x\right)$, and all the probability distributions of that form make up $\psi ⋉K$.

In particular, the infinitely iterated semidirect product here can be written as a repeated process where, for each history of the form $s_0,ao{s}_{1:n},a,$ Murphy gets to select a probability distribution over the next observation and state from $K(s_n,a)$ (as a set of probability distributions) to fill in the next part of the action-observation-state tree. Accordingly every single probability distribution in $K_{:\infty }^{\pi }\left(s_0\right)$ can be written as $\pi$ interacting with an expanded probabilistic environment $e^{\Delta +}$ of type $(A\times O\times S{)}^{<\omega }\times A\to \Delta (O\times S)$ (which gives Murphy's choice wherever it needs to pick the next observation and state), subject to the constraints that

$e^{\Delta +}(ao{s}_{1:n},a)\in K(s_n,a)$

and

$e^{\Delta +}(\varnothing ,a)\in K(s_0,a)$

We'll abbreviate this property that $e^{\Delta +}$ always picks stuff from the appropriate $K$ set and starts off picking from $K(s_0,a)$ as $e^{\Delta +}\sim K,s_0$. 

Our old proof goal of

$\forall s_0:K_{:\infty }^{{\pi }^{\prime }}\left(s_0\right)(\lambda ao{s}_{1:\infty }.U(a{o}_{1:\infty }\left)\right)\ge E_{\pi \sim \zeta }\left[K_{:\infty }^{\pi }\right(s_0\left)\right(\lambda ao{s}_{1:\infty }.U_{\pi }\left(a{o}_{1:\infty }\right)\left)\right]$

can be rephrased as

$\forall s_0:{inf}_{{\mu }^{\prime }\in K_{:\infty }^{{\pi }^{\prime }}\left(s_0\right)}{\mu }^{\prime }(\lambda ao{s}_{1:\infty }.U(a{o}_{1:\infty }\left)\right)\ge E_{\pi \sim \zeta }\left[{inf}_{{\mu }_{\pi }\in K_{:\infty }^{\pi }\left(s_0\right)}{\mu }_{\pi }\right(\lambda ao{s}_{1:\infty }.U_{\pi }\left(a{o}_{1:\infty }\right)\left)\right]$

and then rephrased as

$\forall s_0:{inf}_{{\mu }^{\prime }\in K_{:\infty }^{{\pi }^{\prime }}\left(s_0\right)}{E}_{ao{s}_{1:\infty }\sim {\mu }^{\prime }}\left[U\right(a{o}_{1:\infty }\left)\right]\ge E_{\pi \sim \zeta }\left[{inf}_{{\mu }_{\pi }\in K_{:\infty }^{\pi }\left(s_0\right)}{E}_{ao{s}_{1:\infty }\sim {\mu }_{\pi }}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]$

And now, by our earlier discussion, we can rephrase this statement in terms of picking expanded probabilistic environments.

$\forall s_0:{inf}_{e^{{\Delta }^{\prime }+}\sim K,s_0}{E}_{ao{s}_{1:\infty }\sim {\pi }^{\prime }\cdot e^{{\Delta }^{\prime }+}}\left[U\right(a{o}_{1:\infty }\left)\right]\ge E_{\pi \sim \zeta }\left[{inf}_{e_{\pi }^{\Delta +}\sim K,s_0}{E}_{ao{s}_{1:\infty }\sim \pi \cdot e_{\pi }^{\Delta +}}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]$

Now, on the right side, since the set we're selecting the expanded environments from is the same each time and doesn't depend on $\pi$, we can freely move the inf outside of the expectation. It is unconditionally true that

${inf}_{e^{\Delta +}\sim K,s_0}{E}_{\pi \sim \zeta }\left[E_{ao{s}_{1:\infty }\sim \pi \cdot e^{\Delta +}}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]\ge E_{\pi \sim \zeta }\left[{inf}_{e_{\pi }^{\Delta +}\sim K,s_0}{E}_{ao{s}_{1:\infty }\sim \pi \cdot e_{\pi }^{\Delta +}}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]$

So now, our proof goal shifts to

$\forall s_0:{inf}_{e^{{\Delta }^{\prime }+}\sim K,s_0}{E}_{ao{s}_{1:\infty }\sim {\pi }^{\prime }\cdot e^{{\Delta }^{\prime }+}}\left[U\right(a{o}_{1:\infty }\left)\right]\ge {inf}_{e^{\Delta +}\sim K,s_0}{E}_{\pi \sim \zeta }\left[E_{ao{s}_{1:\infty }\sim \pi \cdot e^{\Delta +}}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]$

because if that were true, we could pair it up with the always-true inequality to hit our old proof goal. And we'd be able to show this proof goal if we showed the following, more ambitious result.

$\forall e^{\Delta +}:E_{ao{s}_{1:\infty }\sim {\pi }^{\prime }\cdot e^{\Delta +}}\left[U\right(a{o}_{1:\infty }\left)\right]\ge E_{\pi \sim \zeta }\left[E_{ao{s}_{1:\infty }\sim \pi \cdot e^{\Delta +}}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]$

Note that we're not restricting to compatibility with $K$ and $s_0$, we're trying to show it for any expanded probabilistic environment of type $(A\times O\times S{)}^{<\omega }\times A\to \Delta (O\times S)$. We can rephrase this new proof goal slightly, viewing ourselves as selecting an action and observation history.

$\forall e^{\Delta +}:E_{a{o}_{1:\infty }\sim p{r}_{(A\times O{)}^{\omega }\ast }({\pi }^{\prime }\cdot e^{\Delta +})}\left[U\right(a{o}_{1:\infty }\left)\right]\ge E_{\pi \sim \zeta }\left[E_{a{o}_{1:\infty }\sim p{r}_{(A\times O{)}^{\omega }\ast }(\pi \cdot e^{\Delta +})}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]$

Now, for any expanded probabilistic environment $e^{\Delta +}:(A\times O\times S{)}^{<\omega }\times A\to \Delta (O\times S)$, there is a unique corresponding probabilistic environment $e^{\Delta }$ of type $(A\times O{)}^{<\omega }\times A\to \Delta O$ where, for any policy, $p{r}_{(A\times O{)}^{\omega }\ast }(\pi \cdot e^{\Delta +})=\pi \cdot e^{\Delta }$. This is just the classical result that any POMDP can be viewed as a MDP with a state space consisting of finite histories, it still behaves the same. Using this swap, our new proof goal is:

$\forall e^{\Delta }:E_{a{o}_{1:\infty }\sim {\pi }^{\prime }\cdot e^{\Delta }}\left[U\right(a{o}_{1:\infty }\left)\right]\ge E_{\pi \sim \zeta }\left[E_{a{o}_{1:\infty }\sim \pi \cdot e^{\Delta }}\right[U_{\pi }\left(a{o}_{1:\infty }\right)\left]\right]$

Where $e^{\Delta }$ is an arbitrary probabilistic environment. Now, you can take any probabilistic environment $e^{\Delta }$ and view it as a mixture of deterministic environments $e$. So we can rephrase $e^{\Delta }$ as, at the start of time, picking a $e$ from $\xi \in \Delta E$ for some particular $\xi$. This is our mixture of deterministic environments that makes up $e^{\Delta }$. This mixture isn't necessarily unique, but there's always some mixture of deterministic enivironments that works to make $e^{\Delta }$ where $e^{\Delta }$ is arbitrary. So, our new proof goal becomes:

$\forall \xi \in \Delta E:E_{e\sim \xi }\left[E_{a{o}_{1:\infty }\sim {\pi }^{\prime }\cdot e}\right[U\left(a{o}_{1:\infty }\right)\left]\right]\ge E_{\pi \sim \zeta }\left[E_{e\sim \xi }\right[E_{a{o}_{1:\infty }\sim \pi \cdot e}\left[U_{\pi }\right(a{o}_{1:\infty }\left)\right]\left]\right]$

Since $\pi \cdot e$ is just a dirac-delta distribution on a particular history, we can substitute that in to get the equivalent

$\forall \xi \in \Delta E:E_{e\sim \xi }\left[U\right({\pi }^{\prime }\cdot e\left)\right]\ge E_{\pi \sim \zeta }\left[E_{e\sim \xi }\right[U_{\pi }(\pi \cdot e)\left]\right]$

Now we just swap the two expectations.

$\forall \xi \in \Delta E:E_{e\sim \xi }\left[U\right({\pi }^{\prime }\cdot e\left)\right]\ge E_{e\sim \xi }\left[E_{\pi \sim \zeta }\right[U_{\pi }(\pi \cdot e)\left]\right]$

And then we remember that our starting assumption was

$\forall e:U({\pi }^{\prime }\cdot e)\ge E_{\pi \sim \zeta }\left[U_{\pi }\right(\pi \cdot e\left)\right]$

So we've managed to hit our proof target and we're done, this propagates back to show causality for $\Theta$.

 

Theorem 7: Pseudocausal to Causal Translation: The following diagram commutes when the bottom belief function $\Theta$ is pseudocausal. The upwards arrows are the causal translation procedures, and the top arrows are the usual morphisms between the type signatures. The new belief function ${\Theta }^c$ is causal. Also, if $U:(A\times O{)}^{\omega }\to [0,1]$, and $U^N:(A\times (O+N){)}^{\omega }\to [0,1]$ is defined as $1$ for any history containing Nirvana, and $U\left(h\right)$ for any nirvana-free history, then $\forall \pi :{\Theta }^c\left(\pi \right)\left(U^N\right)=\Theta \left(\pi \right)\left(U\right)$.

T7.0 Preliminaries. Let's restate what the translations are. The notation $d(e,h)$ is that $e$"defends" $h$. $e$ defends $h$ if it responds to any prefix of $h$ which ends in an action with either the next observation in $h$, or Nirvana, and responds to any non-prefixes of $h$ with Nirvana.

Also, we'll write $h^N\sim {\pi }^{\prime },h$ if $h^N$ is "compatible" with ${\pi }^{\prime }$ and $h$. The criterion for this is that $h^N\sim {\pi }^{\prime }$, and that any prefix of $h^N$ which ends in an action and contains no Nirvana observations must either be a prefix of $h$, or only deviate from $h$ in the last action. An alternate way to state that is that $h^N$ is capable of being produced by a copolicy which defends $h$, interacting with ${\pi }^{\prime }$.

With these two notes, we introduce the infrakernels $K_d:(A\times O{)}^{\omega }\stackrel{ik}{\to }E$, and $K_{{\pi }^{\prime }}:(A\times O{)}^{\omega }\stackrel{ik}{\to }(A\times (O+N){)}^{\omega }$.

$K_d\left(h\right)$ is total uncertainty over $e$ such that $e$ defends $h$. $K_d\left(h\right)\left(f\right):={inf}_{e:d(e,h)}f\left(e\right)$

And $K_{{\pi }^{\prime }}\left(h\right)$ is total uncertainty over $h^N$ such that $h^N$ is compatible with ${\pi }^{\prime }$ and $h$. $K_{{\pi }^{\prime }}\left(h\right)\left(U^N\right):={inf}_{h^N\sim {\pi }^{\prime },h}{U}^N\left(h^N\right)$

Now, to briefly recap the three translations.For first-person static translation, we have

${\Theta }^c\left({\pi }^{\prime }\right):=p{r}_{(A\times (O+N){)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta ⋉K_{{\pi }^{\prime }})$

Where $\Theta$ is the original belief function.

For third-person static translation, we have

$E:=p{r}_{E\ast }(D⋉K_d)$

Where $D$ is the original infradistribution over $(A\times O{)}^{\omega }$.

For first-person dynamic translation, the new infrakernel has type signature

$\left(\right(A\times O{)}^{\omega }+N)\times A\stackrel{ik}{\to }((O+N)\times \left(\right(A\times O{)}^{\omega }+N\left)\right)$

Ie, the state space is destinies plus a single Nirvana state, and the observation state is the old space of observations plus a Nirvana observation. $N$ is used for the Nirvana observation, and $N$ is used for the Nirvana state. The transition dynamics are:

$\forall a^{\prime }\in A:{\to }_N(N,a^{\prime }):={\delta }_{N,N}$

and, if $a^{\prime }\ne a$, then ${\to }_N(aoh,a^{\prime }):={\delta }_{N,N}$

and otherwise, ${\to }_N(aoh,a):={\delta }_{o,h}\vee {\delta }_{N,N}$

The initial infradistribution is $i_{\ast }\left({\psi }_F\right)$, the obvious injection of ${\psi }_F$ from $(A\times O{)}^{\omega }$ to $(A\times O{)}^{\omega }+N$.

The obvious way to show this theorem is that we can assume the bottom part of the diagram commutes and ${\psi }_F,\Theta ,D$ are all pseudocausal, and then show that all three paths to ${\Theta }^c$ produce the same result, and it's causal. Then we just wrap up that last part about the utility functions.

Fortunately, assuming all three paths produce the same ${\Theta }^c$ belief function, it's trivial to show that it's causal. $i_{\ast }\left({\psi }_F\right)$ is an infradistribution since ${\psi }_F$ is, and ${\to }_N$ is a crisp infrakernel, so we can just invoke Theorem 6 that crisp infrakernels produce causal belief functions to show causality for ${\Theta }^c$. So we only have to check that all three paths produce the same result, and show the result about the utility functions. Rephrasing one of the proofs is one phase, and then there are two more phases showing that the other two phases hit the same target, and the last phase showing our result about the utility functions.

 We want to show that

${\Theta }^c\left({\pi }^{\prime }\right)=({\pi }^{\prime }\cdot {)}_{\ast }(E)=p{r}_{(A\times (O+N){)}^{\omega }\ast }(i_{\ast }\left({\psi }_F\right)⋉{\to }_{N:\infty }^{{\pi }^{\prime }})$

T7.1 First, let's try to rephrase ${\Theta }^c\left({\pi }^{\prime }\right)\left(U^N\right)$ into a more handy form for future use. Invoking our definition of ${\Theta }^c\left({\pi }^{\prime }\right)$, we have:

${\Theta }^c\left({\pi }^{\prime }\right)\left(U^N\right)=p{r}_{(A\times (O+N){)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta ⋉K_{{\pi }^{\prime }})\left(U^N\right)$

Then, we undo the projection

$=({\top }_{\Pi }⋉\Theta ⋉K_{{\pi }^{\prime }})(\lambda \pi ,h,h^N.U^N(h^N\left)\right)$

And unpack the semidirect product

$={\top }_{\Pi }(\lambda \pi .\Theta (\pi \left)\right(\lambda h.K_{{\pi }^{\prime }}\left(h\right)(\lambda h^N.U^N(h^N\left)\right)\left)\right)$

And unpack what ${\top }_{\Pi }$ means

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.K_{{\pi }^{\prime }}(h\left)\right(\lambda h^N.U^N\left(h^N\right)\left)\right)$

And then apply the definition of $K_{{\pi }^{\prime }}\left(h\right)$

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{inf}_{h^N\sim {\pi }^{\prime },h}{U}^N(h^N\left)\right)$

This will be our final rephrasing of ${\Theta }^c\left({\pi }^{\prime }\right)\left(U^N\right)$. Our job is to derive this result for the other two paths.

T7.2 First up, the third-person static translation. We can start with definitions.

$({\pi }^{\prime }\cdot {)}_{\ast }(E\left)\right(U^N)=({\pi }^{\prime }\cdot {)}_{\ast }\left(p{r}_{E\ast }\right(D⋉K_d\left)\right)\left(U^N\right)$

And then, we can recall that since $D$ and $\Theta$ are assumed to commute, we can define $D$ in terms of $\Theta$ via $D=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta )$. Making this substitution, we get

$=({\pi }^{\prime }\cdot {)}_{\ast }(p{r}_{E\ast }\left(\right(p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta ))⋉K_d)\left)\right(U^N)$

We undo the first pushforward

$=p{r}_{E\ast }\left(\right(p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta ))⋉K_d)(\lambda e.U^N({\pi }^{\prime }\cdot e\left)\right)$

And then the projection

$=\left(\right(p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta ))⋉K_d)(\lambda h,e.U^N({\pi }^{\prime }\cdot e\left)\right)$

And unpack the semidirect product

$=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta )(\lambda h.K_d(h\left)\right(\lambda e.U^N({\pi }^{\prime }\cdot e)\left)\right)$

And remove the projection

$=({\top }_{\Pi }⋉\Theta )(\lambda \pi ,h.K_d(h\left)\right(\lambda e.U^N({\pi }^{\prime }\cdot e)\left)\right)$

and unpack the semidirect product and what ${\top }_{\Pi }$ is

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.K_d(h\left)\right(\lambda e.U^N({\pi }^{\prime }\cdot e)\left)\right)$

Now, we recall that $K_d\left(h\right)$ is all the $e$ that defend $h$, to get

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{inf}_{e:d(e,h)}{U}^N({\pi }^{\prime }\cdot e\left)\right)$

At this point we can realize that for any $e$ which defends $h$, when $e$ interacts with ${\pi }^{\prime }$, it makes a $h^N$ that is compatible with ${\pi }^{\prime }$ and $h$. Further, all $h^N$ compatible with ${\pi }^{\prime }$ and $h$ have an $e$ which produces them. If $h^N$ has its nirvana-free prefix not being a prefix of $h$, then the defending $e$ which doesn't end $h$ early, just sends deviations to Nirvana, is capable of producing it. If $h^N$ looks like $h$ but ended early with Nirvana, you can just have a defending $e$ which ends with Nirvana at the same time. So we can rewrite this as

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{inf}_{h^N\sim {\pi }^{\prime },h}:U^N(h^N\left)\right)$

And this is exactly the form we got for $\Theta \left({\pi }^{\prime }\right)\left(U^N\right)$.

T7.3 Time for the third and final translation. We want to show that

$p{r}_{(A\times (O+N){)}^{\omega }\ast }\left(i_{\ast }\right({\psi }_F)⋉{\to }_{N:\infty }^{{\pi }^{\prime }})\left(U^N\right)$

is what we want. Because the pseudocausal square commutes, we have that ${\psi }^F=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta )$, so we can make that substitution to yield

$=p{r}_{(A\times (O+N){)}^{\omega }\ast }\left(i_{\ast }\right(p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta ))⋉{\to }_{N:\infty }^{{\pi }^{\prime }})\left(U^N\right)$

Remove the projection, to get

$=\left(i_{\ast }\right(p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta ))⋉{\to }_{N:\infty }^{{\pi }^{\prime }})(\lambda s_0^N,ao{s}_{1:\infty }^N.U^N(a{o}_{1:\infty }^N\left)\right)$

For this notation, we're using $s^N$ to refer to an element of $(A\times O{)}^{\omega }+N$, the state space. $ao{s}_{1:\infty }^N$ is an element of $(A\times (O+N)\times ((A\times O{)}^{\omega }+N){)}^{\omega }$, a full unrolling. $a{o}_{1:\infty }^N$ is the projection of this to $(A\times (O+N){)}^{\omega }$.

We unpack the semidirect product to yield

$=i_{\ast }\left(p{r}_{(A\times O{)}^{\omega }\ast }\right({\top }_{\Pi }⋉\Theta \left)\right)(\lambda s_0^N.{\to }_{N:\infty }^{{\pi }^{\prime }}(s_0^N\left)\right(\lambda ao{s}_{1:\infty }^N.U^N\left(a{o}_{1:\infty }^N\right)\left)\right)$

and rewrite the injection pushforward

$=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉\Theta )(\lambda h.{\to }_{N:\infty }^{{\pi }^{\prime }}(h\left)\right(\lambda ao{s}_{1:\infty }^N.U^N\left(a{o}_{1:\infty }^N\right)\left)\right)$

and remove the projection

$=({\top }_{\Pi }⋉\Theta )(\lambda \pi ,h.{\to }_{N:\infty }^{{\pi }^{\prime }}(h\left)\right(\lambda ao{s}_{1:\infty }^N.U^N\left(a{o}_{1:\infty }^N\right)\left)\right)$

And unpack the semidirect product along with ${\top }_{\Pi }$.

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{\to }_{N:\infty }^{{\pi }^{\prime }}(h\left)\right(\lambda ao{s}_{1:\infty }^N.U^N\left(a{o}_{1:\infty }^N\right)\left)\right)$

Now we rewrite this as a projection to yield

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.p{r}_{(A\times (O+N){)}^{\omega }\ast }({\to }_{N:\infty }^{{\pi }^{\prime }}\left(h\right)\left)\right(\lambda a{o}_{1:\infty }^N.U^N\left(a{o}_{1:\infty }^N\right)\left)\right)$

And do a little bit of reindexing for convenience, swapping out the symbol $a{o}_{1:\infty }^N$ for $h^N$, getting

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.p{r}_{(A\times (O+N){)}^{\omega }\ast }({\to }_{N:\infty }^{{\pi }^{\prime }}\left(h\right)\left)\right(\lambda h^N.U^N\left(h^N\right)\left)\right)$

And now, we can ask what $p{r}_{(A\times (O+N){)}^{\omega }\ast }\left({\to }_{N:\infty }^{{\pi }^{\prime }}\right(h\left)\right)$ is. Basically, the starting state is the destiny $h$, and then ${\pi }^{\prime }$ interacts with it through the kernel ${\to }_N$. Due to how ${\to }_N$ is defined, it can do one of three things. First, it could just unroll $h$ all the way to completion, if $h$ is the sort of history that's compatible with ${\pi }^{\prime }$. Second, it could partially unroll $h$ and deviate to Nirvana early, even if ${\pi }^{\prime }$ is compatible with more, because of how ${\to }_N(aoh,a)$ is defined. Finally, ${\pi }^{\prime }$ could deviate from $h$ and then ${\to }_N$ would have to respond with Nirvana. And of course, once you're in a Nirvana state, you're in there for good. Hm, you have total uncertainty over histories $h^N$ compatible with ${\pi }^{\prime }$ and $h$, any of them at all could be made by $p{r}_{(A\times (O+N){)}^{\omega }\ast }\left({\to }_{N:\infty }^{{\pi }^{\prime }}\right(h\left)\right)$. So, this projection of the infrakernel unrolling $h$ is just $K_{{\pi }^{\prime }}\left(h\right)$. We get

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.K_{{\pi }^{\prime }}(h\left)\right(\lambda h^N.U^N\left(h^N\right)\left)\right)$

And then we use what $K_{{\pi }^{\prime }}\left(h\right)$ does to functions, to get

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{inf}_{h^N\sim {\pi }^{\prime },h}{U}^N(h^N\left)\right)$

Which is exactly the form we need. So, all three translation procedures produce identical belief functions.

T7.4 The only thing which remains to wrap this result up is guaranteeing that, if $U^N:(A\times (O+N){)}^{\omega }\to [0,1]$ is 1 if the history contains Nirvana, (or infinity for the $R$ type signature), and $U$ otherwise, then ${\Theta }^c\left({\pi }^{\prime }\right)\left(U^N\right)=\Theta \left({\pi }^{\prime }\right)\left(U\right)$.

We rephrased ${\Theta }^c\left({\pi }^{\prime }\right)\left(U^N\right)$ as ${inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{inf}_{h^N\sim {\pi }^{\prime },h}{U}^N(h^N\left)\right)$

We can notice something interesting. If $h$ is the sort of history that ${\pi }^{\prime }$ is capable of making, ie $h\sim {\pi }^{\prime }$, then all of the $h^N\sim {\pi }^{\prime },h$ are going to end up in Nirvana except $h$ itself, because all the $h^N$ are like "follow ${\pi }^{\prime }$, any deviations of ${\pi }^{\prime }$ from $h$ go to Nirvana, and also Nirvana can show up early". In this case, since any history ending with Nirvana is maximum utility, and otherwise $U$ is copied, we have ${inf}_{h^N\sim {\pi }^{\prime },h}{U}^N\left(h^N\right)=U\left(h\right)$. However, if $h$ is incompatible with ${\pi }^{\prime }$, then no matter what, a history $h^N$ which follows ${\pi }^{\prime }$ is going to hit Nirvana and be assigned maximum utility. So, we can rewrite

${inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{inf}_{h^N\sim {\pi }^{\prime },h}{U}^N(h^N\left)\right)$

as

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

Which can be written as an update, yielding

$={inf}_{\pi }{u}_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left(U\right)$

And then, we remember that regardless of ${\pi }^{\prime }$ and $\pi$, for pseudocausal belief functions, which $\Theta$ is, we have that $u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left(U\right)\ge \Theta \left({\pi }^{\prime }\right)\left(U\right)$, so the update assigns higher expectation values than $\Theta \left({\pi }^{\prime }\right)$ does. Also, $u_{\sim {\pi }^{\prime }}^1\left(\Theta \right({\pi }^{\prime }\left)\right)=\Theta \left({\pi }^{\prime }\right)$. Thus, the infinimum is attained by ${\pi }^{\prime }$, and we get

$=\Theta \left({\pi }^{\prime }\right)\left(U\right)$

and we're done.

 

Theorem 8: Acausal to Pseudocausal Translation: The following diagram commutes when the bottom belief function $\Theta$ is acausal. The upwards arrows are the pseudocausal translation procedures, and the top arrows are the usual morphisms between the type signatures. The new belief function ${\Theta }^p$ will be pseudocausal.

T8.0 First, preliminaries. The two translation procedures are, to go from an infradistribution over policy-tagged destinies $D$, to an infradistribution over destinies $D^p$, we just project. 

$D^p:=p{r}_{(A\times O{)}^{\omega }\ast }\left(D\right)$

And, to go from an acausal belief function $\Theta$ to a pseudocausal one ${\Theta }^p$, we do the translation

${\Theta }^p\left({\pi }^{\prime }\right):=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)$

We assume that $D$ and $\Theta$ commute, and try to show that these translation procedures result in a ${\Theta }^p$ and $D^p$ which are pseudocausal and commute with each other. So, our proof goals are that

${\Theta }^p\left({\pi }^{\prime }\right)=u_{\sim {\pi }^{\prime }}^1\left(D^p\right)$

and

$D^p=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉{\Theta }^p)$

Once we've done that, it's easy to get that ${\Theta }^p$ is pseudocausal. This occurs because the projection of any infradistribution is an infradistribution, so we can conclude that $D^p$ is an infradistribution over $(A\times O{)}^{\omega }$. Also, back in the Pseudocausal Commutative Square theorem, we were able to derive that any infradistribution $D^p$ over $(A\times O{)}^{\omega }$, when translated to a ${\Theta }^p$, makes a pseudocausal belief function, no special properties were used in that except being an infradistribution.

T8.1 Let's address the first one, trying to show that

${\Theta }^p\left({\pi }^{\prime }\right)=u_{\sim {\pi }^{\prime }}^1\left(D^p\right)$

We'll take the left side, plug in some function, and keep unpacking and rearranging until we get the right side with some function plugged in. First up is applying definitions.

${\Theta }^p\left({\pi }^{\prime }\right)\left(U\right)=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)\left(U\right)$

by how ${\Theta }^p$ was defined. Now, we start unpacking. First, the projection.

$=({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)(\lambda \pi ,h.U(h\left)\right)$

Then unpack the semidirect product and ${\top }_{\Pi }$, for

$={inf}_{\pi }{u}_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)(\lambda h.U(h\left)\right)$

Then unpack the update, to get

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

Then pack up the ${inf}_{\pi }$

$={\top }_{\Pi }(\lambda \pi .\Theta (\pi \left)\right(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U\left(h\right)+{\text{1}}_{h\nsim {\pi }^{\prime }}\left)\right)$

And pack up the semidirect product

$=({\top }_{\Pi }⋉\Theta )(\lambda \pi ,h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

And since $D={\top }_{\Pi }⋉\Theta$ for the original acausal belief function, we can rewrite this as

$=D(\lambda \pi ,h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

And pack this up in a projection.

$=p{r}_{(A\times O{)}^{\omega }\ast }\left(D\right)(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

And then, since we defined $D^p:=p{r}_{(A\times O{)}^{\omega }\ast }\left(D\right)$, we can pack this up as

$=D^p(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

And then pack up the update

$=u_{\sim {\pi }^{\prime }}^1\left(D^p\right)\left(U\right)$

So, that's one direction done.

T8.2 Now for the second result, showing that

$D^p=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉{\Theta }^p)$

Again, we'll take the more complicated form, and write it as the first one, for arbitrary functions $U$.bWe begin with

$p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉{\Theta }^p)\left(U\right)$

and then unpack what ${\Theta }_p\left({\pi }^{\prime }\right)$ is to get

$=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda {\pi }^{\prime }.p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)\left)\right)\left(U\right)$

Undo the projection

$=({\top }_{\Pi }⋉(\lambda {\pi }^{\prime }.p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)\left)\right)(\lambda {\pi }^{\prime },h.U(h\left)\right)$

Unpack the semidirect product and ${\top }_{\Pi }$.

$={inf}_{{\pi }^{\prime }}p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)(\lambda h.U(h\left)\right)$

Remove the projection

$={inf}_{{\pi }^{\prime }}({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right(\lambda {\pi }^{\prime \prime },h.U\left(h\right))$

Unpack the semidirect product and ${\top }_{\Pi }$ again.

$={inf}_{{\pi }^{\prime }}{inf}_{\pi }{u}_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)(\lambda h.U(h\left)\right)$

Let's fold the two infs into one inf, this doesn't change anything, just makes things a bit more concise.

$={inf}_{{\pi }^{\prime },\pi }{u}_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)(\lambda h.U(h\left)\right)$

and unpack the update.

$={inf}_{{\pi }^{\prime },\pi }\Theta \left(\pi \right)(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

Now, we can note something interesting here. If ${\pi }^{\prime }$ is selected to be equal to $\pi$, that inner function is just $U$, because $\Theta \left(\pi \right)$ is only supported over histories compatible with $\pi$. If ${\pi }^{\prime }$ is unequal to $\pi$, that inner function is $U$ with 1's for some inputs, possibly. So, our choice of ${\pi }^{\prime }$ is optimal for minimizing when its equal to $\pi$, so we can rewrite as

$={inf}_{\pi }\Theta \left(\pi \right)(\lambda h.U(h\left)\right)$

and write this as ${\top }_{\Pi }$

$={\top }_{\Pi }(\lambda \pi .\Theta (\pi \left)\right(\lambda h.U\left(h\right)\left)\right)$

And pack up as a semidirect product

$=({\top }_{\Pi }⋉\Theta )(\lambda \pi ,h.U(h\left)\right)$

and then because $D={\top }_{\Pi }⋉\Theta$, we substitute to get

$=D(\lambda \pi ,h.U(h\left)\right)$

and then write as a projection.

$=p{r}_{(A\times O{)}^{\omega }\ast }\left(D\right)\left(U\right)$

Now, this is just $D^p$, yielding

$=D^p\left(U\right)$

and we're done.

 

Proposition 2: The two formulations of x-pseudocausality are equivalent for crisp acausal belief functions.

One formulation of x-pseudocausality is that

$\forall \pi ,{\pi }^{\prime }:u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\subseteq {\Theta }^x\left({\pi }^{\prime }\right)$ where ${\Theta }^x\left({\pi }^{\prime }\right)\left(U\right):=\Theta \left({\pi }^{\prime }\right)(inf(x,U\left)\right)$

The second formulation is,

$\forall \pi ,{\pi }^{\prime },\mu \in \Theta \left(\pi \right):\mu (h\nsim {\pi }^{\prime })\ge x\cdot {inf}_{\nu \in \Theta \left({\pi }^{\prime }\right)}{d}_{TV}(\mu ,\nu )$

This proof will be slightly informal, it can be fully formalized without too many conceptual difficulties. We need to establish some basic probability theory results to work on this. The proof outline is we establish/recap four probability-theory/inframeasure-theory results, and then show the two implication directions of the iff statement.

P2.1 Our first claim is that, given any two probability distributions $\mu$ and $\nu$, you can shatter them into measures $m^{\ast },m_{\mu }$, and $m_{\nu }$ such that $m^{\ast }+m_{\mu }=\mu$ and $m^{\ast }+m_{\nu }=\nu$, and $m_{\mu }\left(1\right)=m_{\nu }\left(1\right)=d_{TV}(\mu ,\nu )$. What this decomposition is basically doing is finding the largest chunk of measure that $\mu$ and $\nu$ agree on (that's $m^{\ast }$), and then subtracting that out from $\mu$ and $\nu$ yields you your $m_{\mu }$ and $m_{\nu }$. These measures have no overlap, because if there was overlap, you could put that overlap into the $m^{\ast }$ chunk of measure. And, the mass of the "unique to $\mu$" piece must equal the mass of the "unique to $\nu$" piece because they must add up to probability distributions, and this quantity is exactly the total variation distance of $\mu ,\nu$.

P2.2 Our second claim is that 

$x\cdot d_{TV}(\mu ,\nu )={sup}_{U:(A\times O{)}^{\omega }\to [0,x]}|\mu \left(U\right)-\nu \left(U\right)|$

Why is this? Well, there's an alternate formulation of total variation distance where

$d_{TV}(\mu ,\nu )={sup}_{U:(A\times O{)}^{\omega }\to [0,1]}|\mu \left(U\right)-\nu \left(U\right)|$

As intuition for this, we can pick a function U which is 1 on the support of $m_{\mu }$, and 0 elsewhere. In such a case, we'd get

$|\mu \left(U\right)-\nu \left(U\right)|=|m^{\ast }\left(U\right)+m_{\mu }\left(U\right)-m^{\ast }\left(U\right)-m_{\nu }\left(U\right)|=|m_{\mu }\left(U\right)-m_{\nu }\left(U\right)|$

and then remember that $m_{\mu }$ and $m_{\nu }$ have disjoint supports, so we get

$=|m_{\mu }\left(1\right)-m_{\nu }\left(0\right)|=m_{\mu }\left(1\right)=d_{TV}(\mu ,\nu )$

And any other function in the $[0,1]$ range wouldn't do as well at attaining different expectation values on $m_{\mu }$ and $m_{\nu }$. So that's where the identity comes from. If we try to do the optimal separation but instead restrict $U$ to be in $[0,x]$, we'd get

$=|m_{\mu }\left(x\right)-m_{\nu }\left(0\right)|=m_{\mu }\left(x\right)=x\cdot m_{\mu }\left(1\right)=x\cdot d_{TV}(\mu ,\nu )$

and any other utility function in $[0,x]$ wouldn't do as well at separating the two.

P2.3 Our third claim is that the function which maps $f$ to $-\infty$, if $f$ goes outside of $[0,x]$, and otherwise maps $f$ to $\psi \left(f\right)$, corresponds to taking the set of sa-measures that is $\Psi$ (the set form of $\psi$), and taking the upper completion of it under all signed-measure, b pairs where $b+x\cdot m^{-}\left(1\right)\ge 0$. Call this an x-sa measure. Ie, if $x=\frac{1}{3}$, then one unit of +b is big enough to cancel out 3 units of negative-measure in the signed measure. Clearly, if $f:X\to [0,x]$, and $(m,b)$ has $b+x\cdot m^{-}\left(1\right)\ge 0$ (is an x-sa measure) then we have

$m\left(f\right)+b=m^{+}\left(f\right)+m^{-}\left(f\right)+b\ge m^{+}\left(0\right)+m^{-}\left(x\right)+b=x\cdot m^{-}\left(1\right)+b\ge 0$

So, adding in the cone of all x-sa pairs like that doesn't actually affect the expectation values of any function bounded in $[0,x]$ at all. However, for any function which goes over the x upper-bound, you can consider a x-sa measure which concentrates all its large amount of negative measure on a point where the function exceeds the upper bound, and exactly compensates for it with the +b term. Adding this on can make the function, evaluated at said point, have an unboundedly negative expectation value, justifying our choice of $-\infty$ for the expectation value.

P2.4 Time for the fourth claim. To build up to it, the monotone hull of a functional $C(X,[0,x\left]\right)\to [0,1]$ is as follows: if ${\psi }^x$ is the original functional, then ${\psi }^m$ is the monotone hull defined by 

${\psi }^m\left(f\right):={sup}_{f^{\prime }:X\to [0,x]:f^{\prime }\le f}{\psi }^x\left(f\right)$

Our fourth claim is that, in the set-based value, this operation corresponds to restricting the set of x-sa measures that is ${\Psi }^x$ to just the a-measures in it. Why? Well, we have

$\forall f\in C_B\left(X\right):{\psi }^m\left(f\right)\ge {\psi }^x\left(f\right)$

This is because ${\psi }^x$ and ${\psi }^m$ both agree that any function with negative parts gets $-\infty$ value, and both agree on the expectation of any function bounded in $[0,x]$, but for functions above 0 which also stray above $x$ somewhere, ${\psi }^x\left(f\right)=-\infty$, while ${\psi }^m\left(f\right)\ge 0$.

Therefore, since ${\psi }^m\ge {\psi }^x$ (when considered as a function, we aren't using the infradistribution reversed ordering here), we have that ${\Psi }^m\subseteq {\Psi }^x$ (higher functions correspond to smaller sets). Now, ${\Psi }^m$ cannot contain any x-sa-measures with negative measure anywhere in the measure component. For, if there was such a point in there, we could consider a function $f$ that assigned extremely high value to the region of negative measure, and 0 value elsewhere, and $f$ would attain a negative expectation value on that x-sa measure, which contradicts the nonnegative worst-case expectation value of $f$ due to how ${\psi }^m$ was defined. So, the set ${\Psi }^m$ must consist entirely of a-measures. Further, for any function $f$ with range in $[0,x]$, it is minimized by an a-measure in ${\Psi }^x$, and the same point is present in ${\Psi }^x\cap M^a$ (no extra a-measures added), so the $\varphi$ corresponding to that set must assign the exact same expectation value to $f$ as ${\psi }^x$ and ${\psi }^m$ do. Also, any set consisting entirely of a-measures must have its expectation functional be monotone.

So, recapping what we've done so far, we know that ${\Psi }^m\subseteq {\Psi }^x$. We know that ${\Psi }^m$ must consist entirely of a-measures, otherwise we'd get a contradiction with monotonicity. Further, ${\Psi }^x\cap M^a$ (the biggest set that ${\Psi }^m$ could possibly be) has its expectation functional $\varphi$ agree with ${\psi }^x$ on the expectations of functions in $[0,x]$, and it's monotone like ${\psi }^m$ is. Now, if ${\Psi }^m\subset {\Psi }^x\cap M^a$ (strict subset), we'd have the functional $\varphi$ corresponding to the intersection being strictly below ${\psi }^m$ on some function. However ${\psi }^m$ is the minimal monotone function that agrees with ${\psi }^x$ on the expectations of functions in $[0,x]$, so this rule out strict subset, and we must have equality. The monotone hull of an expectation functional corresponds to the restriction to the set to a-measures. Further, we can rewrite the definition

${\psi }^m\left(f\right):={sup}_{f^{\prime }:(A\times O{)}^{\omega }\to [0,x]:f^{\prime }\le f}{\psi }^x\left(f\right)$

as just

${\psi }^m\left(f\right):={\psi }^x(inf(x,f\left)\right)$

And we're done with this.

Putting claims 3 and 4 together, we can now express what the set ${\Theta }^x\left({\pi }^{\prime }\right)$ is, from our definition of ${\Theta }^x\left({\pi }^{\prime }\right)\left(U\right):=\Theta \left({\pi }^{\prime }\right)(inf(x,U\left)\right)$. ${\Theta }^x\left({\pi }^{\prime }\right)$ (interpreted as a set of sa-measures) is just the upper completion of $\Theta \left({\pi }^{\prime }\right)$ under x-sa measures, those with $b+x\cdot m^{-}\left(1\right)\ge 0$ (this is the restriction to $[0,x]$), and then the intersection of that set with the cone of a-measures (monotone hull), and then upper completion under sa-measures (the restriction to $[0,1]$).

P2.5 Time to begin showing one direction of the iff statement. Remember, we're assuming that all the $\Theta \left(\pi \right)$ are induced by a set of probability distributions, they're crisp. We'll start with the easy direction, that

$\forall \pi ,{\pi }^{\prime },\mu \in \Theta \left(\pi \right):\mu (h\nsim {\pi }^{\prime })\ge x\cdot {inf}_{\nu \in \Theta \left({\pi }^{\prime }\right)}{d}_{TV}(\mu ,\nu )$

implies

$\forall \pi ,{\pi }^{\prime },U:u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left(U\right)\ge {\Theta }^x\left({\pi }^{\prime }\right)\left(U\right)$

where ${\Theta }^x\left({\pi }^{\prime }\right)\left(U\right):=\Theta \left({\pi }^{\prime }\right)(inf(x,U\left)\right)$. (well, technically, this shouldn't just be continuous functions, but lower-semicontinuous functions as well) To begin with, let $\pi ,{\pi }^{\prime },U$ be arbitrary with $U$ bounded in $[0,1]$. We can start unpacking

$u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right(U\left)\right)=\Theta \left(\pi \right)(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

Now, this minimal value must be attained by some minimal point in $\Theta \left(\pi \right)$, which is some probability distribution $\mu$. So, we have

$=\mu (\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

We can, at this point, select the closest probability distribution to $\mu$ in $\Theta \left({\pi }^{\prime }\right)$ according to total variation distance, call that $\nu$. We do our usual shattering of $\mu$ into $m^{\ast }$ and $m_{\mu }$, the chunk of measure where $\mu$ and $\nu$ overlap, and the chunk of measure that's unique to $\mu$. Note that the chunk of measure where $\mu$ and $\nu$ overlap must be supported on histories compatible with ${\pi }^{\prime }$ since $\nu \in \Theta \left({\pi }^{\prime }\right)$, so we can break things down as

$=m^{\ast }\left(U\right)+m_{\mu }(\lambda h.{\text{1}}_{h\sim {\pi }^{\prime }}U(h)+{\text{1}}_{h\nsim {\pi }^{\prime }})$

And then we can break $m_{\mu }$ down further into $m_{\mu ,\sim {\pi }^{\prime }}$ and $m_{\mu ,\nsim {\pi }^{\prime }}$, for the chunk of measure on histories compatible with ${\pi }^{\prime }$ and incompatible, respectively, yielding

$=m^{\ast }\left(U\right)+m_{\mu ,\sim {\pi }^{\prime }}\left(U\right)+m_{\mu ,\nsim {\pi }^{\prime }}\left(1\right)$

Which can be rephrased as

$=m^{\ast }\left(U\right)+m_{\mu ,\sim {\pi }^{\prime }}\left(U\right)+\mu (h\nsim {\pi }^{\prime })$

Now it's time for some inequalities, explained afterwards.

$m^{\ast }\left(U\right)+m_{\mu ,\sim {\pi }^{\prime }}\left(U\right)+\mu (h\nsim {\pi }^{\prime })\ge m^{\ast }\left(U\right)+\mu (h\nsim {\pi }^{\prime })\ge m^{\ast }(inf(U,x\left)\right)+\mu (h\nsim {\pi }^{\prime })$

$\ge m^{\ast }(inf(U,x\left)\right)+x\cdot d_{TV}(\mu ,\nu )=m^{\ast }(inf(U,x\left)\right)+{sup}_{U^{\prime }:(A\times O{)}^{\omega }\to [0,x]}|\nu \left(U^{\prime }\right)-\mu \left(U^{\prime }\right)|$

$=m^{\ast }(inf(U,x\left)\right)+{sup}_{U^{\prime }:(A\times O{)}^{\omega }\to [0,x]}|m^{\ast }\left(U^{\prime }\right)+m_{\nu }\left(U^{\prime }\right)-m^{\ast }\left(U^{\prime }\right)-m_{\mu }\left(U^{\prime }\right)|$

$=m^{\ast }(inf(U,x\left)\right)+{sup}_{U^{\prime }:(A\times O{)}^{\omega }\to [0,x]}|m_{\nu }\left(U^{\prime }\right)-m_{\mu }\left(U^{\prime }\right)|$

$=m^{\ast }(inf(U,x\left)\right)+m_{\nu }\left(x\right)\ge m^{\ast }(inf(U,x\left)\right)+m_{\nu }(inf(U,x\left)\right)=\nu (inf(U,x\left)\right)$

$\ge {inf}_{{\nu }^{\prime }\in \Theta \left({\pi }^{\prime }\right)}{\nu }^{\prime }(inf(U,x\left)\right)=\Theta \left({\pi }^{\prime }\right)(inf(U,x\left)\right)={\Theta }^x\left(U\right)$

So, for the first line, the first two inequalities are obvious. For the second line, the initial inequality is us invoking the total variation distance variant of x-pseudocausality since $\nu$ is as close as possible to $\mu$ while also being in $\Theta \left({\pi }^{\prime }\right)$, and the equality is reexpressing total variation distance in accordance with our second claim. The third line is just shattering $\nu$ and $\mu$ in our way connected with total variation distance, and the fourth line is just canceling. For the fifth line, the first equality is the supremum being attained by a function that's $x$ on $m_{\nu }$, and 0 on $m_{\mu }$, as the two measures are disjoint, and the second equality is $\nu =m^{\ast }+m_{\nu }$. Then, for line 6, the inequality is obvious because $\nu \in \Theta \left({\pi }^{\prime }\right)$, and then we just wrap the inf up as an expectation according to $\Theta \left({\pi }^{\prime }\right)$, and apply the definition of ${\Theta }^x\left({\pi }^{\prime }\right)$.

P2.6 Now for the other direction of the iff-statement, going from

$\forall \pi ,{\pi }^{\prime },U:u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left(U\right)\ge {\Theta }^x\left({\pi }^{\prime }\right)\left(U\right)$

to

$\forall \pi ,{\pi }^{\prime },\mu \in \Theta \left(\pi \right):\mu (h\nsim {\pi }^{\prime })\ge x\cdot {inf}_{\nu \in \Theta \left({\pi }^{\prime }\right)}{d}_{TV}(\mu ,\nu )$

Using our set-based characterization of inframeasure ordering, we can accurately rephrase our initial statement as

$\forall \pi ,{\pi }^{\prime }:u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\subseteq {\Theta }^x\left({\pi }^{\prime }\right)$

The former set is "take all the minimal points of $\Theta \left(\pi \right)$, convert all their measure on histories incompatible with ${\pi }^{\prime }$ to the +b term, do closed convex hull and upper completion", and the latter set is "take $\Theta \left({\pi }^{\prime }\right)$, do upper completion w.r.t. the cone of x-sa measures, restrict to just the a-measures, and then add in the cone of sa-measures again"

Pick a $\mu \in \Theta \left(\pi \right)$. When we 1-update it on compatibility with ${\pi }^{\prime }$, we get $(m_{\mu ,\sim {\pi }^{\prime }},\mu (h\nsim {\pi }^{\prime }\left)\right)$. And said point lies in ${\Theta }^x\left({\pi }^{\prime }\right)$, which means it must be possible to create by taking a minimal point in $\Theta \left({\pi }^{\prime }\right)$ (call that one $\nu$), and adding an x-sa measure to it. Call the x-sa measure $(m^{\prime },b^{\prime })$. So, our net result is:

$(m_{\mu ,\sim {\pi }^{\prime }},\mu (h\nsim {\pi }^{\prime }\left)\right)=(\nu ,0)+(m^{\prime },b^{\prime })$

The update of $\mu$ equals $\nu$ plus an x-sa measure. Now, breaking up $m^{\prime }$ into its positive and negative parts which are disjoint, $(m^{\prime }{)}^{+}$ and $(m^{\prime }{)}^{-}$, we can rewrite things as:

$b^{\prime }=\mu (h\nsim {\pi }^{\prime })$

$m_{\mu ,\sim {\pi }^{\prime }}=\nu +(m^{\prime }{)}^{+}+(m^{\prime }{)}^{-}$

Adding $m_{\mu ,\nsim {\pi }^{\prime }}$ to both sides and folding it into $\mu$, and rearranging a bit and adding parentheses, that second equality can be restated as

$\mu =\nu +\left(\right(m^{\prime }{)}^{+}+m_{\mu ,\nsim {\pi }^{\prime }})+(m^{\prime }{)}^{-}$

Now, $\nu$ is supported entirely over histories compatible with ${\pi }^{\prime }$, and $(m^{\prime }{)}^{-}$ is a chunk of negative measure taken out of $\nu$, so $(m^{\prime }{)}^{-}$ must be supported entirely over histories compatible with ${\pi }^{\prime }$. Also, $(m^{\prime }{)}^{+}$ and $(m^{\prime }{)}^{-}$ are disjoint (Jordan decomposition), and $m_{\mu ,\nsim {\pi }^{\prime }}$  is supported entirely over histories incompatible with ${\pi }^{\prime }$, so the positive measure $(m^{\prime }{)}^{+}+m_{\mu ,\nsim {\pi }^{\prime }}$ and the negative measure $(m^{\prime }{)}^{-}$ must be disjoint. Since $\mu$ is made from $\nu$ by adding on a chunk of positive measure and a chunk of negative measure which are disjoint, we have $d_{TV}(\mu ,\nu )=-\left(m^{\prime }{)}^{-}\right(1)$. At this point, we only have one step left.

For the last step, because $\left(\right(m^{\prime }{)}^{+}+(m^{\prime }{)}^{-},b^{\prime })$ is an x-sa measure, we have $b^{\prime }+x\cdot \left(m^{\prime }{)}^{-}\right(1)\ge 0$. Also, because $b^{\prime }=\mu (h\nsim {\pi }^{\prime })$, our inequality turns into

$\mu (h\nsim {\pi }^{\prime })+x\cdot \left(m^{\prime }{)}^{-}\right(1)\ge 0$

$\mu (h\nsim {\pi }^{\prime })\ge -x\cdot \left(m^{\prime }{)}^{-}\right(1)$

$\mu (h\nsim {\pi }^{\prime })\ge x\cdot d_{TV}(\mu ,\nu )$

and this gets us our

$\forall \pi ,{\pi }^{\prime },\mu \in \Theta \left(\pi \right):\mu (h\nsim {\pi }^{\prime })\ge x\cdot {inf}_{\nu \in \Theta \left({\pi }^{\prime }\right)}{d}_{TV}(\mu ,\nu )$

result. We're done!

 

Proposition 3: If a utility function $U$ is bounded within $[0,x]$ and a belief function $\Theta$ is x-pseudocausal, then translating $\Theta$ to ${\Theta }^p$ (pseudocausal translation) fulfills $\forall \pi :{\Theta }^p\left(\pi \right)\left(U\right)=\Theta \left(\pi \right)\left(U\right)$.

Blessedly, this one is very easy. First, let's recap the translation of a belief function (assumed to be x-pseudocausal) from acausal to pseudocausal. It is

${\Theta }^p\left({\pi }^{\prime }\right):=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)$

So, applying this, we have

${\Theta }^p\left({\pi }^{\prime }\right)\left(U\right)=p{r}_{(A\times O{)}^{\omega }\ast }({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)\left(U\right)$

$=({\top }_{\Pi }⋉(\lambda \pi .u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left)\right)(\lambda \pi ,h.U(h\left)\right)={inf}_{\pi }{u}_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left(U\right)$

And then we recall that x-pseudocausality is $\forall \pi ,{\pi }^{\prime },U:u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left(U\right)\ge {\Theta }^x\left({\pi }^{\prime }\right)\left(U\right)$ Also, recall that since ${\Theta }^x\left({\pi }^{\prime }\right)\left(U\right):=\Theta \left({\pi }^{\prime }\right)(inf(U,x\left)\right)$, and our utility function is bounded in $[0,x]$, we get the statement $\forall \pi ,{\pi }^{\prime }:u_{\sim {\pi }^{\prime }}^1\left(\Theta \right(\pi \left)\right)\left(U\right)\ge \Theta \left({\pi }^{\prime }\right)\left(U\right)$ Additionally, $u_{{\pi }^{\prime }}^1\left(\Theta \right({\pi }^{\prime }\left)\right)=\Theta \left({\pi }^{\prime }\right)$. Therefore, the infinimum is attained by ${\pi }^{\prime }$ itself, and we get

$=\Theta \left({\pi }^{\prime }\right)\left(U\right)$

and we're done!

0 comments

Comments sorted by top scores.