---
cluster: "D"
day: "D.3"
title: "AIXI"
contributors:
  - David Quarel (ARENA)
summary: Exploring the Bayesian optimal policy for history based reinforcement learning.
---

$\gdef\cA{\mathcal{A}}\gdef\cO{\mathcal{O}}\gdef\cR{\mathcal{R}}\gdef\cE{\mathcal{E}}\gdef\cH{\mathcal{H}}\gdef\cM{\mathcal{M}}\gdef\Ex{\mathbb{E}}\gdef\Prob{\mathbb{P}}\gdef\exmax{\mathop{\overset{\max}{\sum}}\limits}\gdef\TV{\mathrm{TV}}\gdef\aes{\text{\ae}}\gdef\argmax{\operatorname*{arg\,max}}$

## Prerequisites

- [Solomonoff Induction](/agency/solomonoff-induction) — **start there first.** The Bayesian mixture, posterior updates, and dominance carry over directly; AIXI reuses them in the action setting.
- Comfort with discrete probability (conditional distributions, chain rule, expectations).
- Familiarity with sequential decision-making / reinforcement learning (agents, rewards, discounting, value functions) is useful but not assumed.

<LearningOutcomes>

- Formalize the agent-environment interaction, value functions, and the Bayes-optimal policy that defines AIXI.
- Derive the explicit expectimax form of AIXI.
- Prove on-policy value convergence and that AIXI cannot be fooled in deterministic environments.
- Prove the self-optimizing property via likelihood-ratio martingales and change of measure.

</LearningOutcomes>

