Infra-Miscellanea

post by Diffractor · 2022-04-22T02:09:07.306Z · LW · GW · 0 comments

Contents

  Result Summaries:
  Section 2: Infra-algebras
  Section 3: Empty Set Shenanigans
  Section 4: Independent Product
  Section 5: Cross-Entropy
  Section 6: Iterative fixpoints
  Section 7: The Disintegration Theorem
  Section 8: Environment-Forming Constraints
  Section 9: Inframeasure Topologies
  Section 10: Generalizing LF-duality
  Section 11: Faithful Acausal-to-Causal Translations
None
No comments

This post is a writeup of some miscellaneous results that don't cohere into a single big post, but might possibly be of interest.

Also, in mostly unrelated news, this stuff can be a bit tricky to learn for the first time. So, I was thinking of assembling an infra version of the fixpoint exercise sheet [AF · GW], to help cross the gap from "There's all these complicated posts, and it looks nifty-but-intimidating" to "I understand the basic concepts well enough to casually use them when applicable, and can work through most of the requisite math on my own". This particular realm of math is one where it seems pretty feasible to guide someone to reinvent large chunks of it on their own with sufficiently leading discussion, and recreating something yourself does wonders for being able to actually wield it elsewhere. So, if anyone wants to chip in with assembling the problem sheet, or testing it out by spending a day trying out various math problems, please send me a message.

Result Summaries:

1: Because the vector space of signed measures on $X$ and the vector space of continuous functions $X\to R$ are dual to each other, inframeasures are dual to infrafunctions! An infrafunction can be viewed as either a concave functional mapping a measure to an expectation value to expectation values, or as a set of a-functions. Compare this to how an inframeasure can be viewed as either a concave functional mapping a function to an expectation value, or as a set of a-measures. The theory of these sorts of things is highly incomplete at the moment.

2: Convex spaces are spaces with a distinguished function $\Delta X\to X$, which takes the average of a mixture of points. $R$ being a convex space (kinda) is why the notion of "average of a distribution" exists. So, we can ask "what sorts of space $X$ have a distinguished function $\square X\to X$?", to get the infra-analogue of the notion of "average". As it turns out, it's a perfect halfway point between probability theory, and lattice stuff/set theory. They're convex spaces that are also complete lattices, and the probabilistic structure must interact with the order structure in the appropriate way. Specifically, given a probability distribution over subsets, mixing the sets together and taking the infinimum should produce the same result as mixing the infinima of the sets together.

3: What is the space of inframeasures over the empty set? It's just fun working through this, in the same way as it's fun working out why minimizing over the empty set produces infinity.

4: Besides the semidirect product and the free product, another notion of product has shown up. In the specific case of crisp infradistributions, it's the closest match to the naive notion of the product of probability distributions, as it lets you factorize expectations in the same way as products of probability distributions do.

5: The notion of cross-entropy of crisp infradistributions is defined, rounding out the trio of "entropy, cross-entropy, KL-divergence", where we previously had two of the three. An equality in the probability-theory case (entropy plus KL-divergence is cross-entropy) is shown to be an inequality here. Cross-entropy has a nice intuitive interpretation.

6: There's a function $fix:[X\to \square X]\to \square X$ (where $X$ is a compact space) that gets you the Kleene fixpoint theorem (from computer science), the Banach fixpoint theorem, and that one theorem about Markov chains having a stationary distribution.

7: A classic result of probability theory is the disintegration theorem, which roughly states that given a probability distribution $\nu :\Delta (X\times Y)$, it can always be written as being produced by a probability distribution $\mu :\Delta X$, and a Markov kernel $k:X\to \Delta Y$ giving you the conditional probabilities. This is the theorem that secretly underlies the ability to condition a distribution nearly any event or variable you want. This fails for infradistributions, but fortunately, given any crisp infradistribution $\varphi$, there's a canonical choice of nearby infradistribution that is disintegrable into an infradistribution $\psi :\square X$, and an infrakernel $K:X\to \square Y$. So you can kinda make conditional infradistributions.

8: Consider the following computational problem. You've got some value function $V:E\times [0,1]\to [0,1]$ ($E$ is the space of environments), which describes how much you care about getting a particular utility in a particular environment, and you're trying to do

$$argma{x}_{\pi }\underset{e}{min}V(e,E_{e\cdot \pi }[U\left]\right)$$

Ie, pick the policy $\pi$ which maximizes the worst-case value of (your environment,your utility). As it turns out, subject to some mild conditions on the derivatives of the value function, any problem of this form can be rephrased as

$$argma{x}_{\pi }(\Theta \cdot \pi )\left(U\right)$$

Namely, maximizing expected utility w.r.t some causal belief function $\Theta$. This allows recasting several other possible value functions as just the problem of "do well in an infraenvironment".

9: The Objectively Correct topolog(ies) on spaces of inframeasures has been found. It was generated by a minor variation on the attempt made in "Less Basic Inframeasure Theory", and so obsoletes the relevant section. The topology section wound up getting too big and got broken out into its own post [AF · GW].

10: It doesn't matter whether you're viewing inframeasures as a concave function from functions to their expectation values, or viewing them as a set of a-measures. This is LF-duality, aka the Fundamental Theorem of inframeasures. Sadly, the proof of it didn't generalize over to more abstract cases like what shows up in domain theory. Until now!

11: For belief functions, it's proved which sorts of them can be translated into causal belief functions without affecting the utilities particularly much. In other words, this result tells you a decision-theoretic fairness condition on which sorts of problems can be viewed as causal if you try (in an expanded sense which manages to include XOR blackmail, Newcomb, and Counterfactual Mugging). Said fairness condition comes out to be something along the lines of "if what happens now depends on what you'd do in alternate situations, the magnitude of that effect must be proportional to the time-discounted probability of actually getting into those alternate situations"

