Infra-Bayesian physicalism: proofs part II

[Vanessa Kosoy]

This post is an appendix to “Infra-Bayesian physicalism: a formal theory of naturalized induction”.

Proposition 2.16: Consider some ${\Gamma }_0$, ${\Gamma }_1$, $\Phi$ and $\Theta \in {\square }^c({\Gamma }_0\times {\Gamma }_1\times \Phi )$. Define $\pi :{\text{el}}^{{\Gamma }_0\times {\Gamma }_1}\to {\text{el}}^{{\Gamma }_0}$ by $\pi (y,z,\alpha ):=(y,\{y^{\prime }\in {\Gamma }_0\mid (y^{\prime },z)\in \alpha \left\}\right)$. Then, $$(\pi \times {\text{id}}_{\Phi }{)}_{\ast }{\text{Br}}_{{\Gamma }_0\times {\Gamma }_1}(\Theta )\subseteq {\text{pr}}_{{\text{el}}^{{\Gamma }_0}\times \Phi }{\text{Br}}_{{\Gamma }_0}(\Theta )\subseteq {\text{Br}}_{{\Gamma }_0}({\text{pr}}_{{\Gamma }_0\times \Phi }\Theta )$$

We can prove the second subset inclusion directly as a corollary of Proposition 2.10, just let the $t$ of Proposition 2.10 be the projection function ${\Gamma }_1\times \Phi \to \Phi$, so that just leaves the first subset inclusion direction. If you’ve seen the proofs so far, you know we do a thing where we try to show subset inclusion with expectations of functions and inequalities instead. And that the proofs all proceed by transforming the expectations until we get a maximum over contribution expectation values, and that’s always where the hard part of proving the inequalities shows up. So, let’s just get that part over with, an interested reader can work it out with previous proofs as a guide. Unusually, we’ll be keeping track of identity functions here.

Plugging in some $f$, and doing our usual activities to get every term into the appropriate form, we can get this result if we manage to show that $$\underset{{\theta }^{\prime }\in {\text{Br}}_{{\Gamma }_0\times {\Gamma }_1}\left(\Theta \right)}{max}(\pi \times {\text{id}}_{\Phi }{)}_{\ast }{\theta }^{\prime }(\lambda y_0{\alpha }_{0}x.f(y_0,x,{\alpha }_0))$$ $$\le \underset{\theta \in {\text{Br}}_{{\Gamma }_0}\left(\Theta \right)}{max}{\text{pr}}_{{\text{el}}^{{\Gamma }_0}\times \Phi }\theta (\lambda y_0{\alpha }_{0}x.f(y_0,x,{\alpha }_0\left)\right)$$ So, to establish this, we’ll show that, given some ${\theta }^{\prime }\in {\text{Br}}_{{\Gamma }_0\times {\Gamma }_1}\left(\Theta \right)$, we have $(\pi \times {\text{id}}_{{\Gamma }_1\times \Phi }{)}_{\ast }({\theta }^{\prime })\in {\text{Br}}_{{\Gamma }_0}(\Theta )$, and that $${\text{pr}}_{{\text{el}}^{{\Gamma }_0}\times \Phi }\left(\right(\pi \times {\text{id}}_{{\Gamma }_1\times \Phi }{)}_{\ast }{\theta }^{\prime })=(\pi \times {\text{id}}_{\Phi }{)}_{\ast }{\theta }^{\prime }$$ because, if we show that, then it means that ${\text{Br}}_{{\Gamma }_0}\left(\Theta \right)$ is a rich enough set for the right-hand side of the equation to match anything the left-hand-side can put out.

First off, $${\text{pr}}_{{\text{el}}^{{\Gamma }_0}\times \Phi }\left(\right(\pi \times {\text{id}}_{{\Gamma }_1\times \Phi }{)}_{\ast }{\theta }^{\prime })=(\pi \times {\text{id}}_{\Phi }{)}_{\ast }{\theta }^{\prime }$$ is pretty trivial to show. The only difference between the two processes is that the ${\Gamma }_1$ coordinate of ${\theta }^{\prime }$ is discarded immediately on the right-hand-side, and it’s preserved for one step and then discarded on the second step for the left-hand-side.

Now for our inequality of interest. Let ${\theta }^{\prime }\in {\text{Br}}_{{\Gamma }_0\times {\Gamma }_1}\left(\Theta \right)$, and we’re trying to show that $$(\pi \times {\text{id}}_{{\Gamma }_1\times \Phi }{)}_{\ast }({\theta }^{\prime })\in {\text{Br}}_{{\Gamma }_0}(\Theta )$$ First off, showing the support condition for $(\pi \times {\text{id}}_{{\Gamma }_1\times \Phi }{)}_{\ast }({\theta }^{\prime })$ which is somewhat nontrivial this time around. We start off with a guarantee that $(y_0,y_1)\in \alpha$. This happens iff $$y_0\in \left\{y_0^{\prime }|\right(y_0^{\prime },y_1)\in \alpha \}=\pi (y_0,y_1,\alpha {)}_{2^{{\Gamma }_0}}$$ And so, we get that $y_0\in {\alpha }_0$ is guaranteed for that pushforward, support condition established.

endofunction condition time. It’s important to remember that we want to treat ${\text{el}}^{{\Gamma }_0}$ as the computation side of things, and ${\Gamma }_1\times \Phi$ as the environment side of things, for our bridge transform we’re working with.$s:{\Gamma }_0\to {\Gamma }_0$ and $g:{\Gamma }_0\times {\Gamma }_1\times \Phi \to [0,1]$. Begin. $$(\pi \times {\text{id}}_{{\Gamma }_1\times \Phi }{)}_{\ast }{\theta }^{\prime }(\lambda y_0{y}_1{\alpha }_{0}x.{\chi }_{s\left(y_0\right)\in {\alpha }_0}g\left(s\right(y_0),y_1,x))$$ $$={\theta }^{\prime }(\lambda y_0{y}_1\alpha x.{\chi }_{s\left(y_0\right)\in \pi (y_0,\alpha ,y_1{)}_{2^{{\Gamma }_0}}}g(s\left(y_0\right),y_1,x\left)\right)$$ Let’s unpack precisely what that set is. $$={\theta }^{\prime }(\lambda y_0{y}_1\alpha x.{\chi }_{s\left(y_0\right)\in \left\{y_0^{\prime }|\right(y_0^{\prime },y_1)\in \alpha \}}g(s\left(y_0\right),y_1,x\left)\right)$$ $$={\theta }^{\prime }(\lambda y_0{y}_1\alpha x.{\chi }_{\left(s\right(y_0),y_1)\in \alpha }g(s\left(y_0\right),y_1,x\left)\right)$$ And we can rewrite the endofunction a little bit $$={\theta }^{\prime }(\lambda y_0{y}_1\alpha x.{\chi }_{(s\times {\text{id}}_{{\Gamma }_1})(y_0,y_1)\in \alpha }g((s\times {\text{id}}_{{\Gamma }_1})(y_0,y_1),x\left)\right)$$ And finally apply our endofunction condition, since we’ve now got the function in a form that’s treating $y_0,y_1$ as part of the computational universe… $$\le \Theta (\lambda y_0{y}_{1}x.g(y_0,y_1,x\left)\right)$$ And we’re done, this establishes our desired result. $■$

Proposition 2.17: $\text{Br}\left(\Theta \right)$ is a continuous function of $\Theta$.

The way this proof will work is by describing a composition of functions that makes $\text{Br}\left(\Theta \right)$ from $\Theta$, and then showing that each of these functions is continuous, if ${\text{el}}^{\Gamma }\times \Phi$ is a finite set.

Claim: The bridge transform of some $\Theta$ is equal to (using ${\chi }_{{\text{el}}^{\Gamma }}$ to denote restricting an ultradistribution to the event $y\in \alpha$ and ${\chi }_{{\text{el}}^{\Gamma }}^{-1}$ to denote the inverse of said function, mapping an ultradistribution on ${\text{el}}^{\Gamma }$ to the largest ultradistribution that could have produced it via restriction) $${\chi }_{{\text{el}}^{\Gamma }}\left(\bigcap _{s:\Gamma \to \Gamma }{s}^{\ast }\right({\chi }_{{\text{el}}^{\Gamma }}^{-1}\left({\iota }_{\ast }\right(p{r}^{\ast }\left(\Theta \right)\left)\right)\left)\right)$$ Breaking down the unfamilar notation, the type of $pr$ is ${\text{el}}^{\Gamma }\times \Phi \to \Gamma \times \Phi$, just the usual projection. That asterisk up top is pullback along that function. The type of $\iota$ is ${\text{el}}^{\Gamma }\times \Phi \to \Gamma \times 2^{\Gamma }\times \Phi$. And $s^{\ast }$ is pullback along the function $\Gamma \times 2^{\Gamma }\times \Phi \to \Gamma \times 2^{\Gamma }\times \Phi$ given by $(s,{\text{id}}_{2^{\Gamma }},{\text{id}}_{\Phi })$.

Let’s unpack the exact conditions that cause a $\theta$ to lie in the set $${\chi }_{{\text{el}}^{\Gamma }}\left(\bigcap _{s:\Gamma \to \Gamma }{s}^{\ast }\right({\chi }_{{\text{el}}^{\Gamma }}^{-1}\left({\iota }_{\ast }\right(p{r}^{\ast }\left(\Theta \right)\left)\right)\left)\right)$$ First off, a $\theta$ is in this set iff it is supported over the event $y\in \alpha$, and it lies in the set $$\bigcap _{s:\Gamma \to \Gamma }{s}^{\ast }\left({\chi }_{{\text{el}}^{\Gamma }}^{-1}\right({\iota }_{\ast }\left(p{r}^{\ast }\right(\Theta \left)\right)\left)\right)$$ Which occurs iff $\theta$ is supported over the event $y\in \alpha$, and for all $s:\Gamma \to \Gamma$, $\theta$ lies in the set $$s^{\ast }\left({\chi }_{{\text{el}}^{\Gamma }}^{-1}\right({\iota }_{\ast }\left(p{r}^{\ast }\right(\Theta \left)\right)\left)\right)$$ Which occurs iff $\theta$ is suported over the event $y\in \alpha$, and for all $s:\Gamma \to \Gamma$, $s_{\ast }\left(\theta \right)$ lies in the set $${\chi }_{{\text{el}}^{\Gamma }}^{-1}\left({\iota }_{\ast }\right(p{r}^{\ast }\left(\Theta \right)\left)\right)$$ Which occurs iff $\theta$ is supported over the event $y\in \alpha$, and for all $s:\Gamma \to \Gamma$, ${\chi }_{{\text{el}}^{\Gamma }}\left(s_{\ast }\right(\theta \left)\right)$ lies in the set ${\iota }_{\ast }\left(p{r}^{\ast }\right(\Theta \left)\right)$

Now, $\iota$ is just doing a little bit of type conversion, so we’re justified in ignoring it. Anways, the previous thing occurs iff $\theta$ is supported over the event $y\in \alpha$, and for all $s:\Gamma \to \Gamma$, $p{r}_{\ast }\left({\chi }_{{\text{el}}^{\Gamma }}\right(s_{\ast }\left(\theta \right)\left)\right)\in \Theta$.

Which happens iff $\theta$ is supported over the event $y\in \alpha$ and for all $s:\Gamma \to \Gamma$ and $g:\Gamma \times \Phi \to [0,1]$, $$p{r}_{\ast }\left({\chi }_{{\text{el}}^{\Gamma }}\right(s_{\ast }\left(\theta \right)\left)\right)(\lambda yx.g(y,x\left)\right)\le \Theta (\lambda yx.g(y,x\left)\right)$$ However, unpacking the left-hand side, we get $$p{r}_{\ast }\left({\chi }_{{\text{el}}^{\Gamma }}\right(s_{\ast }\left(\theta \right)\left)\right)(\lambda yx.g(y,x\left)\right)$$ $$={\chi }_{{\text{el}}^{\Gamma }}\left(s_{\ast }\right(\theta \left)\right)(\lambda y\alpha x.g(y,x\left)\right)$$ $$=s_{\ast }\left(\theta \right)(\lambda y\alpha x.{\chi }_{y\in \alpha }g(y,x\left)\right)$$ $$=\theta (\lambda y\alpha x.{\chi }_{s\left(y\right)\in \alpha }g(s\left(y\right),x\left)\right)$$ Which is the exact condition for $\theta$ to lie in the bridge transform. So, we have an equivalence.

Now, since we’ve phrased the bridge transform as $${\chi }_{{\text{el}}^{\Gamma }}\left(\bigcap _{s:\Gamma \to \Gamma }{s}^{\ast }\right({\chi }_{{\text{el}}^{\Gamma }}^{-1}\left({\iota }_{\ast }\right(p{r}^{\ast }\left(\Theta \right)\left)\right)\left)\right)$$ We just need to establish that when all the sets are finite, then pullbacks are continuous, pushforwards are continuous, un-restrictions are continuous, intersections are continuous, and restrictions are continuous. Then, this would just be a particularly fancy continuous function, and accordingly, if ${\Theta }_n$ limited to $\Theta$, then $\text{Br}\left({\Theta }_n\right)$ would limit to $\text{Br}\left(\Theta \right)$.

