Proofs Section 2.1 (Theorem 1, Lemmas)

post by Diffractor · 2020-08-27T07:54:59.744Z · LW · GW · 0 comments

Contents

  Lemma 19:
None
No comments

Fair upfront warning: This is not a particularly readable proof section. There's a bunch of dense notation, logical leaps due to illusion of transparency since I've spent months getting fluent with these concepts, and a relative lack of editing since it's long. If you really want to read this, I'd suggest PM-ing me to get a link to MIRIxDiscord, where I'd be able to guide you through it and answer questions. This post will be recapping the notions and building up an arsenal of lemmas, the next one [AF · GW] will show the isomorphism theorem, translation theorems, and behavior of mixing, and the last one [AF · GW] is about updates and the decision-theory results. It's advised to have them open in different tabs and go between them as needed. 

With that said, let's establish some notation and mental intuition. I'll err on the side of including more stuff because illusion of transparency. First, visualize the tree of alternating actions and observations in an environment. A full policy $\pi$ can be viewed as that tree with some branches pruned off, specifying every history that's possible with your policy of interest. All our policies are deterministic. A policy stub ${\pi }_{st}$ is a policy tree that's been mostly pruned down (doesn't extend further than some finite time $n$). A partial policy ${\pi }_{pa}$ is just any policy tree in any state of specification or lack thereof, from tiny stubs to full policies to trees that are infinite down some branches but not others.

${\pi }_{\varnothing }$ denotes the empty policy (a stub) which specifies nothing about what a policy does, and ${\pi }_{\neg h}$ is some partial policy which specifies everything (acts like a full policy) everywhere except on history $h$ and afterwards.

There's a distance metric on histories, as well as a distance metric on partial policies. Both of them are of the form ${\gamma }^t$ where $\gamma <1$, and $t$ is the "time of first difference". For histories, it's "what's the first time these histories differ", for policies, it's "what's the shortest time by which one partial policy is defined and the other is undefined, or where the policies differ on what to do". So, thinking of the distance as getting smaller as the time of first difference gets bigger is a reliable guide.

The outcome set $F\left({\pi }_{pa}\right)$ is... take the tree corresponding to ${\pi }_{pa}$, and it's the set of all the observation leaf nodes and infinite paths. No matter what, if you're interacting with an environment and acting according to ${\pi }_{pa}$, the history you get is guaranteed to have, as a prefix, something in $F\left({\pi }_{pa}\right)$. $F^{NF}\left({\pi }_{pa}\right)$ is that same set but minus all the Nirvana observations. Nirvana is a special observation which can occur at any time, counts as infinite reward, and ends the history. This is our compact metric space of interest that we're using to define a-measures and sa-measures. We assume that there's only finitely many discrete actions/observations available at any given point in time.

In this setting, sa-measures and a-measures over $F^{NF}\left({\pi }_{pa}\right)$ are defined as usual (a pair of a signed measure $m$ and a number $b$ where $b+m^{-}\left(1\right)\ge 0$ for sa-measures, and a measure $m$ with no negative parts and $b\ge 0$, respectively), because there's no infinite reward shenanigans. Sa-measures over $F\left({\pi }_{pa}\right)$ require a technicality, though, which is that no nirvana event can have negative measure. $\lambda$ will denote the total amount of measure you have. So, for a probability distribution, $\lambda$ will be $1$. We'll just use this for a-measures, and talk freely about the $\lambda$ and $b$ values of an a-measure. We use the KR-metric for measuring the distance between sa-measures (or a-measures), which is like "if two measures are really similar for a long time and then start diverging at late times, they're pretty similar." It's also equivalent to the earthmover distance, which is "how much effort does it take to rearrange the pile-of-dirt-that-is-this-measure into the pile-of-dirt-that-is-that-measure."

One important note. While $m\left(f\right)$ is "what's the expectation of the continuous function $f$ over histories, according to the measure we have", we frequently abuse notation and use $m\left(h\right)$ to refer to what technically should be "what's the expectation of the indicator function for "this history has $h$ as a prefix" w.r.t the measure". The reason we can do this is because the indicator function for the finite history $h$ is a continuous function! So we can just view it as "what's the measure assigned to history $h$". Similarly, $f{★}^{h}g$ is the continuous function that's $f$ on histories with $h$ as a prefix and $g$ on histories without $h$ as a prefix.

For a given $M^a\left(F\right({\pi }_{pa}\left)\right)$ or the nirvana-free variant, $NF$ is just the subset of that where the measure components of the a-measures assign 0 measure to Nirvana occurring. They're safe from infinite reward. We suppress the dependency on ${\pi }_{pa}$. Similarly,

$E_B\left(f\right)={inf}_{(m,b)\in B\cap NF}\left(m\right(f)+b)$

because if a Nirvana-containing measure was selected by Murphy, you'd get infinite expected value, so Murphy won't pick anything with Nirvana in it. Keep that in mind.

There's a fiddly thing to take into account about upper completion. We're usually working in the space of a-measures $M^a\left(F\right({\pi }_{pa}\left)\right)$ or the nirvana-free equivalent. But the variant of upper completion we impose on our sets is: take the nirvana-free part of your set of interest, take the upper completion w.r.t the cone of nirvana-free sa-measures, then intersect with a-measures again. So, instead of the earlier setting where we could have any old sa-measure in our set and we could add any old sa-measure to them, now, since we're working purely in the space of a-measures and only demanding upper closure of the nirvana-free part, our notion of upper completion is something more like "start with a nirvana-free a-measure, you can add a nirvana-free sa-measure to it, and adding them has to make a nirvana-free a-measure"

Even worse, this is the notion of upper completion we impose, but for checking whether a point counts as minimal, we use the cone of sa-measures (with nirvana). So, for certifying that a point is non-minimal, we have to go "hey, there's another a-measure where we can add an sa-measure and make our point of interest". A different notion of upper completion here.

And, to make matters even worse, sometimes we do arguments involving the cone of sa-measures or nirvana-free sa-measures and don't impose the a-measure restriction. I'll try to clarify which case we're dealing with, but I can't guarantee it'll all be clear or sufficiently edited.

There's a partial ordering on partial policies, which is ${\pi }_{pa}\ge {\pi }_{pa}^{\prime }$ if the two policies never disagree on which action to take, and ${\pi }_{pa}$ is defined on more histories than ${\pi }_{pa}^{\prime }$ is (is a bigger tree). So, instead of viewing a partial policy as a tree, we can view the set of partial policies as a big poset. The full policies $\pi$ are at the top, the empty policy ${\pi }_{\varnothing }$ is at the bottom. Along with this, we've got two important notions. One is the fundamental sequence of a partial policy. Envisioning it at the tree level, ${\pi }_{pa}^n$ is "the tree that is ${\pi }_{pa}$, just cut off at level $n$". Envisioning it at the poset level, the sequence ${\pi }_{pa}^n$ is a chain of points in our poset ascending up to the point ${\pi }_{pa}$.

Also synergizing with the partial-order view, we've got functions heading down the partial policy poset. $p{r}_{\ast }^{{\pi }_{pa}^{hi},{\pi }_{pa}^{lo}}$ is the function that takes an a-measure or sa-measure over $F\left({\pi }_{pa}^{hi}\right)$, and is like "ok, everything in $F\left({\pi }_{pa}^{hi}\right)$ has a unique prefix in $F\left({\pi }_{pa}^{lo}\right)$, push your measure component down, keep the $b$ term the same". A good way of intuiting this is that this sort of projection describes what happens when you crunch down a measure over 10-bit-bitstrings to a measure over 8-bit-bitstrings. So view your poset of partial policies as being linked together by a bunch of projection arrows heading down.

There's a function $\Theta$ mapping each partial policy ${\pi }_{pa}$ to a set of a-measures over $F\left({\pi }_{pa}\right)$ (or the nirvana-free variant), fulfilling some special properties. Maybe $\Theta$ is only defined over policy stubs or full policies, in which case we use ${\Theta }^{st}$ or ${\Theta }^{\omega }$, respectively. So, the best mental visualization/sketching aid for a lot of the proofs is visualizing your partial policies of interest with an ordering on them where bigger=up and smaller=down, and have a set/point for each one, that organizes things fairly well and is how many of these proofs were created.

Every $\Theta$ (or the stub/full policy analogue) is associated with a ${\lambda }^{\odot }$ and $b^{\odot }$ value, which is "smallest upper bound on the $\lambda$ of the minimal points of the $\Theta \left({\pi }_{pa}\right)$ sets" and "smallest upper bound on the $b$ of the minimal points of the $\Theta \left({\pi }_{pa}\right)$ sets". Accordingly, the set $\{\le \odot \}$ is defined as $\left\{\right(\lambda \mu ,b)|\lambda +b\le {\lambda }^{\odot }+b^{\odot }\}$, and is a way of slicing out a bounded region of a set that contains all minimal points, if we need to do compactness arguments.

Finally, we'll reiterate two ultra-important results from basic inframeasure theory that get used a lot in here and will be tossed around casually for arguments without citing where they came from. There's the Compactness Lemma, which says that if you have a bound on the $\lambda$ values and the $b$ values of a closed set of a-measures, the set is compact. There's also Theorem 2, which says that you can break down any sa-measure into (minimal point + sa-measure), we use that decomposition a whole lot.

Other results we'll casually use are that projections commute (projecting down and then down again is the same as doing one big projection down), projections are linear (it doesn't matter whether you mix before or after projecting), projections don't expand distance (if two a-measures are $ϵ$ apart before being projected down, they'll be $ϵ$ or less apart after being projected down), if two a-measures are distinct in$M^a\left(F\right({\pi }_{pa}\left)\right)$, then the measure components differ at some finite time (or the $b$ terms differ), so we can project down to some finite ${\pi }_{pa}^n$ (same thing, just end history at time $n$) and they'll still be different, and projections preserve the $\lambda$ and $b$ value of an a-measure.

One last note, $M^a\left(\infty \right)$ is the space of a-measures on nirvana-free histories. This is all histories, not just the ones compatible with a specific policy. And a surmeasure $SM$ is like a measure, but it can assign $0^{+}$ value to a nirvana event, marking it as "possible" even though it has 0 (arbitrarily low) measure.

Now, we can begin. Our first order of business is showing how the surtopology/surmetric/surmeasures are made and link together, but the bulk of this is the Isomorphism theorem. Which takes about 20 lemmas to set up first, in order to compress all the tools we need for it, and then the proof itself is extremely long. After that, things go a bit faster.

Lemma 1: $d(x,x^{\prime }):=max\left(d_1\right(x,x^{\prime }),d_2(x,x^{\prime }\left)\right)$ is a metric if $d_1$ is a metric and $d_2$ is a pseudometric.

For identity of indiscernibles, $d(x,x^{\prime })=0\to d_1(x,x^{\prime })=0\to x=x^{\prime }$ because $d_1$ is a metric, and in the reverse direction, if $x=x^{\prime }$, then $d_2(x,x^{\prime })=0$ (pseudometrics have $0$ distance from a point to itself) and $d_1(x,x^{\prime })=0$, so $d(x,x^{\prime })=0$.

For symmetry, both metrics and pseudometrics have symmetry, so

$d(x,x^{\prime })=max\left(d_1\right(x,x^{\prime }),d_2(x,x^{\prime }\left)\right)=max\left(d_1\right(x^{\prime },x),d_2(x^{\prime },x\left)\right)=d(x^{\prime },x)$

For triangle inequality, both metrics and pseudometrics fulfill the triangle inequality, so

$d(x,z)=max\left(d_1\right(x,z)+d_2(x,z\left)\right)\le max\left(d_1\right(x,y)+d_1(y,z),d_2(x,y)+d_2(y,z\left)\right)$

$\le max\left(d_1\right(x,y),d_2(x,y\left)\right)+max\left(d_1\right(y,z),d_2(y,z\left)\right)=d(x,y)+d(y,z)$

And we're done.

Lemma 2: The surmetric is a metric.

To recap, the surmetric over sa-measures is

$d_s\left(\right(m,b),(m^{\prime },b^{\prime }\left)\right):=max\left(d\right(m,m^{\prime })+|b-b^{\prime }|,{\gamma }^{t(m,m^{\prime })})$

where $\gamma <1$, and $t(m,m^{\prime })$ is the minimum length of a Nirvana-containing history that has positive measure according to $m$ and $0$ measure according to $m^{\prime }$ (or vice-versa) We'll show that ${\gamma }^{t(m,m^{\prime })}$ acts as a pseudometric, and then invoke Lemma 1.

The first three conditions of nonnegativity, ${\gamma }^{t(m,m)}={\gamma }^{\infty }=0$, and symmetry are immediate. That just leaves checking the triangle inequality. Let $t_1:=t(m_1,m_2)$, $t_2:=t(m_2,m_3)$, and $t_3:=t(m_1,m_3)$.

Assume $t_3<min(t_1,t_2)$. Then, going from $m_1$ to $m_2$, all changes in the possibility of a Nirvana-history take place strictly after $t_3$, and going from $m_2$ to $m_3$, all changes in the possibility of a Nirvana-history also take place strictly after $t_3$, so $m_1$ and $m_3$ behave identically (w.r.t. Nirvana-possibilities) up to and including time $t_3$, which is impossible, because of $t_3$ being "what's the shortest time where $m_1$ and $m_3$ disagree on the possiblility of a Nirvana-history".
Therefore, $t_3\ge min(t_1,t_2)$. and this case is ruled out.

In one case, either $t_1$ or $t_2$ are $>t_3$. Without loss of generality, assume it's $t_1$. Then, ${\gamma }^{t_3}<{\gamma }^{t_1}\le {\gamma }^{t_1}+{\gamma }^{t_2}$ and the triangle inequality is shown.

In the other case, $t_1=t_2=t_3$. In that case, ${\gamma }^{t_3}={\gamma }^{t_1}\le {\gamma }^{t_1}+{\gamma }^{t_2}$ And the triangle inequality is shown.

Therefore, ${\gamma }^{t(m,m^{\prime })}$ is a pseudometric. Now, we can invoke Lemma 1 to show that $d_s$ is a metric.

Theorem 1: The surmetric on the space of sa-measures $M^a\left(F\right({\pi }_{pa}\left)\right)$ induces the surtopology. The Cauchy completion of $M^a\left(F\right({\pi }_{pa}\left)\right)$ w.r.t the surmetric is exactly the space of sa-surmeasures.

Proof sketch: First, use the metric to get an entourage (check the Wikipedia page on "Uniform Space"), and use the entourage to get a topology. Then, we go in both directions, and check that entourage-open sets are open according to the surtopology and the surtopology subbasis sets are entourage-open, to conclude that the topology induced by the surmetric is exactly the surtopology. Then, for the Cauchy completion, we'll show a bijection between equivalence classes of Cauchy sequences w.r.t. the surmetric and sa-surmeasures.

The surmetric is $d_s\left(\right(m,b),(m^{\prime },b^{\prime }\left)\right):=max\left(d\right(m,m^{\prime })+|b-b^{\prime }|,{\gamma }^{t(m,m^{\prime })})$ where $\gamma <1$, and $t$ is the minimum length of a Nirvana-containing history that has positive measure according to $m$ and $0$ measure according to $m^{\prime }$ (or vice-versa)

