Vanessa Kosoy comments on Vanessa Kosoy’s Shortform

[Vanessa Kosoy]

Ambidistributions

I believe that all or most of the claims here are true, but I haven’t written all the proofs in detail, so take it with a grain of salt.

Ambidistributions are a mathematical object that simultaneously generalizes infradistributions and ultradistributions. It is useful to represent how much power an agent has over a particular system: which degrees of freedom it can control, which degrees of freedom obey a known probability distribution and which are completely unpredictable.

Definition 1: Let $X$ be a compact Polish space. A (crisp) ambidistribution on $X$ is a function $Q:C\left(X\right)\to R$ s.t.

1. (Monotonocity) For any $f,g\in C\left(X\right)$, if $f\le g$ then $Q\left(f\right)\le Q\left(g\right)$.

2. (Homogeneity) For any $f\in C\left(X\right)$ and $\lambda \ge 0$, $Q\left(\lambda f\right)=\lambda Q\left(f\right)$.

3. (Constant-additivity) For any $f\in C\left(X\right)$ and $c\in R$, $Q(f+c)=Q\left(f\right)+c$.

Conditions 1+3 imply that $Q$ is 1-Lipschitz. We could introduce non-crisp ambidistributions by dropping conditions 2 and/​or 3 (and e.g. requiring 1-Lipschitz instead), but we will stick to crisp ambidistributions in this post.

The space of all ambidistributions on $X$ will be denoted $♡X$.^[1] Obviously, $\square X\subseteq ♡X$ (where $\square X$ stands for (crisp) infradistributions), and likewise for ultradistributions.

Examples

Example 1: Consider compact Polish spaces $X,Y,Z$ and a continuous mapping $F:X\times Y\to Z$. We can then define $F^{♡}\in ♡Z$ by

$$F^{♡}\left(u\right):=\underset{\theta \in \Delta X}{max}\underset{\eta \in \Delta Y}{min}{E}_{\theta \times \eta }[u\circ F]$$

That is, $F^{♡}\left(u\right)$ is the value of the zero-sum two-player game with strategy spaces $X$ and $Y$ and utility function $u\circ F$.

Notice that $F$ in Example 1 can be regarded as a Cartesian frame: this seems like a natural connection to explore further.

Example 2: Let $A$ and $O$ be finite sets representing actions and observations respectively, and $\Lambda :\{O^{\ast }\to A\}\to \square (A\times O{)}^{\ast }$ be an infra-Bayesian law. Then, we can define ${\Lambda }^{♡}\in ♡(A\times O{)}^{\ast }$ by

$${\Lambda }^{♡}\left(u\right):=\underset{\pi :O^{\ast }\to A}{max}{E}_{\Lambda \left(\pi \right)}\left[u\right]$$

In fact, this is a faithful representation: $\Lambda$ can be recovered from ${\Lambda }^{♡}$.

Example 3: Consider an infra-MDP with finite state set $S$, initial state $s_0\in S$ and transition infrakernel $T:S\times A\to \square S$. We can then define the “ambikernel” $T^{♡}:S\to ♡S$ by

$$T^{♡}(s;u):=\underset{a\in A}{max}{E}_{T(s,a)}\left[u\right]$$

Thus, every infra-MDP induces an “ambichain”. Moreover:

Claim 1: $♡$ is a monad. In particular, ambikernels can be composed.

This allows us defining

