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?