Let’s establish that when the sets are finite, pullbacks are continuous. Let $g:X\to Y$, and $Y$ and $X$ be finite sets, and $\psi \in \square Y$. Then, we have $$g^{\ast }\left(\psi \right)(\lambda x.f(x\left)\right):=\psi (\lambda y.\underset{x\in g^{-1}\left(y\right)}{max}f(x\left)\right)$$ With the convention that maximizing over the empty set produces a value of 0. That is an alternate phrasing of pullback. We can then go $$\underset{n\to \infty }{lim}d\left(g^{\ast }\right({\psi }_n),g^{\ast }(\psi \left)\right)=\underset{n\to \infty }{lim}\underset{f:X\to [0,1]}{sup}|g^{\ast }\left({\psi }_n\right)\left(f\right)-g^{\ast }\left(\psi \right)\left(f\right)|$$ $$=\underset{n\to \infty }{lim}\underset{f:X\to [0,1]}{sup}|{\psi }_n(\lambda y.\underset{x\in g^{-1}\left(y\right)}{max}f(x\left)\right)-\psi (\lambda y.\underset{x\in g^{-1}\left(y\right)}{max}f(x\left)\right)|$$ $$\le \underset{n\to \infty }{lim}\underset{h:Y\to [0,1]}{sup}|{\psi }_n\left(h\right)-\psi \left(h\right)|=\underset{n\to \infty }{lim}d({\psi }_n,\psi )=0$$ Admittedly, this isn’t quite what our usual modified KR metric usually looks like. The reason we can do this is because we’re just dealing with functions in $[0,1]$, so the norm part of the modified KR metric doesn’t matter, and since our sets are finite, we can say that all points are distance 1 from each other, so all functions are 1-Lipschitz, and then the two metrics coincide. So, pullback along any function is continuous.

For pushforward, it’s easy because, if $\psi \in \square X$, then we’ve got $$\underset{n\to \infty }{lim}d\left(g_{\ast }\right({\psi }_n),g_{\ast }(\psi \left)\right)=\underset{n\to \infty }{lim}\underset{h:Y\to [0,1]}{sup}|g_{\ast }\left({\psi }_n\right)\left(h\right)-g_{\ast }\left(\psi \right)\left(h\right)|$$ $$=\underset{n\to \infty }{lim}\underset{h:Y\to [0,1]}{sup}|{\psi }_n(\lambda x.h(g\left(x\right)\left)\right)-\psi (\lambda x.h(g\left(x\right)\left)\right)|$$ $$\le \underset{n\to \infty }{lim}\underset{f:X\to [0,1]}{sup}|{\psi }_n\left(f\right)-\psi \left(f\right)|=\underset{n\to \infty }{lim}d({\psi }_n,\psi )=0$$ For showing restrictions continuous, for the set $E\subseteq X$ that we’re updating on, $$\underset{n\to \infty }{lim}d\left({\chi }_E\right({\psi }_n),{\chi }_E(\psi \left)\right)=\underset{n\to \infty }{lim}\underset{f:X\to [0,1]}{sup}|{\chi }_E\left({\psi }_n\right)\left(f\right)-{\chi }_E\left(\psi \right)\left(f\right)|$$ $$=\underset{n\to \infty }{lim}\underset{f:X\to [0,1]}{sup}|{\psi }_n\left({\chi }_{x\in E}f\right(x\left)\right)-{\psi }_n\left({\chi }_{x\in E}f\right(x\left)\right)|$$ $$\le \underset{n\to \infty }{lim}\underset{f:X\to [0,1]}{sup}|{\psi }_n\left(f\right)-\psi \left(f\right)|=\underset{n\to \infty }{lim}d({\psi }_n,\psi )=0$$ For intersections… that will take a bit more work. We’ll have to use the equivalent formulation of closeness, that ${\psi }_n$ limits to $\psi$ iff the Hausdorff distance between the corresponding sets (according to the generalized KR measure) limits to 0. So, our task is to assume that ${\psi }_n$ limits to $\psi$, and ${\varphi }_n$ limits to $\varphi$, and show that ${\psi }_n\cap {\varphi }_n$ limits to $\psi \cap \varphi$. The bound we’ll manage to prove is that $$d({\psi }_n\cap {\varphi }_n,\psi \cap \varphi )\le |X|max\left(d\right({\psi }_n,\psi ),d({\varphi }_n,\varphi \left)\right)$$ Where $|X|$ is the number of elements in the finite set $X$. Here’s the basic argument. For any particular point in the set ${\psi }_n$, there’s a nearby point in $\psi$ (since the Hausdorff distance is low) with only $ϵ$ measure moved around or deleted. So, in particular, if all the measure moved or deleted was just deleted from ${\psi }_n$ instead, then that resulting contribution would be below the nearby contribution in $\psi$ that we picked, and so it would lie in $\psi$ as well due to downwards closure.

So, in particular, if ${\psi }_n$ and $\psi$ only have a Hausdorff distance of $ϵ$, then, taking any contribution in ${\psi }_n$ and subtracting $ϵ$ measure from \emph{all points} (if possible, if not, just remove measure till you’re at 0) is \emph{guaranteed} to make a point in $\psi$, and vice-versa.

And a corollary of that is that, given any contribution in ${\psi }_n\cap {\varphi }_n$, the “subtract $max\left(d\right({\psi }_n,\psi ),d({\varphi }_n,\varphi \left)\right)$ measure from each point” contribution is in $\psi$, also in $\varphi$, and at a maximum distance of $|X|max\left(d\right({\psi }_n,\psi ),d({\varphi }_n,\varphi \left)\right)$ from the original contribution. And this argument can be reversed to show that the limit of the intersections is the intersection of the limits (because hausdorff distance between the two goes to 0), so we do in fact have intersection being continuous.

And that just leaves un-restricting. Again, this will take a Hausdorff-distance argument. Fixing some contribution in ${\chi }_E^{-1}\left({\psi }_n\right)$, it can be broken down into an on-E part ${\theta }_{n,E}$, and an off-E part ${\theta }_{n,\neg E}$. When you restrict to E, then ${\theta }_{n,E}\in {\psi }_n$. Since ${\psi }_n$ is within $ϵ$ of $\psi$, there’s some ${\theta }_E\in \psi$ that’s within $ϵ$ of ${\theta }_{n,E}$. Then, let your point in ${\chi }_E^{-1}\left(\psi \right)$ be ${\theta }_E+{\theta }_{n,\neg E}$ (if there’s slightly more than 1 measure there, delete $ϵ$ measure from ${\theta }_{n,\neg E}$, or all the measure if there’s less than $ϵ$ present). It’s close to ${\theta }_{n,E}+{\theta }_{n,\neg E}$ because ${\theta }_{n,E}$ is close to ${\theta }_E$, the other component of it is unchanged, and maybe we deleted a little bit of excess measure which didn’t do much.

This line of argument shows that ${\psi }_n$ being close to the limit $\psi$ is sufficient to establish that the un-restriction of the two of them are comparably close together. So we have continuity for that, which is the last thing we needed.

Since we wrote the bridge transform as a sequence of continuous functions, we know it’s continuous (as long as all the involved sets are finite) $■$

Proposition 3.1: Let $X$ be a finite poset, $f:X\to R$ and $\Theta \in {\square }^{c}X$ downward closed. Define $f^{max}:X\to R$ by $f^{max}\left(x\right):={max}_{y\le x}f\left(y\right)$. Observe that $f^{max}$ is always non-decreasing. Then, $\Theta \left(f\right)=\Theta \left(f^{max}\right)$.

Proof: Pick a ${\theta }^{\prime }\in \Theta$ s.t. ${\theta }^{\prime }\left(f^{max}\right)=\Theta \left(f^{max}\right)$. Ie, a maximizing contribution. Let $k:X\to X$ be defined as $k:=\lambda x.{\text{argmax}}_{y\le x}f\left(y\right)$. Ie, it moves a point down to somewhere below it where it can attain the highest value according to $f$. Now, consider $k_{\ast }\left({\theta }^{\prime }\right)$. It’s present in $\Theta$ because $\Theta$ was, by assumption, downwards closed, and we just moved all the measure down.

Now, we have $$\Theta \left(f\right)=\underset{\theta \in \Theta }{max}\theta \left(f\right)\ge k_{\ast }\left({\theta }^{\prime }\right)\left(f\right)={\theta }^{\prime }(\lambda x.f(k\left(x\right)\left)\right)={\theta }^{\prime }(\lambda x.f({\text{argmax}}_{y\le x}f\left(y\right)\left)\right)$$ $$={\theta }^{\prime }(\lambda x.\underset{y\le x}{max}f(y\left)\right)={\theta }^{\prime }\left(f^{max}\right)=\Theta \left(f^{max}\right)\ge \Theta \left(f\right)$$ And so, all inequalities must be equalities, proving that $\Theta \left(f^{max}\right)\ge \Theta \left(f\right)$. In order, the connectives were: unpacking definitions, using downward closure to conclude that $k_{\ast }\left({\theta }^{\prime }\right)\in \Theta$, unpacking pushforwards, unpacking the definition of $k$, using that applying a function to the argmax of inputs to that function just makes the max of the function, folding the definition of $f^{max}$ back up, using that ${\theta }^{\prime }$ was selected to maximize $f^{max}$, and applying monotonicity. Done! $■$

Proposition 4.1: Consider some $\Gamma$, $\Phi$, a relation $Q\subseteq \Gamma \times \Phi$ and a PUCK $\Xi$ over $Q$. Let $\Theta :={\top }_{\Gamma }⋉\Xi$. Then, $$\text{Br}\left(\Theta \right)=[{\top }_{\Gamma }⋉({\text{sus}}^{\Theta }⋊\Xi ){]}^{\downarrow }=[{\top }_{\Gamma }⋉(Q^{-1}⋊\Xi ){]}^{\downarrow }$$

First off, I’m not terribly picky about variable ordering, so I’ll just write our desired proof target as $$\text{Br}\left(\Theta \right)=[{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }{]}^{\downarrow }=[{\top }_{\Gamma }⋉\Xi ⋉Q^{-1}{]}^{\downarrow }$$ The way we’ll do this is by establishing the following result. For all monotone $f^{\prime }:{\text{el}}^{\Gamma }\times \Phi \to [0,1]$, we have $$\text{Br}\left(\Theta \right)\left(f^{\prime }\right)\le [{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }]\left(f^{\prime }\right)\le [{\top }_{\Gamma }⋉\Xi ⋉Q^{-1}]\left(f^{\prime }\right)\le \text{Br}\left(\Theta \right)\left(f^{\prime }\right)$$ Why does that suffice? Well, assume hypothetically that the result held. Since the inequalities go in a circle, we have equality for all monotone functions. And then, for some non-monotone function $f$, we can go $$\text{Br}\left(\Theta \right)\left(f\right)=\text{Br}\left(\Theta \right)\left(f^{max}\right)=[{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }]\left(f^{max}\right)$$ $$=[{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }{]}^{\downarrow }(f^{max})=[{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }{]}^{\downarrow }\left(f\right)$$ and swap out ${\text{sus}}^{\Theta }$ for $Q^{-1}$ to show the other equality, and then we’d have equality of the three ultradistributions on all functions, so they’re equal.

For the equalities in the above equation, the first one arose because of Proposition 2.4 (bridge transforms are always downwards closed) and Proposition 3.1 (downwards-closed things let you swap out $f$ for $f^{max}$ and it doesn’t affect the value). The second equality arose because $f^{max}$ is a monotone function and by assumption, we have equality for monotone functions. The third equality would arise because taking the downwards closure doesn’t affect the expectation value of monotone functions. If you add a bunch of contributions made by measure flowing down, that’s just strictly worse from the perspective of a monotone function and doesn’t change expectation value. And the fourth equality arises from Proposition 3.1 again.

So, we just need to prove the following three inequalities, for monotone functions $f$. $$\text{Br}\left(\Theta \right)\left(f\right)\le [{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }]\left)\right(f)\le [{\top }_{\Gamma }⋉\Xi ⋉Q^{-1}\left]\right(f)\le \text{Br}(\Theta \left)\right(f)$$ The first one is easily addressable by Proposition 2.7. By proposition 2.7 and the definition of $\Theta$, we have $$\text{Br}\left(\Theta \right)\subseteq (\Theta ⋉{\text{sus}}^{\Theta }{)}^{\downarrow }=[{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }{]}^{\downarrow }$$ And so, for monotone functions $f$, we have $$\text{Br}\left(\Theta \right)\left(f\right)\le [{\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta }]\left)\right(f)$$ Done.

Now to show our second inequality. $$({\top }_{\Gamma }⋉\Xi ⋉{\text{sus}}^{\Theta })(\lambda y\alpha x.f(y,x,\alpha \left)\right)$$ $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.{\delta }_{{\text{sus}}^{\Theta }\left(x\right)}(\lambda \alpha .f(y,x,\alpha )\left)\right)$$ $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,{\text{sus}}^{\Theta }\left(x\right)\left)\right)$$ Unpack the definition of the set $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,\left\{y^{\prime }|\right(y^{\prime },x)\in \text{supp}\Theta \}\left)\right)$$ Unpack the definition of $\Theta$ $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,\left\{y^{\prime }|\right(y^{\prime },x)\in \text{supp}{\top }_{\Gamma }⋉\Xi \}\left)\right)$$ The condition $(y^{\prime },x)\in \text{supp}{\top }_{\Gamma }⋉\Xi$ is equivalent to $x\in \text{supp}\Xi \left(y^{\prime }\right)$. After all, if $x\in \text{supp}\Xi \left(y^{\prime }\right)$, the distribution ${\delta }_{y^{\prime }}$ lies in ${\top }_{\Gamma }$, so ${\delta }_{y^{\prime }}⋉\Xi$ would certify that $(y^{\prime },x)\in \text{supp}{\top }_{\Gamma }⋉\Xi$. And if $x\notin \text{supp}\Xi \left(y^{\prime }\right)$, then no matter the distribution in ${\top }_{\Gamma }$ or kernel selected from $\Xi$, if $y^{\prime }$ gets picked, then the kernel selected from $\Xi$ isn’t going to be making $x$ along with it. Since we have that iff characterization, we have $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,\{y^{\prime }|x\in \text{supp}\Xi (y^{\prime }\left)\right\}\left)\right)$$ $\Xi \left(y^{\prime }\right)$ is the union of a bunch of $k\left(y^{\prime }\right)$ for $k\in \Pi$ (and convex hull), so its support is equal to the union of the supports for the $k\left(y^{\prime }\right)$. $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,\{y^{\prime }|x\in \bigcup _{k\in \Pi }\text{supp}k(y^{\prime }\left)\right\}\left)\right)$$ Then, since each $k$ is a PoCK over $Q$, $k\left(y^{\prime }\right)$ is the restriction of some measure ${\varpi }^k$ to the set $Q\left(y\right)$, which will be written as ${\chi }_{Q\left(y^{\prime }\right)}{\varpi }^k$. $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,\{y^{\prime }|x\in \bigcup _{k\in \Pi }\text{supp}({\chi }_{Q\left(y^{\prime }\right)}{\varpi }^k\left)\right\}\left)\right)$$ And now we’re about to get an inequality.$f$ is monotone, so making the associated set bigger (easier to fulfill the defining condition) should always increase the value of $f$, and by monotonicity, increase the expectation value, so we get $$\le ({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,\{y^{\prime }|x\in Q(y^{\prime }\left)\right\}\left)\right)$$ Then restate $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,\left\{y^{\prime }|\right(x,y^{\prime })\in Q\}\left)\right)$$ $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.f(y,x,Q^{-1}\left(x\right)\left)\right)$$ And pack back up as a semidirect product. $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .f(y,x,\alpha )\left)\right)$$ $$=({\top }_{\Gamma }⋉\Xi ⋉Q^{-1})(\lambda y\alpha x.f(y,x,\alpha \left)\right)$$ And we have our second $\le$ inequality established!

