## 5 Open Problems regarding Optimality of AIXI
** Convergence of \(M\) to \(\mu\) holds somewhat surprisingly even for unbounded horizon, which is good news for AIXI. Unfortunately convergence can be slow, but I expect that convergence is \"reasonably\" fast for \"slowly\" growing horizon, which is important in AIXI. It would be useful to quantify and prove such a result. * **Reinforcement learning. ** Although there is no explicit learning algorithm built into the AIXI model, AIXI is a reinforcement learning system capable of receiving and exploiting rewards. The system learns by eliminating Turing machines \(q\) in the definition of \(M\) once they become inconsistent with the progressing history. This is similar to Gold-style learning [157]. For Markov environments (but not for partially observable environments) there are efficient general reinforcement learning algorithms, like \(TD(\lambda)\) and \(Q\) learning. One could compare the performance (learning speed and quality) of AI\(\xi\) to e.g. \(TD(\lambda)\) and \(Q\) learning, extending [52]. * **Posterization. ** Many properties of Kolmogorov complexity, [PERSON]'s prior, and reinforcement learning algorithms remain valid after \"posteriorization\". With posterization I mean replacing the total value \(V_{1m}\), the weights \(w_{\
u}\), the complexity \(K(\
u)\), the environment \(\
u(or_{1:m}|a_{1:m})\), etc. by their \"posteriors\" \(V_{km}\), \(w_{\
u}(aor_{<k})\), \(K(\
u|aor_{<k})\), \(\
u(or_{k:m}|or_{<k}a_{1:m})\), etc, where \(k\) is the current cycle and \(m\) the lifespan of AIXI. Strangely enough for \(w_{\
u}\) chosen as \(2^{-K(\
u)}\) it is not true that \(w_{\
u}(aor_{<k})\!\sim\!2^{-K(\
u|aor_{<k})}\). If this property were true, weak bounds as the one proven in [27, Sec.6.2] (which is too weak to be of practical importance) could be boosted to practical bounds of order 1. Hence, it is highly import to rescue the posterization property in some way. It may be valid when grouping together essentially equal distributions \(\
u\). * **Relevant and non-computable environments \(\mu\). ** Assume that the observations of AIXI contain irrelevant information, like noise. Irrelevance can formally be defined as being statistically independent of future observations and rewards, i.e. neither affecting rewards, nor containing information about future observations. It is easy to see that [PERSON] prediction does not decline under such noise if it is sampled from a computable distribution. This likely transfers to AIXI. More interesting is the case, where the irrelevant input is complex. If it is easily separable from the useful input it should not affect AIXI. One the other hand, even in prediction this problem is non-trivial, see problem 4.g. How robustly does AIXI deal with complex but irrelevant inputs? A model that explicitly deals with this situation has been developed in [129, 130]. * **Grain of truth problem**[158]. Assume AIXI is used in a multi-agent setup [159] interacting with other agents. For simplicity I only discuss the case of a single other agent in a competitive setup, i.e. a two-person zero-sum game situation. We can entangle agents \(A\) and \(B\) by letting \(A\) observe \(B\)'s actions and vice versa. The rewards are provided externally by the rules of the game. The situation where \(A\) is AIXI and \(B\) is a perfect minimax player was analyzed in [27, Sec.6.3]. In multi-agent systems one is mostly interested in a symmetric setup, i.e. \(B\) is also an AIXI. Whereas both AIXIs _may_ be able to learn the game and improve their strategies (to optimal minimax or more generally _Nash equilibrium_), this setup violates one of the basic assumptions. Since AIXI is incomputable, AIXI(\(B\)) does not constitute a computable environment for AIXI(\(A\)). More generally, starting with any class of environments \(\mathcal{M}\), then \(\mu\hat{=}\)AI\(\xi_{\mathcal{M}}\) seems not to belong to class \(\mathcal{M}\) for most (all?) choices of \(\mathcal{M}\).