Infrafunctions Proofs

post by Diffractor · 2023-04-27T19:25:44.903Z · LW · GW · 1 comments

Contents

  Proposition 1:
  Theorem 1: Fundamental Theorem of Infrafunctions
  Theorem 2: Lp Ball Theorem
  Theorem 3: Dynamic Consistency
  Proposition 2: Lp Double Integral Inequality
  Corollary 1: Lp-Averaging is Well-Defined
  Theorem 4: Crappy Optimizer Theorem
  Proposition 3:
  Proposition 4:
None
1 comment

Proposition 1:

Given some compact metric space of options $X$, if $U:X\to R$ is a bounded function, $\{\mu |\forall \nu \in \Delta X:\mu (U)\ge \nu (U\left)\right\}=\Delta \{x|\forall y\in X:U(x)\ge U(y\left)\right\}$

PROOF: To do this, we must show that anything in the first set is in the second, and vice-versa. So, assume $\mu$ is in the first set. Then for any $\nu$, $\nu \left(U\right)\le \mu \left(U\right)$. However, if $\mu$ is not in the second set, then it has probability-mass on some points $x$ where there's a $y$ s.t. $U\left(y\right)>U\left(x\right)$. Moving that new probability mass to points of higher utility, we'd construct a new probability distribution $\nu$ s.t. $\nu \left(U\right)>\mu \left(U\right)$, which is impossible. So $\mu$ must be in the second set.

In the reverse direction, any probability distribution $\mu$ supported over the maximum of $U$ (let $x$ be an arbitrary point in it) has $\mu \left(U\right)=U\left(x\right)$. Thus, for any $\nu$, it's supported entirely over points with equal or lesser utility than this maximum value, so $\mu \left(U\right)\ge \nu \left(U\right)$. Both subset inclusion directions have been proved, so the equality holds.

Theorem 1: Fundamental Theorem of Infrafunctions

There is a bijection between concave upper-semicontinuous functions of type $\Delta X\to R\cup \{-\infty \}$, and closed convex upper-complete sets of continuous functions $X\to R$.

Proof: For the reverse direction, going from sets to functions, letting $\hat{\text{F}}$ denote the set and $\text{F}$ denote the function, we have that $$\text{F}\left(\mu \right):=\underset{f\in \hat{\text{F}}}{inf}\mu \left(f\right)$$ With this definition being made, let's verify that the resulting function fulfills the indicated property. For verifying concavity, we have $$\text{F}(p\mu +(1-p\left)\nu \right)=\underset{f\in \hat{\text{F}}}{inf}(p\mu +(1-p\left)\nu \right)\left(f\right)\ge p\underset{f\in \hat{\text{F}}}{inf}\mu \left(f\right)+(1-p)\underset{f\in \hat{\text{F}}}{inf}\nu \left(f\right)=p\text{F}\left(\mu \right)+(1-p)\text{F}\left(\nu \right)$$ For verifying upper-semicontinuity, let ${\mu }_n$ limit to $\mu$. Now, for any particular function $f^{\ast }$, due to ${\mu }_n$ limiting to $\mu$, we have $$\underset{n\to \infty }{limsup}{\mu }_n\left(f^{\ast }\right)=\mu \left(f^{\ast }\right)$$ So, for any $f^{\ast }$ where $\mu \left(f^{\ast }\right)$ is an (arbitrarily close) approximation to ${inf}_{f\in \hat{\text{F}}}\mu \left(f\right)$, we can go $$\text{F}\left(\mu \right)=\underset{f\in \hat{\text{F}}}{inf}\mu \left(f\right)\simeq \mu \left(f^{\ast }\right)=\underset{n\to \infty }{limsup}{\mu }_n\left(f^{\ast }\right)\ge \underset{n\to \infty }{limsup}\underset{f\in \hat{\text{F}}}{inf}{\mu }_n\left(f\right)=\underset{n\to \infty }{limsup}\text{F}\left({\mu }_n\right)$$ And so upper-semicontinuity is established, that $$\text{F}\left(\mu \right)\ge \underset{n\to \infty }{limsup}\text{F}\left({\mu }_n\right)$$ For the forwards direction, going from functions to sets, letting $\text{F}$ denote the function, the corresponding set of functions is $$\{f|\forall \mu \in \Delta X:\mu (f)\ge \text{F}(\mu \left)\right\}$$ We must show that the result is closed, convex, and upper-complete.

For closure, if $f_m$ limits to $f$, and all the $f_m$ are in the set (so $\mu \left(f_m\right)\ge \text{F}\left(\mu \right)$ for all $m$ and $\mu$) and $\mu$ is arbitrary, then due to $f_m$ limiting to $f$, we have that $\mu \left(f\right)={lim}_{m\to \infty }\mu \left(f_m\right)\ge \text{F}\left(\mu \right)$ and this argument works for all $\mu$, so $f$ is in the indicated set.

For convexity, our job is to show that if $f$ and $g$ are in the set, $pf+(1-p)g$ are in the set too. Fix an arbitrary $\mu$. $$\mu (pf+(1-p\left)g\right)=p\mu \left(f\right)+(1-p)\mu \left(g\right)\ge p\text{F}\left(\mu \right)+(1-p)\text{F}\left(\mu \right)=\text{F}\left(\mu \right)$$ And convexity is shown. For upper-completeness, assume that $g\ge f$ according to the usual ordering on functions. Then $$\mu \left(g\right)\ge \mu \left(f\right)\ge \text{F}\left(\mu \right)$$

Now, all that remains is to show that the two translation directions compose to identity in both directions.