$$\varphi \left(\gamma \right):=(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^n\left(T^{♡}{)}^n\right(s_0)$$

This object is the infra-Bayesian analogue of the convex polytope of accessible state occupancy measures in an MDP.

Claim 2: The following limit always exists:

$${\varphi }^{\ast }:=\underset{\gamma \to 1}{lim}\varphi \left(\gamma \right)$$

Legendre-Fenchel Duality

Definition 3: Let $D$ be a convex space and $A_1,A_2\dots A_n,B\subseteq D$. We say that $B$ occludes $(A_1\dots A_n)$ when for any $(a_1\dots a_n)\in A_1\times \dots \times A_n$, we have

$$CH(a_1\dots a_n)\cap B\ne \varnothing$$

Here, $CH$ stands for convex hull.

We denote this relation $A_1\dots A_n⊢B$. The reason we call this “occlusion” is apparent for the $n=2$ case.

Here are some properties of occlusion:

1. For any $1\le i\le n$, $A_1\dots A_n⊢A_i$.

2. More generally, if $c\in \Delta \{1\dots n\}$ then $A_1\dots A_n⊢{\sum }_i{c}_i{A}_i$.

3. If $\Phi ⊢A$ and $\Phi \subseteq \Psi$ then $\Psi ⊢A$.

4. If $\Phi ⊢A$ and $A\subseteq B$ then $\Phi ⊢B$.

5. If $A_1\dots A_n⊢B$ and $A_i^{\prime }\subseteq A_i$ for all $1\le i\le n$, then $A_1^{\prime }\dots A_n^{\prime }⊢B$.

6. If $\Phi ⊢A_i$ for all $1\le i\le n$, and also $A_1\dots A_n⊢B$, then $\Phi ⊢B$.

Notice that occlusion has similar algebraic properties to logical entailment, if we think of $A\subseteq B$ as ”$B$ is a weaker proposition than $A$”.

Definition 4: Let $X$ be a compact Polish space. A cramble set^[2] over $X$ is $\Phi \subseteq \square X$ s.t.

1. $\Phi$ is non-empty.

2. $\Phi$ is topologically closed.

3. For any finite ${\Phi }_0\subseteq \Phi$ and $\Theta \in \square X$, if ${\Phi }_0⊢\Theta$ then $\Theta \in \Phi$. (Here, we interpret elements of $\square X$ as credal sets.)

Question: If instead of condition 3, we only consider binary occlusion (i.e. require $|{\Phi }_0|\le 2)$, do we get the same concept?

Given a cramble set $\Phi$, its Legendre-Fenchel dual ambidistribution is

$$\hat{\Phi }\left(f\right):=\underset{\Theta \in \Phi }{max}{E}_{\Theta }\left[f\right]$$

Claim 3: Legendre-Fenchel duality is a bijection between cramble sets and ambidistributions.

Lattice Structure

Functionals

The space $♡X$ is equipped with the obvious partial order: $Q\le P$ when for all $f\in C\left(X\right),$ $Q\left(f\right)\le P\left(f\right)$. This makes $♡X$ into a distributive lattice, with

$$(P\wedge Q)\left(f\right)=min\left(P\right(f),Q(f\left)\right)$$$$(P\vee Q)\left(f\right)=max\left(P\right(f),Q(f\left)\right)$$

This is in contrast to $\square X$ which is a non-distributive lattice.

The bottom and top elements are given by

$$\perp \left(f\right)=\underset{x\in X}{min}f\left(x\right)$$$$\top \left(f\right)=\underset{x\in X}{max}f\left(x\right)$$

Ambidistributions are closed under pointwise suprema and infima, and hence $♡X$ is complete and satisfies both infinite distributive laws, making it a complete Heyting and co-Heyting algebra.

$♡X$ is also a De Morgan algebra with the involution

$$\overline{Q}\left(f\right):=-Q(-f)$$

For $X\ne \varnothing$, $♡X$ is not a Boolean algebra: $\Delta X\subseteq ♡X$ and for any $\theta \in \Delta X$ we have $\overline{\theta }=\theta$.

One application of this partial order is formalizing the “no traps” condition for infra-MDP:

Definition 2: A finite infra-MDP is quasicommunicating when for any $s\in S$

$$\underset{\gamma \to 1}{lim}(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^n\left(T^{♡}{)}^n\right(s_0)\le \underset{\gamma \to 1}{lim}(1-\gamma \left)\sum _{n=0}^{\infty }{\gamma }^n\right(T^{♡}{)}^n\left(s\right)$$

Claim 4: The set of quasicommunicating finite infra-MDP (or even infra-RDP) is learnable.

Cramble Sets

Going to the cramble set representation, $\hat{\Phi }\le \hat{\Psi }$ iff $\Phi \subseteq \Psi$.

$\Phi \wedge \Psi$ is just $\Phi \cap \Psi$, whereas $\Phi \vee \Psi$ is the “occlusion hall” of $\Phi$ and $\Psi$.

The bottom and the top cramble sets are

$$\perp =\left\{{\top }_{\square }\right\}$$$$\top =\square X$$

Here, ${\top }_{\square }$ is the top element of $\square X$ (corresponding to the credal set $\Delta X)$.

The De Morgan involution is

$$\overline{\Phi }=\{\Theta \in \square X\mid \forall \Xi \in \Phi :\Theta \cap \Xi \ne \varnothing \}$$

Operations

Definition 5: Given $X,Y$ compact Polish spaces and a continuous mapping $h:X\to Y$, we define the pushforward $h_{\ast }:♡X\to ♡Y$ by

$$h_{\ast }(Q;f):=Q(f\circ h)$$

When $h$ is surjective, there are both a left adjoint and a right adjoint to $h_{\ast }$, yielding two pullback operators $h_{min}^{\ast },h_{max}^{\ast }:♡Y\to ♡X$:

$$h_{min}^{\ast }(Q;f):=\underset{g\in C\left(Y\right):g\circ h\ge f}{min}Q\left(g\right)$$$$h_{max}^{\ast }(Q;f):=\underset{g\in C\left(Y\right):g\circ h\le f}{max}Q\left(g\right)$$

Given $Q\in ♡X$ and $P\in ♡Y$ we can define the semidirect product $Q⋉P\in ♡(X\times Y)$ by

$$(Q⋉P)\left(f\right):=Q(\lambda x.P(\lambda y.f(x,y)\left)\right)$$

There are probably more natural products, but I’ll stop here for now.

Polytopic Ambidistributions

Definition 6: The polytopic ambidistributions ${♡}_{\text{pol}}X$ are the (incomplete) sublattice of $♡X$ generated by $\Delta X$.

Some conjectures about this:

• For finite $X$, an ambidistributions $Q$ is polytopic iff there is a finite polytope complex $C$ on $R^X$ s.t. for any cell $A$ of $C$, $Q{|}_C$ is affine.

• For finite $X$, a cramble set $\Phi$ is polytopic iff it is the occlusion hall of a finite set of polytopes in $\Delta X$.

• $\varphi \left(\gamma \right)$ and ${\varphi }^{\ast }$ from Example 3 are polytopic.

1. ^

   The non-convex shape $♡$ reminds us that ambidistributions need not be convex or concave.

2. ^

   The expression “cramble set” is meant to suggest a combination of “credal set” with “ambi”.