Section 1: Infrafunctions

 $C_B\left(X\right)$ is the space of bounded continuous functions $X\to R$, and $M^{\pm }\left(X\right)$ is the space of finite signed measures on $X$. $X$ is just some space. Compact metric spaces are the best, though it's possible to go beyond that.

The fundamental theorem of inframeasures aka LF-duality, says that there's a bijection between closed, convex, upper-complete subsets of $M^{\pm }\left(X\right)\times R$, and concave functions $C_B\left(X\right)\to R$. This is nice because it lets you transition back and forth between an "analytic" way of viewing inframeasures (the concave functionals), and a "geometric" way (as a set of measure,number pairs).

Just embellish your theorem with a bunch of fiddly details about what sort of space $X$ is and what additional conditions to impose on the subsets and concave functions, and you're done.

And the core piece that makes the fundamental theorem tick is "for every concave function, the set of hyperplanes above it is sufficient data to recover the concave function", which isn't especially sensitive to measures vs functions, it's a general fact of linear algebra/functional analysis. The only extra step that's specific to inframeasures is the interpretation of those hyperplanes as measure, number pairs.

But note that $C_B\left(X\right)$ (the space of bounded continuous functions $X\to R$), and $M^{\pm }\left(X\right)$ (the space of finite signed measures on $X$) are dual to each other. Continuous linear functionals $C_B\left(X\right)\to R$ correspond to signed measures, and continuous linear functionals $M^{\pm }\left(X\right)\to R$ correspond to bounded continuous functions, it's a completely symmetric situation. So what if we tried doing things the other way around?

Inframeasures are what you get when you start with concave functions $C_B\left(X\right)\to R$, represent them as a set of affine functions/hyperplanes, and interpret those affine functions as measure,number pairs. But what about when you start with concave functions $M^{\pm }\left(X\right)\to R$, represent them as a set of affine functions/hyperplanes, and interpret those affine functions as function,number pairs? Well, that's an infrafunction.

An infrafunction $F$ is either a concave function of type $M^{\pm }\left(X\right)\to R$, or a set of function/number pairs $(f,b)$, and we have

$$F\left(m\right)=\underset{(f,b)\in F}{min}m\left(f\right)+b$$

Just as inframeasures respond to functions with the worst-case measure, infrafunctions respond to measures with the worst-case function.

When would these be useful? Well, they seem to capture every case where randomizing your action is better than picking what to do deterministically. If randomizing your action is better than deterministic choice, that means that the function $\Delta A\to [0,1]$ yielding the value of various distributions over actions is a concave function. And so, LF-duality will turn that concave function over distributions into a set of functions $A\to [0,1]$ that you're (implicitly) assuming the worst-case of. This formalizes the thing Eliezer was talking about where randomization is only helpful when you're trying to do worst-case optimization against an adversary instead of average-case optimization.

Most of the proofs for this are utterly routine. There's probably lots of interesting stuff to show about infrafunctions but I want to get this post out in a timely manner, so instead I'll just observe that infrafunction theory is a pretty wide-open place to look for nifty results.

Section 2: Infra-algebras

Note: In this section, and for the proofs, the domain-theory ordering on inframeasures is used, where infinimum corresponds to union.

As motivated in the results preamble, which spaces $X$ have a distinguished function $\square X\to X$? This would be the infra-version of "average". Well, the space of infradistributions contains the space of probability distributions within it. So, any space like that induces a function $\Delta X\to X$. Thus, whatever sort of space we're looking for, it should at least be a convex space, with a notion of mixture of points.

Well, if $X$ is a convex space, is that enough to get a function $\square X\to X$? Not yet. We do know where the probability distributions should get mapped to, we've got a function $av{g}_X:\Delta X\to X$. But, for a crisp infradistribution (ie, set of probability distributions) $\psi$, where should that get mapped to? Well, $\psi$ is associated with a set of probability distributions $\Psi$, so $\psi$ should probably get mapped to a point that has something to do with the set $av{g}_X\left(\Psi \right)$, the set you get by pushing $\Psi$ through the "take the average" function. The set $\Psi$ is compact, so the set $av{g}_X\left(\Psi \right)$ should be compact as well.

Net question: Given a nonempty compact subset of $X$, is there some distinguished point of $X$ associated with it? Well, that's basically like asking for a space $X$ with a distinguished function $KX\to X$, mapping nonempty compact sets ($KX$ is the space of nonempty compact subsets of $X$) to points. As it turns out, (if the entire space $X$ is compact), a space like that is a poset with all nonempty infinima existing. It's basically a complete lattice except it may be missing the top point. Just map your compact set to the infinimum.

So, the function we're after (let's call it $fla{t}_X$ for "flatten") should be defined something like

$$fla{t}_X\left(\psi \right):=\wedge \left\{av{g}_X\right(\mu )|\mu \in \Psi \}$$

Ie, convert $\psi$ into a set of probability distributions, take the average of all of those distributions to get a set of points in $X$, and take the inf of that set.

This, at minimum, requires that $X$ be a convex space (so you know where to map the probability distributions to), and a poset with all nonempty infinima (so you know where to map sets of probability distributions to). But actually, this isn't enough by itself, the mixture structure and the order structure must interact in a certain way, as we'll get to later.

But wait, there's lots of sorts of infradistributions, and we've just dealt with the crisp infradistributions (sets of probability distributions) so far! Yes. It's important to note that there's actually lots of inframeasure monads (space of crisp infradimeasures, space of cohomogenous inframeasures, etc...), producing different spaces of inframeasures. $\square X$ is ambiguous notation that's bad here, because all the different possible choices of "space of inframeasures" produce a slightly different batch of properties a space $X$ needs for there to be a special function $\square X\to X$.

It's not too hard to work out the details for other sorts of inframeasures, but my preferred choice is the inframeasures of type $(X\to [0,1\left]\right)\to [0,1]$, which are made of sets of a-measures $(\lambda \mu ,b)$ where $\lambda +b\le 1$, which heretofore haven't been named.