For function-to-set-to-function being identity, a sufficient property for this to hold is that, for every ${\mu }^{\prime }\in \Delta X$ and $x>\text{F}\left({\mu }^{\prime }\right)$, there exists a continuous function $f$ s.t. $\forall \mu \in \Delta X:\mu \left(f\right)\ge \text{F}\left(\mu \right)$ and $x\ge {\mu }^{\prime }\left(f\right)$

Why? Well, every function $f$ that lies in the set $\hat{\text{F}}$ has the property that $\forall \mu :\mu \left(f\right)\ge \text{F}\left(\mu \right)$. Therefore, regardless of $\mu$, we have that $$\forall {\mu }^{\prime }:\underset{f:\forall \mu ,\mu \left(f\right)\ge \text{F}\left(\mu \right)}{inf}{\mu }^{\prime }\left(f\right)\ge \text{F}\left({\mu }^{\prime }\right)$$ Or, rephrasing $$\forall {\mu }^{\prime }:\underset{f\in \hat{\text{F}}}{inf}{\mu }^{\prime }\left(f\right)\ge \text{F}\left({\mu }^{\prime }\right)$$ And, \emph{if} we had the property that for every ${\mu }^{\prime }\in \Delta X$ and $x>\text{F}\left({\mu }^{\prime }\right)$, there exists a continuous function $f$ s.t. $\forall \mu \in \Delta X:\mu \left(f\right)\ge \text{F}\left(\mu \right)$ and $x\ge {\mu }^{\prime }\left(f\right)$, that would mean that regardless of ${\mu }^{\prime }$, you could find functions $f$ that would lie in $\hat{\text{F}}$, and where ${\mu }^{\prime }\left(f\right)$ would lie arbitrarily close to $\text{F}\left({\mu }^{\prime }\right)$. This would get equality, that $$\forall {\mu }^{\prime }:\underset{f:\forall \mu ,\mu \left(f\right)\ge \text{F}\left(\mu \right)}{inf}{\mu }^{\prime }\left(f\right)=\text{F}\left({\mu }^{\prime }\right)$$ Or, rephrasing, $$\forall {\mu }^{\prime }:\underset{f\in \hat{\text{F}}}{inf}{\mu }^{\prime }\left(f\right)=\text{F}\left({\mu }^{\prime }\right)$$ Or, rephrasing, $$\underset{f\in \hat{\text{F}}}{inf}=\text{F}$$ Ie, going from function to set to function again is identity.

As for the other direction, in order for set-to-function-to-set to be identity, the $\subseteq$ inclusion direction is pretty easy to prove outright. For any $f$ in a set of functions, it'll exceed the inf of that set of functions, and so it'll end up being in the set generated by that inf.

The $\supseteq$ inclusion direction is harder. We'd need to show that given any closed convex upper-complete set of continuous bounded functions, $\hat{\text{F}}$, any function $g$ which is outside of that set has some $\mu$ where $\mu \left(g\right)<{inf}_{f\in \hat{\text{F}}}\mu \left(f\right)$. The reason that showing that helps is it establishes that $g$ cannot be in the set induced by the inf of everything in $\hat{\text{F}}$. Therefore, the set induced by the inf function can't be a strict superset of $\hat{\text{F}}$, because any $g$ in the former set and not the latter one can be used to generate a witness that it's not in the former set.

So, our two missing results to prove to establish the entire isomorphism theorem are:

1: Establishing that for every ${\mu }^{\prime }\in \Delta X$ and $x>\text{F}\left({\mu }^{\prime }\right)$, there exists a continuous function $f$ s.t. $\forall \mu \in \Delta X:\mu \left(f\right)\ge \text{F}\left(\mu \right)$ and $x\ge {\mu }^{\prime }\left(f\right)$.

2: Establishing that for any closed convex upper-complete set of continuous bounded functions, $\hat{\text{F}}$, any function $g$ which is outside of that set has some $\mu$ where $\mu \left(g\right)<{inf}_{f\in \hat{\text{F}}}\mu \left(f\right)$.

For both of these, we'll use the Hahn-Banach theorem. For the first one, let the set $A$ (a subset of $M^{\pm }\left(X\right)\oplus R$) be $\{y,\mu |y\le \text{F}(\mu \left)\right\}$, and the set $B$ be the set consisting of the single point $x,{\mu }^{\prime }$. The set $B$ is clearly convex, compact, and nonempty. That leaves showing that $A$ is closed, convex, and nonempty.

What we'll do is prove our desired result outright if the set $A$ is empty. It's the region under the graph of $\text{F}$, which can only be empty if $\text{F}=-\infty$, in which case you could take any function $f$ and subtract a sufficiently large constant from it to get a function whose expectation w.r.t $\mu$ was below the $x$ you named.

So, we may safely assume that the set $A$ is nonempty. Closure works because if $y_n$ limits to $y$ and ${\mu }_n$ limits to $\mu$, we have that $$y=\underset{n\to \infty }{lim}{y}_n\le \underset{n\to \infty }{limsup}\text{F}\left({\mu }_n\right)\le \text{F}\left(\mu \right)$$ by upper-semicontinuity. And convexity works because $$py+(1-p)y^{\prime }\le p\text{F}\left(\mu \right)+(1-p)\text{F}\left({\mu }^{\prime }\right)\le \text{F}(p\mu +(1-p\left){\mu }^{\prime }\right)$$ due to concavity of $\text{F}$.

