Value Under Ignorance in Universal Artificial Intelligence

AI summary

Overview

Research area: Universal artificial intelligence, specifically the AIXI reinforcement learning agent, general reinforcement learning, algorithmic information theory (semimeasures), and imprecise probability / Choquet integration.

Technical level: Advanced. The paper is mathematical throughout: Cantor space topology, σ-algebras, Carathéodory extension, upper/lower semicomputability, and Choquet integrals.

Scope (one sentence): The paper generalizes AIXI from maximizing discounted reward to maximizing the expectation of an arbitrary continuous utility function, develops the semimeasure theory needed to make such expectations rigorous, and compares two readings of semimeasure loss—"chance of death" versus "total ignorance," the latter handled with Choquet integrals over the core of an imprecise probability.

What This Paper Is About

AIXI is a clean, nearly parameter-free model of general intelligence, but it is tied to the reinforcement learning setting: it maximizes an external reward signal, which limits the goals it can represent. The authors ask what happens when the reward-sum is replaced by an arbitrary utility function over interaction histories, including utilities assigned to finite histories that may terminate early. Because AIXI's belief distribution consists of "defective" semimeasures whose probabilities may sum to less than one, assigning utilities to histories forces a choice about what that missing probability (the semimeasure loss) actually means, and the paper investigates the consequences of two different readings.

Key Contributions

1. A rigorous semimeasure extension. The paper proves (Theorem 4.1) that a probability pre-semimeasure ν₀ on strings extends uniquely to a probability measure P on Ω′ = 𝒜* ∪ 𝒜^∞, and that ν(S) := Σ_{xA^∞ ⊆ S} P(x) + P(S) extends ν₀ to a semimeasure on (Ω, ℱ) = (𝒜^∞, σ(ℭ_𝒜)), with P(x) = L_ν(x). The proof idea is a routine application of Carathéodory's extension theorem, with superadditivity replacing σ-additivity.

2. Equivalence between the recursive value function and a Choquet integral. Theorem 6.1 shows V^{π}{ν} = 𝖢∫(Σ_t γ_t r_t) dν^π, connecting classical history-based RL value functions to imprecise-probability integration. Lemma 1 shows the Choquet integral of f with respect to a termination semimeasure equals the integral of the lower envelope u̲ (defined as u̲(x) = inf{ω ∈ x𝒜^∞} u(ω)) with respect to P_ν; this is noted as a special case of [GS94, Thm.4.3] and [GS95, Thm.E].

3. A general utility-based AIXI. Definition 9 defines V^{π}{ν,u} = ∫ u dP{ν^π} for a continuous utility u : ℋ* ∪ ℋ^∞ → ℝ⁺, with a universal mixture ξ^AI over l.s.c. chronological semimeasures using weights w_ν := 2^{−K(ν)}. The paper shows an optimal policy exists (from compactness of Cantor space and continuity of u, in an argument similar to [LH14, Thm.8]) and derives lower semicomputability of the resulting value functions (Theorem 7.1).

4. A comparison of two interpretations of semimeasure loss. The paper contrasts the "death" reading (finite histories get utilities, semimeasure loss as a chance of termination) with a credal-set reading (semimeasure loss as total ignorance, evaluated by the Choquet integral). It reports that the credal-set view can give better computability properties and recovers the standard recursive value function as a special case, while the most general expected utilities under the death interpretation cannot be characterized as Choquet integrals.

Main Findings

• Choquet integral equals pessimistic minimum over the credal set. By [GS95, Thm.2.1&2.2], for bounded measurable f and convex semimeasure ν (which includes the termination semimeasures studied here), 𝖢∫ f dν = min_{p ∈ Core(ν)} ∫ f dp. The corresponding decision rule is therefore max-min (pessimistic).

• The recovery of the recursive value function is, in the authors' words, "almost coincidental." The Choquet integral of Σ_t γ_t r_t matches V^{π}{ν} because the minimizing distribution concentrates the loss L{ν^π}(æ_{1:t}) on histories with r_{t+1:∞} = 0; as noted by [MEH16], transitioning to an absorbing zero-reward death state is the same as terminating and awarding the partial discounted sum.

• A continuity requirement is needed for optimal policies to exist. Example 3 gives a utility function with binary action set that pays reward 1 − 1/t the first time action 1 is taken, with no discounting; it is well-defined but not continuous and has no optimal policy, since it is always better to take action 1 one step later.

