Formalizing Embeddedness Failures in Universal Artificial Intelligence

Cole Wyeth; Marcus Hutter

REVIEW 4 major objections 6 minor 16 references

Formalizing Embeddedness Failures in Universal Artificial Intelligence

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that joint AIXI—the direct embedded variant that models actions and percepts by the universal distribution—fails to learn even the trivial environment that echoes each action, given adversarially chosen actions.

desk verdict Proves a real but off-policy failure of the joint-AIXI belief; honest about the gap, but the title overstates what is established about the agent. read the letter →

arxiv 2505.17882 v1 pith:YNC3GLG4 submitted 2025-05-23 cs.AI

Cole Wyeth , Marcus Hutter This is my paper · ORCID

classification cs.AI MSC 68Q30

keywords embeddedagencyuniversalartificialintelligenceAIXIdistributionadversarialactionsequencesemimeasureevidentialdecisiontheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper formalizes a suspicion that has been treated as folklore in artificial intelligence research: that a direct route to 'embedded agency'—modeling the agent's actions and percepts as one sequence drawn from the universal distribution—breaks down. The authors define joint AIXI, whose belief is the environment version $\xi_U := \operatorname{env}(\xi_U)$ of the universal distribution, and prove that under adversarially chosen actions it fails to learn even the environment $\mu_{\mathrm{id}}$ that simply echoes each action back as the reward. Concretely, there exists an action sequence along which the agent's probability for the correct percept tends to $0$ (Theorem 7), and as a consequence joint AIXI's belief does not dominate the standard AIXI environment $\xi_{\mathrm{AI}}$ (Theorem 8), so the usual AIXI learning guarantees do not transfer. The paper also proves a positive result: normalizing the universal distribution to a proper measure restores learning of deterministic environments, and it reviews why reflective-oracle constructions are the more reliable response to embeddedness.

What carries the argument

The key machinery is the pair of distributions $\xi_U$ and $\xi_{\mathrm{AI}}$ together with the maps $\operatorname{env}$ and $\operatorname{dual}$. $\operatorname{env}$ turns a sequence semimeasure into a chronological environment by conditioning on the action prefix; $\operatorname{dual}(\nu,\pi)$ combines a policy and an environment into a history distribution. The paper's negative theorems are direct translations of the selected-bits theorem of [LHG11], which constructs adversarial binary sequences on which the universal distribution fails to learn even indices that exactly repeat the preceding odd indices. The decisive object is the action-conditional posterior weight $w_i(h_{<t}a_t) = \nu_i(h_{<t}a_t)/\xi_U(h_{<t}a_t)$, which makes $\xi_U$ an evidential-decision-theoretic mixture and is precisely what breaks chronological dominance over $\xi_{\mathrm{AI}}$.

What would settle it

Run or reason about the joint AIXI policy $\pi_{\mathrm{JAIXI}}$ on the echo environment $\mu_{\mathrm{id}}$ and check whether the posterior probability $\xi_U(a_{1:t}\|a_{1:t})$ along the policy's own trajectory remains bounded away from zero. If the policy never produces the adversarial action sequence of Theorem 7, the worst-case collapse does not apply to the actual agent; if it does, the paper's negative result extends to the on-policy setting. Equivalently, any explicit demonstration that $\pi_{\mathrm{JAIXI}}$ follows an adversarial sequence $a$ for which $\xi_U(a_{1:t}\|a_{1:t}) \to 0$ would make the failure on-policy, while a proof that it avoids all such sequences would bound the practical damage.

Watch

Extended reading notes

Core claim

