---
cluster: D
day: D.3
title: "AIXI"
contributors:
  - David Quarel (Australian National University)
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}}$

<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."

## 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.

## 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 [Section 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-14e23c80befc.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^{\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>

<Solution>

Expanding the definition: $\nu^{\pi}(\aes_{1:t}) = \prod_{k=1}^{t} \pi(a_{k} \mid \aes_{<k})\, \nu(e_{k} \mid \aes_{<k}a_{k}) = \underbrace{\prod_{k=1}^t \pi(a_k \mid \aes_{<k})}_{\pi(\aes_{1:t})}\cdot \underbrace{\prod_{k=1}^t \nu(e_k \mid \aes_{<k} a_k)}_{\nu(\aes_{1:t})}$.

Key observation: $\pi(\aes_{1:t})$ is the same regardless of the environment. When comparing $\nu^{\pi}$ and $\mu^{\pi}$, the policy factors cancel.

</Solution>

<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>

<Solution>

From the definition $\nu(\aes_{1:t}) = \prod_{k=1}^{t} \nu(e_{k} \mid \aes_{<k}a_{k})$, split off the last factor:

$$
\nu(\aes_{1:t}) ~=~ \prod_{k=1}^{t-1}\nu(e_{k} \mid \aes_{<k}a_{k}) \cdot \nu(e_{t} \mid \aes_{<t}a_{t}) ~=~ \nu(\aes_{<t}) \cdot \nu(e_{t} \mid \aes_{<t}a_{t}).
$$

</Solution>

<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>

<Solution>