• Lower semicomputability carries over for the Choquet-integral form (Theorem 7.1). If u : ℋ^∞ → ℝ⁺ is l.s.c. and continuous, then u̲ is l.s.c. and continuous; if ν^π is l.s.c. then V^{π}{ν,u̲} is l.s.c., and if ν is l.s.c. then the optimal value V*{ν,u̲} = max_π 𝖢∫ u dν^π is l.s.c. The proof idea uses König's lemma plus approximation by l.s.c. simple functions and the monotone convergence theorem.

• The Choquet-integral form is essential for that computability result. The paper states the value function may not be l.s.c. otherwise, and that the most general expected utilities under the death interpretation cannot be characterized as Choquet integrals.

• The "death" utility is not l.s.c. in general. For u_r(æ) := Σ_{t=1}^{l(æ)} γ_t r_t, u_r is continuous and l.s.c. (even estimable) when Σ_t γ_t < ∞. But when inf ℛ < 0 and γ_t > 0 for all t, u_r(æ_{≤t}) ≠ inf_{ω ∈ æ_{≤t}ℋ^∞} u_r(ω), so V^{π}{ν,u_r} is not l.s.c. in general; inverting a positive set of rewards including 0 produces a u.s.c. value function typically not l.s.c. When 0 ∈ ℛ ⊂ ℝ⁺, however, V^{π}{ν,u_r} = V^{π}_{ν,u̲} for u̲ of Σ_t γ_t r_t, implying lower semicomputability.

• Example 1 (a simple defective semimeasure): on binary alphabet 𝔹 with ν₀^d(ε) = 1 and ν₀^d(x) = 2^{−l(x)−1} for l(x) > 0, one obtains P(ε) = 1/2 and P(𝔹^∞) = 1/2; identifying 𝔹^∞ with [0,1] via binary expansions, ν^d(S) equals λ(S)/2 (λ the Lebesgue measure) everywhere except ν^d([0,1]) = 1.

• Example 2 (the "perilous" environment): with action set {1,2}, empty observation, reward r_t = a_t, and termination with chance 1/2 when action 2 is chosen, and γ_t = 2^{−t}, the policy π₂ choosing action 2 has value 2 · (1/4) · 1/(1 − 1/4) = 2/3, while π₁ choosing action 1 has value 1 · (1/2) · 1/(1 − 1/2) = 1. Because the reward set does not contain 0 here, the Choquet integral ∫(Σ_t γ_t r_t) d(ν^p)^{π₂} exceeds V^{π₂}_{ν^p}.

• Lower semicomputability does not directly improve the existing limit-computability result. The paper notes that [LH18] uses only the weaker notion of limit computability for V^{π}{ν} to obtain limit computable ε-approximations to AIXI. It does observe that l.s.c. of V^{π}{ν,u_r}, when it holds, can be used to show convergence of AIXI_tl [HQC24, Thm.13.2.4] depending on the strength of the proof system [Lei16, Sec.5.2.3].

• Bayesian updating can break lower semicomputability. The paper notes this often happens for ν^π, including for (ξ^AI)^π when π is computable; nevertheless any policy maximizing V^{π}{ν,u̲} remains optimal at all times except with ν^π probability 0, and it suffices after observing æ{≤t} to maximize a renormalized value function 𝖢∫{æ{≤t}ℋ^∞} u dν^π := 𝖢∫ u I_{æ_{≤t}ℋ^∞} dν^π.

Methodology in Plain English

The authors work in the history-based setting where an agent exchanges actions and percepts with an environment, and the agent's belief is a Bayesian mixture (ξ^AI) over lower semicomputable chronological semimeasures. The problem is that these semimeasures are "defective": the probability of a prefix can be strictly greater than the sum over its one-symbol extensions, and the difference is the semimeasure loss. Ordinary probability theory does not apply directly, so the authors first repair it. They treat a pre-semimeasure as data given on cylinder sets, then use Carathéodory's extension theorem to build a genuine probability measure P on the larger space of finite and infinite sequences, from which the semimeasure is recovered by summing over finite strings plus the measure of the remaining infinite sequences. That lets them define expectations of arbitrary utility functions as ordinary Lebesgue integrals, and to compare those to the Choquet integral, which simply integrates the "level sets" ν(f ≥ b) over b. They then invoke known results from imprecise probability (the Choquet integral equals the minimum over the credal set Core(ν) for convex semimeasures) to identify the Choquet integral with a pessimistic, max-min evaluation, and they build the general AIXI agent around a continuous utility function. Finally, they analyze computability by approximating utilities from below with simple functions on cylinder sets and applying the monotone convergence theorem, obtaining lower semicomputability of the Choquet value functions and of the optimal value. No experiments, datasets, or benchmarks are reported; the arguments are mathematical proofs and worked examples.