We must show that the two sets aren't disjoint, which is easy because the single point has $x>\text{F}\left({\mu }^{\prime }\right)$. Thus the Hahn-Banach hyperplane separation theorem may be used to find an continuous affine hyperplane with $B$ on the top side of it, and $A$ on the top side of it. All continuous affine functions $M^{\pm }\left(X\right)\to R$ can be decomposed as a continuous linear functional $M^{\pm }\left(X\right)\to R$ (which can be interpreted as expectation w.r.t a bounded continuous function $f$), plus a constant. So, there's some bounded continuous function $f$ and constant number $b$ s.t. $\forall \mu ,y\in A:y\le \mu \left(f\right)+b$ (ie, $A$ is below the hyperplane induced by the affine function induced by $f,b$), and where ${\mu }^{\prime }\left(f\right)+b\le x$ (ie, the point $B$ consisting of ${\mu }^{\prime },x$ lies above the hyperplane induced by the affine function induced by $f,b$).

Now, specializing to the case where $y=\text{F}\left(\mu \right)$, and observing that $\mu (f+b)=\mu \left(f\right)+b$ for probability distributions, we can take $f+b$ to be our function of interest, and get that $$\forall \mu \in \Delta X:\mu (f+b)=\mu \left(f\right)+b\ge \text{F}\left(\mu \right)$$ and also, $x\ge {\mu }^{\prime }\left(f\right)+b={\mu }^{\prime }(f+b)$. So, we've found a function with the indicated properties, outright proving the first of our two unsolved problems.

This leaves the second one. The set $\hat{\text{F}}$ is closed and convex, and $g$ is just a single point, so we can invoke the Hahn-Banach theorem to get a separating linear functional. Some signed measure $m$ where $m\left(g\right)<{inf}_{f\in \hat{\text{F}}}m\left(f\right)$.

We need to show that this signed measure is a measure. If there was any negative region in the signed measure, then there could be a continuous function $g\ge 0$ that acted as a massive spike in the negative region of $m$, and $m(f+ag)$ (for very large constants $a$ and some $f\in \hat{\text{F}}$) would be arbitrarily negative, while $f+ag$ would lie in $\hat{\text{F}}$ by upper-closure, and we'd have a contradiction.

So, $m$ is a measure. Multiplying it by a suitable nonnegative constant turns it into a probability distribution $\mu$ that still fulfills the property that $\mu \left(g\right)<{inf}_{f\in \hat{\text{F}}}\mu \left(f\right)$, and we're done.

Since our two missing part of the proof were cleaned up, we've proven the overall theorem.

Theorem 2: $L_p$ Ball Theorem

For any $ϵ>0$, $p\in [1,\infty ]$, $f:X\to R$, and $\nu :\Delta X$, the infrafunction corresponding to $\{g|{(\int |f-g{|}^{p}d\nu )}^{\frac{1}{p}}\le ϵ\}$ (Knightian uncertainty over the $L_p$ ball of size $ϵ$ centered at $f$, w.r.t $\nu$), is $\mu \mapsto \mu \left(f\right)-ϵ||\frac{d\mu }{d\nu }|{|}_q$ where $\frac{1}{p}+\frac{1}{q}=1$. Further, given a function $f$, the optimal $\mu$ to pick is the distribution $a\cdot \nu \cdot max(f-b,0{)}^{p-1}$ for some constants $a>0$ and $b\le max\left(f\right)$.

Proof: The Lp norm of a function w.r.t. $\nu$ will be denoted as $||g|{|}_p$. The function associated with the worst-case amongst the $L_p$ ball centered at $f$ is $$\lambda \mu .\underset{g:||f-g|{|}_p\le ϵ}{inf}\mu \left(g\right)$$ We can rewrite this as $f$ plus a function $h$ that has an $L_p$ norm of $ϵ$ or less. So we get the equivalent function $$=\lambda \mu .\underset{h:||h|{|}_p\le ϵ}{inf}\mu (f+h)$$ $$=\lambda \mu .\underset{h:||h|{|}_p\le ϵ}{inf}\mu \left(f\right)+\mu \left(h\right)$$ $$=\lambda \mu .\mu \left(f\right)+\underset{h:||h|{|}_p\le ϵ}{inf}\mu \left(h\right)$$ $$=\lambda \mu .\mu \left(f\right)-\underset{h:||h|{|}_p\le ϵ}{sup}\mu \left(h\right)$$ Now, we'll show that ${sup}_{h:||h|{|}_p\le ϵ}\mu \left(h\right)=||\frac{d\mu }{d\nu }|{|}_q$ where $\frac{1}{p}+\frac{1}{q}=1$, by showing that it's both $\le$ and $\ge$ that quantity. For one inequality direction, we can go $$\underset{h:||h|{|}_p\le ϵ}{sup}\mu \left(h\right)=\underset{h:||h|{|}_p\le ϵ}{sup}\int hd\mu =\underset{h:||h|{|}_p\le ϵ}{sup}\int h\frac{d\mu }{d\nu }d\nu$$ And then apply Holder's inequality. $$\le \underset{h:||h|{|}_p\le ϵ}{sup}||h|{|}_p\cdot ||\frac{d\mu }{d\nu }|{|}_q=ϵ||\frac{d\mu }{d\nu }|{|}_q$$ And so, we have one inequality direction, that $$\underset{h:||h|{|}_p\le ϵ}{sup}\mu \left(h\right)\le ϵ||\frac{d\mu }{d\nu }|{|}_q$$ For the other inequality direction, we can let $h$ be defined as $ϵ\cdot \frac{{\left(\frac{d\mu }{d\nu }\right)}^{\frac{1}{p-1}}}{{(\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{1}{p}}}$