Much of this material is drawn from ([Hutter et al. 2024](#bib-hutter-24uaibook2)). The book provides fuller explanations, additional context, and proofs omitted here.

**Difficulty ratings.** Each subproblem is tagged with a rating in square brackets using Knuth's scale ([Knuth 1973](#bib-knuth-73a)): roughly, **[00]** trivial, **[10]** 15-minute pencil-and-paper, **[20]** 1–2 hours, **[30]** several hours to a day, **[40]** a significant research result. Intermediate values are possible. See [Appendix B](#b-knuths-difficulty-scale) for the full scale.

Problems marked **($\ast$)** are less interesting/insightful, and while the result may be used later, I would recommend skipping them on a first pass.

## Overview

AIXI is the *action* half of **Universal AI**: it lifts the Bayesian mixture from [Solomonoff induction](/agency/solomonoff-induction) — learning to predict — to learning to act. Now the agent takes actions that shape what it observes, and AIXI is the **Bayes-optimal policy** over a universal mixture $\xi$ of environments. It learns to act as well as if it knew the true environment $\mu$. Under the universal choice — $\cM$ = all lower-semicomputable environments, prior $w_{\nu} = 2^{-K(\nu)}$ — the assumption "$\mu \in \cM$" again becomes "the universe is computable."

## Goal and Roadmap

This exercise sheet builds towards three main results:

- **On-policy value convergence** ([Section 7](#7-on-policy-value-convergence-of-bayes)): the Bayesian mixture $\xi$ learns to predict the value of any fixed policy as well as the true environment $\mu$.
- **AIXI can't be fooled** ([Section 8](#8-aixi-cannot-be-fooled-in-deterministic-environments)): in deterministic environments, the Bayes-optimal agent is guaranteed non-zero value whenever optimal value is non-zero.
- **Self-optimizing property** ([Section 11](#11-proving-the-self-optimizing-property), advanced stretch goal): the Bayes-optimal policy $\pi_{\xi}^{*}$ learns to *act* as well as if it knew $\mu$, provided that any learnable policy can achieve this. This is the central theoretical justification for the AIXI agent.

A good target is to complete [Sections 7](#7-on-policy-value-convergence-of-bayes) and [8](#8-aixi-cannot-be-fooled-in-deterministic-environments). The self-optimizing property ([Sections 9–11](#9-likelihood-ratios-are-martingales)) requires substantial additional machinery (supermartingales, change of measure) and is an advanced stretch goal.

**Critical path.** The three results share a common foundation ([Sections 0–4](#0-properties-of-measures)) and then diverge:

<Figure src="/uploads/aixi/tikz-4dc0e19d14b9.svg" alt="diagram" />

**In summary:**

- [Sections 0–4](#0-properties-of-measures) establish the Bayesian RL framework: measure algebra, mixture properties, existence of optimal policies, dominance, and linearity.
- [Section 5](#5-the-expectimax-form-of-aixi) derives the explicit expectimax form of AIXI.
- [Sections 6–7](#6-bounding-expectation-differences-by-total-variation) prove *on-policy value convergence*: $V_{\xi}^{\pi}$ and $V_{\mu}^{\pi}$ become indistinguishable for any fixed $\pi$.
- [Section 8](#8-aixi-cannot-be-fooled-in-deterministic-environments) shows *AIXI can't be fooled*: the Bayes-optimal agent achieves non-zero value whenever optimal value is non-zero (in deterministic environments).
- [Sections 9–11](#9-likelihood-ratios-are-martingales) (advanced stretch goal) prove the *self-optimizing property*: if any policy can learn to act optimally, $\pi_{\xi}^{*}$ inherits this.

## Setup

An **agent** interacts with an **environment** in discrete time steps $t = 1, 2, \ldots$.

<Definition id="def-spaces">

**Definition 0.1 (Spaces and notation).** - $\cA$: finite set of **actions**
- $\cO$: finite set of **observations**
- $\cR \subset [0,1]$: finite set of **rewards**
- $\cE := \cO \times \cR$: set of **percepts**; $e_{t} = (o_{t}, r_{t}) \equiv o_{t}r_{t}$
- $\cH^{t} := (\cA \times \cE)^{t}$: set of all histories of length $t$
- $\cH^{*} := \cup_{t=0}^{\infty} \cH^{t}$: set of all finite **histories**
- $\cH \equiv \cH^{*}$: set of all finite histories
- $\cH^{\infty} := (\cA \times \cE)^{\infty}$: set of all infinite histories
- $\Delta S$: set of all probability distributions over set $S$
- $\llbracket \cdot \rrbracket$: **Iverson bracket**: $\llbracket P \rrbracket = 1$ if $P$ is true, $0$ if false
- $t$: current time step; $m$: finite horizon; $1 \leq t \leq m$
- $i, j, k$: arbitrary integer indices
- $xy$: concatenation
- $\epsilon$: the empty string/history
- $\aes_{i:j}:= a_{i} e_{i}\, a_{i+1}e_{i+1}\,\cdots\, a_{j} e_{j}$: history segment from time $i$ to $j$
- $\aes_{<t}:= a_{1} e_{1}\, a_{2} e_{2} \,\cdots\, a_{t-1}e_{t-1}$: history up to (but not including) time $t$

</Definition>

<Definition id="def-policy">

**Definition 0.2 (Policy $\pi$).** A **policy** $\pi : \cH \to \Delta \cA$ maps each history to a probability distribution over actions. Given history $\aes_{<t}$:

- $\pi(\cdot \mid \aes_{<t})$ is a distribution over $\cA$,
- $\pi(a_{t} \mid \aes_{<t}) \in [0,1]$ is the probability of choosing action $a_{t}$,
- the agent samples $a_{t} \sim \pi(\cdot \mid \aes_{<t})$.

A policy is **deterministic** if $\pi(a \mid \aes_{<t}) \in \{0,1\}$ for all $a, \aes_{<t}$. We write $\pi(\aes_{i:j}) := \prod_{k=i}^{j} \pi(a_{k} \mid \aes_{<k})$.

</Definition>

<Definition id="def-environment">

**Definition 0.3 (Environment $\nu$).** An **environment** $\nu : \cH \times \cA \to \Delta \cE$ maps each history–action pair to a distribution over percepts. Given history $\aes_{<t}$ and action $a_{t}$:

- $\nu(\cdot \mid \aes_{<t}a_{t})$ is a distribution over $\cE$,
- $\nu(e_{t} \mid \aes_{<t}a_{t}) \in [0,1]$ is the probability of percept $e_{t}$,
- the environment samples $e_{t} \sim \nu(\cdot \mid \aes_{<t}a_{t})$.

We write $\nu(\aes_{i:j}) := \prod_{k=i}^{j} \nu(e_{k} \mid \aes_{<k}a_{k})$. This satisfies the chain rule: $\nu(\aes_{i:j}) = \nu(\aes_{i:j-1}) \cdot \nu(e_{j} \mid \aes_{i:j-1}a_{j})$ or in the form we will usually use, $\nu(\aes_{1:t}) = \nu(\aes_{<t}) \cdot \nu(e_{t} \mid \aes_{<t}a_{t})$. An environment is **deterministic** if $\nu(e_{t} \mid \aes_{<t}a_{t}) \in \{0,1\}$ for all $e_{t}, \aes_{<t}, a_{t}$ (each percept is produced with certainty). We denote the true (unknown) environment by $\mu$.

</Definition>

<Definition id="def-interaction">

**Definition 0.4 (Interaction measure $\nu^{\pi}$).** When policy $\pi$ interacts with environment $\nu$, the joint probability of a history segment $\aes_{i:j}$ given past $\aes_{<i}$ is

$$
\nu^{\pi}(\aes_{i:j}\mid \aes_{<i}) ~:=~ \prod_{k=i}^{j} \pi(a_{k} \mid \aes_{<k})\, \nu(e_{k} \mid \aes_{<k}a_{k}).
$$

</Definition>

## 0. Properties of Measures

<Exercise id="prob-factorization">
**Exercise 0.1 (Factorization) [05].** Show that $\nu^{\pi}(\aes_{1:t}) = \pi(\aes_{1:t}) \cdot \nu(\aes_{1:t})$.
</Exercise>


<Exercise id="prob-chain-rule">
**Exercise 0.2 (Chain rule) [05].** Show that $\nu(\aes_{1:t}) = \nu(\aes_{<t}) \cdot \nu(e_{t} \mid \aes_{<t}a_{t})$.
</Exercise>


<Exercise id="prob-marginal-percepts">
**Exercise 0.3 (∗) (Marginalizing percepts) [03].** Show that $\sum_{e_t}\nu^{\pi}(a_{t} e_{t} \mid \aes_{<t}) = \pi(a_{t} \mid \aes_{<t})$.
</Exercise>


<Exercise id="prob-det-interaction">
**Exercise 0.4 (∗) (Deterministic interaction measure) [05].** Let $\pi$ be a deterministic policy, i.e. at each history $\aes_{<k}$ there is a unique action $a^{*}_{k}$ with $\pi(a^{*}_{k} \mid \aes_{<k}) = 1$. Show that, provided $\aes_{i:j}$ is consistent with $\pi$ (i.e. $a_{k} = a^{*}_{k}$ for every $k \in \{i, \ldots, j\}$):

$$
\nu^{\pi}(\aes_{i:j}\mid \aes_{<i}) ~=~ \nu(\aes_{i:j}\mid \aes_{<i}),
$$

i.e. on $\pi$-consistent futures the interaction measure reduces to the environment measure: every policy factor is $1$.
</Exercise>


<Exercise id="prob-chain-rule-nupi">
**Exercise 0.5 [05].** (General chain rule for $\nu^{\pi}$) Show that for any $p \leq q \leq r$:

$$
\nu^{\pi}(\aes_{p:r}\mid \aes_{<p}) ~=~ \nu^{\pi}(\aes_{p:q}\mid \aes_{<p}) \cdot \nu^{\pi}(\aes_{q+1:r}\mid \aes_{<p}\, \aes_{p:q}).
$$
</Exercise>


## The Bayesian Mixture and Value Function

<Definition id="def-mixture">

**Definition 0.1 (Model class, prior, and Bayesian mixture $\xi$).** Let $\cM = \{\nu_{1}, \nu_{2}, \ldots\}$ be a countable class of environments with prior weights $w_{\nu} > 0$ satisfying $\sum_{\nu \in \cM}w_{\nu} \leq 1$. We assume $\mu \in \cM$.

The **Bayesian mixture** $\xi$ is defined as

$$
\xi(\aes_{1:t}) := \sum_{\nu \in \cM}w_{\nu}\, \nu(\aes_{1:t}) \quad \text{ and }\quad \xi(e_{t} \mid \aes_{<t}a_{t}) := \xi(\aes_{1:t}) / \xi(\aes_{<t}).
$$

One can show that the one-step predictive distribution can be written as

$$
\xi(e_{t} \mid \aes_{<t}a_{t}) ~=~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, \nu(e_{t} \mid \aes_{<t}a_{t}),
$$

where the **posterior weight** is

$$
w(\nu \mid \aes_{<t}) ~:=~ w_{\nu} \,\frac{\nu(\aes_{<t})}{\xi(\aes_{<t})}, \qquad w(\nu \mid \epsilon) := w_{\nu}.
$$

See [Appendix A](#a-worked-example-bayesian-mixture-and-value-function) for a worked example.

</Definition>

<Definition id="def-expectation">

**Definition 0.2 (Expectation $\Ex_{\nu}^{\pi}$).** For a function $f : \cH \to \mathbb{R}$ of a finite future segment $\aes'_{t:m}$:

$$
\Ex_{\nu}^{\pi}[f \mid \aes_{<t}] ~:=~ \underset{\aes_{t:m} \sim \nu^\pi(\cdot \mid \aes_{<t})}{\Ex}[f] ~=~ \sum_{\aes'_{t:m}}\nu^{\pi}(\aes'_{t:m}\mid \aes_{<t})\, f(\aes'_{t:m}).
$$

For functions $f$ of the infinite future (like the value function), with a sequence $f_{1}, f_{2}, \ldots \to f$, where $f_{m}$ depends only on $\aes'_{t:m}$, we define $\Ex_{\nu}^{\pi}[f \mid \aes_{<t}] := \lim_{m \to \infty}\Ex_{\nu}^{\pi}[f_{m} \mid \aes_{<t}]$.

</Definition>

<Definition id="def-return">

**Definition 0.3 (Discounted return $G_{t:m}$).** Fix a discount factor $\gamma \in (0,1)$, held constant throughout. The **discounted return** at time step $t$, up to horizon $m$, is

$$
G^{\gamma}_{t:m}~:=~ \sum_{k=t+1}^{m}\gamma^{k-(t+1)}\, r_{k} ~=~ r_{t+1}+ \gamma\, r_{t+2}+ \cdots + \gamma^{m-t}\, r_{m}.
$$

Since $\gamma$ is fixed we drop it and write $G_{t:m}\equiv G^{\gamma}_{t:m}$. It satisfies the recursion $G_{t:m}= r_{t+1}+ \gamma\, G_{t+1:m}$, with $G_{m-1:m}= r_{m}$ and $G_{n:m}= 0$ for $n \geq m$. The **infinite-horizon return** is the pointwise limit

$$
G_{\geq t}~\equiv~ G_{t:\infty}~:=~ \lim_{m \to \infty}G_{t:m}~=~ \sum_{k=t+1}^{\infty}\gamma^{k-(t+1)}\, r_{k},
$$

with the clean recursion $G_{\geq t}= r_{t+1}+ \gamma\, G_{\geq t+1}$ and no boundary cases.

</Definition>

<Definition id="def-value">

**Definition 0.4 (Value function[^1]).** The **value** of policy $\pi$ in environment $\nu$ with horizon $m \geq t$ given history $\aes_{<t}$ is

$$
\begin{aligned}&V_{\nu}^{\pi,m}(\aes_{<t}) ~:=~ (1-\gamma)\, \Ex_{\nu}^{\pi}\!\left[G_{t-1:m}\mid \aes_{<t}\right] \\ ~&=~ (1-\gamma) \sum_{\aes_{t:m}}\nu^{\pi}(\aes_{t:m}\mid \aes_{<t})\, G_{t-1:m}\\ ~&=~ (1-\gamma) \sum_{\aes_{t:m}}\nu^{\pi}(\aes_{t:m}\mid \aes_{<t}) \left[ \sum_{k=t}^{m}\gamma^{k-t}r_{k} \right].\end{aligned}
$$

The **infinite-horizon value** is the pointwise limit $V_{\nu}^{\pi,\infty}(\aes_{<t}) := \lim_{m \to \infty}V_{\nu}^{\pi,m}(\aes_{<t}) = (1-\gamma)\, \Ex_{\nu}^{\pi}[G_{\geq t-1}\mid \aes_{<t}]$. We write $V_{\nu}^{\pi} \equiv V_{\nu}^{\pi,\infty}$ for short.

The **optimal value** is $V_{\nu}^{*,m}(\aes_{<t}) := \sup_{\pi} V_{\nu}^{\pi,m}(\aes_{<t})$ for $m \in \mathbb{N}\cup \{\infty\}$, with $V_{\nu}^{*} \equiv V_{\nu}^{*,\infty}$. [^2] An **optimal policy** $\pi_{\nu}^{*}$ satisfies $V_{\nu}^{\pi_\nu^*}= V_{\nu}^{*}$. The **Bayes-optimal policy** is $\pi_{\xi}^{*} \in \argmax_{\pi} V_{\xi}^{\pi}$.

</Definition>

<Callout type="note">

**Remark (AIXI).** All results in this sheet hold for any countable $\cM$ and prior weights $w_{\nu}$. **AIXI** is a special case of the Bayes-optimal policy $\pi_{\xi}^{*}$ for the particular choice $\cM :=$ the class of all lower-semicomputable chronological semimeasures, and prior $w_{\nu} := 2^{-K(\nu)}$, where $K(\nu)$ is the Kolmogorov complexity of $\nu$: the length of the shortest program that computes $\nu$. The resulting agent is written $\pi^{*}_{\xi_U}$, or simply AI$\xi$.

**Why this $\cM$?** By including every computable environment, the assumption $\mu \in \cM$ reduces to "the universe is computable": as weak an assumption as one can make.

**Why this prior?** The prior $2^{-K(\nu)}$ is *dominant*: for any other computable prior $w'_{\nu}$, there exists a constant $c > 0$ such that $2^{-K(\nu)}\geq c \cdot w'_{\nu}$ for all $\nu$.

**Caveat:** The constant $c$ depends on the choice of universal Turing machine $U$, and adversarial choices of $U$ can make AIXI behave arbitrarily badly ([Leike & Hutter 2015](#bib-leike-15badpriors)).

See ([Hutter et al. 2024](#bib-hutter-24uaibook2)): Chapter 2.7 for Kolmogorov complexity, Chapters 3.7–3.8 for the model class and universal prior, and Chapter 7.4 for AIXI itself.

</Callout>

## 1. Properties of the Bayesian Mixture

<Exercise id="prob-posterior-update">
**Exercise 1.1 (∗) (Posterior update) [10].** Show that the posterior updates multiplicatively:

$$
w(\nu \mid \aes_{1:t}) ~=~ w(\nu \mid \aes_{<t}) \frac{\nu(e_{t} \mid \aes_{<t}a_{t})}{\xi(e_{t} \mid \aes_{<t}a_{t})}.
$$

<Hint>

Use the definitions of $w(\nu \mid \aes_{1:t})$ and $w(\nu \mid \aes_{<t})$, and apply [Exercise 0.2](#prob-chain-rule).

</Hint>
</Exercise>


<Exercise id="prob-one-step">
**Exercise 1.2 [15].** (One-step predictive distribution of $\xi$) Starting from $\xi(\aes_{1:t}) = \sum_{\nu \in \cM}w_{\nu} \nu(\aes_{1:t})$, derive the one-step predictive form:

$$
\xi(e_{t} \mid \aes_{<t}a_{t}) ~=~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, \nu(e_{t} \mid \aes_{<t}a_{t}).
$$

<Hint>

Write $\xi(e_{t} \mid \aes_{<t}a_{t}) = \xi(\aes_{1:t}) / \xi(\aes_{<t})$, expand the numerator, and use [Exercise 0.2](#prob-chain-rule).

</Hint>
</Exercise>


<Exercise id="prob-bounded-value">
**Exercise 1.3 (Bounded value) [10].** Show that $V_{\nu}^{\pi,m}(\aes_{<t}) \in [0,1]$ for any $\nu, \pi, m \in \mathbb{N}\cup \{\infty\}, \aes_{<t}$.

<Hint>

Recall the formula for geometric series: $(1-\gamma)\sum_{k=0}^{n}\gamma^{k} = 1 - \gamma^{n+1}$.

</Hint>
</Exercise>


<Exercise id="prob-multi-step-xi">
**Exercise 1.4 (∗) [15].** (Multi-step posterior linearity of $\xi^{\pi}$) Extend [Exercise 1.2](#prob-one-step) to multi-step histories: show that for finite $m \geq t$,

$$
\xi^{\pi}(\aes_{t:m}\mid \aes_{<t}) ~=~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, \nu^{\pi}(\aes_{t:m}\mid \aes_{<t}).
$$

<Hint>

Apply the general chain rule ([Exercise 0.5](#prob-chain-rule-nupi)) to $\xi(\aes_{1:m}) = \sum_{\nu} w_{\nu} \nu(\aes_{1:m})$, then use factorization ([Exercise 0.1](#prob-factorization)).

</Hint>
</Exercise>


## 2. Existence of Optimal Policies

Recall that $V_{\nu}^{*}(\aes_{<t}) := \sup_{\pi} V_{\nu}^{\pi}(\aes_{<t})$ is defined as a supremum over all policies. In general, a supremum need not be achieved: for example, $\sup_{x \in (0,1)}x = 1$, but no $x \in (0,1)$ attains this value. This problem shows that in our setting, the supremum *is* attained, so an optimal policy $\pi_{\nu}^{*}$ with $V_{\nu}^{\pi_\nu^*}= V_{\nu}^{*}$ exists.

<Exercise id="prob-sup-eq-max">
**Exercise 2.1 [05].** Consider a single time step. Given history $\aes_{<t}$ and a function $Q : \cA \to \mathbb{R}$, show that $\sup_{\pi} \sum_{a \in \cA}\pi(a \mid \aes_{<t})\, Q(a) = \max_{a \in \cA}Q(a)$, and that the supremum is attained by the deterministic policy that places all probability on an action achieving the maximum.
</Exercise>


<Exercise id="prob-bellman-finite">
**Exercise 2.2 (Bellman equation) [15].** Show that for finite $m$ and $t \leq m$:

$$
V_{\nu}^{\pi,m}(\aes_{<t}) ~=~ \sum_{\aes'_t}\nu^{\pi}(\aes'_{t} \mid \aes_{<t}) \Big[(1-\gamma)\, r'_{t} ~+~ \gamma\, V_{\nu}^{\pi,m}(\aes_{<t}\, \aes'_{t})\Big],
$$

<Hint>

Use the general chain rule ([Exercise 0.5](#prob-chain-rule-nupi)) to peel off the *first* step,

$$
\nu^{\pi}(\aes_{t:m}\mid \aes_{<t}) ~=~ \nu^{\pi}(\aes_{t} \mid \aes_{<t}) \cdot \nu^{\pi}(\aes_{t+1:m}\mid \aes_{1:t}).
$$

Break up the sum $\sum_{\aes_{t:m}}= \sum_{\aes_t}\sum_{\aes_{t+1:m}}$, and factor out $r'_{t}$ using $\sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes) = 1$ for any history $\aes$.

</Hint>
</Exercise>


<Exercise id="prob-backward-induction">
**Exercise 2.3 (∗) (Backward induction) [20].** Using the Bellman equation from [Exercise 2.2](#prob-bellman-finite) and [Exercise 2.1](#prob-sup-eq-max), show by backward induction on $t = m, m-1, \ldots, 1$ that for each finite $m$, a deterministic optimal policy exists.
</Exercise>


<Exercise id="prob-bellman-opt">
**Exercise 2.4 (Bellman optimality equation) [10].** Using [Exercise 2.3](#prob-backward-induction), show that for finite $m$:

$$
V_{\nu}^{*,m}(\aes_{<t}) ~=~ \max_{a'_t}\sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}a'_{t}) \Big[(1-\gamma)\, r'_{t} ~+~ \gamma\, V_{\nu}^{*,m}(\aes_{<t}\, \aes'_{t})\Big].
$$

where $e_{t}' = o_{t}' r_{t}'$ and $\aes'_{t} = a'_{t} e'_{t}$.
</Exercise>


<Exercise id="prob-inf-horizon">
**Exercise 2.5 (∗) [15].** (Existence of $V_{\nu}^{*}$) Show that the pointwise limit $V_{\nu}^{*}(\aes_{<t}) := \lim_{m \to \infty}V_{\nu}^{*,m}(\aes_{<t})$ exists for all histories $\aes_{<t}$.

<Hint>

Show $V_{\nu}^{*,m+1}(\aes_{<t}) \geq V_{\nu}^{*,m}(\aes_{<t})$ by expanding $V_{\nu}^{*,m+1}$. Use this and [Exercise 1.3](#prob-bounded-value) and [Monotone Convergence Theorem](https://en.wikipedia.org/wiki/Monotone_convergence_theorem) to obtain the result.

</Hint>
</Exercise>


<Exercise id="prob-inf-bellman-opt">
**Exercise 2.6 (Infinite-horizon Bellman optimality equation) [10].** Show that the Bellman optimality equation ([Exercise 2.4](#prob-bellman-opt)) extends to $m = \infty$:

$$
V_{\nu}^{*}(\aes_{<t}) ~=~ \max_{a'_t}\sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}a'_{t}) \Big[(1-\gamma)\, r'_{t} ~+~ \gamma\, V_{\nu}^{*}(\aes_{<t}\, a'_{t}\, e'_{t})\Big].
$$
</Exercise>


<Exercise id="prob-inf-opt-policy">
**Exercise 2.7 (∗) (Optimal policy for infinite horizon) [25].** Show that a deterministic policy $\pi_{\nu}^{*}$ exists achieving $V_{\nu}^{\pi_\nu^*}(\aes_{<t}) = V_{\nu}^{*}(\aes_{<t})$ for all $\aes_{<t}$.

*Approach:*

**(a)** Define $\pi_{\nu}^{*}$ as the greedy policy (the $\argmax$ action from [Exercise 2.6](#prob-inf-bellman-opt)).

**(b)** Write two Bellman equations: one for $V_{\nu}^{*}$, one for $V_{\nu}^{\pi_\nu^*, m}$.

**(c)** Define $\Delta V_{\nu}^{m} := V_{\nu}^{*} - V_{\nu}^{\pi_\nu^*, m}$ and obtain a recursive equation for it.

**(d)** Iterate out to the finite horizon, noting $V_{\nu}^{\pi_\nu^*, m}(\aes_{1:m}) = 0$ (why?)

**(e)** Bound the tail, take $m \to \infty$.
</Exercise>


## 3. Dominance of the Bayesian Mixture

<Exercise id="prob-auto1">
**Exercise 3.1 [03].** Show that $\xi(\aes_{<t}) \geq w_{\nu} \cdot \nu(\aes_{<t})$ for every $\nu \in \cM$.
</Exercise>


<Exercise id="prob-auto2">
**Exercise 3.2 [10].** Conclude that $\xi^{\pi}(\aes_{1:m}) \geq w_{\nu} \cdot \nu^{\pi}(\aes_{1:m})$ for any $\nu \in \cM$ and any policy $\pi$.
</Exercise>


## 4. Properties of $V_{\xi}$

<Exercise id="prob-linearity-finite">
**Exercise 4.1 [15].** Show that for finite $m$:

$$
V_{\xi}^{\pi,m}(\aes_{<t}) ~=~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, V_{\nu}^{\pi,m}(\aes_{<t}).
$$

<Hint>

Use the multi-step posterior linearity of $\xi^{\pi}$ ([Exercise 1.4](#prob-multi-step-xi)).

</Hint>
</Exercise>


<div id="thm-dom-conv">
<Callout type="note">

**Fact 4.1 (Dominated convergence for sums).** If $a_{\nu,m}\to a_{\nu}$ as $m \to \infty$ for each $\nu$, and $|a_{\nu,m}| \leq b_{\nu}$ for all $m$ with $\sum_{\nu} b_{\nu} < \infty$, then $\sum_{\nu} a_{\nu,m}\to \sum_{\nu} a_{\nu}$. (For finite sums this is trivial.)

</Callout>
</div>

<Exercise id="prob-linearity-inf">
**Exercise 4.2 (∗) (Infinite-horizon linearity) [17].** Show that the result extends to $m = \infty$:

$$
V_{\xi}^{\pi}(\aes_{<t}) ~=~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, V_{\nu}^{\pi}(\aes_{<t}).
$$

<Hint>

Take $m \to \infty$ in the finite-horizon result. You will need [Fact 4.1](#thm-dom-conv) to exchange limit and sum for countably infinite $\cM$.

</Hint>
</Exercise>


[Exercise 4.1](#prob-linearity-finite) shows $V_{\xi}^{\pi}$ is linear in $\nu$. The optimal value $V_{\xi}^{*}$ is only convex: a single policy must perform well across all $\nu \in \cM$ simultaneously, rather than being tailored to each $\nu$ individually.

<Exercise id="prob-convex-opt">
**Exercise 4.3 (∗) [10].** (Convexity of $V_{\xi}^{*}$) Using [Exercise 4.1](#prob-linearity-finite), show that for finite $m$:

$$
V_{\xi}^{*,m}(\aes_{<t}) ~\leq~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, V_{\nu}^{*,m}(\aes_{<t}).
$$

<Hint>

Apply [Exercise 4.1](#prob-linearity-finite) with $\pi = \pi_{\xi}^{*}$, the Bayes-optimal policy for $\xi$.

</Hint>
</Exercise>


<Exercise id="prob-nonlinear-opt">
**Exercise 4.4 (∗) [15].** (Non-linearity of $V_{\xi}^{*}$) Show by example that the inequality in [Exercise 4.3](#prob-convex-opt) can be strict, i.e. $V_{\xi}^{*,m}$ is *not* linear in $\nu$.

<Hint>

Consider $\cM = \{\nu_{0}, \nu_{1}\}$: predicting a two-headed coin vs. a two-tailed coin.

</Hint>
</Exercise>


## 5. The Expectimax Form of AIXI

We have specified AIXI only implicitly, as the Bayes-optimal policy $\pi_{\xi}^{*}$ ([Definition 0.4](#def-value)). We now unroll this definition into the explicit **expectimax** expression: an alternating sequence of maximizations over actions and $\xi$-expectations over percepts.

<Exercise id="prob-expectimax-derivation">
**Exercise 5.1 (Expectimax form of AIXI) [20].** By iterating the finite-horizon Bellman optimality equation ([Exercise 2.4](#prob-bellman-opt)), show that

$$
\begin{aligned}V_{\xi}^{*,m}(\aes_{<t}) ~=~ (1-\gamma)&\max_{a_t}\sum_{e_t}\xi(e_{t} \mid \aes_{<t}a_{t}) \\&\max_{a_{t+1}}\sum_{e_{t+1}}\xi(e_{t+1}\mid \aes_{<t+1}a_{t+1}) \cdots \\ \cdots&\max_{a_m}\sum_{e_m}\xi(e_{m} \mid \aes_{<m}a_{m}) \,G_{t-1:m}\end{aligned}
$$

and hence, collecting the percept factors with the chain rule ([Exercise 0.2](#prob-chain-rule)) and taking $m \to \infty$ ([Exercises 2.5](#prob-inf-horizon) and [2.7](#prob-inf-opt-policy)), that AIXI selects the action

$$
\begin{aligned}a_{t}&~=~ \pi_{\xi}^{*}(\aes_{<t}) \\&~\in~ \argmax_{a_t}\lim_{m\to\infty}\sum_{e_t}\max_{a_{t+1}}\sum_{e_{t+1}}\cdots \max_{a_m}\sum_{e_m}\xi(e_{t:m}\mid \aes_{<t}\, a_{t:m}) \,G_{t-1:m}\end{aligned}
$$

<Hint>

Prove the first display by backward induction on $t$ from $m$ down to $1$, using the finite-horizon Bellman optimality equation ([Exercise 2.4](#prob-bellman-opt)) and the return recursion $G_{t-1:m}= r_{t} + \gamma\, G_{t:m}$ ([Definition 0.3](#def-return)). At each step the leftover reward term $(1-\gamma)\, r_{t}$ is constant in the deeper variables; carry it inward using $\sum_{e_k}\xi(e_{k} \mid \aes_{<k}a_{k}) = 1$ and $c + \max(\cdot) = \max(c + \cdot)$.

</Hint>
</Exercise>


## On-Policy Value Convergence

The following problems prove the first two main results: on-policy value convergence ([Section 7](#7-on-policy-value-convergence-of-bayes)), and that AIXI can't be fooled in deterministic environments ([Section 8](#8-aixi-cannot-be-fooled-in-deterministic-environments)). The path to the self-optimizing property (advanced stretch goal) resumes at [Section 9](#9-likelihood-ratios-are-martingales).

## 6. Bounding Expectation Differences by Total Variation

<Definition id="def-tv">

**Definition 6.1 (Total variation distance).** The **total variation distance** between probability measures $P$ and $Q$ on a countable set $\Omega$ is $\TV[\Omega](P, Q) := \sup_{S \subseteq \Omega}|P(S) - Q(S)|$, where $P(S) := \sum_{\omega \in S}P(\omega)$.

</Definition>

<Definition id="def-expectation-p">

**Definition 6.2 (Expectation under $P$).** For a probability measure $P$ on a countable set $\Omega$ and a function $f : \Omega \to \mathbb{R}$, the **expectation** of $f$ under $P$ is $\Ex_{P}[f] := \sum_{\omega \in \Omega}f(\omega)\, P(\omega)$.

</Definition>

The following technical lemma is needed for the on-policy value convergence proof.

<Exercise id="prob-auto3">
**Exercise 6.1 (∗) [15].** Let $f : \Omega \to [0, c]$. Show that $\big|\Ex_{P}[f] - \Ex_{Q}[f]\big| \leq c \cdot \TV[\Omega](P, Q)$.

<Hint>

Define $A^{+} = \{\omega \in \Omega : P(\omega) \geq Q(\omega)\}$ and decompose the expectation difference as a sum over $A^{+}$ and its complement $A^{-} = \Omega \setminus A^{+}$.

</Hint>
</Exercise>


## 7. On-Policy Value Convergence of Bayes

The following definitions are needed for the on-policy value convergence theorem.

<Definition id="def-events">

**Definition 7.1 (Probability of events).** A **finite-length event** is a set $A \subseteq (\cA \times \cE)^{t}$ of histories of fixed length $t$. Its probability under $\nu^{\pi}$ is

$$
\nu^{\pi}(A) ~:=~ \sum_{\aes_{1:t} \in A}\nu^{\pi}(\aes_{1:t}).
$$

An **event on infinite histories** is any set built from finite-length events by countable unions, intersections, and complements.[^3] Probabilities of such events are uniquely determined by two properties:

- **Normalization:** $\nu^{\pi}\!\big((\cA \times \cE)^{\infty}\big) = 1$.
- **Countable additivity:** if $A_{1}, A_{2}, \ldots$ are pairwise disjoint events, then $\nu^{\pi}\!\big(\bigcup_{n=1}^{\infty} A_{n}\big) = \sum_{n=1}^{\infty} \nu^{\pi}(A_{n})$.

From these, all standard rules of probability can be derived (e.g. $\nu^{\pi}(A \cup B) = \nu^{\pi}(A) + \nu^{\pi}(B) - \nu^{\pi}(A \cap B)$, etc.), though we will not prove them here. Two derived properties we use explicitly:

- **Complement:** $\nu^{\pi}(A^{c}) = 1 - \nu^{\pi}(A)$.
- **Monotone limits:** if $A_{1} \supseteq A_{2} \supseteq \cdots$, then $\nu^{\pi}\!\big(\bigcap_{n=1}^{\infty} A_{n}\big) = \lim_{n \to \infty}\nu^{\pi}(A_{n})$.

Further useful notions:

- **Conditional probability:** The probability of event $A$ given observed history $\aes_{<t}$ is

$$
\nu^{\pi}(A \mid \aes_{<t}) ~:=~ \frac{\nu^{\pi}(\{\aes_{<t}h : h \in A\})}{\nu^{\pi}(\aes_{<t})}.
$$

</Definition>

<Callout type="tip">

**Example 7.2 (A fair coin shows 1 infinitely often).** Let $\cA = \cO = \{0,1\}$, $\cR = \{0\}$, and let $\nu$ be a fair coin that ignores the action: $\nu(o_{t} = 1 \mid \aes_{<t}\, a_{t}) = \tfrac{1}{2}$ for all $\aes_{<t}, a_{t}$. Consider the event $F := \text{``}o_{t} = 1\text{ for infinitely many }t\text{''}$.

*Step 1: Build $F^{c}$ from finite-prefix events.* For each $t$, the set $\{o_{t} = 0\} := \{\aes_{1:t}: o_{t} = 0\}$ is a finite-length event. For each $N$ and $T \geq N$, the set $D_{N,T}:= \bigcap_{t=N}^{T}\{o_{t} = 0\}$ is also a finite-length event (determined by time $T$). Define $C_{N} := \bigcap_{t=N}^{\infty}\{o_{t} = 0\}$ ("all zeros from time $N$ onwards"): this is an infinite-history event, built as a countable intersection of finite-length events. Then $F^{c} = \bigcup_{N=1}^{\infty} C_{N}$ ("eventually all zeros").

*Step 2: Compute $\nu^{\pi}(C_{N}) = 0$.* Since $D_{N,T}\supseteq D_{N,T+1}\supseteq \cdots$ (adding more constraints), the monotone limit property (for decreasing sets) gives:

$$
\nu^{\pi}(C_{N}) ~=~ \lim_{T \to \infty}\nu^{\pi}(D_{N,T}) ~=~ \lim_{T \to \infty}\left(\tfrac{1}{2}\right)^{T - N + 1}~=~ 0.
$$

(The probability $\nu^{\pi}(D_{N,T}) = (1/2)^{T-N+1}$ is independent of $\pi$, since $\nu$ ignores actions.)

*Step 3:* By countable additivity: $\nu^{\pi}(F^{c}) \leq \sum_{N=1}^{\infty} \nu^{\pi}(C_{N}) = 0$, so $\nu^{\pi}(F) = 1$. A fair coin shows 1 infinitely often, almost surely.

As such, $F^{c}$ (the set of all infinite histories containing only finitely many 1s) is a $\nu^{\pi}$-measure-zero set. Such histories "exist" as infinite sequences, but occur with probability zero.

</Callout>

<Definition id="def-covering">

**Definition 7.3 (Covering[^4]).** We say $Q$ **covers** $P$ if $Q$ is positive everywhere $P$ is: $P(A) > 0 \implies Q(A) > 0$ for all events $A$. Equivalently: any event that $Q$ rules out, $P$ also rules out. By [Section 3](#3-dominance-of-the-bayesian-mixture), $\xi^{\pi}$ covers $\mu^{\pi}$.

</Definition>

<Definition id="def-as">

**Definition 7.4 (Convergence $\nu^{\pi}$-almost surely).** Let $f_{t} : \cH^{t-1}\to \mathbb{R}$ be a sequence of functions, where $f_{t}$ depends on the history $\aes_{<t}$ of length $t-1$. We write $f_{t}(\aes_{<t}) \to 0$ $\nu^{\pi}$**-almost surely** ($\nu^{\pi}$-a.s.) if

$$
\nu^{\pi}\!\Big(\Big\{\aes_{1:\infty}: f_{t}(\aes_{<t}) \not\to 0\Big\}\Big) = 0.
$$

This set is built from finite-prefix conditions: $\{f_{t} \not\to 0\} = \bigcup_{n=1}^{\infty} \bigcap_{N=1}^{\infty} \bigcup_{t=N}^{\infty} \big\{|f_{t}(\aes_{<t})| > \tfrac{1}{n}\big\}$, so its probability is well-defined ([Definition 7.1](#def-events)).

</Definition>

<Callout type="tip">

**Example 7.5 (Unpacking "$f_{t}\not\to 0$").** The set $\{f_{t} \not\to 0\}$ looks intimidating, but it reads naturally from the inside out:

- $\big\{|f_{t}(\aes_{<t})| > \tfrac{1}{n}\big\}$ is a finite-length event: "at time $t$, the function is at least $\tfrac{1}{n}$ away from zero."
- $\bigcup_{t=N}^{\infty} \big\{|f_{t}| > \tfrac{1}{n}\big\}$: "at *some* time $t \geq N$, $f_{t}$ is at least $\tfrac{1}{n}$ away from zero."
- $\bigcap_{N=1}^{\infty} \bigcup_{t=N}^{\infty} \big\{|f_{t}| > \tfrac{1}{n}\big\}$: "for *every* $N$, there is some $t \geq N$ where $f_{t}$ is at least $\tfrac{1}{n}$ from zero", i.e., $f_{t}$ exceeds $\tfrac{1}{n}$ *infinitely often*.
- $\bigcup_{n=1}^{\infty} \bigcap_{N=1}^{\infty} \bigcup_{t=N}^{\infty} \big\{|f_{t}| > \tfrac{1}{n}\big\}$: "for *some* $\tfrac{1}{n}> 0$, $f_{t}$ exceeds $\tfrac{1}{n}$ infinitely often."

This last condition is exactly $\{f_{t} \not\to 0\}$: convergence $f_{t} \to 0$ means that for *every* $\varepsilon > 0$, $|f_{t}| \leq \varepsilon$ for all sufficiently large $t$. Its negation is that *some* $\varepsilon > 0$ is exceeded infinitely often.

Each layer is a countable union or intersection of the previous, so the whole set is a well-defined event on infinite histories.

</Callout>

The Bayesian agent uses the mixture $\xi$ because the true environment $\mu$ is unknown. A natural question: does planning with $\xi$ eventually become as good as planning with $\mu$? The following theorem says *yes*: the value of any fixed policy $\pi$, as evaluated by $\xi$, converges to the value under the true environment $\mu$, along histories that $\mu^{\pi}$ actually generates.[^5] This tells us that the Bayesian mixture "learns" to predict the true environment's value, on policy.

<Theorem id="thm-on-policy">

**Theorem 7.6 (On-policy value convergence; ([Hutter et al. 2024](#bib-hutter-24uaibook2), Theorem 7.3.1)).** For any $\mu \in \cM$ and any policy $\pi$: $V_{\xi}^{\pi}(\aes_{<t}) - V_{\mu}^{\pi}(\aes_{<t}) \to 0$ as $t \to \infty$, $\mu^{\pi}$-almost surely. That is, the set of infinite histories along which the value difference does not vanish has $\mu^{\pi}$-probability zero:

$$
\mu^{\pi}\!\Big(\Big\{\aes_{1:\infty}: V_{\xi}^{\pi}(\aes_{<t}) - V_{\mu}^{\pi}(\aes_{<t}) \not\to 0\Big\}\Big) = 0.
$$

</Theorem>

The proof reduces to a finite-horizon TV bound ([Exercise 7.1](#prob-tv-finite)), a covering argument ([Exercise 7.2](#prob-covering-proof)), and the Blackwell–Dubins theorem ([Exercise 7.3](#prob-on-policy-proof)). The only ingredient we do not prove is Blackwell–Dubins itself, which we state as a given fact.

<Exercise id="prob-tv-finite">
**Exercise 7.1 (Finite-horizon TV bound on value difference) [10].** Using [Section 6](#6-bounding-expectation-differences-by-total-variation), show that for finite $m$:

$$
\big|V_{\xi}^{\pi,m}(\aes_{<t}) - V_{\mu}^{\pi,m}(\aes_{<t})\big| ~\leq~ \TV[\cH^{m-t+1}]\!\big(\xi^{\pi}(\cdot \mid \aes_{<t}),\; \mu^{\pi}(\cdot \mid \aes_{<t})\big),
$$

where $\cH^{m-t+1}:= (\cA \times \cE)^{m-t+1}$ is the set of all future history segments $\aes_{t:m}$.
</Exercise>


<Exercise id="prob-covering-proof">
**Exercise 7.2 (Covering) [05].** Show that $\xi^{\pi}$ covers $\mu^{\pi}$ ([Definition 7.3](#def-covering)).

<Hint>

Use [Section 3](#3-dominance-of-the-bayesian-mixture).

</Hint>
</Exercise>


To complete the proof, we need the TV distance on finite segments to vanish $\mu^{\pi}$-a.s. as $t \to \infty$. This follows from the following deep result, which we state without proof:

<div id="fact-bd">
<Callout type="note">

**Fact 7.7 (Blackwell–Dubins merging of opinions ([Blackwell & Dubins 1962](#bib-blackwell-62))).** If $Q$ covers $P$, then $\sup_{S} |P(S \mid \aes_{<t}) - Q(S \mid \aes_{<t})| \to 0$ $P$-almost surely, where the supremum ranges over all measurable events $S$ (including events on infinite histories).

</Callout>
</div>

The proof of Blackwell–Dubins requires the Radon–Nikodym derivative and Levy's martingale convergence theorem: tools from measure theory that are beyond the scope of this sheet. See ([Hutter et al. 2024](#bib-hutter-24uaibook2), Chapter 3.9) for discussion.

<Exercise id="prob-on-policy-proof">
**Exercise 7.3 (On-policy convergence) [15].** Using [Fact 7.7](#fact-bd), [Exercise 7.1](#prob-tv-finite) and [Exercise 7.2](#prob-covering-proof), prove [Theorem 7.6](#thm-on-policy).
</Exercise>


<Exercise id="prob-auto4">
**Exercise 7.4 (∗) [40].** Prove [Fact 7.7](#fact-bd).

<Hint>

See ([Blackwell & Dubins 1962](#bib-blackwell-62)). The proof uses the Radon–Nikodym derivative $dP/dQ$, Levy's martingale convergence theorem, and the Lebesgue decomposition. No elementary proof is known that avoids graduate-level measure theory.

</Hint>
</Exercise>

## 8. AIXI Cannot Be Fooled in Deterministic Environments

<Theorem id="thm-cant-be-fooled">

**Theorem 8.1 (AIXI cannot act poorly in good environments).** If $\mu \in \cM$ is deterministic and $V_{\mu}^{*}(\aes_{<t}) > \varepsilon > 0$ for all $t$ along the history generated by $\mu$ and $\pi_{\xi}^{*}$, then $V_{\xi}^{*}(\aes_{<t}) \geq w_{\mu}\, \varepsilon > 0$ for all $t$. ([Hutter et al. 2024](#bib-hutter-24uaibook2), Theorem 7.4.10)

</Theorem>

<Exercise id="prob-xi-lower-bound">
**Exercise 8.1 [10].** Show that $V_{\xi}^{*}(\aes_{<t}) \geq w(\mu \mid \aes_{<t}) \cdot V_{\mu}^{*}(\aes_{<t})$.

<Hint>

Use linearity of $V^{\pi}$ ([Exercise 4.2](#prob-linearity-inf)).

</Hint>
</Exercise>


<Exercise id="prob-auto5">
**Exercise 8.2 [15].** Show $w(\mu \mid \aes_{<t}) \geq w_{\mu}$ when $\mu$ is deterministic, and combine with [Exercise 8.1](#prob-xi-lower-bound) to prove [Theorem 8.1](#thm-cant-be-fooled).
</Exercise>


<Callout type="note">

**Remark.** With the Solomonoff prior, $w_{\mu} = 2^{-K(\mu)}$ may be astronomically small. The result guarantees non-zero value, not near-optimal value.

</Callout>

## [Sections 9–11](#9-likelihood-ratios-are-martingales): Self-Optimizing Policy (Finite Model Class)

We now prove: if *any* policy can learn to act optimally, $\pi_{\xi}^{*}$ also learns. We restrict to finite $\cM = \{\nu_{1}, \ldots, \nu_{N}\}$ where each $\nu_{i}$ is a proper probability measure.

## 9. Likelihood Ratios Are Martingales

The following definition and theorem state the main goal of [Sections 9–11](#9-likelihood-ratios-are-martingales).

<Definition id="def-selfopt">

**Definition 9.1 (Self-optimizing).** Fix a historic policy $\pi$. A policy $\tilde\pi$ is **self-optimizing** for $\cM$ with respect to $\pi$ if for every $\nu \in \cM$: $V_{\nu}^{*}(\aes_{<t}) - V_{\nu}^{\tilde\pi}(\aes_{<t}) \to 0$ as $t \to \infty$, $\nu^{\pi}$-almost surely.

The percepts $e_{1:\infty}$ are sampled from $\nu$; the historic actions $a_{<t}$ come from $\pi$, which may differ from $\tilde\pi$.

</Definition>

<Theorem id="thm-selfopt">

**Theorem 9.2 (Self-optimizing; ([Hutter et al. 2024](#bib-hutter-24uaibook2), Theorem 7.5.2)).** Let $\cM$ be finite and fix a historic policy $\pi$. If there exists a $\tilde\pi$ self-optimizing for $\cM$ with respect to $\pi$, then $\pi_{\xi}^{*}$ is also self-optimizing for $\cM$ with respect to $\pi$: for any $\mu \in \cM$, $V_{\mu}^{*}(\aes_{<t}) - V_{\mu}^{\pi_\xi^*}(\aes_{<t}) \to 0$ $\mu^{\pi}$-almost surely.

</Theorem>

<Definition id="def-supermartingale">

**Definition 9.3 (Supermartingale).** A sequence of functions $X_{t} : \cH^{t}\to \mathbb{R}_{\geq 0}$ (each depending on the history $\aes_{1:t}$) is a $\mu^{\pi}$-**supermartingale** if $\Ex_{\mu^\pi}[X_{t} \mid \aes_{<t}] \leq X_{t-1}$ for all $t$; that is,

$$
\sum_{\aes_t}\pi(a_{t} \mid \aes_{<t})\, \mu(e_{t} \mid \aes_{<t}a_{t})\, X_{t}(\aes_{1:t}) ~\leq~ X_{t-1}(\aes_{<t}).
$$

If equality holds, it is a $\mu^{\pi}$-**martingale**.

</Definition>

**Intuition.** A supermartingale is a quantity whose expected future value, given the present, is no larger than its current value: it cannot "drift upward on average." A martingale is the equality case: expected future value equals current value. The key example is the **likelihood ratio** $X_{\nu,t}(\aes_{1:t}) := \nu(\aes_{1:t})/\mu(\aes_{1:t})$: how much more (or less) likely the observed history is under $\nu$ than under the true environment $\mu$. Under $\mu$, this ratio is a martingale: the true environment does not, on average, favour any alternative $\nu$ over itself. Non-negativity plus the (super)martingale structure forces $X_{\nu,t}$ to converge (by Doob's theorem below), which is the engine behind the self-optimizing proof: it lets us separate environments that remain plausible ($X_{\nu,\infty}> 0$) from those that are eventually ruled out ($X_{\nu,\infty}= 0$), and handle each case differently in [Section 11](#11-proving-the-self-optimizing-property).

<div id="fact-doob">
<Callout type="note">

**Fact 9.4 (Doob's supermartingale convergence).** If $(X_{t})_{t \geq 0}$ is a non-negative $\mu^{\pi}$-supermartingale, then there exists a function $X_{\infty} : \cH^{\infty} \to \mathbb{R}_{\geq 0}$ of the infinite history such that $X_{t}(\aes_{1:t}) \to X_{\infty}(\aes_{1:\infty})$ as $t \to \infty$, with $X_{\infty}(\aes_{1:\infty}) < \infty$, for $\mu^{\pi}$-almost every infinite history $\aes_{1:\infty}$. That is:

$$
\mu^{\pi}\!\Big(\Big\{\aes_{1:\infty}\in (\cA \times \cE)^{\infty} : X_{t}(\aes_{1:t}) \not\to X_{\infty}(\aes_{1:\infty})\Big\}\Big) ~=~ 0.
$$

</Callout>
</div>

For each $\nu \in \cM$, define the likelihood ratio

$$
X_{\nu,t}: \cH^{t} \to \mathbb{R}_{\geq 0}, \qquad X_{\nu,t}(\aes_{1:t}) ~:=~ \frac{\nu(\aes_{1:t})}{\mu(\aes_{1:t})}, \qquad X_{\nu,0}:= 1.
$$

$X_{\nu,t}$ is a *function* of the history $\aes_{1:t}$, not a number: different histories give different values. Throughout this section and the next, any unqualified statement of the form "$X_{\nu,t}\geq c$" or "$X_{\nu,t}\to X_{\nu,\infty}$" is shorthand for "$X_{\nu,t}(\aes_{1:t}) \geq c$" or "$X_{\nu,t}(\aes_{1:t}) \to X_{\nu,\infty}(\aes_{1:\infty})$" holding $\mu^{\pi}$-almost surely, i.e. on every infinite history outside a set of $\mu^{\pi}$-measure zero. We will not track these null sets explicitly; their countable union over all claims is still a $\mu^{\pi}$-null set.

<Exercise id="prob-martingale">
**Exercise 9.1 [15].** Show that $X_{\nu,t}$ is a $\mu^{\pi}$-martingale: $\Ex_{\mu^\pi}[X_{\nu,t}\mid \aes_{<t}] = X_{\nu,t-1}$.

<Hint>

Write $X_{\nu,t}(\aes_{1:t}) = X_{\nu,t-1}(\aes_{<t}) \cdot \nu(e_{t} \mid \aes_{<t}a_{t})/\mu(e_{t} \mid \aes_{<t}a_{t})$. Sum over $a_{t}, e_{t}$; $\mu$ cancels, leaving $\sum_{e_t}\nu(e_{t} \mid \aes_{<t}a_{t}) = 1$.

</Hint>
</Exercise>


<Exercise id="prob-x-converges">
**Exercise 9.2 [05].** Apply [Fact 9.4](#fact-doob) to conclude $X_{\nu,t}\to X_{\nu,\infty}< \infty$ $\mu^{\pi}$-a.s.
</Exercise>


<Exercise id="prob-x-bounded-mu">
**Exercise 9.3 [10].** Define $X_{\xi,t}:= \xi(\aes_{1:t})/\mu(\aes_{1:t})$. Show $X_{\xi,t}= \sum_{\nu} w_{\nu} X_{\nu,t}$ and $X_{\xi,t}\geq w_{\mu} > 0$.
</Exercise>


## 10. Change of Measure

<Exercise id="prob-cm-finite">
**Exercise 10.1 [15].** Let $A$ be a set of finite histories of length $m$. Show:

$$
\nu^{\pi}[\aes_{1:m}\in A] ~=~ \Ex_{\mu^\pi}\big[X_{\nu,m}\cdot \llbracket \aes_{1:m}\in A \rrbracket\big].
$$

<Hint>

Use [Exercise 0.1](#prob-factorization) to show $\nu^{\pi}/\mu^{\pi} = \nu/\mu = X_{\nu,m}$.

</Hint>
</Exercise>


<Exercise id="prob-cm-extension">
**Exercise 10.2.** (Given.) The identity extends to infinite histories: for any event $A \subseteq (\cA \times \cE)^{\infty}$,

$$
\nu^{\pi}[A] ~=~ \Ex_{\mu^\pi}\big[X_{\nu,\infty}\cdot \llbracket \aes_{1:\infty}\in A \rrbracket\big].
$$

This says that $X_{\nu,\infty}$ plays the role of the Radon–Nikodym derivative $\mathrm{d}\nu^{\pi}/\mathrm{d}\mu^{\pi}$ on the space of infinite histories. The proof rests on two ingredients beyond the scope of this worksheet:

- **$L^{1}$ martingale convergence** (closed martingale / Levy's upward theorem): since $\Ex_{\mu^\pi}[X_{\nu,t}] = 1$ for every $t$, the non-negative $\mu^{\pi}$-martingale $(X_{\nu,t})$ is uniformly integrable, so $X_{\nu,t}\to X_{\nu,\infty}$ in $L^{1}(\mu^{\pi})$, not merely $\mu^{\pi}$-a.s. This lets us pass the $t\to\infty$ limit through the expectation.
- **Uniqueness of measure extension** (Caratheodory / $\pi$–$\lambda$ theorem): both sides of the identity are finite measures on $(\cA\times\cE)^{\infty}$; the finite-history identity ([Exercise 10.1](#prob-cm-finite)) shows they agree on all cylinder events $A = A_{0} \times (\cA\times\cE)^{\infty}$, and cylinders generate the full event $\sigma$-algebra, so agreement extends uniquely to every event.

We omit the proof and use this identity freely below.
</Exercise>

<Exercise id="prob-markov-cm">
**Exercise 10.3 (Markov inequality for change of measure) [15].** Let $E$ be an event of infinite histories. For any $\varepsilon > 0$, show that

$$
\mu^{\pi}\big[E \cap \{X_{\nu,\infty}\geq \varepsilon\}\big] ~\leq~ \frac{\nu^{\pi}[E]}{\varepsilon}.
$$

<Hint>

On $E \cap \{X_{\nu,\infty}\geq \varepsilon\}$, $X_{\nu,\infty}\geq \varepsilon$ pointwise. Take $\mu^{\pi}$-expectations and apply [Exercise 10.2](#prob-cm-extension).

</Hint>
</Exercise>


## 11. Proving the Self-Optimizing Property

Fix a policy $\tilde\pi$ that is self-optimizing for $\cM$ with respect to $\pi$ ([Definition 9.1](#def-selfopt)): its existence is the hypothesis of [Theorem 9.2](#thm-selfopt). For each $\nu \in \cM$, define the **suboptimality gap**

$$
\delta_{\nu,t}: \cH^{t-1}\to [0,1], \qquad \delta_{\nu,t}(\aes_{<t}) ~:=~ V_{\nu}^{*}(\aes_{<t}) - V_{\nu}^{\tilde\pi}(\aes_{<t}).
$$

As with $X_{\nu,t}$, we write $\delta_{\nu,t}$ without its argument when convenient: "$\delta_{\nu,t}\to 0$ $\mu^{\pi}$-a.s." means $\delta_{\nu,t}(\aes_{<t}) \to 0$ on every infinite history outside a $\mu^{\pi}$-null set, and similarly for "$\delta_{\nu,t}\leq 1$" etc.

<Exercise id="prob-chain-ineq">
**Exercise 11.1 (Chain of inequalities) [20].** Show:

$$
0 ~\leq~ w(\mu \mid \aes_{<t}) \big[V_{\mu}^{*} - V_{\mu}^{\pi_\xi^*}\big] ~\leq~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, \delta_{\nu,t}.
$$

<Hint>

Use $V_{\xi}^{\pi_\xi^*}\geq V_{\xi}^{\tilde\pi}$ and [Exercise 4.2](#prob-linearity-inf).

</Hint>
</Exercise>


<Exercise id="prob-vanishing-posterior">
**Exercise 11.2 (Vanishing posterior) [10].** Show: if $X_{\nu,\infty}= 0$ then $w(\nu \mid \aes_{<t}) \to 0$ $\mu^{\pi}$-a.s.

<Hint>

Show $w(\nu \mid \aes_{<t}) = w_{\nu} X_{\nu,t-1}/X_{\xi,t-1}$ and use [Exercise 9.3](#prob-x-bounded-mu).

</Hint>
</Exercise>


<Exercise id="prob-delta-transfer">
**Exercise 11.3 (Transferring convergence) [20].** Let $F := \{\aes_{1:\infty}: \delta_{\nu,t}(\aes_{<t}) \not\to 0\}$, the set of infinite histories on which the suboptimality gap fails to vanish. Show that $\mu^{\pi}\big[F \cap \{X_{\nu,\infty}> 0\}\big] = 0$.

<Hint>

Self-optimizing ([Definition 9.1](#def-selfopt)) gives $\nu^{\pi}[F] = 0$. Apply [Exercise 10.3](#prob-markov-cm) with $E = F$ and $\varepsilon = 1/n$ to conclude $\mu^{\pi}[F \cap \{X_{\nu,\infty}\geq 1/n\}] = 0$ for each $n \geq 1$. Then note $\{X_{\nu,\infty}> 0\} = \bigcup_{n \geq 1}\{X_{\nu,\infty}\geq 1/n\}$ and take the countable union ([Definition 7.1](#def-events)).

</Hint>
</Exercise>


<Exercise id="prob-single-term">
**Exercise 11.4 (Single-term convergence) [10].** Combine [Exercise 11.2](#prob-vanishing-posterior) and [Exercise 11.3](#prob-delta-transfer) to show $w(\nu \mid \aes_{<t}) \delta_{\nu,t}\to 0$ $\mu^{\pi}$-a.s.
</Exercise>


<Exercise id="prob-auto6">
**Exercise 11.5 (Self-Optimizing Theorem) [15].** Combine [Exercise 11.4](#prob-single-term), [Exercise 11.1](#prob-chain-ineq), [Exercise 9.3](#prob-x-bounded-mu) to finally prove the main result of [Theorem 9.2](#thm-selfopt).

<Hint>

$w(\mu \mid \aes_{<t}) = w_{\mu}/X_{\xi,t-1}$.

</Hint>
</Exercise>


<Callout type="note">

**Remark.** We do not need to know which policy $\tilde\pi$ is self-optimizing, or whether it is computable. Mere existence suffices. For countable $\cM$, this final step is harder: a countable sum of $\mu^{\pi}$-a.s.-convergent sequences need not converge $\mu^{\pi}$-a.s. The general proof uses a "convergence of mixture tails" argument ([Hutter 2005](#bib-hutter-04uaibook), Lem. 5.28).

</Callout>

## Further reading

- Hutter, [*An Introduction to Universal Artificial Intelligence*](https://www.hutter1.net/publ/uaibook2.pdf) (2024): Chapter 2.7 (Kolmogorov complexity), Chapters 3.7–3.8 (the model class and universal prior), and Chapter 7.4 (AIXI).
- Hutter, [*Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability*](http://www.hutter1.net/ai/uaibook.htm) (Springer, 2005) — the original book-length treatment; Lem. 5.28 handles the countable-$\cM$ self-optimizing case.
- Blackwell & Dubins, [*Merging of Opinions with Increasing Information*](https://doi.org/10.1214/aoms/1177704456) (Ann. Math. Statist., 1962) — the merging-of-opinions theorem behind on-policy value convergence.
- Leike & Hutter, [*Bad Universal Priors and Notions of Optimality*](https://arxiv.org/abs/1510.04931) (COLT 2015) — adversarial choices of the universal Turing machine can make AIXI behave arbitrarily badly.

## A. Worked Example: Bayesian Mixture and Value Function

<Callout type="note">

**Setup.**

- **Actions:** $\cA = \{H, T\}$ (predict the next coin flip)
- **Observations:** $\cO = \{H, T\}$ (actual coin flip)
- **Rewards:** $\cR = \{0, 1\}$, with $r_{t} = \llbracket a_{t} = o_{t} \rrbracket$
- **Model class:** $\cM = \{\nu_{HH}, \nu_{HT}\}$ (two-headed coin, fair coin)
- **Prior:** $w_{\nu_{HH}}= w_{\nu_{HT}}= \tfrac{1}{2}$

</Callout>

**Before any interaction** ($t=1$, $\aes_{<1}= \epsilon$):

$$
\begin{aligned}\xi(o_{1} = H \mid a_{1}) ~&=~ \tfrac{1}{2}\cdot 1 + \tfrac{1}{2}\cdot \tfrac{1}{2}~=~ \tfrac{3}{4}.\end{aligned}
$$

**After observing a head** ($t=2$), the posterior updates:

$$
\begin{aligned}w(\nu_{HH}\mid \aes_{1}) ~&=~ \tfrac{1}{2}\cdot \frac{1}{3/4}~=~ \tfrac{2}{3},&w(\nu_{HT}\mid \aes_{1}) ~&=~ \tfrac{1}{2}\cdot \frac{1/2}{3/4}~=~ \tfrac{1}{3}.\end{aligned}
$$

**Updated prediction:** $\xi(o_{2} = H \mid \aes_{1}a_{2}) = \tfrac{2}{3}\cdot 1 + \tfrac{1}{3}\cdot \tfrac{1}{2}= \tfrac{5}{6}$.

**Value function.** Continuing the same setup, suppose the agent always predicts $H$ (policy $\pi_{H}$).

Under $\nu_{HH}$: always correct, $r_{t} = 1$ every step: $V_{\nu_{HH}}^{\pi_H}(\epsilon) = (1-\gamma) \sum_{k=0}^{\infty} \gamma^{k} \cdot 1 = 1$.

Under $\nu_{HT}$: correct half the time: $V_{\nu_{HT}}^{\pi_H}(\epsilon) = (1-\gamma) \sum_{k=0}^{\infty} \gamma^{k} \cdot \tfrac{1}{2}= \tfrac{1}{2}$.

The mixture value (by [Exercise 4.2](#prob-linearity-inf)) is: $V_{\xi}^{\pi_H}(\epsilon) = \tfrac{1}{2}\cdot 1 + \tfrac{1}{2}\cdot \tfrac{1}{2}= \tfrac{3}{4}$.

As the agent observes more heads ($\mu = \nu_{HH}$), the posterior on $\nu_{HH}$ increases towards 1, and $V_{\xi}^{\pi_H}\to V_{\nu_{HH}}^{\pi_H}= 1$. This is on-policy value convergence ([Theorem 7.6](#thm-on-policy)) in action.

## B. Knuth's Difficulty Scale

Each subproblem carries a difficulty rating in square brackets, following Knuth's rating scheme for exercises ([Knuth 1973](#bib-knuth-73a)) in slightly adapted form. The rating assumes that the material in the preceding problems (on which the subproblem depends) has been understood. In-between values are possible.

**[00]** *Very easy.* Solvable from the top of your head.

**[10]** *Easy.* Needs 15 minutes to think, possibly pencil and paper.

**[20]** *Average.* May take 1–2 hours to answer completely.

**[30]** *Moderately difficult or lengthy.* May take several hours to a day.

**[40]** *Quite difficult or lengthy.* Often a significant research result.

**[50]** *Open research problem.* An obtained solution should be published.

## References

<div id="bib-blackwell-62">

D. Blackwell and L. Dubins (1962). [*Merging of opinions with increasing information*](http://www.dklevine.com/archive/refs4565.pdf). Annals of Mathematical Statistics.

</div>

<div id="bib-hutter-04uaibook">

Marcus Hutter (2005). [*Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability*](http://www.hutter1.net/ai/uaibook.htm). Springer.

</div>

<div id="bib-hutter-24uaibook2">

Marcus Hutter, David Quarel, and Elliot Catt (2024). [*An Introduction to Universal Artificial Intelligence*](http://www.hutter1.net/ai/uaibook2.htm). Chapman & Hall.

</div>

<div id="bib-knuth-73a">

D. E. Knuth (1973). *The Art of Computer Programming, Volume I: Fundamental Algorithms*. Addison-Wesley.

</div>

<div id="bib-leike-15badpriors">

Jan Leike and Marcus Hutter (2015). [*Bad Universal Priors and Notions of Optimality*](https://arxiv.org/abs/1510.04931). CoRR.

</div>

[^1]: See [Appendix A](#a-worked-example-bayesian-mixture-and-value-function) for a worked example. For simplicity, we consider only geometric discounting.

[^2]: The optimal value is defined as a $\sup$ over policies. In general, a supremum need not be attained (e.g. $\sup_{x \in (0,1)}x = 1$ but no $x \in (0,1)$ achieves it). [Section 2](#2-existence-of-optimal-policies) shows that the sup is attained in our setting.

[^3]: We are deliberately avoiding a formal treatment of measure theory here. Not all subsets of $(\cA \times \cE)^{\infty}$ are measurable; we restrict to "nice" (measurable) sets built from finite-prefix conditions via countable set operations, which suffice for everything in this sheet. For a rigorous treatment using $\sigma$-algebras and probability measures, see ([Hutter et al. 2024](#bib-hutter-24uaibook2), Chapter 2.2).

[^4]: The standard name is *absolute continuity* of $P$ with respect to $Q$, written $P \ll Q$.

[^5]: If the true environment is $\mu$ then we don't care about the behaviour of the Bayesian agent on histories that have $\mu^{\pi}$-probability zero: such histories will never be observed anyway.