From [Definition 0.4](#def-interaction), the one-step interaction is $\nu^{\pi}(a_{t} e_{t} \mid \aes_{<t}) = \pi(a_{t} \mid \aes_{<t})\, \nu(e_{t} \mid \aes_{<t}a_{t})$. Summing over $e_{t}$:

$$
\sum_{e_t}\nu^{\pi}(a_{t} e_{t} \mid \aes_{<t}) ~=~ \pi(a_{t} \mid \aes_{<t}) \underbrace{\sum_{e_t} \nu(e_t \mid \aes_{<t} a_t)}_{=\,1}~=~ \pi(a_{t} \mid \aes_{<t}).
$$

Interpretation: after summing out the environment's response, only the agent's action probability remains.

</Solution>

<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>

<Solution>

Since $\pi$ is deterministic, $\pi(a_{k} \mid \aes_{<k}) = \llbracket a_{k} = a^{*}_{k} \rrbracket$. By hypothesis $\aes_{i:j}$ is $\pi$-consistent, so every such bracket equals $1$. From [Definition 0.4](#def-interaction):

$$
\begin{aligned}\nu^{\pi}(\aes_{i:j}\mid \aes_{<i}) ~&=~ \prod_{k=i}^{j} \underbrace{\pi(a_k \mid \aes_{<k})}_{=\, 1}\, \nu(e_{k} \mid \aes_{<k}a_{k}) \\ ~&=~ \prod_{k=i}^{j} \nu(e_{k} \mid \aes_{<k}\, a_{k}) ~=~ \nu(\aes_{i:j}\mid \aes_{<i}),\end{aligned}
$$

where the last equality is the natural segment extension of $\nu(\aes_{1:t}) := \prod_{k=1}^{t} \nu(e_{k} \mid \aes_{<k}a_{k})$.

</Solution>

<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>

<Solution>

Split the defining product $\nu^{\pi}(\aes_{p:r}\mid \aes_{<p}) = \prod_{k=p}^{r} \pi(a_{k} \mid \aes_{<k})\, \nu(e_{k} \mid \aes_{<k}a_{k})$ at index $q$:

$$
\begin{aligned}&\nu^{\pi}(\aes_{p:r}\mid \aes_{<p}) ~=~ \prod_{k=p}^{r} \pi(a_{k} \mid \aes_{<k})\, \nu(e_{k} \mid \aes_{<k}a_{k})\\&=~ \underbrace{\prod_{k=p}^{q} \pi(a_k \mid \aes_{<k})\, \nu(e_k \mid \aes_{<k} a_k)}_{\nu^\pi(\aes_{p:q} \mid \aes_{<p})}\;\cdot\; \underbrace{\prod_{k=q+1}^{r} \pi(a_k \mid \aes_{<k})\, \nu(e_k \mid \aes_{<k} a_k)}_{\nu^\pi(\aes_{q+1:r} \mid \aes_{<p}\, \aes_{p:q})},\end{aligned}
$$

identifying each block as a conditional via the same expansion: the past for step $k \geq q+1$ is the given history $\aes_{<p}$ extended by the first chunk $\aes_{p:q}$.

Note: for a deterministic policy, [Exercise 0.4](#prob-det-interaction) simplifies this further: each factor $\pi(a_{k} \mid \aes_{<k})\, \nu(e_{k} \mid \aes_{<k}a_{k})$ becomes just $\nu(e_{k} \mid \aes_{<k}\, a^{*}_{k})$.

</Solution>

## 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>

<Solution>

From the definition: $w(\nu \mid \aes_{1:t}) = w_{\nu} \cdot \nu(\aes_{1:t})/\xi(\aes_{1:t})$ and $w(\nu \mid \aes_{<t}) = w_{\nu} \cdot \nu(\aes_{<t})/\xi(\aes_{<t})$.

Dividing:

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

where we used the chain rule ([Exercise 0.2](#prob-chain-rule)) for both $\nu$ and $\xi$.

</Solution>

<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>

<Solution>

The one-step conditional is the ratio of joint to marginal: $\xi(e_{t} \mid \aes_{<t}a_{t}) := \xi(\aes_{1:t})/\xi(\aes_{<t})$.

Expanding the numerator using $\xi(\aes_{1:t}) = \sum_{\nu} w_{\nu} \nu(\aes_{1:t})$:

$$
\begin{aligned}\xi(e_{t} \mid \aes_{<t}a_{t}) ~&=~ \frac{\sum_{\nu \in \cM}w_{\nu}\, \nu(\aes_{1:t})}{\xi(\aes_{<t})}\\[4pt] ~&=~ \frac{\sum_{\nu}w_{\nu}\, \nu(\aes_{<t}) \cdot \nu(e_{t} \mid \aes_{<t}a_{t})}{\xi(\aes_{<t})}\qquad \text{(chain rule, Exercise 0.2)}\\[4pt] ~&=~ \sum_{\nu}\underbrace{\frac{w_{\nu}\, \nu(\aes_{<t})}{\xi(\aes_{<t})}}_{= \, w(\nu \mid \aes_{<t})}\cdot\, \nu(e_{t} \mid \aes_{<t}a_{t}) \\[4pt] ~&=~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, \nu(e_{t} \mid \aes_{<t}a_{t}).\end{aligned}
$$

</Solution>

<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>

<Solution>

Since $r_{k} \in [0,1]$, each discounted reward sum is bounded:

$$
0 ~\leq~ (1-\gamma)\, G_{t-1:m}~\leq~ (1-\gamma)\sum_{k=t}^{m}\gamma^{k-t}~=~ 1 - \gamma^{m-t+1}~\leq~ 1.
$$

The interaction measure satisfies $\nu^{\pi}(\aes'_{t:m}\mid \aes_{<t}) \geq 0$ and $\sum_{\aes'_{t:m}}\nu^{\pi}(\aes'_{t:m}\mid \aes_{<t}) = 1$, so the value function is a weighted average of terms in $[0,1]$:

$$
0 ~\leq~ V_{\nu}^{\pi,m}(\aes_{<t}) ~=~ \sum_{\aes'_{t:m}}\nu^{\pi}(\aes'_{t:m}\mid \aes_{<t})\, (1-\gamma)\, G_{t-1:m}~\leq~ 1.
$$

For $m = \infty$: since $0 \leq V_{\nu}^{\pi,m}(\aes_{<t}) \leq 1$ for all finite $m$, the limit $V_{\nu}^{\pi}(\aes_{<t}) = \lim_{m \to \infty}V_{\nu}^{\pi,m}(\aes_{<t})$ also lies in $[0,1]$.

</Solution>

<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>

<Solution>

Start from the definition $\xi(\aes_{1:m}) = \sum_{\nu \in \cM}w_{\nu}\, \nu(\aes_{1:m})$. Apply the general chain rule ([Exercise 0.5](#prob-chain-rule-nupi)) to both sides: $\xi(\aes_{1:m}) = \xi(\aes_{<t}) \cdot \xi(\aes_{t:m}\mid \aes_{<t})$ and $\nu(\aes_{1:m}) = \nu(\aes_{<t}) \cdot \nu(\aes_{t:m}\mid \aes_{<t})$. Dividing by $\xi(\aes_{<t})$:

$$
\begin{aligned}\xi(\aes_{t:m}\mid \aes_{<t}) ~&=~ \sum_{\nu \in \cM}\frac{w_{\nu}\, \nu(\aes_{<t})}{\xi(\aes_{<t})}\nu(\aes_{t:m}\mid \aes_{<t}) \\ ~&=~ \sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, \nu(\aes_{t:m}\mid \aes_{<t}).\end{aligned}
$$

Now multiply both sides by $\pi(\aes_{t:m}\mid \aes_{<t})$. By factorization ([Exercise 0.1](#prob-factorization)), $\pi(\aes_{t:m}\mid \aes_{<t}) \cdot \xi(\aes_{t:m}\mid \aes_{<t}) = \xi^{\pi}(\aes_{t:m}\mid \aes_{<t})$ and likewise for each $\nu$:

$$
\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}).
$$

</Solution>

## 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>

<Solution>

Let $a^{*} \in \argmax_{a' \in \cA}Q(a')$, which exists because $\cA$ is finite. So $Q(a^{*}) = \max_{a'}Q(a')$.

*Upper bound.* For any $\pi$: $\sum_{a} \pi(a \mid \aes_{<t}) Q(a) \leq \sum_{a} \pi(a \mid \aes_{<t}) Q(a^{*}) = Q(a^{*})$.

*Lower bound.* The deterministic $\pi^{*}$ with $\pi^{*}(a^{*} \mid \aes_{<t}) = 1$ achieves $Q(a^{*})$.

Combining: $\sup_{\pi} \sum_{a} \pi(a) Q(a) = Q(a^{*}) = \max_{a'}Q(a')$, attained by $\pi^{*}$.

</Solution>

<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>

<Solution>

*Step 1: Factor the future.* Write $\aes'_{t:m}= \aes'_{t}\, \aes'_{t+1:m}$: $\nu^{\pi}(\aes'_{t:m}\mid \aes_{<t}) = \nu^{\pi}(\aes'_{t} \mid \aes_{<t}) \cdot \nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t})$.

*Step 2: Split the reward sum.* This is just the return recursion ([Definition 0.3](#def-return)): $G_{t-1:m}= r'_{t} + \gamma\, G_{t:m}$, where $G_{t-1:m}= \sum_{k=t}^{m}\gamma^{k-t}r'_{k}$ is the return given $\aes_{<t}$.

*Step 3: Substitute into the definition of $V_{\nu}^{\pi,m}(\aes_{<t})$.*

$$
\begin{aligned}V_{\nu}^{\pi,m}(\aes_{<t}) ~&=~ (1-\gamma) \sum_{\aes'_t}\nu^{\pi}(\aes'_{t} \mid \aes_{<t}) \sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t}) \\&\qquad \times \left[ r'_{t} + \gamma G_{t:m}\right].\end{aligned}
$$

Consider the inner term $\sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t}) \left[ r'_{t} + \gamma G_{t:m}\right]$. We can expand as:

$$
\begin{aligned}&= \sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t}) r'_{t} + \gamma \sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t}) G_{t:m}\\&= r'_{t} \cancel{\sum_{\aes'_{t+1:m}} \nu^\pi(\aes'_{t+1:m} \mid \aes_{<t}\, \aes'_t)}+ \gamma \sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t}) G_{t:m}\\&= r'_{t} + \gamma \sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t}) G_{t:m}\end{aligned}
$$

as $r'_{t}$ doesn't depend on $\aes'_{t+1:m}$, and $\sum_{\aes'_{t+1:m}}\nu^{\pi}(\aes'_{t+1:m}\mid \aes_{<t}\, \aes'_{t}) = 1$. Inserting this above, we obtain:

$$
\begin{aligned}V_{\nu}^{\pi,m}(\aes_{<t})&= \sum_{\aes'_t}\nu^{\pi}(\aes'_{t} \mid \aes_{<t}) \bigg[ (1-\gamma)\, r'_{t} \\&\qquad + \gamma\, \underbrace{(1-\gamma) \sum_{\aes'_{t+1:m}} \nu^\pi(\aes'_{t+1:m} \mid \aes_{<t}\, \aes'_t)G_{t:m}}_{=\; V_\nu^{\pi,m}(\aes_{<t}\, \aes'_t)}\bigg].\end{aligned}
$$

</Solution>

<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>

<Solution>

We induct on $t = m, m-1, \ldots, 1$, showing that for every history $\aes_{<t}$, a deterministic policy achieves $V_{\nu}^{*,m}(\aes_{<t})$.

*Base case ($t = m$):* At $t = m$ the continuation term vanishes (the value from time $m+1$ is an empty sum), so the Bellman equation gives $V_{\nu}^{\pi,m}(\aes_{<m}) = (1-\gamma) \sum_{\aes'_m}\nu^{\pi}(\aes'_{m} \mid \aes_{<m})\, r'_{m}$. Splitting the step $\aes'_{m} = a'_{m} e'_{m}$ via $\nu^{\pi}(\aes'_{m} \mid \aes_{<m}) = \pi(a'_{m} \mid \aes_{<m})\, \nu(e'_{m} \mid \aes_{<m}a'_{m})$ gives $V_{\nu}^{\pi,m}(\aes_{<m}) = (1-\gamma) \sum_{a'_m}\pi(a'_{m} \mid \aes_{<m}) \sum_{e'_m}\nu(e'_{m} \mid \aes_{<m}a'_{m})\, r'_{m}$. This has the form $\sum_{a} \pi(a) Q(a)$ with $Q(a) = (1-\gamma)\sum_{e'_m}\nu(e'_{m} \mid \aes_{<m}a)\, r'_{m}$, which is independent of $\pi$. By [Exercise 2.1](#prob-sup-eq-max), the supremum over $\pi$ is $\max_{a} Q(a)$, attained by the deterministic policy playing $a^{*} \in \argmax_{a} Q(a)$.

*Inductive step:* Suppose that for every history of length $t$, there exists a deterministic policy $\pi^{*}_{t+1}$ achieving $V_{\nu}^{\pi^*_{t+1},m}= V_{\nu}^{*,m}$ from time $t+1$ onwards. Substituting this optimal continuation into the Bellman equation from [Exercise 2.2](#prob-bellman-finite) gives

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

Splitting the step $\aes'_{t} = a'_{t} e'_{t}$ via $\nu^{\pi}(\aes'_{t} \mid \aes_{<t}) = \pi(a'_{t} \mid \aes_{<t})\, \nu(e'_{t} \mid \aes_{<t}a'_{t})$ and grouping the percept sum into the action weight:

$$
V_{\nu}^{\pi,m}(\aes_{<t}) ~=~ \sum_{a'_t}\pi(a'_{t} \mid \aes_{<t})\, Q(a'_{t}),
$$

where $Q(a'_{t}) := \sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}a'_{t}) [(1-\gamma)\, r'_{t} + \gamma\, V_{\nu}^{*,m}(\aes_{<t}\, a'_{t}\, e'_{t})]$ is independent of $\pi$ (the continuation value $V_{\nu}^{*,m}$ is fixed by the inductive hypothesis). By [Exercise 2.1](#prob-sup-eq-max), $\sup_{\pi} \sum_{a'_t}\pi(a'_{t})\, Q(a'_{t}) = \max_{a'_t}Q(a'_{t})$, attained by the deterministic policy playing $a^{*}_{t} \in \argmax_{a'_t}Q(a'_{t})$ at time $t$, then following $\pi^{*}_{t+1}$.

</Solution>

<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>

<Solution>

By [Exercise 2.3](#prob-backward-induction), a deterministic optimal policy $\pi^{*}_{\nu}$ exists with $V_{\nu}^{\pi^*_\nu,m}= V_{\nu}^{*,m}$. Substituting $\pi = \pi^{*}_{\nu}$ into the Bellman equation from [Exercise 2.2](#prob-bellman-finite) (using $V_{\nu}^{\pi^*_\nu,m}= V_{\nu}^{*,m}$ on both sides):

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

Splitting the step $\aes'_{t} = a'_{t} e'_{t}$ via $\nu^{\pi^*_\nu}(\aes'_{t} \mid \aes_{<t}) = \pi^{*}_{\nu}(a'_{t} \mid \aes_{<t})\, \nu(e'_{t} \mid \aes_{<t}a'_{t})$:

$$
\begin{aligned}V_{\nu}^{*,m}(\aes_{<t}) ~&=~ \sum_{a'_t}\pi^{*}_{\nu}(a'_{t} \mid \aes_{<t}) \\&\qquad \times \sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}a'_{t}) \Big[(1-\gamma)\, r'_{t} + \gamma\, V_{\nu}^{*,m}(\aes_{<t}\, a'_{t}\, e'_{t})\Big].\end{aligned}
$$

Since $\pi^{*}_{\nu}$ is deterministic, let $a^{*}_{t}$ denote the unique action with $\pi^{*}_{\nu}(a^{*}_{t} \mid \aes_{<t}) = 1$. Then:

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

Define $Q(a) := \sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}a) [(1-\gamma)\, r'_{t} + \gamma\, V_{\nu}^{*,m}(\aes_{<t}\, a\, e'_{t})]$. Then $V_{\nu}^{*,m}(\aes_{<t}) = Q(a^{*}_{t})$. We must have $Q(a^{*}_{t}) = \max_{a}Q(a)$: if some $\tilde{a}$ had $Q(\tilde{a}) > Q(a^{*}_{t})$, then the policy that plays $\tilde{a}$ at $\aes_{<t}$ and follows $\pi^{*}_{\nu}$ elsewhere would achieve value $Q(\tilde{a}) > V_{\nu}^{*,m}(\aes_{<t})$, contradicting $V_{\nu}^{*,m}= \sup_{\pi} V_{\nu}^{\pi,m}$. Hence:

$$
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}\, a'_{t}\, e'_{t})\Big].
$$

</Solution>

<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>

<Solution>

We show $V_{\nu}^{*,m+1}(\aes_{<t}) \geq V_{\nu}^{*,m}(\aes_{<t})$ for all $\aes_{<t}$. Since $V_{\nu}^{*,m+1}= \sup_{\pi} V_{\nu}^{\pi,m+1}$, it suffices to show $V_{\nu}^{\pi,m+1}(\aes_{<t}) \geq V_{\nu}^{\pi,m}(\aes_{<t})$ for every $\pi$. Expanding the definition:

$$
\begin{aligned}&V_{\nu}^{\pi,m+1}(\aes_{<t}) \\ ~&=~ (1-\gamma) \sum_{\aes_{t:m+1}}\nu^{\pi}(\aes_{t:m+1}\mid \aes_{<t})\, G_{t-1:m+1}\\ ~&=~ (1-\gamma) \sum_{\aes_{t:m+1}}\nu^{\pi}(\aes_{t:m+1}\mid \aes_{<t}) \left[G_{t-1:m}~+~ \gamma^{m+1-t}r_{m+1}\right] \\ ~&=~ (1-\gamma) \sum_{\aes_{t:m+1}}\nu^{\pi}(\aes_{t:m+1}\mid \aes_{<t}) G_{t-1:m}\\ ~&\qquad+~ \underbrace{(1-\gamma)\, \gamma^{m+1-t} \sum_{\aes_{t:m+1}} \nu^\pi(\aes_{t:m+1} \mid \aes_{<t})\, r_{m+1}}_{\geq\; 0}.\end{aligned}
$$

For the first term, marginalize over $a_{m+1}, e_{m+1}$ (which $G_{t-1:m}$ does not depend on):

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

So $V_{\nu}^{\pi,m+1}(\aes_{<t}) \geq (1-\gamma) \sum_{\aes_{t:m}}\nu^{\pi}(\aes_{t:m}\mid \aes_{<t}) G_{t-1:m}= V_{\nu}^{\pi,m}(\aes_{<t})$.

Since $V_{\nu}^{*,m}(\aes_{<t})$ is non-decreasing in $m$ and bounded in $[0,1]$ by [Exercise 1.3](#prob-bounded-value), the monotone convergence theorem gives that $V_{\nu}^{*}(\aes_{<t}) := \lim_{m \to \infty}V_{\nu}^{*,m}(\aes_{<t})$ exists for each $\aes_{<t}$.

</Solution>

<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>

<Solution>

By [Exercise 2.4](#prob-bellman-opt), for every 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}\, a'_{t}\, e'_{t})\Big].
$$

By [Exercise 2.5](#prob-inf-horizon), each $V_{\nu}^{*,m}(\cdot)$ converges pointwise to $V_{\nu}^{*}(\cdot)$ as $m \to \infty$. Since $\cA$ and $\cE$ are finite, the $\max$ and $\sum$ are over finitely many convergent terms, so:

$$
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].
$$

</Solution>

<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>

<Solution>

*Step 1: Define the greedy policy.* For each history $\aes_{<t}$, let

$$
a^{*}_{t} \in \argmax_{a'_t}\sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}a'_{t}) [(1-\gamma)\, r'_{t} + \gamma\, V_{\nu}^{*}(\aes_{<t}\, a'_{t}\, e'_{t})],
$$

which exists because $\cA$ is finite. Define the deterministic policy $\pi_{\nu}^{*}(a \mid \aes_{<t}) := \llbracket a = a^{*}_{t} \rrbracket$. By [Exercise 2.6](#prob-inf-bellman-opt), the infinite-horizon Bellman optimality equation becomes:

$$
V_{\nu}^{*}(\aes_{<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].
$$

*Step 2: Error recursion.* The Bellman equation ([Exercise 2.2](#prob-bellman-finite)) holds for any policy, so for $\pi_{\nu}^{*}$ at finite horizon $m$:

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

Subtracting this from the equation in Step 1, the $(1-\gamma)\, r'_{t}$ terms cancel:

$$
\begin{aligned}V_{\nu}^{*}(\aes_{<t}) - V_{\nu}^{\pi_\nu^*,m}(\aes_{<t}) ~&=~ \gamma \sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}\, a^{*}_{t}) \\&\qquad \times \Big[V_{\nu}^{*}(\aes_{<t}\, a^{*}_{t}\, e'_{t}) - V_{\nu}^{\pi_\nu^*,m}(\aes_{<t}\, a^{*}_{t}\, e'_{t})\Big].\end{aligned}
$$

The error at time $t$ is $\gamma$ times a weighted average of errors at time $t+1$.

*Step 3: Iterate the contraction.* Write $\Delta V_{\nu}^{m}(\aes_{<t}) := V_{\nu}^{*}(\aes_{<t}) - V_{\nu}^{\pi_\nu^*,m}(\aes_{<t}) \geq 0$ for the error. Step 2 gives:

$$
\Delta V_{\nu}^{m}(\aes_{<t}) ~=~ \gamma \sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}\, a^{*}_{t})\, \Delta V_{\nu}^{m}(\aes_{<t}\, a^{*}_{t}\, e'_{t}).
$$

Applying the same recursion at time $t+1$ (with greedy action $a^{*}_{t+1}$ at history $\aes_{<t}\, a^{*}_{t}\, e'_{t}$):

$$
\Delta V_{\nu}^{m}(\aes_{<t}) ~=~ \gamma^{2} \sum_{e'_t}\nu(e'_{t} \mid \aes_{<t}\, a^{*}_{t}) \sum_{e'_{t+1}}\nu(e'_{t+1}\mid \aes_{<t}\, a^{*}_{t}\, e'_{t}\, a^{*}_{t+1})
$$

$$
\qquad \times \Delta V_{\nu}^{m}(\aes_{<t}\, a^{*}_{t}\, e'_{t}\, a^{*}_{t+1}\, e'_{t+1}).
$$

After $m - t + 1$ iterations, summing over all percept sequences $e'_{t:m}$:

$$
\Delta V_{\nu}^{m}(\aes_{<t}) ~=~ \gamma^{m-t+1}\sum_{e'_{t:m}}\left(\prod_{k=t}^{m} \nu(e'_{k} \mid \aes'_{<k}\, a^{*}_{k})\right) \Delta V_{\nu}^{m}(\aes_{<t}\, \aes'_{t:m}),
$$

where $\aes'_{t:m}= a^{*}_{t}\, e'_{t}\, \cdots\, a^{*}_{m}\, e'_{m}$ is the history segment generated by $\pi_{\nu}^{*}$. By [Exercise 0.4](#prob-det-interaction), the product of $\nu$-conditionals is $\nu^{\pi_\nu^*}(\aes'_{t:m}\mid \aes_{<t})$. At the boundary, $V_{\nu}^{\pi_\nu^*,m}(\aes_{<t}\, \aes'_{t:m}) = 0$ (summing over no rewards past horizon $m$), so $\Delta V_{\nu}^{m}(\aes_{<t}\, \aes'_{t:m}) = V_{\nu}^{*}(\aes_{<t}\, \aes'_{t:m}) \in [0,1]$. Therefore:

$$
\Delta V_{\nu}^{m}(\aes_{<t}) ~=~ \gamma^{m-t+1}\sum_{\aes'_{t:m}}\nu^{\pi_\nu^*}(\aes'_{t:m}\mid \aes_{<t})\, V_{\nu}^{*}(\aes_{<t}\, \aes'_{t:m}) ~\leq~ \gamma^{m-t+1}.
$$

*Step 4: Take $m \to \infty$.* Since $0 \leq V_{\nu}^{*}(\aes_{<t}) - V_{\nu}^{\pi_\nu^*,m}(\aes_{<t}) \leq \gamma^{m-t+1}\to 0$, we have $V_{\nu}^{\pi_\nu^*,m}(\aes_{<t}) \to V_{\nu}^{*}(\aes_{<t})$, i.e. $V_{\nu}^{\pi_\nu^*}= V_{\nu}^{*}$.

</Solution>

## 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>

<Solution>

$\xi(\aes_{<t}) = \sum_{\nu' \in \cM}w_{\nu'}\nu'(\aes_{<t}) \geq w_{\nu} \nu(\aes_{<t})$.

</Solution>

<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>

<Solution>

By [Exercise 0.1](#prob-factorization): $\xi^{\pi}(\aes_{1:m}) = \pi(\aes_{1:m}) \cdot \xi(\aes_{1:m}) \geq \pi(\aes_{1:m}) \cdot w_{\nu} \nu(\aes_{1:m}) = w_{\nu} \cdot \nu^{\pi}(\aes_{1:m})$.

</Solution>

## 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>

<Solution>

By [Exercise 1.4](#prob-multi-step-xi): $\xi^{\pi}(\aes_{t:m}\mid \aes_{<t}) = \sum_{\nu} w(\nu \mid \aes_{<t})\, \nu^{\pi}(\aes_{t:m}\mid \aes_{<t})$. Multiply both sides by $(1-\gamma)G_{t-1:m}$ and sum over all $\aes_{t:m}$:

$$
\begin{aligned}V_{\xi}^{\pi,m}(\aes_{<t}) ~&=~ (1-\gamma) \sum_{\aes_{t:m}}\xi^{\pi}(\aes_{t:m}\mid \aes_{<t}) G_{t-1:m}\\ ~&=~ (1-\gamma) \sum_{\aes_{t:m}}\left[\sum_{\nu} w(\nu \mid \aes_{<t})\, \nu^{\pi}(\aes_{t:m}\mid \aes_{<t})\right] G_{t-1:m}\\ ~&=~ \sum_{\nu} w(\nu \mid \aes_{<t}) \underbrace{(1-\gamma) \sum_{\aes_{t:m}} \nu^\pi(\aes_{t:m} \mid \aes_{<t}) G_{t-1:m}}_{=\; V_\nu^{\pi,m}(\aes_{<t})}.\end{aligned}
$$

In the last step we exchanged $\sum_{\aes_{t:m}}$ and $\sum_{\nu}$; this is valid because both are sums of non-negative terms (or, for finite $m$, the sum over $\aes_{t:m}$ is finite). So:

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

</Solution>

<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>

<Solution>

The left side converges: $V_{\xi}^{\pi,m}(\aes_{<t}) \to V_{\xi}^{\pi}(\aes_{<t})$ by definition.

For the right side, we need to push $\lim_{m \to \infty}$ through $\sum_{\nu}$. If $\cM$ is finite this is immediate. For countably infinite $\cM$, we apply [Fact 4.1](#thm-dom-conv) (dominated convergence for sums):

- For each $\nu$: $a_{\nu,m}:= w(\nu \mid \aes_{<t})\, V_{\nu}^{\pi,m}(\aes_{<t}) \to w(\nu \mid \aes_{<t})\, V_{\nu}^{\pi}(\aes_{<t})$ as $m \to \infty$ by definition.
- Domination: $|a_{\nu,m}| \leq w(\nu \mid \aes_{<t}) \cdot 1 =: b_{\nu}$ for all $m$, since $V_{\nu}^{\pi,m}\in [0,1]$ ([Exercise 1.3](#prob-bounded-value)).
- Summability: $\sum_{\nu} b_{\nu} = \sum_{\nu} w(\nu \mid \aes_{<t}) = 1 < \infty$.

So [Fact 4.1](#thm-dom-conv) gives:

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

</Solution>

[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>

<Solution>

By [Exercise 2.3](#prob-backward-induction), a deterministic Bayes-optimal policy $\pi_{\xi}^{*}$ exists with $V_{\xi}^{\pi_\xi^*,m}= V_{\xi}^{*,m}$. Applying [Exercise 4.1](#prob-linearity-finite) with $\pi = \pi_{\xi}^{*}$:

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

Since $\pi_{\xi}^{*}$ is optimal for $\xi$ but not necessarily for each individual $\nu$, we have $V_{\nu}^{\pi_\xi^*,m}(\aes_{<t}) \leq V_{\nu}^{*,m}(\aes_{<t})$ for each $\nu$. Since $w(\nu \mid \aes_{<t}) \geq 0$:

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

</Solution>

<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>

<Solution>

*Coin-flip prediction.* Let $\cA = \cO = \cR = \{0,1\}$, $\cM = \{\nu_{0}, \nu_{1}\}$ with $w_{\nu_0}= w_{\nu_1}= \tfrac{1}{2}$, horizon $m = 1$. Environment $\nu_{i}$ always shows outcome $i$, and the agent is rewarded for a correct prediction:

$$
\nu_{i}(e_{t} \mid \aes_{<t}\, a_{t}) ~:~ o_{t} = i, \quad r_{t} = \llbracket a_{t} = i \rrbracket.
$$

In $\nu_{i}$ the optimal policy plays $a_{t} = i$, achieving $V_{\nu_i}^{*,m}= 1$. In $\xi = \tfrac{1}{2}\nu_{0} + \tfrac{1}{2}\nu_{1}$ the outcome is a fair coin flip, so no policy predicts better than chance: $V_{\xi}^{*,m}= \tfrac{1}{2}$. Therefore:

$$
\sum_{\nu} w_{\nu}\, V_{\nu}^{*,m}(\aes_{<t}) ~=~ \tfrac{1}{2}\cdot 1 + \tfrac{1}{2}\cdot 1 ~=~ 1 ~>~ \tfrac{1}{2}~=~ V_{\xi}^{*,m}(\aes_{<t}).
$$

</Solution>

## 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$ ([Exercise 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>

<Solution>

Abbreviate the one-step predictor $\xi_{k} := \xi(e_{k} \mid \aes_{<k}a_{k})$, and write the **expectimax operator** over steps $i, \ldots, j$ as

$$
\exmax_{i:j}~:=~ \max_{a_i}\sum_{e_i}\xi_{i}\, \max_{a_{i+1}}\sum_{e_{i+1}}\xi_{i+1}\cdots \max_{a_j}\sum_{e_j}\xi_{j},
$$

the alternating "maximize over the action, average over the percept" chain, with the $\xi_{k}$ weights built in; the single step is $\exmax_{k} := \max_{a_k}\sum_{e_k}\xi_{k}$. Two facts:

- **(E1) Composition:** $\exmax_{i:j}= \exmax_{i}\, \exmax_{i+1:j}$, by nesting the definition.
- **(E2) Affine pass-through:** for any $c \in \mathbb{R}$ and $\lambda \geq 0$ not depending on $(a_{i}, e_{i}, \ldots, a_{j}, e_{j})$,

$$
c + \lambda\, \exmax_{i:j}X ~=~ \exmax_{i:j}(c + \lambda X),
$$

since each layer has $\sum_{e_k}\xi_{k} = 1$ (so $\sum_{e_k}\xi_{k}(c+\lambda Y) = c + \lambda \sum_{e_k}\xi_{k} Y$) and $\max_{a}(c + \lambda\, g(a)) = c + \lambda \max_{a} g(a)$ for $\lambda \geq 0$.

We prove by backward induction on $t = m, m-1, \ldots, 1$ that

$$
V_{\xi}^{*,m}(\aes_{<t}) ~=~ (1-\gamma)\, \exmax_{t:m}\, G_{t-1:m}.
$$

*Base case $t = m$.* Here $G_{m-1:m}= r_{m}$ and $V_{\xi}^{*,m}(\aes_{1:m}) = 0$ (the return past the horizon is empty, $G_{m:m}= 0$). The Bellman optimality equation ([Exercise 2.4](#prob-bellman-opt)) for $\nu = \xi$ gives

$$
V_{\xi}^{*,m}(\aes_{<m}) ~=~ \max_{a_m}\sum_{e_m}\xi_{m} \big[(1-\gamma)\, r_{m} + \gamma \cdot 0\big] ~=~ (1-\gamma)\, \exmax_{m:m}\, G_{m-1:m}.
$$

*Inductive step.* Assume the claim at time $t+1$, i.e. $V_{\xi}^{*,m}(\aes_{1:t}) = (1-\gamma)\, \exmax_{t+1:m}\, G_{t:m}$ for every length-$t$ history (recall $\aes_{<t+1}= \aes_{1:t}$). The Bellman optimality equation ([Exercise 2.4](#prob-bellman-opt)) at time $t$ reads

$$
V_{\xi}^{*,m}(\aes_{<t}) ~=~ \exmax_{t} \big[(1-\gamma)\, r_{t} + \gamma\, V_{\xi}^{*,m}(\aes_{1:t})\big].
$$

Substituting the inductive hypothesis and pulling out $(1-\gamma)$,

$$
V_{\xi}^{*,m}(\aes_{<t}) ~=~ (1-\gamma)\, \exmax_{t} \big[r_{t} + \gamma\, \exmax_{t+1:m}\, G_{t:m}\big].
$$

As $r_{t}$ and $\gamma$ do not depend on $(a_{t+1}, e_{t+1}, \ldots, a_{m}, e_{m})$, property (E2) carries them inside the inner operator, and the return recursion $G_{t-1:m}= r_{t} + \gamma\, G_{t:m}$ ([Definition 0.3](#def-return)) gives

$$
r_{t} + \gamma\, \exmax_{t+1:m}\, G_{t:m}~\overset{(E2)}{=}~ \exmax_{t+1:m}(r_{t} + \gamma\, G_{t:m}) ~=~ \exmax_{t+1:m}\, G_{t-1:m}.
$$

Recombining the two operators by (E1),

$$
V_{\xi}^{*,m}(\aes_{<t}) ~=~ (1-\gamma)\, \exmax_{t}\, \exmax_{t+1:m}\, G_{t-1:m}~=~ (1-\gamma)\, \exmax_{t:m}\, G_{t-1:m},
$$

which expands back into the $\max/\sum$ layers of the first display.

*Infinite horizon and the action.* Taking $m \to \infty$ ([Exercise 2.5](#prob-inf-horizon) and [2.7](#prob-inf-opt-policy)), $G_{t-1:m}\to G_{\geq t-1}$ and the chain extends indefinitely, so $V_{\xi}^{*}(\aes_{<t}) = (1-\gamma)\, \exmax_{t:\infty}\, G_{\geq t-1}$. Collecting the per-step factors by the chain rule ([Exercise 0.2](#prob-chain-rule), iterated), $\prod_{k=t}^{m}\xi_{k} = \xi(e_{t:m}\mid \aes_{<t}\, a_{t:m})$. A Bayes-optimal action maximizes this expression; peeling the outer $\max_{a_t}$ off as an $\argmax$ and dropping the positive constant $(1-\gamma)$ (which does not move the maximizer) gives the stated action.

</Solution>

## 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>

<Solution>

Write out the expectation difference using [Definition 6.2](#def-expectation-p):

$$
\Ex_{P}[f] - \Ex_{Q}[f] ~=~ \sum_{\omega \in \Omega}f(\omega)\big(P(\omega) - Q(\omega)\big).
$$

Define $A^{+} := \{\omega \in \Omega : P(\omega) \geq Q(\omega)\}$ and $A^{-} := \Omega \setminus A^{+}$, and split the sum:

$$
\Ex_{P}[f] - \Ex_{Q}[f] ~=~ \sum_{\omega \in A^+}f(\omega)\big(P(\omega) - Q(\omega)\big) ~+~ \sum_{\omega \in A^-}f(\omega)\big(P(\omega) - Q(\omega)\big).
$$

*Bounding the sum over $A^{+}$.* On $A^{+}$, $P(\omega) - Q(\omega) \geq 0$ and $f(\omega) \leq c$, so:

$$
\begin{aligned}\sum_{\omega \in A^+}f(\omega)\big(P(\omega) - Q(\omega)\big) ~&\leq~ c \sum_{\omega \in A^+}\big(P(\omega) - Q(\omega)\big) \\ ~&=~ c \cdot \big(P(A^{+}) - Q(A^{+})\big) \\ ~&\leq~ c \cdot \sup_{S} |P(S) - Q(S)| \\ ~&=~ c \cdot \TV[\Omega](P, Q).\end{aligned}
$$

*Bounding the sum over $A^{-}$.* On $A^{-}$, $P(\omega) - Q(\omega) < 0$ and $f(\omega) \geq 0$, so every term $f(\omega)(P(\omega) - Q(\omega)) \leq 0$:

$$
\sum_{\omega \in A^-}f(\omega)\big(P(\omega) - Q(\omega)\big) ~\leq~ 0.
$$

*Combining.* $\Ex_{P}[f] - \Ex_{Q}[f] \leq c \cdot \TV[\Omega](P,Q) + 0 = c \cdot \TV[\Omega](P,Q)$.

*The other direction.* Swapping $P$ and $Q$: define $\tilde{A}^{+} = \{\omega : Q(\omega) \geq P(\omega)\} = A^{-}$. The same argument gives $\Ex_{Q}[f] - \Ex_{P}[f] \leq c \cdot \TV[\Omega](Q, P) = c \cdot \TV[\Omega](P, Q)$.

Therefore $|\Ex_{P}[f] - \Ex_{Q}[f]| \leq c \cdot \TV[\Omega](P, Q)$.

</Solution>

## 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} \subseteq A_{2} \subseteq \cdots$, then $\nu^{\pi}\!\big(\bigcup_{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}: \lim_{t \to \infty}\big(V_{\xi}^{\pi}(\aes_{<t}) - V_{\mu}^{\pi}(\aes_{<t})\big) \neq 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>

<Solution>

We want to apply [Section 6](#6-bounding-expectation-differences-by-total-variation). Identify:

- $\Omega := \cH^{m-t+1}= (\cA \times \cE)^{m-t+1}$, the finite set of future history segments $\aes_{t:m}$.
- $P := \mu^{\pi}(\cdot \mid \aes_{<t})$ and $Q := \xi^{\pi}(\cdot \mid \aes_{<t})$, the conditional measures over $\Omega$.
- $f(\aes_{t:m}) := (1-\gamma)G_{t-1:m}$, which satisfies $f \in [0,1]$ by [Exercise 1.3](#prob-bounded-value) (so $c = 1$).

Then $V_{\nu}^{\pi,m}(\aes_{<t}) = \sum_{\aes_{t:m}}\nu^{\pi}(\aes_{t:m}\mid \aes_{<t})\, f(\aes_{t:m})$ is exactly $\Ex_{P}[f]$ (for $\nu = \mu$) or $\Ex_{Q}[f]$ (for $\nu = \xi$). Applying [Section 6](#6-bounding-expectation-differences-by-total-variation):

$$
\big|V_{\xi}^{\pi,m}(\aes_{<t}) - V_{\mu}^{\pi,m}(\aes_{<t})\big| ~=~ \big|\Ex_{Q}[f] - \Ex_{P}[f]\big| ~\leq~ 1 \cdot \TV[\cH^{m-t+1}](P, Q).
$$

</Solution>

<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>

<Solution>

By [Section 3](#3-dominance-of-the-bayesian-mixture), $\xi^{\pi}(\aes_{1:m}) \geq w_{\mu} \cdot \mu^{\pi}(\aes_{1:m})$ for all histories and all $m$. So for any event $A$: $\mu^{\pi}(A) > 0 \implies \xi^{\pi}(A) \geq w_{\mu} \cdot \mu^{\pi}(A) > 0$. Hence $\xi^{\pi}$ covers $\mu^{\pi}$.

</Solution>

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>

<Solution>

*Step 1: Finite-horizon bound.* By [Exercise 7.1](#prob-tv-finite), for each finite $m$:

$$
\begin{aligned}\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) \\ ~&\leq~ \sup_{S} \big|\xi^{\pi}(S \mid \aes_{<t}) - \mu^{\pi}(S \mid \aes_{<t})\big|,\end{aligned}
$$

where the second inequality uses that the sup over subsets of $\cH^{m-t+1}$ is at most the sup over all measurable events.

*Step 2: Take $m \to \infty$.* The LHS converges to $|V_{\xi}^{\pi}(\aes_{<t}) - V_{\mu}^{\pi}(\aes_{<t})|$ (by definition of the infinite-horizon value as the pointwise limit). The RHS does not depend on $m$. Hence

$$
\big|V_{\xi}^{\pi}(\aes_{<t}) - V_{\mu}^{\pi}(\aes_{<t})\big| ~\leq~ \sup_{S} \big|\xi^{\pi}(S \mid \aes_{<t}) - \mu^{\pi}(S \mid \aes_{<t})\big|.
$$

*Step 3: Take $t \to \infty$.* By [Exercise 7.2](#prob-covering-proof), $\xi^{\pi}$ covers $\mu^{\pi}$. By [Fact 7.7](#fact-bd) (Blackwell–Dubins) with $P = \mu^{\pi}$ and $Q = \xi^{\pi}$, the RHS tends to $0$ as $t \to \infty$, $\mu^{\pi}$-a.s. Therefore

$$
\big|V_{\xi}^{\pi}(\aes_{<t}) - V_{\mu}^{\pi}(\aes_{<t})\big| ~\to~ 0 \qquad \mu^{\pi}\text{-a.s.}
$$

</Solution>

<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>

<Solution>

By definition, $V_{\xi}^{*}(\aes_{<t}) = \sup_{\pi} V_{\xi}^{\pi}(\aes_{<t}) \geq V_{\xi}^{\pi'}(\aes_{<t})$ for any policy $\pi'$. By [Exercise 4.2](#prob-linearity-inf) (linearity of $V^{\pi}$ in the environment):

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

Choose $\pi' = \pi_{\mu}^{*}$, the deterministic optimal policy for $\mu$ whose existence is guaranteed by [Exercise 2.7](#prob-inf-opt-policy):

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

Every term is non-negative ($w(\nu \mid \aes_{<t}) \geq 0$ and $V_{\nu}^{\pi_\mu^*}\geq 0$). Dropping all terms except $\nu = \mu$:

$$
V_{\xi}^{*}(\aes_{<t}) ~\geq~ w(\mu \mid \aes_{<t})\, V_{\mu}^{\pi_\mu^*}(\aes_{<t}) ~=~ w(\mu \mid \aes_{<t})\, V_{\mu}^{*}(\aes_{<t}).
$$

</Solution>

<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>

<Solution>

From [Definition 0.1](#def-mixture), the posterior weight is:

$$
w(\mu \mid \aes_{<t}) ~=~ w_{\mu} \cdot \frac{\mu(\aes_{<t})}{\xi(\aes_{<t})}~=~ w_{\mu} \cdot \frac{\prod_{k=1}^{t-1}\mu(e_{k} \mid \aes_{<k}a_{k})}{\prod_{k=1}^{t-1}\xi(e_{k} \mid \aes_{<k}a_{k})}.
$$

Since $\mu$ is deterministic, for the history that $\mu$ actually generates, $\mu(e_{k} \mid \aes_{<k}a_{k}) = 1$ for each $k$ (the environment produces each percept with certainty). So:

$$
\mu(\aes_{<t}) ~=~ \prod_{k=1}^{t-1}1 ~=~ 1.
$$

Meanwhile, $\xi(e_{k} \mid \aes_{<k}a_{k}) \leq 1$ for each $k$ (it is a probability), so $\xi(\aes_{<t}) = \prod_{k=1}^{t-1}\xi(e_{k} \mid \aes_{<k}a_{k}) \leq 1$.

Therefore $w(\mu \mid \aes_{<t}) = w_{\mu} \cdot 1 / \xi(\aes_{<t}) \geq w_{\mu}$.

Combining with [Exercise 8.1](#prob-xi-lower-bound):

$$
V_{\xi}^{*}(\aes_{<t}) ~\geq~ w(\mu \mid \aes_{<t}) \cdot V_{\mu}^{*}(\aes_{<t}) ~\geq~ w_{\mu} \cdot V_{\mu}^{*}(\aes_{<t}) ~>~ w_{\mu} \cdot \varepsilon ~>~ 0.
$$

</Solution>

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

## [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>

<Solution>

We need to compute $\Ex_{\mu^\pi}[X_{\nu,t}\mid \aes_{<t}]$. Conditioning on $\aes_{<t}$ means $a_{t}$ and $e_{t}$ are the random quantities (sampled from $\pi$ and $\mu$ respectively). First, write $X_{\nu,t}$ pointwise as a function of history in terms of $X_{\nu,t-1}$:

$$
\begin{aligned}X_{\nu,t}(\aes_{1:t}) ~&=~ \frac{\nu(\aes_{1:t})}{\mu(\aes_{1:t})}~=~ \frac{\nu(\aes_{<t})}{\mu(\aes_{<t})}\cdot \frac{\nu(e_{t} \mid \aes_{<t}a_{t})}{\mu(e_{t} \mid \aes_{<t}a_{t})}\\ ~&=~ X_{\nu,t-1}(\aes_{<t}) \cdot \frac{\nu(e_{t} \mid \aes_{<t}a_{t})}{\mu(e_{t} \mid \aes_{<t}a_{t})},\end{aligned}
$$

using the chain rule ([Exercise 0.2](#prob-chain-rule)) for both $\nu$ and $\mu$. Now take the conditional expectation. Since $X_{\nu,t-1}$ depends only on $\aes_{<t}$, it comes out of the expectation:

$$
\begin{aligned}\Ex_{\mu^\pi}[X_{\nu,t}\mid \aes_{<t}] ~&=~ X_{\nu,t-1}\cdot \Ex_{\mu^\pi}\!\left[\frac{\nu(e_{t} \mid \aes_{<t}a_{t})}{\mu(e_{t} \mid \aes_{<t}a_{t})}~\Big|~ \aes_{<t}\right] \\ ~&=~ X_{\nu,t-1}\sum_{a_t \in \cA}\pi(a_{t} \mid \aes_{<t}) \sum_{e_t \in \cE}\mu(e_{t} \mid \aes_{<t}a_{t}) \cdot \frac{\nu(e_{t} \mid \aes_{<t}a_{t})}{\mu(e_{t} \mid \aes_{<t}a_{t})}\\ ~&=~ X_{\nu,t-1}\sum_{a_t}\pi(a_{t} \mid \aes_{<t}) \sum_{e_t}\nu(e_{t} \mid \aes_{<t}a_{t}).\end{aligned}
$$

In the last step, $\mu(e_{t} \mid \aes_{<t}a_{t})$ cancels. Since $\nu$ is a probability measure, $\sum_{e_t}\nu(e_{t} \mid \aes_{<t}a_{t}) = 1$ for every $\aes_{<t}, a_{t}$; and $\sum_{a_t}\pi(a_{t} \mid \aes_{<t}) = 1$. Therefore:

$$
\Ex_{\mu^\pi}[X_{\nu,t}\mid \aes_{<t}] ~=~ X_{\nu,t-1}\cdot 1 \cdot 1 ~=~ X_{\nu,t-1}.
$$

Since $X_{\nu,t}\geq 0$ (a ratio of non-negative quantities), $(X_{\nu,t})_{t \geq 0}$ is a non-negative $\mu^{\pi}$-martingale, in particular, a non-negative $\mu^{\pi}$-supermartingale.

</Solution>

<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>

<Solution>

$X_{\nu,t}$ is a non-negative $\mu^{\pi}$-supermartingale by [Exercise 9.1](#prob-martingale). By [Fact 9.4](#fact-doob) (Doob's convergence theorem), $X_{\nu,t}$ converges $\mu^{\pi}$-a.s. to a finite limit: $X_{\nu,t}\to X_{\nu,\infty}< \infty$.

</Solution>

<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>

<Solution>

From the definition:

$$
X_{\xi,t}~:=~ \frac{\xi(\aes_{1:t})}{\mu(\aes_{1:t})}~=~ \frac{\sum_{\nu} w_{\nu} \nu(\aes_{1:t})}{\mu(\aes_{1:t})}~=~ \sum_{\nu} w_{\nu} \cdot \frac{\nu(\aes_{1:t})}{\mu(\aes_{1:t})}~=~ \sum_{\nu} w_{\nu} X_{\nu,t}.
$$

By [Section 3](#3-dominance-of-the-bayesian-mixture): $\xi(\aes_{1:t}) \geq w_{\mu} \cdot \mu(\aes_{1:t})$, so $X_{\xi,t}= \xi(\aes_{1:t})/\mu(\aes_{1:t}) \geq w_{\mu} > 0$.

Since $\cM$ is finite, $X_{\xi,t}= \sum_{\nu} w_{\nu} X_{\nu,t}$ is a finite sum of convergent sequences, so $X_{\xi,t}\to X_{\xi,\infty}:= \sum_{\nu} w_{\nu} X_{\nu,\infty}< \infty$ $\mu^{\pi}$-a.s., with $X_{\xi,\infty}\geq w_{\mu} > 0$.

</Solution>

## 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>

<Solution>

By [Exercise 0.1](#prob-factorization), $\nu^{\pi}(\aes'_{1:m}) = \pi(\aes'_{1:m}) \cdot \nu(\aes'_{1:m})$ and $\mu^{\pi}(\aes'_{1:m}) = \pi(\aes'_{1:m}) \cdot \mu(\aes'_{1:m})$. For any history $\aes'_{1:m}$ with $\mu^{\pi}(\aes'_{1:m}) > 0$, the policy factors cancel:

$$
\begin{aligned}\nu^{\pi}(\aes'_{1:m}) ~&=~ \frac{\nu^{\pi}(\aes'_{1:m})}{\mu^{\pi}(\aes'_{1:m})}\cdot \mu^{\pi}(\aes'_{1:m}) ~=~ \frac{\nu(\aes'_{1:m})}{\mu(\aes'_{1:m})}\cdot \mu^{\pi}(\aes'_{1:m}) \\ ~&=~ X_{\nu,m}(\aes'_{1:m}) \cdot \mu^{\pi}(\aes'_{1:m}).\end{aligned}
$$

For histories with $\mu^{\pi}(\aes'_{1:m}) = 0$: since $\mu^{\pi} = \pi \cdot \mu$, some $\pi(a_{k} \mid \aes'_{<k}) = 0$, which forces $\nu^{\pi}(\aes'_{1:m}) = 0$ too (the same $\pi$-factor appears in $\nu^{\pi} = \pi \cdot \nu$). So both sides are zero.

Summing over $\aes'_{1:m}\in A$:

$$
\begin{aligned}\nu^{\pi}[\aes_{1:m}\in A] ~&=~ \sum_{\aes'_{1:m} \in A}\nu^{\pi}(\aes'_{1:m}) ~=~ \sum_{\aes'_{1:m} \in A}X_{\nu,m}(\aes'_{1:m}) \cdot \mu^{\pi}(\aes'_{1:m}) \\ ~&=~ \Ex_{\mu^\pi}\big[X_{\nu,m}\cdot \llbracket \aes_{1:m}\in A \rrbracket\big].\end{aligned}
$$

</Solution>

<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>

<Solution>

Let $E_{\varepsilon} := E \cap \{X_{\nu,\infty}\geq \varepsilon\}$. On $E_{\varepsilon}$, $X_{\nu,\infty}\geq \varepsilon$, so pointwise

$$
X_{\nu,\infty}\cdot \llbracket \aes_{1:\infty}\in E_{\varepsilon} \rrbracket ~\geq~ \varepsilon \cdot \llbracket \aes_{1:\infty}\in E_{\varepsilon} \rrbracket.
$$

Take $\mu^{\pi}$-expectations and apply [Exercise 10.2](#prob-cm-extension):

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

Since $E_{\varepsilon} \subseteq E$, $\nu^{\pi}[E_{\varepsilon}] \leq \nu^{\pi}[E]$. Dividing by $\varepsilon$ gives $\mu^{\pi}[E_{\varepsilon}] \leq \nu^{\pi}[E]/\varepsilon$.

*Interpretation.* A likelihood ratio of at least $\varepsilon$ forces $\nu^{\pi}$ and $\mu^{\pi}$ measures of an event to be comparable: $\mu^{\pi}$ of the event can exceed $\nu^{\pi}$ of it only by the factor $1/\varepsilon$. In particular, if $\nu^{\pi}$ vanishes on $E$, so does $\mu^{\pi}$ on the part where the likelihood ratio stays bounded away from zero.

</Solution>

## 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>

<Solution>

We establish two inequalities and chain them.

*First inequality: isolate the $\mu$-term.* For each $\nu \in \cM$, the optimal value is at least the value of any policy: $V_{\nu}^{*}(\aes_{<t}) \geq V_{\nu}^{\pi_\xi^*}(\aes_{<t})$, so $V_{\nu}^{*} - V_{\nu}^{\pi_\xi^*}\geq 0$. Since the posterior weights $w(\nu \mid \aes_{<t}) \geq 0$, every term in $\sum_{\nu} w(\nu \mid \aes_{<t})[V_{\nu}^{*} - V_{\nu}^{\pi_\xi^*}]$ is non-negative. The $\mu$-term is one such term:

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

*Second inequality: replace $\pi_{\xi}^{*}$ with $\tilde\pi$.* By definition of the optimal value, $V_{\xi}^{*}(\aes_{<t}) \geq V_{\xi}^{\tilde\pi}(\aes_{<t})$. Expanding both sides using infinite-horizon linearity ([Exercise 4.2](#prob-linearity-inf), applied to the fixed policies $\pi_{\xi}^{*}$ and $\tilde\pi$):

$$
\begin{aligned}\sum_{\nu} w(\nu \mid \aes_{<t})\, V_{\nu}^{\pi_\xi^*}(\aes_{<t}) ~&=~ V_{\xi}^{*}(\aes_{<t}) ~\geq~ V_{\xi}^{\tilde\pi}(\aes_{<t}) \\ ~&=~ \sum_{\nu} w(\nu \mid \aes_{<t})\, V_{\nu}^{\tilde\pi}(\aes_{<t}).\end{aligned}
$$

Rearranging: $\sum_{\nu} w(\nu)[V_{\nu}^{*} - V_{\nu}^{\pi_\xi^*}] \leq \sum_{\nu} w(\nu)[V_{\nu}^{*} - V_{\nu}^{\tilde\pi}] = \sum_{\nu} w(\nu)\, \delta_{\nu,t}$.

*Chaining:*

$$
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}.
$$

</Solution>

<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>

<Solution>

From the posterior weight formula, dividing numerator and denominator by $\mu(\aes_{<t})$:

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

where $X_{\nu,t-1}$ and $X_{\xi,t-1}$ are evaluated at the length-$(t{-}1)$ history $\aes_{<t}$.

If $X_{\nu,\infty}= 0$, then $X_{\nu,t-1}\to 0$ $\mu^{\pi}$-a.s. ([Exercise 9.2](#prob-x-converges)). Since $X_{\xi,t-1}\geq w_{\mu} > 0$ always ([Exercise 9.3](#prob-x-bounded-mu)), the ratio $w(\nu \mid \aes_{<t}) = w_{\nu} X_{\nu,t-1}/X_{\xi,t-1}\to 0$ $\mu^{\pi}$-a.s.

</Solution>

<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>

<Solution>

*Step 1: $F$ is $\nu^{\pi}$-null.* By the self-optimizing assumption ([Definition 9.1](#def-selfopt)), under $\nu^{\pi}$ the suboptimality gap $\delta_{\nu,t}$ vanishes, so $\nu^{\pi}[F] = 0$.

*Step 2: Apply [Exercise 10.3](#prob-markov-cm).* For each $n \geq 1$, take $E = F$ and $\varepsilon = 1/n$:

$$
\mu^{\pi}\!\big[F \cap \{X_{\nu,\infty}\geq 1/n\}\big] ~\leq~ \frac{\nu^{\pi}[F]}{1/n}~=~ 0.
$$

*Step 3: Countable union.* The level sets of $X_{\nu,\infty}$ form a nested increasing family: $\{X_{\nu,\infty}> 0\} = \bigcup_{n \geq 1}\{X_{\nu,\infty}\geq 1/n\}$. Intersecting with $F$ gives $F \cap \{X_{\nu,\infty}> 0\} = \bigcup_{n \geq 1}\big(F \cap \{X_{\nu,\infty}\geq 1/n\}\big)$, a countable union. By countable subadditivity ([Definition 7.1](#def-events)):

$$
\begin{aligned}\mu^{\pi}\!\big[F \cap \{X_{\nu,\infty}> 0\}\big] ~=~&\mu^{\pi}\!\Big[\textstyle\bigcup_{n}F \cap \{X_{\nu,\infty}\geq 1/n\}\Big] \\ ~\leq~ \sum_{n \geq 1}\,&\mu^{\pi}\!\big[F \cap \{X_{\nu,\infty}\geq 1/n\}\big] ~=~ 0.\end{aligned}
$$

*What this says.* "$\delta_{\nu,t}\to 0$ $\mu^{\pi}$-a.s. on $\{X_{\nu,\infty}> 0\}$" is shorthand for exactly this event statement: among infinite histories on which the likelihood ratio stays bounded away from zero, all but a $\mu^{\pi}$-null subset are ones where $\delta_{\nu,t}(\aes_{<t}) \to 0$. We do *not* claim convergence on histories where $X_{\nu,\infty}= 0$: that case is handled separately in [Exercise 11.2](#prob-vanishing-posterior) via the posterior weight.

</Solution>

<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>

<Solution>

Fix $\nu \in \cM$. We show $w(\nu \mid \aes_{<t})\, \delta_{\nu,t}\to 0$ $\mu^{\pi}$-a.s. by considering two exhaustive cases:

*Case 1: $X_{\nu,\infty}= 0$.* By [Exercise 11.2](#prob-vanishing-posterior), $w(\nu \mid \aes_{<t}) \to 0$. Since $\delta_{\nu,t}\in [0,1]$ ([Exercise 1.3](#prob-bounded-value)), the product $w(\nu \mid \aes_{<t}) \cdot \delta_{\nu,t}\leq 1 \cdot w(\nu \mid \aes_{<t}) \to 0$.

*Case 2: $X_{\nu,\infty}> 0$.* By [Exercise 11.3](#prob-delta-transfer), $\delta_{\nu,t}\to 0$. Since $w(\nu \mid \aes_{<t}) \leq 1$ (posterior weights are at most 1), the product $w(\nu \mid \aes_{<t}) \cdot \delta_{\nu,t}\leq 1 \cdot \delta_{\nu,t}\to 0$.

These two cases cover all infinite histories ($\mu^{\pi}$-a.s.), so $w(\nu \mid \aes_{<t})\, \delta_{\nu,t}\to 0$ $\mu^{\pi}$-a.s.

</Solution>

<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>

<Solution>

Since $\cM = \{\nu_{1}, \ldots, \nu_{N}\}$ is finite, we can sum [Exercise 11.4](#prob-single-term) over all $\nu \in \cM$:

$$
\sum_{\nu \in \cM}w(\nu \mid \aes_{<t})\, \delta_{\nu,t}~\longrightarrow~ 0 \qquad \mu^{\pi}\text{-a.s.}
$$

From [Exercise 11.1](#prob-chain-ineq):

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

So $w(\mu \mid \aes_{<t})[V_{\mu}^{*} - V_{\mu}^{\pi_\xi^*}] \to 0$ $\mu^{\pi}$-a.s.

It remains to divide by $w(\mu \mid \aes_{<t})$. From [Exercise 9.3](#prob-x-bounded-mu):

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

Fix an infinite history outside the (single) $\mu^{\pi}$-null set on which $X_{\xi,t}\to X_{\xi,\infty}< \infty$ fails. Along this history:

- $X_{\xi,t-1}\to X_{\xi,\infty}$, a finite positive number (with $X_{\xi,\infty}\geq w_{\mu} > 0$ by [Exercise 9.3](#prob-x-bounded-mu)).
- Hence $w(\mu \mid \aes_{<t}) = w_{\mu} / X_{\xi,t-1}\to w_{\mu} / X_{\xi,\infty}> 0$, so eventually $w(\mu \mid \aes_{<t}) \geq w_{\mu} / (2 X_{\xi,\infty}) > 0$.

Dividing the convergence $w(\mu \mid \aes_{<t}) (V_{\mu}^{*} - V_{\mu}^{\pi_\xi^*}) \to 0$ by this positive (per-history) lower bound, and using $V_{\mu}^{*} - V_{\mu}^{\pi_\xi^*}\geq 0$:

$$
V_{\mu}^{*}(\aes_{<t}) - V_{\mu}^{\pi_\xi^*}(\aes_{<t}) ~\longrightarrow~ 0 \qquad \mu^{\pi}\text{-a.s.}
$$

This completes the proof of [Theorem 9.2](#thm-selfopt).

</Solution>

*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).

## 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.

Problems marked **($\ast$)** are enrichment: they are off the critical path to the three main results ([Theorem 7.6](#thm-on-policy), [Theorem 8.1](#thm-cant-be-fooled), [Theorem 9.2](#thm-selfopt)) and can be skipped on a first pass without loss of continuity.

## 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.