Our first order of business is showing that the $L_p$ norm of $h$ is $ϵ$ or less. So, compute it. $${(\int {(ϵ\cdot \frac{{\left(\frac{d\mu }{d\nu }\right)}^{\frac{1}{p-1}}}{{(\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{1}{p}}})}^{p}d\nu )}^{\frac{1}{p}}$$ Distribute the power in. $$={(\int {ϵ}^p\cdot \frac{{\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}}{\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu }d\nu )}^{\frac{1}{p}}$$ Pull the ${ϵ}^p$, group and cancel out. $$={\left({ϵ}^p\right)}^{\frac{1}{p}}=ϵ$$ So, this is a valid choice of function $h$. So, we can compute (by pulling the multiplicative constants out) $$\underset{h:||h|{|}_p\le ϵ}{sup}\mu \left(h\right)\ge \mu (ϵ\cdot \frac{{\left(\frac{d\mu }{d\nu }\right)}^{\frac{1}{p-1}}}{{(\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{1}{p}}})=ϵ\cdot {(\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{-1}{p}}\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{1}{p-1}}d\mu$$ Now, since $$\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{1}{p-1}}d\mu =\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{1}{p-1}}\frac{d\mu }{d\nu }d\nu =\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu$$ We can reexpress our old equation as $$=ϵ\cdot {(\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{-1}{p}}{(\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{p}{p}}=ϵ\cdot {(\int {\left(\frac{d\mu }{d\nu }\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{p-1}{p}}$$ $$=ϵ\cdot {(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}}=ϵ||\frac{d\mu }{d\nu }|{|}_q$$ So we have $$\underset{h:||h|{|}_p\le ϵ}{sup}\mu \left(h\right)\ge ϵ||\frac{d\mu }{d\nu }|{|}_q$$ Since that's the other inequality direction, we have equality. Now, since we were last at $$=\lambda \mu .\mu \left(f\right)-\underset{h:||h|{|}_p\le ϵ}{sup}\mu \left(h\right)$$ we can proceed to $$=\lambda \mu .\mu \left(f\right)-ϵ||\frac{d\mu }{d\nu }|{|}_q$$ And that addresses one part of the theorem, about the objective function we're minimizing.

Sadly, the last part, about the optimal $\mu$, can only be done according to a physics level of rigor. Given two points $x$ and $y$ which the optimal $\mu$ assigns probability to, the increase in the objective function from adding a tiny little $\delta$ of probability mass to $x$ must be the same as the increase from adding a tiny little $\delta$ of probability mass to $y$. This is because, otherwise, if $x$ got a higher score than $y$, you could steal a tiny amount of probability mass from $y$, reallocate it to $x$, and you'd get a higher score.

So, we can ask, what is $\frac{\partial }{\partial x}(\mu \mapsto \mu (f)-ϵ||\frac{d\mu }{d\nu }|{|}_q)$ for the optimal $\mu$? We know that it will end up being equal for every $x$ which is in the support of the optimal $\mu$. Well, we can write it as $$\frac{\partial }{\partial x}\left(\mu \right(f)-ϵ||\frac{d\mu }{d\nu }|{|}_q)$$ $$=\frac{\partial }{\partial x}(\int fd\mu -ϵ{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}})$$ $$=\frac{\partial }{\partial x}(\int fd\mu )-\frac{\partial }{\partial x}\left(ϵ{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}}\right)$$ $$=f\left(x\right)-ϵ\cdot \frac{1}{q}{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}-1}\frac{\partial }{\partial x}(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )$$ $$=f\left(x\right)-ϵ\cdot \frac{1}{q}{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}-1}\nu \left(x\right)\frac{\partial }{\partial x}\left({\left(\frac{d\mu }{d\nu }\right)}^q\right)$$ $$=f\left(x\right)-ϵ\cdot \frac{1}{q}{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}-1}\nu \left(x\right)\cdot \frac{1}{\nu (x{)}^q}\frac{\partial }{\partial x}(d\mu {)}^q$$ $$=f\left(x\right)-ϵ\cdot \frac{1}{q}{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}-1}\nu \left(x\right)\cdot \frac{1}{\nu (x{)}^q}\cdot q\cdot \mu (x{)}^{q-1}$$ And cancel $$=f\left(x\right)-ϵ{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}-1}{\left(\frac{d\mu }{d\nu }\right(x\left)\right)}^{q-1}$$ Now, since $ϵ{(\int {\left(\frac{d\mu }{d\nu }\right)}^{q}d\nu )}^{\frac{1}{q}-1}$ is the same regardless of which $x$ was picked, we can abbreviate it as $\alpha$, and write things as $$\frac{\partial }{\partial x}\left(\mu \right(f)-ϵ||\frac{d\mu }{d\nu }|{|}_q)=f\left(x\right)-\alpha {\left(\frac{d\mu }{d\nu }\right(x\left)\right)}^{q-1}$$ As previously explained, this quantity must be the same for all $x$ that are supported by the optimal $\mu$. In fact, this quantity can be called $b$. So, for every $x$ with support, we have that $$b=f\left(x\right)-\alpha {\left(\frac{d\mu }{d\nu }\right(x\left)\right)}^{q-1}$$ We can rearrange this $$\alpha {\left(\frac{d\mu }{d\nu }\right(x\left)\right)}^{q-1}=f\left(x\right)-b$$ $${\left(\frac{d\mu }{d\nu }\right(x\left)\right)}^{q-1}=\frac{f\left(x\right)-b}{\alpha }\left(f\right(x)-b)$$ $$\frac{d\mu }{d\nu }\left(x\right)={\left(\frac{f\left(x\right)-b}{\alpha }\right)}^{\frac{1}{q-1}}$$ And now we see that, since the left-hand side is always nonnegative, $f\left(x\right)-b$ must also be nonnegative too. And for any $x$ which fulfilled the above equation, it can be rearranged to show that this $x$ must have its partial derivative in the $x$ direction being the maximal value of $b$, as expected, and so $\mu$ would not be harmed by placing any probability mass on that $x$. So, without loss of generality, we can assume that $\mu$ is supported over all $x$ which fulfill the above equation, and make it into an equation that's valid for \emph{all} $x$ by going $$\frac{d\mu }{d\nu }\left(x\right)={\left(\frac{max\left(f\right(x)-b,0)}{\alpha }\right)}^{\frac{1}{q-1}}$$ Rearrange. $$\mu \left(x\right)=\nu \left(x\right)\cdot {\left(\frac{max\left(f\right(x)-b,0)}{\alpha }\right)}^{\frac{1}{q-1}}$$ Now, ${\left(\frac{1}{\alpha }\right)}^{\frac{1}{q-1}}$ is a constant, so call it $a$. And since it's valid over all $x$, we can rephrase it as $$\mu =a\cdot \nu \cdot max(f-b,0{)}^{\frac{1}{q-1}}$$ And now, since $\frac{1}{p}+\frac{1}{q}=1$, we can rearrange this into $q=\frac{p}{p-1}$, and so $$\frac{1}{q-1}=\frac{1}{\frac{p}{p-1}-\frac{p-1}{p-1}}=\frac{1}{\frac{1}{p-1}}=p-1$$ And so our equation rearranges into $$\mu =a\cdot \nu \cdot max(f-b,0{)}^{p-1}$$ As desired.