Now, onto the third inequality. $$({\top }_{\Gamma }⋉\Xi ⋉Q^{-1})(\lambda y\alpha x.f(y,x,\alpha \left)\right)$$ Unpack the semidirect products $$={\top }_{\Gamma }(\lambda y.\Xi (y\left)\right(\lambda x.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .f(y,x,\alpha \left)\right)\left)\right)$$ And what top means $$=\underset{y\in \Gamma }{max}\Xi \left(y\right)(\lambda x.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .f(y,x,\alpha )\left)\right)$$ And as for $\Xi$… well, each $\Xi \left(y\right)$ is the convex hull of the various $k\left(y\right)$, for $k\in \Pi$. So, the expectation for $\Xi \left(y\right)$ is the maximum expectation for the various $k\left(y\right)$, so we can rewrite as $$=\underset{y\in \Gamma }{max}\underset{k\in \Pi }{max}k\left(y\right)(\lambda x.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .f(y,x,\alpha )\left)\right)$$ Pick a particular $y^{\ast }$ and $k^{\ast }$ that attain the maximal value $$=k^{\ast }\left(y^{\ast }\right)(\lambda x.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .f(y^{\ast },x,\alpha )\left)\right)$$ Reexpress a little bit $$={\delta }_{y^{\ast }}(\lambda y.k^{\ast }(y\left)\right(\lambda x.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .f(y,x,\alpha \left)\right))$$ And pack this back up as a semidirect product $$=({\delta }_{y^{\ast }}⋉k^{\ast }⋉Q^{-1})(\lambda y\alpha x.f(y,x,\alpha \left)\right)$$ And then we’ll be showing that this contribution lies in $\text{Br}\left(\Theta \right)$. Once we’ve done that, we can go $$\le \underset{{\theta }^{\prime }\in \text{Br}\left(\Theta \right)}{max}{\theta }^{\prime }(\lambda y\alpha x.f(y,x,\alpha \left)\right)$$ $$=\text{Br}\left(\Theta \right)(\lambda y\alpha x.f(y,x,\alpha \left)\right)$$ And we’d be done, having proven the third inequality and the last one to finish up the proof. So, now our proof target switches to showing that $({\delta }_{y^{\ast }}⋉k^{\ast }⋉Q^{-1})\in \text{Br}\left(\Theta \right)$. We can show this if we show the support condition and the endofunction condition.

For the support condition, we have $$({\delta }_{y^{\ast }}⋉k^{\ast }⋉Q^{-1})(\lambda y\alpha x.{\chi }_{y\notin \alpha })$$ $$={\delta }_{y^{\ast }}(\lambda y.k^{\ast }(y\left)\right(\lambda x.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .{\chi }_{y\notin \alpha })\left)\right)$$ $$={\delta }_{y^{\ast }}(\lambda y.k^{\ast }(y\left)\right(\lambda x.{\chi }_{y\notin Q^{-1}\left(x\right)}\left)\right)$$ $$=k^{\ast }\left(y^{\ast }\right)(\lambda x.{\chi }_{y^{\ast }\notin Q^{-1}\left(x\right)})$$ And then we use that the $k^{\ast }\left(y^{\ast }\right)$ are all of the form “take this measure, restrict it to $Q\left(y^{\ast }\right)$”, to get $$=\left({\chi }_{Q\left(y^{\ast }\right)}{\varpi }^{k^{\ast }}\right)(\lambda x.{\chi }_{y^{\ast }\notin Q^{-1}\left(x\right)})$$ $$={\varpi }^{k^{\ast }}(\lambda x.{\chi }_{x\in Q\left(y^{\ast }\right)}{\chi }_{y^{\ast }\notin Q^{-1}\left(x\right)})$$ Unpacking the definitions, we get $$={\varpi }^{k^{\ast }}(\lambda x.{\chi }_{(x,y^{\ast })\in Q}{\chi }_{(x,y^{\ast })\notin Q})=0$$ And so, this contribution is indeed supported on $(y,\alpha )$ pairs s.t. $y\in \alpha$.

Now for the endofunction condition. As usual, fix an $s$ and a $g$. $$({\delta }_{y^{\ast }}⋉k^{\ast }⋉Q^{-1})(\lambda y\alpha x.{\chi }_{s\left(y\right)\in \alpha }g(s\left(y\right),x\left)\right)$$ Unpack the semidirect product $$={\delta }_{y^{\ast }}(\lambda y.k^{\ast }(y\left)\right(\lambda x.{\delta }_{Q^{-1}\left(x\right)}(\lambda \alpha .{\chi }_{s\left(y\right)\in \alpha }g(s\left(y\right),x\left)\right)\left)\right)$$ Plug in the dirac-deltas $$=k^{\ast }\left(y^{\ast }\right)(\lambda x.{\chi }_{s\left(y^{\ast }\right)\in Q^{-1}\left(x\right)}g(s\left(y^{\ast }\right),x\left)\right)$$ Reexpress the set membership criterion a bit $$=k^{\ast }\left(y^{\ast }\right)(\lambda x.{\chi }_{x\in Q\left(s\right(y^{\ast }\left)\right)}g(s\left(y^{\ast }\right),x\left)\right)$$ And the contribution at the start $$=\left({\chi }_{Q\left(y^{\ast }\right)}{\varpi }^{k^{\ast }}\right)(\lambda x.{\chi }_{x\in Q\left(s\right(y^{\ast }\left)\right)}g(s\left(y^{\ast }\right),x\left)\right)$$ Distribute it in as an indicator function. $$={\varpi }^{k^{\ast }}(\lambda x.{\chi }_{x\in Q\left(y^{\ast }\right)}{\chi }_{x\in Q\left(s\right(y^{\ast }\left)\right)}g(s\left(y^{\ast }\right),x\left)\right)$$ Pull the other indicator function out. $$=\left({\chi }_{Q\left(s\right(y^{\ast }\left)\right)}{\varpi }^{k^{\ast }}\right)(\lambda x.{\chi }_{x\in Q\left(y^{\ast }\right)}g(s\left(y^{\ast }\right),x\left)\right)$$ Rewrite with $k^{\ast }$ $$=k^{\ast }\left(s\right(y^{\ast }\left)\right)(\lambda x.{\chi }_{x\in Q\left(y^{\ast }\right)}g(s\left(y^{\ast }\right),x\left)\right)$$ Use an inequality to get rid of the indicator function $$\le k^{\ast }\left(s\right(y^{\ast }\left)\right)(\lambda x.g(s\left(y^{\ast }\right),x\left)\right)$$ Rewrite it a bit $$={\delta }_{s\left(y^{\ast }\right)}(\lambda y.k^{\ast }(y\left)\right(\lambda x.g(y,x)\left)\right)$$ Swap out $k^{\ast }\left(y\right)$ for $\Xi \left(y\right)$, the latter is larger $$\le {\delta }_{s\left(y^{\ast }\right)}(\lambda y.\Xi (y\left)\right(\lambda x.g(y,x)\left)\right)$$ Swap out ${\delta }_{s\left(y^{\ast }\right)}$ for ${\top }_{\Gamma }$, the latter is larger $$\le {\top }_{\Gamma }(\lambda y.\Xi (y\left)\right(\lambda x.g(y,x)\left)\right)$$ $$=({\top }_{\Gamma }⋉\Xi )(\lambda yx.g(y,x\left)\right)$$ Abbreviate $$=\Theta (\lambda yx.g(y,x\left)\right)$$ And bam, endofunction condition is shown, the entire proof goes through now. $■$

Corollary 4.3: Suppose that for any $d\in D$ and $\pi :H\to A$ s.t. $d\in \text{supp}W\left(\pi \right)$, it holds that $dC\pi$. That is, the observations $W$ predicts to receive from the computer are consistent with the chosen policy. Let $L:D\to R$ be a Cartesian loss function and $\pi :H\to A$ a policy. Then, $$\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W)\cap {\text{C}}_{\text{fair}}^{\pi })\left(L^{\text{phys}}\right)=W(\pi ;L)$$