From the Wikipedia page on "Uniform Space", a fundamental system of entourages for $M^{sa}\left(F\right({\pi }_{pa}\left)\right)$ is given by

$\left\{\right(M,M^{\prime })\in M^{sa}(F\left({\pi }_{pa}\right))\times M^{sa}(F\left({\pi }_{pa}\right)):d_s(M,M^{\prime })\le ϵ\}$

A set $O$ is open w.r.t. the uniformity iff for all $M\in O$, there exists an entourage $V$ where $V\left[M\right]$ lies entirely within $O$ (wikipedia page). Because $V$ is a subset of $M^a\left(F\right({\pi }_{pa}\left)\right)\times M^a\left(F\right({\pi }_{pa}\left)\right)$, $V\left[M\right]$ is the set of all the second components paired with a given sa-measure.
So, let's say $O$ is open w.r.t. the uniformity. Then, for all $M\in O$, there's an entourage $V$ where $V\left[M\right]$ lies entirely within $O$. A fundamental system of entourages has the property that every entourage is a superset of some set from the fundamental system. Thus, from our earlier definition of the fundamental system, there exists some ${ϵ}_M$ where

$\{M^{\prime }\in M^{sa}(F\left({\pi }_{pa}\right)):d_s(M,M^{\prime })\le {ϵ}_M\}\subseteq O$

We'll construct an open set from the surtopology that is a subset of this set and contains $M$, as follows. First, observe that if $d_s(M,M^{\prime })\le {ϵ}_M$, then $d(M,M^{\prime })\le {ϵ}_M$, and ${\gamma }^{t(m,m^{\prime })}\le {ϵ}_M$. For the latter, there are finitely many nirvana-containing histories with a length less than ${\log }_{\gamma }\left({ϵ}_M\right)+1$, and if a $M^{\prime }$ matches $M$ w.r.t. which nirvana-containing histories of that finite set are possible or impossible, then ${\gamma }^{t(m,m^{\prime })}<{ϵ}_M$ (because $M$ and $M^{\prime }$ only differ on which Nirvana-histories are possible at very late times)

Accordingly, intersect the following sets:

1: the open ball centered at $M$ with a size of ${ϵ}_M$

2: For all the nirvana-histories $hN$ where $|hN|\le {\log }_{\gamma }\left({ϵ}_M\right)+1$ and $m\left(hN\right)>0$, intersect all the sets of a-measures where that history has positive measure. These are open because they're the complements of "this finite history has zero measure", which is a closed set of sa-measures.

3: For all the nirvana-histories $hN$ where $|hN|\le {\log }_{\gamma }\left({ϵ}_M\right)+1$ and $m\left(hN\right)=0$, intersect all the sets of a-measures where that nirvana-history has 0 measure. These are open because they are subbasis sets for the surtopology.

We intersected finitely many open sets, so the result is open. Due to 2 and 3 and our earlier discussion, any $M^{\prime }$ in the intersection must have ${\gamma }^{t(m,m^{\prime })}<{ϵ}_M$. Due to 1, $d(M,M^{\prime })<{ϵ}_M$.

This finite intersection of open sets (in the surtopology) produces an open set that contains $M$ (obviously) and is a subset of $\{M^{\prime }\in M^{sa}(F\left({\pi }_{pa}\right)):d_s(M,M^{\prime })\le {ϵ}_M\}$, which is a subset of $V\left[M\right]$ which is a subset of $O$.

Because this argument can be applied to every point $M\in O$ to get an open set (in the surtopology) that contains $M$ and is a subset of $O$, we can make $O$ itself by just unioning all our open sets together, which shows that $O$ is open in the surtopology.

In the reverse direction, let's show that all sets in the subbasis of the surtopology are open w.r.t. the uniform structure.

First, we'll address the open balls around a point $M$. Every point $M^{\prime }$ in such an open ball has some ${ϵ}_{M^{\prime }}$-sized open ball which fits entirely within the original open ball. Then, we can just consider our entourage $V$ being

$\{M,M^{\prime \prime }\in M^{sa}(F\left({\pi }_{pa}\right))\times M^{sa}(F\left({\pi }_{pa}\right)):d_s(M,M^{\prime \prime })\le \frac{{ϵ}_{M^{\prime }}}{2}\}$

And then $V\left[M^{\prime }\right]$ is all points that are $\frac{{ϵ}_{M^{\prime }}}{2}$ or less away from $M^{\prime }$ according to the surmetric, and $d_s(M^{\prime },M^{\prime \prime })\ge d(M^{\prime },M^{\prime \prime })$ so this is a subset of the ${ϵ}_{M^{\prime }}$-sized ball around $M^{\prime }$, which is a subset of the ball around $M$. The extra measure we added in total on step $n$ is (note that no nirvana-history can have a length of 0, so we start at 1, and $t$ denotes timesteps in the history)

${\sum }_t{\sum }_{hN:|hN|=t}\frac{2^{-(n+t)}}{\#\left(t\right)}={\sum }_t\#\left(t\right)\frac{2^{-(n+t)}}{\#\left(t\right)}\le {\sum }_t{2}^{-(n+t)}=2^{-n}{\sum }_t{2}^{-t}\le 2^{-n}$

So, as $n$ increases, the deviation of this sequence of sa-measures from the limit sa-surmeasure approaches $0$ w.r.t. the usual metric, and every component in this sequence agrees with the others and the limit sa-surmeasure on which nirvana events are possible or impossible, so it's a Cauchy sequence limiting to the sa-surmeasure of interest.

Thus, all parts have been shown. The surmetric induces the surtopology, and the Cauchy completion of the sa-measures w.r.t. the surmetric is the set of sa-surmeasures. The same proof works if you want a-surmeasures (get it from the a-measures), or surmeasures (get it from the measures).

Alright, now we can begin the lemma setup for the Isomorphism Theorem, which is the Big One. See you again at Lemma 21.

Lemma 3: If $B\subseteq M^a\left(F^{NF}\right({\pi }_{st}\left)\right)$ and $B$ is nonempty, closed, convex, nirvana-free upper-complete, and has bounded-minimals, then $c.h\left(B^{min}\right)=c.h\left(B^{\text{xmin}}\right)$

So, first, $B^{\text{xmin}}$ refers to the set of extreme minimal points of $B$. An extreme point of $B$ is one that cannot be written as a mixture of other points in $B$.

Proof Sketch: One subset direction, $c.h\left(B^{min}\right)\supseteq c.h\left(B^{\text{xmin}}\right)$ is immediate. For the other direction, we need a way to write a minimal point as a finite mixture of extreme minimal points. What we do is first show that all extreme points in $B$ must lie below the ${\lambda }^{\odot }+b^{\odot }$ bound by crafting a way to write them as a mix of different points with upper completion if they violate the bound. Then, we slice off the top of $B$ to get a compact convex set with all the original minimal (and extreme) points in it. Since ${\pi }_{st}$ is a policy stub, $F^{NF}\left({\pi }_{st}\right)$ has finitely many possible outcomes, so we're working in a finite-dimensional vector space. In finite dimensions, a convex compact set is the convex hull of its extreme points, which are all either (extreme points in $B$ originally), or (points on the high hyperplane we sliced at). Further, a minimal point can only be made by mixing together other minimal points. Putting this together, our minimal point of interest can be made by mixing together extreme minimal points, and the other subset direction is immediate from there.

Proof: As stated in the proof sketch, one subset direction is immediate, so we'll work on the other one. To begin with, fix a $M^{ex}$ that is extreme in $B$. It's an a-measure. If $M^{ex}$ has $\lambda +b>{\lambda }^{\odot }+b^{\odot }$, then it's not minimal ($B$ has bounded-minimals) so we can decompose it into a minimal point $M^{min}$ respecting the bound and some nonzero sa-measure $M^{\ast }$. $M^{ex}=M^{min}+M^{\ast }$. Now, consider the point $M^{min}+(m^{\ast -},-m^{\ast -}(1\left)\right)$ instead. We're adding on the negative part of $m^{\ast }$, and just enough of a $b$ term to compensate, so it's an sa-measure. The sum of these two points is an a-measure, because we already know from $M^{ex}$ being an a-measure that the negative part of $m^{\ast }$ isn't enough to make any negative parts when we add it to $m^{min}$.

Anyways, summing the two parts like that saps a bit from the $\lambda$ value of $M^{min}$, but adds an equal amount on the $b$ value, so it lies below the ${\lambda }^{\odot }+b^{\odot }$ "barrier", and by nirvana-free upper-completeness, it also lies in $B$. Then, we can express $M^{ex}$ as

$M^{ex}=M^{min}+M^{\ast }=M^{min}+(m^{\ast },b^{\ast })=M^{min}+(m^{\ast -},-m^{\ast -}(1\left)\right)+(m^{\ast +},b^{\ast }+m^{\ast -}(1\left)\right)$

$=0.5(M^{min}+(m^{\ast -},-m^{\ast -}\left(1\right)\left)\right)+0.5(M^{min}+(m^{\ast -},-m^{\ast -}\left(1\right))+2(m^{\ast +},b^{\ast }+m^{\ast -}\left(1\right)\left)\right)$

Now, we already know that $M^{min}+(m^{\ast -},-m^{\ast -}(1\left)\right)$ is an a-measure, and $(m^{\ast +},b^{\ast }+m^{\ast -}(1\left)\right)$ is an a-measure (no negative parts, end term is $\ge 0$). So, we just wrote our extreme point as a mix of two distinct a-measures, so it's not extreme. Contradiction. Therefore, all extreme points have $\lambda +b\le {\lambda }^{\odot }+b^{\odot }$.

Let's resume. From bounded-minimals, we know that $B$ has a suitable bound on $\lambda +b$, so the minimal points respect the ${\lambda }^{\odot }+b^{\odot }$ bound. Take $B$ and chop it off at some high hyperplane, like $\lambda +b\le 2({\lambda }^{\odot }+b^{\odot })$. (the constant 2 isn't that important, it just has to be above 1 so we net all the extreme points and minimal points). Call the resulting set $C$. Due to the bound, and $B$ being closed, $C$ is compact by the Compactness Lemma. It's also convex.

Now, invoke the Krein-Milman theorem (and also, we're in a finite-dimensional space since we're working with a stub, finitely many observation leaf nodes, so we don't need to close afterwards, check the Wikipedia page for Krein-Milman Theorem at the bottom) to go $C=c.h\left(\text{extreme}\right(C\left)\right)$. The only extreme points in $C$ are either points that were originally extreme in $B$, or points on the high hyperplane that we chopped at.

Fix some$M^{min}\in B^{min}$. $B^{min}\subseteq C$, so $M^{min}\in C$. Thus, $M^{min}$ can be written as a finite mixture of points from $\text{extreme}\left(C\right)$. However, because $M^{min}$ is minimal, it can only be a mixture of minimal points, as we will show now.

Decompose $M^{min}$ into $E_{\zeta }{M}_i$, and then decompose the $M_i$ into $M_i^{min}+M_i^{\ast }$ . To derive a contradiction, assume there exists some $i^{\prime }$ where $M_{i^{\prime }}$ isn't minimal, so that $M_{i^{\prime }}^{\ast }$ isn't 0. Then,

$M^{min}=E_{\zeta }{M}_i=E_{\zeta }(M_i^{min}+M_i^{\ast })=E_{\zeta }\left(M_i^{min}\right)+E_{\zeta }\left(M_i^{\ast }\right)$

Thus, we have decomposed our minimal point into another point which is also present in $B$, and a nonzero sa-measure because $M_{i^{\prime }}^{\ast }$ is nonzero, so our original minimal point is actually nonminimal. and we have a contradiction. Therefore, all decompositions of a minimal point into a mix of points must have every component point being minimal as well.

So, when we decomposed $M^{min}$ into a mix of points in $\text{extreme}\left(C\right)$, all the extreme points we decomposed it into are minimal, so there's no component on the high hyperplane. $M^{min}$ was arbitrary in $B^{min}$ establishing that $B^{min}\subseteq c.h\left(B^{\text{xmin}}\right)$. Therefore, $c.h\left(B^{min}\right)\subseteq c.h\left(B^{\text{xmin}}\right)$

So we have our desired result.

Lemma 4: If ${\pi }_{pa}\ge {\pi }_{st}^{hi}\ge {\pi }_{st}^{lo}$, and $A\subseteq M^a\left(F\right({\pi }_{st}^{hi}\left)\right)$ and $B\subseteq M^a\left(F\right({\pi }_{st}^{lo}\left)\right)$ (also works with the nirvana-free variants) and $p{r}_{\ast }^{{\pi }_{st}^{hi},{\pi }_{st}^{lo}}\left(A\right)\subseteq B$ then $\left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}^{hi}}{)}^{-1}\right(A)\subseteq (p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}^{lo}}{)}^{-1}\left(B\right)$ This works for surmeasures too.

A point $M$ in the preimage of $A$ has $p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}^{hi}}\left(M\right)\in A$, and by projections commuting and projecting down further landing you in $B$, we get $p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}^{lo}}\left(M\right)\in B$, so $M$ is in the preimage of $B$ too.

Lemma 5: Given a partial policy ${\pi }_{pa}$ and stub ${\pi }_{st}$, if ${\pi }_{pa}\ge {\pi }_{st}$, then $\exists n:{\pi }_{pa}^n\ge {\pi }_{st}$

${\pi }_{st}$ is a stub that specifies less about what the policy does than ${\pi }_{pa}$, and because it's a stub it has a minimum time beyond which it's guaranteed to be undefined, so just let that be your $n$. ${\pi }_{pa}^n$ then specifies everything that ${\pi }_{st}$ does, and maybe more, because it has all the data of ${\pi }_{pa}$ up till time $n$.

Lemma 6: If ${\pi }_{pa}$ is a partial policy, and $\forall {\pi }_{st}^{lo},{\pi }_{st}^{hi}\ge {\pi }_{st}^{lo}:p{r}_{\ast }^{{\pi }_{st}^{hi},{\pi }_{st}^{lo}}\left({\Theta }^{st}\right({\pi }_{st}^{hi}\left)\right)\subseteq {\Theta }^{st}\left({\pi }_{st}^{lo}\right)$ holds, then, for all $m$, ${\bigcap }_{{\pi }_{st}\le {\pi }_{pa}}\left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}}{)}^{-1}\right({\Theta }^{st}\left({\pi }_{st}\right))={\bigcap }_{n\ge m}(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}{)}^{-1}\left({\Theta }^{st}\right({\pi }_{pa}^n\left)\right)$ This works for surmeasures too.

First, all the ${\pi }_{pa}^n\le {\pi }_{pa}$ are stubs, so we get one subset direction immediately.

${\bigcap }_{{\pi }_{st}\le {\pi }_{pa}}\left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}}{)}^{-1}\right({\Theta }^{st}\left({\pi }_{st}\right))\subseteq {\bigcap }_{n\ge m}(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}{)}^{-1}\left({\Theta }^{st}\right({\pi }_{pa}^n\left)\right)$