Theorem 3: Dynamic Consistency

For any environment $e$, finite history $h$, off-history policy ${\pi }_{\neg h}$, and infrafunctions $\text{U}$ and $\text{V}$, we have that} $$\text{U}(({\pi }_{\neg h}\bullet {\text{argmax}}_{{\pi }^{\ast }}(\text{U}|e,h,{\pi }_{\neg h}\left)\right({\pi }^{\ast }\cdot \left(e|h\right)\left)\right)\cdot e)\ge \text{U}(({\pi }_{\neg h}\bullet {\text{argmax}}_{{\pi }^{\ast }}\text{V}({\pi }^{\ast }\cdot \left(e|h\right)\left)\right)\cdot e)$$ \emph{Or, restating in words, selecting the after-h policy by argmaxing for $\text{U}|e,h,{\pi }_{\neg h}$ makes an overall policy that outscores the overall policy made by selecting the after-h policy to argmax for $\text{V}$.

Proof: $$\text{U}(({\pi }_{\neg h}\bullet {\text{argmax}}_{{\pi }^{\ast }}(\text{U}|e,h,{\pi }_{\neg h}\left)\right({\pi }^{\ast }\cdot \left(e|h\right)\left)\right)\cdot e)$$ Use ${\pi }^{\ast }$ to abbreviate the optimal policy for $\text{U}|e,h,{\pi }_{\neg h}$, and interacting with the environment $e|h$. $$=\text{U}\left(\right({\pi }_{\neg h}\bullet {\pi }^{\ast })\cdot e)$$ $$=\underset{U\in \hat{\text{U}}}{min}{E}_{({\pi }_{\neg h}\bullet {\pi }^{\ast })\cdot e}\left[U\right]$$ $$=\underset{U\in \hat{\text{U}}}{min}{E}_{({\pi }_{\neg h}\bullet {\pi }^{\ast })\cdot e}\left[{\text{1}}_{\neg h}U\right]+E_{({\pi }_{\neg h}\bullet {\pi }^{\ast })\cdot e}\left[{\text{1}}_{h}U\right]$$ $$=\underset{U\in \hat{\text{U}}}{min}{E}_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_{\neg h}U\right]+E_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_h\right]\cdot E_{{\pi }^{\ast }\cdot \left(e|h\right)}\left[U_{\downarrow h}\right]$$ Now, since ${\pi }^{\ast }$ is optimal for $\text{U}|e,h,{\pi }_{\neg h}$ and interacting with $e|h$, that means that for all other post-h policies ${\pi }^{\prime }$, we have that $$(\text{U}|e,h,{\pi }_{\neg h})({\pi }^{\ast }\cdot (e|h\left)\right)\ge (\text{U}|e,h,{\pi }_{\neg h})({\pi }^{\prime }\cdot (e|h\left)\right)$$ Unpacking the definition of the updated infrafunction, since everything in the set associated with $\text{U}|e,h,{\pi }_{\neg h}$ came from the set associated with $\text{U}$, this turns into $$\underset{U\in \hat{\text{U}}}{min}{E}_{{\pi }^{\ast }\cdot \left(e|h\right)}\left[E_{{\pi }_{\neg h}\cdot e}\right[{\text{1}}_h]\cdot U_{\downarrow h}+E_{{\pi }_{\neg h}\cdot e}[{\text{1}}_{\neg h}U\left]\right]\ge \underset{U\in \hat{\text{U}}}{min}{E}_{{\pi }^{\prime }\cdot \left(e|h\right)}\left[E_{{\pi }_{\neg h}\cdot e}\right[{\text{1}}_h]\cdot U_{\downarrow h}+E_{{\pi }_{\neg h}\cdot e}[{\text{1}}_{\neg h}U\left]\right]$$ Reshuffling some expectations, this turns into $$\underset{U\in \hat{\text{U}}}{min}{E}_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_{\neg h}U\right]+E_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_h\right]E_{{\pi }^{\ast }\cdot \left(e|h\right)}\left[U_{\downarrow h}\right]\ge \underset{U\in \hat{\text{U}}}{min}{E}_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_{\neg h}U\right]+E_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_h\right]E_{{\pi }^{\prime }\cdot \left(e|h\right)}\left[U_{\downarrow h}\right]$$ Let ${\pi }^{\prime }$ be the policy that optimizes $\text{V}({\pi }^{\prime }\cdot (e|h\left)\right)$. Now, we were previously at $$=\underset{U\in \hat{\text{U}}}{min}{E}_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_{\neg h}U\right]+E_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_h\right]\cdot E_{{\pi }^{\ast }\cdot \left(e|h\right)}\left[U_{\downarrow h}\right]$$ but using the above inequality, we can proceed to $$\ge \underset{U\in \hat{\text{U}}}{min}{E}_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_{\neg h}U\right]+E_{{\pi }_{\neg h}\cdot e}\left[{\text{1}}_h\right]\cdot E_{{\pi }^{\prime }\cdot \left(e|h\right)}\left[U_{\downarrow h}\right]$$ $$=\underset{U\in \hat{\text{U}}}{min}{E}_{({\pi }_{\neg h}\bullet {\pi }^{\prime })\cdot e}\left[{\text{1}}_{\neg h}U\right]+E_{({\pi }_{\neg h}\bullet {\pi }^{\prime })\cdot e}\left[{\text{1}}_{h}U\right]$$ $$=\underset{U\in \hat{\text{U}}}{min}{E}_{({\pi }_{\neg h}\bullet {\pi }^{\prime })\cdot e}\left[U\right]$$ $$=\text{U}\left(\right({\pi }_{\neg h}\bullet {\pi }^{\prime })\cdot e)$$ $$=\text{U}(({\pi }_{\neg h}\bullet {\text{argmax}}_{{\pi }^{\prime }}\text{V}({\pi }^{\prime }\cdot \left(e|h\right)\left)\right)\cdot e)$$ And we're done, we've shown our desired inequality $$\text{U}(({\pi }_{\neg h}\bullet {\text{argmax}}_{{\pi }^{\ast }}(\text{U}|e,h,{\pi }_{\neg h}\left)\right({\pi }^{\ast }\cdot \left(e|h\right)\left)\right)\cdot e)\ge \text{U}(({\pi }_{\neg h}\bullet {\text{argmax}}_{{\pi }^{\ast }}\text{V}({\pi }^{\ast }\cdot \left(e|h\right)\left)\right)\cdot e)$$ And the $\text{U}$, $\text{V}$, and everything else was arbitrary, so it's universally valid.