The central discovery is the pair of negative theorems for the joint AIXI belief $\xi_U := \operatorname{env}(\xi_U)$. Theorem 7 states that there exists an action sequence $a \in B^\infty$ such that $\xi_U(a_{1:t}\|a_{1:t}) \to 0$ as $t \to \infty$ even for the trivial chronological environment $\mu_{\mathrm{id}}(e_t \mid h_{<t}a_t) = [e_t = a_t]$. Theorem 8 then states that $\xi_U$ does not multiplicatively dominate the standard universal environment $\xi_{\mathrm{AI}}$, since $\xi_{\mathrm{AI}}$ assigns probability 1 to the echo history while $\xi_U$'s probability vanishes along the adversarial sequence. The mechanism is $\xi_U$'s action-conditioned re-weighting: the posterior weights $w_i = \nu_i(h_{<t}a_t)/\xi_U(h_{<t}a_t)$ favor environments that assign high probability to the actions actually taken, making $\xi_U$ behave like an evidential decision theory and allowing the agent's own actions to corrupt its predictions. A positive counterpart shows that the normalized universal distribution $\hat{\xi}_U$, a proper measure, learns every deterministic l.s.c. environment whose next percept is a recursive function of the history.

Load-bearing premise

The negative theorems assume the action sequence is adversarially chosen rather than generated by the joint AIXI policy itself, and the paper states that it is unknown whether the deployed policy ever produces such adversarial action sequences.

Editorial extensions

If this is right

The naive 'joint' embedding of AIXI does not inherit AIXI's dominance guarantees; in the worst case the agent can be arbitrarily wrong despite a trivial environment.
The negative results are confined to adversarially chosen actions, so on-policy behavior of the deployed joint AIXI policy is not settled by this paper.
Normalizing the universal distribution to a proper measure recovers learning for deterministic environments, linking the failure to the semimeasure's probability gap rather than to joint modeling per se.
The analysis supports the view that realizable embedded agents should draw their own actions from the hypothesis class, as reflective-oracle constructions do, rather than treat actions as exogenous adversarial inputs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A concrete next step would be to test empirically whether $\pi_{\mathrm{JAIXI}}$ on the echo environment ever follows the adversarial sequences from Theorem 7; if it does not, the worst-case failure may be irrelevant to the deployed agent, but if it does, the negative results extend on-policy.
The same selected-bit construction may apply to any embedded agent whose predictive distribution is a non-normalized universal mixture over the joint action-percept history, so the failure may be generic rather than specific to this definition of joint AIXI.
The normalization result hints at a cheap repair: a normalized joint AIXI might serve as a practically viable embedded learner for deterministic worlds, leaving the stochastic case as the real boundary of the repair.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the paper proves something real but narrower than the title suggests. The joint AIXI belief ξU does not dominate ξAI, and there is an adversarially chosen action sequence on which ξU fails to learn even the echo environment. But the failure is off-policy: the authors concede in Section 6 that πJAIXI may never pick those sequences, so the phrase 'embeddedness failure' is not actually established for the agent.

What's new: the explicit joint AIXI definition in Eq. (9) cleanly formalizes a commonly hand-waved idea, and Theorem 8 is the first proof I know that the resulting belief is not a dominating alternative to ξAI. The reduction to Lattimore-Hutter-Gavane's selected-bits results is sensible, and the translation into chronological semimeasures is careful. I also like the positive Theorem 10: Solomonoff normalization recovers learning of deterministic environments even under adversarial actions, which is genuinely surprising and useful.

Soft spots, in proportion. The off-policy gap is central: the LHG11 counterexample sequence in Theorem 7 has to be noncomputable, while πJAIXI is a fixed policy that might well produce a computable sequence; nothing rules out on-policy success. The authors say this openly, so the paper is not dishonest, but the framing runs ahead of the result. Second, Theorem 7 is stated as a 'direct result' with no derivation; a minor annoyance given how careful the rest is. Third, the paper relies on two unpublished manuscripts (WH25, WHLT25) for technical support, which makes independent checking harder. Fourth, non-domination of beliefs does not by itself imply bad policy behavior; the paper does not claim otherwise, but readers should keep that in mind.

