I feel that this post would benefit from having the math spelled out. How is inserting a trader a way to do feedback? Can you phrase classical RL like this?

Two thoughts about the role of quining in IBP:

• Quine's are non-unique (there can be multiple fixed points). This means that, viewed as a prescriptive theory, IBP produces multi-valued prescriptions. It might be the case that this multi-valuedness can resolve problems with UDT such as Wei Dai's 3-player Prisoner's Dilemma and the anti-Newcomb problem^[1]. In these cases, a particular UDT/IBP (corresponding to a particular quine) loses to CDT. But, a different UDT/IBP (corresponding to a different quine) might do as well as CDT.
• What to do about agents that don't know their own source-code? (Arguably humans are such.) Upon reflection, this is not really an issue! If we use IBP prescriptively, then we can always assume quining: IBP is just telling you to follow a procedure that uses quining to access its own (i.e. the procedure's) source code. Effectively, you are instantiating an IBP agent inside yourself with your own prior and utility function. On the other hand, if we use IBP descriptively, then we don't need quining: Any agent can be assigned "physicalist intelligence" (Definition 1.6 in the original post, can also be extended to not require a known utility function and prior, along the lines of ADAM) as long as the procedure doing the assigning knows its source code. The agent doesn't need to know its own source code in any sense.

1. ^{^}

   @Squark is my own old LessWrong account.

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

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

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

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

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

This allows us defining

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:

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

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

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

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

The bottom and top elements are given by

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

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$

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

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

The De Morgan involution is

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

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$:

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

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".

Here's the sketch of an AIT toy model theorem that in complex environments without traps, applying selection pressure reliably produces learning agents. I view it as an example of Wentworth's "selection theorem" concept.

Consider any environment $\mu$ of infinite Kolmogorov complexity (i.e. uncomputable). Fix a computable reward function

Suppose that there exists a policy ${\pi }^{\ast }$ of finite Kolmogorov complexity (i.e. computable) that's optimal for $\mu$ in the slow discount limit. That is,

Then, $\mu$ cannot be the only environment with this property. Otherwise, this property could be used to define $\mu$ using a finite number of bits, which is impossible^[1]. Since $\mu$ requires infinitely many more bits to specify than ${\pi }^{\ast }$ and $r$, there has to be infinitely many environments with the same property^[2]. Therefore, ${\pi }^{\ast }$ is a reinforcement learning algorithm for some infinite class of hypothesis.

Moreover, there are natural examples of $\mu$ as above. For instance, let's construct $\mu$ as an infinite sequence of finite communicating infra-RDP refinements that converges to an unambiguous (i.e. "not infra") environment. Since each refinement involves some arbitrary choice, "most" such $\mu$ have infinite Kolmogorov complexity. In this case, ${\pi }^{\ast }$ exists: it can be any learning algorithm for finite communicating infra-RDP with arbitrary number of states.

Besides making this a rigorous theorem, there are many additional questions for further investigation:

• Can we make similar claims that incorporate computational complexity bounds? It seems that it should be possible to at least constraint our algorithms to be PSPACE in some sense, but not obvious how to go beyond that (maybe it would require the frugal universal prior).
• Can we argue that ${\pi }^{\ast }$ must be an infra-Bayesian learning algorithm? Relatedly, can we make a variant where computable/space-bounded policies can only attain some part of the optimal asymptotic reward of $\mu$?
• The setting we described requires that all the traps in $\mu$ can be described in a finite number of bits. If this is not the case, can we make a similar sort of an argument that implies ${\pi }^{\ast }$ is Bayes-optimal for some prior over a large hypothesis class?

1. ^{^}

   Probably, making this argument rigorous requires replacing the limit with a particular regret bound. I ignore this for the sake of simplifying the core idea.

2. ^{^}

   There probably is something more precise that can be said about how "large" this family of environment is. For example, maybe it must be uncountable.

Can you explain what's your definition of "accuracy"? (the 87.7% figure)
Does it correspond to some proper scoring rule?