I’m going to be proceeding very cautiously here. First off, make our $\pi$ value visually distinct by swapping it out for ${\pi }^{\ast }$ $$\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W)\cap {\text{C}}_{\text{fair}}^{{\pi }^{\ast }})\left(L^{\text{phys}}\right)$$ Now, by the identifications we made earlier, we can identify $\Gamma$ with $A^H$, the space of policies. Using that to unpack the function a little bit, we have $$=\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W)\cap {\text{C}}_{\text{fair}}^{{\pi }^{\ast }})(\lambda \pi \alpha .L^{\text{phys}}(\pi ,\alpha \left)\right)$$ Now, we note that intersecting with top of a particular set is equivalent to updating on the indicator function for that set. Using definition 1.5 to unpack ${\text{C}}_{\text{fair}}^{{\pi }^{\ast }}$, we get $$=\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W\left)\right)(\lambda \pi \alpha .{\chi }_{\forall h\in H_{\pi ,\alpha }:G^{\pi }\left(h\right)={\pi }^{\ast }\left(h\right)}{L}^{\text{phys}}(\pi ,\alpha \left)\right)$$ Apply that $G^{\pi }\left(h\right)$ is “what would the agent do on $h$ if the agent is copying the behavior of $\pi$”, so we can rephrase as: $$=\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W\left)\right)(\lambda \pi \alpha .{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}{L}^{\text{phys}}(\pi ,\alpha \left)\right)$$ Pull off the projection, and use $d$ for a destiny in $D$. $$=\text{Br}\left({\Theta }_W\right)(\lambda \pi \alpha d.{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}{L}^{\text{phys}}(\pi ,\alpha \left)\right)$$ At this point, we use that ${\Theta }_W:={\top }_{\Gamma }⋉W$, and that $W$ is a PUCK over $Q_0$ and Proposition 4.1 to go $$=[{\top }_{\Gamma }⋉W⋉Q_0^{-1}{]}^{\downarrow }(\lambda \pi \alpha d.{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}{L}^{\text{phys}}(\pi ,\alpha ))$$ Before we can remove the downwards closure, we’ll want to verify the function is monotone. So, we’ll want to start unpacking the physicalist loss next. Applying definition 3.1, and using $d^{\prime }$ instead of $g$ to remember it’s a destiny, we have $$=[{\top }_{\Gamma }⋉W⋉Q_0^{-1}{]}^{\downarrow }(\lambda \pi \alpha d.{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}\underset{ha:ha\in X_{\pi ,\alpha }}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ Next up is unpacking $X_{\pi ,\alpha }$. Using definition 3.1, it’s $$=[{\top }_{\Gamma }⋉W⋉Q_0^{-1}{]}^{\downarrow }(\lambda \pi \alpha d.{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,\alpha }\times A\wedge (\forall {\pi }^{\prime }\in \alpha :G^{{\pi }^{\prime }}(h)=a)}{min}\underset{d^{\prime \prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ At this point, we can, again, treat $G^{{\pi }^{\prime }}\left(h\right)$ the same as ${\pi }^{\prime }\left(h\right)$. $$=[{\top }_{\Gamma }⋉W⋉Q_0^{-1}{]}^{\downarrow }(\lambda \pi \alpha d.{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,\alpha }\times A\wedge (\forall {\pi }^{\prime }\in \alpha :{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime \prime }}{max}L\left(d^{\prime }\right))$$ And now we need to take a moment to show that $H_{\pi ,\alpha }$ gets smaller when $\alpha$ gets larger. Applying definition 1.5, the event $h\in H_{\pi ,\alpha }$ unpacks as $$(\forall h^{\prime }a⊏h,{\pi }^{\prime }\in \alpha :G^{{\pi }^{\prime }}(h^{\prime })=a)\wedge (\exists d^{\prime }:h⊏d^{\prime }\wedge d^{\prime }C\pi )$$ Now, if $\alpha$ becomes a larger set, then it gets harder for the first condition to be fulfilled, so the set $H_{\pi ,\alpha }$ shrinks. Now, since this happens, it means that if $\alpha$ gets bigger, it gets more difficult for the prerequisite of the implication in the indicator function to be fulfilled, so the implication is more likely to hold. Further, the minimization is taking place over a smaller set, so the loss goes up. So our function is monotone in $\alpha$, and we can remove the downwards closure. $$=({\top }_{\Gamma }⋉W⋉Q_0^{-1})(\lambda \pi \alpha d.{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,\alpha }\times A\wedge (\forall {\pi }^{\prime }\in \alpha :{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime \prime }}{max}L\left(d^{\prime }\right))$$ Unpacking the semidirect product, it is $$={\top }_{\Gamma }(\lambda \pi .W(\pi \left)\right(\lambda d.{\delta }_{Q_0^{-1}\left(d\right)}(\lambda \alpha .{\chi }_{\forall h\in H_{\pi ,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,\alpha }\times A\wedge (\forall {\pi }^{\prime }\in \alpha :{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right)\left)\right))$$ Substituting in the dirac-delta everywhere that $\alpha$ is, we get $$={\top }_{\Gamma }(\lambda \pi .W(\pi \left)\right(\lambda d.{\chi }_{\forall h\in H_{\pi ,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,Q_0^{-1}\left(d\right)}\times A\wedge (\forall {\pi }^{\prime }\in Q_0^{-1}(d):{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right)\left)\right)$$ Now, $Q_0^{-1}\left(d\right)$ is the set of policies ${\pi }^{\prime }$ s.t. ${\pi }^{\prime }{Q}_{0}d$. The “this policy is consistent with this destiny” relation. Also let’s swap out ${\top }_{\Gamma }$ for maximization $$=\underset{\pi }{max}W\left(\pi \right)(\lambda d.{\chi }_{\forall h\in H_{\pi ,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,Q_0^{-1}\left(d\right)}\times A\wedge (\forall {\pi }^{\prime }{Q}_{0}d:{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ Now, we’re going to try to address that minimum, and show that the only $ha$ that fulfill the conditions are exactly those $ha⊑d$. This requires showing that $ha⊑d$ is a sufficient condition to fulfill the relevant properties, and then to show that $ha⋢d$ implies a failure of one of the properties.

So, first up. Assume $ha⊑d$. Then, for any ${\pi }^{\prime }$, $d{Q}_0{\pi }^{\prime }$ and $ha⊑d$ \emph{must} imply that ${\pi }^{\prime }\left(h\right)=a$, that’s what policy consistency means. Also, $h\in H_{\pi ,Q_0^{-1}\left(d\right)}$ unpacks as the two conditions $$\forall h^{\prime }{a}^{\prime },{\pi }^{\prime }:h^{\prime }{a}^{\prime }⊏h\wedge d{Q}_0{\pi }^{\prime }\to {\pi }^{\prime }\left(h^{\prime }\right)=a^{\prime }$$ $$\exists d^{\prime }:h⊏d^{\prime }\wedge d^{\prime }C\pi$$ As for the first condition,clearly, if ${\pi }^{\prime }$ is consistent with $d$, it’s consistent with $ha$ because $ha⊑d$, and so it must be consistent with any prefix of $ha$, so the first condition holds.

For the second condition, $d$ is a valid choice, because we assumed $ha⊑d$, and $dC\pi$ occurs always, because $W\left(\pi \right)$ always being supported on $d$ s.t.$dC\pi$ was one of our problem assumptions.

So, we have one implication direction down. Now for the reverse implication direction. Assume $ha⋢d$. Then there are two possibilities. the first possibility is that $ha$ first diverges from $d$ on an observation. The second possibility is that $ha$ first diverges from $d$ on an action.

For the first possibility, it’s possible to make two policies which are consistent with $d$ but also differ in their actions on history $h$, because $h$ isn’t a prefix of $d$ if $ha$ first differs from $d$ on an observation.

For the second possibility, it’s ruled out by either the condition for $h\in H_{\pi ,Q_0^{-1}\left(d\right)}$ that goes $$\forall h^{\prime }{a}^{\prime },{\pi }^{\prime }:h^{\prime }{a}^{\prime }⊏h\wedge {\pi }^{\prime }{Q}_{0}d\to {\pi }^{\prime }\left(h^{\prime }\right)=a^{\prime }$$ or the extra condition that $$\forall {\pi }^{\prime }:{\pi }^{\prime }{Q}_{0}d\to {\pi }^{\prime }\left(h\right)=a$$ applied to the first a-history prefix that deviates from $d$, because ${\pi }^{\prime }{Q}_{0}d$ implies that ${\pi }^{\prime }\left(h^{\prime }\right)$ must be the action which $d$ dictates, not the action $a^{\prime }$ that deviates from $d$.

And that establishes the other direction of the iff statement.

Thus, we can swap out our fancy minimization with just minimizing over the $ha⊑d$. $$=\underset{\pi }{max}W\left(\pi \right)(\lambda d.{\chi }_{\forall h\in H_{\pi ,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha⊑d}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ This minimization is attained by selecting $d$ itself. So then it turns into $$=\underset{\pi }{max}W\left(\pi \right)(\lambda d.{\chi }_{\forall h\in H_{\pi ,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ At this point, what we’ll do is show that an upper bound and lower bound on the value of this term is the same. Going from upper bound to lower bound, it’s starting out with $$W\left({\pi }^{\ast }\right)(\lambda d.L(d\left)\right)$$ At this point, we’ll use that $W$ is a PUCK, so there’s a set $E$ of environments $e$ (PoCK’s) that $W$ is generated from, so we can go: $$=\underset{e\in E}{max}e\left({\pi }^{\ast }\right)(\lambda d.L(d\left)\right)$$ $$=\underset{\pi }{max}\underset{e\in E}{max}e\left({\pi }^{\ast }\right)(\lambda d.{\chi }_{d{Q}_0\pi }L(d\left)\right)$$ $$=\underset{\pi }{max}\underset{e\in E}{max}\left({\chi }_{Q_0\left({\pi }^{\ast }\right)}{\varpi }^e\right)(\lambda d.{\chi }_{d{Q}_0\pi }L(d\left)\right)$$ $$=\underset{\pi }{max}\underset{e\in E}{max}{\varpi }^e(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}{\chi }_{d{Q}_0\pi }L(d\left)\right)$$ Now pull the indicator function back out. $$=\underset{\pi }{max}\underset{e\in E}{max}\left({\chi }_{Q_0\left(\pi \right)}{\varpi }^e\right)(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)$$ $$=\underset{\pi }{max}\underset{e\in E}{max}e\left(\pi \right)(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)$$ $$=\underset{\pi }{max}W\left(\pi \right)(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)$$ Now we must show that this is a looser constraint than what was previously in our indicator function to proceed further. So our next order of business is showing that, certainly, $$\forall h\in H_{\pi ,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)\to d{Q}_0{\pi }^{\ast }$$ Let $h$ be one of the history prefixes of some $d$ in the support of $W\left(\pi \right)$. The two conditions for $h\in H_{\pi ,Q_0^{-1}\left(d\right)}$ are fulfilled, because they are $$\forall h^{\prime },a^{\prime },{\pi }^{\prime }:h^{\prime }{a}^{\prime }⊏h\wedge d{Q}_0{\pi }^{\prime }\to {\pi }^{\prime }\left(h^{\prime }\right)=a^{\prime }$$ $$\exists d^{\prime }:h⊏d^{\prime }\wedge d^{\prime }C\pi$$ For the first condition, if $h^{\prime }{a}^{\prime }⊏h$, then $h^{\prime }{a}^{\prime }⊏d$, and so if ${\pi }^{\prime }$ is consistent with $d$, it must take the same action in response to $h^{\prime }$, the action that $d$ commands, $a^{\prime }$. So that’s fulfilled. For the second condition, let $d^{\prime }$ be $d$. $h⊏d$ holds, and so $dC\pi$ holds certainly, because $W\left(\pi \right)$ is supported on $d$ s.t. $dC\pi$.

So, for all $d$ in the support of $W\left(\pi \right)$, $h⊏d\to h\in H_{\pi ,Q_0^{-1}\left(d\right)}$. Since we assumed our forall statement as prerequisite, this means that for all $h⊏d$, $\pi \left(h\right)={\pi }^{\ast }\left(h\right)$. And $d{Q}_0\pi$ means $\forall ha⊑d:\pi \left(h\right)=a$. Since ${\pi }^{\ast }\left(h\right)$ mimics $\pi \left(h\right)$ for all history prefixes of $d$, this means $\forall ha⊑d:{\pi }^{\ast }\left(h\right)=a$, ie $d{Q}_0{\pi }^{\ast }$.

So, since this is a looser constraint, when we were previously at $$=\underset{\pi }{max}W\left(\pi \right)(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)$$ we can proceed further to $$\ge \underset{\pi }{max}W\left(\pi \right)(\lambda d.{\chi }_{\forall h\in H_{\pi ,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ Which is our value we’re trying to sandwich. Now, at this point, plug in ${\pi }^{\ast }$ and get $$\ge W\left({\pi }^{\ast }\right)(\lambda d.{\chi }_{\forall h\in H_{{\pi }^{\ast },Q_0^{-1}\left(d\right)}:{\pi }^{\ast }\left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ $$=W\left({\pi }^{\ast }\right)(\lambda d.L(d\left)\right)$$ And bam, we’ve sandwiched our term between $W\left({\pi }^{\ast }\right)\left(L\right)$ on both sides, and so the result follows. $■$

Proposition 4.2: Let $X$, $Y$ and $Z$ be finite sets, $Q\subseteq Y\times X$ a relation, $\kappa :Y\to {\Delta }^c(X\times Z)$ a $Z$-PoCK over $Q$ and $\Theta \in {\square }^{c}Y$. Then, there exist $\mu \in {\Delta }^{c}Z$ and $\varphi :Z\times Y\to {\Delta }^{c}X$ s.t. for all $z$, $\lambda y.\varphi (z,y)$ is a PoCK over $Q$, and for all $y\in Y$, $\kappa \left(y\right)=(\lambda z.\varphi (z,y\left)\right)⋊\mu$. Moreover, suppose that $({\mu }_1,{\varphi }_1)$ and $({\mu }_2,{\varphi }_2)$ are both as above. Then, $${\mu }_1⋉\Theta ⋉{\varphi }_1={\mu }_2⋉\Theta ⋉{\varphi }_2$$

Our first order of business is establishing that there’s even a $\mu$ and $\varphi$ that has those effects at all. Here’s a way to define them. $$\mu \left(z\right):=\underset{y^{\prime }\in Y}{max}\sum _{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })$$ Where ${\varpi }^{\kappa }$ is the measure on $Z\times X$ that $\kappa$ is associated with, ie, $\kappa \left(y\right)={\chi }_{Q\left(y\right)}{\varpi }^{\kappa }$ must be true for some ${\varpi }^{\kappa }$ because $\kappa$ is a Z-PoCK over Q. And, $\varphi$ will be defined as: $$\varphi (y,z)\left(x\right):=\frac{{\chi }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(z,x)}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}$$ With those definitions in place, it’s easy to establish that $\mu ⋉(\lambda z.\varphi (y,z\left)\right)=\kappa \left(y\right)$. We can just fix an arbitrary $x,z$ pair and go $$\kappa \left(y\right)(x,z)={\chi }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(z,x)=\underset{y^{\prime }\in Y}{max}\sum _{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })\cdot \frac{{\chi }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(z,x)}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}$$ $$=\mu \left(z\right)\cdot \varphi (y,z)\left(x\right)=(\mu ⋉(\lambda z^{\prime }.\varphi (y,z^{\prime })\left)\right)(x,z)$$ And we’re done with showing that such functions exist in the first place. Well, as long as we check that $\mu$ and $\varphi$ behave accordingly. First off, $\mu$ being a contribution follows from ${\varpi }^{\kappa }$ being a Z-polycontribution, and the definition of Z-polycontributions. Also, to show that $(\lambda y.\varphi (y,z\left)\right)$ is a PoCK over Q, we need to show that there’s a ${\varpi }^{\varphi ,z}$ s.t. $\varphi (y,z)={\chi }_{Q\left(y\right)}{\varpi }^{\varphi ,z}$, and that always has 1 or less measure.

In order to do this, define $${\varpi }^{\varphi ,z}:=\frac{1}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}p{r}_X\left({\chi }_{\left\{z\right\}\times X}{\varpi }^{\kappa }\right)$$ Clearly, you get $\varphi (y,z)$ from restricting this to $Q\left(y\right)$, because we have $$\left({\chi }_{Q\left(y\right)}{\varpi }^{\varphi ,z}\right)\left(x\right)=\frac{1}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}{\chi }_{Q\left(y\right)}\left(p{r}_X\right({\chi }_{\left\{z\right\}\times X}{\varpi }^{\kappa }\left)\right)\left(x\right)$$ $$=\frac{{\chi }_{Q\left(y\right)}\left(p{r}_X\right({\chi }_{\left\{z\right\}\times X}{\varpi }^{\kappa }\left)\right)\left(x\right)}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}=\frac{{\chi }_{x\in Q\left(y\right)}p{r}_X\left({\chi }_{\left\{z\right\}\times X}{\varpi }^{\kappa }\right)\left(x\right)}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}$$ $$=\frac{{\chi }_{x\in Q\left(y\right)}{\sum }_{z^{\prime }}\left({\chi }_{\left\{z\right\}\times X}{\varpi }^{\kappa }\right)(x,z^{\prime })}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}=\frac{{\chi }_{x\in Q\left(y\right)}{\sum }_{z^{\prime }}{\chi }_{z^{\prime }=z}{\varpi }^{\kappa }(x,z^{\prime })}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}$$ $$=\frac{{\chi }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(x,z)}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}=\varphi (y,z)\left(x\right)$$ And we’re done. And also, the measure is $\le 1$, because $$\sum _{x\in Q\left(y\right)}{\varpi }^{\varphi ,z}\left(x\right)=\sum _{x\in Q\left(y\right)}\frac{p{r}_X\left({\chi }_{\left\{z\right\}\times X}{\varpi }^{\kappa }\right)\left(x\right)}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })}$$ and, skipping over a few routine steps, $$=\frac{{\sum }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(x,z)}{{max}_{y^{\prime }\in Y}{\sum }_{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(x^{\prime },z)}$$ $$\le \frac{{\sum }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(x,z)}{{\sum }_{x^{\prime }\in Q\left(y\right)}{\varpi }^{\kappa }(x^{\prime },z)}=1$$ And we’re done, we figured out how to decompose $\kappa$ into $\mu$ and $\varphi$.

Now for the second half of the proof. The first thing to establish is that, for all $y,z$, we have ${\mu }_1\left(z\right)\cdot {\varphi }_1(y,z)={\mu }_2\left(z\right)\cdot {\varphi }_2(y,z)$. This occurs because, for all $x$, $${\mu }_1\left(z\right)\cdot {\varphi }_1(y,z)\left(x\right)=({\mu }_1⋉(\lambda z.{\varphi }_1(y,z)\left)\right)(x,z)=\kappa \left(y\right)(x,z)$$ And then by symmetry, the exact same holds for ${\mu }_2$ and ${\varphi }_2$, both were declared to be equal to $\kappa$. Now that this result is in place, we can begin. $$({\mu }_1⋉\Theta ⋉{\varphi }_1)(\lambda xyz.f(x,y,z\left)\right)$$ $$={\mu }_1(\lambda z.\Theta (\lambda y.{\varphi }_1(y,z)(\lambda x.f(x,y,z\left)\right)\left)\right)$$ Now, we do something odd. We can reexpress this as $$=C(\lambda z.{\mu }_1(z)\cdot \Theta (\lambda y.{\varphi }_1\left(y\right)(\lambda x.f(x,y,z\left)\right)\left)\right)$$ Basically, what’s going on here is that we can swap out the contribution ${\mu }_1$ for the counting measure $C$ (1 measure on each distinct point) and just scale down the expectation values accordingly. It’s pretty much the same way that you can think of ${\sum }_x\mu \left(x\right)f\left(x\right)$ (expectation of $f$ w.r.t $\mu$) as ${\sum }_{x}1\cdot \mu \left(x\right)f\left(x\right)$ (expectation of $\mu \cdot f$ w.r.t the counting measure). Now, since $\Theta$ is homogenous, we can move constants in or out of it, to get $$=C(\lambda z.\Theta (\lambda y.{\mu }_1\left(z\right)\cdot {\varphi }_1(y,z)(\lambda x.f(x,y,z\left)\right)\left)\right)$$ Now, at this point, we can use that ${\mu }_1\left(z\right)\cdot {\varphi }_1(y,z)={\mu }_2\left(z\right)\cdot {\varphi }_2(y,z)$, to get $$=C(\lambda z.\Theta (\lambda y.{\mu }_2\left(z\right)\cdot {\varphi }_2(y,z)(\lambda x.f(x,y,z\left)\right)\left)\right)$$ And just back up and reverse everything. $$=C(\lambda z.{\mu }_2(z\left)\Theta \right(\lambda y.{\varphi }_2(y,z)(\lambda x.f(x,y,z\left)\right)\left)\right)$$ $$={\mu }_2(\lambda z.\Theta (\lambda y.{\varphi }_2\left(y\right)(\lambda x.f(x,y,z\left)\right)\left)\right)$$ $$=({\mu }_2⋉\Theta ⋉{\varphi }_2)(\lambda xyz.f(x,y,z\left)\right)$$ And we’re done! $■$

Lemma 4: Let $X$, $Y$ and $Z$ be finite sets, $Q\subseteq Y\times X$ a relation, ${\Xi }_1,{\Xi }_2:Y\to {\square }^c(X\times Z)$ $Z$-PUCKs over $Q$, $\Theta \in {\square }^{c}Y$ and $p\in [0,1]$. Then, $p{\Xi }_1+(1-p){\Xi }_2$ is also a $Z$-PUCK over $Q$, and $$\Theta \ast (p{\Xi }_1+(1-p\left){\Xi }_2\right)\subseteq p(\Theta \ast {\Xi }_1)+(1-p)(\Theta \ast {\Xi }_2)$$

Our first order of business is establishing that the mix of Z-PUCK’s over Q is a Z-PUCK over Q. Here’s what we’ll do. We’ll define a family of kernels, show that they’re all Z-PoCK’s, and that said family makes a Z-PUCK that’s equal to the mix of ${\Xi }_1$ and ${\Xi }_2$.

So, let ${\Pi }_1$ be the set of Z-PoCK’s associated with ${\Xi }_1$, and ${\Pi }_2$ be the set of Z-PoCK’s associated with ${\Xi }_2$. Elements of these sets are ${\kappa }_1$ and ${\kappa }_2$. Define $\Pi$ as $\{p{\kappa }_1+(1-p){\kappa }_2|{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2\}$.

By Definition 4.5, in order to establish that these are Z-PoCK’s over Q, we need to make an appropriate choice of $\varpi$. In particular, the $\varpi$ associated with $\kappa =p{\kappa }_1+(1-p){\kappa }_2$ is ${\varpi }^{\kappa }:=p{\varpi }^{{\kappa }_1}+(1-p){\varpi }^{{\kappa }_2}$. It fufills definition 4.5 because $$\kappa \left(y\right)(x,z)=(p{\kappa }_1+(1-p\left){\kappa }_2\right)\left(y\right)(x,z)=p{\kappa }_1\left(y\right)(x,z)+(1-p){\kappa }_2\left(y\right)(x,z)$$ $$=p\left({\chi }_{Q\left(y\right)}{\varpi }^{{\kappa }_1}\right)(x,z)+(1-p)\left({\chi }_{Q\left(y\right)}{\varpi }^{{\kappa }_2}\right)(x,z)=(p{\chi }_{Q\left(y\right)}{\varpi }^{{\kappa }_1}+(1-p\left){\chi }_{Q\left(y\right)}{\varpi }^{{\kappa }_2}\right)(x,z)$$ $$={\chi }_{Q\left(y\right)}(p{\varpi }^{{\kappa }_1}+(1-p\left){\varpi }^{{\kappa }_2}\right)(x,z)={\chi }_{Q\left(y\right)}{\varpi }^{\kappa }(x,z)$$ By unpacking our definition, using how mixes of kernels work, applying definition 4.5 for ${\kappa }_1$ and ${\kappa }_2$, and then just doing some simple regrouping and packing the definition back up, we get our result.

But wait, we still need to show that ${\varpi }^{\kappa }$ is a Z-Polycontribution on Q. Again, this isn’t too hard to show, with Definition 4.4. $$\sum _{z\in Z}\underset{y\in Y}{max}\sum _{x\in Q\left(y\right)}{\varpi }^{\kappa }(x,z)=\sum _{z\in Z}\underset{y\in Y}{max}\sum _{x\in Q\left(y\right)}(p{\varpi }^{{\kappa }_1}+(1-p\left){\varpi }^{{\kappa }_2}\right)(x,z)$$ $$=\sum _{z\in Z}\underset{y\in Y}{max}\sum _{x\in Q\left(y\right)}\left(p{\varpi }^{{\kappa }_1}\right(x,z)+(1-p\left){\varpi }^{{\kappa }_2}\right(x,z\left)\right)$$ $$=\sum _{z\in Z}\underset{y\in Y}{max}\left(p\sum _{x\in Q\left(y\right)}{\varpi }^{{\kappa }_1}\right(x,z)+(1-p\left)\sum _{x\in Q\left(y\right)}{\varpi }^{{\kappa }_2}\right(x,z\left)\right)$$ $$\le \sum _{z\in Z}\left(p\underset{y\in Y}{max}\sum _{x\in Q\left(y\right)}{\varpi }^{{\kappa }_1}\right(x,z)+(1-p\left)\underset{y\in Y}{max}\sum _{x\in Q\left(y\right)}{\varpi }^{{\kappa }_2}\right(x,z\left)\right)$$ $$=p\sum _{z\in Z}\underset{y\in Y}{max}\sum _{x\in Q\left(y\right)}{\varpi }^{{\kappa }_1}(x,z)+(1-p)\sum _{z\in Z}\underset{y\in Y}{max}\sum _{x\in Q\left(y\right)}{\varpi }^{{\kappa }_2}(x,z)\le p\cdot 1+(1-p)\cdot 1=1$$ And bam, we have our inequality demonstrated, everything works out. Now we just need to show that this family of Z-PoCK’s makes the Z-PUCK that’s the mixture of the two. We’ll establish equality by showing equality for all functions and all $y$. $$\Xi \left(y\right)\left(f\right)=\underset{\kappa \in \Pi }{max}\kappa \left(y\right)\left(f\right)=\underset{\kappa \in \{p{\kappa }_1+(1-p){\kappa }_2|{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2\}}{max}\kappa \left(y\right)\left(f\right)$$ $$=\underset{{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2}{max}(p{\kappa }_1+(1-p\left){\kappa }_2\right)\left(y\right)\left(f\right)=\underset{{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2}{max}p{\kappa }_1\left(y\right)\left(f\right)+(1-p){\kappa }_2\left(y\right)\left(f\right)$$ $$=p\underset{{\kappa }_1\in {\Pi }_1}{max}{\kappa }_1\left(y\right)\left(f\right)+(1-p)\underset{{\kappa }_2\in {\Pi }_2}{max}{\kappa }_2\left(y\right)\left(f\right)=p{\Xi }_1\left(y\right)\left(f\right)+(1-p){\Xi }_2\left(y\right)\left(f\right)$$ $$=(p{\Xi }_1+(1-p\left){\Xi }_2\right)\left(y\right)\left(f\right)$$ Done, we’ve shown equality of the Z-PUCK with the mixture of other Z-PUCKs, establishing that the mixture of Z-PUCKs is a Z-PUCK.

That leaves establishing our relevant inequality. But before we do that, we’ll be wanting a nice handy form for that asterisk operator to manipulate things with. Given some $\kappa$ that’s a Z-PUCK over Q, remember from the previous proof that a valid choice for $\mu$ and $\varphi$ to break $\kappa$ down is $$\mu \left(z\right):=\underset{y^{\prime }\in Y}{max}\sum _{x^{\prime }\in Q\left(y^{\prime }\right)}{\varpi }^{\kappa }(z,x^{\prime })$$ and, abbreviating things a little bit, we have $$\varphi (y,z)\left(x\right):=\frac{{\chi }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(z,x)}{\mu \left(z\right)}$$ So, we can get a pleasant-to-manipulate form for $\Theta \ast \kappa$ as follows. $$(\Theta \ast \kappa )(\lambda xyz.f(x,y,z\left)\right)=(\mu ⋉\Theta ⋉\varphi )(\lambda xyz.f(x,y,z\left)\right)$$ $$=\mu (\lambda z.\Theta (\lambda y.\varphi (y,z)(\lambda x.f(x,y,z\left)\right)\left)\right)$$ And proceed further $$=\sum _{z\in Z}\mu \left(z\right)\cdot \Theta (\lambda y.\varphi (y,z\left)\right(\lambda x.f(x,y,z)\left)\right)$$ $$=\sum _{z\in Z}\mu \left(z\right)\cdot \Theta (\lambda y.\sum _{x\in X}\varphi (y,z\left)\right(x)\cdot f(x,y,z\left)\right)$$ $$=\sum _{z\in Z}\mu \left(z\right)\cdot \Theta (\lambda y.\sum _{x\in X}\frac{{\chi }_{x\in Q\left(y\right)}{\varpi }^{\kappa }(z,x)}{\mu \left(z\right)}\cdot f(x,y,z\left)\right)$$ And then we move the constant into $\Theta$ since it’s homogenous, and then into the sum, and it cancels out with the fraction. $$=\sum _{z\in Z}\Theta (\lambda y.\sum _{x\in X}{\chi }_{x\in Q\left(y\right)}\cdot {\varpi }^{\kappa }(z,x)\cdot f(x,y,z\left)\right)$$ $$=\sum _{z\in Z}\Theta (\lambda y.\sum _{x\in Q\left(y\right)}{\varpi }^{\kappa }(z,x)\cdot f(x,y,z\left)\right)$$ $$=\sum _{z\in Z}\Theta (\lambda y.{\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{\kappa }(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime })\left)\right)$$ This general form will be used whenever we need to unpack $\Theta \ast \kappa$. Now, let’s get started on the proof of our subset inclusion thingy. As usual, $\Pi$ will be the set $\{p{\kappa }_1+(1-p){\kappa }_2|{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2\}$, and as we’ve shown, that’s the set of Z-PoCK’s associated with $p{\Xi }_1+(1-p){\Xi }_2$. Also, as we’ve already shown, the associated Z-polycontribution ${\varpi }^{\kappa }$ for $\kappa =p{\kappa }_1+(1-p){\kappa }_2$ is $p{\varpi }^{{\kappa }_1}+(1-p){\varpi }^{{\kappa }_2}$. This will be implicitly used in the following. $$(\Theta \ast (p{\Xi }_1+(1-p){\Xi }_2\left)\right)(\lambda xyz.f(x,y,z\left)\right)=\underset{\kappa \in \Pi }{max}(\Theta \ast \kappa )(\lambda xyz.f(x,y,z\left)\right)$$ Now we use our preferred unpacking of how that asterisk operator works. $$=\underset{\kappa \in \Pi }{max}\sum _{z\in Z}\Theta (\lambda y.{\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{\kappa }(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime })\left)\right)$$ And unpack $\kappa$ and ${\varpi }^{\kappa }$ appropriately. $$=\underset{{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2}{max}\sum _{z\in Z}\Theta (\lambda y.{\chi }_{Q\left(y\right)\times \left\{z\right\}}(p{\varpi }^{{\kappa }_1}+(1-p){\varpi }^{{\kappa }_2}\left)\right(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime })\left)\right)$$ $$=\underset{{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2}{max}\sum _{z\in Z}\Theta (\lambda y.p{\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{{\kappa }_1}(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime }))$$ $$+(1-p){\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{{\kappa }_2}(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime }\left)\right))$$ At this point, we use convexity of $\Theta$, since it’s an ultradistribution. $$\le \underset{{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2}{max}\sum _{z\in Z}\left(p\Theta \right(\lambda y.\left({\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{{\kappa }_1}\right)(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime }\left)\right))$$ $$+(1-p)\Theta (\lambda y.({\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{{\kappa }_2}\left)\right(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime })\left)\right))$$ $$=\underset{{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2}{max}\left(p\sum _{z\in Z}\Theta \right(\lambda y.\left({\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{{\kappa }_1}\right)(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime }\left)\right))$$ $$+(1-p)\sum _{z\in Z}\Theta (\lambda y.({\chi }_{Q\left(y\right)\times \left\{z\right\}}{\varpi }^{{\kappa }_2}\left)\right(\lambda x^{\prime }{z}^{\prime }.f(x^{\prime },y,z^{\prime })\left)\right))$$ At this point, you can pack up things. $$=\underset{{\kappa }_1\in {\Pi }_1,{\kappa }_2\in {\Pi }_2}{max}p(\Theta \ast {\kappa }_1)(\lambda xyz.f(x,y,z\left)\right)+(1-p)(\Theta \ast {\kappa }_2)(\lambda xyz.f(x,y,z\left)\right)$$ $$=p\underset{{\kappa }_1\in {\Pi }_1}{max}(\Theta \ast {\kappa }_1)(\lambda xyz.f(x,y,z\left)\right)+(1-p)\underset{{\kappa }_2\in {\Pi }_2}{max}(\Theta \ast {\kappa }_2)(\lambda xyz.f(x,y,z\left)\right)$$ $$=p(\Theta \ast {\Xi }_1)(\lambda xyz.f(x,y,z\left)\right)+(1-p)(\Theta \ast {\Xi }_2)(\lambda xyz.f(x,y,z\left)\right)$$ $$=\left(p\right(\Theta \ast {\Xi }_1)+(1-p\left)\right(\Theta \ast {\Xi }_2\left)\right)(\lambda xyz.f(x,y,z\left)\right)$$ Done! $■$

Proposition 4.3: Let $X$, $Y$ and $Z$ be finite sets, $Q\subseteq Y\times X$ a relation, ${\kappa }_1,{\kappa }_2:Y\to {\Delta }^c(X\times Z)$ $Z$-PoCKs over $Q$, $\Theta \in {\square }^{c}Y$ and $p\in [0,1]$. Then, $p{\kappa }_1+(1-p){\kappa }_2$ is also a $Z$-PoCK over $Q$, and $$\Theta \ast (p{\kappa }_1+(1-p\left){\kappa }_2\right)\subseteq p(\Theta \ast {\kappa }_1)+(1-p)(\Theta \ast {\kappa }_2)$$

Use Lemma 4, along with $Z$-PoCKs being a special case of $Z$-PUCKs.

Proposition 4.4: Let $X$, $Y$ and $Z$ be finite sets, $Q\subseteq Y\times X$ a relation and $\Xi :Y\to {\square }^c(X\times Z)$ a $Z$-PUCK over $Q$. Denote $\Theta :={\top }_Y\ast \Xi$. Define ${\beta }_0,{\beta }_1:Z\times Y\times X\to 2^{Z\times Y}$ by ${\beta }_0(z,y,x):=\left\{z\right\}\times Q^{-1}\left(x\right)$, \textbf{${\beta }_1(z,y,x):=Z\times Q^{-1}\left(x\right)$}. Then $$(\Theta ⋉{\beta }_0{)}^{\downarrow }\subseteq \text{Br}(\Theta )\subseteq (\Theta ⋉{\beta }_1{)}^{\downarrow }$$

Proof: As usual, when establishing inequalities with downwards closures, we only have to verify the result for monotone functions. So, we may assume that $f$ is monotone, and attempt to show that $$(\Theta ⋉{\beta }_0)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)\le {\text{Br}}_{Z\times Y}\left(\Theta \right)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)$$ $$\le (\Theta ⋉{\beta }_1)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)$$ Remember, bridge transforms cash out as a maximum over contributions, so to show the first inequality, we’ll need to build a contribution that matches or exceeds that first term, and that lands in the bridge transform of $\Theta$. For the second inequality, it’s considerably easier, we just use our Lemma 2 to figure out what sort of sets the bridge transform is supported on, swap out the sets it’s supported on for a bigger set upper bound, and bam, monotonicity of $f$ takes over from there. From there, it’s easy to show the second inequality. Let’s unpack that first thing $$(\Theta ⋉{\beta }_0)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)$$ $$=\Theta (\lambda xyz.{\delta }_{{\beta }_0(x,z)}(\lambda \alpha .f(x,y,z,\alpha )\left)\right)$$ $$=\Theta (\lambda xyz.f(x,y,z,{\beta }_0(x,z)\left)\right)$$ And at this point we unpack what $\Theta$ is. $$=({\top }_Y\ast \Xi )(\lambda xyz.f(x,y,z,{\beta }_0(x,z)\left)\right)$$ And the $\Xi$. $$=\underset{\kappa \in \Pi }{max}({\top }_Y\ast \kappa )(\lambda xyz.f(x,y,z,{\beta }_0(x,z)\left)\right)$$ And then, $\kappa$ can be broken down into some ${\mu }^{\kappa }$ and ${\varphi }^{\kappa }$, and that goes on both sides of ${\top }_Y$ as our previous proposition shows. $$=\underset{\kappa \in \Pi }{max}({\mu }^{\kappa }⋉{\top }_Y⋉{\varphi }^{\kappa })(\lambda xyz.f(x,y,z,{\beta }_0(x,z)\left)\right)$$ $$=\underset{\kappa \in \Pi }{max}{\mu }^{\kappa }(\lambda z.{\top }_Y(\lambda y.{\varphi }^{\kappa }(y,z)(\lambda x.f(x,y,z,{\beta }_0(x,z)\left)\right)\left)\right)$$ $$=\underset{\kappa \in \Pi }{max}{\mu }^{\kappa }(\lambda z.\underset{y}{max}{\varphi }^{\kappa }(y,z\left)\right(\lambda x.f(x,y,z,{\beta }_0(x,z\left)\right)\left)\right)$$ Now we can start filling in some data. There’s a maximizing ${\kappa }^{\ast }$, so we can substitute that in. That gives us a canonical choice for what ${\mu }^{{\kappa }^{\ast }}$ and ${\varphi }^{{\kappa }^{\ast }}$ are. Making that substitution, $$={\mu }^{{\kappa }^{\ast }}(\lambda z.\underset{y}{max}{\varphi }^{{\kappa }^{\ast }}(y,z\left)\right(\lambda x.f(x,y,z,{\beta }_0(x,z\left)\right)\left)\right)$$ And then, let $d:Z\to Y$ be the function mapping each particular $z$ to the $y$ which maximizes ${\varphi }^{{\kappa }^{\ast }}(y,z)(\lambda x.f(x,y,z,{\beta }_0(x,z)\left)\right)$. This lets us reexpress things as $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.f(x,d(z),z,{\beta }_0(x,z\left)\right)\left)\right)$$ And now, we can start unpacking things a bit. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\delta }_{d\left(z\right)}(\lambda y.{\varphi }^{{\kappa }^{\ast }}(y,z)(\lambda x.f(x,y,z,{\beta }_0(x,z)\left)\right)\left)\right)$$ $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\delta }_{d\left(z\right)}(\lambda y.{\varphi }^{{\kappa }^{\ast }}(y,z)(\lambda x.{\delta }_{{\beta }_0(x,z)}(\lambda \alpha .f(x,y,z,\alpha )\left)\right)\left)\right)$$ And now we can write things as just a giant semidirect product. $$=({\mu }^{{\kappa }^{\ast }}⋉d⋉{\varphi }^{{\kappa }^{\ast }}⋉{\beta }_0)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)$$ Now we’ll show that this particular contribution lies in $\text{Br}\left(\Theta \right)$.