The math looks sound: the central proof is a reduction to a published theorem, and the l.s.c. semimeasure representation caveat is flagged in footnote 2 rather than hidden. The citation pattern is legitimate; the self-citations are on point and the reliance on LHG11 is transparent.

This is for people working on universal induction, decision theory, and embedded agency. It clears up a previously assumed failure and points to an open on-policy question. I'd send it to a serious referee, with the instruction to press on the on-policy gap and the title's overreach. I would cite it as a specific off-policy non-convergence result, not as a demonstration that joint AIXI fails as an embedded agent.

Referee Report

4 major / 6 minor

Summary. The paper studies an 'embedded' variant of AIXI, called joint AIXI, whose belief is obtained by applying the env map to Solmonoff's universal semimeasure ξU over joint action-percept sequences, so that actions and percepts are modeled symmetrically. The main results are: Theorem 7, which asserts that for the echo environment μ_id there exists an action sequence a such that ξU(a_{1:t}||a_{1:t}) → 0; Theorem 8, which concludes from this that the joint AIXI belief ξU does not dominately dominate the standard AIXI environment ξAI; and Theorem 11, which claims that a Solomonoff-normalized version of ξU can learn deterministic environments even under adversarially chosen actions. Section 6 explicitly concedes that the negative results assume adversarially selected action bits and that the on-policy behavior of the joint AIXI policy πJAIXI is not known.

Significance. If the negative theorems are taken as statements about the joint AIXI agent, they would constitute a striking formalization of a suspected embeddedness failure. The reduction to the published selected-bits result of Lattimore, Hutter, and Gavane [LHG11] is a useful and nontrivial connection, and the paper is commendably explicit about its own limitations. The positive normalization result (Theorem 11) is also a meaningful contribution. However, as the paper itself concedes, the negative theorems quantify over adversarially chosen action sequences rather than over the actions generated by the joint AIXI policy, and non-domination of beliefs does not by itself imply suboptimal behavior. The advertised conclusion that joint AIXI exhibits embeddedness failures is therefore not established; the paper's solid contribution is an off-policy analysis of the joint universal belief, with an honest statement of the open on-policy problem.

major comments (4)

[§5, §6] The central negative claim is not established for the agent. Theorems 7 and 8 (Section 5) construct an adversarial action sequence a ∈ B^∞ for which ξU(a_{1:t}||a_{1:t}) → 0, but the object the paper wishes to indict is the joint AIXI policy πJAIXI := π*_{ξU} defined in Eq. (9), whose action choices are selected by expected-reward maximization rather than adversarially. Section 6 concedes this: 'we assume adversarially selected action bits. For a deployed agent, the action bits would be selected by the policy πJAIXI which may never produce these adversarial action sequences, so we do not know whether πJAIXI learns to behave well in reasonable environments.' Since multiplicative non-domination of beliefs (Theorem 8) does not imply suboptimal behavior of the corresponding policy, the paper does not prove that joint AIXI fails as an embedded agent. The authors should either provide an on-policy failure result, or explicitly reframe the paper's contribution as an off-policy prediction failure of the belief ξU.
[Theorem 7] The proof of Theorem 7 is a single sentence: 'This is a direct result of Theorem 6.' The reduction is not written out, and it is load-bearing. Theorem 6 concerns the sequence-level conditional probability ξU(ω_{2n}|ω_{1:2n-1}) at even positions of a binary string, while Theorem 7 concerns the chronological environment probability ξU(a_{1:t}||a_{1:t}) = ∏_{i=1}^t ξU(e_i = a_i | a_{1:i-1}e_{1:i-1}a_i). The connection between the two requires the semimeasure representation of Section 3 and needs to be made explicit, including the caveat of footnote 2. Without this derivation, a reader cannot verify that the noncomputable sequence produced by [LHG11, Theorem 12] indeed yields an action sequence satisfying the domination-failure condition in Definition 5.
[Footnote 2 / §3] The paper relies on converting the l.s.c. sequence semimeasure ξU into the chronological environment env(ξU), but footnote 2 states that the semimeasure representation 'does not seem to hold when we restrict to l.s.c. (chronological) semimeasures.' This is a missing proof, not merely a caveat, because Theorem 7 and the definition of ξU = env(ξU) in Section 5 assume that this conversion is legitimate for the specific universal semimeasure. The authors should either prove the needed instance of the representation or state the negative theorems directly in terms of the sequence distribution without passing through env.
[Theorem 11] The proof of Theorem 11 asserts without proof that a deterministic l.s.c. environment 'must also be recursive in the sense that the next percept is finitely computable from the history.' This is plausible, and for binary alphabets it follows from the l.s.c. condition applied to both the indicator of the observed percept and its complement, but the argument is not given. Since Theorem 11 is the paper's main positive result, this unproved equivalence should be supplied. Additionally, the application of Theorem 10 requires identifying the recursive function f at every time step; the proof should state explicitly which function is used and why its domain includes all relevant histories.