Proposition 2: $L_p$ Double Integral Inequality

If $f\ge 0$, let ${\oint }^{p}fd\mu$ be an abbreviation for ${(\int f^{p}d\mu )}^{\frac{1}{p}}$. Then for all $p\in [-\infty ,1]$, and $\mu :\Delta X$ and $\nu :\Delta Y$ and $f:X\times Y\to R^{\ge 0}$, we have that $$\int {\oint }^{p}f(x,y)d\nu d\mu \le {\oint }^p\int f(x,y)d\mu d\nu$$

Here's why. Define the function $g:Y\to R^{\ge 0}$ as $g\left(y\right)={(\int f(x,y\left)d\mu \right)}^{p-1}$. Reverse Holder's inequality, because $p\le 1$, says that, for all $x$, $$\int f(x,y)g\left(y\right)d\nu \ge {\oint }^{p}f(x,y)d\nu \cdot {\oint }^{q}g\left(y\right)d\nu$$ Where $\frac{1}{p}+\frac{1}{q}=1$. So, using that inequality, we can derive that $$\frac{\int f(x,y)g\left(y\right)d\nu }{{\oint }^{q}g\left(y\right)d\nu }\ge {\oint }^{p}f(x,y)d\nu$$ And so we derive that $$\int {\oint }^{p}f(x,y)d\nu d\mu \le \int \frac{\int f(x,y)g\left(y\right)d\nu }{{\oint }^{q}g\left(y\right)d\nu }d\mu$$ Pull the constant out, and group this into a double integral. $$={\left({\oint }^{q}g\right(y\left)d\nu \right)}^{-1}\cdot \int \int f(x,y)g\left(y\right)d\nu d\mu$$ Swap the order of double integration, and unpack what ${\oint }^q$ is. $$={\left({(\int g(y{)}^{q}d\nu )}^{\frac{1}{q}}\right)}^{-1}\cdot \int \int f(x,y)g\left(y\right)d\mu d\nu$$ Pull the constant $g\left(y\right)$ partway out of the inner integral, and also collapse the two powers on the left-hand side. $$={(\int g(y{)}^{q}d\nu )}^{\frac{-1}{q}}\cdot \int g\left(y\right)\int f(x,y)d\mu d\nu$$ Now, since $\frac{1}{q}+\frac{1}{p}=1$, solving for $q$, we get that it is equal to $\frac{p}{p-1}$. Similarly, $\frac{-1}{q}=\frac{1}{p}-1$. Make those substitutions. $$={(\int g(y{)}^{\frac{p}{p-1}}d\nu )}^{\frac{1}{p}-1}\cdot \int g\left(y\right)\int f(x,y)d\mu d\nu$$ Unpack what $g\left(y\right)$ is. $$={(\int {\left({(\int f(x,y\left)d\mu \right)}^{p-1}\right)}^{\frac{p}{p-1}}d\nu )}^{\frac{1}{p}-1}\cdot \int {(\int f(x,y\left)d\mu \right)}^{p-1}(\int f(x,y\left)d\mu \right)d\nu$$ Simplify $$={(\int {(\int f(x,y\left)d\mu \right)}^{p}d\nu )}^{\frac{1}{p}-1}\cdot \int {(\int f(x,y\left)d\mu \right)}^{p}d\nu$$ Cancel $$={(\int {(\int f(x,y\left)d\mu \right)}^{p}d\nu )}^{\frac{1}{p}}$$ Rewrite $$={\oint }^p\int f(x,y)d\mu d\nu$$ And we're done! We've shown that $$\int {\oint }^{p}f(x,y)d\nu d\mu \le {\oint }^p\int f(x,y)d\mu d\nu$$ For some values of $p$, like 0 or 1 or $-\infty$, these quantities will be ill-defined, but this can be handled by taking limits of the $p$ where this argument works.