Checking the support condition, we want to check for sure that $y,z\in \alpha$, ie, the event $y,z\notin \alpha$ has measure 0. Let’s begin. $$({\mu }^{{\kappa }^{\ast }}⋉d⋉{\varphi }^{{\kappa }^{\ast }}⋉{\beta }_0)(\lambda xyz\alpha .{\chi }_{y,z\notin \alpha })$$ $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\delta }_{d\left(z\right)}(\lambda y.{\varphi }^{{\kappa }^{\ast }}(y,z)(\lambda x.{\delta }_{{\beta }_0(x,z)}(\lambda \alpha .{\chi }_{y,z\notin \alpha }\left)\right)\left)\right)$$ Substitute in the dirac-deltas. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{d\left(z\right),z\notin {\beta }_0(x,z)}\left)\right)$$ Unpack what ${\beta }_0(x,z)$ is. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{d\left(z\right),z\notin Q^{-1}\left(x\right)\times \left\{z\right\}}\left)\right)$$ Now, $z\in \left\{z\right\}$ always occurs, so that indicator function is the same as just testing whether $d\left(z\right)\in Q^{-1}\left(x\right)$. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{d\left(z\right)\notin Q^{-1}\left(x\right)}\left)\right)$$ Rephrasing things a little bit, $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{x\notin Q\left(d\right(z\left)\right)}\left)\right)$$ Then, from proposition 4.2, we remember that $\lambda y.{\varphi }^{{\kappa }^{\ast }}(y,z)$ is a PoCK over $Q$. Ie, for any particular $y$, ${\varphi }^{{\kappa }^{\ast }}(y,z)$ looks like a particular measure (${\varpi }^{{\kappa }^{\ast },z}$) restricted to $Q\left(y\right)$. So, in particular, ${\varphi }^{{\kappa }^{\ast }}\left(d\right(z),z)$ must be supported over $Q\left(d\right(z\left)\right)$. Put another way, with full measure, $x\in Q\left(d\right(z\left)\right)$. So, this event failing has 0 measure. $$={\mu }^{{\kappa }^{\ast }}\left(\lambda z.0\right)=0$$ And we’re done with that support condition.

