Self-Predictive Universal AI
Authors: Elliot Catt
Jordi Grau-Moya
Marcus Hutter
Matthew Aitchison
Tim Genewein
Gregoire Deletang
Li Kevin Wenliang
Joel Veness
Venue: NeurIPS 2023 poster (2023)
Keywords: General Reinforcement Learning
Reinforcement Learning
Self-Modeling
Bayes-optimality
Policy Distillation
Uncertainty
Universal AI

Abstract: Reinforcement Learning (RL) algorithms typically utilize learning and/or planning techniques to derive effective policies. The integration of both approaches has proven to be highly successful in addressing complex sequential decision-making challenges, as evidenced by algorithms such as AlphaZero and MuZero, which consolidate the planning process into a parametric search-policy. AIXI, the most potent theoretical universal agent, leverages planning through comprehensive search as its primary means to find an optimal policy. Here we define an alternative universal agent, which we call Self-AIXI, that on the contrary to AIXI, maximally exploits learning to obtain good policies. It does so by self-predicting its own stream of action data, which is generated, similarly to other TD(0) agents, by taking an action maximization step over the current on-policy (universal mixture-policy) Q-value estimates. We prove that Self-AIXI converges to AIXI, and inherits a series of properties like maximal Legg-Hutter intelligence and the self-optimizing property.