Corollary 1: Lp-Averaging is Well-Defined

Given any distribution $\nu$ over a family of functions or infrafunctions, define the $L_p$-average of this family (for $p\in [-\infty ,1]$) as the function $$\mu \mapsto {\oint }^p{\text{F}}_i\left(\mu \right)d\nu$$ If all infrafunctions ${\text{F}}_i\left(\mu \right)$ are $\ge 0$, then the $L_p$-average will be an infrafunction as well.

Proof: The main thing we need to verify is concavity of the resulting function. So, fix some ${\mu }_1$ and ${\mu }_2$, and use $q$ as our mixing parameter. Then, $$q\left({\oint }^p{\text{F}}_{i}d\nu \right)\left({\mu }_1\right)+(1-q)\left({\oint }^p{\text{F}}_{i}d\nu \right)\left({\mu }_2\right)$$ $$=q{\oint }^p{\text{F}}_i\left({\mu }_1\right)d\nu +(1-q){\oint }^p{\text{F}}_i\left({\mu }_2\right)d\nu$$ Now, this can actually be interpreted as an ordinary integral outside of a p-integral. The outer integral is over the space of two points, and $f(1,\text{F})=\text{F}\left({\mu }_1\right)$ and $f(2,\text{F})=\text{F}\left({\mu }_2\right)$. So applying our inequality from the previous theorem, we get $$\le {\oint }^{p}q{\text{F}}_i\left({\mu }_1\right)+(1-q){\text{F}}_i\left({\mu }_2\right)d\nu$$ And then apply concavity of each $\text{F}$. $$\le {\oint }^p{\text{F}}_i(q{\mu }_1+(1-q\left){\mu }_2\right)d\nu$$ Concavity has been proved.

Theorem 4: Crappy Optimizer Theorem

For any selection process $s$ where $Q\left(s\right)$ fulfills the four properties, $\forall f:Q\left(s\right)\left(f\right)={max}_{\mu \in \Psi }\mu \left(f\right)$ will hold for some closed convex set of probability distributions $\Psi$. Conversely, the function $f\mapsto {max}_{\mu \in \Psi }\mu \left(f\right)$ for any closed convex set $\Psi$ will fulfill the four properties of an optimization process.

It's already a theorem that any function $\psi :(X\to R)\to R$ which fulfills the three properties of concavity, monotonicity, and $\psi (af+c)=a\psi \left(f\right)+c$, has a representation as minimizing over a closed convex set of probability distributions, and that minimizing over a closed convex set of probability distributions will produce a functional which fulfills those four properties. It's somewhere in Less Basic Inframeasure Theory. Well, actually, I proved some stuff about ultradistributions and all the proofs were the same just flipping concave to convex, and minimization to maximization, in an extremely straightforward way. And I proved that those three properties (but with convex flipped to concave) were equivalent to minimizing over a closed convex set of probability distributions, so the same result should hold.

Very similar arguments prove that any function which fulfills the three properties of convexity, monotonicity, and being able to pull multiplicative and additive constants out, has a representation as maximizing over a closed convex set of probability distributions $\Psi$, and vice-versa.

So, that just leaves proving the three defining properties of an ultradistribution from the four properties assumed of the function $Q\left(s\right)$, and vice-versa. As a recap, the four properties assumed were $$P1:\forall f,c\in R:Q\left(s\right)(f+c)=Q\left(s\right)\left(f\right)+c$$ $$P2:\forall f,a\ge 0:Q\left(s\right)\left(af\right)=aQ\left(s\right)\left(f\right)$$ $$P3:\forall f,g:Q\left(s\right)(f+g)\le Q\left(s\right)\left(f\right)+Q\left(s\right)\left(g\right)$$ $$P4:\forall f:f\le 0\to Q\left(s\right)\left(f\right)\le 0$$ And the four defining properties of ultradistributions are $$U1:\forall f,g,p\in [0,1]:\psi (pf+(1-p\left)g\right)\le p\psi \left(f\right)+(1-p)\psi \left(g\right)$$ $$U2:\forall f,g:f\le g\to \psi \left(f\right)\le \psi \left(g\right)$$ $$U3:\forall f,c\in R,a\ge 0:\psi (af+c)=a\psi \left(f\right)+c$$ Proof of U1 from P2 and P3: $$Q\left(s\right)(pf+(1-p\left)g\right)\le Q\left(s\right)\left(pf\right)+Q\left(s\right)\left(\right(1-p\left)g\right)=pQ\left(s\right)\left(f\right)+(1-p)Q\left(s\right)\left(g\right)$$ Proof of U2 from P3 and P4 and $f\le g$ $$Q\left(s\right)\left(f\right)=Q\left(s\right)\left(\right(f-g)+g)\le Q\left(s\right)(f-g)+Q\left(s\right)\left(g\right)\le Q\left(s\right)\left(g\right)$$ Proof of U3 from P1 and P2: $$Q\left(s\right)(af+c)=Q\left(s\right)\left(af\right)+c=aQ\left(s\right)\left(f\right)+c$$ Now for the reverse direction!