In the other direction, use Lemma 5 to find a ${\pi }_{pa}^n\ge {\pi }_{st}$, with $n\ge m$, and then pair

$\forall {\pi }_{st}^{lo},{\pi }_{st}^{hi}\ge {\pi }_{st}^{hi}:p{r}_{\ast }^{{\pi }_{st}^{hi},{\pi }_{st}^{lo}}\left({\Theta }^{st}\right({\pi }_{st}^{hi}\left)\right)\subseteq {\Theta }^{st}\left({\pi }_{st}^{lo}\right)$

with Lemma 4 to deduce that

$\left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}{)}^{-1}\right({\Theta }^{st}\left({\pi }_{pa}^n\right))\subseteq (p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}}{)}^{-1}\left({\Theta }^{st}\right({\pi }_{st}\left)\right)$

Due to being able to take any stub preimage and find a smaller preimage amongst the fundamental sequence for ${\pi }_{pa}$ (with an initial segment clipped off) we don't need anything other than the preimages of the fundamental sequence (with an initial segment clipped off), which establishes the other direction and thus our result.

Lemma 7: If $M$ is an a-measure and $p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}}\left(M\right)=M^{\prime }$ and $M^{\prime }=M^{{}^{\prime }lo}+M^{{}^{\prime }\ast }$ and $M^{{}^{\prime }lo}$ is an a-measure, then there exists a $M^{lo}\in M^a\left(F\right({\pi }_{pa}\left)\right)$ (or the nirvana-free variant) s.t. $p{r}_{\ast }^{{\pi }_{pa},{\pi }_{st}}\left(M^{lo}\right)=M^{{}^{\prime }lo}$ and there's an sa-measure $M^{\ast }$ s.t. $M^{lo}+M^{\ast }=M$. This works for a-surmeasures and sa-surmeasures too.

What this essentially says is "let's say we start with a $M$ and project it down to $M^{\prime }$, and then find a point $M^{{}^{\prime }lo}$ below $M^{\prime }$. Can we "go back up" and view $M^{{}^{\prime }lo}$ as the projection of some point below $M$? Yes". It's advised to sketch out the setup of this one, if not the proof itself.

Proof sketch: To build our $M^{lo}$ and $M^{\ast }$, the $b$ components are preserved, but crafting the measure component for them is tricky. They've gotta project down to $M^{{}^{\prime }lo}$ and $M^{{}^{\prime }\ast }$ so those two give us our base case to start working from with the measures (and automatically get the "must project down appropriately" requirement) and then we can recursively build up by extending both of them with the conditional probabilities that $M$ gives us. However, we must be wary of division-by-zero errors and accidentally assigning negative measure on Nirvana, which complicates things considerably. Once we've shown how to recursively build up the measure components of our $M^{lo}$ and $M^{\ast }$, we then need to check four things. That they're both well formed (sum of measure on 1-step extensions of a history=measure on the history, no semimeasures here), that they sum up to make $M$, the measure component of $M^{lo}$ can't go negative anywhere (to certify that it's an a-measure), and that the $b$ term attached to $M^{\ast }$ is big enough to cancel out the negative regions (to certify that it's an sa-measure).

Proof: Let $M^{lo}=(m^{lo},b^{lo})$ where $b^{lo}$ is the $b$ term of $M^{{}^{\prime }lo}$. Let $M^{\ast }=(m^{\ast },b^{\ast })$ where $b^{\ast }$ is the $b$ term of $M^{{}^{\prime }\ast }$. Recursively define $m^{lo}$ and $m^{\ast }$ on $h$ that are prefixes of something in $F\left({\pi }_{pa}\right)$ (or the nirvana-free variant) as follows:

If $h$ is a prefix of something in $F\left({\pi }_{st}\right)$ (or the nirvana-free variant), $m^{lo}\left(h\right)=m^{{}^{\prime }lo}\left(h\right)$ and $m^{\ast }\left(h\right)=m^{{}^{\prime }\ast }\left(h\right)$. That defines our base case. Now for how to inductively build up by mutual recursion. Let's use $haN$ for a nirvana-history and $hao$ for a non-nirvana history.

If $m^{\ast }\left(h\right)<0$, then

$m^{lo}\left(haN\right)=m\left(haN\right),m^{lo}\left(hao\right)=m\left(hao\right)-\frac{m^{\ast }\left(h\right)}{\#o}$

$m^{\ast }\left(haN\right)=0,m^{\ast }\left(hao\right)=\frac{m^{\ast }\left(h\right)}{\#o}$

$\#o$ is the number of non-nirvana observations that can come after $ha$.

If $m^{\ast }\left(h\right)\ge 0$ and $m\left(h\right)>0$, then

$m^{lo}\left(hao\right)=\frac{m\left(hao\right)}{m\left(h\right)}{m}^{lo}\left(h\right),m^{\ast }\left(hao\right)=\frac{m\left(hao\right)}{m\left(h\right)}{m}^{\ast }\left(h\right)$

and the same holds for defining $m^{lo}\left(haN\right)$ and $m^{\ast }\left(haN\right)$.

If $m^{\ast }\left(h\right)\ge 0$ and $m\left(h\right)=0$, then $m^{lo}\left(hao\right)=m^{\ast }\left(hao\right)=0$

We need to verify that these sum up to $m$, that they're both well-formed signed measures, that $m^{lo}$ has no negative parts, and that the $b$ value for $M^{\ast }$ is big enough. $m^{lo}$ having no negative parts is immediate by the way we defined it, because it's nonnegative on all the base cases since $m^{{}^{\prime }lo}$ came from an a-measure, and $m$ came from an a-measure as well which lets you use induction to transfer that property all the way up the histories.

To verify that they sum up to $m$, observe that for base-case histories in $F\left({\pi }_{st}\right)$,

$m^{lo}\left(h\right)+m^{\ast }\left(h\right)=m^{{}^{\prime }lo}\left(h\right)+m^{{}^{\prime }\ast }\left(h\right)=m^{\prime }\left(h\right)=m\left(h\right)$

For non-base-case histories $hao$ we can use induction (assume it's true for $h$) and go:

Negative case, $m^{\ast }\left(h\right)<0$.

$m^{lo}\left(haN\right)+m^{\ast }\left(haN\right)=m\left(haN\right)+0=m\left(haN\right)$

$m^{lo}\left(hao\right)+m^{\ast }\left(hao\right)=m\left(hao\right)-\frac{m^{\ast }\left(h\right)}{\#o}+\frac{m^{\ast }\left(h\right)}{\#o}=m\left(hao\right)$

Nonnegative case, no division by zero.

$m^{lo}\left(hao\right)+m^{\ast }\left(hao\right)=\frac{m\left(hao\right)}{m\left(h\right)}\left(m^{lo}\right(h)+m^{\ast }(h\left)\right)=\frac{m\left(hao\right)}{m\left(h\right)}m\left(h\right)=m\left(hao\right)$

Zero case: $m\left(hao\right)=0$ because $m\left(h\right)=0$ and $m$ came from an a-measure and has no negative parts. $m^{lo}\left(hao\right)+m^{\ast }\left(hao\right)=0+0=0=m\left(hao\right)$

Ok, so we've shown that $m^{lo}+m^{\ast }=m$.

What about checking that they're well-formed signed measures? To do this, it suffices to check that summing up their measure-mass over $ha{o}_i$ gets the measure-mass over $h$. This works over the base case, so we just have to check the induction steps.

In the negative case, for $m^{\ast }$,

$m^{\ast }\left(haN\right)+{\sum }_i{m}^{\ast }\left(ha{o}_i\right)={\sum }_i\frac{m^{\ast }\left(h\right)}{\#o}=m^{\ast }\left(h\right)$

and for $m^{lo}$

$m^{lo}\left(haN\right)+{\sum }_i{m}^{lo}\left(ha{o}_i\right)=m\left(haN\right)+{\sum }_i\left(m\right(ha{o}_i)-\frac{m^{\ast }\left(h\right)}{\#o})=m\left(h\right)-m^{\ast }\left(h\right)=m^{lo}\left(h\right)$

In the nonnegative case, no division by zero, then

$m^{lo}\left(haN\right)+{\sum }_i{m}^{lo}\left(ha{o}_i\right)=\frac{m\left(haN\right)}{m\left(h\right)}{m}^{lo}\left(h\right)+{\sum }_i\frac{m\left(ha{o}_i\right)}{m\left(h\right)}{m}^{lo}\left(h\right)$

$=\frac{m^{lo}\left(h\right)}{m\left(h\right)}\left(m\right(haN)+{\sum }_{i}m(ha{o}_i\left)\right)=\frac{m^{lo}\left(h\right)}{m\left(h\right)}m\left(h\right)=m^{lo}\left(h\right)$

And similar for $m^{\ast }$.

In the zero case where $m\left(h\right)=0$, we need to show that $m^{lo}\left(h\right)$ and $m^{\ast }\left(h\right)$ will also be zero. Winding $h$ back, there's some longest prefix $h^{\prime }$ where $m\left(h^{\prime }\right)>0$. Now, knowing that $m\left(h^{\prime }\right)=m^{lo}\left(h^{\prime }\right)+m^{\ast }\left(h^{\prime }\right)$, we have two possible options here.

In the first case, $m^{\ast }\left(h^{\prime }\right)\ge 0$, so $m^{lo}\left(h^{\prime }ao\right)$ (advancing one step) is:

$m^{lo}\left(h^{\prime }ao\right)=\frac{m\left(h^{\prime }ao\right)}{m\left(h^{\prime }\right)}{m}^{lo}\left(h^{\prime }\right)=\frac{0}{m\left(h^{\prime }\right)}{m}^{lo}\left(h^{\prime }\right)=0$

And similar for $m^{\ast }\left(h^{\prime }ao\right)$, so they're both 0, along with $m^{\prime }$, on $h^{\prime }ao$, and then the zero case transfers the "they're both zero" property all the way up to $h$.

In the second case, $m^{\ast }\left(h^{\prime }\right)<0$ and $m^{lo}\left(h^{\prime }\right)>0$. Then, proceeding forward, $m^{\ast }\left(h^{\prime }ao\right)<0$, and this keeps holding all the way up to $h$, so we're actually in the negative case, not the zero case.

So, if $m\left(h\right)=0$, then $m^{lo}\left(h\right)=m^{\ast }\left(h\right)=0$ as long as we're in the case where $m^{\ast }\left(h\right)\ge 0$ and $m\left(h\right)=0$. Then, it's easy. $m^{lo}\left(haN\right)+{\sum }_i{m}^{lo}\left(ha{o}_i\right)=0=m^{lo}\left(h\right)$ and the same for $m^{\ast }$.

Also, $m^{\ast }$, by the way we defined it, never puts negative measure on a nirvana event, so we're good there, they're both well-formed signed measures. For the $b^{\ast }$ value being sufficient to compensate for the negative-measure of $m^{\ast }$, observe that the way we did the extension, the negative-measure for $m^{\ast }$ is the same as the negative measure for $m^{{}^{\prime }\ast }$, and $b^{\ast }=b^{{}^{\prime }\ast }$, and the latter is sufficient to cancel out the negative measure for $m^{{}^{\prime }\ast }$, so we're good there.

We're done now, and this can be extended to a-surmeasures by taking the $0^{+}$ nirvana-events in $m$ and saying that all those nirvana-events have $0^{+}$ measure in $m^{lo}$.

Lemma 8: Having a $\lambda +b$ bound on a set of a-surmeasures is sufficient to ensure that it's contained in a compact set w.r.t the surtopology.

This is the analogue of the Compactness Lemma for the sur-case. We'll keep it in the background instead of explicitly invoking it each time we go "there's a bound, therefore compactness". It's important.

Proof sketch: Given a sequence, the bound gets convergence of the measure part by the Compactness Lemma, and then we use Tychonoff to show that we can get a subsequence where the a-surmeasures start agreeing on which nirvana events are possible or impossible, for all nirvana events, so their first time of disagreement gets pushed arbitrarily far out, forcing convergence w.r.t. the surmetric.

Proof: given a sequence of a-surmeasures $S{M}_n$, and rounding them off to their "standard" part (slicing off the $0^{+}$ probability), we can get a convergent subsequence, where the measure part and $b$ part converges, by the Compactness Lemma since we have a $\lambda +b$ bound, which translates into bounds on $\lambda$ and $b$.

Now, all we need is a subsequence of that subsequence that ensures that, for each nirvana-event, the sequence of a-surmeasures starts agreeing on whether it's possible or impossible. There are countably many finite histories, and each nirvana-history is a finite history, so we index our nirvana events by natural numbers, and we can view our sequence as wandering around within $\{0,1{\}}^{\omega }$, where the t'th coordinate keeps track of whether the t'th nirvana event is possible or impossible. $\{0,1{\}}^{\omega }$ is compact by Tychonoff's Theorem, so we can find a convergent subsequence, which corresponds to a sequence of a-surmeasures that, for any nirvana event, eventually start agreeing on whether it's possible or impossible. There's finitely many nirvana events before a certain finite time, so if we go far enough out in the $n$, the a-surmeasures agree on what nirvana events are possible or impossible for a very long time, and so the surdistance shrinks to 0 and they converge, establishing that all sequences have a convergent subsequence, so the set is compact.

Lemma 9: Given a ${\pi }_{pa}$ and a sequence of nonempty compact sets $B_n\in M^a\left(F\right({\pi }_{pa}^n\left)\right)$ (or the nirvana-free variant) where $\forall n:p{r}_{\ast }^{{\pi }_{pa}^{n+1},{\pi }_{pa}^n}\left(B_{n+1}\right)\subseteq B_n$ then there is a point $M\in M^a\left(F\right({\pi }_{pa}\left)\right)$ (or the nirvana-free variant) where $\forall n:p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}\left(M\right)\in B_n$. This also works with a-surmeasures.

Sketch this one out. It's essentially "if sets get smaller and smaller, but not empty, as you ascend up the chain ${\pi }_{pa}^n$ towards ${\pi }_{pa}$, and are nested in each other, then there's something at the ${\pi }_{pa}$ level that projects down into all the ${\pi }_{pa}^n$"

Proof sketch: Projection preserves $\lambda$ and $b$, the Compactness Lemma says that compactness means you have a $\lambda$ and $b$ bound, so the preimage of a compact set is compact. Then, we just have to verify the finite intersection property to show that the intersection of the preimages is nonempty, which is pretty easy since all our preimages are nested in each other like an infinite onion.

Proof: Consider the intersection ${\bigcap }_n\left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}{)}^{-1}\right(B_n)$. Because $B_n$ are all compact, they have a $\lambda$ and $b$ bound. Projection preserves the $\lambda$ and $b$ values, so the preimage of $B_n$ has a $\lambda$ and $b$ bound, therefore lies in a compact set (By Lemma 8 for the sur-case). The preimage of a closed set is also closed set, so all these preimages are compact. This is then an intersection of a family of compact sets, so we just need to check the nonempty intersection property. Fixing finitely many $m$, we can find an $n$ above them all, and pick an arbitrary point in the preimage of $B_n$, and invoke Lemma 4 on $B_n$ to conclude that said point lies in all lower preimages, thus demonstrating finite intersection. Therefore, the intersection is nonempty.

Lemma 10: Given a sequence of nonempty closed sets $B_n$ where $p{r}_{\ast }^{{\pi }_{pa}^{n+1},{\pi }_{pa}^n}\left(B_{n+1}\right)\subseteq B_n$, and a sequence of points $M_n\in \left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}{)}^{-1}\right(B_n)$, all limit points of the sequence $M_n$ (if they exist) lie in ${\bigcap }_n\left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}{)}^{-1}\right(B_n)$ (works in the a-surmeasure case)