Now to show the endofunction condition. As usual, we’ll let $s:Y\times Z\to Y\times Z$, and let $g:X\times Y\times Z\to [0,1]$. Actually, for conceptual clarity, since $s:Y\times Z\to Y\times Z$ can be viewed as a pair of functions $s_Y:Y\times Z\to Y$ and $s_Z:Y\times Z\to Z$, we’ll be using that formulation in our equation. $$({\mu }^{{\kappa }^{\ast }}⋉d⋉{\varphi }^{{\kappa }^{\ast }}⋉{\beta }_0)(\lambda xyz\alpha .{\chi }_{s_Y(y,z),s_Z(y,z)\in \alpha }g(s_Y(y,z),s_Z(y,z),x\left)\right)$$ $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\delta }_{d\left(z\right)}(\lambda y.{\varphi }^{{\kappa }^{\ast }}(y,z)(\lambda x.{\delta }_{{\beta }_0(x,z)}(\lambda \alpha .{\chi }_{s_Y(y,z),s_Z(y,z)\in \alpha }g\left(s_Y\right(y,z),s_Z(y,z),x)\left)\right)\left)\right)$$ As usual, we’ll substitute in our dirac-deltas to simplify things. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{s_Y\left(d\right(z),z),s_Z\left(d\right(z),z)\in {\beta }_0(x,z)}g\left(s_Y\right(d\left(z\right),z),s_Z(d\left(z\right),z),x)\left)\right)$$ Substitute in what ${\beta }_0(x,z)$ is. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{s_Y\left(d\right(z),z),s_Z\left(d\right(z),z)\in Q^{-1}\left(x\right)\times \left\{z\right\}}g\left(s_Y\right(d\left(z\right),z),s_Z(d\left(z\right),z),x)\left)\right)$$ Now, if that “this pair of points lies in this set” indicator function goes off, then $s_Z\left(d\right(z),z)=z$. So, we can substitute that into the $g$ term afterwards. And then get a $\le$ inequality by making the indicator function less strict. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{s_Y\left(d\right(z),z),s_Z\left(d\right(z),z)\in Q^{-1}\left(x\right)\times \left\{z\right\}}g\left(s_Y\right(d\left(z\right),z),z,x)\left)\right)$$ $$\le {\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{s_Y\left(d\right(z),z)\in Q^{-1}\left(x\right)}g\left(s_Y\right(d\left(z\right),z),z,x)\left)\right)$$ And reexpress the indicator function a little bit $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(d\left(z\right),z\left)\right(\lambda x.{\chi }_{x\in Q\left(s_Y\right(d\left(z\right),z\left)\right)}g\left(s_Y\right(d\left(z\right),z),z,x)\left)\right)$$ At this point, we can use that ${\varphi }^{{\kappa }^{\ast }}(y,z)$ is ${\chi }_{Q\left(y\right)}{\varpi }^{{\varphi }^{{\kappa }^{\ast }},z}$ (ie, fixing $z$ and varying $y$ it just looks like you’re taking one measure and conditioning on various $Q\left(y\right)$), so reexpress things as $$={\mu }^{{\kappa }^{\ast }}(\lambda z.({\chi }_{Q\left(d\right(z\left)\right)}{\varpi }^{{\varphi }^{{\kappa }^{\ast }},z}\left)\right(\lambda x.{\chi }_{x\in Q\left(s_Y\right(d\left(z\right),z\left)\right)}g\left(s_Y\right(d\left(z\right),z),z,x)\left)\right)$$ And then, view the indicator function as just more conditioning. $$={\mu }^{{\kappa }^{\ast }}(\lambda z.({\chi }_{Q\left(d\right(z\left)\right)\cap Q\left(s_Y\right(d\left(z\right),z\left)\right)}{\varpi }^{{\varphi }^{{\kappa }^{\ast }},z}\left)\right(\lambda x.g\left(s_Y\right(d\left(z\right),z),z,x)\left)\right)$$ And then, relax about what you’re conditioning on. $$\le {\mu }^{{\kappa }^{\ast }}(\lambda z.{\chi }_{Q\left(s_Y\right(d\left(z\right),z\left)\right)}{\varpi }^{{\varphi }^{{\kappa }^{\ast }},z}(\lambda x.g\left(s_Y\right(d\left(z\right),z),z,x)\left)\right)$$ Rewrite it as a kernel again $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\varphi }^{{\kappa }^{\ast }}(s_Y\left(d\right(z),z),z\left)\right(\lambda x.g\left(s_Y\right(d\left(z\right),z),z,x)\left)\right)$$ Pull out the dirac-delta $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\delta }_{s_Y\left(d\right(z),z)}(\lambda y.{\varphi }^{{\kappa }^{\ast }}(y,z)(\lambda x.g(y,z,x\left)\right)\left)\right)$$ Throw one more inequality at it $$\le {\mu }^{{\kappa }^{\ast }}(\lambda z.\underset{y}{max}{\varphi }^{{\kappa }^{\ast }}(y,z\left)\right(\lambda x.g(y,z,x)\left)\right))$$ Write it as top $$={\mu }^{{\kappa }^{\ast }}(\lambda z.{\top }_Y(\lambda y.{\varphi }^{{\kappa }^{\ast }}(y,z)(\lambda x.g(y,z,x\left)\right)\left)\right)$$ Write as a semidirect product $$=({\mu }^{{\kappa }^{\ast }}⋉{\top }_Y⋉{\varphi }^{{\kappa }^{\ast }})(\lambda yzx.g(y,z,x\left)\right)$$ Reexpress $$=({\top }_Y\ast {\kappa }^{\ast })(\lambda yzx.g(y,z,x\left)\right)$$ $$\le \underset{\kappa \in \Pi }{max}({\top }_Y\ast \kappa )(\lambda yzx.g(y,z,x\left)\right)$$ $$=({\top }_Y\ast \Xi )(\lambda yzx.g(y,z,x\left)\right)$$ $$=\Theta (\lambda yzx.g(y,z,x\left)\right)$$ And we’re done! endofunction condition shown. Our relevant contribution is in $\text{Br}\left(\Theta \right)$. Let’s see, where were we… ah right, we had shown that for all monotone $f$, $$(\Theta ⋉{\beta }_0)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)$$ $$=({\mu }^{{\kappa }^{\ast }}⋉d⋉{\varphi }^{{\kappa }^{\ast }}⋉{\beta }_0)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)$$ For some choice of $d$ and ${\kappa }^{\ast }$. We know this is in $\text{Br}\left(\Theta \right)$, so we get $$\le \underset{\theta \in \text{Br}\left(\Theta \right)}{max}\theta (\lambda yz\alpha x.f(x,y,z,\alpha \left)\right)$$ $$=\text{Br}\left(\Theta \right)(\lambda yz\alpha x.f(x,y,z,\alpha \left)\right)$$ And we’re done! One inequality done. That just leaves showing the second inequality, where ${\beta }_1\left(x\right)=Z\times Q^{-1}\left(x\right)$. It’s actually not too bad to show. Start with $\text{Br}\left(\Theta \right)(\lambda xy\alpha z.f(x,y,z,\alpha \left)\right)$ $$=\underset{\theta \in \text{Br}\left(\Theta \right)}{max}\theta (\lambda yz\alpha x.f(x,y,z,\alpha \left)\right)$$ And then, we recall our Lemma 2, that if $\Theta$ had its support entirely on $x,y,z$ tuples where $y,z$ in $h\left(x\right)$ (for some $h:X\to 2^{Y\times Z}$), then all the $\theta \in \text{Br}\left(\Theta \right)$ would be supported on $(x,\alpha )$ pairs where $\alpha \subseteq h\left(x\right)$. And then, swapping out $\alpha$ for $h\left(x\right)$, by monotonicity of $f$, produces a larger value.