Why This Matters

Impact on research. The paper claims to be the first to rigorously formulate a general class of utility functions for AIXI and to show how to define optimal policies in terms of the mathematical expectation of utility in the history-based RL framework. It subsumes earlier alternate-utility proposals such as Orseau's knowledge-seeking agents, and it links universal AI to the literature on semimeasures on Cantor space—which the authors say previously existed only as conjectures and suggestions in [HQC24, Sec.2.8.2] rather than a formal theory. By showing that the standard recursive value function is a special case of a Choquet integral, and that the Choquet form can have better hypercomputability properties, it connects universal AI to the theory of non-additive set functions [Cho54, GS94, GS95].

Motivation for the work, as stated by the authors:

• AIXI's drive to maximize expected returns would arguably lead it to instrumentally seek power even at the expense of its creators, whatever rewards they choose to administer [CHO22], so a more general class of agents whose terminal goals are parameterized is desirable [Mil23].
• The reward-sum target was motivated by reinforcement learning, whereas the primary pre-training method for frontier AI systems is now next-token prediction [HDN+24], though RL still plays an important role [BBE25].
• For AI alignment, a modular and user-specifiable utility function may be preferable; the authors also note this may be preferable for modeling human cognition.

Real-world applications (as directions of relevance, not demonstrated results — the paper reports no empirical evaluation, datasets, or benchmarks):

• AI alignment and goal specification: providing a formal way to parameterize terminal goals rather than fixing reward maximization, which is the paper's stated alignment motivation.
• Robust reinforcement learning under model misspecification: the paper cites recent work adapting imprecise probability for "robust" RL [AK25]; credal-set semantics are designed for cases where the hypothesis class may not contain the truth [Wal91].
• Decision theory with non-Bayesian beliefs: the Choquet/max-min construction offers a concrete decision rule for agents whose beliefs are not a single probability distribution.
• Analysis of "death" in artificial agents: building directly on work that identifies semimeasure loss with a chance of transitioning to a zero-reward absorbing state and studies resulting suicidal behavior of agents with negative reward sets [MEH16].

Industry relevance: Indirect. The paper is foundational theory rather than an engineering contribution, but its subject—how to specify what a general-purpose learning agent should optimize, and what its behavior implies—bears on the design of reward-agnostic objectives and on alignment concerns around power-seeking, which the authors raise explicitly. The authors' acknowledgments state that the work was supported in part by a grant from the Long-Term Future Fund (EA Funds - Cole Wyeth - 9/26/2023).

Future Directions

• Higher hypercomputability levels. The authors state they intend to investigate an even larger class of utility functions with hypercomputability levels higher in the arithmetic hierarchy.
• A philosophically justified normalization. The paper notes that its imprecise-probability view does not inherently justify pessimism in the face of ignorance (as the Choquet integral does), and suggests searching for a normalization following Solomonoff instead.
• Resolving the interpretation of semimeasure loss. The authors say they are not aware of strong arguments that semimeasure loss tends to coincide with a chance of death, leaving the choice between the death interpretation and credal-set semantics unresolved.
• Extending the computability analysis. The paper describes its own analysis as exploratory and "not very deep," leaving open how lower semicomputability interacts with Bayesian updating and with convergence results such as AIXI_tl.

Target Audience

Researchers in general reinforcement learning and universal artificial intelligence, decision theorists working on non-Bayesian or imprecise-probability decision rules, and alignment-oriented theorists interested in parameterized terminal goals. Readers need comfort with measure theory, Cantor space topology, and computability notions such as lower semicomputability; the paper is not accessible without that mathematical background.

Authors’ abstract

We generalize the AIXI reinforcement learning agent to admit a wider class of utility functions. Assigning a utility to each possible interaction history forces us to confront the ambiguity that some hypotheses in the agent's belief distribution only predict a finite prefix of the history, which is sometimes interpreted as implying a chance of death equal to a quantity called the semimeasure loss. This death interpretation suggests one way to assign utilities to such history prefixes. We argue that it is as natural to view the belief distributions as imprecise probability distributions, with the semimeasure loss as total ignorance. This motivates us to consider the consequences of computing expected utilities with Choquet integrals from imprecise probability theory, including an investigation of their computability level. We recover the standard recursive value function as a special case. However, our most general expected utilities under the death interpretation cannot be characterized as such Choquet integrals.