minor comments (6)

[§3, Eq. (2)-(4)] The notation '×=' is used in Eqs. (2) and (4) and in Definition 5 but is never defined; it appears to mean equality up to a multiplicative constant, and this should be stated explicitly.
[§3, Definition 3] The sentence 'For simplicity of exposition we assume A=E by expanding the smaller alphabet' appears immediately after the definition of ξU, but it is not clear how the expansion interacts with the action/percept split in later definitions; a short explanation would help.
[§5, Eq. (7)] In the chain of equalities in Eq. (7), the summation index switches from i to ν without comment in the third and fourth lines; this should be made consistent.
[§3, Footnote 1 and Definition 3] The paper cites [WH25] for the 'unique sensible extension' of a pre-semimeasure to a σ-algebra and [WHLT25] for a result about Self-AIXI, but both are listed as 'under review.' For load-bearing technical claims, the authors should either provide full proofs in the manuscript or cite published versions.
[Abstract and §6] The abstract states that the paper proves embeddedness failures 'occur,' while Section 6 limits the negative results to the adversarial action protocol and explicitly leaves on-policy behavior open. The abstract and introduction should be aligned with the actual scope of the theorems, e.g., by referring to off-policy prediction failures of ξU.
[§4] The definition of the weights w^π_ν = ω_π w_ν = 2^{-K(π)}2^{-K(ν)} in Section 4 relies on the Kolmogorov complexity K, which is introduced only informally in the notation section; a precise definition or reference would improve accessibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the negative theorems are explicit corollaries of the prior published LHG11 selected-bit results, and Section 6 concedes the on-policy question remains open.

full rationale

The derivation chain is self-contained and cites prior work appropriately rather than importing its conclusion. Theorem 6 is a direct translation of [LHG11, Theorem 12], a peer-reviewed result about universal prediction of selected bits; its assumptions concern arbitrary binary sequences and do not mention joint AIXI or μ_id, so it is independent evidence. Theorem 7 then specializes that sequence to the echo environment μ_id (Eq. (10)) via the definition ξ_U := env(ξ_U), and Theorem 8 combines this with the standard universality property that ξ_AI dominates every l.s.c. chronological semimeasure, including μ_id. No parameter is fitted to data and no prediction is defined in terms of the quantity it is said to predict. The self-citations include LHG11, whose overlap in authorship with Hutter is normal and does not make the cited theorem circular, since the theorem is published, parameter-free, and does not assume the present paper's target; the unpublished citations (WH25, WHLT25) are used only for context or side remarks, not for Theorems 7–8. Finally, the authors explicitly state in Section 6 that their negative results hold under adversarially selected action bits and that on-policy behavior of π_JAIXI remains unknown, so they do not present an unsupported conclusion as a forced consequence of an input.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters or invented physical entities. It relies on standard Solomonoff induction and AIXI machinery, plus two external theorems from LHG11. The main modeling assumption is the adversarial treatment of actions, which the authors explicitly flag.

assumptions (4)