Proof of P1 from U3: $$\psi (f+c)=\psi \left(f\right)+c$$ Proof of P2 from U3: $$\psi \left(af\right)=a\psi \left(f\right)$$ Proof of P3 from U1 and U3: $$\psi (f+g)=\psi (p\frac{1}{p}f+(1-p\left)\frac{1}{1-p}g\right)\le p\psi \left(\frac{1}{p}f\right)+(1-p)\psi \left(\frac{1}{1-p}g\right)=\psi \left(f\right)+\psi \left(g\right)$$ Proof of P4 from U2 and U3 and $f\le 0$ $$\psi \left(f\right)\le \psi \left(0\right)=\psi (0\cdot 0)=0\cdot \psi \left(0\right)=0$$ And done!

Proposition 3:

The space of infrafunctions is a $\square$-algebra, with the function $fla{t}_{FX}:\square FX\to FX$ being defined as $\lambda \psi .\lambda \mu .\psi (\lambda \text{F}.\text{F}(\mu \left)\right)$.

We just need to show two commuting diagrams. For the square one, fix an arbitrary $\Psi :\square \square FX$ and $\mu \in \Delta X$. $$fla{t}_{FX}\left(fla{t}_{\square FX}\right(\Psi \left)\right)\left(\mu \right)$$ Unpack the outer layer of flattening. $$=fla{t}_{\square FX}\left(\Psi \right)(\lambda \text{F}.\text{F}(\mu \left)\right)$$ Unpack the next layer of flattening, via the usual way that flattening works for infradistributions. $$=\Psi (\lambda \psi .\psi (\lambda \text{F}.\text{F}\left(\mu \right)\left)\right)$$ Regroup this back up in a different way with how $fla{t}_{FX}$ works. $$=\Psi (\lambda \psi .fla{t}_{FX}(\psi \left)\right(\mu \left)\right)$$ Write this as the beta reduction of the more complicated term $$=\Psi (\lambda \psi .(\lambda \text{F}.\text{F}\left(\mu \right)\left)\right(fla{t}_{FX}\left(\psi \right)\left)\right)$$ Write this as a pushforward along an infrakernel. $$=fla{t}_{FX\ast }\left(\Psi \right)(\lambda \text{F}.\text{F}(\mu \left)\right)$$ Write this as a flattening. $$=flatFX\left(fla{t}_{FX\ast }\right(\Psi \left)\right)\left(\mu \right)$$ Now, since this holds for all $\mu$, that means that $$fla{t}_{FX}\left(fla{t}_{\square FX}\right(\Psi \left)\right)=fla{t}_{FX}\left(fla{t}_{FX\ast }\right(\Psi \left)\right)$$ And since this holds for all $\Psi$, this means that $$fla{t}_{FX}\circ fla{t}_{\square FX}=fla{t}_{FX}\circ fla{t}_{FX\ast }$$ This demonstrates the first commutative diagram of an algebra of a monad, the one that looks like a square. Now for the forward-and-back digram composing to identity.

We need that the usual embedding $e:FX\to \square FX$ given by $e\left(\text{F}\right)=\lambda g.g\left(\text{F}\right)$ where $g:FX\to R$, has $fla{t}_{FX}\circ e=i{d}_{FX}$. Let's compute it. Fix an arbitrary $\text{F}:FX$ and a $\mu :\Delta X$. Then $$fla{t}_{FX}\left(e\right(\text{F}\left)\right)\left(\mu \right)$$ $$=fla{t}_{FX}(\lambda g.g(\text{F}\left)\right)\left(\mu \right)$$ $$=(\lambda g.g(\text{F}\left)\right)(\lambda \text{G}.\text{G}(\mu \left)\right)$$ $$=(\lambda \text{G}.\text{G}(\mu \left)\right)\left(\text{F}\right)$$ $$=\text{F}\left(\mu \right)=i{d}_{FX}\left(\text{F}\right)\left(\mu \right)$$ And this holds for all $\mu$ and $\text{F}$, so composing flattening and the usual embedding produces the identity, which is the second property to declare something a $\square$-algebra.

Proposition 4:

All continuous infrakernels $k:X\to \square Y$ induce a function $FY\to FX$ via $\text{G}\mapsto (\mu \mapsto \text{G}(k_{\ast }\left(\mu \right))$

We've got two things to verify. Namely, concavity, and upper-semicontinuity, of $\lambda \mu .\text{G}\left(k_{\ast }\right(\mu \left)\right)$. Upper-semicontinuity is easy, because if ${\mu }_n$ converges to $\mu$, then $k_{\ast }\left({\mu }_n\right)$ converges to $k_{\ast }\left(\mu \right)$, and then upper-semicontinuity of $\text{G}$ takes over. For concavity, we have $$\text{G}\left(k_{\ast }\right(p{\mu }_1+(1-p){\mu }_2\left)\right)=\text{G}\left(p{k}_{\ast }\right({\mu }_1)+(1-p\left)k_{\ast }\right({\mu }_2\left)\right)\ge p\text{G}\left(k_{\ast }\right({\mu }_1\left)\right)+(1-p)\text{G}\left(k_{\ast }\right({\mu }_2\left)\right)$$ And it's proved.

1 comments

Comments sorted by top scores.