Proof: Assume a limit point exists, isolate a subsequence limiting to it. By Lemma 4, the preimages are nested in each other. Also, the preimage of a closed set is closed. Thus, for our subsequence, past $n$, the points are in the preimage of $B_n$ and don't ever leave, so the limit point is in the preimage of $B_n$. This argument works for all $n$, so the limit point is in the intersection of the preimages.

The next three Lemmas are typically used in close succession to establish nirvana-free upper-completeness for projecting down a bunch of nirvana-free upper complete sets, and taking the closed convex hull of them, which is an operation we use a lot. The first one says that projecting down a nirvana-free upper-complete set is upper-complete, the second one says that convex hull preserves the property, and the third one says that closure preserves the property. The first one requires building up a suitable measure via recursion on conditional probabilities, the second one requires building up a whole bunch of sa-measures via recursion on conditional probabilities and taking limits of them to get suitable stuff to mix together, and the third one also requires building up a whole bunch of sa-measures via recursion on conditional probabilities and then some fanciness with defining a limiting sequence.

Lemma 11: In the nirvana-free setting, a projection of an upper-complete set is upper-complete.

Proof sketch: To be precise about exactly what this says, since we're working with a-measures, it says "if you take the fragment of the upper completion composed of a-measures, and project it down, then the thing you get is: the fragment of the upper completion of (projected set) composed of a-measures". Basically, since we're not working in the full space of sa-measures, and just looking at the a-measure part of the upper completion, that's what makes this one tricky and not immediate.

