Paper deep dive
A Model-Free Universal AI
Yegon Kim, Juho Lee
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/20/2026, 9:00:51 AM
Summary
This paper introduces Universal AI with Q-Induction (AIQI), a model-free reinforcement learning agent that performs universal induction over distributional action-value functions. Unlike traditional model-based agents like AIXI, AIQI learns directly from experience without maintaining an explicit environment model. The authors prove that under a 'grain of truth' condition, AIQI achieves strong asymptotic epsilon-optimality and asymptotic epsilon-Bayes-optimality in general reinforcement learning environments. The work also demonstrates that these proof techniques can be applied to show the asymptotic epsilon-optimality of Self-AIXI without ad-hoc assumptions.
Entities (7)
Relation Signals (6)
AIQI → isa → Model-Free Agent
confidence 98% · AIQI is the first model-free agent proven to be asymptotically ε-optimal in general RL.
AIQI → achieves → Strong Asymptotic ε-Optimality
confidence 95% · Under a grain of truth condition, we prove that AIQI is strong asymptotically ε-optimal...
AIXI → isa → Model-Based Agent
confidence 95% · all established optimal agents, including AIXI, are model-based...
AIQI → contrastswith → AIXI
confidence 92% · In contrast, the dominant paradigm in practical RL is model-free... AIQI is a model-free agent...
AIQI → uses → Universal Induction
confidence 90% · AIQI performs universal induction over distributional action-value functions...
Proof Techniques → appliedto → Self-AIXI
confidence 85% · We also apply our novel proof techniques to show asymptotic ε-optimality of Self-AIXI...
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In general reinforcement learning, all established optimal agents, including AIXI, are model-based, explicitly maintaining and using environment models. This paper introduces Universal AI with Q-Induction (AIQI), the first model-free agent proven to be asymptotically $\varepsilon$-optimal in general RL. AIQI performs universal induction over distributional action-value functions, instead of policies or environments like previous works. Under a grain of truth condition, we prove that AIQI is strong asymptotically $\varepsilon$-optimal and asymptotically $\varepsilon$-Bayes-optimal. We also apply our novel proof techniques to show asymptotic $\varepsilon$-optimality of Self-AIXI without any ad-hoc assumptions. Our results significantly expand the diversity of known universal agents.
Tags
Links
- Source: https://arxiv.org/abs/2602.23242v4
- Canonical: https://arxiv.org/abs/2602.23242v4
Trouble viewing inline? Open PDF directly →
Full Text
76,803 characters extracted from source content.
Expand or collapse full text
A Model-Free Universal AI Yegon Kim 1 Juho Lee 1 1 Graduate School of AI, KAIST, Seoul, South Korea Abstract In general reinforcement learning, all established optimal agents, including AIXI, are model-based, explicitly maintaining and using environment mod- els. This paper introduces Universal AI with Q- Induction (AIQI), the first model-free agent proven to be asymptoticallyε-optimal in general RL. AIQI performs universal induction over distributional action-value functions, instead of policies or en- vironments like previous works. Under a grain of truth condition, we prove that AIQI is strong asymptoticallyε-optimal and asymptoticallyε- Bayes-optimal. We also apply our novel proof tech- niques to show asymptoticε-optimality of Self- AIXI without any ad-hoc assumptions. Our results significantly expand the diversity of known univer- sal agents. 1 INTRODUCTION The theory of general reinforcement learning [GRL; Latti- more, 2014] provides a framework for studying agents in the most general class of environments, those that satisfy only minimal structural assumptions. In this setting, AIXI [Hut- ter, 2005] is a foundational theoretical model: it combines universal induction [Solomonoff, 1964a,b] with sequential decision theory [Von Neumann and Morgenstern, 1944, Bell- man, 1957] to define a Bayes-optimal agent. Although AIXI is uncomputable, it serves as a useful theoretical model of powerful goal-driven AIs [Orseau and Ring, 2012a, Everitt et al., 2016], and has also been used to define a universal measure of intelligence, called the Legg-Hutter intelligence [Legg and Hutter, 2007]. Interestingly, AIXI and all other established optimal agents in GRL [Lattimore and Hutter, 2014, Leike et al., 2016a, Cohen et al., 2019, Catt et al., 2023], otherwise known as universal agents or universal AI, are model-based: they ex- plicitly infer and make use of a model of the environment (a world model). In contrast, the dominant paradigm in prac- tical RL is model-free, learning value functions or policies directly from experience [Watkins, 1989, Williams, 1992, Rummery and Niranjan, 1994, Konda and Tsitsiklis, 1999]. Showing that a model-free algorithm is optimal in GRL has therefore remained elusive and has been repeatedly high- lighted as an open problem [Everitt and Hutter, 2018b, Catt, 2022, Hutter et al., 2024]. In this paper, we present Universal AI with Q-Induction (AIQI), a model-free agent that performs universal induc- tion over return-predictors, objects similar to distributional Q-values [Bellemare et al., 2017]. AIQI is essentially an ε-greedy, on-policy distributional Monte Carlo control algo- rithm. Under a grain of truth condition [Kalai and Lehrer, 1993], we prove that AIQI achieves strong asymptoticε- optimality and asymptoticε-Bayes-optimality in GRL. Our proof techniques can also be used to show asymptoticε- optimality of Self-AIXI without incurring ad-hoc assump- tions such as in the proof by Catt et al. [2023]. Our results significantly expand the class of known universal agents, and provide a blueprint for the analysis of other policy itera- tion algorithms in general environments. 2 BACKGROUND 2.1 GENERAL REINFORCEMENT LEARNING We establish the basic notation for general reinforcement learning. We also provide a summary of all the important symbols in § A. LetA,O, andR⊆ [0, 1]denote the finite sets of actions, observations, and rewards, respectively. The percept space isE := O×R, and a historyh 1:t ∈ H := (A×E ) ∗ is a sequence of actions and percepts. We write h 1:t = a 1 e 1 ...a t e t for the history up to timet.H t := (A × E ) t denotes the set of all histories up to timet. A policyπ :H→ ∆Amaps histories to action distributions, while an environmentν :H×A→ ∆Emaps history-action pairs to percept distributions. When policyπinteracts with Accepted for the 42 nd Conference on Uncertainty in Artificial Intelligence (UAI 2026). arXiv:2602.23242v4 [cs.AI] 13 Jul 2026 environment ν, they induce a distribution ν π overH t : ν π (h 1:t ) := π(a 1 )ν(e 1 |a 1 ) · π(a t |h <t )ν(e t |h <t a t ) = Q 1≤i≤t π(a i | h <i ) Q 1≤i≤t ν(e i | h <i a i ) = π(a 1:t ∥ e <t )ν(e 1:t ∥ a 1:t ) This is a valid distribution, that is, the probabilities sum to 1 across all historiesh 1:t . A direct consequence is that for a deterministic policy π ′ , X e 1:t ∈E t ν (e 1:t ∥ π ′ (e <t )) = 1,(1) whereπ ′ (e <t )is the sequence of actionsa 1:t taken byπ ′ under fixed perceptse <t . We also define the sample space Ω := (A×E ) ∞ , which consists of all infinite action-percept sequencesh. Every historyh 1:t is a prefix of some outcome h. Given a discount factorγ ∈ (0, 1), the (full) return at timet is defined as R t := (1− γ) ∞ X k=0 γ k r t+k , where1− γ = P ∞ k=0 γ k −1 ensures that returns lie in [0, 1], like the rewards. This definition assumes a geomet- ric discount, and we discuss the generalization to general discount sequences in § E. The value function for policy π in environment ν is V π ν (h <t ) := E π ν [R t | h <t ], whereE π ν is the expectation with respect toν π . The optimal value is defined asV ∗ ν = sup π V π ν , and an optimal policyπ ∗ ν is any policy that achieves this supremum. The action-value, or Q-value function, is Q π ν (h <t ,a t ) := E π ν [R t | h <t a t ]. Value functions satisfy the Bellman equations, which allow us to express one with the other: V π ν (h <t ) =E a t ∼π(·|h <t ) [Q π ν (h <t ,a t )] Q π ν (h <t ,a t ) =E e ′ t ∼ν(·|h <t ,a t ) (1− γ)r t + γV π ν (h ′ <t+1 ) Obtaining the full return requires simulating or experiencing an infinite length trajectory. Given some horizon length H ∈ Z + , the H -step return is defined as R t,H := (1− γ) H−1 X k=0 γ k r t+k , which can be computed withHsteps of agent-environment interactions. TheH-step value function is defined as V π ν,H (h <t ) := E π ν [R t,H | h <t ]. Finally, we define the ef- fective horizon as follows. Definition 2.1 (Effective horizon). Forη > 0, theη- effective horizon is H(η) := min ( H ∈ Z + (1− γ) ∞ X k=H γ k ≤ η ) . One can show that theH(η)-step return differs from the full return by at mostη, and likewise for the value function: R t − R t,H(η) = (1− γ) P ∞ k=H(η) γ k r t+k ≤ η. 2.2 AIXI To define AIXI, we first need to introduce the mixture envi- ronment ξ. Definition 2.2 (Mixture environment). For a countable en- vironment classMand a prior distributionw(ν) > 0over the environmentsνinM, the mixture environmentξis de- fined as the unique environment that satisfies ξ(e 1:t ∥ a 1:t ) = X ν∈M w(ν)ν(e 1:t ∥ a 1:t ). Equivalently, ξ π (·) = P ν w(ν)ν π (·) for any policy π. AIXI is then defined as the optimal policy in the mixture environmentξ. By its definition, AIXI is the Bayes-optimal agent with respect to the prior w(ν). Definition 2.3 (AIXI). AIXI is the optimal policyπ ∗ ξ in the mixture environment ξ: π ∗ ξ (h <t ) := arg max a Q ∗ ξ (h <t ,a). 3 UNIVERSAL AI WITH Q-INDUCTION We present Universal AI with Q-Induction (AIQI), a model- free approach to general reinforcement learning. For a discretization levelM ∈ Z + , theM-discretizedH- step return at time t is defined as z t := ⌊MR t,H ⌋ M , z t ∈Z := 0, 1 M ,..., M − 1 M . Note thatz t is an approximation ofR t,H whose error gets smaller asM → ∞. More precisely, it always holds that R t,H − z t < 1/M. We choosez t as the target of prediction instead ofR t,H . Although this choice isn’t necessary for our case of geometric discounting, there exist general discount sequences (§ E) whereR t,H can take an infinite number of possible values, which would complicate our analysis, and also the implementation. We would like to be able to predict the discretized return z t conditioned on any historyh <t and actiona t . One can naturally consider augmenting the history with returns, ...a t−3 z t−3 e t−3 a t−2 z t−2 e t−2 a t−1 z t−1 e t−1 a t , which would be passed in to a Bayesian sequence predictor to predictz t . However, a complication arises: computing the ground truth returnz t−1 requires the yet to be observed rewardr t ine t . Similarly, the returnsz t−H+1 ,...,z t−1 are all unavailable at timet. Therefore, instead of augmenting the sequence with returns at every step, we augment with a period N ≥ H , at only the positions i≡ t (mod N ): ...a t−2N z t−2N e t−2N ...a t−N z t−N e t−N ...a t−1 e t−1 a t . Then, the augmented returns require rewards at times only up tot− N + H− 1≤ t− 1, which are all available. Why we don’t simply considerN = Hwill be revealed in the proof of Lemma 4.2. The periodically augmented sequence can be passed in to a Bayesian sequence predictor, to predict the next return z t . We formalize this below. Given an augmentation periodN ≥ H, the augmented sample space associated with phasen∈0,...,N − 1, is ̃ Ω (n) := ∞ Y i=1 B (n) i , B (n) i := ( A×Z ×E, i≡ n (mod N ), A×E,otherwise. In other words, an augmented outcome ̃ h (n) ∈ ̃ Ω (n) contains some ̃z i k ∈ Zat the periodic positionsi k = n + kN, in betweena i k ande i k . Note that these augmented returns do not necessarily have to match the ground truth returnsz i k computed withr i k :i k +H−1 , in order for ̃ h (n) to qualify as an element of ̃ Ω (n) . We call an augmented outcome ̃ h (n) “valid” if its augmented returns match the ground truth returns. The prefix ̃ h (n) 1:t is called an augmented history. The set of aug- mented histories is denoted ̃ H (n) , and the set of augmented histories up to time t is denoted ̃ H (n) t . A return-predictor with phasenis any mappingφ : S i≡n ( ̃ H (n) i−1 ×A)→ ∆Z. The domain consists exactly of all phasenaugmented histories that end exactly at positions where the augmented return ̃z i should come next. We define the mixture return-predictor, like the mixture environment in Definition 2.2. Definition 3.1 (Mixture return-predictor). Given a class P n of phasenreturn-predictorsφ, and a prior distribution ω n (φ), a mixture return-predictorψ n is the unique phasen return-predictor that satisfies K Y k=0 ψ n ( ̃z i k | ̃ h (n) <i k a i k ) = X φ∈P n ω n (φ) K Y k=0 φ( ̃z i k | ̃ h (n) <i k a i k ), for all K ≥ 0, where i k = n + kN . Equivalently,ψ n ( ̃z i k | ̃ h (n) <i k a i k )is given by the posterior predictive distribution X φ∈P n ω n (φ| ̃ h (n) <i k−1 a i k−1 ̃z i k−1 )φ( ̃z i k | ̃ h (n) <i k a i k ), with the posterior weights ω n (φ| ̃ h (n) <i k a i k ̃z i k ) updated to ω n (φ| ̃ h (n) <i k−1 a i k−1 ̃z i k−1 ) φ( ̃z i k | ̃ h (n) <i k a i k ) ψ n ( ̃z i k | ̃ h (n) <i k a i k ) , starting withω n (φ| ε) = ω n (φ)whereεdenotes the empty string. In other words, by conditioning the mixtureψ n on a history, we are implicitly performing Bayesian inference over the return-predictors φ. Letaug n : Ω ,→ ̃ Ω (n) be the injective mapping that aug- ments an outcomehto its corresponding valid augmented outcomeaug n (h), by inserting the true returnsz i k com- puted with the rewardsr i k :i k +H−1 inh. Under a certain condition, a historyh <t uniquely determinesaug n (h) <t regardless ofh t:∞ , and in that case we abuse the notation aug n to also denote the mappingaug n (h <t ) = aug n (h) <t . Fortunately, we can state this condition explicitly as: (t− 1− n) modN ≥ H − 1.(2) This is because the latest indexi ≡ n (mod N )smaller thantis exactlyt− 1− (t− 1− n) modN, and the return at this index requires rewards at times up tot− 1− (t− 1− n) modN + H− 1, which is smaller thantif and only if Eq. 2 holds. In other words, all the rewards required for augmenting with the true returnsz i k are available inh <t . Note that Eq. 2 is trivially satisfied ifn = t modN. We can hence define a unified predictor, that abstracts away the periodic augmentation. Definition 3.2 (Unified return-predictor). Given a collection ofNmixture return-predictorsψ n 0≤n<N , the unified predictor ψ :H×A→ ∆Z is given by ψ( ̃z t | h <t a t ) := ψ n ( ̃z t | aug n (h <t )a t ) where n = t modN . Next, we define AIQI as follows. We also provide a pseu- docode in Algorithm 1. Definition 3.3 (AIQI). Fix a return horizonH, a discretiza- tion levelM, an augmentation periodN ≥ H, an explo- ration rateτ > 0, and a unified predictorψ. Let the Q-value estimate given history h <t be ˆ Q(h <t ,a t ) = X ̃z t ∈Z ̃z t · ψ( ̃z t | h <t a t ). AIQI, denotedˆπ H,M,N,τ ψ orˆπ, chooses the action that maxi- mizes this estimate, with random exploration rate τ : ˆπ(a| h <t ) := (1− τ )1 [a = a ∗ ] + τ/|A|, wherea ∗ = arg max a t ˆ Q(h <t ,a t ) . We allow for stochastic tie-breaking when multiple actions maximize ˆ Q. Algorithm 1 Universal AI with Q-Induction (AIQI) Require:Return horizonH, discretization levelM, aug- mentation periodN ≥ H, exploration probabilityτ, set of unified predictor ψ 1: History h <1 ← ε, time t← 1 2: loop 3:for each action a∈A do 4: ˆ Q(h <t ,a)← P ̃z∈Z ̃z· ψ( ̃z | h <t ,a) 5:end for 6: a ∗ ← argmax a∈A ˆ Q(h <t ,a) 7:Sample p∼U [0, 1] 8:if p < 1− τ then 9:a t ← a ∗ ▷ Exploit 10:else 11:a t ∼U (A)▷ Explore 12:end if 13:Execute a t , observe e t 14: h <t+1 ← h <t a t e t 15: t← t + 1 16: end loop Note that AIQI doesn’t simulate the environment or plan for the future. Instead, AIQI directly predicts its own action- value, and at every step chooses the action that maximizes it. As evidence accumulates, the value predictions become more and more accurate. In the limit, AIQI chooses the action that maximizes its true action-value, and will keep doing so in all future steps, thereby turning into a globally optimal policy. Another way to look at AIQI is that it is per- forming policy evaluation at every step, treating the whole trajectory as having been generated by a single policy, and performing policy improvement in choosing the next action. As is common in the universal AI literature, AIQI faces the grain of truth (self-referential) problem [Kalai and Lehrer, 1993, Leike et al., 2016b, Meulemans et al., 2025, Wyeth et al., 2025]. Roughly speaking, every mixture return- predictorψ n inψhas to contain in its class the true condi- tional return distribution under the AIQI policyˆπ ψ , which itself depends on ψ. The formal statement is given below. Definition 3.4 (Grain of truth). Fix the AIQI parameters H,M,N,τ. A unified predictorψhas a grain of truth w.r.t. environmentνif: everyψ n is a mixture of a classP n that contains the return-predictor φ ∗ given by φ ∗ ( ̃z i | ̃ h (n) <i a i ) = ν ˆπ (z i = ̃z i | h <i a i ), i≡ n (mod N ), whereˆπ = ˆπ H,M,N,τ ψ and the right hand side is the condi- tional return distribution under ν ˆπ . A nontrivial solution can be obtained by fixing a reflective oracleO[Fallenstein et al., 2015, Leike et al., 2016b, Wyeth et al., 2025], settingP n to be the class of allO-estimable return-predictors, and assuming thatνisO-estimable. Un- der this setup, the AIQI policyˆπisO-estimable, and φ ∗ = ν ˆπ is alsoO-estimable, hence insideP n . Allowing for stochastic tie-breaking in Definition 3.3 is essential for the use of reflective oracles. We now introduce a notion of optimality that AIQI will be shown to satisfy. It is a more lenient form of strong asymptotic optimality, which is one of the strongest forms of optimality considered in the universal AI literature. Definition 3.5 (Strong Asymptoticε-Optimality). Given ε > 0and a class of environmentsM, a policyπis strong asymptotically ε-optimal if, for all environments ν ∈M, lim sup t→∞ V ∗ ν (h <t )− V π ν (h <t )≤ ε, ν π -a.s. It has been shown by Lattimore and Hutter [2011, Theo- rem 8] that any deterministic policy, including AIXI, is not strong asymptotically ε-optimal for all ε < 1/4. 4 RESULTS The aim of this section is to prove that: •For arbitrarily smallε > 0, one can choose parame- tersH,M,N,τ,ψwith which AIQI satisfies strong asymptotic ε-optimality. (Theorem 4.6) •With the same choice of parameters, AIQI is asymptot- icallyε-optimal in the mixture environmentξ. (Theo- rem 4.8) • In contrast to AIXI, AIQI is not necessarily self- optimizing—a property that roughly translates to “off- policy asymptotic optimality”. (Theorem 4.10) Notably, we do not invoke any novel, ad-hoc assumptions in proving our results. The list of notations can be found in § A, and omitted proofs are in § B. We have also per- formed experiments with a computable approximation of AIQI, which we report in § F. We also show in § 5 that our novel proof techniques can be applied to the analysis of Self- AIXI [Catt et al., 2023], to get rid of strong assumptions such as off-policy sensibility. 4.1 CONVERGENCE OF RETURN-PREDICTOR First, we show that the unified return-predictorψconverges to the true return-predictorφ ∗ = ν π , when conditioned on increasingly longer histories generated byν π . A useful analytic device is the total variation (TV) distance. Given two probability measuresPandQdefined on a measurable space (Ω,F ), the TV distance is defined as D(P,Q) := sup E∈F |P (E)− Q(E)|. An elementary property of TV distance is that, for a count- able setE i of pairwise disjoint events, P i |P (E i )− Q(E i )|≤ 2· D(P,Q).(3) Given an environmentνand a policyπ, define the phase naugmented distribution ̃ν π n := ν π ◦ aug −1 n as the push- forward ofν π byaug n . We can express ̃ν π n as a product of conditional probabilities whose dependencies respect the written order in ̃ h (n) = a 1 e 1 ...a n ̃z n e n ... , as follows: ̃ν π n ( ̃ h (n) ) = Y i ̃ν π n (a i | ̃ h (n) <i ) Y i̸≡n ̃ν π n (e i | ̃ h (n) <i a i ) · Y i≡n ̃ν π n (e i | ̃ h (n) <i a i ̃z i ) Y i≡n ̃ν π n ( ̃z i | ̃ h (n) <i a i ). (4) Note that the above characterization of ̃ν π n is informal, as ̃ν π n ( ̃ h (n) )is just 0 for most ̃ h (n) . A proper characterization would involve ̃ν π n ( ̃ h (n) <t )and all products indexed up toi = t− 1. We use the informal notation for brevity. The last factor in Eq. 4 is simplyν π (z i = ̃z i | h <i a i ), which we abbreviate asν π ( ̃z i | h <i a i ). Let us also abbreviate the first three factors in Eq. 4 as ̃ν π n (h∥ ̃z i≡n ), so that ̃ν π n ( ̃ h (n) ) = ̃ν π n (h∥ ̃z i≡n ) Y i≡n ν π ( ̃z i | h <i a i ).(5) Letπbe the AIQI policyˆπwith some parametersH,M,N,τ, ψ. Suppose its mixture return-predictorψ n inψis a mixture of return-predictors including φ ∗ given by φ ∗ ( ̃z i | ̃ h (n) <i a i ) = ν π ( ̃z i | h <i a i ), i≡ n (mod N ), which is exactly the grain of truth condition. Then, define q n ( ̃ h (n) ) := ̃ν π n (h∥ ̃z i≡n ) Y i≡n ψ n ( ̃z i | ̃ h (n) <i a i ), which is Eq. 5 withν π = φ ∗ replaced byψ n . Intuitively, we want to show that our mixtureψ n converges toφ ∗ , and we do so by first showing that q n converges to ̃ν π n . By the definition of a mixture in Definition 3.1, q n ( ̃ h (n) )≥ ̃ν π n (h∥ ̃z i≡n ) ω n (φ ∗ ) Y i≡n φ ∗ ( ̃z i | ̃ h (n) <i a i ) ! = ω n (φ ∗ ) ̃ν π n ( ̃ h (n) ). By the inequality, ̃ν π n is absolutely continuous with respect to q n , so that by Blackwell and Dubins [1962], lim t→∞ D(q n , ̃ν π n | ̃ h (n) <t ) = 0, ̃ν π n -a.s. We can then prove the following lemma. Intuitively, ̃ν π n is the pushforward ofν π byaug n , so we can replace ̃ h (n) <t with aug n (h) <t , and ̃ν π n - with ν π -almost sure convergence. Lemma 4.1 (Convergence in TV distance). Letπbe the AIQI policyˆπ H,M,N,τ ψ whereψhas a grain of truth w.r.t. an environmentν. There exists aν π -probability-one setS ⊆ Ω such that for all h∈ S and n∈ [0,N − 1], lim t→∞ D(q n , ̃ν π n | aug n (h) <t ) = 0. We are now ready to show that each mixture return-predictor ψ n , or more generally the unified predictorψ, converges to the true return-predictorφ ∗ = ν π . By “convergence”, one would usually mean something along the line of lim t→∞ X ̃z t ∈Z |ψ( ̃z t |h <t a t )− ν π ( ̃z t |h <t a t )| = 0.(6) Instead, we prove something strictly stronger, involving a sum over hypothetical future trajectoriesh ′ t:m−1 that extend h <t . This stronger form of convergence is essential for prov- ing Theorem 4.6 without invoking any ad-hoc assumptions, e.g., off-policy sensibility [Catt et al., 2023, Theorem 16]. Let us denote the return-predictor error by δ ψ (h <t a t ) := X ̃z t ∈Z |ψ( ̃z t | h <t a t )− ν π ( ̃z t | h <t a t )|, and letT be the set of hypothetical trajectories h ′ <m , T :=h ′ <m | h ′ <t = h <t , e ′ t:m−1 ∈E m−t , a ′ t:m−1 = π ′ (h <t ,e ′ t:m−2 ),(7) formed byh <t appended with all possible percept sequences of lengthm−tand reactions from some deterministic policy π ′ . We assume for now thatπ ′ is an arbitrary deterministic policy, and specify it later in the proof of Theorem 4.6. We can show the following result. Lemma 4.2 (Convergence of return-predictor). Letπbe the AIQI policyˆπ H,M,N,τ ψ whereψhas a grain of truth w.r.t. an environmentν. For everyβ > 0, there exists aν π - probability-one setS ⊆ Ωwhere, for every outcomeh∈ S, there exists t 0 such that: for t≥ t 0 and m∈ [t,t+N−H], P h ′ <m ∈T ,a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ ψ (h ′ <m a ′ m ) < 2β (τ/|A|) −(m−t+1) . A corollary of our result is Eq. 6, obtained by settingm = t. Remarkably, our result is stronger, bounding the sum over hypothetical trajectories for allm ∈ [t,t + N − H]. This is possible due to the subtle fact thataug n (h <t )is well- defined forn = m modN, according to Eq. 2. This subtle fact also reveals why we can’t simply setN = Hand have to add a buffer of lengthN − H. In fact, the length of this buffer is exactly the maximum length of hypothetical future trajectories that can extend h <t in our bound. 4.2 ONE-STEP OPTIMALITY We continue to denote the AIQI policyˆπasπ. Let the AIQI parameterHbe theη-effective horizonH(η)for some η > 0. We can show that the estimated action-value ˆ Qin Definition 3.3 converges to the true action-valueQ π ν . Denote the Q-value estimation error by δ Q (h <t a t ) :=| ˆ Q(h <t a t )− Q π ν (h <t a t )|. Lemma 4.3 (Convergence of Q-value prediction). Under the conditions established in Lemma 4.2, P h ′ <m ∈T ,a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ Q (h ′ <m a ′ m ) < 2β (τ/|A|) −(m−t+1) + M −1 + η. Next, we show that the difference between the on-policy value and maximum Q-value becomes small. We call this difference the one-step optimality gap, δ 1 (h <t ) := max a Q π ν (h <t ,a)− V π ν (h <t ), which is non-negative due to V (·) = E a [Q(·,a)]. Lemma 4.4 (Convergence of one-step optimality gap). Un- der the conditions established in Lemma 4.2, P h ′ <m ∈T ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ 1 (h ′ <m ) < 2· (2β (τ/|A|) −(m−t+1) + M −1 + η) + 2τ. Intuitively, since AIQI chooses the actiona ∗ that maximizes the estimate ˆ Q, the valueVof AIQI is approximately equal to its Q-value under the actiona ∗ , with only a slight differ- ence due to the exploration probabilityτ. As the estimate ˆ Qconverges to the true Q-value due to Lemma 4.3, the Q-valueQ(·,a ∗ ), and hence the valueV (·), converges to the true maximum max a Q(·,a). 4.3 ASYMPTOTIC OPTIMALITY Let the global optimality gap be δ ∞ (h <t ) := V ∗ ν (h <t )− V π ν (h <t ). We now want to show the convergence of the global optimal- ity gap, which is equivalent to asymptotic optimality. First, we present a lemma that relates the global optimality gap to the one-step optimality gap. Lemma 4.5 (Bound on global optimality gap). For any environment ν, policy π, and history h <t , δ ∞ (h <t )≤ γ X e ′ t ν(e ′ t | h <t a ′ t )δ ∞ (h <t a ′ t e ′ t ) + δ 1 (h <t ), where a ′ t = arg max a (Q ∗ ν (h <t ,a)− Q π ν (h <t ,a)). Note that we can form a chain of inequalities by repeatedly applying the lemma toδ ∞ on the right hand side, as follows: δ ∞ (h <t )≤ γ X e ′ t ν(e ′ t | h <t a ′ t )δ ∞ (h ′ <t+1 ) + δ 1 (h <t ) ≤ γ 2 X e ′ t:t+1 ν(e ′ t:t+1 | h <t ∥ a ′ t:t+1 )δ ∞ (h ′ <t+2 ) + γ X e ′ t ν(e ′ t | h <t a ′ t )δ 1 (h ′ <t+1 ) + δ 1 (h <t ) ≤ ... ≤ γ L X e ′ t:t+L−1 ν(e ′ t:t+L−1 | h <t ∥ a ′ t:t+L−1 )δ ∞ (h ′ <t+L ) + L−1 X l=0 γ l X e ′ t:t+l−1 ν(e ′ t:t+l−1 | h <t ∥ a ′ t:t+l−1 )δ 1 (h ′ <t+l ) where a ′ i = arg max a |Q ∗ ν (h ′ <i ,a)− Q π ν (h ′ <i ,a)|. Furthermore, the first term in the last inequality is smaller than or equal toγ L , sinceδ ∞ (h ′ <t+L )≤ 1. Thusδ ∞ (h <t ) is smaller than or equal to γ L + L−1 X l=0 γ l X e ′ t:t+l−1 ν(e ′ t:t+l−1 |h <t ∥a ′ t:t+l−1 )δ 1 (h ′ <t+l ). (8) We have bound the global optimality gapδ ∞ (h <t )using only one-step optimality gaps δ 1 . We are now ready to prove the central result of our paper, that AIQI is strong asymptotically ε-optimal. Theorem 4.6 (AIQI is strong asymptoticallyε-optimal). Fix an environment classMand toleranceε > 0. Let τ ≤ ε(1−γ) 10 ,M ≥ 10 ε(1−γ) ,H = H(η)withη ≤ ε(1−γ) 10 , andN ≥ H + log γ ε 5 . Supposeψis a unified predictor that has a grain of truth with respect to all environmentsν ∈M and the above parameters for AIQI. Then, the AIQI policy ˆπ H,M,N,τ ψ is strong asymptotically ε-optimal inM. Proof. We simply writeπfor the AIQI policyˆπ H,M,N,τ ψ . Fix an environmentν ∈M, and letL = N − H + 1. Fix someβ > 0, and with it, chooseS ⊆ Ωas in Lemma 4.2. For anyh∈ S, chooset 0 , again as in Lemma 4.2. Then for all t≥ t 0 , substituting m = t + l in Eq. 8 and noting that a ′ i = arg max a |Q ∗ ν (h ′ <i ,a)− Q π ν (h ′ <i ,a)| is the output of a deterministic policy, we apply Lemma 4.4 to obtain δ ∞ (h <t ) < γ L + L−1 X l=0 γ l 2(2β τ |A| −(l+1) +M −1 + η) + 2τ . Recall thatL ≥ log γ ε 5 ,τ ≤ ε(1−γ) 10 ,M ≥ 10 ε(1−γ) , and η ≤ ε(1−γ) 10 . If we useβ = ετ 20 |A| −1 ( P L−1 l=0 (γ|A|/τ ) l ) −1 in choosingSandt 0 , the right hand side is smaller than or equal toε. Thus forh∈ Sandt≥ t 0 ,δ ∞ (h <t )≤ ε. This concludes our proof that lim sup t→∞ δ ∞ (h <t )≤ ε, ν π -a.s. We can also show that strong asymptoticε-optimality in the environment classMimplies asymptotic optimality in the mixture environment ξ. Lemma 4.7 (Optimality inMimplies optimality inξ). Given a mixtureξof environment classM, and a policyπ that is strong asymptoticallyε-optimal with respect toM, the same policy π is asymptotically ε-optimal in ξ: lim sup t→∞ V ∗ ξ (h <t )− V π ξ (h <t )≤ ε holds both ξ π -a.s. and, for all ν ∈M, ν π -a.s. As a consequence, AIQI is also asymptotically optimal inξ. In other words, AIQI approximates Bayes-optimality, which is the defining feature of AIXI. Theorem 4.8 (AIQI is asymptoticallyε-Bayes-optimal). For any mixtureξof environment classM, the AIQI policy ˆπ H,M,N,τ ψ with the parameters in Theorem 4.6 is asymptoti- cally ε-optimal in ξ. Proof. Theorem 4.6 and Lemma 4.7. The single-agent result extends directly to multi-agent inter- action by viewing each agentias acting in the subjective environmentσ i induced by the other agents’ policiesπ ̸=i [Leike et al., 2016b, Section 4.1]. Thus, if each AIQI agent π i = ˆπ H i ,M i ,N i ,τ i ψ i satisfies the assumptions of Theorem 4.6, every agent is eventually anε-best response to the others. Hence the joint policy profileπ 1:n converges to anε-Nash equilibrium,σ π 1:n -almost surely. We detail this extension in § D. 4.4 OFF-POLICY BEHAVIOR Until now we have solely discussed the on-policy setting, where the policy that interacts with the environment is the same as the policy that we are optimizing. In the off-policy setting, we must infer an optimal policy from the interac- tions generated by some “historic policy”π ′ that we do not have control over. We can formalize this notion of optimality with the self-optimizing property. Definition 4.9 (Self-optimizing policy). A policy ̄πis called self-optimizing for a class of environmentsMand a historic policy π ′ , if for every ν ∈M, lim t→∞ V ∗ ν (h <t )− V ̄π ν (h <t ) = 0, ν π ′ -a.s. Hutter [2002] showed a remarkable property of AIXI, that if there exists a self-optimizing policy forMandπ ′ , then AIXI is one of those self-optimizing policies. On the other hand, we can expect that AIQI does not satisfy this property, since it is an on-policy MC control algorithm. In fact, if the predictorψsupports the return-predictor φ ∗ = ν π ′ , AIQI will eventually choose actions with the highest value under the historic policyπ ′ , and not its own value—the optimality of AIQI is thus no longer guaranteed. Even if we relax the self-optimizing property to theε-self- optimizing property by replacinglim = 0withlim sup≤ ε, the following can be shown. Theorem 4.10 (AIQI is not self-optimizing). Suppose the unified predictorψis built from classesP n that contain all computable variable-order Markov models. For any period N, exploration rateτ, horizonH ≥ 2, toleranceεsmall enough (depending onH), and discretization levelMlarge enough (depending onH,ε,τ), there exist an environment classM, a historic policyπ ′ , and a discount factorγ ∈ (0, 1) , for which there exists a self-optimizing policy, but the AIQI policy ˆπ H,M,N,τ ψ is not even ε-self-optimizing. This completes our investigation of the theoretical prop- erties of AIQI. We have assumed a geometric discount setting for simplicity, but we can extend all our results to the general discount setting, where returns are defined asR t = P ∞ k=t γ k r k / P ∞ k=t γ k for a general discount se- quenceγ k . Specifically, our results can be generalized to cases where the discount sequence decays faster than a geo- metric sequence. We detail the generalization in § E. 5 APPLICATION TO SELF-AIXI Self-AIXI [Catt et al., 2023] is similar to AIQI in that it makes predictions of its own action values, and chooses the actiona t that maximizes the predicted value. As noted by Wyeth [2025], Catt et al. [2023] make unjustified assump- tions in their attempt to prove the asymptotic optimality of Self-AIXI. We suggest addingε-greedy exploration to Self- AIXI and proving its asymptoticε-optimality without any ad-hoc assumptions. Fortunately, our proof techniques can be applied with minimal changes. The key is in proving an analogue of Lemma 4.3. We present the key results below, and provide their proofs in § C. First, we define theε-greedy Self-AIXI. Definition 5.1 (ε-greedy Self-AIXI). Letξbe a mixture environment constructed from some environment classM, andζbe a mixture policy constructed from some policy classP. Then,ε-greedy Self-AIXI, denotedπ S , is defined as π S (a| h <t ) := (1− τ )1 [a = a ∗ ] + τ/|A|, wherea ∗ = arg max a t Q ζ ξ (h <t ,a t ) . We allow for stochas- tic tie-breaking when multiple actions maximize Q ζ ξ . The following lemmas serve as a bridge between Self-AIXI and our proof technique. Lemma 5.2 (Convergence ofξ ζ toν π ). For any environ- ment ν ∈M and policy π ∈ P , lim t→∞ D ξ ζ ,ν π | h <t = 0, ν π -a.s. Lemma 5.3 (Bounds on Q-value difference). For any two policies π 1 ,π 2 and two environments ν 1 ,ν 2 , Q π 1 ν 1 (h <t ,a t )− Q π 2 ν 2 (h <t ,a t ) ≤ D(ν π 1 1 ,ν π 2 2 | h <t a t ) Proof. See Leike [2016, Lemma 4.17]. Lemma 5.4 (Average conditional TV bound). LetPandQ be probability measures onX ×Y, whereXis finite. Let P X and Q X denote the marginals onX . Then X x∈X P X (x)D P,Q| X = x ≤ 2D(P,Q). Now we can prove an analogue of Lemma 4.3 for π S . Let δ Q (h <t a t ) :=|Q ζ ξ (h <t a t )− Q π ν (h <t a t )|, and defineT as in Eq. 7. Lemma 5.5 (Convergence of Q-value prediction for ε-greedy Self-AIXI). Letπ = π S . For everyβ > 0, there exists aν π -probability-one setS ⊆ Ωwhere, for every outcomeh ∈ S, there existst 0 such that: fort ≥ t 0 and m≥ t, X h ′ <m ∈T ,a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ Q (h ′ <m a ′ m ) < 2β (τ/|A|) −(m−t+1) . We can then show analogues of Lemmas 4.4 and 4.5 and Theorem 4.6 forε-greedy Self-AIXI, with our proof for AIQI repeated almost verbatim. Note that the error term 2τwould be introduced by the analogue of Lemma 4.4, and thusπ S can only be asymptoticallyε-optimal, whereε depends on the exploration rate τ . 6 RELATED WORK Compress and Control [CNC; Veness et al., 2015] is an al- gorithm that shares many similarities to AIQI such as return prediction, but has only been analyzed for fully observable MDPs. Both CNC and AIQI are on-policy Monte Carlo con- trol methods with a distributional flavour [Bellemare et al., 2017], since they predict the return distribution instead of the average return. CNC uses a model-based approach for MC evaluation, unlike AIQI. Feature reinforcement learning [Daswani, 2015] converts a general environment to a finite state MDP through a learned feature map, and then performs planning [Hutter, 2009] or model-free RL [Nguyen et al., 2011, Daswani et al., 2013] inside the MDP. Hutter [2014] shows that any general envi- ronment can be mapped to an MDP where the optimal policy is stillε-optimal in the general environment. However, these theoretical results do not tell us about the learning of such mappings, and results that are concerned with the learning [Sunehag and Hutter, 2010] do not concern themselves with control. Self-AIXI [Catt et al., 2023] is a variant of AIXI that learns both a model of the environment and a model of itself. At every step, it uses both models to estimate its own action- values, by simulating the model of itself interacting with the model of the environment. It then chooses the action with the highest estimated value. Although Self-AIXI gets rid of planning, it is clearly model-based in that it learns and uses an environment model. Our work was inspired by Self-AIXI, and can be seen as a modification that further gets rid of environment models by directly predicting action-values. Finally, Optimal Direct Policy Search [ODPS; Glasmachers and Schmidhuber, 2011] is a policy search method that enu- merates computable policies (or more generally policies in some arbitrary class) and evaluates them by repeated interac- tion with the environment. Like AIQI, ODPS is model-free and avoids planning. However, ODPS assumes an episodic POMDP setting with bounded episode lengths, whereas our results apply to general environments. 7 DISCUSSION 7.1 PROOF TECHNIQUE To prove that AIQI is strong asymptoticallyε-optimal, we first showed that the action-value estimates converge to the trueν π action-values (Lemma 4.3), and that choosing the action with the highest (estimated)ν π value makes the pol- icy converge to optimal actions (Theorem 4.6). There are two key novelties in our proofs compared to existing work in universal AI. First, we had to deal with the problem of delayed feedback using periodic augmentations. This was not needed in previous works which model policies or en- vironments, since actions and percepts are never delayed, unlikeH-step returns. Second, we introduced a chain of inequalities using Lemma 4.5, to make theδ ∞ term in the upper bound vanish with γ L . This allowed us to bypass ad- hoc assumptions such as off-policy sensibility [Catt et al., 2023, Theorem 16]. In fact, we show in § 5 that our tech- nique can be applied to Self-AIXI to show analogous results without off-policy sensibility. Overall, our work provides a blueprint for the analysis of policy iteration algorithms in general environments. 7.2 CONTINUAL REINFORCEMENT LEARNING The class of general environments is equivalent to the class of infinite-state POMDPs, which might seem unnecessarily large. However, there are nontrivial settings that cannot be captured by finite-state POMDPs, one such example being continual RL [Ring, 1994]. Continual RL studies environ- ments that never stop changing [Khetarpal et al., 2022], and where agents must keep learning in order to act opti- mally [Abel et al., 2023]. The theory of universal AI sets aside problems with continual learning, e.g., catastrophic forgetting, by assuming a perfect Bayesian learner with a broad prior. This lets it focus on a different question: how to design principled objectives for continual RL, assum- ing continual learning is approximately solved. Our work shows that learning distributional action-values is one such objective. 7.3 AGENT FOUNDATIONS The theory of universal AI is central to agent foundations research [Soares and Fallenstein, 2017], since it provides formal models of powerful goal-directed agents under min- imal assumptions about the environment. As such, it has been used to analyze important issues in AI safety in a the- oretically grounded way [Everitt et al., 2016, Orseau and Armstrong, 2016, Majha et al., 2019, Everitt and Hutter, 2018a, Cohen et al., 2021]. Our results show that asymp- totic optimality in general reinforcement learning does not require an explicit world model. We therefore view AIQI as a new theoretical object that may help clarify which ingredi- ents of general-agent theory matter for safety. Although our paper set out to primarily show that AIQI and AIXI are similar, they might differ in other ways, e.g., the off-policy behavior as we discussed in § 4.4. Another interesting difference is that, unlike AIXI, AIQI needs to deal with self-reference (Definition 3.4), which is in turn related to embedded agency [Demski and Garrabrant, 2019, Orseau and Ring, 2012b]. 8 CONCLUSION We introduced Universal AI with Q-Induction (AIQI), the first model-free universal agent. AIQI performs universal induction over distributional action-value functions—rather than over environments or policies as in prior work. It is essentially a Monte Carlo control algorithm, the most primi- tive form of model-free RL. We prove that AIQI is strong asymptoticallyε-optimal, asymptoticallyε-Bayes-optimal, and, as expected from an on-policy MC control algorithm, not self-optimizing. Remarkably, the only assumption we make is grain of truth, which is standard in universal AI and has a known resolution via reflective oracles. Our findings significantly broaden the known landscape of universal agents. We hope this provides both a theoretical foundation for understanding MC control with sequence models, and a blueprint for the analysis of other policy iteration algorithms in general environments. Promising di- rections for future work include analyzing the properties of AIQI with exploration strategies that are more sophisticated thanε-greedy, such as knowledge-seeking agents [Orseau, 2014], investigating similarities/differences between AIQI and AIXI, and exploring other possible forms of model-free universal AI such as those that involve policy search. Acknowledgements This work was supported by Institute for Information & communications Technology Planning & Evaluation(IITP) grant funded by the Korea government(MSIT) (RS-2019- I190075, Artificial Intelligence Graduate School Pro- gram(KAIST); RS-2024-00509279, Fundamental Research in Artificial Intelligence). We thank Cole Wyeth for carefully reading the paper and discussing ways to improve it. We also thank the Universal Algorithmic Intelligence community for inviting us for a talk and providing insightful questions/feedback. References David Abel, André Barreto, Benjamin Van Roy, Doina Pre- cup, Hado P van Hasselt, and Satinder Singh. A definition of continual reinforcement learning. Advances in Neural Information Processing Systems, 36:50377–50407, 2023. Marc G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. In International conference on machine learning, pages 449– 458. Pmlr, 2017. Richard Ernest Bellman. Dynamic Programming. Courier Dover Publications, Mineola, NY, 1957. David Blackwell and Lester Dubins. Merging of opinions with increasing information. The Annals of Mathematical Statistics, 33(3):882–886, 1962. Elliot Catt. On the Foundations of Universal Artificial Intel- ligence. PhD thesis, The Australian National University, Canberra, Australia, 2022. Elliot Catt, Jordi Grau-Moya, Marcus Hutter, Matthew Aitchison, Tim Genewein, Gregoire Deletang, Kevin Li, and Joel Veness. Self-predictive universal ai. Advances in Neural Information Processing Systems, 36:27181– 27198, 2023. Michael K Cohen, Elliot Catt, and Marcus Hutter. A strongly asymptotically optimal agent in general environments. arXiv preprint arXiv:1903.01021, 2019. Michael K Cohen, Elliot Catt, and Marcus Hutter. Curios- ity killed or incapacitated the cat and the asymptotically optimal agent. IEEE Journal on Selected Areas in Infor- mation Theory, 2(2):665–677, 2021. Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72–83. Springer, 2006. Mayank Daswani. Generic Reinforcement Learning Beyond Small MDPs. PhD thesis, Australian National University, 2015. Mayank Daswani, Peter Sunehag, and Marcus Hutter. Q- learning for history-based reinforcement learning. In Asian Conference on Machine Learning, pages 213–228. PMLR, 2013. Abram Demski and Scott Garrabrant. Embedded agency. arXiv preprint arXiv:1902.09469, 2019. Tom Everitt and Marcus Hutter. The alignment problem for bayesian history-based reinforcement learners. Under submission, 2018a. Tom Everitt and Marcus Hutter. Universal artificial intelli- gence: Practical agents and fundamental challenges. In Foundations of trusted autonomy, pages 15–46. Springer, 2018b. Tom Everitt, Daniel Filan, Mayank Daswani, and Marcus Hutter. Self-modification of policy and utility function in rational agents. In International conference on artificial general intelligence, pages 1–11. Springer, 2016. Benja Fallenstein, Jessica Taylor, and Paul F Christiano. Re- flective oracles: A foundation for game theory in artificial intelligence. In International Workshop on Logic, Ratio- nality and Interaction, pages 411–415. Springer, 2015. Tobias Glasmachers and Jürgen Schmidhuber. Optimal direct policy search. In International Conference on Arti- ficial General Intelligence, pages 52–61. Springer, 2011. Marcus Hutter. Self-optimizing and pareto-optimal policies in general environments based on bayes-mixtures. In International Conference on Computational Learning Theory, pages 364–379. Springer, 2002. Marcus Hutter. Universal artificial intelligence: Sequential decisions based on algorithmic probability, volume 300. Springer, 2005. Marcus Hutter. Feature reinforcement learning: Part i. un- structured mdps. arXiv preprint arXiv:0906.1713, 2009. Marcus Hutter. Extreme state aggregation beyond mdps. In International Conference on Algorithmic Learning Theory, pages 185–199. Springer, 2014. Marcus Hutter, David Quarel, and Elliot Catt. An introduc- tion to universal artificial intelligence. Chapman and Hall/CRC, 2024. Ehud Kalai and Ehud Lehrer. Rational learning leads to nash equilibrium. Econometrica: Journal of the Econometric Society, pages 1019–1045, 1993. Khimya Khetarpal, Matthew Riemer, Irina Rish, and Doina Precup. Towards continual reinforcement learning: A review and perspectives. Journal of Artificial Intelligence Research, 75:1401–1476, 2022. Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999. Tor Lattimore. Theory of General Reinforcement Learning. PhD thesis, Australian National University, 2014. Tor Lattimore and Marcus Hutter. Asymptotically opti- mal agents. In International Conference on Algorithmic Learning Theory, pages 368–382. Springer, 2011. Tor Lattimore and Marcus Hutter. Bayesian reinforcement learning with exploration. In International conference on algorithmic learning theory, pages 170–184. Springer, 2014. Shane Legg and Marcus Hutter. Universal intelligence: A definition of machine intelligence. Minds and machines, 17(4):391–444, 2007. Jan Leike. Nonparametric general reinforcement learning. The Australian National University (Australia), 2016. Jan Leike, Tor Lattimore, Laurent Orseau, and Marcus Hut- ter. Thompson sampling is asymptotically optimal in general environments. arXiv preprint arXiv:1602.07905, 2016a. Jan Leike, Jessica Taylor, and Benya Fallenstein. A formal solution to the grain of truth problem. arXiv preprint arXiv:1609.05058, 2016b. Arushi Majha, Sayan Sarkar, and Davide Zagami. Catego- rizing wireheading in partially embedded agents. arXiv preprint arXiv:1906.09136, 2019. Alexander Meulemans, Rajai Nasser, Maciej Wołczyk, Marissa A Weis, Seijin Kobayashi, Blake Richards, Guil- laume Lajoie, Angelika Steger, Marcus Hutter, James Manyika, et al. Embedded universal predictive intelli- gence: a coherent framework for multi-agent learning. arXiv preprint arXiv:2511.22226, 2025. Phuong Nguyen, Peter Sunehag, and Marcus Hutter. Feature reinforcement learning in practice. In European Work- shop on Reinforcement Learning, pages 66–77. Springer, 2011. Laurent Orseau. Universal knowledge-seeking agents. The- oretical Computer Science, 519:127–139, 2014. Laurent Orseau and Stuart Armstrong. Safely interruptible agents. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, pages 557–566, 2016. Laurent Orseau and Mark Ring. Memory issues of intel- ligent agents. In International Conference on Artificial General Intelligence, pages 219–231. Springer, 2012a. Laurent Orseau and Mark Ring. Space-time embedded intelligence. In International Conference on Artificial General Intelligence, pages 209–218. Springer, 2012b. Mark Bishop Ring. Continual learning in reinforcement environments. The University of Texas at Austin, 1994. Gavin A Rummery and Mahesan Niranjan. On-line Q- learning using connectionist systems, volume 37. Uni- versity of Cambridge, Department of Engineering Cam- bridge, UK, 1994. Nate Soares and Benya Fallenstein. Agent foundations for aligning machine intelligence with human interests: a technical research agenda. In The technological singu- larity: Managing the journey, pages 103–125. Springer, 2017. Ray J Solomonoff. A formal theory of inductive inference. part i. Information and control, 7(1):1–22, 1964a. Ray J Solomonoff. A formal theory of inductive inference. part i. Information and control, 7(2):224–254, 1964b. Peter Sunehag and Marcus Hutter. Consistency of feature markov processes. In International Conference on Algo- rithmic Learning Theory, pages 360–374. Springer, 2010. Joel Veness, Kee Siong Ng, Marcus Hutter, William Uther, and David Silver. A monte-carlo aixi approximation. Journal of Artificial Intelligence Research, 40:95–142, 2011. Joel Veness, Marc Bellemare, Marcus Hutter, Alvin Chua, and Guillaume Desjardins. Compress and control. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 29, 2015. John Von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, 1944. Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, King’s College, University of Cambridge, Cambridge, United Kingdom, 1989. FMJ Willems, Yu M Shtarkov, and TJ Tjalkens. The context- tree weighting method: basic properties. IEEE Transac- tions on Information Theory, 41(3):653–664, 1995. Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Ma- chine learning, 8(3):229–256, 1992. Cole Wyeth.Unbounded embedded agency: AEDT w.r.t.rOSI.https://w.lesswrong. com/posts/B6gumHyuxzR5yn5tH/ unbounded-embedded-agency-aedt-w-r-t-rosi , July 2025. LessWrong blog post. Accessed: 2026-06-02. Cole Wyeth, Marcus Hutter, Jan Leike, and Jessica Tay- lor. Limit-computable grains of truth for arbitrary com- putable extensive-form (un) known games. arXiv preprint arXiv:2508.16245, 2025. A Model-Free Universal AI (Supplementary Material) Yegon Kim 1 Juho Lee 1 1 Graduate School of AI, KAIST, Seoul, South Korea A NOTATION Table 1: Summary of Notations SymbolDescription εThe empty string, e.g., initial history h <1 NSet of natural numbers0, 1, 2,... Z + Set of positive integers1, 2, 3,... A,O,RSets of actions, observations, and rewards EPercept space, defined asO×R HThe set of all finite histories (A×E ) ∗ h <t History sequence a 1 e 1 ...a t−1 e t−1 π,νPolicy π :H→ ∆A and environment ν :H×A→ ∆E V π ν ,Q π ν Value function and Q-value function H(η)η-effective horizon MDiscretization level for returns ZAlphabet of discretized returns0, 1 M ,..., M−1 M z t M -discretized H -step return at time t ̃z t Augmented return at time t in an augmented outcome NAugmentation period (N ≥ H ) nPhase of periodic augmentation (n∈0,...,N − 1) ̃ Ω (n) , ̃ H (n) Phase n augmented sample space and histories aug n Mapping from outcomes to phase n-augmented outcomes ψ n Mixture return-predictor for phase n ψUnified predictor that selects ψ n where n = t mod N ˆ Q(h <t ,a t )AIQI estimated Q-value (expected discretized return) τExploration probability D(P,Q)Total Variation (TV) distance between measures P and Q LEffective lookahead length (N − H + 1) B PROOFS Lemma 4.1 (Convergence in TV distance). Letπbe the AIQI policyˆπ H,M,N,τ ψ whereψhas a grain of truth w.r.t. an environment ν. There exists a ν π -probability-one set S ⊆ Ω such that for all h∈ S and n∈ [0,N − 1], lim t→∞ D(q n , ̃ν π n | aug n (h) <t ) = 0. Accepted for the 42 nd Conference on Uncertainty in Artificial Intelligence (UAI 2026). Proof. Recall that lim t→∞ D(q n , ̃ν π n | ̃ h (n) <t ) = 0, ̃ν π n -a.s. In other words, there exists an event ̃ S n ⊆ ̃ Ω (n) , with ̃ν π n ( ̃ S n ) = 1, whereD(q n , ̃ν π n | ̃ h (n) <t )converges to0pointwise. LetF be the set of “faulty” outcomes in ̃ S n whose augmented returns ̃z i≡n do not agree with the true returnsz i≡n . Recall the definition of ̃ν π n as the pushforward of ν π by aug n . Since F is disjoint from the image of aug n , we get ̃ν π n (F ) = 0. LetS n be the preimage of ̃ S n − Funderaug n . Then, by the injectivity ofaug n , we see thatν π (S n ) = ̃ν π n ( ̃ S n − F ) = ̃ν π n ( ̃ S n ) = 1 . Since pointwise convergence on ̃ S n implies pointwise convergence on the subset ̃ S n − F, we see that D(q n , ̃ν π n | aug n (h) <t )converges pointwise to0onS n . Construct suchS n for everyn, and letS = T n S n . Then, ν π (S) = 1, and D(q n , ̃ν π n | aug n (h) <t ) converges pointwise to 0 on S for all n. Lemma 4.2 (Convergence of return-predictor). Letπbe the AIQI policyˆπ H,M,N,τ ψ whereψhas a grain of truth w.r.t. an environmentν. For everyβ > 0, there exists aν π -probability-one setS ⊆ Ωwhere, for every outcomeh∈ S, there exists t 0 such that: for t≥ t 0 and m∈ [t,t+N−H], P h ′ <m ∈T ,a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ ψ (h ′ <m a ′ m ) < 2β (τ/|A|) −(m−t+1) . Proof. Fix someβ > 0. By Lemma 4.1, we can choose someS ⊆ Ωwithν π (S) = 1such that∀h∈ S,∃t 0 ,∀t≥ t 0 ,∀n∈ [0,N − 1], D(q n , ̃ν π n | aug n (h) <t ) < β.(9) Consider someh∈ Sandt≥ t 0 . For allm∈ [t,t+N−H]andn = m modN, we see that Eq. 2 is satisfied for bothtand m, so we can apply aug n on histories of lengths t− 1 and m− 1. Then, X h ′ <m ∈T ,a ′ m ∈A, ̃z m ∈Z ν π h ′ t:m−1 a ′ m | h <t · ψ( ̃z m | h ′ <m a ′ m )− ν π ( ̃z m | h ′ <m a ′ m ) (a) = X h ′ <m ∈T ,a ′ m ∈A, ̃z m ∈Z ν π h ′ t:m−1 a ′ m | h <t · ψ n ( ̃z m | aug n (h ′ <m )a ′ m )− ̃ν π n ( ̃z m | aug n (h ′ <m )a ′ m ) (b) = X h ′ <m ∈T ,a ′ m ∈A, ̃z m ∈Z ̃ν π n h ′ t:m−1 a ′ m | aug n (h <t ) · ψ n ( ̃z m | aug n (h <t )h ′ t:m−1 a ′ m )− ̃ν π n ( ̃z m | aug n (h <t )h ′ t:m−1 a ′ m ) (c) = X h ′ <m ∈T ,a ′ m ∈A, ̃z m ∈Z q n h ′ t:m−1 a ′ m ̃z m | aug n (h <t ) − ̃ν π n h ′ t:m−1 a ′ m ̃z m | aug n (h <t ) (d) ≤ 2· D(q n , ̃ν π n | aug n (h) <t ).(10) Equality(a)is just rewriting the unified predictorψas the phasenpredictorψ n (and likewise rewriting the true conditional using ̃ν π n ) via the definitions ofψand ̃ν π n . Equality(b)uses thataug n (h <t )is a deterministic function ofh <t , and thus conditioning underh <t is the same as conditioning underaug n (h <t ). Equality(c)uses the definitions ofq n and ̃ν π n , noting that there are no augmented returns between indicestandmother than ̃z m . Inequality(d)is Eq. 3 applied to the disjoint cylinder sets formed by h ′ <m a ′ m ̃z m . By the definition of AIQI, each action in a ′ t:m receives a probability of at least τ/|A| from the AIQI policy π. Thus, ν π h ′ t:m−1 a ′ m | h <t = m Y i=t π(a ′ i | h ′ <i ) m−1 Y i=t ν(e ′ i | h ′ <i a ′ i ) ≥ (τ/|A|) m−t+1 ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 ).(11) By combining Eqs. 9 to 11, we obtain the desired result. Lemma 4.3 (Convergence of Q-value prediction). Under the conditions established in Lemma 4.2, P h ′ <m ∈T ,a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ Q (h ′ <m a ′ m ) < 2β (τ/|A|) −(m−t+1) + M −1 + η. Proof. Let us define the lower-approximate Q-value as Q π ν (h <t ,a t ) := E ν π [z t | h <t a t ] = X z t ∈Z z t · ν π (z t | h <t ,a t ). Recall that theH-step Q-value isQ π ν,H (h <t ,a t ) = E ν π [R t,H | h <t a t ].Since|z t − R t,H | < 1/M, we see that|Q π ν (·)− Q π ν,H (·)| < 1/M . Since we setHto be theη-effective horizonH(η),|R t,H − R t | ≤ η, so that|Q π ν,H (·)− Q π ν (·)| ≤ η. Thus we obtain|Q π ν (·)− Q π ν (·)| < M −1 + η, and X h ′ <m ∈T ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )·|Q π ν (h ′ <m a ′ m )− Q π ν (h ′ <m a ′ m )| < M −1 + η,(12) where we used Eq. 1. Recall the definition of ˆ Q in Definition 3.3. X h ′ <m ∈T , a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )·| ˆ Q(h ′ <m a ′ m )− Q π ν (h ′ <m a ′ m )| (a) = X h ′ <m ∈T , a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )·| X ̃z m ∈Z ̃z m [ψ( ̃z m | h ′ <m a ′ m )− ν π ( ̃z m | h ′ <m a ′ m )]| (b) ≤ X h ′ <m ∈T , a ′ m ∈A, ̃z m ∈Z ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· ̃z m ·|ψ( ̃z m | h ′ <m a ′ m )− ν π ( ̃z m | h ′ <m a ′ m )| (c) ≤ X h ′ <m ∈T , a ′ m ∈A, ̃z m ∈Z ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )·|ψ( ̃z m | h ′ <m a ′ m )− ν π ( ̃z m | h ′ <m a ′ m )| = X h ′ <m ∈T , a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ ψ (h ′ <m a ′ m ) (d) < 2β (τ/|A|) −(m−t+1) .(13) Equality(a)expands ˆ QandQ π ν as expectations over ̃z m (by definition). Inequality(b)is the triangle inequality. Inequality (c) uses ̃z m ∈ [0, 1]. Finally, (d) is an application of Lemma 4.2. Combining Eqs. 12 and 13 with triangle inequality, we obtain the desired result. Lemma 4.4 (Convergence of one-step optimality gap). Under the conditions established in Lemma 4.2, P h ′ <m ∈T ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ 1 (h ′ <m ) < 2· (2β (τ/|A|) −(m−t+1) + M −1 + η) + 2τ. Proof. δ 1 (h ′ <m ) =| max a Q(h ′ <m ,a)− V (h ′ <m )| (a) = max a Q(h ′ <m ,a)− (1− τ )Q(h ′ <m , arg max a ˆ Q) + (τ/|A|) X a Q(h ′ <m ,a) (b) ≤| max a Q(h ′ <m ,a)− Q(h ′ <m , arg max a ˆ Q)| + 2τ ≤| max a Q(h ′ <m ,a)− max a ˆ Q(h ′ <m ,a)| +| max a ˆ Q(h ′ <m ,a)− Q(h ′ <m , arg max a ˆ Q)| + 2τ (c) ≤ max a |Q(h ′ <m ,a)− ˆ Q(h ′ <m ,a)| +| ˆ Q(h ′ <m ,a ‡ )− Q(h ′ <m ,a ‡ )| + 2τ =|Q(h ′ <m ,a † )− ˆ Q(h ′ <m ,a † )| +| ˆ Q(h ′ <m ,a ‡ )− Q(h ′ <m ,a ‡ )| + 2τ, where a † := arg max a |Q(h ′ <m ,a)− ˆ Q(h ′ <m ,a)| and a ‡ := arg max a ˆ Q(h ′ <m ,a) are functions of h ′ <m . Equality(a)uses the Bellman equationV (·) = P a π(a|·)Q(·,a) together with the AIQI policy definition (greedy with probability1− τand uniform exploration with probabilityτ). Inequality(b)upper-bounds the effect of the exploration mixture; sinceQ ∈ [0, 1], the mixture term can change the value by at most2τ. Inequality(c)uses the standard bound | maxf − maxg|≤ max|f − g| and that a ‡ = arg max a ˆ Q(h ′ <m ,a). Multiplying both sides by ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 ) and summing, we obtain X h ′ <m ∈T ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ 1 (h ′ <m ) ≤ X h ′ <m ∈T ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 ) |Q(h ′ <m ,a † )− ˆ Q(h ′ <m ,a † )| +| ˆ Q(h ′ <m ,a ‡ )− Q(h ′ <m ,a ‡ )| + X h ′ <m ∈T ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· 2τ (a) ≤ 2· X h ′ <m ∈T , a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )·| ˆ Q(h ′ <m a ′ m )− Q π ν (h ′ <m a ′ m )| + 2τ (b) < 2· (2β (τ/|A|) −(m−t+1) + M −1 + η) + 2τ. Inequality(a)uses thata † (h ′ <m )anda ‡ (h ′ <m )select particular actions, so summing over alla ′ m ∈Aupper-bounds each choice. Finally, (b) applies Lemma 4.3. Lemma 4.5 (Bound on global optimality gap). For any environment ν, policy π, and history h <t , δ ∞ (h <t )≤ γ X e ′ t ν(e ′ t | h <t a ′ t )δ ∞ (h <t a ′ t e ′ t ) + δ 1 (h <t ), where a ′ t = arg max a (Q ∗ ν (h <t ,a)− Q π ν (h <t ,a)). Proof. We omit the subscript ν under Q and V for brevity. δ ∞ (h <t ) =| max a Q ∗ (h <t ,a)− V π (h <t )| (a) ≤| max a Q ∗ (h <t ,a)− max a Q π (h <t ,a)| +| max a Q π (h <t ,a)− V π (h <t )| (b) ≤ max a |Q ∗ (h <t ,a)− Q π (h <t ,a)| + δ 1 (h <t ) (c) =|Q ∗ (h <t ,a ′ t )− Q π (h <t ,a ′ t )| + δ 1 (h <t ) (d) = X e ′ t ν(e t |h <t a ′ t ) [((1− γ)r t + γV ∗ (h <t a ′ t e ′ t ))− ((1− γ)r t + γV π (h <t a ′ t e ′ t ))] + δ 1 (h <t ) = γ X e ′ t ν(e t |h <t a ′ t ) [V ∗ (h <t a ′ t e ′ t )− V π (h <t a ′ t e ′ t )] + δ 1 (h <t ) (e) ≤ γ X e ′ t ν(e t | h <t a ′ t )δ ∞ (h <t a ′ t e ′ t ) + δ 1 (h <t ) Inequality(a)is the triangle inequality. Inequality(b)uses| maxf− maxg|≤ max|f−g|and the definition ofδ 1 . Equality (c)is by the definition ofa ′ t = arg max a |Q ∗ (h <t ,a)− Q π (h <t ,a)| as stated in the lemma. Equality(d)is the Bellman expansion of Q ∗ and Q π . Finally, (e) uses| P x p x u x |≤ P x p x |u x | and δ ∞ = V ∗ − V π . Lemma 4.7 (Optimality inMimplies optimality inξ). Given a mixtureξof environment classM, and a policyπthat is strong asymptotically ε-optimal with respect toM, the same policy π is asymptotically ε-optimal in ξ: lim sup t→∞ V ∗ ξ (h <t )− V π ξ (h <t )≤ ε holds both ξ π -a.s. and, for all ν ∈M, ν π -a.s. Proof.Proving that the inequality in our theorem holdsξ π -almost surely implies that the inequality holdsν π -almost surely for anyν ∈ M. This is because, ifEis the set of all outcomeshwhere the inequality doesn’t hold,ν π (E) ≤ ξ π (E)/w(ν) = 0. Thus it suffices to prove that the inequality holds ξ π -almost surely. By the definition of the mixture ξ and the value function V , we see that V π ξ (h <t ) = X ν∈M w(ν | h <t )V π ν (h <t ). Let π ∗ ξ be an optimal policy in ξ. Then V ∗ ξ (h <t ) = V π ∗ ξ ξ (h <t ) = X ν w(ν | h <t )V π ∗ ξ ν (h <t )≤ X ν w(ν | h <t )V ∗ ν (h <t ), so that 0≤ V ∗ ξ (h <t )− V π ξ (h <t )≤ X ν w(ν | h <t ) (V ∗ ν (h <t )− V π ν (h <t )).(14) Thus it suffices to show that the right-hand side has lim sup≤ ε, ξ π -almost surely. For each environmentν ∈M, by Theorem 4.6 there exists an eventS ν ⊆ Ωwithν π (S ν ) = 1such that for all outcomes h∈ S ν , lim sup t→∞ V ∗ ν (h <t )− V π ν (h <t ) ≤ ε.(15) Define the posterior processw t (ν) := w(ν | h <t )and its limitw ∞ (ν) := lim t→∞ w t (ν), which existsξ π -a.s. since (w t (ν)) t≥1 is a bounded martingale. Let us consider the joint probability measure onM× Ω, where we first drawν ∼ w, then draw the outcome h∼ν π . Then ξ π is its marginal over Ω. A standard identity is the following: E[w ∞ (ν)1 E ] = P(ν = ν,h∈ E) = w(ν)ν π (E).(16) Due to Eq. 16 and ν π (S c ν ) = 0, E ξ π [w ∞ (ν)1 S c ν ] = 0. Since the integrand is nonnegative, w ∞ (ν)1 S c ν = 0, ξ π -a.s.(17) Hence, there exists aξ π -probability-one set, such that for any outcomehin this set, Eq. 15 holds for allνwherew ∞ (ν) > 0. Now define the per-environment gap δ t,ν := V ∗ ν (h <t )− V π ν (h <t )∈ [0, 1], and the posterior-weighted gap G t := X ν w t (ν)δ t,ν . By Eq. 14, it is enough to show lim sup t→∞ G t ≤ ε, ξ π -a.s. Fix an outcomehin aξ π -probability-one set on whichw t (ν) → w ∞ (ν)for allνand Eq. 17 holds for allν. Letα > 0. Sincew ∞ (·)is a probability mass function on a countable set, there exists a finiteF ⊆ Msuch thatw ∞ (ν) > 0for all ν ∈ F , and X ν∈F w ∞ (ν)≥ 1− α.(18) Sincew ∞ (ν) > 0, we havelim sup t→∞ δ t,ν ≤ εby Eq. 17. Therefore, for every suchνthere existst ν such that for all t≥ t ν , δ t,ν ≤ ε + α. Let t 0 := max ν∈F t ν . Then for all t≥ t 0 , X ν∈F w t (ν)δ t,ν ≤ (ε + α) X ν∈F w t (ν)≤ ε + α.(19) Moreover, sinceδ t,ν ≤ 1, P ν/∈F w t (ν)δ t,ν ≤ P ν/∈F w t (ν). BecauseFis finite andw t (ν)→ w ∞ (ν)pointwise, we have P ν∈F w t (ν)→ P ν∈F w ∞ (ν) , so by Eq. 18, P ν/∈F w t (ν) = 1− P ν∈F w t (ν)→ 1− P ν∈F w ∞ (ν)≤ α. Hence there exists t 1 such that for all t≥ t 1 , X ν/∈F w t (ν)≤ 2α.(20) Combining Eqs. 19 and 20, we obtain that for all t≥ maxt 0 ,t 1 , G t = X ν∈F w t (ν)δ t,ν + X ν/∈F w t (ν)δ t,ν ≤ (ε + α) + 2α. Since α > 0 is arbitrary, we conclude that lim sup t→∞ G t ≤ ε, ξ π -a.s. Theorem 4.10 (AIQI is not self-optimizing). Suppose the unified predictorψis built from classesP n that contain all computable variable-order Markov models. For any periodN, exploration rateτ, horizonH ≥ 2, toleranceεsmall enough (depending onH), and discretization levelMlarge enough (depending onH,ε,τ), there exist an environment classM, a historic policyπ ′ , and a discount factorγ ∈ (0, 1), for which there exists a self-optimizing policy, but the AIQI policy ˆπ H,M,N,τ ψ is not even ε-self-optimizing. Proof. Given H ≥ 2, define c H := max γ∈(0,1) (1− γ)γ H−1 = 1 H H − 1 H H−1 . Fix a tolerance ε∈ (0,c H ). Let γ := H − 1 H ∈ (0, 1), c := (1− γ)γ H−1 = c H . Choose δ := 1− ε/c 3 ∈ (0, 1), K ∈ N s.t. τ K ≤ δ 2 . Finally, assume M is large enough so that discretization cannot collapse the strict value gap: 1 M < c δ 2 equivalently M > 2 cδ .(21) Environment.LetA =1, 2,...,K,O =·,⋆, andR =0,δ, 1. The environmentμconsists of episodes of length H. For the firstH − 1steps of each episode, output(o,r) = (·, 0). On the last step output(o,r) = (⋆,r)whererdepends on the H actions taken in that episode: • if all H actions are 1, then r = 1; • if the first action is 1 but not all H actions are 1, then r = 0; • if the first action is not 1, then r = δ. Then a new episode starts and the construction repeats forever. Historic policy.Defineπ ′ episode-wise as follows. At the first step of an episode, sampleauniformly fromA. If this first action is not1, sample the remainingH − 1actions uniformly fromA. If the first action is1, then for each of the remaining H − 1 steps play 1 with probability p := δ 2 1/(H−1) , and otherwise sample uniformly from2,...,K. Then conditioned on starting an episode with action1, the probability of playing 1 for all remaining H − 1 steps is p H−1 = δ/2. Existence of a self-optimizing policy. SinceMis a singleton, theμ-optimal policyπ ∗ μ that always plays action1is trivially self-optimizing for (M,π ′ ). AIQI learns theπ ′ -value. Underμ π ′ , the (periodically augmented) discretized return process is a computable variable- order Markov model of orderO(H)(episode boundaries are marked by⋆and terminal rewards depend only on theH actions in the current episode). Becauseψis a Bayesian mixture over a class containing the true return-predictor forμ π ′ , Blackwell and Dubins [1962] implies thatψ’s posterior predictive distribution converges to the true conditional return distribution under μ π ′ . In particular, AIQI’s value estimate ˆ Q(h <t ,a) = X ̃z∈Z ̃z ψ( ̃z | h <t a) converges to the true conditional expectation of the discretized target z t under μ π ′ : Q π ′ μ (h <t ,a) := E π ′ μ [z t | h <t ,a t = a]. Now fix an episode-start timet(immediately after observing⋆). In this environment, the only nonzero reward within the next H steps is the terminal reward, so the H -step discounted return from t satisfies R t,H = (1− γ) H−1 X k=0 γ k r t+k = (1− γ)γ H−1 r t+H−1 = cr t+H−1 . If we force a t ̸= 1 and then follow π ′ , the terminal reward is deterministically δ, hence Q π ′ μ,H (h <t ,a̸= 1) = cδ. If we force a t = 1 and then follow π ′ , the terminal reward is 1 with probability δ/2 and 0 otherwise, hence Q π ′ μ,H (h <t ,a = 1) = c· δ 2 . Because AIQI optimizes the discretized targetz t =⌊MR t,H ⌋/Mand0≤ R t,H − z t < 1/Mpointwise, we have for each action a: Q π ′ μ,H (h <t ,a)− 1 M < Q π ′ μ (h <t ,a)≤ Q π ′ μ,H (h <t ,a). Therefore at episode starts, Q π ′ μ (h <t ,a̸= 1)− Q π ′ μ (h <t ,a = 1) ≥ c δ 2 − 1 M > 0 by (21). So action 1 is strictly suboptimal under the discretized π ′ -value at episode starts. Byμ π ′ -a.s. convergence of ˆ QtoQ π ′ μ , there exists at 0 such that for all episode-start timest≥ t 0 , AIQI’s exploitation choice a ∗ (h <t )̸= 1. Lower-bound on the self-optimization gap.Fix any episode-startt≥ t 0 . Sincea ∗ (h <t )̸= 1, AIQI chooses action1at timetwith probability at mostτ/K(it can only happen by uniform exploration). Hence the expected terminal reward of the next episode satisfies E ˆπ μ [r t+H−1 | h <t ] ≤ δ 1− τ K + 1· τ K ≤ δ + τ K ≤ 3δ 2 . Letπ ∗ denote the policy that always outputs action1. Thenπ ∗ achieves terminal reward1at the end of every episode, in particularE π ∗ μ [r t+H−1 | h <t ] = 1 . Because rewards are in[0, 1], the termwise differences at episode-terminal times are nonnegative, so V ∗ μ (h <t )− V ˆπ μ (h <t )≥ V π ∗ μ (h <t )− V ˆπ μ (h <t ) = (1− γ) ∞ X j=0 γ jH+H−1 1− E ˆπ μ [r t+jH+H−1 | h <t ] ≥ (1− γ)γ H−1 1− E ˆπ μ [r t+H−1 | h <t ] ≥ c 1− 3δ 2 . With our choice δ = (1− ε/c)/3, we have 1− 3δ 2 = 1− 1− ε/c 2 = 1 + ε/c 2 , so V ∗ μ (h <t )− V ˆπ μ (h <t ) ≥ c· 1 + ε/c 2 = c + ε 2 > ε. Episode starts occur infinitely often, hence lim sup t→∞ V ∗ μ (h <t )− V ˆπ μ (h <t ) > ε μ π ′ -a.s. Thus AIQI is not ε-self-optimizing for (M,π ′ ). C PROOFS FOR SELF-AIXI Lemma 5.2 (Convergence of ξ ζ to ν π ). For any environment ν ∈M and policy π ∈ P , lim t→∞ D ξ ζ ,ν π | h <t = 0, ν π -a.s. Proof. Since ν π is absolutely continuous w.r.t. ξ π , we obtain by Blackwell and Dubins [1962] that lim t→∞ D(ξ π ,ν π | h <t ) = 0, ν π -a.s. Similarly, we obtain that lim t→∞ D ξ ζ ,ξ π | h <t = 0, ξ π -a.s. ξ π -almost sure convergence impliesν π -almost sure convergence, sinceν π is absolutely continuous w.r.t.ξ π . By triangle inequality for total variation distance, we obtain the desired result. Lemma 5.4 (Average conditional TV bound). LetPandQbe probability measures onX ×Y, whereXis finite. LetP X and Q X denote the marginals onX . Then X x∈X P X (x)D P,Q| X = x ≤ 2D(P,Q). Proof. Define a probability measure R onX ×Y by R(x,dy) := P X (x)Q(dy | x). Thus, R has the same marginal on X as P , but uses the conditional law of Y | X from Q. We can show that D(P,R) = X x∈X P X (x)D P,Q| X = x , and that D(R,Q) = D(P X ,Q X ). Now apply the triangle inequality: D(P,R)≤ D(P,Q) + D(R,Q). Substituting the identities above gives X x∈X P X (x)D P,Q| X = x ≤ D(P,Q) + D(P X ,Q X ). Finally, total variation distance is non-increasing under measurable maps. Applying this to the projection(x,y)7→ x,we get D(P X ,Q X )≤ D(P,Q). Therefore, D(P,Q) + D(P X ,Q X )≤ 2D(P,Q), which completes the proof. Lemma 5.5 (Convergence of Q-value prediction forε-greedy Self-AIXI). Letπ = π S . For everyβ > 0, there exists a ν π -probability-one set S ⊆ Ω where, for every outcome h∈ S, there exists t 0 such that: for t≥ t 0 and m≥ t, X h ′ <m ∈T ,a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ Q (h ′ <m a ′ m ) < 2β (τ/|A|) −(m−t+1) . Proof. Fixβ > 0. By Lemma 5.2, there exists aν π -probability-one setS ⊆ Ωsuch that for everyh∈ Sthere is somet 0 with D(ν π ,ξ ζ | h <t ) < βfor all t≥ t 0 . Now fix h∈ S, t≥ t 0 , and m≥ t. By Lemma 5.4, X h ′ <m ∈T , a ′ m ∈A ν π h ′ t:m−1 a ′ m | h <t · D(ν π ,ξ ζ | h ′ <m a ′ m )≤ 2D(ν π ,ξ ζ | h <t ), and by Lemma 5.3, δ Q (h ′ <m a ′ m ) = Q ζ ξ (h ′ <m ,a ′ m )− Q π ν (h ′ <m ,a ′ m ) ≤ D(ν π ,ξ ζ | h ′ <m a ′ m ). Hence X h ′ <m ∈T , a ′ m ∈A ν π h ′ t:m−1 a ′ m | h <t · δ Q (h ′ <m a ′ m )≤ 2D(ν π ,ξ ζ | h <t ) < 2β. Since π S assigns probability of at least τ/|A| to each action, ν π h ′ t:m−1 a ′ m | h <t = m Y i=t π(a ′ i | h ′ <i ) m−1 Y i=t ν(e ′ i | h ′ <i a ′ i ) ≥ (τ/|A|) m−t+1 ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 ), and we obtain the desired result: X h ′ <m ∈T , a ′ m ∈A ν(e ′ t:m−1 | h <t ∥ a ′ t:m−1 )· δ Q (h ′ <m a ′ m ) < 2β (τ/|A|) −(m−t+1) . D MULTI-AGENT ENVIRONMENT The single-agent results in § 4.3 extend directly to multi-agent sequential interaction by viewing each agent as acting in a subjective environment induced by the other agents [Leike et al., 2016b, Section 4.1]. Considernagents interacting in a multi-agent environment σ : (A n ×E n ) ∗ ×A n → ∆(E n ), where at timetthe joint action and percept area t := (a 1 t ,...,a n t )ande t := (e 1 t ,...,e n t ). Agentionly observes its own action-percept history h i <t := a i 1 e i 1 ...a i t−1 e i t−1 . Givennpoliciesπ 1 ,...,π n , letσ i denote the subjective environment of agenti, obtained by combiningσwith the policies of the other agents and marginalizing out the components not observed by agenti. Together withπ i , this defines an ordinary environment-policy pair, so the formalism of the previous sections applies unchanged. We say that π i is an ε-best response at history h i <t if V ∗ σ i (h i <t )− V π i σ i (h i <t )≤ ε. If this holds for every i∈1,...,n, then the policies π 1:n is an ε-Nash equilibrium at time t. As in Definition 3.4, the key self-referential requirement is that each agent’s unified predictorψ i has a grain of truth with respect to its own subjective environmentσ i . A nontrivial instantiation can again be obtained by lettingP i n be the class of all O-computable return-predictors for every i and n, and assuming that the environment σ is O-computable. Theorem D.1 (AIQI converges toε-Nash equilibria). Fix a multi-agent environmentσand a toleranceε > 0. For each agent i∈1,...,n, let π i := ˆπ H i ,M i ,N i ,τ i ψ i , where the parametersH i ,M i ,N i ,τ i satisfy the conditions of Theorem 4.6 with toleranceε/2, and suppose thatψ i has a grain of truth with respect to the subjective environmentσ i induced byσand the policiesπ ̸=i . Then, the policiesπ 1:n converge to an ε-Nash equilibrium, σ π 1:n -almost surely. Proof. Fix an agent i. Since σ i is an ordinary environment for agent i, Theorem 4.6 applied with tolerance ε/2 gives lim sup t→∞ V ∗ σ i (h i <t )− V π i σ i (h i <t ) ≤ ε/2, σ π i i -a.s. Becauseσ π i i is exactly the marginal of the joint history distributionσ π 1:n on agenti’s coordinates, the same statement holds σ π 1:n -almost surely. Hence, for σ π 1:n -almost every outcome h, there exists t i such that V ∗ σ i (h i <t )− V π i σ i (h i <t )≤ εfor all t≥ t i . Since there are finitely many agents, intersecting these probability-one events overistill yields a probability-one event. Takingt 0 := max i t i proves that all agents are simultaneouslyε-best responses for allt≥ t 0 , which is exactly the claim. E GENERAL DISCOUNT SEQUENCES We can extend all our results to general time-consistent discount sequences [Hutter et al., 2024, p. 245] that decay faster than a geometric sequence. First, we should introduce the relevant concepts. A time-consistent discount sequence is a sequenceγ k ∞ k=1 withγ k ≥ 0 and P ∞ k=1 γ k <∞. An example is the geometric discount sequenceγ k = γ k . The discount normalization factor is defined as Γ t = P ∞ k=t γ k . The full return at time t is defined as R t = 1 Γ t ∞ X k=t γ k r k , and the value functionsVandQare defined withR t as in § 2.1. The value functions satisfy the general discount Bellman equations: V π ν (h <t ) = X a ′ t ∈A π(a ′ t | h <t )Q π ν (h <t ,a ′ t ), Q π ν (h <t ,a t ) = 1 Γ t X e ′ t ∈E ν(e ′ t | h <t a t ) γ t r t + Γ t+1 V π ν (h <t a t e ′ t ) . H -step returns and values are defined as in § 2.1. We define the η-effective horizon at time t as H t (η) := min H ∈ Z + Γ t+H Γ t ≤ η . One can easily show that theH t (η)-step return attdiffers from the full return attby at mostη. If a discount sequence decays faster than a geometric sequence, i.e., lim sup t→∞ γ t+1 γ t < λ for some λ < 1, the effective horizon H t (η) for a fixed η has an upper bound across all t. We only need to modify our proofs and results in several places to accommodate the generalization. • The statement of Lemma 4.5 should change to δ ∞ (h <t )≤ Γ t+1 Γ t X e ′ t ν(e ′ t | h <t a ′ t )δ ∞ (h <t a ′ t e ′ t ) + δ 1 (h <t ), which is just the original statement withγreplaced byΓ t+1 /Γ t . The logic of its proof remains the same, except that we should use the general discount Bellman equation instead of the geometric discount Bellman equation, in one of its steps. • The chain of inequalities resulting from Lemma 4.5 should be slightly modified: γ l turns into Γ t+l /Γ t . • In the proof of Theorem 4.6, the core inequality should be changed to δ ∞ (h <t ) < Γ t+L Γ t + L−1 X l=0 Γ t+l Γ t 2(2β τ |A| −(l+1) + M −1 + η) + 2τ , so that for large enough t, δ ∞ (h <t ) < λ L + L−1 X l=0 λ l 2(2β τ |A| −(l+1) + M −1 + η) + 2τ . •Theorem 4.6 thus generalizes to general discount sequences that decay faster than a geometric sequence. It suffices to change γ with λ in the criterion for parameters, and use H = lim sup t H t (η) + 1. • Theorem 4.8 and Theorem D.1 generalize accordingly. F AIQI-CTW We introduce AIQI-CTW, a computable instantiation of AIQI with the context tree weighting [CTW; Willems et al., 1995] algorithm. We also provide experiments that compare AIQI-CTW and MC-AIXI-CTW [Veness et al., 2011]. The source code for experiments can be found at https://github.com/yegonkim/aiqi. Context tree weighting. Context Tree Weighting (CTW) is a fast, principled method for doing Bayesian sequence prediction over binary strings. It builds a variable-order Markov model by maintaining a context tree up to some maximum depth. Rather than committing to a single context length, CTW mixes predictions from all context depths using an efficient recursive weighting scheme, which effectively performs Bayesian model averaging over a large family of context trees. Remarkably, it makes online predictions by updating in time linear in the context depth, assigns non-zero probability to all sequences, and tends to quickly exploit repeated structure. ParameterBiased Rock-Paper-ScissorsKuhn Poker4×4 Grid MC-AIXI-CTWAIQI-CTWMC-AIXI-CTWAIQI-CTWMC-AIXI-CTWAIQI-CTW Horizon H—4—2—12 Period N—4—2—12 Discretization M—9—9—13 Baseline exploration τ—0.01—0.01—0.01 Exploration (initial)0.9990.9990.990.9990.9990.999 Explore decay rate0.999990.99990.99990.99990.99990.9999 CTW depth323242429696 MCTS horizon4—2—12— MCTS simulations200—200—40— Learning period500010000050001000005000100000 Terminating age100001000001000010000010000100000 Table 2: Hyperparameters for MC-AIXI-CTW and AIQI-CTW across environments Implementation. AIQI-CTW is an instantiation of AIQI that uses CTW as its return-predictorψ n . MC-AIXI-CTW is similarly an approximation of AIXI that uses CTW as the environment model, and additionally a Monte Carlo Tree Search [MCTS; Coulom, 2006] algorithm that replaces exact planning. AIQI-CTW usesNCTW models, each corresponding to one of theNreturn-predictors. They receive the augmented sequences as described in § 3, to predict theM-discretizedH-step returns. All rewards, observations, actions, and discretized returns are represented as blocks of bits. Note that the weighted probabilities of CTW are updated only with the bits corresponding to returns. This is in line with Definition 3.1. Expectation over returns is taken in an exact manner by computing all the probabilities. The implementation of MC-AIXI-CTW was taken from the pyaixi repository 1 , and AIQI-CTW was adapted from this implementation. Experimental setup. We tested the algorithms on 3 environments: “Biased Rock-Paper-Scissor”, “Kuhn Poker”, and “4×4 Grid”. Biased Rock-Paper-Scissor is a repeated rock paper scissors game against an opponent with a simple exploitable bias: if it won the previous round by playing rock it plays rock again, otherwise it plays uniformly at random. Kuhn Poker is a simplified two-player, zero-sum poker game with a three-card deck (K, Q, J) in which players alternately choose between pass and bet under hidden information, capturing core phenomena such as bluffing and slow-playing. The 4×4 Grid task is a small gridworld environment in which an agent moves on a 4-by-4 lattice using the primitive actions up, down, left, right (with boundary constraints) to reach a designated goal state and receive reward. More details on the environments and experimental setup can be found in Veness et al. [2011]. Hyperparameters.For MC-AIXI-CTW, we use the default hyperparameter used in Veness et al. [2011]. One exception is the terminating age, which was reduced to keep the runtime manageable. The number of MCTS simulations in 4×4 Grid was also reduced for the same reason. For AIQI-CTW, we use a decayingε-greedy exploration and a minimum baseline exploration rateτ. The CTW depth and horizonHwere chosen to equal those of MC-AIXI-CTW. Note that we choose N = H, since the buffer periodN − Hwas introduced in § 4 solely as a theoretical device for proofs. We report all the important hyperparameters in Table 2. Results.We performed each experiment on 8 seeds. Fig. 1 is a plot of the exponential moving average (EMA) of reward (withα = 10 −3 ) against wall clock time. AIQI-CTW spends much less time in deciding an action than MC-AIXI-CTW, since it doesn’t involve planning with MCTS. In all experiments we find that AIQI-CTW has an advantage over MC-AIXI- CTW given the restricted computational budget. Note that optimal performance can be obtained with MC-AIXI-CTW, albeit with orders of magnitude more compute, as described in Veness et al. [2011]. 1 https://github.com/sgkasselau/pyaixi 05001000 0.0 0.5 1.0 EMA Reward Biased Rock Paper Scissors 0250500750 Time (s) 1 2 Kuhn Poker 0100020003000 0.0 0.1 0.2 4x4 Grid MC-AIXI-CTWAIQI-CTWOptimal 050000100000 0.0 0.5 1.0 EMA Reward Biased Rock Paper Scissors 050000100000 Step 0 1 2 Kuhn Poker 050000100000 0.0 0.1 0.2 4x4 Grid MC-AIXI-CTWAIQI-CTWOptimal Figure 1: Plots of EMA reward vs wall clock time (in seconds) and environment steps on three environments.