Self-Predictive Universal AI
Elliot Catt, Jordi Grau Moya, Marcus Hutter, Matthew Aitchison Tim Genewein, Gregoire Deletang, Kevin Li Wenliang, Joel Veness Google DeepMind
ecatt&google.com com
Abstract
Reinforcement Learning (RL) algorithms typically utilize learning and/or planning techniques to derive effective policies. Integrating both approaches has proven to be highly successful in addressing complex sequential decision-making challenges, as evidenced by algorithms such as AlphaZero and MuZero, which consolidate the planning process into parametric gearch-policy. AIXI, the universal Bayes- optimal agent, leverages planning through comprehensive search as its primary means find an optimal policy. Here we define an alternative universal Bayesian agent, which we call Self-AIXI, that on the contrary to AIXI, maximally exploits learning to obtain good policies. It does so by self-predicting action data, which is generated, similarly to other TD(0) agents, by taking an action maximization step over the current on-policy (universal mixture-policy) Q-value estimates. We prove that Self-AIXI converges to AIXI, and inherits a series of properties like maximal Legg- Hutter intelligence and the self-optimizing property.
own stream of
1 Introduction
Reinforcement Learning (RL) [1] algorithms exploit learning, planning or their combination, to obtain good policies from experience. Pure learning consists of using real experience for improving policy via a (parametric) model, possibly representing an explicit policy-model and/or the Q-values [2- 6]. In sense, learning stores the computational effort of policy-improvenen which makes a computationally efficient approach when needing to reuse the policy later on. In contrast, pure planning finds good policies via simulated experience using environment model and randomized (or exhaustive) search policy [1, 7, 8J. In the case of unknown or stochastic environments, one must re-plan after receiving new observation, thus wasting all computational-effor from the previous step. This makes pure planning a wasteful approach. Using both, planning and learning, good way improve performance and efficiency demonstrated by modern high-performant RL algorithms such as MuZero [9-12]. These algorithms distill the planning effort back into the parametric search-policy by training it predict the good actions obtained from planning. In way, these agents are self-predicting their own poprey-insssseemnts. Although empirically successful and widely used, this distillation [13] self- iif-preddictinn process is motivated in purely heuristic way without much theoretical understanding on its optimality condition.
into the parameters,
The AIXI agent [14, 15] is theoretical universal Bayes-optimal agent obtained through pure plan- ning without relying on distilling the search effort as described above. AIXI learns an environment model via a Solomonoff predictor [16, 17] and uses it for exhaustive (computationally intractable) planning. Thus, although it uses learning for the environment model, we say AIXI adopts a pure planning approach in the context of policy generation. Two desirable properties of Solomonoff pre- diction are universaliy-obtained by considering a huge hypothesis class containing all computable
We use the terms planning and search interchangeably.
PPolicy distillation usually refers the process of amortizing or several policies into another policy model. We view self-prediction as type distillation where search-policy consolidated into another model.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

environments- and fast convergence to the true environment statistics [18, 19]. Unfortunately, univer- sality makes Solomonoff prediction incomputable. a property that AIXI also inherits. Nevertheless, the AIXI agent is considered as the most powerful agent and the gold-standard in decision-making under unknown general environments. An existing gap in the literature, however, is the lack of an alternative universal agent that maximally exploits learning and distillation, instead of the more wasteful planning approach used by AIXI. Understanding this distillation process from a theoretical standpoint can inspire taking new directions in approximating the AIXI agent as done in [20], which based on a pure planning approach.
The central aim of this paper is to define an agent, which we name Self-AIXI, that maximally exploits preficeeditiin (or distillation) instead of planning, and to prove that this agent optimal in the sense that converges to the gold-standard AIXI agent. We define self-prediction as the process of predicting the stream of action-data generated by the agent itself. Self-AIXI generates action-data in similar fashion as other Temporal Difference TD(O) [1] algorithms in which there is only a single "planning" step when choosing action i.e. arg max,, (h,, a.) for history h, action d, and current
Q-value estimates Q. The difference lies in that Self-AIXI does exact Bayesian inference on the policy space by holding universal mixture Ç over policies (in addition to &, the universal mixture over environments), and consumes action-data generated by maximizing the Self-AIXI policy i.e.
arg max, Q (be, a). In summary our contributions are:
We define Self-AIXI, a novel universal agent based on self-prediction.
We prove that Self-AIXI's Q-values converge to AIXI's Q-values asymptotically.
We show how Self-AIXI leads to maximum Legg- [21] intelligence and inherits the self-optimization [22] property.
These results provide compelling evidence that self- self-prediction can effectively serve as robust alternative to traditional planning methods.
Background
2.1 General Reinforcement Learning
Let A. O. R denote the (finite) action, observation and reward set respectively. Let the set of percepts be defined as & == O x R. A.' denotes distribution over X. Define the set of histories H := (A x E)". A policy π H + AA is distribution over actions given history. An environment μ : x + AE is a distribution over percepts given history and action. We use her = djé1 ... Gr- 1 01 01711 ... 04-10t-177-1 to denote the history of interactions up to time I 1. Given an environment 1r and policy æ we use μzt denote the induced probability measure on histories, i.e. hes is assumed to be sampled from n² We are interested in how well agents (policies) perform. We measure this performance by the future expected sum of discounted rewards, called value function.
Definition 1 (Value function and optimal policy). The value V : 7 - [0. 1] of a policy in an enviroument v, and discount factor ? given history hige E H defined as
VJ = r, E
x-
rw
lice
Where r, Ede -0- 1- is the normalization factor of the discount. The optimal value defined as Vy (hee) = sup, vi (hee),, the set of optimal policies with respect that value is defined as arg max, V (hea), and an optimal policy with respect to the value is defined as (())) E arg max, V (h<z))
We similarly define the action value Qavalue function QT 0z) V2 (herat), which allows to write the pseudo-recursive Bellman forms
Vi (hee) = Σ x(aelhee) (her,, ar), (h = Σ v(eelteerae) (rs + (V, (I)
G.EAA
01E8

---

We use throughout the paper the Total- Variation distance convenient way to compare two policies.
Definition 2 (TV distance). We define the Total Variation (TV) distance of two measures ui , between timesteps and i S m S 0c as
sup Dm U/ Ihet) HC(AxE))
1 (H)))) (H het)l S
The following lemma, useful for our later proofs, shows that TV distance is an upper bound for value function difference in general reinforcement learning.
Lemma 3 ([23, Lemma 4.17]) For any two policies T1, and two environments V1,
V (hea) V (h 1 (v ,12 (h
2.2 Universal Artificial Intelligence
We achieve universality by considering Bayesian mixture over a class of potential environments M which is large enough so as to include the true environment the agent is interacting with. typical choice is the class of all computable functions.
Definition 4 (Bayesian mixture environment). The Bayesian mixture over the class of environments M is defined
w(llhee) with posterior w(v[haa) := wo(/het) v(ea(hecas)) E(eelhicaat)
{(e()hcaat)= = Σ
NEM
and w(vlc) == w(v) is the prior probability v.
Given this environment mixture E, we define AIÉ (AIXI) acting optimally with respect to &. Definition (AIE). AIXI, the optimal Bayesian agent is defined as
Te (hee) = arg max (het,,))) a)
The following results prove that the AIXI agent achieves maximal intelligence in the Legg-Hutter sense and self-optimizing. These are important to have in mind throughout the paper since we will prove the same type of results for our Self-AIXI agent.
Legg-Hutter Intelligence measures the performance of agent in wide range of environments M, weighted by their p(oste)rior plausibility w(.)):
Definition (LH Intelligence [21]). The Legg-Hutter Intelligence measure " of policy v given
history het is defined as
(TT( = Σ wwulhhz) = (h2t)
DEM
It has been shown that if M is such that there exists a policy (sequence) which able achieve strong asymptotic optimality then AIXI can achieve this as well. This property is known as self-optimizing.
Theorem (AIXI is Self-optimizing [14]). Let be some environment. If there a policy n and a sequence of policies WI, ... such that for all E M
(h - (hea) + + as t 4d allmmstt surely
(2)
then
(her)) - (ber)) - as 1 x 1= -almmost surely
T = पे and Equation holds for all p E M, then कद strongly asymptotically optimal in the class M.
For taxonomy of classes that do (not) allow for self-optimizing policies, see [21, Figure 3. challenge that difficult to overcome that for geometric discounting, there may not yet be widely-recognized classes of environments that allow self-optimizing policies.

---

3 Self-prediction in General Reinforcement Learning
We are ready to define our Self-AIXI agent that based on self-prediction instead of pure planning. We start with our definition of the mixture policy Ç and discuss the choices of model class and prior. Definition (Bayesian mixture policy). The Bayesian mixture over the class of policies P defined as
a(as)he)) ((aelher)
((ay)het) = Σ ((rthee)m(aaltee with posterior w(m(hha) w(r)he)) TEP
and w(xle)=== == w(x) is the prior probability of Note w()) is prior for the mixture policy, while we()) was prior for the mixture environment.
Lemma (Linearity of Q-values). For all p. n, lett and oz we have
(het,, E ((etha))) PEM
(g(net, = -E (i
TEP
From the linearity of Q-values we can define the following Q-value over the Bayesian mixture environment and Bayesian mixture policy.
(her at) = Σ [((T)
Σ
(hees, ax)
xEP
VEM
Definition 10 (Self-AIXI). The agent Self-AIXI is defined as taking the (one step) optimal action with respect to Q Formally,
xs(hee) == a max (her,,))
a,
Remark 11 (Self-AIXI does not optimize the future.). Importantly, Self-AIXI maximizes the Q-values from the mixture policy instead of the optimal policy, which means that there is need to optimize the future but needs to know the Q-values of the current Ç-mixture, Pragmatically, these Q-values are on-policy, typically easier to estimate than the optimal off-policy values.
Note how action selection and history interact with the policy-mixture. The action selected by the Self- AIXI agent necessarily improves, by definition, over the current value estimates max., Q (hice, az) 2
V (hex). Then, this action is added to the next history h<++1 which is consumed by the policy- mixture at the next time step i.e., {(ott1/h<44)) This leads to the following remark.
Remark 12 (Self- preediciedi minimal improvements.). The policy-mixture does Bayesian inference over the incoming self- generated action-data and makes better predictions over time. Thus, Self-AIXI self- predicting its own small improvements made by the arg max operation Definition 10. In the case of using the largest class of policies (all computable functions), the mixture is a Solomonoff predictor with enough power to represent, within itself. the policy evaluation and improvement operation.
Showing that the self-prediction process employed by Self-AIXI converges to AIXI the aim of our theoretical results in Section 4.
3.1 Choice of class and prior
When choosing an environment class M we need pick one large enough so as to contain the true environment μı; the larger the class the weaker the assumption that μ E M. However, the larger the class we choose the harder will be to compute the Bayesian mixture of that class, to the point that & may become incomputable (or at least more incomputable than any V E M). With all of this in mind there are two directions that this can taken: The first is to choose the largest class such that computing & is still tractable and the second is to choose the largest possible class such that it contains all possible environments our universe could contain (or be). the first case we can choose something like the class of variablc-order MDPs with efficient Context Tree Weighting

---

(CTW) algorithm [24] for ç, is done in [20]. In the second case we can pick the set of all (cumulatively lower-) semicomputable semimeasures [25]. Without going too much into the choice of prior, a simplicity-basee prior is an ideal choice. There is an interesting poly-time computable class of all measures of logarithmic complexity [26] for which & E M ((a, ---spe measures). One easy way of achieving & E M is to add & to MM with some weight u/ > O and renormalize wi ~ wy = (1 - w() w, then = MM == {5} U.M. We can apply the same logic to the policy class P and policy prior w(T)) as we just did for M and w(u), similarly we need to have that g E P. leave the full investigation of policy classes to future work. Full discussion on the choice of class
M and prior wxl) are beyond the scope of this work [14, 27].
3.2 Experimental Results
While our work mainly theoretical, we also conducted experiments (see Appendix B) comparing self-prediction, using a Self-AIXI approximation, against the pure planning approach, using an AIXI approximation, using Context Tree Weighting as predictor and Monte-Carlo Tree Search for the Q-value estimates. In short, the Self-AIXI approximation outperforms the AIXI approximation in three environments and performs equally in the remaining two.
Theoretical Results
In this section will demonstrate the intelligence of Self-AIXI by showing that it asymptotically converges to AIXI in expectation. We specifically chose this criterion over other types of optimality, since Cesaro and Almost-Sure asymptotic optimality (converging the optimal policy) are strong [28-30], and are not satisfied by AIXI. In fact, agents which satisfy these also die with certainty [31].
The goal is show that Self-AIXI eventually performs well as the most intelligent agent, and AIXI is the most intelligent agent [21]. We will do this by proving an asymptotic convergence result to the Bayes optimal policy in all environments.
To summarize the results of this section:
Theorem 18: Vu. Vus Ve in nT -xxpeeccctain.n.
Theorem 21: Vp. VT + Vnz in nT =xxeeppcttation.
Theorem 22: VEs + V. -amost surely, under similar conditions to the AIXI Self- optimizing result from Theorem 7.
The initial three results successively broaden in scope, with the second being a more general form of the first, and the third further generalizing the second, holding for all μ instead of just ç. All proofs not found in this section can be found in the appendix.
4.1 Expected AIXI-like behavior
To start with, we will present useful Lemma about the environment mixture g: Lemma 13 (Convergence of & to in TV). For any environment μ E M and policy we have
Dxo(ET , (ba)) + 0 as + 0o -alalmost surely
Proof. Dominance {*) 2 w()) (+) implies that nx' absolutely continuous with respect to &T and therefore 5" merges strongly with f(" [32]. For full details and definitions of strong merging and absolute continuity see [23].
We can derive a dual to Lemma 13 and restate it in terms of asymptotic convergence in expectation:
Lemma 14 (Convergence of ( to in expectation). Ifx E P then for all u we have
D uf [hee) + O as -
Proof. The proof is dual to the proof Lemma 13 with policies and environments exchanged. Finally, almost convergence implics convergence in expectation for bounded random variables. D
5

---

Now we can show that if policy is close to one-step optimal, then it is also close to optimal (this result is independent of and will work for any environment, but we are only interested in the E case).
Lemma 15 (A one-step good policy is close to optimal). Let A(h) == IV (h) V (h)) with (A x 8) for 2 to E N.
If E max ( (h, a) - Vi <B Vt # to
and E mmax Ee (((ehha)(haa)) S + a) a) A to
A4 2 to provided 1 1+a< then Eg)(h) 1-7(1+a)
8
Using the previous Lemma can show our main result about the behavior of Self-AIXI. This result shows that the performance Self-AIXI converges to that of AIXI on (expected) histories generated by Self-AIXI. We call a policy that satisfied the second condition for some 1 + < 1/7 for some (large) to, sensible off policy. We conjecture this plausible condition holds for Ts, bar some exotic counter-example classes MM.
Theorem 16 LeXf-AIXI converges to AIXI in f-expectation). Assuming Te is sensible off-po
VV (heee) - Ve= (hei) +0 0 as + cc.
Proof.
(a) S
(0) Ve (h) v2(()) 2 D (5h))
max ah, VV(h)
where (a) and (b) follow from
Ve (h) = max (h, a) > Σ [((al))(((hha) = (h)
and (c) follows from Lemma 3. Let B > 0 and h E (Ax EY'. Now Lemma 14 and the above implies that there exists a to such that for all 2 to.
0
S E TH
max 2 a) - V (h)] s Doo 1hh < B
Taking the expectation of 0
S Ve V S Vē V (which follows from Ve 2 Vē 2 V(),
Lemma 15 implies
0
S E (4) V (h)) S E.g IV - vV $ 8/(1 -(1 +
Since 3 0 was arbitrary, get the E (V (h) V (h)] + 0.
The previous theorem also holds in expectation over the true environment, μ4, instead of in expectation w.r.t. S, but first we need small lemma:
Lemma 17 (E implies E + O). If a is such that
B [V= (her)) - (h=t)) + as +
then for all E M we have
E (h<c)) Vi (h=r)) +0 as t oc.
We can now present the main Theorem of the paper, this theorem states that as Self-AIXI interacts with the true environment μs Aelf-AIXI will learn to act like the optimal Bayesian agent AIXI. Theorem 18 (Main Theorem: Self-AIXI converges AIXI in p-expectation). For all μ E M have
B
(g(het) - VS (hei) +0 0 as + 00.
Proof. Theorem 16 and Lemma 17.
We can rewrite the above theorem in the form of the Universal Intelligence measure T.

---

Corollary 19 (LH Form of Theorem 18), For all M
EE max I(T ((Thhe)) T(TT]/eae) 0 as +
Finally we can generalise our previous result to work for the value function of any μ. This is important because most interested in the performance of our agent the true environment. We first need to show that convergence of the value function with ç implies convergence the value function with ja (in j--xpectation).
Lemma 20 (VT + Ve implies V + Vi in u-expectation). If n is such that for all E M
E Vē" (hee) - Ve (her) + as + co.
and Dio , (haa) 0 nM -almost surely then have
E VT (her) -V (hec) + 0 as t - cc.
Now we can present a convergence value functions with the true environment
Theorem 21 (SeIf-AIXI converges to the Ç-optimal agent in p-expectation). For all E M if Doo (n " (het)) + 0 T aalmsst surely then we have
b [ (het) - V (hze) + as - oc.
Proof. Immediate result form Theorem 18 and Lemma 20
This result states that as Self-AIXI interacts with the true environment the expected future performance difference between Self-AIXI and AIXI in μ will go to zero, that to say, they will (asymptotically) have equal performance in
4.2
Self-optimization
We have previously shown the performance of Self-AIXI using convergence of value functions u-expectation. We can also demonstrate the performance of Self-AIXI a more direct way, using self-optimization. That is, showing that if it is possible for policy to learn to be optimal in all environments a given class, then Self-AIXI will learn to optimal in all environments this class.
Self-AIXI can self-optimize in the same way as AIXI, with an additional assumption on the self model. The additional assumption is that for all t, het we have (h 2 V (h2z)) -t.
Theorem 22 (Self-AIXI is Self-optimizing). Let μ be some environment. If there is policy т and a sequence of policies T1. 72 all contained within P such that for all t, het we have V (hex)) 2 (hzz)) - 4 with ét + 0, and for all u E M
(1(h))) - V (her) + 0 as t n= -almotstt surely
(4)
then
(h( - (her)
as 1 xo 1ºth -almost surely
If π πg and Equation 4 holds for all p M, then me is strongly asymptotically optimal in the class M.
There are known important cases model classes which admit self-optimising policies such as Er- godic MDPs [33] and Ergodic k-MDPs [34]. However, we have not yet shown there exist (interesting) classes M and P where the assumption that for all t, her have V (h<r) V (h<e) with 0 and the other sclf-optimizing assumptions hold. We leave this to future work.

---

Policy Learning (or distillation)
Environment Model
Bayes
Planning
Optimal
Practical
AIXI
No
Yes
Yes
Yes
No
Self-AIXI
Yes
No
Yes
Yes
No
MIXIIXI-
No
Yes
Yes
Yes
Yes
117err
Yes
Yes
Yes
No
Yes
DQN
Yes
No
Yes
CaC
No
No
No
Yes
Yes
PhiMDP
No
No
No
No
No
Table Comparison between different methods
All models in the table learn (action) value function.
5 Related work
5.1 Universal Artificial Intelligence
There has been much work studying the Bayesian optimal agent AIXI and extending it in various ways [14, 21, 23]. Some of these extensions include: Knowledge seeking agent (KSA), an extension of AIXI which seeks information leading to form of maximal exploration [35, 36]. BayesExp, which combines the exploiting of AIXI and exploring of KSA way that allows the agent to be weakly asymptotically optimal [37, 38J. An AIXI variant that uses Thompson sampling [39] for additional exploration asymptotically optimal in expectation [28]. Inquisitive Agent (Inq) uses an information gaining strategy based expeditions to achieve strong asymptotic optimality [40].
AIXI achieves (by definition) Bayesian optimality, and although there are problems with this notion of optimality, it is widely agreed to be the (current) best choice for an optimality criterion. Every notion of optimality possesses inherit difficulties; these difficulties have been extensively studied Leike and Hutter [29], Lattimore and Hutter [30], Cohen et al. [31].
5.2 Comparison with other methods in the literature
To overcome the computational burden of the AIXI's planning phase, approximation techniques usually relax the planning problem into an estimation problem [41, 42]. The main approach for off- the-shelf estimation methods such as Monte Carlo Tree Search (MCTS) is an (optimistic) estimation of the Q-values. Though seemingly different, planning and learning, in the general case, can be seen following very similar computational processes shown by [43]. Other practical methods which reduce or remove the planning problem are distributional reinforcement learning [44], Compress and Control (CnC) [45] and feature reinforcement learning (FRL) [46, 47]. In distributional reinforcement learning and CnC powerful sequence prediction methods are utilized to estimate the distribution of returns directly. While it does not remove the planning entirely, FRL adaptively compresses the general RL problem to more simple (often MDP) problem and solves that problem by traditional methods. The planning required in the simple problem often far less than in the general problem.
In Table we compare some exemplary agents where each column denotes whether they use some form of learning (or policy distillation), whether they use explicit search/planning, whether they learn an explicit model of the environment, if they are a Bayes-optimal agent, and if there are practical in the sense that there is actual implementation of the agent. As be seen, Self-AIXI is the only Bayes-optimal agent that universal and exploits learning instead of planning.
5.3 Agents modeling themselves
Self- seff-predictio can be thought as an agent modeling itself. Within the universal AI literature, there are other works that go further and drop the dualism of traditional reinforcement learning for the (more realistic) physicalism where agents are contained within their own environment. In this case many complications arise which previous work tries to address. For example, in [48] the behavior of several agents able to modify their own source code is analyzed. In [49], Orseau et. al. presents space-time embedded definition the value function and intelligence, and in [50] Leike et. al. aims to solve the grain of truth (a self-referential problem of Bayesian agents in GRL, showing that there
8

---

is a non non-trivial class of environments for which the optimal Bayesian agent over that class is within
the class.
5.4 Self Prediction in Traditional RL
Recently traditional reinforcement learning has begun to embrace self-prediction. In [51] Predictions of Bootstrapped Latents (PBL) is presented as a method which can use predictive representations on multitask environments. [52] used Self- Self-Predictive Representations (SPR) to train agents to anticipate future latent states, which showed improvements on Atari games benchmarks. In [53], exploration in visually complex environments was streamlined with B BYOL-Explore using a bootstrapped prediction. Additionally, [54] underscores the challenges of representation collapse in self-predictive learning and introduces bidirectional learning to address this. Together, these studies underscore the evolving landscape of self- seff-predittvee strategies in traditional RL.
Discussion, Future Work and Limitations
Practical considerations for computing the mixture component in each step. Computing the Self-AIXI policy requires estimating Q-values using the Bayesian mixture policy ((ae)hex). Naively, this means evaluating each policy in the mixture and computing its respective posterior weight. However, more efficient schemes can be derived, e.g., similar to how the CTW algorithm computes the Bayesian mixture without explicitly evaluating each hypothesis and computing the (marginalizing) sum over hypotheses in each step.
Leveraging large sequence models. Powerful sequence predictors like large language models (LLMs) are the cornerstone of modern general AI due to their impressive zero- and few-shot per- formance [55-57]. An open question in AGI research is how leverage the strength of sequence prediction not only for environment modeling, but also to derive goal-directed policies; how to build agents from predictors. We have shown how to shift computational effort for planning (in AIXI) can be transferred into effort devoted to prediction in Self-AIX LeXf,AIX, making self -reeiiediition theoretically very well suited to exploit strong predictors such as LLMs. In contrast to similar ad-hoc approaches [58], Self-AIXI is derived from sound theoretical design principles and comes with theoretical guarantees.
Safety implications. Self-AIXI constitutes a theoretical blueprint for building powerful general Al agents that may be very suitable to leverage strong predictors, such as LLMs, in practice. The implications of such agents have recently been discussed in the philosophical and technical literature, and concerns regarding their safety have been raised [59, 60]. Self-AIXI comes with some interesting favorable safety properties. First and foremost, Self-AIXI derived from sound reasoning and decision-making principles: Bayesian posterior inference and rational optimization of rewards. Self- AIXI comes with well-understood theoretical model to study abstract properties, guarantees and bounds. An advantage over AIXI, by design, is the self- model of the agent, which can be analyzed on its own. The explicit separation of beliefs over the environment and posterior over the own policy leads to agent that is more interpretable and can be verified more easily compared to a monolithic agent where components are mixed. If the self-predictor used is not a Bayesian one, but instead some black box predictor, then both the guarantees of Self-AIXI and the guarantees on interpretability are no longer maintained, We strongly encourage an open and differentiated wider discussion on the safety of (universal) RL agents, and believe that theoretical models, like Self-AIXI, can facilitate this discussion by providing a formal and mathematically concrete formulation.
Limitations. Our theoretical results require that the Self-AIXI policy is part of the policy class under consideration, i.c., Ti E P (meaning that the mixture policy itself part of the policy class). Generally, if there is a policy in the policy class that is "close" to the optimal policy (in terms of minimal KL divergence), Self-AIXI will still perform well. This result can be stated formally using known formulations and bounds for Bayesian mixtures. We leave a detailed mathematical analysis for future work, since the aim of this work is to introduce the theory of Self-AIXI. Another issue is that Self-AIXI, like the original AIXI, is incomputable for environment classes required for (strict) universality. To tackle this, many practical approximations of AIXI have been proposed in the literature, which provide straightforward starting points for similar approximations for Self-AIXI

---

Designing and studying non-trivial practical approximations of Self-AIXI is beyond the scope of this paper.
Future work. On the theoretical side there are several promising directions of future work: explor- ing which non-trivial policy classes P satisfy as E P (or replacing this assumption); extending this work with a sampling-fins approach (e.g. Thompson Sampling). On the practical side the first step is to empirically demonstrate the performance of the self- prediction approach proposed this paper. We believe that especially when coupled with powerful modern predictors, e.g., transformer based sequence predictors, high-fidelity approximations of & and Ç are possible, which can lead to strong, general agents.
7 Conclusion
In this paper we presented Self-AIXI, theoretical framework for universal Al that extends AIXI by celf-prediction (the agent performs inference over its own policy). The result is an agent that matches AIXIS performance guarantees, while shifting the computational focus on prediction instead of planning. This makes Self-AIXI interesting for building general agents by leveraging recent breakthroughs sequence predictors, and combining them with RL in a sound fashion. Current approaches to do this, such as RL from human/artificial feedback (R (RLHF/RLAF) are quite limited (in terms of generality of the RL formulation) and do not come with optimality or universality guarantees. We believe our results to be an important cornerstone for building agents that go beyond zero- or few-shot transfer, towards rapid and data efficient RL.
Acknowledgments
We thank Tor Lattimore, Laurent Orseau and Anian Ruoss for their helpful feedback and insightful discussions.
References
[1] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2018.
[2] Ronald J Williams. Simple statistical sradient-following algorithms for connectionist reinforce- ment learning. Reinforcement learning, pages 5-32, 1992.
[3] John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Picter Abbeel. High- dimensional continuous control using generalized advantage estimation. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:/ arxiv. org/
www./////////oooooooooo/eeeeese/ abs/aab5.555 02438.
[4] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):5599553 -33333,, 2015.
[5] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International conference on machine learning, pages 1937. PMLR, 2016.
[6] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018
[7] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in games, 4(1):1 03:1-43,222 2012.
[8] Carlos E Garcia, David M Prett, and Manfred Morari. Model predictive control: Theory and practice-al survey, Automatica, 25(3):335-344 1989.
10

---

[9] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 550(7676):354-337 2017.
[10] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 16206419):1140-11144 2018.
[11] Julian Schritwieser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604 609, 2020.
[12] loannis Antonoglou, Julian Schrittwieser, Sherjil Ozair, Thomas K. Hubert, and David Silver. Planning in Stochastic Environments with a Learned Model. In International Conference on Learning Representations, March 2022.
[13] Andrei A Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distillation. arXiv preprint arXiv: 15/1v625 2015.
[14] Marcus Hutter. Universal artificial intelligence: Sequential decisions based algorithmic probability. Springer Science Business Media, 2004.
[15] Tom Everitt and Marcus Hutter. Universal artificial intelligence: Practical agents and fundamen- tal challenges. In Hussein A. Abbass, Jason Scholz, and Darryn J. Reid, editors, Foundations of Trusted Autonomy, chapter 2, pages 15-46. Springer, 2018. ISBN 978-3-319-64815-6 doi:
00.1007/978-3-319-68881
[16] Ray J Solomonoff. A formal theory of inductive inference, part Information and control, 7(1):
1 1-22, 1964.
[17] Samuel Rathmanner and Marcus Hutter. A philosophical treatise of universal induction. Entropy. 1376):1076-1136 2011. ISSN 1099-4300. doi: 10.3390/e 003390//1306000 33660776.
[18] Marcus Hutter. Convergence and loss bounds for bayesian sequence prediction. IEEE Transac- tions on Information Theory, 49(8):2061-206 2003.
[19] Marcus Hutter. On universal prediction and Bayesian confirmation. Theoretical Computer Science, 384(1):33-44 48, 2007. ISSN 0304-3975. doi: 10.10166j.css.2007.88
[20] Joel Veness, Kee Siong Ng, Marcus Hutter, and David Silver. Reinforcement learning via AIXI approximation. In Proc. 24th AAAI Conference Artificial Intelligence, pages 605-611, Atlanta, USA, 2010. AAAI Press. URL /eatt://areee www.vooggaaaaoooooeoo 1tt.:1117.222220 .209.
[21] Shane Legg and Marcus Hutter. Universal intelligence: A definition of machine intelligence. Minds and machines, 17(4):391-444 2007.
[22] Mareus Hutter. Self-optimizing and Pareto-optimal policies in general environments based on Bayes-mixtures. In Proc. /5th Annual Conf. on Computational Learning Theory (COLT'02), volume 2375 of LNAI, pages 364 179, Sydney, Australia, 2002. Springer. ISBN 978-3-540- URL
43836-6. doi: 10. 10.10077/3-540444355--2 0204040.
cs .s......... AI/
[23] Jan Leike. Nonparametric general reinforcement learning. PhD thesis, The Australian National University (Australia), 2016.
[24] Frans MJ Willems, Yuri M Shtarkov, and Tjalling J Tjalkens. The context-tree weighting method: Basic properties. IEEE transactions on information theory, 41(3):653 664, 1995. doi:
http://dx.doi.or/11.. http://kw.o..../11.110099///2000 10101111.18111111111
[25] J. Schmidhuber. Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable the limit. International Journal of Foundations of Computer Science, 13(4):587-612, 2002.

---

[26] Vladimir G Vovk. Prediction of stochastic sequences. Rossiiskaya Akademiya Nauk. Problemy Peredachi Informatsii. 25(4):35-49 1989.
[27] Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008.
[28] Jan Leike, Tor Lattimore, Laurent Orseau, and Marcus Hutter. On Thompson sampling and asymptotic optimality. In Proc. 26th International Joint Conf. on Artificial Intelligence (IJ- CAI'17), pages 10. 10.24963/jjcai.222 2016/888 7/688. URL petttp://arxite org/ abs 602 07905. ferences paper track.
Melbourne, Australia, 2017. ISBN 978-0-9992411 doi:
Best sister con-
[29] Jan Leike and Marcus Hutter. Bad universal priors and notions of optimality. Jour- nal of Machine Learning Research, W&CP: COLT, 40:1244-1259, 2015. ISSN 1532- 4435. URL http:://rxixii wwtp://wrgg//////b//o/oo/es/ /1000. 04931. Also presented at EWRL'15. htt.://www.woodrree..ooo///oo0..
[30] Tor Lattimore and Mareus Hutter. Asymptotically optimal agents. Proc. 22nd International Conf. Algorithmic Learning Theory (1), volume 6925 of LNAI, pages 368-382, Espoo, Finland, 2011. Springer. ISBN 1-642-24411-4, doi: 000007978-3-642-225 http: / arxiv org/ abs 5537.
2__ URL
[31] Michael K Cohen, Elliot Catt, and Marcus Hutter. Curiosity killed incapacitated the cat and the asymptotically optimal agent. IEEE Journal on Selected Areas in Information Theory, 2(2): 665-677, 2021.
[32] D. Blackwell and L. Dubins. Merging opinions with increasing information. Annals of Mathematical Statisties, 33:882-888 887, 1962.
[33] Shane Legg and Marcus Hutter. Ergodic mdps admit self-optimising policies. Technical report, Technical Report IDSIA-21-04 IDSIA, 2004.
[34] Joel Veness. Approximate universal artificial intelligence and self-play learning for games. PhD thesis, University New South Wales, Sydney, Australia, 2011.
[35] L. Orseau. Universal knowledge-seckinng agents. In Proc. 22nd International Conf. on Algorith- mic Learning Theory (ALT' II), volume 6925 of LNAI, pages 353-367, Espoo, Finland, 2011. Springer. doi:
[36] Laurent Orscau, Tor Lattimore, and Marcus Hutter. Universal knowledge-secking agents for stochastic environments. In Proc. 24th International Conf. on Algorithmic Learning Theory (ALT" 13), volume 8139 of LNAI, pages 158-172, Singapore, 2013. Springer. ISBN 978-3-642- 40934-9. doi:
01077/9788--64240933-5 12.
[37] Tor Lattimore and Marcus Hutter. Bayesian reinforcement learning with exploration. In Proc. 25th International Conf. on Algorithmic Learning Theory (AL.T" volume 8776 of LNAI, pages 170-184, Bled, Slovenia, 2014. Springer. ISBN 118-3-319-1166111 doi: 10. 1001/ 11883-399-11622-41
[38] T. Lattimore. Theory of General Reinforcement Learning. PhD thesis, Research School of Computer Science, Australian National University, 2014. URL httLhtttt//brrrrrr anu. edu adu.aul www.aaa/errrbbb335
[39] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):25-294 1933.
[40] Michael Cohen, Elliot Catt, and Marcus Hutter. A strongly asymptotically optimal agent in general environments. In Proc. 28th International Joint Conf. Artificial Intelligence (IJCA' 19), pages 2179-2186, Macao, China, 2019. ISBN 978-0-999241 1-4-1. doi: 10.24963/ 20199.20 URL http:/// http///axivvv.. org/ abs/ /1///1993111 01021.
[41] Joel Veness, Kee Siong Ng, Marcus Hutter, William Uther, and David Silver. monte-carlo aixi approximation. Journal of Artificial Intelligence Research, 40:95-142, 2011.
12

---

[42] Samuel Zhag, Tianyu Wang, and Kee Siong Ng. A direct approximation of aixi using logical state abstractions. In Advances in Neural Information Processing Systems.
[43] Jean-Bastien Grill, Florent Altché, Yunhao Tang, Thomas Hubert, Michal Valko, Ioannis Antonoglou, and Rémi Munos. Monte-carlo tree search as regularized policy optimization. In International Conference on Machine Learning, pages 3769-3778. PMLR, 2020.
[44] Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforce- ment learning. In International conference machine learning, pages 449-458. PMLR, 2017.
[45] Joel Veness, Mare Bellemare, Marcus Hutter, Alvin Chua, and Guillaume Desjardins. Compress and control. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[46] Mareus Hutter et al. Feature reinforcement learning: Part i, unstructured mdps. 2009.
[47] Sultan Majeed. Abstractions of general reinforcement learning. 1rX1v:2112.13404, 2021.
arXiv preprint
[48] Laurent Orseau and Mark Ring. Self-modification and mortality in artificial agents. In Interna- tional Conference on Artificial General Intelligence, pages 1-10. Springer, 2011.
[49] Laurent Orseau and Mark Ring. Space-time embedded intelligence. International Conference on Artificial General Inielligence, pages 209-218. Springer, 2012.
[50] Jan Leike, Jessica Taylor, and Benya Fallenstein. A formal solution to the grain of truth problem. In Proceedings of the Thirty-Secona Conference on Uncertainty Artificial Intelligence, pages 427-436 2016.
[51] Zhaohan Daniel Guo, Bernardo Avila Pires, Bilal Piot, Rémi Munos, and Mohammad Gheshlaghi Azar. Bootstrap latent theent-predictve representations for multitask reinforcement learning. In International Conference Machine Learning, pages 3875-3886. PMLR, 2020.
Grill, Florent Altché,
[52] Max Schwarzer, Ankesh Anand, Rishab Goel, R Devon Hjelm, Aaron Courville, and Philip Bachman. Data-efficient reinforcement learning with self-predictive representations. arXiv preprint arXiv:2007.059229 2020.
[53] Zhaohan Guo, Shantanu Thakoor, Miruna Pislar, Bernardo Avila Pires, Florent Altché, Corentin Tallec, Alaa Saade, Daniele Calandriello, Exploration by bootstrapped prediction. Advances in neural information processing systems, 35:31855-31870, 2022.
Grill, Yunhao Tang. et Byol-explore:
[54] Yunhao Tang, Zhaohan Daniel Guo, Pierre Harvey Richemond, Bernardo Avila Pires, Yash Chandak, Rémi Munos, Mark Rowland, Mohammad Gheshlaghi Azar, Charline Le Lan, Clare Lyle, et al. Understanding self-predictive learning for reinforcement learning. In International Conference Machine Learning, pages
PMLR, 2023.
[55] Jacob Devlin Ming-Wai Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, pages 4171-4186, 2019.
[56) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.022. 00301111.111......00 2022.
[57] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint wwXiv:2206.07682 2022.
[58] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems, 34:1 5009--50977 2021.
13

---

[59] Nick Bostrom. Superintelligene:: Paths, Dangers, Strategies. Oxford University Press, Inc., USA, 1st edition, 2014. ISBN 0199678111.
[60] Stuart Russell. Human compatible: Artificial intelligence and the problem of control. Penguin, 2019.
[61] Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in Games, 4(1):1-43, 2012. doi: 10.1 0011099/CIIIIG:22122216888 10.
[62] F.M.J. Willems, Y.M. Shtarkov, and T.J. Tjalkens. The context-tree weighting method: basic properties. IEEE Transactions on Information Theory, 41(():653-664 1995. doi: 10. 109/18. 382012.
14

---

A Proofs
Lemma 15 (A one-step good policy is close to optimal). Les A(h) E (Ax E)' fort 2 tu E N.
(v) V2² with
If _ max Q (h, a) VG < 3 Vt 2 to
and E m Ee ((e/ha)))((0 [ - (1 + a R A (hhae) V/ to
then E (h) < (11() A4 ス to provided 1 1 a < 1/7
Proof. Let 8 == 2 EA (h),, where h E (A E)' and E is short for E.
EA(h) = max Q (h, a) (h)
E max Qi (h, a) max Q (h, a) max Q2 - V (h)
E max Q h, a) Vē (h)l El max (2) max QF a))
(1)
3 + max Σ E(elha) (r + VVद (hae)) -mxx Σ E(elha) (r vV (hae))
< 8 + E max
(F Vg" (hae))
< + + (haae)
Taking suP:2t, on both sides implies 8 < 3 + 7(1 + 0d8 implies 6 3/(11-7( + a)).
Lemma 17 (Rg implies By + 0). If is such that
E [VV (hee) V2 (h=t)) ++ as 00.
then all μ M we have
By Ve (hett) - V52 (hct))
+ 00 as + 00.
Proof.
E7 [V (hee) Ve (M<t)) S - Ee [Ve (her) - Ve (hec)) 0 by the dominance of E(-) 2 w())u(-).
w(n)
Lemma 20 (V2'" + Vē implies Vp VA in p-expectation). If a is such that for all μ E M
E Ve (hea) - VT (hcc)] 0 as +
00. co.
and (yo 5et (hee)) 0 nMT aalmsst surely then we have
E VV (hee) - V (h2e)] +0 as +
Proof.
V7' (hee)) V7 (hec)]
|Iv (lec)) V (hee) + V5 (hea) - (har) + (T Vi (her)))
s Eg [ (hee) - VØ (hze)] + +E [ (hea) V (h=t)) + E [IVE (her) V (hee))
The second and third term go to 0 as t + oo by the assumptions and Lemma 3 with Lemma 13. The first term goes to as Doo (N=', _5T (her) + 0 -almost surely implies B Doolu'', ,5" [her)) +
and we have E7 [1 (Iee) - V/ (keee) < B [uo' .e" [M<es]
15

---

Theorem 22 (Self-AIXI is Self-optimizing), Let P be some environment. If there is policy and sequence of policies Ti. u2 ... all contained within P such that for all het we have Ve (h<c) 2 Ve th (her) - &t with Et + 0, for all v M
(het) (her) +0 as t 00 1² -almost surely
then
(h) ( + +0 as t 00 4º -amoost surely
I = vs and Equation 4 holds for all μ E M. then ms strongly usymptotically optimal in the class M.
Proof.
w(ulhee) (ha() Vi (h<e))
(5)
Σ w(vlhet) (bc() V (het))
(6)
NeM
Σ uoul)h (hea)
NeM
Σ [(Vllhtt (hatt
NEM
Σ (((ee)) -Ve (bect)))) +
Σ
w(vlhet) (Ve()) V (bcr)) +
(10)
PEM
0
(11)
Equation 6 comes from adding positive terms. Equations and 10 comes from the linearity of the value function. Equation comes from Ts being one step optimal then following and Equation comes from the assumptions. Lastly, comes from Equation 4 and [14, Lem.5.28ii.
w(p)het) lige is generated from μ²" (for more details Self-Optimiznng proof in [14]).
Therefore V (lice) Va (her) - 0 nm -lmost surely.
16

---

B Experimental Validation
In this section we heuristically evaluate the effect of self-modelling using the AIXI approximation provided by Veness et al. This AIXI approximation uses Monte-Carka Tree Search (MCTS) [61] and the Context Tree Weighting [62] technique respectively to approximate the expectimax planning and Bayesian environment learning components of the AIXI optimal agent. At each timestep the approximation performs a MCTS to estimate the action-value function with respect to its CTW- based environment model. We consider two agent configurations: MC-AIXI, which chooses each action uniformly at random in the rollout stage of MCTS, i.e. " (a, hhaa == 1/|A|, and matches identically the original configuration in [20]; and WCC-Sel-AIXX which uses Context Tree Weighting, i.e. # E
(a, hea) == CT let)), to predict the outcome of each MCTS decision.
Experimental Setup. For all experiments, we use a finite m- m-horizon undiscounted return setup, with each domain specific horizon choice given by Table [20]. The CTW depth parameter to both the environment model ( == cTW²) and the self-prediction model (C == CTW₂) was also chosen match Table 3 in [20]. We evaluated across 5 stochastic, partially observable and history dependent domains: Cheeze Maze, Kuhn Poker, 4x4 Grid, Tiger and Biased Seissor/Paper/Rock The description for each of these domains once again be found in [20]. Each environment was evaluated by performing a single online run across 10* timesteps; here a smaller number timesteps was used than in [20] that could better assess the transient effects performance improvement. At each timestep I, both agents pick either a random action with probability e, = 0.2 x 0.999', or otherwise return the estimated best action according to action-value estimates computed with 500 simulations.
Results. Figure shows learning curves for the Cheeze Maze, Tiger and 4x4 Grid domains respectively. The vertical axis shows the average reward per timestep obtained over the previous 2000 time steps. In these 3 domains the original MC-AIXI agent given the restricted data and computational budget described above, approaching optimal performance in each domain; note that optimal performance can be obtained too with the original MC-AIXI agent, albeit with more compute and data, as described in [20]. This matches the theory which states that both agents will converge optimal performance, but shows that self-modelling can, in some cases, converge to the optimal behavior more quickly. In two of the easier domains, ScissorPaperRoce and Kuhn Poker, there was no significant difference performance between the two methods. The final performance (as evaluated by the average reward per step over the final 2000 timesteps) of each agent configuration is shown in Table
that self saff-modeliing gives qualitative advantage over
Biased Scissor Paper Rock
Agent
Kuhn Poker
Cheese Maze
Tiger
4x4 Grid
MC-AIXI
1.98
0.17
-1.0
-0.29
0.0
MC-Self-AIXI
1.93
0.22
1.08
0.5
0.24
Table 2: Final performance of MC-AIXI- ATW and MC-Self-AIXI CTW after 10 time steps.
17

---

Cheese Maze: Rolling mean reward over time
baseline
mele--odeliing
Rolling Mean Reward (window 2000)
0.5
-0.5
-1.0
-1.5
2000
3000
4000
5000
6000
7000
8000
9000
10000
Timestep
Tiger: Rolling mean reward over time
Rolling Mean Reward (window 2000)
-1-
-2
baseline
self-modelling
-5
2000
3000
4000
5000
7000
8000
9000
10000
Timestep
4x4 Grid: Rolling mean reward over time
baseline
modelling
Rolling Mean Reward (window 2000)
0.20
0.15
0.10
0.05
2000
3000
4000
5000
6000
7000
8000
9000
10000
Timestep
Figure 1: Rolling average reward per step for MC-AIXI (green) and MC-Self-AIXI (red).
18


Reviews:
[{"review_id": "eCYvTepCr3", "reviewer": "Reviewer_mKJS", "summary": "This paper focuses on the issue of inefficiency in planning for AIXI agent, particularly lacking an alternative universal agent that maximally exploits learning and distillation. To address the issue, this work proposed a new method, named self-AIXI, that maximally exploits self-prediction instead of planning by doing exact Bayesian inference on the policy space. Further, theoretical results were provided to prove that self-AIXI's Q-values can converge to AIXI's Q-values asymptotically.\n", "questions": "- See my comments in the weakness.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n- It's an interesting work for self-AIXI to consider both planning and learning to improve the efficiency and guarantee the optimal solution and its convergence to the gold-standard AIXI agent. Besides, this work also provides theoretical analysis for the optimality condition, compared to the existing empirically successful model-based reinforcement learning framework like MuZero. \n- The paper is well-written and I can read it smoothly.", "weaknesses": "Weaknesses:\n- This is a theoretical paper, but only introducing the theory of self-AIXI might be a little bit less. It would be better if some preliminary results towards a concrete algorithm can be included in this work. This is because there exists some practical work for AIXI and model-based RL like MuZero (target to theoretical or/and empirical problems), so it's not quite clear why this self-AIXI is really needed, although there were some discussions shown in the paper. I do appreciate this work, so I'd like to hear more about this from the authors.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. \n* “It would be better if some preliminary results towards a concrete algorithm can be included in this work.”: We are conducting some proof-of-concept experiments with MC-AIXI-CTW, which will be included in the updated manuscript. Please see our main response for details. Additionally we have added more discussion to the paper towards bridging the gap between theory and practical algorithms.\n* “it's not quite clear why this self-AIXI is really needed”: We see Self-AIXI as an important step in the path to understanding the optimal behaviour of general agents. This theory shows us that optimal behaviour can be achieved with minimal planning, if a sufficiently powerful predictor is used."}, {"review_id": "WX42mzwh0m", "reviewer": "Reviewer_sXfu", "summary": "The paper proposes a Bayesian agent for reinforcement learning called Self-AIXI. Self-AIXI learns from its own Q-value maximizing actions and performs action prediction, instead of using extensive search to find optimal action at each step like AIXI. The paper proves that Self-AIXI converges to AIXI and therefore shares optimality properties of AIXI.", "questions": "I am not particularly familiar with reinforcement learning theory, but from a generalized perspective, I found the following points in the paper a little bit confusing. Hopefully, these questions might be helpful if the authors want to address a broader audience.\n\n* Self-prediction is defined in the paper as the process of predicting the action generated by the agent itself, but it does not seem intuitively clear where such prediction happens in the definition of Self-AIXI. \n\n* The authors also regard self-prediction as a form of learning, but it is not very explicit where the learning component is.\n\n* If one wants to optimize a parameterized policy, what would be the objective function? If the objective is to predict the action with max Q-value, why can AIXI not employ learning to predict its optimal action selected from planning?\n\nOther questions:\n\n* What does $\\gamma$ represent in Lemma 15? It does not seem very clear from the context.", "limitations": "The authors adequately addressed the limitations of the theory of Self-AIXI in their paper.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "A proof of optimality of policy distillation methods: by proving the optimality of Self-AIXI, a theoretical guarantee is given to policy distillation methods, which could enable further analysis of the theoretical properties of such approach and help design practical methods with a guarantee.\n\nExtending the theory of general reinforcement learning to include learning: the policy learning component is introduced into the theoretical framework of RL agents, which could potentially enable analysis of strong RL agents based on extensive learning.\n\nTheory framework is clear and easy to follow: the definition of Self-AIXI and the proof framework is presented neatly and very easy to follow. The proofs are straightforward and do not require advanced techniques.", "weaknesses": "A central condition of the main theorem might be too strong or hard to evaluate: the main theorem requires that $\\pi_S$ be a sensible off-policy that satisfies conditions of Lemma 15, but the authors leave the proof of the satisfiability as a conjecture. This would make it hard to evaluate the significance of the condition and consequently the significance of the main theorem.\n\nConnection between empirical discussion and theory work is kind of ambiguous: the authors try to motivate the  theory of Self-AIXI from empirical work on policy distillation, and terms such as \"learning\", \"distillation\" and \"self-prediction\" are used throughout the paper to bridge theoretical discussions and empirical practice. However, the connection between empirical claims such as \"method X uses learning\" and theoretical results of Self-AIXI seems ambiguous without a clear definition of such terms in mathematical language. It would make the connection much clearer if  \"learning\" and \"self-prediction\" could be formally defined within the framework of reinforcement learning.\n\n*Regarding originality and contribution over prior work, I would like to leave the assessment to other reviewers as I am not familiar with the related work.*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. \n* “the main theorem requires that $\\pi_S$ be a sensible off-policy that satisfies conditions of Lemma 15, but the authors leave the proof of the satisfiability as a conjecture. This would make it hard to evaluate the significance of the condition and consequently the significance of the main theorem.”: In response to the concerns about the satisfiability of $\\pi_S$, it's important to note that its satisfiability is intrinsically linked to the chosen model and policy class. While we acknowledge the importance of a comprehensive investigation into the categorization and conditions under which this can be achieved, such an exhaustive exploration is beyond the purview of this paper.\n* Connection between theory and empirical algorithms too ambiguous (“learning” and “self-prediction” would need a formal definition): we have added formal definitions for “learning” and self-prediction to the paper.\n\n**Questions:**\n* “Self-prediction is defined in the paper as the process of predicting the action generated by the agent itself, but it does not seem intuitively clear where such prediction happens in the definition of Self-AIXI.”: This prediction lies in the mixture zeta, this mixture uses the past actions in the history to model and predict the future actions of the agent.\n* “The authors also regard self-prediction as a form of learning, but it is not very explicit where the learning component is.”: The learning done in the self prediction is Bayesian learning as we use a Bayesian mixture as the self predictor.\n* “If one wants to optimize a parameterized policy, what would be the objective function? If the objective is to predict the action with max Q-value, why can AIXI not employ learning to predict its optimal action selected from planning?”: The goal of the agent is to achieve the maximal expected reward, defined by the value function. AIXI will take the optimal action from planning, AIXI is the optimal agent. Self-AIXI shows us that when implementing agents, we can use powerful predictors to assist (or almost completely remove) the planning component\n* “What does $\\gamma$ represent in Lemma 15? It does not seem very clear from the context.”: $\\gamma$ is the discount factor (see Definition 1)."}, {"review_id": "pnSNYnGAan", "reviewer": "Reviewer_AePK", "summary": "The paper introduces a reinforcement learning version of an agent\n(Self-Predictive Universal AI == Self-AIXI) that converges to the\nAIXI universal Bayes optimal agent. The advanage of the approach is \nit is based on learning/reinforcement learning rather than planning and\nthus opens up new avenues for practical approximations to the AIXI scheme.\nThe term 'self' is based on learning a more compact (distilled) model\nfor predicting the agent's actions.\nA good property-based comparison with other theoretical and practical implementations is given in table 1.\n", "questions": "It would be helpful if the theorems/lemmas/etc had a plain-English statement to help\npresent the concepts clearly as well as precisely. A table of symbols would also help.\n", "limitations": "Somewhat - the paper recognizes that the approach is still computtionally intractable.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The claim is based on a mathematical proof. I could not follow all of the details,\nbut the general structure of the argument and proof seemed sound.\n", "weaknesses": "This is a theoretical existence proof rather than an demonstation by implementation,\nand thus it is unclear whether there are benefits of the approach, eg: faster learner for\na given error rate, more accurate practical approximation to AIXI, etc. The paper \nstates that both AIXI and Self-AIXI in their pure form are computationally intractable.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. \n* “it is unclear whether there are benefits of the approach, eg: faster learner for a given error rate, more accurate practical approximation to AIXI, etc”: From a theoretical perspective the benefits are that we have shown how predictors can be used to assist the planning effort of the agent. We are conducting a proof-of-concept experiment (see general response) to determine if the self prediction of Self-AIXI can be used to improve an AIXI approximation.\n* “It would be helpful if the theorems/lemmas/etc had a plain-English statement to help present the concepts clearly as well as precisely. A table of symbols would also help.”: We have added plain-English statements of our main theorems and lemmas to the paper."}, {"review_id": "nGu0hgkBp0", "reviewer": "Reviewer_dcXk", "summary": "This paper presents a new universal Bayesian AI agent framework that uses reinforcement learning to predict its own learning to form incrementally better and ultimately optimal policies. The paper then shows theoretically that this agent, Self-AIXI, converges to the same policies as a planning based universal, Bayesoptimal agent, AIXI, thus showing that the learning based system itself will converge to optimal. The main contribution of the paper is a theoretical analysis of the self-predicting agent in the context of universal, Bayes-optimal agent frameworks. ", "questions": "My main question would be whether the authors see any direct  way in which the presented system would be practically applyable ? Outside the perview of universal AI, would there be subproblem domains for which this agent would be practical ? And how small would those have to be ? (Having such - even small - domains could make the paper of interest to a larger part of the community).", "limitations": "The authors very clearly state the main limitations of the preented work, which lie in the practicality of the approach and in the strong assumption they had to make for the self-optimization proof (and in particular that there currently are no practical environment distributions for which these assumptions hold).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a self-predicting agent that uses reinforcement learning to form a universal AI agent that learns an optimal policy in the Bayes sense over a distribution of environments. The formal analysis and proofs seem sound and the final result is of interest to persons in universal AI as it introduces a differnt approach to Bayes optimal agents that could further down lead to more practical agents in this class. While (as acknowledged by the authors) self-AIXI right now is not a practical framework and the assumptions in the self-optimization proof are very strong, the paper provides a point and potential direction and stepping stone towards more practical universal AI.", "weaknesses": "The main weaknesses of the paper are that it is mainly a formal, theoretical endeavor with no direct known (or anticipated) practical applications. This is clearly acknowledged by the authors in terms of the practical application as well as there not being any practical classes of environments for which the assumptions of the central self-optimization proof would hold.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. \n* “mainly a formal, theoretical endeavor with no direct known (or anticipated) practical applications”: As the reviewer correctly states, the main goal of this paper is to work out the theory for self-prediction and distillation in the limit. We can anticipate practical applications, as is demonstrated by the experiment described in the general response.\n* “My main question would be whether the authors see any direct way in which the presented system would be practically applyable ?”: We are conducting a proof-of-concept experiment (see general response) to determine if using a self predictor can improve performance of an AIXI approximation."}, {"review_id": "sYcr50lW9f", "reviewer": "Reviewer_xEuK", "summary": "The authors propose Self-AIXI, an extension of the universal Bayes-optimal agent (AIXI), combining it with self-prediction for use in combination with reinforcement learning instead of planning. They provide theoretical evidence that Self-AIXI inherits optimality properties from AIXI.", "questions": "- I failed to find any motivation for increasing the complexity of AIXI even more by incorporating reinforcement learning instead of planning. Could you elaborate on that?\n\nFurther comments / suggestions:\n\n- The related work presented in 5 seems to have little relation to Self-AIXI and could be extended.\n- Table 1 could be explained more extensively. \n- Regarding the safety implications mentioned in 6, i tend to disagree, as the addition of further (possilby blackbox) models mostly hinders interpretability, thus safety-critical validation.", "limitations": "Limitations are clearly pointed out.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- Overall, the paper is well-written and theoretically sound. \n- All claims are supported by extensive theoretical analysis.", "weaknesses": "- As Self-AIXI inherits its optimality properties from AIXI, the overall contriubution seems limited. \n- Even though the proposed extension seems interesting, I fail to find proper motivation or clear comunication of the sigificance of the contribution by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. \n* “As Self-AIXI inherits its optimality properties from AIXI, the overall contribution seems limited.”: We argue that one of the key results (and the main effort) of our paper is to show that Self-AIXI can perform equally optimally and achieve AIXI optimality. Once we can show that “Self-AIXI” converges to “AIXI” (in the sense spelled out in the paper), this does allow us to “inherit” many known optimality properties of AIXI without having to prove these properties again for Self-AIXI. Constructing an algorithm that improves over AIXI’s optimality properties would indeed be a significant contribution to the field of (universal) AI, but unless there are substantial flaws in the optimality proofs of AIXI this is impossible.\n* “I fail to find proper motivation or clear communication of the significance of the contribution by the authors.”: We have added this motivation and statement of significance to the introduction and main contributions of our paper.\n* “I failed to find any motivation for increasing the complexity of AIXI even more by incorporating reinforcement learning instead of planning. Could you elaborate on that?”: In this work we have demonstrated an alternate formula for an optimal agent. The complexity that is added from self prediction is taken away from additional planning. While we do have some added complexity in terms of the self model, since we are already modeling the environment the added complexity will be just our model complexity, and we will save not having to do the traditional planning.\n* “The related work presented in 5 seems to have little relation to Self-AIXI and could be extended.”: We would like to kindly ask whether the reviewer has any particular references in mind?\n* “Table 1 could be explained more extensively.”: We have expanded our explanation of Table 1.\n* “Regarding the safety implications mentioned in 6, I tend to disagree, as the addition of further (possilbly blackbox) models mostly hinders interpretability, thus safety-critical validation.”: We have expanded our safety discussion by this point raised by the reviewer."}]

Author rebuttal:
We thank the reviewers for their helpful comments. We are pleased to see that all reviewers found our paper easy to read (giving the maximum score of 3 for presentation), and all reviewers consider the theoretical claims and analysis sound and easy to follow. We respond to comments shared by reviewers in this general response and also provide a detailed response to each reviewer individually under their reviews. 

The main criticism, shared by reviewers, is that it is difficult to connect the theory to concrete implementations and applications. We understand this criticism, which applies to most theoretical work in universal AI, and want to emphasize that the main goal of this manuscript is to provide a sound theoretical construction and analysis of an alternative to the planning-centric approach, enabling in theory the development of more efficient and practical universal AI agents. We strongly agree with dcXk: “the paper provides a point and potential direction and stepping stone towards more practical universal AI.”. Closing the gap towards practical implementations is the next critical step in this line of research, but we believe that this requires quite a bit of setup and clarification that deserves a full separate publication. To show that the practical impact of the theory is not completely beyond reach, we are conducting some proof-of-concept experiments with Monte Carlo AIXI Context Tree Weighting (MC-AIXI-CTW)[1]. In these experiments we are comparing a Self-AIXI approximation with an AIXI approximation. The AIXI approximation is the base MC-AIXI-CTW, and the Self-AIXI approximation is MC-AIXI-CTW equipped with a self predictor (CTW predicting its own actions used within the MC rollout). This comparison is done on the environments in [1].

We want to thank the reviewers for pointing out parts of the manuscript that can be improved, in particular the clarification of Lemma 15 (sXfu), the formal definitions of “learning” and “self-prediction” (sXfu),motivation for incorporating reinforcement learning (xEuK), and plain-English statements of the main theorems and lemmas (AePK). We have also added a discussion on how to bridge the gap towards practical applications (dcXk) and concrete algorithms (mKJS).

[1] Veness, J., Ng, K. S., Hutter, M., Uther, W., & Silver, D. (2011). A Monte-Carlo AIXI approximation. Journal of Artificial Intelligence Research, 40, 95-142.

Meta-review: This paper introduces a new 'universal' Bayesian AI agent framework that uses RL to predict its own learning and incrementally obtain better—and ultimately optimal—policies. In particular, the paper introduces a new method, called self-AIXI, that maximally exploits self-prediction instead of planning by performing exact Bayesian inference on the policy space. The authors prove that this approach converges to the same policies as universal planning-based, Bayes-optimal agents (AIXI), thereby showing that their novel learning-based system will also converge to optimal solutions. This paper's main contribution is a theoretical analysis of the self-predicting agent in the context of universal, Bayes-optimal frameworks.

The reviewers agree that taking into account both planning and learning to improve efficiency (while guaranteeing optimality and convergence to the gold-standard AIXI solution) is interesting. Furthermore, reviewers also acknowledged the importance of this work's theoretical analyses regarding the optimality condition, compared to existing—and empirically successful—model-based RL frameworks such as MuZero.

A few concerns were raised. First, many reviewers—although aware of the correctness of the paper's theoretical results—argued that this work's practical significance remains vague and unclear. They understand that this is a theoretical paper but argued that by only introducing the theory of self-AIXI, it is challenging for readers to assess its relevance to the field. During the discussion, it was brought up that it would have been better if preliminary results towards a concrete algorithm could have been included. After all, there exists practical work (which target both theoretical and empirical problem) for AIXI and model-based RL like MuZero, and so it is not entirely clear why/when/whether self-AIXI is needed or advantageous compared to existing approaches. Another reviewer was concerned with a central condition of the main theorem, which they believe might be too strong or hard to evaluate. In particular, the main theorem requires that $\pi_S$ satisfy the conditions of Lemma 15, but the authors leave the satisfiability proof as a conjecture. This makes it difficult to evaluate the significance of this condition and, consequently, the significance of the main theorem itself. Finally, many reviewers commented on how adding plain English explanations of the theorems would help clarify many points discussed in this paper and clarify its contributions. As it is, there was a consensus that readers may likely have trouble following the claims and results presented in this work and, consequently, properly evaluating its relevance.

Having said that, the reviewers acknowledged this work's contributions while emphasizing the points that need improvement before publication. They encouraged the authors to explore these points and address all limitations that were brought up in the reviews when preparing an updated version of this paper.
Decision: Accept (poster)