To invoke this argument, our choice of $h$ will be ${\beta }_1$, where ${\beta }_1\left(x\right)=Q^{-1}\left(x\right)\times Z$. We do need to show that $\Theta$ is supported on such tuples. $$\Theta (\lambda xyz.{\chi }_{y,z\notin Q^{-1}\left(x\right)\times Z})=\Theta (\lambda xyz.{\chi }_{y\notin Q^{-1}\left(x\right)})=\Theta (\lambda xyz.{\chi }_{x\notin Q\left(y\right)})$$ $$=({\top }_Y\ast \Xi )(\lambda xyz.{\chi }_{x\notin Q\left(y\right)})=\underset{\kappa \in \Pi }{max}({\top }_Y\ast \kappa )(\lambda xyz.{\chi }_{x\notin Q\left(y\right)})$$ $$=\underset{\kappa \in \Pi }{max}({\mu }^{\kappa }⋉{\top }_Y⋉{\varphi }^{\kappa })(\lambda xyz.{\chi }_{x\notin Q\left(y\right)})$$ $$=\underset{\kappa \in \Pi }{max}{\mu }^{\kappa }(\lambda z.{\top }_Y(\lambda y.{\varphi }^{\kappa }(y,z)(\lambda x.{\chi }_{x\notin Q\left(y\right)})\left)\right)$$ And then use that ${\varphi }^{\kappa }(y,z)={\chi }_{Q\left(y\right)}{\varpi }^{{\varphi }^{\kappa },z}$ since it’s a PoCK in Q, to get $$=\underset{\kappa \in \Pi }{max}{\mu }^{\kappa }(\lambda z.{\top }_Y(\lambda y.\left({\chi }_{Q\left(y\right)}{\varpi }^{{\varphi }^{\kappa },z}\right)(\lambda x.{\chi }_{x\notin Q\left(y\right)})\left)\right)$$ Hm, we updated on a set, and are evaluating the indicator function for not being in the set. $$=\underset{\kappa \in \Pi }{max}{\mu }^{\kappa }(\lambda z.{\top }_Y(\lambda y.0\left)\right)=0$$ Ok, so this means we can invoke Lemma 2. We were previously at $$=\underset{\theta \in \text{Br}\left(\Theta \right)}{max}\theta (\lambda yz\alpha x.f(x,y,z,\alpha \left)\right)$$ So now we can invoke monotonicity and go $$\le \underset{\theta \in \text{Br}\left(\Theta \right)}{max}\theta (\lambda yz\alpha x.f(x,y,z,{\beta }_1\left(x\right)\left)\right)$$ And then invoke our endofunction property for the stuff in $\text{Br}\left(\Theta \right)$, letting $s$ be the identity function (and also $y,z\in \alpha$ occurs always) to establish a uniform upper bound of $$\le \Theta (\lambda xyz\alpha .f(x,y,z,{\beta }_1\left(x\right)\left)\right)$$ $$=\Theta (\lambda xyz.{\delta }_{{\beta }_1\left(x\right)}(\lambda \alpha .f(x,y,z,\alpha )\left)\right)$$ $$=(\Theta ⋉{\beta }_1)(\lambda xyz\alpha .f(x,y,z,\alpha \left)\right)$$ And we’re done! Second inequality demonstrated. $■$

Corollary 4.5: Suppose that for any $d\in D$, $z\in {\Gamma }_1$ and $\pi :H\to A$ s.t. $(d,z)\in \text{supp}W\left(\pi \right)$, it holds that $dCz\pi$. That is, the observations $W$ predicts to receive from the computer are consistent with the chosen policy and $W$’s beliefs about computations. Let $L:D\to R$ be a Cartesian loss function and $\pi :H\to A$ a policy. Define $\tilde{L}:D\times {\Gamma }_1\to R$ by $\tilde{L}(h,z):=L\left(h\right)$. Then, $$\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W)\cap {\text{C}}_{fair}^{\pi })\left(L^{\text{phys}}\right)=W(\pi ;\tilde{L})$$

To a large extent, this will follow the proof of the previous corollary. We’ll use $\beta$ for $2^{\Gamma }$ and $\alpha$ for just the policy component.