The proof path is: Take an arbitrary point $M^{lo}$ in the projection of $B$ which has been crafted by projecting down $M^{hi}$. Given an arbitrary $M^{{}^{\prime }lo}:=M^{lo}+M^{\ast lo}$ (assuming it's an a-measure) which lies in the upper completion of the projection of $B$, we need to certify that it's in the projection of $B$ to show that $B$ is upper-complete. In order to do this, we craft a $M^{\ast hi}$ and $M^{{}^{\prime }hi}$ (an a-measure) s.t: $M^{hi}+M^{\ast hi}=M^{{}^{\prime }hi}$ (certifying that $M^{{}^{\prime }hi}$ is in $B$ since $B$ is upper complete), and $M^{{}^{\prime }hi}$ projects down to hit our $M^{{}^{\prime }lo}$ point of interest.

These a-measures are crafted by starting with the base case of $M^{\ast lo}$ and $M^{{}^{\prime }lo}$, and recursively building up the conditional probabilities in accordance with the conditional probabilities of $M^{hi}$. Then we just verify the basic conditions like the measures being well-formed, $M^{{}^{\prime }hi}$ being an a-measure, $M^{\ast hi}$ having a big enough $b$ term, and $M^{hi}+M^{\ast hi}=M^{{}^{\prime }hi}$, to get our result. Working in the Nirvana-free case is nice since we don't need to worry about assigning negative measure to Nirvana.

Proof: Let $B\subseteq M^a\left(F^{NF}\right({\pi }_{pa}^{hi}\left)\right)$ be our upper-complete set. We want to show that $p{r}_{\ast }^{{\pi }_{pa}^{hi},{\pi }_{pa}^{lo}}\left(B\right)$ is upper-complete. To that end, fix a $M^{lo}$ in the projection of $B$ that's the projection of a $M^{hi}\in B$. Let $M^{{}^{\prime }lo}:=M^{lo}+M^{\ast lo}$, where $M^{{}^{\prime }lo}$ is an a-measure. Can we find an a-measure $M^{{}^{\prime }hi}$ in $B$ that projects down to $M^{{}^{\prime }lo}$? Let's define $M^{\ast hi}$ and $M^{{}^{\prime }hi}$ as follows:

Let $M^{{}^{\prime }hi}=(m^{{}^{\prime }hi},b^{{}^{\prime }hi})$ where $b^{{}^{\prime }hi}$ is $b^{{}^{\prime }lo}$. Let $M^{\ast hi}=(m^{\ast hi},b^{\ast hi})$ where $b^{\ast hi}$ is $b^{\ast lo}$. Recursively define $m^{{}^{\prime }hi}$ and $m^{\ast hi}$ on $h$ that are prefixes of something in $F^{NF}\left({\pi }_{pa}^{hi}\right)$ as follows:

If $h$ is a prefix of something in $F\left({\pi }_{pa}^{lo}\right)$, $m^{{}^{\prime }hi}\left(h\right)=m^{{}^{\prime }lo}\left(h\right)$ and $m^{\ast hi}\left(h\right)=m^{\ast lo}\left(h\right)$.

Otherwise, recursively define the measure components $m^{{}^{\prime }hi}$ and $m^{\ast hi}$ as:

If $m^{hi}\left(h\right)>0$, then

$m^{{}^{\prime }hi}\left(hao\right)=\frac{m^{hi}\left(hao\right)}{m^{hi}\left(h\right)}{m}^{{}^{\prime }hi}\left(h\right),m^{\ast hi}\left(hao\right)=\frac{m^{hi}\left(hao\right)}{m^{hi}\left(h\right)}{m}^{\ast hi}\left(h\right)$

If $m^{hi}\left(h\right)=0$, then $m^{{}^{\prime }hi}\left(hao\right)=m^{\ast hi}\left(hao\right)=0$.

We need to verify that $m^{{}^{\prime }hi}$ has no negative parts so it's fitting for an a-measure, that $m^{hi}+m^{\ast hi}=m^{{}^{\prime }hi}$, that the $b$ value for $s{m}^{\ast hi}$ works, and that they're both well-formed signed measures. The first part is easy to establish, $m^{{}^{\prime }hi}\left(h\right)=m^{{}^{\prime }lo}\left(h\right)\ge 0$ in the base cases since $M^{{}^{\prime }lo}$ is an a-measure and a quick induction as well as $m^{hi}$ coming from the a-measure $M^{hi}$ (so no negatives anywhere) establish $m^{{}^{\prime }hi}$ as not having any negative parts.

To verify that they sum up to $m^{{}^{\prime }hi}$, observe that for base-case histories in $F^{NF}\left({\pi }_{pa}^{lo}\right)$, $m^{hi}\left(h\right)+m^{\ast hi}\left(h\right)=m^{lo}\left(h\right)+m^{\ast lo}\left(h\right)=m^{{}^{\prime }lo}\left(h\right)=m^{{}^{\prime }hi}\left(h\right)$. Then, in the general case, we can use induction (assume it's true for $h$) and go:

If $m^{hi}\left(h\right)>0$, then

$m^{hi}\left(hao\right)+m^{\ast hi}\left(hao\right)=m^{hi}\left(hao\right)+\frac{m^{hi}\left(hao\right)}{m^{hi}\left(h\right)}{m}^{\ast hi}\left(h\right)=\frac{m^{hi}\left(hao\right)}{m^{hi}\left(h\right)}\left(m^{hi}\right(h)+m^{\ast hi}(h\left)\right)$

$=\frac{m^{hi}\left(hao\right)}{m^{hi}\left(h\right)}{m}^{{}^{\prime }hi}\left(h\right)=m^{{}^{\prime }hi}\left(h\right)$

If $m^{hi}\left(h\right)=0$, then $m^{hi}\left(hao\right)=0$, so

$m^{hi}\left(hao\right)+m^{\ast hi}\left(hao\right)=0+0=0=m^{{}^{\prime }hi}\left(hao\right)$

What about checking that they're well-formed measures? To do this, it suffices to check that summing up their measure-mass over $ha{o}_i$ gets the measure-mass over $h$. If $m^{hi}\left(h\right)>0$, then:

${\sum }_i{m}^{{}^{\prime }hi}\left(ha{o}_i\right)={\sum }_i\frac{m^{hi}\left(ha{o}_i\right)}{m^{hi}\left(h\right)}{m}^{{}^{\prime }hi}\left(h\right)=\frac{m^{hi}\left(h\right)}{m^{hi}\left(h\right)}{m}^{{}^{\prime }hi}\left(h\right)=m^{{}^{\prime }hi}\left(h\right)$

And similar for $m^{\ast }$.

If $m^{hi}\left(h\right)=0$, then, when we trace back to some longest prefix $h^{\prime }$ where $m^{hi}\left(h^{\prime }\right)>0$, then $m^{hi}\left(h^{\prime }ao\right)=0$, so:

$m^{{}^{\prime }hi}\left(hao\right)=\frac{m^{hi}\left(hao\right)}{m^{hi}\left(h\right)}{m}^{{}^{\prime }hi}\left(h\right)=\frac{0}{m^{hi}\left(h^{\prime }\right)}{m}^{{}^{\prime }hi}\left(h^{\prime }\right)=0$

And the same for $m^{\ast hi}\left(hao\right)$. This extends forward up to $h$, so $m^{hi}\left(h\right)=0$ implies $m^{{}^{\prime }hi}\left(h\right)=m^{\ast hi}\left(h\right)=0$. And we get:

${\sum }_i{m}^{{}^{\prime }hi}\left(ha{o}_i\right)=0=m^{{}^{\prime }hi}\left(h\right)$

and the same for $m^{\ast hi}\left(h\right)$.

For the $b$ value being sufficient, observe that the way we did the extension, the negative-measure for $m^{\ast hi}$ is the same as the negative measure for $m^{\ast lo}$, and $b^{\ast hi}=b^{\ast lo}$, and the latter is sufficient to cancel out the negative measure for $m^{\ast lo}$, so we're good there. And for projecting down appropriately, observe that $m^{\ast hi}$ and $m^{{}^{\prime }hi}$ copy $m^{\ast lo}$ and $m^{{}^{\prime }lo}$ wherever they get a chance to do so.

Thus, $M^{{}^{\prime }hi}=M^{hi}+M^{\ast hi}$ so $M^{{}^{\prime }hi}$ lies in the upper completion of $B$, so it's in $B$, and projects down onto $M^{{}^{\prime }lo}$, certifying that $M^{{}^{\prime }lo}$ lies in the projection of $B$, so the projection of an upper-complete set of a-measures is upper-complete.

Lemma 12: In the nirvana-free setting, the convex hull of an upper-closed set is upper-closed.

Proof sketch: Again, this is tricky since we're working with a-measures. We have a point $M$ in the convex hull, which shatters into $E_{\zeta }{M}_i$ where the $M_i$ are in the (non-convex) set $B$ itself. If $M+M^{\ast }$ is an a-measure, we want to find $M_i^{\ast }$ s.t. $M_i+M_i^{\ast }$ is an a-measure, and mixing these makes $M+M^{\ast }$. However, it's really hard to define these $M_i^{\ast }$ directly, so we craft approximations indexed by n where $M_i+M_{i,n}^{\ast }$ is an a-measure, and mixing the $m_{i,n}^{\ast }$ matches $m^{\ast }$ perfectly up till time n. We get weak bounds on the amount of positive measure and the $b$ term to invoke the compactness lemma, and then use Tychonoff to get a suitable convergent subsequence for all the i to define our final $M_i^{\ast }$ that, when combined with $M_i$, makes an a-measure. Mixing these together replicates the measure component of $M^{\ast }$, but not the $b$ term. However, that's easily fixable by adding a bit of excess to one of the $b$ terms, and we're done. We took an arbitrary $M+M^{\ast }$ where $M\in c.h\left(B\right)$, and crafted $M_i^{\ast }$ where, for all i, $M_i+M_i^{\ast }$ is an a-measure (and in $B$ by its upper-completeness) and it mixes together to make $M+M^{\ast }$, certifying that the convex hull is upper-closed.

Our way of constructing the $m_{i,n}^{\ast }$ is basically: start at length n, use $\frac{m_i\left(h\right)}{m\left(h\right)}$ as your scale factor for filling in the measure of histories, extend down, and then extend up with the conditional probabilities of $M_i$. 

Proof: Take a point $M\in c.h\left(B\right)$. It decomposes into $E_{\zeta }{M}_i$ for finitely many i, where $M_i\in B$. Fix some arbitrary $M+M^{\ast }$ (as long as it's an a-measure). We'll craft $M_i^{\ast }$ where $M_i+M_i^{\ast }\in B$ by upper completeness of $B$,and the $M_i^{\ast }$ mix together to make $M^{\ast }$ itself, certifying that $M+M^{\ast }$ lies in $c.h\left(B\right)$.

Let $m_{i,n}^{\ast }$ be defined by: If $h$ is of length n, or lies in $F^{NF}\left({\pi }_{pa}\right)$ and is shorter than length n,

$m_{i,n}^{\ast }\left(h\right)=\frac{m_i\left(h\right)}{m\left(h\right)}{m}^{\ast }\left(h\right)$

($m_{i,n}^{\ast }\left(h\right)$ defaults to $m^{\ast }\left(h\right)$ if $m\left(h\right)=0$)

And then it's defined for shorter $h$ via:

$m_{i,n}^{\ast }\left(h\right)={\sum }_j{m}_{i,n}^{\ast }\left(ha{o}_j\right)$

The $b$ value is (we're summing over the base-case histories where $h$ is of length n or lies in $F^{NF}\left({\pi }_{pa}\right)$ and is shorter than length n) $-{\sum }_{h}min(0,m_{i,n}^{\ast }(h\left)\right)$

And if $m_i\left(h\right)>0$, extend to bigger histories via 

$m_{i,n}^{\ast }\left(hao\right)=\frac{m_i\left(hao\right)}{m_i\left(h\right)}{m}_{i,n}^{\ast }\left(h\right)$

And if $m_i\left(h\right)=0$, it's $m_{i,n}^{\ast }\left(hao\right)=\frac{m_{i,n}^{\ast }\left(h\right)}{\#o}$

We've got a few things to show. first is showing that $m_{i,n}^{\ast }\left(h\right)$ is a well-defined signed measure. ${\sum }_j{m}_{i,n}^{\ast }\left(ha{o}_j\right)=m_{i,n}^{\ast }\left(h\right)$ trivially if $h$ is shorter than length n. 

Otherwise, (assuming $m_i\left(h\right)>0$)

${\sum }_j{m}_{i,n}^{\ast }\left(ha{o}_j\right)={\sum }_j\frac{m_i\left(ha{o}_j\right)}{m_i\left(h\right)}{m}_{i,n}^{\ast }\left(h\right)=\frac{m_i\left(h\right)}{m_i\left(h\right)}{m}_{i,n}^{\ast }\left(h\right)=m_{i,n}^{\ast }\left(h\right)$

If $m_i\left(h\right)=0$, then ${\sum }_j{m}_{i,n}^{\ast }\left(ha{o}_j\right)={\sum }_j\frac{m_{i,n}^{\ast }\left(h\right)}{\#o}=m_{i,n}^{\ast }\left(h\right)$

Ok, so it's well-defined. Also, past n, it doesn't add any more negative measure. If it's negative on a length n history, it'll stay that negative forevermore and never go positive, so the $b$ value we stuck on it is a critical $b$ value (exactly sufficient to cancel out the areas of negative measure)

We do need to show that $m_{i,n}^{\ast }+m_i$ is an a-measure. For the $h$ of length n or in $F^{NF}\left({\pi }_{pa}\right)$ and shorter, we can split into two cases. For the case where $m\left(h\right)>0$,

$m_{i,n}^{\ast }\left(h\right)m_i\left(h\right)=\frac{m_i\left(h\right)}{m\left(h\right)}{m}^{\ast }\left(h\right)+m_i\left(h\right)=m_i\left(h\right)(\frac{m^{\ast }\left(h\right)}{m\left(h\right)}+1)$

And because $m^{\ast }\left(h\right)+m\left(h\right)\ge 0$ (they sum to make an a-measure), $m^{\ast }\left(h\right)\ge -m\left(h\right)$, so $\frac{m^{\ast }\left(h\right)}{m\left(h\right)}\ge -1$, so we get a nonnegative number times a nonnegative number, so $m_{i,n}^{\ast }\left(h\right)+m_i\left(h\right)\ge 0$.

Now for the case where $m\left(h\right)=0$. In that case $m_i\left(h\right)=0$ because $m$ came from an a-measure and is the mix of the $m_i$. Also, because $m\left(h\right)+m^{\ast }\left(h\right)\ge 0$ due to $M+M^{\ast }$ being an a-measure, $m^{\ast }\left(h\right)\ge 0$. Then, $m_{i,n}^{\ast }\left(h\right)+m_i\left(h\right)=m^{\ast }\left(h\right)\ge 0$

Now for the short histories. By induction down,

$m_{i,n}^{\ast }\left(h\right)+m_i\left(h\right)={\sum }_j{m}_{i,n}^{\ast }\left(ha{o}_j\right)+{\sum }_j{m}_i\left(ha{o}_j\right)={\sum }_j\left(m_{n,i}^{\ast }\right(ha{o}_j)+m_i(ha{o}_j\left)\right)\ge 0$

Now for the long histories. If $m_i\left(h\right)>0$,

$m_{i,n}^{\ast }\left(hao\right)+m_i\left(hao\right)=m_i\left(hao\right)+\frac{m_i\left(hao\right)}{m_i\left(h\right)}{m}_{i,n}^{\ast }\left(h\right)=m_i\left(hao\right)(1+\frac{m_{i,n}^{\ast }\left(h\right)}{m_i\left(h\right)})$

And then, by induction up we can assume $m_{i,n}^{\ast }\left(h\right)+m_i\left(h\right)\ge 0$, so $m_{i,n}^{\ast }\left(h\right)\ge -m_i\left(h\right)$, so $\frac{m_{i,n}^{\ast }\left(h\right)}{m_i\left(h\right)}\ge -1$, so it's a multiplication of a nonnegative number and a nonnegative number, so we're good there on showing nonnegativity.

If $m_i\left(h\right)=0$, then $m_i\left(hao\right)=0$. Since $m_{i,n}^{\ast }\left(h\right)+m_i\left(h\right)\ge 0$, then $m_{i,n}^{\ast }\left(h^{\prime }\right)\ge 0$. Then, $m_{i,n}^{\ast }\left(hao\right)+m_i\left(hao\right)=\frac{m_{i,n}^{\ast }\left(h\right)}{\#o}\ge 0$

Ok, so, for all n, $M_i+M_{i,n}$ is an a-measure.

One last thing we'll want to show is that, for histories $h$ of length n or shorter, $\left(E_{\zeta }{m}_{i,n}^{\ast }\right)\left(h\right)=m^{\ast }\left(h\right)$

First, for the histories of length n or in $F^{NF}\left({\pi }_{pa}\right)$ (assuming $m\left(h\right)>0$)

$\left(E_{\zeta }{m}_{i,n}^{\ast }\right)\left(h\right)=E_{\zeta }\left(m_{i,n}^{\ast }\right(h\left)\right)=E_{\zeta }\left(\frac{m_i\left(h\right)}{m\left(h\right)}{m}^{\ast }\right(h\left)\right)=\frac{m^{\ast }\left(h\right)}{m\left(h\right)}{E}_{\zeta }\left(m_i\right(h\left)\right)=\frac{m^{\ast }\left(h\right)}{m\left(h\right)}\left(E_{\zeta }{m}_i\right)\left(h\right)$

$=\frac{m^{\ast }\left(h\right)}{m\left(h\right)}m\left(h\right)=m^{\ast }\left(h\right)$

Assuming $m\left(h\right)=0$, then $m_{i,n}^{\ast }\left(h\right)=m^{\ast }\left(h\right)$ immediately giving you your result. So, since the mixture of the $m_{i,n}^{\ast }$ mimics $m^{\ast }$ on everything of length n or shorter in $F^{NF}\left({\pi }_{pa}\right)$, the "sum up the stuff ahead of you" thing makes it mimic $m^{\ast }$ on all histories of length n or shorter.

Further, $m^{\ast }$ is nonpositive on a history of length n or a shorter history in $F^{NF}\left({\pi }_{pa}\right)$ iff for all i, $m_{i,n}^{\ast }$ is nonpositive on it. So, since the $b$ values for $m_{i,n}^{\ast }$ are the negative component, $E_{\zeta }{b}_{i,n}^{\ast }$ is the negative-measure of $m^{\ast }$ up till time n, which is less negative than the negative-measure of $m^{\ast }$, so the mixture of the $b_{i,n}^{\ast }$ terms undershoots $b^{\ast }$.

Consider the sequence $M_{i,n}^{\ast }$ (the sequence is in n, i is fixed). It's a sequence of sa-measures. To show that there's a limit point, we need a bound on the positive value part, and the negative value part (our $b$ is critical, it can't go any smaller, so bounding the negative value part bounds the $b$) Fixing an n, the "boundary" of stuff of length n or shorter and in $F^{NF}\left({\pi }_{pa}\right)$ suffices to establish what the mass of the negative part and positive part are. We either mimic $m^{\ast }$ if $m\left(h\right)=0$, or $m_i\left(h\right)=0$ while $m\left(h\right)>0$ so $m_{i,n}\left(h\right)=0$, or both quantities are positive so we have a scale term of  $\frac{m_i\left(h\right)}{m\left(h\right)}=\frac{m_i\left(h\right)}{E_{\zeta }{m}_i\left(h\right)}\le \frac{m_i\left(h\right)}{{\zeta }_i{m}_i\left(h\right)}=\frac{1}{{\zeta }_i}$

So, our amount of positive and negative measure on $m_{i,n}^{\ast }$ on the "n boundary" is at most $\frac{1}{{\zeta }_i}$ times the positive and negative measure on $m^{\ast }$ at the "n boundary", which is less than or equal to the amount of positive and negative measure that $m^{\ast }$ has overall. So, that gets us our bounds on the positive and negative part of $m_{i,n}^{\ast }$ of $\frac{m^{\ast +}\left(1\right)}{{\zeta }_i}$ and $\frac{m^{\ast -}\left(1\right)}{{\zeta }_i}$, respectively (which bounds our $b_{i,n}^{\ast }$ terms) 

Now, we can consider our sequence $(m_{i,n}^{\ast },b_{i,n}^{\ast })$ as a sequence ${\overline{M}}_n$ in

${\prod }_i\left(M^{sa}\right(F^{NF}\left({\pi }_{pa}\right))\cap \{(m,b)|m^{+}\left(1\right)\le \frac{m^{\ast +}\left(1\right)}{{\zeta }_i},b\le -\frac{m^{\ast -}\left(1\right)}{{\zeta }_i}\left\}\right)$

where ${\overline{M}}_n\left(i\right)=(m_{i,n}^{\ast },b_{i,n}^{\ast })$

By the Compactness Lemma, these sets are compact, and by Tychonoff, the product is compact. So, there's a convergent subsequence, and the limit point projects down to the coordinates to make a $M_i^{\ast }$ for each i.The set of sa-measures that, when added to an a-measure, make another a-measure, is closed, and regardless of n, $M_i+M_{i,n}^{\ast }$ is an a-measure, so $M_i+M_i^{\ast }$ is an a-measure.

$E_{\zeta }{m}_{i,n}^{\ast }$ mimics $m^{\ast }$ up till timestep n, so $E_{\zeta }{m}_i^{\ast }=m^{\ast }$ And because, at each step, the mixture of the $b$ values undershoots $b^{\ast }$, $E_{\zeta }{b}_i^{\ast }\le b^{\ast }$.

So, our final batch of sa-measures is $M_i^{\ast }$ for $i>0$, and for $i=0$, it's  $M_0^{\ast }+(0,\frac{b^{\ast }-E_{\zeta }{b}_i^{\ast }}{{\zeta }_0})$ Now, all these $M_i^{\ast }$ are sa-measures that, when added to $M_i$, make a-measures, and one of them has some extra b term on it, which doesn't impede it from being an a-measure. By upper-completeness of $B$, they're all in $B$, and mixing them makes $M+M^{\ast }$ exactly, because

${\zeta }_0(M_0+M_0^{\ast }+(0,\frac{b^{\ast }-E_{\zeta }{b}_i^{\ast }}{{\zeta }_0}))+{\sum }_{i>0}{\zeta }_i(M_i+M_i^{\ast })=E_{\zeta }\left(M_i\right)+E_{\zeta }\left(M_i^{\ast }\right)+(0,b^{\ast }-E_{\zeta }{b}_i^{\ast })$

$=M+E_{\zeta }(m_i^{\ast },b_i^{\ast })+(0,b^{\ast }-E_{\zeta }{b}_i^{\ast })=M+(E_{\zeta }{m}_i^{\ast },E_{\zeta }{b}_i^{\ast })+(0,b^{\ast }-E_{\zeta }{b}_i^{\ast })$

$=M+(E_{\zeta }{m}_i^{\ast },b^{\ast })=M+(M^{\ast },b^{\ast })=M+M^{\ast }$

$M+M^{\ast }$ was an arbitrary a-measure above a $M\in c.h\left(B\right)$, and we showed it's a mix of a-measures in $B$ since $B$ is upper complete so $c.h\left(B\right)$ is upper-complete.

Lemma 13: In the nirvana-free setting, the closure of an upper-closed set of a-measures is upper-closed.

Proof sketch: We have an $M\in \overline{B}$, and a sequence $M_n\in B$ limiting to $M$. Let $M^{\prime }:=M+M^{\ast }$ be an arbitrary a-measure above $M$. We must craft a sequence limiting to $M^{\prime }$. What we do, is make a bunch of $M_{n,j}^{\ast }$ with the special property that $m_n+m_{n,j}^{\ast }$ perfectly mimics $m^{\prime }$ up till time j, by basically going "copy $m^{\prime }-m_n$ for time j or before, and complete with the conditional probabilities of $m_n$ so $m_n+m_{n,j}^{\ast }$ doesn't go negative". And then the $b$ term is set to mimic the $b$ term of $M^{\ast }$, or set to cancel out the amount of negative measure, whichever is greater. The reason we only copy up till time j instead of skipping to the chase and just going "copy $m^{\prime }-m_n$, stick on whichever $b$ term you need" is it affords us finer control and understanding over what our $b$ terms are doing.

Then, we let j increase as $\rho \left(n\right)$ to get a sequence of one variable, $M_n+M_{n,\rho \left(n\right)}^{\ast }$ where $\rho \left(n\right)$ is selected to diverge to infinity at a suitable rate to get convergence to $M^{\prime }$ itself. Again, no matter what $\rho \left(n\right)$ is, as long as it diverges to infinity as n does, we get convergence of the measure term to the measure term $m^{\prime }$, the hard part is selecting $\rho$ to appropriately control what the $b$ term is doing. Once $\rho \left(n\right)$ is suitably defined, then we can get upper and lower bounds on how the $b$ term of the sum compares to the $b$ term of $M^{\prime }$, and show convergence.

Proof: Ok, so $B$ is upper-closed, and we want to show upper-closure of $\overline{B}$. Thus, we have an $M\in \overline{B}$, a sequence of points $M_n\in B$ that limit to $M$, and if $M^{\prime }=M+M^{\ast }$ is an a-measure, we want to show that $M^{\prime }$ is in $\overline{B}$. This is going to require a rather intricate setup to get our limit of interest. In this case, we'll be using both n and j as limit parameters.

Let $m_{n,j}^{\ast }$ be defined up till time j by: If $h$ is of length j or shorter, $m_{n,j}^{\ast }\left(h\right)=m^{\prime }\left(h\right)-m_n\left(h\right)$

Extend to longer histories via (if $m_n\left(h\right)>0$)

$m_{n,j}^{\ast }\left(hao\right)=\frac{m_n\left(hao\right)}{m_n\left(h\right)}{m}_{n,j}^{\ast }\left(h\right)$

And if $m_n\left(h\right)=0$, go with $m_{n,j}^{\ast }\left(hao\right)=\frac{m_{n,j}^{\ast }\left(h\right)}{\#o}$

The $b$ value is defined as (we're summing over histories of length j or in $F^{NF}\left({\pi }_{pa}\right)$ and shorter) $max(b^{\ast },-{\sum }_{h}min(0,m_{n,j}^{\ast }\left(h\right)\left)\right)$

We've got a few things to show. first is showing that $m_{n,j}^{\ast }\left(h\right)$ is a well-defined signed measure. If $h$ is length j or shorter,

${\sum }_i{m}_{n,j}^{\ast }\left(ha{o}_i\right)={\sum }_i\left(m^{\prime }\right(ha{o}_i)-m_n(ha{o}_i\left)\right)=m^{\prime }\left(h\right)-m_n\left(h\right)=m_{n,j}^{\ast }\left(h\right)$

Otherwise, (assuming $m_n\left(h\right)>0$)

${\sum }_i{m}_{n,j}^{\ast }\left(ha{o}_i\right)={\sum }_i\frac{m_n\left(ha{o}_i\right)}{m_n\left(h\right)}{m}_{n,j}^{\ast }\left(h\right)=\frac{m_n\left(h\right)}{m_n\left(h\right)}{m}_{n,j}^{\ast }\left(h\right)=m_{n,j}^{\ast }\left(h\right)$

Assuming $m_n\left(h\right)=0$, ${\sum }_i{m}_{n,j}^{\ast }\left(ha{o}_i\right)={\sum }_i\frac{m_{n,j}^{\ast }\left(h\right)}{\#o}=m_{n,j}^{\ast }\left(h\right)$

Ok, so it's well-defined. Also, past j, it doesn't add any more negative measure. If it's negative on a length j history, it'll stay that negative forevermore and never go positive, so the $b$ value we stuck on it is either a critical $b$ value, or greater than that. In particular, this implies that our definition of $b_{n,j}^{\ast }$ can be reexpressed as: $b_{n,j}^{\ast }=max(b^{\ast },-m_{n,j}^{\ast -}(1\left)\right)$

We do need to show that $m_{n,j}^{\ast }+m_n$ is an a-measure. For the $h$ of length j or in $F^{NF}\left({\pi }_{pa}\right)$ and shorter, we can go: $m_{n,j}^{\ast }\left(h\right)+m_n\left(h\right)=m^{\prime }\left(h\right)-m_n\left(h\right)+m_n\left(h\right)=m^{\prime }\left(h\right)\ge 0$ This is because $M^{\prime }$ is an a-measure. This also means that $m_n+m_{n,j}^{\ast }$ perfectly mimics $m^{\prime }$ up till time j.

Now for the long histories. Assume $m_n\left(h\right)>0$

$m_{n,j}^{\ast }\left(hao\right)+m_n\left(hao\right)=m_n\left(hao\right)+\frac{m_n\left(hao\right)}{m_n\left(h\right)}{m}_{n,j}^{\ast }\left(h\right)=m_n\left(hao\right)(1+\frac{m_{n,j}^{\ast }\left(h\right)}{m_n\left(h\right)})$

And then, by induction up we can assume $m_{n,j}^{\ast }\left(h\right)+m_n\left(h\right)\ge 0$, so $m_{n,j}^{\ast }\left(h\right)\ge -m_n\left(h\right)$, so $\frac{m_{n,j}^{\ast }\left(h\right)}{m_n\left(h\right)}\ge -1$, so it's a multiplication of a nonnegative number and a nonnegative number, so we're good there. 

Assume $m_n\left(h\right)=0$. Then $m_n\left(hao\right)=0$ and $m_{n,j}^{\ast }\left(hao\right)+m_n\left(hao\right)=\frac{m_{n,j}^{\ast }\left(h\right)}{\#o}$

And then, since $m_{n,j}^{\ast }\left(h\right)+m_n\left(h\right)\ge 0$ (induction up), and $m_n\left(h\right)=0$, $m_{n,j}^{\ast }\left(h\right)\ge 0$, and we get our result, showing that $M_n+M_{n,j}^{\ast }$ is an a-measure, and by upwards closure of $B$, all the $M_n+M_{n,j}^{\ast }$ lie in $B$. 

There's one more fiddly thing to take care of. What we'll be doing is letting j increase as $\rho \left(n\right)$, to get a function of 1 variable, and showing that $M_n+M_{n,\rho \left(n\right)}^{\ast }$ limits to $M^{\prime }$. So we should think carefully about what we want out of $\rho$.

First, let $m^{\ast j-}$ be the measure gotten by restricting $m^{\ast }$ to only histories which are in $F^{NF}\left({\pi }_{pa}\right)$ with a length of <j with negative measure, and histories where their length j prefix has negative measure. This is kinda like a bounded way of slicing out areas with negative measure from $m^{\ast }$, falling short of the optimal decomposition $m^{\ast -}$

Also, $\left(m_{n,j}^{\ast }{)}^{-}\right(1)$, as n increases and j remains fixed, limits to $m^{\ast j-}\left(1\right)$. The reason for this is that for histories of length j or shorter,

 $m_{n,j}^{\ast }\left(h\right)-m^{\ast }\left(h\right)=\left(m^{\prime }\right(h)-m_n(h\left)\right)-\left(m^{\prime }\right(h)-m(h\left)\right)=m\left(h\right)-m_n\left(h\right)$ 

and the end term limits to 0 because $m_n$ limits to $m$. So, past a sufficently large n, $m_{n,j}^{\ast }$ comes extremely close to mimicking $m^{\ast }$ for the first j steps. So, dialing up n far enough, the negative-measure of $m_{n,j}^{\ast }$ comes really close to the negative measure mass in $m^{\ast }$ as evaluated up till time j, due to the aforementioned mimicry.

Further, $m^{\ast j-}\left(1\right)\ge m^{\ast -}\left(1\right)$, because only evaluating up till length j isn't as good at slicing out areas of negative measure as the optimal decomposition of $m^{\ast }$ into positive and negative components.

With all this, our rule for $\rho \left(n\right)$ will be: 

$\rho \left(n\right):=sup\{j\le n|\forall n^{\prime }\ge n:|m_{n^{\prime },j}^{\ast -}(1)-m^{\ast j-}(1)|\le 2^{-j}\}$

$\rho \left(n\right)$ never decreases. What this is basically doing is going "ok, I'll step up j but only when there's a guarantee that I'll mimic $m^{\ast }$ up till timestep j (re: amount of negative measure) sufficiently closely forever afterward" $\rho \left(n\right)$ eventually diverges to infinity, though it might do so very slowly, because for all the j, $m_{n,j}^{\ast -}\left(1\right)$ limits to $m^{\ast j-}\left(1\right)$ so eventually we get to a large enough n that the defining condition is fulfilled and we can step up j.

Now we can finally define our sequence as: $M_{n,\rho \left(n\right)}^{\ast }+M_n$. We'll show that this limits to $M^{\prime }$. First, it's always an a-measure, and always in $B$ because it's in the upper completion of $B$ which is upper-complete. For a fixed n, $m_{n,\rho \left(n\right)}^{\ast }+m_n$ always flawlessly matches $m^{\prime }$ up till time $\rho \left(n\right)$. Since $\rho \left(n\right)$ diverges to infinity, eventually we get a flawless match up till any finite time we name, so the measure components do converge to $m^{\prime }$ as n limits to infinity.

But what about the $b$ component? Well, the $b$ component of the sum is: $max(b^{\ast },-m_{n,\rho \left(n\right)}^{\ast -}(1\left)\right)+b_n$. Let's bound it. Obviously, a lower bound is $b^{\ast }+b_n$.
An upper bound is a bit more interesting.

$max(b^{\ast },-m_{n,\rho \left(n\right)}^{\ast -}(1\left)\right)+b_n\le max(b^{\ast }+2^{-\rho \left(n\right)},-m_{n,\rho \left(n\right)}^{\ast -}(1\left)\right)+b_n$

By the way we defined $\rho \left(n\right)$, we can go to $-m^{\ast \rho \left(n\right)-}\left(1\right)$ with a small constant overhead, and then swap out $-m^{\ast \rho \left(n\right)-}\left(1\right)$ (amount of negative measure up till time $\rho \left(n\right)$) for $-m^{\ast -}\left(1\right)$ (total amount of negative measure) which is greater.

$max(b^{\ast }+2^{-\rho \left(n\right)},-m_{n,\rho \left(n\right)}^{\ast -}(1\left)\right)+b_n\le max(b^{\ast }+2^{-\rho \left(n\right)},-m^{\ast \rho \left(n\right)-}(1)+2^{-\rho \left(n\right)})+b_n$

$\le max(b^{\ast }+2^{-f\left(n\right)},-m^{\ast -}(1)+2^{-\rho \left(n\right)})+b_n\le max(b^{\ast }+2^{-\rho \left(n\right)},b^{\ast }+2^{-\rho \left(n\right)})+b_n$

$=b^{\ast }+2^{-\rho \left(n\right)}+b_n$

(because $b^{\ast }$ must be equal to or exceed the amount of negative measure in $m^{\ast }$ for $M^{\ast }$ to be a legit sa-measure)

So, our bounds on the $b$ term for $M_{n,\rho \left(n\right)}^{\ast }+M_n$ are $b^{\ast }+b_n$ on the low end, and $b^{\ast }+2^{-\rho \left(n\right)}+b_n$ on the high end. As n limits to infinity, so does $\rho \left(n\right)$, so that term vanishes, and $b_n$ limits to $b$, so our limiting $b$ value is $b^{\ast }+b=b^{\prime }$, and we're done. We built a sequence of a-measures in $B$ limiting to $M^{\prime }$, certifying that it's in $\overline{B}$, and $M^{\prime }$ was arbitrary above some $M\in \overline{B}$. Thus, the closure of an upper-complete set is upper-complete.

 

The next one is a story proof, because I couldn't figure out how to make it formal. It essentially says that given two points near each other, their nirvana-free upper-completions (the set of a-measures, if it was a set of sa-measures, it'd be immediate to show) are close to each other.

Lemma 14: For stubs, in the nirvana-free setting, if $M$ and $M^{\prime }$ are $ϵ$ apart, then the Hausdorff-distance between $\{M{\}}^{uc}\cap M^a(F^{NF}\left({\pi }_{st}\right))$ and $\{M^{\prime }{\}}^{uc}\cap M^a(F^{NF}\left({\pi }_{st}\right))$ is $ϵ$ or less.

Ok, I don't really know how to make this formal, so all I have is a story-proof. The KR-metric (what's the maximum difference between two measures w.r.t 1-Lipschitz bounded functions) is the same as (or at least within a constant of) the earthmover distance. The earthmover distance is "interpret your measure as piles (or pits) of dirt on various spots. It takes $ϵ$ effort to move 1 unit of dirt $ϵ$ distance. Also, $ϵ$ effort lets you create or destroy $ϵ$ units of dirt. What's the minimum amount of effort it takes to rearrange one pile of dirt into the other pile of dirt?". So our proof will be a story about moving dirt.

Let's just examine the measure components of $M$ and $M^{\prime }$. Since the earthmover distance is $ϵ$ (it might be less because of different $b$), it takes $ϵ$ effort to rearrange the dirt pile of $m$ into the dirt pile of $m^{\prime }$ in an optimal way. Let's say $M+M^{\ast }$ is an a-measure (no negative parts ie no dirt pits). We need some $M^{{}^{\prime }\ast }$ to add to $M^{\prime }$ to make an a-measure within $ϵ$ of $M+M^{\ast }$.

The procedure to construct $M^{{}^{\prime }\ast }$ is as follows: $b^{{}^{\prime }\ast }=b^{\ast }$. For the measure component, start with the $m^{\ast }$ pile (there may be dirt pits ie areas of negative measure). Now, keep a close tab on the process of rearranging $m$ into $m^{\prime }$. One crumb of dirt at a time is moved, or dirt is created/destroyed. The rule is:

Let's say a crumb of dirt is moved from $h$ to $h^{\prime }$, created at $h$ or destroyed at $h$. If the pile-being-rearranged into $m^{\prime }$ has its measure on $h$ being greater than the size of the pit (negative measure) for $h$ for the pile-being-rearranged into $m^{{\ast }^{\prime }}$, sit around and do nothing. If moving that crumb/destroying it would make $h$ have negative measure (the dirt pile on $h$ for the pile-being-turned-into $m^{\prime }$ would become smaller than the size of the hole for $h$ for the pile-being-turned-into $m^{{}^{\prime }\ast }$), then take the latter pile and move a crumb from $h^{\prime }$ into the pit for $h$ (at the same expenditure of effort), or create a crumb of dirt there instead. Once you're done, that's your $m^{{}^{\prime }\ast }$. Keep the $b$ value the same.

Now, this process does several things. First, very little effort was expended ($ϵ$ or less), to reshuffle $m^{\ast }$ into $m^{{}^{\prime }\ast }$ because you're either sitting around, or mimicking the same low-effort dirt moving process in reverse. Second, $b^{\ast }$ stays as a viable bound throughout, because whenever you move a crumb, you're dropping it into a pit, so an increase in negative measure at one spot is balanced out by a decrease in negative measure for the spot you moved the crumb to. Also, you never destroy crumbs, only create them. Also, in the whole process by which we rearrange $m+m^{\ast }$ into $m^{\prime }+m^{{}^{\prime }\ast }$, we always preserve the invariant that (pile on $h$ + pit on $h$ $\ge 0$), so $m^{\prime }+m^{{}^{\prime }\ast }$ is a measure, not a signed measure.

For the final bit, we can imagine reshuffling $m+m^{\ast }$ into $m^{\prime }+m^{{}^{\prime }\ast }$ as a whole. Then, either a crumb is moved from point A to point B, or you move a crumb from point A to point B, and a crumb back from point B to point A so you can skip that step. Or, a crumb is created at point A, or a crumb is both destroyed and created at A, so you can skip that step. So, the dirt-moving procedure to turn $m+m^{\ast }$ into $m^{\prime }+m^{{}^{\prime }\ast }$ spends as much or less effort than the procedure to turn $m$ into $m^{\prime }$, which takes $ϵ$ effort.

Putting it all together, we took an arbitrary point in the upper-completion of $M$, and it only takes $ϵ$ or less effort to shift the $b$ a little bit and reshuffle the measures to get a point in the upper-completion of $M^{\prime }$.

The argument works in reverse, just switch the labels, to establish that the two upper-completions are $ϵ$ apart or less.

 

For the next one, we have two ways of expressing uniform Hausdorff-continuity for a belief function. As a recap, $M^a\left(\infty \right)$ is the set of a-measures over all outcomes (regardless of whether or not they could have come from a single policy or not), and all belief functions have a critical ${\lambda }^{\odot }+b^{\odot }$ parameter that controls the $\lambda$ and $b$ values of the set of minimal points regardless of ${\pi }_{pa}$. $\{\le \odot \}$ is the set $\left\{\right(\lambda \mu ,b)|\lambda +b\le {\lambda }^{\odot }+b^{\odot }\}$. They are:

1: For all nonzero $ϵ$, there exists a nonzero $\delta$ where $d({\pi }_{pa},{\pi }_{pa}^{\prime })<\delta$ implies $\left(p{r}_{\ast }^{\infty ,{\pi }_{pa}}{)}^{-1}\right(\Theta \left({\pi }_{pa}\right)\cap NF\cap \{\le \odot \})$ has a Hausdorff-distance of $ϵ$ from the corresponding set for ${\pi }_{pa}^{\prime }$.

2: For all nonzero $ϵ$, there exists a nonzero $\delta$ where $d({\pi }_{pa},{\pi }_{pa}^{\prime })<\delta$ implies: If $(\lambda \mu ,b)\in \left(p{r}_{\ast }^{\infty ,{\pi }_{pa}}{)}^{-1}\right(\Theta \left({\pi }_{pa}\right)\cap NF)$, then $(\lambda \mu ,b)$ has a distance of $ϵ(\lambda +1)$ or less from the set $\left(p{r}_{\ast }^{\infty ,{\pi }_{pa}^{\prime }}{)}^{-1}\right(\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF)$ (and symmetrically for the other set)

Lemma 15: The two ways of expressing the Hausdorff-continuity requirement are equivalent for a belief function $\Theta$ or ${\Theta }^{\omega }$ obeying nirvana-free nonemptiness, closure, nirvana-free upper-completion, and bounded-minimals.

Proof sketch: We start with the second $\lambda$-dependent distance condition and derive the first. Roughly, that $\{\le \odot \}$ restriction means the tail where the $\lambda$ values are high gets clipped so the two sets are within a constant of $ϵ$ away from each other. In the other direction... Well, we start with a point $M$ in one preimage and do a bunch of projecting points down and finding minimals and taking preimages and using earlier lemmas and our first distance condition, and eventually end up with a fancy diagram, and finish up with an argument that two points are close to each other, so $M$ and one other point are "similarly close". This isn't good exposition, but I've got diagrams to keep a mental picture of the dozen different points and how they relate to each other in working memory.

Folk Result (from Vanessa): if two measures $m$ and $m^{\prime }$ are $ϵ$-distance apart in the KR metric, then if you extend $m$ in some way, and extend $m^{\prime }$ with the same conditional probabilities, then the two resulting measures remain $ϵ$-apart. We'll be using this in both directions.

Proof direction 1: Ok, we'll show the second way implies the first way, first. Fix some $ϵ$, and let the $\delta$ (distance between two partial policies) be low enough to guarantee that the distance parameter between the two preimages (according to definition 2, which has the $\lambda$-dependent distance guarantee) is $\frac{ϵ}{2(1+{\lambda }^{\odot })}(1+\lambda )$. We can always do this. ${\lambda }^{\odot }$ is fixed by our belief function.

Keep this image in mind while reading the following arguments. The upper left set is the preimage of $\Theta \left({\pi }_{pa}\right)\cap NF$, the upper right set is the preimage of $\Theta \left({\pi }_{pa}\right)\cap NF$, and the bottom right set is $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ itself.

Now, any $M$ in the preimage of $\Theta \left({\pi }_{pa}\right)\cap NF\cap \{\le \odot \}$ has a ${\lambda }^{\odot }$ upper bound on its $\lambda$ value because projection preserves $\lambda$. By the $\lambda$-dependent distance condition, it's within $\frac{ϵ}{2(1+{\lambda }^{\odot })}(1+{\lambda }^{\odot })$ from the preimage of $\Theta \left({\pi }_{pa}\right)\cap NF$, so we can hop over that far and get a point $M^{\prime }$.

Admittedly, moving over to the nearby point $M^{\prime }$ may involve violating the ${\lambda }^{\odot }$ bound by $\frac{ϵ}{2(1+{\lambda }^{\odot })}(1+{\lambda }^{\odot })$ or less, but if that happens, we can project down our $M^{\prime }$ point to $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ making $M^{{}^{\prime }lo}$, find a point $M^{{}^{\prime }min}$ (nirvana-free) in $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF\cap \{\le \odot \}$ (bounded-minimals) below $M^{lo}$ where $M^{{}^{\prime }min}+M^{\ast }=M^{{}^{\prime }lo}$ by upper-completion for $\Theta \left({\pi }_{pa}^{\prime }\right)$, and then consider the reexpression of $M^{lo}$ as $M^{{}^{\prime }min}+(m^{\ast -},-m^{\ast -}(1\left)\right)+(m^{\ast +},b^{\ast }+m^{\ast -}(1\left)\right)$

The sum of the first two terms is a nirvana-free a-measure (because $M^{lo}$ is an a-measure, adding on the negative component does nothing) that lies below $M^{lo}$ and respects the ${\lambda }^{\odot }+b^{\odot }$ bound (exactly as much as it adds to $b$, it takes away from the measure). and then you can add in most of the third term, going just up to the bound), to get a point $M^{{}^{\prime \prime }lo}$ only $\frac{ϵ}{2(1+{\lambda }^{\odot })}(1+{\lambda }^{\odot })$ (at most) away from $M^{{}^{\prime }lo}$, which respects the bound (so it lies in $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF\cap \{\le \odot \}$)

Now, you can complete $M^{{}^{\prime \prime }lo}$ with the conditional probabilities of the measure part of $M^{\prime }$, to make a point $M^{\prime \prime }$ in the preimage of $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF\cap \{\le \odot \}$ that's $\frac{ϵ}{2(1+{\lambda }^{\odot })}(1+{\lambda }^{\odot })$ or less distance away from $M^{\prime }$

Going from $M$ to $M^{\prime }$, and $M^{\prime }$ to $M^{\prime \prime }$ is $\frac{ϵ}{2(1+{\lambda }^{\odot })}(1+{\lambda }^{\odot })$ distance both times, so we found a $\delta$ distance between any two partial policies ${\pi }_{pa}$ and ${\pi }_{pa}^{\prime }$ that ensures the preimages of $\Theta \left({\pi }_{pa}\right)\cap NF\cap \{\le \odot \}$ and $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF\cap \{\le \odot \}$ are only $ϵ$ apart.

Proof Direction 2: Keep tabs on the following diagram to see how the 12 different points in 5 different sets relate to each other.

This $\delta$ gives us an n via: $n={\log }_{\gamma }\left(\delta \right)$ which is the first time the partial policies start disagreeing on what to do. The upper left and upper right sets are the preimages of $\Theta \left({\pi }_{pa}\right)\cap NF$ and $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ respectively, the middle-left and middle-right sets are the sets themselves, and the bottom set is: Take the inf of ${\pi }_{pa}$ and ${\pi }_{pa}^{\prime }$, it's another partial policy that's fully defined before time n because those policies agree up till that time, and chop it off at time n, so it's a stub, call this stub ${\pi }_{pa}^{lo}$. The bottom set is $M^a\left(F^{NF}\right({\pi }_{pa}^{lo}\left)\right)$.

Now, follow the diagram in conjunction with the following proof. We start with an arbitrary $M$ in the preimage of $\Theta \left({\pi }_{pa}\right)\cap NF$. We project it down to $\Theta \left({\pi }_{pa}\right)\cap NF$ to make $M^{mid}$. Due to bounded-minimals, we can find a minimal point below it, $M^{\ast mid}$ which obeys the ${\lambda }^{\odot }+b^{\odot }$ bound. Now, we go in two directions. One is projecting $M^{mid}$ and $M^{\ast mid}$ down to make $M^{lo}$ and $M^{\ast lo}$, the latter of which lies below $M^{lo}$. Let's just keep those two in mind. In the other direction, since $M^{\ast mid}$ obeys the ${\lambda }^{\odot }+b^{\odot }$ bound and lies in $\Theta \left({\pi }_{pa}\right)\cap NF\cap \{\le \odot \}$, we can find a point $M^{\ast }$ in the preimage that obeys the ${\lambda }^{\odot }+b^{\odot }$ bound, and so, there's another point

 $M^{{}^{\prime }\ast }$ in $\left(p{r}_{\ast }^{\infty ,{\pi }_{pa}^{\prime }}{)}^{-1}\right(\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF\cap \{\le \odot \})$

 that's only $ϵ$ or less away, by our version of the Hausdorff condition that only works on the clipped version of the preimages. $M^{{}^{\prime }\ast }$ projects down to $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ to make $M^{{}^{\prime }\ast mid}$, and projects down further to make $M^{{}^{\prime }\ast lo}$.

Now, projections preserve or contract distances, and $M^{\ast lo}$ is the projection of $M^{\ast }$, and $M^{{}^{\prime }\ast lo}$ is the projection of $M^{{}^{\prime }\ast }$, and $M^{\ast }$ and $M^{{}^{\prime }\ast }$ are only $\frac{ϵ}{2}$ apart, so $M^{\ast lo}$ and $M^{{}^{\prime }\ast lo}$ are only $\frac{ϵ}{2}$ apart, and $M^{lo}$ lies above $M^{\ast lo}$. Now, we can invoke Lemma 14 to craft a $M^{{}^{\prime }lo}$ that's above $M^{{}^{\prime }\ast lo}$ and within $\frac{ϵ}{2}$ of $M^{lo}$. Then, we can observe that $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ is nirvana-free and nirvana-free upper-complete. So, by Lemma 11, its projection down is nirvana-free and nirvana-free upper complete. $M^{{}^{\prime }\ast lo}$ is the projection down of $M^{{}^{\prime }\ast mid}$, and $M^{{}^{\prime }lo}$ is above $M^{{}^{\prime }\ast lo}$, so $M^{{}^{\prime }lo}$ is in the projection of $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ and we can craft a point $M^{{}^{\prime }mid}\in \Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ that projects down accordingly. And then go a level up to the preimage of $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$, and make a preimage point $M^{\prime }$ by extending $m^{{}^{\prime }mid}$ with the conditional probabilities of $m$ up till time n whenever you get a chance, and then doing whatever, that'll be our $M^{\prime }$ point of interest. The diagram sure came in handy, huh?

We still need to somehow argue that $M$ and $M^{\prime }$ are close to each other in a $\lambda$ (the $\lambda$ of $M$) dependent way. And the only tool we have is that $M^{lo}$ and $M^{{}^{\prime }lo}$ are within $\frac{ϵ}{2}$ of each other, and $M$ and $M^{\prime }$ project down onto them. So how do we do that? Well, notice that before time n, $m^{\prime }$ and $m$ are either: in a part of the action-observation tree where ${\pi }_{pa}^{lo}$ has opinions on, and they're $\frac{ϵ}{2}$-apart there, or $m^{\prime }$ is copying the conditional probabilities of $m$. So, if we were to chop $m$ and $m^{\prime }$ off at timestep n, the two measures would be within $\frac{ϵ}{2}$ of each other.

However, after timestep n, things go to hell, they both end up diverging and doing their own thing. 

Now, we can give the following dirt-reshuffling procedure to turn $m$ into $m^{\prime }$. You've got piles of dirt on each history, corresponding to the measure component of $M$. You can "coarse-grain" and imagine all your distinct and meticulous, but close-together, piles of dirt on histories with a prefix of $h$, where $|h|=n$, as just one big pile on $h$. So, you follow the optimal dirt-reshuffling procedure for turning $m$ (clipped off at length n) into $m^{\prime }$ (clipped off at length n), which takes $\frac{ϵ}{2}$ effort or less. Then, we un-coarse-grain and go "oh damn, we've gotta sort out all our little close-together-piles now to make $m^{\prime }$ exactly! We're not done yet!"

But we've got something special. When we're sorting out all our little close-together-piles... said piles are the extensions of a finite history with length n. All those extensions will agree for the first n timesteps. And the distance between histories is ${\gamma }^n$ where n is the first timestep they disagree, right? And further, n was ${\log }_{\gamma }\left(\delta \right)$, so whenever we move a bit of dirt somewhere else to rearrange all our close-together-piles, we're only moving it $\delta$ distance! So, in the worst case of doing a complete rearrangement, we've gotta move our whole quantity of dirt $\delta$ distance, at a cost of $\delta {\lambda }^{\prime }$ effort (total amount of measure for $m^{\prime }$)

Let's try to bound this, shall we? Our first phase of dirt rearrangement (and adjusting the $b$ values) took $\frac{ϵ}{2}$ effort or less, our second phase took $\delta {\lambda }^{\prime }$ effort or less. Now, we can observe two crucial facts. The first is, at the outset, we insisted that $\delta$ was $<\frac{ϵ}{2}$. Our second crucial fact is that ${\lambda }^{\prime }$ and $\lambda$ can't be more than $\frac{ϵ}{2}$ apart, because projection preserves $\lambda$ values, and $M$ and $M^{\prime }$ project down to $M^{lo}$ and $M^{{}^{\prime }lo}$ respectively, which are $\frac{ϵ}{2}$ or less apart. So, the total amount of measure they have can't differ by more than $\frac{ϵ}{2}$. This lets us get:

$d(M,M^{\prime })\le \frac{ϵ}{2}+\delta {\lambda }^{\prime }\le \frac{ϵ}{2}+\delta (\frac{ϵ}{2}+\lambda )<\frac{ϵ}{2}+\frac{ϵ}{2}(\frac{ϵ}{2}+\lambda )<\frac{ϵ}{2}+\frac{ϵ}{2}(1+2\lambda )$

$=ϵ+ϵ\lambda =ϵ(1+\lambda )$

And so, given any $ϵ$, there's a $\delta$ where if $d({\pi }_{pa},{\pi }_{pa}^{\prime })<\delta$, then for any point $M$ in the preimage of $\Theta \left({\pi }_{pa}\right)\cap NF$, there's a point $M^{\prime }$ in the preimage of $\Theta \left({\pi }_{pa}^{\prime }\right)\cap NF$ s.t. $d(M,M^{\prime })<ϵ(1+\lambda )$, deriving our second formulation of Hausdorff-continuity from our first one. And we're done! Fortunately, the next one is easier.

Lemma 16: If $M_n$ limits to $M$, and $M_n^{lo}$ are all below their corresponding $M_n$ and obey a ${\lambda }^{\odot }+b^{\odot }$ bound, then all limit points of $M_n^{lo}$ lie below $M$. This works for a-surmeasures too.

Proof sketch: We've got a ${\lambda }^{\odot }+b^{\odot }$ bound, so we can use the Compactness Lemma or Lemma 8 to get a convergent subsequence. Now, this is a special proof because we don't have to be as strict as we usually are about working only with a-measures and sa-measures only showing up as intermediate steps. What we do is take a limit point of the low sequence, and add some sa-measure to it that makes the resulting sa-measure close to $M$, so $M$ is close to the upper completion of our limit point. We can make it arbitrarily close, and the upper completion of a single point is closed, so $M$ actually does lie above our limit point and we're done. To do our distance fiddling argument in the full generality that works for sur-stuff, we do need to take a detour and show that for surmeasures, $d_s(x+y,z+y)\le d_s(x,z)$.

Proof: The $M_n^{lo}$ obey the ${\lambda }^{\odot }+b^{\odot }$ bound, so convergent subsequences exist by the compactness lemma or Lemma 8. Pick out a convergent subsequence to work in, giving you a limit point $M^{lo}$. All the $M_n$ can be written as $M_n^{lo}+M_n^{\ast }$.

We'll take a brief detour, and observe that if we're just dealing with sa-measures, then, since we're in a Banach space, $d(x+y,z+y)=d(x,z)$. But what about the surmetric? Well, the surmetric is the max of the usual metric and \gam raised to the power of "first time the measure components start disagreeing on what nirvana events are possible or impossible". Since sa-measures and sa-surmeasures can't assign negative probability to Nirvana, adding an sa-surmeasure adds more nirvana spots into both surmeasure components! In particular, they won't disagree more, and may disagree less, since adding that sa-surmeasure in may stick nirvana on a spot that they disagree on, so now they both agree that Nirvana happens there. So, since the standard distance component stays the same and the nirvana-sensitive component says they stayed the same or got closer, $d_s(x+y,z+y)\le d_s(x,z)$. We'll be using this. 

Let n be large enough that $d(M_n,M)<ϵ$ and $d(M_n^{lo},M^{lo})<ϵ$ (same for surmetric) Now, consider the point $M^{lo}+M_n^{\ast }$. It is an sa-measure or sa-surmeasure that lies above $M_n$ and we'll show that it's close to $M$. Whether we're working with the sa-measures or sa-surmeasures,

$d(M^{lo}+M_n^{\ast },M)\le d(M^{lo}+M_n^{\ast },M_n)+d(M_n,M)<d(M^{lo}+M_n^{\ast },M_n^{lo}+M_n^{\ast })+ϵ$

$\le d(M^{lo},M_n^{lo})+ϵ<2ϵ$

So, $M$ is $<2ϵ$ distance from the upper completion of $M^{lo}$ in the space of sa-measures/sa-surmeasures, for all $ϵ$. Said upper completion is the sum of a closed set (cone of sa-measures/sa-surmeasures) and a compact set (a single point) so it's closed, so $M$ (an a-measure/a-surmeasure) lies above $M^{lo}$ (an a-measure/a-surmeasure that was an arbitrary limit point of the $M_n^{lo}$) and we're done.

 

The next three, Lemmas 17, 18, and 19, are used to set up the critical Lemma 20 which we use a lot.

Lemma 17: The function $\Pi \to M^a\left(\infty \right)$ of the form $\pi \mapsto {\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}$ has closed graph assuming Hausdorff-continuity for ${\Theta }^{\omega }$ on policies, and that ${\Theta }^{\omega }\left(\pi \right)$ is closed for all $\pi$. Also works for a $\Theta$ that fulfills the stated properties.

Let ${\pi }_n$ limit to $\pi$, and let $M_n\in {\Theta }^{\omega }\left({\pi }_n\right)\cap NF\cap \{\le \odot \}$ limit to $M$. We'll show that $M\in {\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}$ (the definition of closed graph) Take some really big n that guarantees that $d({\pi }_n,\pi )<\delta$ and $d(M_n,M)<ϵ$. Then we go:

The distance from $M$ to $M_n$ is $ϵ$ or less, and since $M_n\in {\Theta }^{\omega }\left({\pi }_n\right)$, we can invoke uniform Hausdorff continuity and conclude $M_n$ is only $ϵ$ or less away from a point in ${\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}$. So, the distance from $M$ to ${\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}$ is $\le 2ϵ$. This argument works for all $ϵ$, so it's at distance 0 from ${\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}$, and that set is closed because it's an intersection of closed sets, so $M\in {\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}$, and we have closed-graph.

Lemma 18: ${\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\left({\Theta }^{\omega }\right(\pi )\cap NF\cap \{\le \odot \left\}\right)$  is compact as long as ${\Theta }^{\omega }\left(\pi \right)$ is closed for all $\pi$ and ${\Theta }^{\omega }$ fulfills the Hausdorff-continuity property on policies. Also works for a $\Theta$ that fulfills the stated properties.

The set of $\pi \ge {\pi }_{st}$ is closed in the topology on $\Pi$, because a limit of policies above ${\pi }_{st}$ will still be above ${\pi }_{st}$. More specifically, because it's a closed subset of a compact space, it's compact. Also, remembering that projection preserves $\lambda$ and $b$, we can consider the set $\{\le \odot \}$ (for $M^a\left(\infty \right)$) which is compact.

Take the product of those two compact sets to get a compact set in $\Pi \times M^a\left(\infty \right)$, intersect it with the graph of our function mapping $\pi$ to ${\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}$ (which is closed by Lemma 17), we get a compact set, project it down to the $M^a\left(\infty \right)$ coordinate (still compact, projection to a coordinate is continuous), and everything in that will be safe to project down to $M^a\left(F^{NF}\right({\pi }_{st}\left)\right)$, getting you exactly the set  ${\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\left({\Theta }^{\omega }\right(\pi )\cap NF\cap \{\le \odot \left\}\right)$ which is compact because it's the image of a compact set through a continuous function.

Lemma 19:

$\overline{c.h}\left({\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right({\Theta }^{\omega }\left(\pi \right)\cap NF\left)\right)={(c.h\left({\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right({\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}\left)\right))}^{uc}$

Where the upper completion is with respect to the cone of nirvana-free sa-measures and then we intersect with the set of nirvana-free a-measures, and ${\Theta }^{\omega }\left(\pi \right)$ is closed and nirvana-free upper-complete for all $\pi$ and ${\Theta }^{\omega }$ fulfills the Hausdorff-continuity property on policies and the bounded-minimals property. Also works for a $\Theta$ that fulfills the stated properties.

One direction of this,

$\overline{c.h}\left({\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right({\Theta }^{\omega }\left(\pi \right)\cap NF\left)\right)\supseteq {(c.h\left({\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right({\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}\left)\right))}^{uc}$

is pretty easy. Everything in the convex hull of the clipped projections lies in the closed convex hull of the full projections, and then, from lemmas 11, 12, and 13, the closed convex hull of these projections is nirvana-free upper complete since ${\Theta }^{\omega }\left(\pi \right)$ is for all $\pi$, so that gets the points added by upper completion as well, establishing one subset direction.

Now for the other direction,

$\overline{c.h}\left({\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right({\Theta }^{\omega }\left(\pi \right)\cap NF\left)\right)\subseteq {(c.h\left({\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right({\Theta }^{\omega }\left(\pi \right)\cap NF\cap \{\le \odot \}\left)\right))}^{uc}$

Let $M$ lie in the closed convex hull. There's a sequence $M_n$ that limits to it, where all the $M_n$ are made by taking $M_{i,n}^{\infty }$ from above, projecting down and mixing. By bounded minimals, we can find some $M_{i,n}^{\infty ,min}\in {\Theta }^{\omega }\left(\pi \right)\cap NF$ below the $M_{i,n}^{\infty }$, and they're minimal points so they all obey the ${\lambda }^{\odot }+b^{\odot }$ bound. Now, project the $M_{i,n}^{\infty ,min}$ down, and mix in the same way, to get an a-measure $M_n^{lo}$ below $M_n$, which lies in the convex hull of clipped projections.

From Lemma 16, we can take a limit point of $M_n^{lo}$ to get a $M^{lo}$ below $M$. Now, we just have to show that $M^{lo}$ lies in the convex hull set in order to get $M$ by upper completion. $M_{lo}$ is a limit of points from the convex hull set, so we just have to show that said convex hull set is closed. The thing we're taking the convex hull of is compact (Lemma 18), and in finite dimensions (because we're working in a stub), the convex hull of a compact set is compact. Thus, $M^{lo}$ lies in the convex hull, and is below $M$, so $M$ lies in the upper completion of the convex hull and we're done.

Lemma 20:  $c.h\left({\bigcup }_{\pi \ge {\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right({\Theta }^{\omega }\left(\pi \right)\cap NF\left)\right)$ is closed, if ${\Theta }^{\omega }\left(\pi \right)$ is closed and nirvana-free upper-complete for all $\pi$ and ${\Theta }^{\omega }$ fulfills the Hausdorff-continuity property on policies and the bounded-minimals property. Also works for a $\Theta$ that fulfills the stated properties.

By Lemmas 11 and 12, said convex hull is nirvana-free upper-complete. Any point in the closure of the convex hull, by Lemma 19, lies above some finite mixture of nirvana-free stuff from above that respects the ${\lambda }^{\odot }+b^{\odot }$ bound, projected down. However, since the convex hull is upper-complete, our arbitrary point in the closure of the convex hull is captured by the convex hull alone.

Lemma 21: If $\Theta$ is consistent and nirvana-free upper-complete for $\Theta \left(\pi \right)$, and obeys the extreme point condition, and obeys the Hausdorff-continuity condition on policies, then$\Theta \left({\pi }_{pa}\right)\cap NF=\overline{c.h}\left({\bigcup }_{\pi \ge {\pi }_{pa}}p{r}_{\ast }^{\pi ,{\pi }_{pa}}\right(\Theta \left(\pi \right)\cap NF\left)\right)$ and$\Theta \left({\pi }_{st}\right)\cap NF=c.h\left({\bigcup }_{\pi >{\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right(\Theta \left(\pi \right)\cap NF\left)\right)$ This works in the sur-case too.

Proof sketch: One subset direction is pretty dang easy from Consistency. The other subset direction for stubs (that any nirvana-free point in $\Theta \left({\pi }_{st}\right)$ lies in the convex hull of projections from above) is done by taking your point $M$ of interest, finding a minimal point below it, using Lemma 3 to split your minimal points into finitely many minimal extreme points, and using the extreme point condition to view them as coming from policies above, so the minimal point has been captured by the convex hull, and then Lemmas 11 and 12 say that the convex hull of those projections is nirvana-free upper-complete, so our $M$ is captured by the convex hull.
Getting it for partial policies is significantly more complex. We take our $M$ and project it down into $\Theta \left({\pi }_{pa}^n\right)$ for some very large n. Then, using our result for stubs, we can view our projected point $M_n$ as a mix of nirvana-free stuff from policies above ${\pi }_{pa}^n$. If n is large enough, ${\pi }_{pa}^n$ is very close to ${\pi }_{pa}$ itself, so we can perturb our points at the infinite level a little bit to be associated with policies above ${\pi }_{pa}$ with Hausdorff-Continuity, and then we can project down and mix, and show that this point (in the convex hull of projections of nirvana-free stuff from above) is close to $M$ itself, getting a sequence that limits to $M$, witnessing that it's in the closed convex hull of projections of nirvana-free stuff from above. It's advised to diagram the partial policy argument, it's rather complicated.

Ok, so one direction is easy, $\Theta \left({\pi }_{pa}\right)\cap NF\supseteq \overline{c.h}\left({\bigcup }_{\pi \ge {\pi }_{pa}}p{r}_{\ast }^{\pi ,{\pi }_{pa}}\right(\Theta \left(\pi \right)\cap NF\left)\right)$ (and likewise for stubs). Consistency implies that $\Theta \left({\pi }_{pa}\right)$ (or $\Theta \left({\pi }_{st}\right)$) is the closed convex hull of projections down from above, so the closed (or vanilla) convex hulls of the projections of nirvana-free stuff from above are a subset of the nirvana-free part of $\Theta \left({\pi }_{pa}\right)$ (or $\Theta \left({\pi }_{st}\right)$).

For the other direction... we'll show the stub form, that's easier, and build on that. We're shooting for $\Theta \left({\pi }_{st}\right)\cap NF\subseteq c.h\left({\bigcup }_{\pi >{\pi }_{st}}p{r}_{\ast }^{\pi ,{\pi }_{st}}\right(\Theta \left(\pi \right)\cap NF\left)\right)$

Fix some $M\in \Theta \left({\pi }_{pa}\right)\cap NF$. Find a minimal point $M^{min}$ below it, which must be nirvana-free, because you can't make Nirvana vanish by adding sa-measures. Invoke Lemma 3 to write $M^{min}$ as a finite mixture of minimal extreme points in the nirvana-free part of $\Theta \left({\pi }_{st}\right)$. These must be minimal and extreme and nirvana-free in $\Theta \left({\pi }_{st}\right)$, because you can't mix nirvana-containing points and get a nirvana-free point, nor can you add something to a nirvana-containing point without getting a nirvana-containing point. By the extreme point condition, there are nirvana-free points from above that project down to those extreme points. Mixing them back together witnesses that $M^{min}$ lies in the convex hull of projections of nirvana-free stuff from above. $M$ is nirvana-free and lies above $M^{min}$, so it's captured by the convex hull (with Lemmas 11 and 12)

Now for the other direction with partial policies, that

$\Theta \left({\pi }_{pa}\right)\cap NF\subseteq \overline{c.h}\left({\bigcup }_{\pi \ge {\pi }_{pa}}p{r}_{\ast }^{\pi ,{\pi }_{pa}}\right(\Theta \left(\pi \right)\cap NF\left)\right)$

Fix some $M\in \Theta \left({\pi }_{pa}\right)\cap NF$. We can project $M$ down to all the ${\pi }_{pa}^n$ to get $M_n$ which are nirvana-free and in $\Theta \left({\pi }_{pa}^n\right)$ by Consistency.

Our task is to express $M$ as a limit of some sequence of points that are finite mixtures of nirvana-free projected from policies above ${\pi }_{pa}$. Also, remember the link between "time of first difference n" and the $\delta$ distance between two partial policies. ${\delta }_n={\gamma }^n$ where $\gamma <1$. Each ${\delta }_n$ induces an ${ϵ}_n$ number for the purposes of Hausdorff-continuity.

First, ${\pi }_{pa}^n$ is a stub, which, as we have already established has its nirvana-free part equal the convex hull of projections of nirvana-free stuff down from above. So, $M_n$ is made by taking finitely many $M_{i,n}^{\infty }\in \Theta \left({\pi }_i\right)\cap NF$ where ${\pi }_i\ge {\pi }_{pa}^n$, projecting down, and mixing. By linearity of projection, we can mix the $M_{i,n}^{\infty }$ before projecting down and hit the same point, call this mix $M_n^{\infty }$. 

Since the distance between ${\pi }_{pa}^n$ and ${\pi }_{pa}$is ${\delta }_n$ or less, each policy ${\pi }_i$ has another policy within ${\delta }_n$ that's above ${\pi }_{pa}$, and by uniform Hausdorff-continuity (the variant from Lemma 15) we only have to perturb the $M_{i,n}^{\infty }$ by ${ϵ}_n(1+{\lambda }_{i,n})$ to get $M_{i,n}^{{}^{\prime }\infty }$ in $\Theta \left({\pi }_i^{\prime }\right)\cap NF$ where ${\pi }_i^{\prime }\ge {\pi }_{pa}$ for all i. 

Mixing these in the same proportion makes a $M_n^{{}^{\prime }\infty }$ within ${ϵ}_n(1+\lambda )$ of $M_n^{\infty }$, which projects down to $\Theta \left({\pi }_{pa}\right)\cap NF$ (because mix-then-project is the same as projecting the $M_{i,n}^{{}^{\prime }\infty }$ then mixing, and the convex hull of projections of stuff from above is a subset of $\Theta \left({\pi }_{pa}\right)$ by consistency) The projection of $M_n^{{}^{\prime }\infty }$ we'll call $M_n^{\prime }$. It lies in the convex hull of the projections of nirvana-free stuff from above.

Now, to finish up, we just need to show that $M_n^{\prime }$ limit to $M$, witnessing that $M$ is in the closed convex hull of projections of nirvana-free stuff from above. Since $M_n^{\prime }$ is the projection of $M_n^{{}^{\prime }\infty }$, which is ${ϵ}_n(1+\lambda )$ away from $M_n^{\infty }$, and projection doesn't increase distance, and the projection of $M_n^{\infty }$ is $M_n$, we can go 

$d\left(p{r}_{\ast }^{{\pi }_{pa},{\pi }_{pa}^n}\right(M_n^{\prime }),M_n)=d\left(p{r}_{\ast }^{\infty ,{\pi }_{pa}^n}\right(M_n^{{}^{\prime }\infty }),p{r}_{\ast }^{\infty ,{\pi }_{pa}^n}(M_n^{\infty }\left)\right)\le d(M_n^{{}^{\prime }\infty },M_n^{\infty })<{ϵ}_n(1+\lambda )$

So, we can conclude that, restricting to before time n, the measure components of $M_n^{\prime }$ and $M$ are fairly similar (${ϵ}_n(1+\lambda )$ distance), and so are the $b$ components. Then some stuff happens after time n. Because our distance evaluation is done with Lipschitz functions, they really don't care that much what happens at late times. So, in the $n\to \infty$ limit, the difference between the $b$ terms vanishes, and the measure components agree increasingly well (limiting to perfect agreement for times before n, and then some other stuff happens, and since the other stuff happens at increasingly late time (n is diverging), the measure components converge.

So, we just built $M$ as a limit of points from the convex hull of the projections of nirvana-free parts down from above, and we're done.

Alright, we're back. We've finally accumulated a large enough lemma toolkit to attack our major theorem, the Isomorphism theorem. Time for the next post! [AF · GW]

0 comments

Comments sorted by top scores.