standard math Existence and properties of universal lower semicomputable semimeasure ξ_U and universal chronological semimeasure ξ_AI.
These are standard constructs in algorithmic information theory, introduced in Definitions 3 and 4 and used throughout.
standard math Theorems 10 and 12 from Lattimore, Hutter, and Gavane (LHG11) are valid and applicable to the sequences used here.
The proof of Theorem 7 and the positive result Theorem 11 rely directly on these external results, which are cited but not proven in this paper.
domain assumption The alphabets for actions and percepts can be assumed equal (A = E) without loss of generality.
Stated in Section 3: 'For simplicity of exposition we assume A=E by expanding the smaller alphabet.' This is harmless but a modeling convenience.
domain assumption The interaction history can be modeled with actions chosen adversarially for worst-case analysis.
Section 1 states 'we will treat it as adversarially chosen and consider the worst case.' This is load-bearing for the negative results, as acknowledged in Section 6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Formalizing Embeddedness Failures in Universal Artificial Intelligence." pith.science (2026). https://pith.science/paper/YNC3GLG4

@misc{pith2026250517882,
  author       = {Pith},
  title        = {Pith review of: Formalizing Embeddedness Failures in Universal Artificial Intelligence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YNC3GLG4}},
  note         = {Machine review of arXiv:2505.17882}
}

read the original abstract

We rigorously discuss the commonly asserted failures of the AIXI reinforcement learning agent as a model of embedded agency. We attempt to formalize these failure modes and prove that they occur within the framework of universal artificial intelligence, focusing on a variant of AIXI that models the joint action/percept history as drawn from the universal distribution. We also evaluate the progress that has been made towards a successful theory of embedded agency based on variants of the AIXI agent.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

[1]

Blackwell and L

D. Blackwell and L. Dubins. Merging of opinions with increasing information. Annals of Mathematical Statistics , 33:882--887, 1962

work page 1962
[2]

Self- Predictive Universal AI

Elliot Catt, Jordi Grau-Moya, Marcus Hutter, Matthew Aitchison, Tim Genewein, Grégoire Delétang, Kevin Li, and Joel Veness. Self- Predictive Universal AI . Advances in Neural Information Processing Systems , 36:27181--27198, December 2023

work page 2023
[3]

Towards a New Decision Theory

Wei Dai. Towards a New Decision Theory . August 2009

work page 2009
[4]

Sequential extensions of causal and evidential decision theory, 2015

Tom Everitt, Jan Leike, and Marcus Hutter. Sequential extensions of causal and evidential decision theory, 2015

work page 2015
[5]

Reflective Variants of Solomonoff Induction and AIXI

Benja Fallenstein, Nate Soares, and Jessica Taylor. Reflective Variants of Solomonoff Induction and AIXI . In Jordi Bieger, Ben Goertzel, and Alexey Potapov, editors, Artificial General Intelligence , pages 60--69, Cham, 2015. Springer International Publishing

work page 2015
[6]

Reflective Oracles: A Foundation for Classical Game Theory

Benja Fallenstein, Jessica Taylor, and Paul F. Christiano. Reflective Oracles : A Foundation for Classical Game Theory , August 2015. arXiv:1508.04145 [cs]

work page Pith review arXiv 2015
[7]

On semimeasures predicting Martin - Löf random sequences

Marcus Hutter and Andrej Muchnik. On semimeasures predicting Martin - Löf random sequences. Theoretical Computer Science , 382(3):247--261, September 2007

work page 2007
[8]

A Theory of Universal Artificial Intelligence based on Algorithmic Complexity , April 2000

Marcus Hutter. A Theory of Universal Artificial Intelligence based on Algorithmic Complexity , April 2000. arXiv:cs/0004001

arXiv 2000

Show all 16 references

[9]

Universal Artificial Intellegence

Marcus Hutter. Universal Artificial Intellegence . Texts in Theoretical Computer Science An EATCS Series . Springer, Berlin, Heidelberg, 2005