The reason why is because any a-measure of that form can be expressed as an element of $\Delta (X+2)$. Basically, the measure component $\lambda \mu$ tells you how probability is distributed on the space $X$, the $b$ term is the probability of a distinguished "utility" point, and $1-\lambda -b$ is the probability of a distinguished "no utility" point.

So, if we can just figure out where "pure utility" and "pure lack of utility" should go, then we can go "by convexity, we know where all the a-measures should get mapped to", and then map an inframeasure to the inf of the set it induces, like usual.

The answer is that there should be a top point of the space $X$ (we already know there's a bottom point because of all nonempty infinima existing), and "pure utility" gets mapped to the top point, and "pure lack of utility" goes to the bottom point.

And so, we're about ready to define the necessary-and-sufficient conditions for a compact metric space $X$ to have a distinguished function $\square X\to X$. Where $\square X$ is the space of inframeasures on $X$ generated by sets of a-measures $(\lambda \mu ,b)$ with $\lambda +b\le 1$.

1: The space $X$ is a $\Delta$-algebra, ie there's a distinguished continuous function $av{g}_X:\Delta X\to X$.

2: The space $X$ is a $K$-algebra, ie there's a distinguished continuous function ${\wedge }_X:KX\to X$. In particular, this induces an ordering on $X$ where $x\le y$ if ${\wedge }_X\{x,y\}=x$.

3: Under the induced ordering, there is a top point, ${\top }_X$.

4: The ${\wedge }_X$ and $av{g}_X$ functions interact as follows. Given any $\mu :\Delta KX$, a probability distribution over compact sets, we have

$${\wedge }_X\overline{\left\{av{g}_X\right(k_{\ast }\left(\mu \right))|k:KX\to X\text{is measurable selection}\}}=av{g}_X\left({\wedge }_{X\ast }\right(\mu \left)\right)$$

Condition 4 is the key one, and quite mystifying at first glance. The key insight is that it's just implementing mixture of sets. If you've got two sets, $C$ and $D$, what would the set $pC+(1-p)D$ be? Well, you take all possible ways of picking a point from $C$ and a point from $D$, and for each way of doing that, you average the two points together, and this gets you the set $\{pc+(1-p)d|c\in C,d\in D\}$, and that's the obvious way to mix two sets together. If we generalize beyond this to any probability distribution over sets, you'd take all possible (measurable) ways of picking a point from each set (that'd be the function $k$), $k_{\ast }\left(\mu \right)$ would be the resulting distribution over points, you average them together, and that gets you the mixture set. This whole mess is just implementing averaging sets together, we could write that whole process as $av{g}_{KX}\left(\mu \right)$ if we wanted.

This would turn the mysterious condition 4 into

$${\wedge }_X\left(av{g}_{KX}\right(\mu \left)\right)=av{g}_X\left({\wedge }_{X\ast }\right(\mu \left)\right)$$

Which is just a commutative diagram. It's saying that going $\Delta KX\to KX\to X$ (the left-hand path) and $\Delta KX\to \Delta X\to X$ (the right-hand path) are the same function. Intuitively, if you have a batch of sets, it doesn't matter whether you average them together first, and then take the infinimum of the mixture set, or whether you take the infinimum of all of the sets first, and then mix the infinima together.

And so, in informal slogan form, the conditions for a space $X$ to have a distinguished function $\square X\to X$ are:

1: You can mix points together.

2,3: The space is a complete lattice.

4: Mixing sets together and taking the inf of the mixture set is the same as taking the infs of the various sets and mixing those together.

Some minor differences show up when you adjust the sorts of spaces you're dealing with, or the sorts of inframeasures you're considering, but this is the basics.

Theorem 1: If $X$ is a compact metrizable space, then the four conditions above are necessary and sufficient for $X$ to be an algebra of the $\square$ monad.

"algebra of the $\square$ monad" is the formal category-theory way of saying "there's a distinguished function $\square X\to X$". It means that there's a continuous function $fla{t}_X:\square X\to X$ (which we explicitly gave earlier! That's the unique function that works) s.t. $fla{t}_X\circ fla{t}_{X\ast }=fla{t}_X\circ fla{t}_{\square X}$ (both paths go $\square \square X\to \square X\to X$), and $fla{t}_X\circ e_X=i{d}_X$ (where $e_X:X\to \square X$ is the unit of the monad, ie, the function mapping a point to the dirac-delta distribution on that point). Also, $\square$ in this case is the monad mapping the space $X$ to the space of inframeasures $C(X,[0,1\left]\right)\to [0,1]$ generated by a set of a-measures $(\lambda \mu ,b)$ s.t. $\lambda +b\le 1$.

The theorem was way harder to prove than I thought. It requires expanding things into a 4x4 grid of commutative squares, requiring seven different lemmas to eventually turn one path into the other, and that was for only one direction of the proof.

As it turns out, the category of infra-algebras and the structure-preserving maps between them (affine functions that preserve infinima, top, and bottom) is somewhat interesting. If you're an ncatlab fan, it's the Eilenberg-Moore category of the inframeasure monad.

The product in it is the ordinary Cartesian product. Coproduct is a hideous complicated mess but it exists, and as it turns out, the coproduct of $\square X$ and $\square Y$ is $\square (X+Y)$. The category *might* be monoidal closed, I don't know. For the specific case of infradistributions, the monoidal product of $\square X$ and $\square Y$ should be $\square (X\times Y)$, but generalizing that construction to all convex complete lattices is pretty hard and I haven't done it yet. And the internal hom of $\square X$ and $\square Y$ should be the space $[X\to \square Y]$ of all lower-semicontinuous infrakernels. But again, I don't know how to generalize that construction to all convex lattices.

Section 3: Empty Set Shenanigans

What is $\square \varnothing$? After all, $\varnothing$ is vacuously a compact metric space. Well, it depends on what $\square$ is. If $\square$ is the space of crisp infradistributions, then $\square \varnothing =\varnothing$. Well, let's say $\square$ is the space of all $[0,1]$-inframeasures that can be generated by sets of a-measures $(\lambda \mu ,b)$, with $\lambda +b\le 1$, and work it out (since I like that one).

A $[0,1]$-inframeasure is a concave function of type $C(X,[0,1\left]\right)\to [0,1]$, fulfilling some extra properties. If $X$ is the empty set, then our elements would be the inhabitants of $C(\varnothing ,[0,1\left]\right)\to [0,1]$ (fulfilling some extra properties). Now, there's only one function from the empty set to anything, the empty function, which is vacuously continuous. So, the inframeasures would be the inhabitants of $1\to [0,1]$, the various constant functions. Or, expressing it another way, just the space $[0,1]$. These functionals are all vacuously concave, continuous, and all the rest.

So, we have $\square \varnothing =[0,1]$. Remember, an a-measure is $(\lambda \mu ,b)$ where $b,\lambda$ are nonzero numbers, and $\mu$ is a probability distribution. There are no probability distributions over the empty set, so all that's left is that $+b$ constant term.

Now, if $f_{\varnothing ,X}:\varnothing \to X$ is the empty function, then what is its pushforward? What's $f_{\varnothing ,X\ast }:[0,1]\to \square X$? Well, if $a$ is a constant, and $g$ is some function $X\to [0,1]$, then we have

$$f_{\varnothing ,X\ast }\left(a\right)\left(g\right)=a(g\circ f_{\varnothing ,X})=a\left(f_{\varnothing ,[0,1]}\right)=a$$

So, the pushforward along the empty function is just the function mapping the constant $a$ to the constant infradistribution $c_a$ (which returns the value $a$ no matter which function is fed in).

Section 4: Independent Product

To start off with recapping the two existing notions of product...

The first notion, the semidirect product, was defined as follows. If $\psi :\square X$ and $\varphi :\square Y$, then $\psi ⋉\varphi :\square (X\times Y)$ is defined as

$$(\psi ⋉\varphi )\left(f\right):=\psi (\lambda x.\varphi (\lambda y.f(x,y)\left)\right)$$

This is an asymmetric notion, and the notation reflects this. $\psi ⋉\varphi \ne \varphi ⋉\psi$. For the special case of crisp infradistributions, you could think of $\psi ⋉\varphi$ as containing all the distributions whose marginal distribution on $X$ lies in $\Psi$, and whose conditional distributions on $Y$ are all selected from $\Phi$, regardless of the $x$. If we think of $\Psi$ and $\Phi$ as being sets of available strategies for a player 1 and player 2 respectively, then $\psi ⋉\varphi$ would be the set of probability distributions over results that are possible when player 2 is allowed to look at player 1's result, but player 2's set of available choices doesn't vary as player 1's result varies.

The second notion, free product, is defined as follows. If $\psi :\square X$ and $\varphi :\square Y$, then $\psi \otimes \varphi :\square (X\times Y)$ is defined as

$$\psi \otimes \varphi :=p{r}_X^{\ast }\left(\psi \right)\cap p{r}_Y^{\ast }\left(\varphi \right)$$

Note that $p{r}_X^{\ast }$ is the pullback of projection. It's like the preimage of projection, going $\square X\to \square (X\times Y)$. So, you just take the intersection of the two sets. For the special case of crisp infradistributions, $\psi \otimes \varphi$ consists of all the distributions whose marginal distribution on $X$ lies in $\Psi$, and whose marginal distribution on $Y$ lies in $\Phi$. Note that taking the free product of two probability distributions produces a set of many probability distributions.

But wait... Restricting to crisp infradistributions (sets of probability distributions)... If free product is "the set of probability distributions where their marginals must be thus-and-such", and semidirect product is "the set of probability distributions where their marginal along this coordinate is thus-and-such, and the conditional distributions along the other coordinate are thus-and-such"... That points to a missing notion of product, where the conditionals along both coordinates.

It'd be something like... $\psi \times \varphi$ is the set of all probability distributions $\mu$ where, regardless of $x$ and $y$, $\mu |x\in \Phi$, and $\mu |y\in \Psi$.

Making it more formal, the independent product $\psi \times \varphi :\square (X\times Y)$ is given by

$$\psi \times \varphi :=({\top }_X⋉\varphi )\cap ({\top }_Y⋉\psi )$$

Where ${\top }_X$ is the infradistribution $\lambda f.{min}_{x\in X}f\left(x\right)$, the infradistribution corresponding to total uncertainty over $X$. Similar for ${\top }_Y$. Technically, that equation should have a function that flips the coordinates of that second thingy from $Y\times X$ to $X\times Y$, but whatever, it's pretty understandable anyways.

Does this have any nice properties? Well, it's a bit tricky to tell in general, but for the restricted special case of crisp infradistributions (sets of probability distributions), we have the following key property which also characterizes products of distributions in ordinary probability theory. And it plays a big role in evaluating expectations of factorizable functions, because you can find expectations of those functions by just decomposing it into smaller parts and multiplying them together.

Theorem 2: If $f:X\to R$, and $g:Y\to R$ (or $[0,1]$ as the case may be), and $\psi ,\varphi$ are crisp infradistributions, then

$$(\psi \times \varphi )(f\cdot g)=\psi \left(f\right)\cdot \varphi \left(g\right)$$

Also, in the probabilistic case, we have that the entropy of a product of distributions is the sum of their individual entropies. The same thing holds here, for the generalization of entropy to sets of probability distributions.

Theorem 3: If $\psi ,\varphi$ are crisp infradistributions, then $H(\psi \times \varphi )=H\left(\psi \right)+H\left(\varphi \right)$.

Section 5: Cross-Entropy

The definition of cross-entropy, $H(\psi ,\varphi )$, when $\psi ,\varphi$ are sets of probability distributions, is

$$H(\psi ,\varphi ):=\underset{\nu \in \Phi }{min}\underset{\mu \in \Psi }{max}H(\mu ,\nu )$$

The interpretation of this is that the cross-entropy of distributions, $H(\mu ,\nu )$, is "how many bits does it take on average to communicate what happened when reality is drawing from the distribution $\mu$, and you're using a communication scheme optimized for the distribution $\nu$". And so, if there's a set of possible things that reality could be ($\psi$), and a set of possible codes you could use ($\varphi$), and you knew you were in a worst-case scenario, you'd use an encoding from $\varphi$ that achieves fairly good efficiency over all the possible distributions in $\psi$ that reality could be selecting from. And, we're assuming reality is being mean and trying to maximize the communication cost. This whole paragraph abbreviates as ${min}_{\nu \in \Phi }{max}_{\mu \in \Psi }H(\mu ,\nu )$.

An interesting thing, however, is that this makes the usual "cross entropy equals entropy plus KL-divergence" equality into an inequality. This is because entropy, in this setting, is

$$H\left(\psi \right)=\underset{\mu \in \Psi }{max}H\left(\mu \right)$$

This is actually a theorem. The original definition of entropy was way more complex. And also, KL-divergence was previously defined as

$$D_{KL}\left(\psi |\varphi \right):=\underset{\nu \in \Phi }{min}\underset{\mu \in \Psi }{max}{D}_{KL}\left(\mu |\nu \right)$$

So, we get

$$H(\psi ,\varphi )=\underset{\nu \in \Phi }{min}\underset{\mu \in \Psi }{max}H(\mu ,\nu )=\underset{\nu \in \Phi }{min}\underset{\mu \in \Psi }{max}\left(H\right(\mu )+D_{KL}(\mu |\nu \left)\right)$$

$\le {min}_{\nu \in \Phi }\left({max}_{\mu \in \Psi }H\right(\mu )+{max}_{\mu \in \Psi }{D}_{KL}(\mu |\nu \left)\right)$

$={max}_{\mu \in \Psi }H\left(\mu \right)+{min}_{\nu \in \Phi }{max}_{\mu \in \Psi }{D}_{KL}\left(\mu |\nu \right)=H\left(\psi \right)+D_{KL}\left(\psi |\varphi \right)$

And so, we have

$$H(\psi ,\varphi )\le H\left(\psi \right)+D_{KL}\left(\psi |\varphi \right)$$

The cross-entropy/entropy/KL-divergence inequality, instead of equality.

 

Section 6: Iterative fixpoints

There's a function $fix:[X\to \square X]\to \square X$, where, if $K:[X\to \square X]$, then $fix\left(K\right)$ is the limit of ${\top }_X,K_{\ast }\left({\top }_X\right),K_{\ast }\left(K_{\ast }\right({\top }_X\left)\right)..$.

This may look very familiar, and it is! It's just a special case of Kleene's fixpoint theorem! Kleene's fixpoint theorem says that if you've got a poset where all chains have suprema, and there's a bottom point, and your function $f:X\to X$ is monotone and preserves suprema, you can make the chain $\perp ,f\left(\perp \right),f\left(f\right(\perp \left)\right),f\left(f\right(f\left(\perp \right)\left)\right)..$ and the supremum of that chain will be the least fixpoint of the function $f$.

In our particular case, given some infrakernel $K:X\to \square X$, the pushforward through that infrakernel, $K_{\ast }$, is a function of type $\square X\to \square X$. Since $\square X$ has a bottom (under the domain theory ordering, which is reversed from the usual ordering. And this is why we're using ${\top }_X$, because that's actually bottom under the domain theory ordering), and $\square X$ has suprema of chains (intersection), we can just throw Kleene's fixpoint theorem at this to show that it's well-defined.

The cool thing about this is that it manages to unify Kleene's fixpoint theorem, the Banach fixpoint theorem, stationary distributions on Markov chains, and more.

We can't expect fix to be continuous in the usual sense. As an example, let the space $X$ be the space $[0,1{]}^2$, the unit square. The sequence of functions $K_n:X\to X$ (extend it to a function $X\to \square X$ in the obvious way) we feed it are defined as

$$K_n(x,y)=x+\frac{1}{n}(0.5-x),y+\frac{1}{n}(0.5-y)$$

Basically, $K_n$ maps points closer to the center, though the rate at which it gets closer slows down as $n$ increases. Now, for all finite $n$, $fix\left(K_n\right)={\delta }_{0.5,0.5}$ (the one fixpoint is the center of the square, since everything else moves towards that.) However, the limit of the $K_n$ is just the identity function, and then pushforward through identity is identity, so we have $fix\left(K\right)={\top }_{[0,1{]}^2}$. This is a clear example where there's a sudden change in the least fixpoint as the function changes. The winds blowing points towards the center get weaker and weaker until they cease at the limit, and then the fixpoint suddenly goes from a single point to the entire space.

However, we can at least hope for Scott-continuity, a weakening of ordinary continuity that's closely tied to lower-semicontinuity, and domain theory. This requires that $fix$ is monotone and preserves suprema of chains, and this actually does hold.

Theorem 4: fix is Scott-continuous.

So, what sort of results does this produce? What if $K$ is just a function $X\to X$? Well then, $fix\left(K\right)$ is ${\top }_{{\bigcap }_n{K}^n\left(X\right)}$. Ie, take the entire space, shove it through $K$ over and over and over and over, and eventually your set stabilizes to something where $K$ is a bijection on it.

For places where you'd normally apply the Banach fixpoint theorem, that limiting set will shrink to a point, so applying $fix$ to a contractive function will produce a single point/the dirac-delta distribution on that point.

If $K$ is a Markov chain, mapping inputs to probability distributions over outputs, and it has a single stationary distribution, then $fix\left(K\right)$ will give you exactly that stationary distribution.

If you're in a domain-theory setting, and you've got a function $K:X\to X$, fix will just give you the least fixpoint of the function, as expected.

Section 7: The Disintegration Theorem

So, the original formulation of the Disintegration Theorem, in the probabilistic case, says that given any probability distribution on $X\times Y$, it's possible to decompose it uniquely into a distribution on $X$, and a conditional probability function $X\to \Delta Y$ which is unique almost everywhere.

So, for crisp infradistributions (sets of probability distributions), we might reasonably ask whether a similar thing holds, whether they decompose into a crisp infradistribution on $X$ and an infrakernel $X\to \square Y$.

The answer is, kinda. It certainly doesn't hold in general, but given any crisp infradistribution, there's always a smallest superset of it that does disintegrate like that. Here's how it's constructed.

To make the infradistribution on the $X$ coordinate (given some $\varphi :\square (X\times Y)$ that we're trying to decompose into $\psi :\square X$ and $K:X\to \square Y$), it's given by $\psi :=p{r}_{X\ast }\left(\varphi \right)$. Just project it onto the $X$ coordinate, as expected.

As for constructing the $K$, that will be more difficult to express. First, the definition of enclosing sets, for $\mu :\Delta (X\times Y)$.

A closed set $C\subseteq X\times \Delta Y$ is $\mu$-enclosing if, for $p{r}_{X\ast }\left(\mu \right)$-almost all x, $(x,\mu |x)\in C$.

Stated informally, an enclosing set gives you a set of available conditional probability distributions for each $x$, and the conditional probabilities of $\mu$ have to be picked from that set. And there should be a weak sort of continuity where if you zoom in far enough on any particular $x$ value, the set of available options for conditional probabilities for $x$ should be approximately as-big-or-bigger than the set of options available in its immediate neighborhood.

The definition of a $\mu$-enclosing set is robust against precisely what choice of conditional probabilities we have, because by the disintegration theorem, $\mu |x$ is unique for $p{r}_{X\ast }\left(\mu \right)$-almost-all x, so altering the conditional probabilities only disrupts a set of measure zero, and so can only ensure that a measure-zero set of $x$ have $(x,\mu |x)$ go outside of $C$.

Now that that's defined, given a crisp infradistribution $\varphi$, a closed set $C\subseteq X\times \Delta Y$ is $\varphi$-enclosing when it's $\mu$-enclosing for all $\mu \in \Phi$.

Or, in other words, the set of available conditional distributions for each $x$ has to be consistent with the conditional distributions of all the probability distributions in your set $\Phi$.

Let $C_{\varphi }\subseteq X\times \Delta Y$ be defined as ${\bigcap }_{C:C\text{is}\varphi \text{-enclosing}}C$

Basically, this is the smallest allowable set of conditional distributions for each $x$ where all the probability distributions in your set $\Phi$ are like "yeah, this set is big enough to have my conditional distributions in it", and that also fulfills our closed-graph continuity-like condition.

And now can finally define our conditional infradistribution! $K\left(x\right):=C_{\varphi }\left(x\right)$, where $C_{\varphi }\subseteq X\times \Delta Y$. We're implicitly converting the closed subset of $X\times \Delta Y$ to a closed subset of $\Delta Y$, by picking an x, and then using the usual translation from a set of probability distributions to an infradistribution.

Theorem 5: $C_{\varphi }$ is a lower-semicontinuous infrakernel, and $p{r}_{X\ast }\left(\varphi \right)⋉C_{\varphi }$ is the smallest disintegrable superset of $\varphi$.

Section 8: Environment-Forming Constraints

Credit to Vanessa for this idea.

We might want to have worst-case desiderata of the form "you must do this well in these environments". This can be expressed as a zero-sum game where you're trying to find a policy where, regardless of environment, a value function depending on the environment and your expected utility, exceeds a particular value. (You can have the value function automatically score well for environments you want to ignore, since yu're optimizing the worst-case.)

Ie, you're doing

$${\text{argmax}}_{\pi }\underset{e}{min}V(e,E_{e\cdot \pi }[U\left]\right)$$

Where $V:E\times [0,1]\to [0,1]$ ($E$ is the space of environments) is the value function. And $e\cdot \pi$ is the distribution over histories from policy $\pi$ interacting with environment $e$, and $U$ is expected utility. Increased expected utility should always be good, so we demand that $V$ is monotone in its second argument.

As it turns out, any constraint of this form (subject to some conditions on the first and second derivatives) can be reexpressed as just trying to do well vs one particular causal law/infraenvironment/set of a-environments/causal belief function/damn we really need to sort out this terminology, don't we.

Theorem 6: Given any value function $V:E\times [0,1]\to [0,1]$ (where $E$ is the space of environments) which is monotone in the second argument, and has first derivatives bounded above 0 and second derivatives bounded below infinity, there is a causal law (set of infraenvironments) $\Theta$ s.t

$$\underset{e}{min}V(e,E_{e\cdot \pi }[U\left]\right)>\underset{e}{min}V(e,E_{e\cdot {\pi }^{\prime }}[U\left]\right)$$

occurs iff

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

Regardless of $\pi ,{\pi }^{\prime }$, and utility function $U$.

As it turns out, if $\lambda x.V(e,x)$ is concave for all $e$, you can translate it very directly to a causal law. If it's not concave, you might get some nonlinear scaling of how the various policies do relative to each other, but the ordering of how well various policies do is unchanged. Concavity is very important here, and almost all of the difficulty with proving this theorem is concentrated in figuring out how to build a monotone function $g:[0,1]\to [0,1]$ (the nonlinear rescaling) s.t. $g\circ (\lambda x.V(e,x\left)\right)$ is concave for every choice of environment $e$.

Section 9: Inframeasure Topologies

This section entirely obsoletes section 6 in Less Basic Inframeasure Theory, and propositions 41 through 50. I mean, the theorems are correct, but they're not about the Right Thing.

But it was too long, so I had to break it out into its own post [AF · GW]. Suffice to say, there's two "objectively correct" topologies on inframeasures motivated purely by continuity considerations. And the continuity considerations naturally spit out all the complicated compact-set requirements for Polish spaces, for free. There's four highly distinct and equivalent ways to view inframeasure convergence, and all the complicated conditions on when an infrakernel is "well-behaved" can be obsoleted in one strike with "it's a continuous function $X\to \square Y$ when you give $\square Y$ the objectively correct topology".

Also, some of the results like LF-duality for Polish spaces were actually subtly wrong. The flaw was that $C_B\left(X\right)$, the space of bounded continuous functions $X\to R$, actually should have been equipped with a much more unusual and obscure topology than I originally thought it had. But don't worry, everything got repaired to the correct form.

Section 10: Generalizing LF-duality

So, if there's a Fundamental Theorem of Inframeasures, it'd definitely be LF-duality, the theorem about how it's equally valid to look at inframeasures as concave functions fulfilling certain properties, or as sets of a-measures fulfilling certain properties. It's equally valid to look at a concave function or the set of hyperplanes above it.

Sadly, if you dig into the mathematical guts of how this result is proven, it doesn't generalize to the case of domain theory. Until now, it's been impossible to take an inframeasure defined on a domain, and have an assurance that the "set of a-measures" view is faithful to the originally defined function.

But it got solved anyways. Thank "Hahn-Banch Type Theorems for Locally Convex Cones", an excellent paper by Walter Roth on abstract generalizations of the Hahn-Banach separation theorem. Their Theorem 1 is what I disassembled and reassembled to prove what I needed.

Theorem 7: Given $X$ a locally compact and compact space, and a convex function $\varphi$ and concave Scott-continuous function $\psi$ (both of type $[X\to (-\infty ,\infty \left]\right]\to (-\infty ,\infty ]$ or $[X\to [0,\infty \left]\right]\to [0,\infty ]$) where $\psi \le \varphi$, then there is some affine, Scott-continuous function $\mu$ of the same type signature, where $\psi \le \mu \le \varphi$.

Corollary 1, LF-duality for domains Given any $\omega$-BC domain $X$ and inframeasure $\psi :\square X$

$$\psi =\sqcap \{\lambda f.m(f)+b|\forall f:[X\to (-\infty ,\infty ]],m(f)+b\ge \psi (f\left)\right\}$$

So even in domain theory, it's legitimate to view an inframeasure as the same as a set of a-measures.

Section 11: Faithful Acausal-to-Causal Translations

Referring back to "The Many Faces of Infra-Beliefs [AF · GW]", there was a way to (non-faithfully) translate acausal belief functions (which can encode any sort of problem where the way reality goes depends on your policy) to pseudocausal belief functions, which is, intuitively, "assume it's possible for the predictor to make a mistake". And there was a way to faithfully translate pseudocausal belief functions to causal belief functions, by adding an extra imaginary state, "Nirvana", that's 1 utility if you ever hit it.

So, all decision theory problems can be recast in causal form, by adding imaginary extra reward states!

Well... not really. There's two complications. One of them is the acausal-to-pseudocausal translation, not all decision-theory problems survive that one. It was extensively analyzed back in "The Many Faces of Infra-Beliefs", and the key to the translation not affecting expected values particularly much is whether a particular condition holds, which can be roughly described as "for a misprediction to have a large effect on what happens, it must be the case that you've got a non-negligible chance at actually entering the situation where you're mispredicted". It's like a sort of fairness condition. If Omega screwed up its predictions, could you prove it wrong?

The other complication is the "if Nirvana ever happens, it's 1 utility" part, as that isn't a continuous utility function, that's a lower-semicontinuous one. You could try to make Nirvana into a 1-reward state forevermore (and then things would be continuous, because Nirvana late isn't as good), but then that introduces another complication that could change things, where you stop dealing well with decision-theory problems because the time where you're being predicted is just way way too far in the future and it gets time-discounted into negligibility.

Although, that actually does sound somewhat sensible for good learning behavior. It seems quite difficult to learn good behavior in policy-selection problems when the gap between the action and the results is long.

Anyways, the result we want is some condition on acausal belief functions ${\Theta }^a$ s.t. translating them into causal belief functions ${\Theta }^c$ (with the Nirvana state counting as 1 reward forevermore) doesn't affect expected utilities of the policies particularly much, so the good things to do post-translation are still considered pretty good things to do pre-translation, and they agree more and more as the time-discount goes to infinity and the agent ges more farsighted.

To explain what's going on, we'll need to introduce the $\gamma$-metric on histories, a notion of difference between histories that depends on the time-discount. Remember, $\gamma \in [0,1)$, values closer to 1 are more far-sighted, and the utility functions are like

$$U^{\gamma }\left(h\right)=\frac{1}{1-\gamma }\sum _{n=0}^{\infty }{\gamma }^n\cdot r\left(h_{0:n}\right)$$

Ie, the reward on timestep n depends on the first n+1 actions and observations (the string $h_{0:n}$), and we do a time-discounted sum of them. This lets you assess what happens to a utility function as its time-discount goes to 1, ie, the limit of farsightedness.

Anways, the $\gamma$-metric, the time-discount dependent notion of difference between histories, is

$$d_{\gamma }(h,h^{\prime })={\gamma }^{\text{first n where}{h}_n\ne h_n^{\prime }}$$

The intuitive reason we care about this notion of distance is that it being small means that any utility function $U^{\gamma }$ with the same time-discount will assign similar values to those two histories, as they only start differing rather late. It's like "how indistinguishable are these two histories with our our given time discount".

Let $Theta$ be your acausal belief function/decision theory problem that you want to translate. Then the condition to be able to translate it faithfully to a causal form is

$$\underset{\gamma \to 1}{lim}\left(\underset{\pi ,{\pi }^{\prime },\mu \in \Theta \left(\pi \right)}{sup}(x\cdot \underset{\nu \in \Theta \left({\pi }^{\prime }\right)}{inf}{d}_{\gamma KR}(\mu ,\nu )-\mu ({\gamma }^{n:h_n\nsim {\pi }^{\prime }}\left)\right)\right)=0$$

Where $x$ is the upper bound to your reward function. $x\in [0,1]$.

This is pretty complicated and introduces some new notation, so we'll break it down. I don't expet the reader to spot this, but that quantity that we're taking the limit of is always 0 or higher. For the limit and the supremum, this is basically saying "in the farsightedness limit, as the time-discount $\gamma$ approaches 1, we should have that for any two policies $\pi ,{\pi }^{\prime }$, and any distribution over histories $\mu$ that can result from the first policy (ie, $\mu \in \Theta \left(\pi \right)$), the quantity in parentheses should be low or negative"

But, uh... what is that quantity in parentheses? Why do we need it to be low or negative? Reshuffling the statement "the quantity in paretheses should be 0 or lower", it turns into

$$x\cdot \underset{\nu \in \Theta \left({\pi }^{\prime }\right)}{inf}{d}_{\gamma KR}(\mu ,\nu )\le \mu \left({\gamma }^{n:h_n\nsim {\pi }^{\prime }}\right)$$

Remember, the acausal to pseudocausal translation is basically "the predictor is allowed o make mistakes", and then the pseudocausal to causal translation is basically "if the predictor makes a mistake, you get 1 reward forever".

If you think of $\pi$ as "what you're predicted to do", and ${\pi }^{\prime }$ as "what you actually do", and $\mu$ as "the distribution over histories that results from what you're predicted to do", then $\mu \left({\gamma }^{n:h_n\nsim {\pi }^{\prime }}\right)$ is "the time-discounted reward, according to the predicted distribution over histories, from going to Nirvana because your actual behavior (the policy ${\pi }^{\prime }$) is inconsistent with was was supposed to happen (the history $h$)".

Basically, this quantity is "you were mispredicted, your actual policy is something different, how much time-discounted utility do you pick up from Nirvana. Remember, Nirvana happens when your policy goes off the rails of what it was predicted to do"

And what's that quantity $x\cdot {inf}_{\nu \in \Theta \left({\pi }^{\prime }\right)}{d}_{\gamma KR}(\mu ,\nu )$? Well, $d_{\gamma }$ is a distance metric on histories, that's basically like "level of similarity according to utility functions with time-discount $\gamma$". $d_{\gamma KR}$ is just extending this metric to probability distributions. Thinking of a probability distribution as a pile of dirt on events, the KR-distance is "effort to rearrange one dirt pile into the other dirt pile". You can either move a small amount of dirt/measure a large distance to a very different outcome, or a large amount of dirt/measure a small distance to a very similar outcome. So, $\gamma KR$-distance being low means that the two probability distributions on histories are similar at early times, and only start diverging quite late, so any utility function with time-discount $\gamma$ thinks that the expected value doesn't change much. So, that quantity is like "the magnitude of the time-discounted change in the probability flow that results from being mispredicted". The ${inf}_{\nu \in \Theta \left({\pi }^{\prime }\right)}$ part is because we're trying to find the possible distribution that's consistent with you being correctly predicted which is the closest to the distribution $\mu$ that occurred from the wrong prediction. And the multiplication by $x$ is because, if your utility function is bounded in $[0,x]$, larger differences in the $\gamma$-KR distance make less difference to your expected values. Putting this all together, we can summarize the condition

$$\underset{\gamma \to 1}{lim}\left(\underset{\pi ,{\pi }^{\prime },\mu \in \Theta \left(\pi \right)}{sup}(x\cdot \underset{\nu \in \Theta \left({\pi }^{\prime }\right)}{inf}{d}_{\gamma KR}(\mu ,\nu )-\mu ({\gamma }^{n:h_n\nsim {\pi }^{\prime }}\left)\right)\right)=0$$

as "in the farsightedness limit, regardless of your true policy (${\pi }^{\prime }$), predicted policy ($\pi$), or results from the misprediction ($\mu$), the payoff from going off the rails of destiny and attaining Nirvana (the $\mu \left({\gamma }^n\right)$ part) should be comparable to or greater than the time-discounted change in probability flow that results from the misprediction (the KR-distance thing). If your utility function is bounded in $[0,x]$, that means that "1 reward forever" is a bigger boon to you, so bigger changes in probbility flow from being mispredicted are acceptable"

It's the fairness condition of "if I'm mispredicted, the misprediction should either have little effect on what happens, or if has a large effect, I should have a comparably large chance of actually entering the situation where I've been mispredicted and proving the prediction wrong".

For the theorem, ${\Theta }^c$ is the causal translation of the acausal belief function $\Theta$, and $U^{\gamma ,N}$ is the utility function that's just $U^{\gamma }$ but with 1 reward forevermore if it hits a Nirvana state.

Theorem 8: For any acausal belief function $\Theta$, if

$$\underset{\gamma \to 1}{lim}\left(\underset{\pi ,{\pi }^{\prime },\mu \in \Theta \left(\pi \right)}{sup}(x\cdot \underset{\nu \in \Theta \left({\pi }^{\prime }\right)}{inf}{d}_{\gamma KR}(\mu ,\nu )-\mu ({\gamma }^{n:h_n\nsim {\pi }^{\prime }}\left)\right)\right)=0$$

and the utility function $U$ has rewards bounded in $[0,x]$, then

$$\underset{\gamma \to 1}{lim}\underset{{\pi }^{\prime }}{sup}|\Theta \left({\pi }^{\prime }\right)\left(U^{\gamma }\right)-{\Theta }^c\left({\pi }^{\prime }\right)\left(U^{\gamma ,N}\right)|=0$$

So, pretty much, this theorem says that the condition we discussed means that in the farsightedness limit, regardless of the utility function $U$, the maximum difference in expected utility between the old acausal belief function and its causal translation shrinks to 0, uniformly across all of the policies.

0 comments

Comments sorted by top scores.