I’m going to be proceeding very cautiously here. First off, make our $\pi$ value special by swapping it out for ${\pi }^{\ast }$ $$\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W)\cap {\text{C}}_{\text{fair}}^{{\pi }^{\ast }})\left(L^{\text{phys}}\right)$$ Now, by the identifications we made earlier, we can identify $\Gamma$ with $A^H\times {\Gamma }_1$, the space of policies and computations. Using that to unpack the function a little bit, we have $$=\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W)\cap {\text{C}}_{\text{fair}}^{{\pi }^{\ast }})(\lambda \pi z\beta .L^{\text{phys}}(\pi ,z,\beta \left)\right)$$ Now, we note that intersecting with top of a particular set is equivalent to updating on the indicator function for that set. Using definition 1.5 to unpack ${\text{C}}_{\text{fair}}^{{\pi }^{\ast }}$, we get $$=\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W\left)\right)(\lambda \pi z\beta .{\chi }_{\forall h\in H_{\pi ,z,\beta }:G^{\pi ,z}\left(h\right)={\pi }^{\ast }\left(h\right)}{L}^{\text{phys}}(\pi ,z,\beta \left)\right)$$ Throughout we’ll be applying that $G^{\pi ,z}\left(h\right)$ is “what would the agent do on $h$ if the agent is copying the behavior of $\pi$” (remember, part of the math is “what does the agent do in response to this history” and $\pi$ is our term for that chunk of the math), so we’ll just always rephrase things like that and won’t bother to say $G^{\pi ,z}\left(h\right)=\pi \left(h\right)$ every time we do it. $$=\left({\text{pr}}_{{\text{el}}^{\Gamma }}\text{Br}\right({\Theta }_W\left)\right)(\lambda \pi z\beta .{\chi }_{\forall h\in H_{\pi ,z,\beta }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}{L}^{\text{phys}}(\pi ,z,\beta \left)\right)$$ Pull off the projection, and use $d$ for a destiny in $D$. $$=\text{Br}\left({\Theta }_W\right)(\lambda \pi z\beta d.{\chi }_{\forall h\in H_{\pi ,z,\beta }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}{L}^{\text{phys}}(\pi ,z,\beta \left)\right)$$ Applying definition 3.1, and using $d^{\prime }$ instead of $g$ to remember it’s a destiny, we have $$=\text{Br}\left({\Theta }_W\right)(\lambda \pi z\beta d.{\chi }_{\forall h\in H_{\pi ,z,\beta }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}\underset{ha:ha\in X_{\pi ,z,\beta }}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L(d^{\prime }\left)\right)$$ Next up is unpacking $X_{\pi ,z,\beta }$. Using definition 3.1, it’s $$=\text{Br}\left({\Theta }_W\right)(\lambda \pi z\beta d.{\chi }_{\forall h\in H_{\pi ,z,\beta }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,z,\beta }\times A\wedge \left(\forall \right({\pi }^{\prime },z^{\prime })\in \beta :{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ Now we’ll show that $H_{\pi ,z,\beta }$ only depends on $pr\left(\beta \right)$, ie, the projection of $\beta$ from $2^{A^H\times {\Gamma }_1}$ to $2^{A^H}$, and that it gets smaller as $\beta$ gets larger, so the function above is monotone. Let’s use definition 1.5 to unpack the event $h\in H_{\pi ,z,\beta }$. $$(\forall h^{\prime }{a}^{\prime }⊏h,({\pi }^{\prime },z^{\prime })\in \beta :{\pi }^{\prime }(h^{\prime })=a^{\prime })\wedge (\exists d^{\prime }:h⊏d^{\prime }\wedge d^{\prime }Cz\pi )$$ It shouldn’t be too hard to tell that $\beta$ getting larger makes this set smaller, and that, since the $z^{\prime }$ doesn’t matter, this condition is really the same as $$(\forall h^{\prime }{a}^{\prime }⊏h,{\pi }^{\prime }\in pr(\beta ):{\pi }^{\prime }(h^{\prime })=a^{\prime })\wedge (\exists d^{\prime }:h⊏d^{\prime }\wedge d^{\prime }Cz\pi )$$ So, we’ll use $pr\left(\beta \right)$ to remind us that our function only depends on the projection of $\beta$. $$=\text{Br}\left({\Theta }_W\right)(\lambda \pi z\beta d.{\chi }_{\forall h\in H_{\pi ,z,pr\left(\beta \right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,z,pr\left(\beta \right)}\times A\wedge (\forall {\pi }^{\prime }\in pr(\beta ):{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ And now we can pull that out as a projection! We’re now using $\alpha$ for our set of policies, instead of $\beta$ for our set of policy/​computation pairs. $$=pr\left(\text{Br}\right({\Theta }_W\left)\right)(\lambda \pi z\alpha d.{\chi }_{\forall h\in H_{\pi ,z,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,z,\alpha }\times A\wedge (\forall {\pi }^{\prime }\in \alpha :{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ To proceed further, we’re going to need to adapt our previous result which gets an upper and lower bound on the bridge transform of suitable $\Theta$. Our first order of business is checking that $\alpha$ getting larger makes the function larger, which is easy to check since $\alpha$ getting larger cuts down on the options to minimize over (increasing value), and makes the antecedent of the implication harder to fulfill, which makes the implication as a whole easier to fulfill, so the indicator function is 1 more often. Now we can proceed further. Abstracting away a bit from our specific function, which will be swapped out for some $f:A^H\times {\Gamma }_1\times D\times 2^{A^H}\to [0,1]$ which is monotone in that last argument, we have $$({\Theta }_W⋉{\beta }_0{)}^{\downarrow }(\lambda z\pi d\beta .f(z,\pi ,d,pr(\beta \left)\right))$$ $$=({\Theta }_W⋉{\beta }_0)(\lambda z\pi d\beta .f(z,\pi ,d,pr\left(\beta \right)\left)\right)$$ $$={\Theta }_W(\lambda z\pi d.f(z,\pi ,d,pr\left({\beta }_0\right(z,d\left)\right)\left)\right)$$ $$={\Theta }_W(\lambda z\pi d.f(z,\pi ,d,pr\left(\right\{z\}\times Q_0^{-1}(d\left)\right)\left)\right)$$ $$={\Theta }_W(\lambda z\pi d.f(z,\pi ,d,Q_0^{-1}\left(d\right)\left)\right)$$ $$={\Theta }_W(\lambda z\pi d.f(z,\pi ,d,pr(Z\times Q_0^{-1}(d\left)\right)\left)\right)$$ $$={\Theta }_W(\lambda z\pi d.f(z,\pi ,d,pr\left({\beta }_1\right(d\left)\right)\left)\right)$$ $$=({\Theta }_W⋉{\beta }_1)(\lambda z\pi d\beta .f(z,\pi ,d,pr\left(\beta \right)\left)\right)$$ $$=({\Theta }_W⋉{\beta }_1{)}^{\downarrow }(\lambda z\pi d\beta .f(z,\pi ,d,pr(\beta \left)\right))$$ Monotonicity was used to go back and forth between the downwards closure and the raw form.${\beta }_0$ and ${\beta }_1$ are as they were in Proposition 4.4, and $Q$ would be the relation on $A^H\times D$ telling you whether a policy is consistent with a destiny. Now, by Proposition 4.4, since the bridge transform of ${\Theta }_W$ is sandwiched between those two values, and they’re both equal, we have $$pr\left(\text{Br}\right({\Theta }_W\left)\right)(\lambda z\pi d\alpha .f(z,\pi ,d,\alpha \left)\right)=\text{Br}\left({\Theta }_W\right)(\lambda z\pi d\beta .f(z,\pi ,d,pr\left(\beta \right)\left)\right)$$ $$={\Theta }_W(\lambda z\pi d.f(z,\pi ,d,Q_0^{-1}\left(d\right)\left)\right)=({\Theta }_W⋉Q_0^{-1})(\lambda z\pi d\alpha .f(z,\pi ,d,\alpha \left)\right)$$ The first equality was just relocating the projection. the second equality was from the bridge transform being sandwiched between two equal quantities, so it equals all the stuff on our previous big list of equalities (we went with the middle one). Then just express as a semidirect product, and you’re done. Applying this to our previous point of $$=pr\left(\text{Br}\right({\Theta }_W\left)\right)(\lambda \pi z\alpha d.{\chi }_{\forall h\in H_{\pi ,z,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,z,\alpha }\times A\wedge (\forall {\pi }^{\prime }\in \alpha :{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ We can reexpress it as $$=({\Theta }_W⋉Q_0^{-1})(\lambda \pi z\alpha d.{\chi }_{\forall h\in H_{\pi ,z,\alpha }:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,z,\alpha }\times A\wedge (\forall {\pi }^{\prime }\in \alpha :{\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ And start unpacking the semidirect product $$={\Theta }_W(\lambda \pi zd.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}$$ $$\underset{ha:ha\in H_{\pi ,z,Q_0^{-1}\left(d\right)}\times A\wedge (\forall {\pi }^{\prime }:d{Q}_0{\pi }^{\prime }\to {\pi }^{\prime }(h)=a)}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L\left(d^{\prime }\right))$$ Now, we’re going to try to address that minimum, and show that the only $ha$ that fulfill the conditions are exactly those $ha⊑d$. This requires showing that $ha⊑d$ is a sufficient condition to fulfill the relevant properties, and then to show that $ha⋢d$ implies a failure of one of the properties.

The proof for this is almost entirely identical to the corresponding proof in the non-turing-law case, there are no substantive differences besides one issue to clear up. We need to show that $W\left(\pi \right)$ always being supported on the relation $C$, for all $\pi$ (as one of our starting assumptions) implies that ${\Theta }_W$ is supported on $C$ as well. Here’s how we do it. We have ${\Theta }_W={\top }_{A^H}\ast W$. And then this ultracontribution (by the definition of ${\Gamma }_1$-PUCK’s) can be written as the convex hull of the union of a bunch of ultracontributions of the form ${\top }_{A^H}\ast w$, where $w$ is a ${\Gamma }_1$-PoCK. So, if we can show all of these are supported on the relation $C$, then the same holds for the convex hull of their union, ie, ${\Theta }_W$. By Proposition 4.2, we can reexpress this ultracontribution as ${\mu }^w⋉{\top }_{A^H}⋉{\varphi }^w$, where $w\left(\pi \right)={\mu }^w⋉(\lambda z.{\varphi }^w(z,\pi \left)\right)$, for any policy $\pi$. Now, let’s check the expectation value of the indicator function for $C$ being violated. $$({\mu }^w⋉{\top }_{A^H}⋉{\varphi }^w)(\lambda z\pi d.{\chi }_{\neg dCz\pi })$$ $$={\mu }^w(\lambda z.{\top }_{A^H}(\lambda \pi .{\varphi }^w(z,\pi )(\lambda d.{\chi }_{\neg dCz\pi })\left)\right)$$ $$={\mu }^w(\lambda z.\underset{\pi }{max}{\varphi }^w(z,\pi \left)\right(\lambda d.{\chi }_{\neg dCz\pi }\left)\right)$$ Let’s assume that the expectation of that indicator function is \emph{not} zero. Then there must be some particular $z$ in the support of ${\mu }^w$ where it is nonzero, and some particular ${\pi }^{\ast }$ that attains that nonzero expectation value. So, there’s a $z$ in the support of ${\mu }^w$ and ${\pi }^{\ast }$ s.t. $${\varphi }^w(z,{\pi }^{\ast })(\lambda d.{\chi }_{\neg dCz{\pi }^{\ast }})>0$$ and so this means that we have $${\mu }^w(\lambda z.{\varphi }^w(z,{\pi }^{\ast }\left)\right(\lambda d.{\chi }_{\neg dCz{\pi }^{\ast }}\left)\right)>0$$ Because that $z$ is assigned nonzero measure, and then this reshuffles to $$({\mu }^w⋉(\lambda z.{\varphi }^w(z,{\pi }^{\ast })\left)\right)(\lambda d.{\chi }_{\neg dCz{\pi }^{\ast }})>0$$ Which, via Proposition 4.2, is $$w\left({\pi }^{\ast }\right)(\lambda zd.{\chi }_{\neg dCz{\pi }^{\ast }})>0$$ But this contradicts that $W\left({\pi }^{\ast }\right)$ (and so all the $w\left({\pi }^{\ast }\right)$) were supported on the event $dCz{\pi }^{\ast }$, so we have a contradiction, and our result follows.

Now that that issue is taken care of, we can swap out our fancy minimization with just minimizing over the $ha⊑d$. $$={\Theta }_W(\lambda \pi zd.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}\underset{ha:ha⊑d}{min}\underset{d^{\prime }:ha⊑d^{\prime }}{max}L(d^{\prime }\left)\right)$$ This minimization is attained by selecting $d$ itself. So then it turns into $$={\Theta }_W(\lambda \pi zd.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ At this point, we’ll upper-and-lower-bound this quantity by $W\left({\pi }^{\ast }\right)(\lambda zd.L(d\left)\right)$. Let’s begin. $$W\left({\pi }^{\ast }\right)(\lambda zd.L(d\left)\right)$$ $$=\underset{w\in \Pi }{max}w\left({\pi }^{\ast }\right)(\lambda zd.L(d\left)\right)$$ $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.{\varphi }^w({\pi }^{\ast },z\left)\right(\lambda d.L\left(d\right)\left)\right)$$ Here we’re using Proposition 4.2 on being able to split up Z-PoCK’s (which $W$ is) a certain way. $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.\underset{\pi }{max}{\varphi }^w({\pi }^{\ast },z\left)\right(\lambda d.{\chi }_{d{Q}_0\pi }L\left(d\right)\left)\right)$$ This equality happens because you can always just pick ${\pi }^{\ast }$ as your choice of $\pi$, and since ${\varphi }^w({\pi }^{\ast },z)$ can only produce destinies consistent with ${\pi }^{\ast }$. Now, we can swap out ${\varphi }^w$ for the measure we’re conditioning on an event $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.\underset{\pi }{max}({\chi }_{Q\left({\pi }^{\ast }\right)}{\varpi }^{{\varphi }^w,z}\left)\right(\lambda d.{\chi }_{d{Q}_0\pi }L\left(d\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.\underset{\pi }{max}{\varpi }^{{\varphi }^w,z}(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}{\chi }_{d{Q}_0\pi }L\left(d\right)\left)\right)$$ Reshuffle the indicator function back in $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.\underset{\pi }{max}({\chi }_{Q\left(\pi \right)}{\varpi }^{{\varphi }^w,z}\left)\right(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}L\left(d\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.\underset{\pi }{max}{\varphi }^w(\pi ,z\left)\right(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}L\left(d\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.{\top }_{A^H}(\lambda \pi .{\varphi }^w(\pi ,z)(\lambda d.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}({\mu }^w⋉{\top }_{A^H}⋉{\varphi }^w)(\lambda \pi zd.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}({\top }_{A^H}\ast w)(\lambda \pi zd.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)\left)\right)$$ $$=({\top }_{A^H}\ast W)(\lambda \pi zd.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)\left)\right)$$ $$={\Theta }_W(\lambda \pi zd.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)\left)\right)$$ Now we must show that this is a looser constraint than what was previously in our indicator function to proceed further. So our next order of business is showing that, certainly, $$\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)\to d{Q}_0{\pi }^{\ast }$$ Let $d$ be an arbitrary destiny in the support of ${\Theta }_W$, and $h$ be one of the history prefixes of $d$. The two conditions for $h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}$ are fulfilled, because they are $$\forall h^{\prime },a^{\prime },{\pi }^{\prime }:h^{\prime }{a}^{\prime }⊏h\wedge d{Q}_0{\pi }^{\prime }\to {\pi }^{\prime }\left(h^{\prime }\right)=a^{\prime }$$ $$\exists d^{\prime }:h⊏d^{\prime }\wedge d^{\prime }C\pi z$$ For the first condition, if $h^{\prime }a⊏h$, then $h^{\prime }{a}^{\prime }⊏d$, and so if ${\pi }^{\prime }$ is consistent with $d$, it must take the same action in response to $h^{\prime }$, the action that $d$ commands. So it is fulfilled. For the second condition, let $d^{\prime }$ be $d$. $h⊏d$ holds, and $dC\pi z$ holds certainly, because ${\Theta }_W$ is supported on $C$, as we’ve previously shown.

So, certainly, $h⊏d\to h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}$. Since we assumed our forall statement as prerequisite, this means that for all $h⊏d$, $\pi \left(h\right)={\pi }^{\ast }\left(h\right)$. And $d{Q}_0\pi$ means $\forall ha⊑d:\pi \left(h\right)=a$. Since ${\pi }^{\ast }\left(h\right)$ mimics $\pi \left(h\right)$ for all history prefixes of $d$, this means $\forall ha⊑d:{\pi }^{\ast }\left(h\right)=a$, ie $d{Q}_0{\pi }^{\ast }$.

So, since this is a looser constraint, when we were previously at $$={\Theta }_W(\lambda \pi zd.{\chi }_{d{Q}_0{\pi }^{\ast }}L(d\left)\right)\left)\right)$$ we can proceed further to $$\ge {\Theta }_W(\lambda \pi zd.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ which is the value we wanted to sandwich. Proceed further with $$=({\top }_{A^H}\ast W)(\lambda \pi zd.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ $$=\underset{w\in \Pi }{max}({\top }_{A^H}\ast w)(\lambda \pi zd.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ $$=\underset{w\in \Pi }{max}({\mu }^w⋉{\top }_{A^H}⋉{\varphi }^w)(\lambda \pi zd.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)$$ $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.{\top }_{A^H}(\lambda \pi .{\varphi }^w(\pi ,z)(\lambda d.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L(d\left)\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.\underset{\pi }{max}{\varphi }^w(\pi ,z\left)\right(\lambda d.{\chi }_{\forall h\in H_{\pi ,z,Q_0^{-1}\left(d\right)}:\pi \left(h\right)={\pi }^{\ast }\left(h\right)}L\left(d\right)\left)\right)$$ $$\ge \underset{w\in \Pi }{max}{\mu }^w(\lambda z.{\varphi }^w({\pi }^{\ast },z\left)\right(\lambda d.{\chi }_{\forall h\in H_{{\pi }^{\ast },z,Q_0^{-1}\left(d\right)}:{\pi }^{\ast }\left(h\right)={\pi }^{\ast }\left(h\right)}L\left(d\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}{\mu }^w(\lambda z.{\varphi }^w({\pi }^{\ast },z\left)\right(\lambda d.L\left(d\right)\left)\right)$$ $$=\underset{w\in \Pi }{max}({\mu }^w⋉(\lambda z.{\varphi }^w({\pi }^{\ast },z)\left)\right)(\lambda zd.L(d\left)\right))$$ $$=\underset{w\in \Pi }{max}w\left({\pi }^{\ast }\right)(\lambda zd.L(d\left)\right))=W({\pi }^{\ast }\left)\right(\lambda zd.L\left(d\right)\left)\right)$$ And we’ve got the same upper and lower bound, so our overall quantity is $$W\left({\pi }^{\ast }\right)\left(\tilde{L}\right)$$ And we’re done. $■$