2005
[10]

Infra- Bayesian physicalism: a formal theory of naturalized induction, November 2021

Vanessa Kosoy. Infra- Bayesian physicalism: a formal theory of naturalized induction, November 2021

2021
[11]

On the computability of Solomonoff induction and AIXI

Jan Leike and Marcus Hutter. On the computability of Solomonoff induction and AIXI . Theoretical Computer Science , 716:28--49, March 2018

2018
[12]

Universal Prediction of Selected Bits

Tor Lattimore, Marcus Hutter, and Vaibhav Gavane. Universal Prediction of Selected Bits . In Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann, editors, Algorithmic Learning Theory , pages 262--276, Berlin, Heidelberg, 2011. Springer

2011
[13]

A formal solution to the grain of truth problem

Jan Leike, Jessica Taylor, and Benya Fallenstein. A formal solution to the grain of truth problem. In Proceedings of the Thirty - Second Conference on Uncertainty in Artificial Intelligence , UAI '16, pages 427--436, Arlington, Virginia, USA, June 2016. AUAI Press

2016
[14]

Space- Time Embedded Intelligence

Laurent Orseau and Mark Ring. Space- Time Embedded Intelligence . In Joscha Bach, Ben Goertzel, and Matthew Iklé, editors, Artificial General Intelligence , pages 209--218, Berlin, Heidelberg, 2012. Springer

2012
[15]

Value under ignorance in universal artificial intelligence

Cole Wyeth and Marcus Hutter. Value under ignorance in universal artificial intelligence. (under review) 2025

2025
[16]

Limit-computable grains of truth for arbitrary computable extensive-form (un)known games

Cole Wyeth, Marcus Hutter, Jan Leike, and Jessica Taylor. Limit-computable grains of truth for arbitrary computable extensive-form (un)known games. (under review) 2025

2025

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Blackwell and L

D. Blackwell and L. Dubins. Merging of opinions with increasing information. Annals of Mathematical Statistics , 33:882--887, 1962

work page 1962

[2] [2]

Self- Predictive Universal AI

Elliot Catt, Jordi Grau-Moya, Marcus Hutter, Matthew Aitchison, Tim Genewein, Grégoire Delétang, Kevin Li, and Joel Veness. Self- Predictive Universal AI . Advances in Neural Information Processing Systems , 36:27181--27198, December 2023

work page 2023

[3] [3]

Towards a New Decision Theory

Wei Dai. Towards a New Decision Theory . August 2009

work page 2009

[4] [4]

Sequential extensions of causal and evidential decision theory, 2015

Tom Everitt, Jan Leike, and Marcus Hutter. Sequential extensions of causal and evidential decision theory, 2015

work page 2015

[5] [5]

Reflective Variants of Solomonoff Induction and AIXI

Benja Fallenstein, Nate Soares, and Jessica Taylor. Reflective Variants of Solomonoff Induction and AIXI . In Jordi Bieger, Ben Goertzel, and Alexey Potapov, editors, Artificial General Intelligence , pages 60--69, Cham, 2015. Springer International Publishing

work page 2015

[6] [6]

Reflective Oracles: A Foundation for Classical Game Theory

Benja Fallenstein, Jessica Taylor, and Paul F. Christiano. Reflective Oracles : A Foundation for Classical Game Theory , August 2015. arXiv:1508.04145 [cs]

work page Pith review arXiv 2015

[7] [7]

On semimeasures predicting Martin - Löf random sequences

Marcus Hutter and Andrej Muchnik. On semimeasures predicting Martin - Löf random sequences. Theoretical Computer Science , 382(3):247--261, September 2007

work page 2007

[8] [8]

A Theory of Universal Artificial Intelligence based on Algorithmic Complexity , April 2000

Marcus Hutter. A Theory of Universal Artificial Intelligence based on Algorithmic Complexity , April 2000. arXiv:cs/0004001

arXiv 2000