Epistemic status: This first collaboration between Daniel Chiang (who is interested in the algorithmic information theory of incrementally constructed representations) and myself (Cole Wyeth) contains some fairly simple but elegant results that help illustrate differences between ordinary and reflective Oracle Solomonoff Induction.

Practical reasoning relies on context-specific prediction rules, which can be described as "incomplete models" or "partial experts." One simple example is "sleeping experts" which make predictions only at certain times (when they are "awake"), discussed here: https://www.lesswrong.com/posts/CGzAu8F3fii7gdgMC/a-simple-explanation-of-incomplete-models

Can Solomonoff's universal distribution take advantage of sleeping experts? We argue that the ordinary universal distribution has only a weak version of this property, while reflective Oracle Solomonoff Induction (rOSI) is perfectly capable of representing sleeping experts.

Note on inequalities: Globally assume that $\stackrel{+}{\le }$ is up to a small additive constant independent of all measures and sequences but possibly depending on the choice of UTM.  

Independent Sub-Environments with M

We first prove a simple lemma which we call "modular loss bound" for the ordinary universal distribution $M\left(x\right)$ where $x$ is a binary string. The rough idea is that if we have a true environment $\mu \left(x\right)$, while $\nu \left(x\right)$ is a simpler environment which agrees with $\mu \left(x\right)$ on the first $n$ bits, then we should we be able to bound the KL divergence between $\mu \left(x\right)$ and $M\left(x\right)$ for the first $n$ bits using $K\left(\nu \right)$, since both environments have identical behavior on the first $n$ bits. Let $M$ be the set of lower semicomputable semimeasures.

Lemma 1 (Modular loss bound): Denote $D_n={\sum }_{t=1}^n{E}_{\mu }\left[d_t\right(\cdot \left)\right]$ where $d_t\left(x_{<t}\right):={\sum }_{x_t\in X}\mu \left(x_t|x_{<t}\right)\ln \left(\frac{\mu \left(x_t|x_{<t}\right)}{M\left(x_t|x_{<t}\right)}\right)$ as the KL divergence between $\mu \left(x\right)$ and $M\left(x\right)$ for the first $n$ bits, let $M_{\mu }^n=\{\nu \in M|\forall x_{1:n}\in B^n,\nu (x_{1:n})=\mu (x_{1:n}\left)\right\}$  and $\nu =\underset{{\nu }^{\prime }\in M_{\mu }^n}{\text{argmin}}K\left({\nu }^{\prime }\right)$, then we have $D_n\le ln\left(2\right)K\left(\nu \right)$ with $K\left(\nu \right)\le K\left(\mu \right)$ by definition.

Proof:

Define $\xi \left(x\right)={\sum }_{\nu \in M}{2}^{-K\left(\nu \right)}\nu \left(x\right)$

By universality, we have

$M\left(x\right)\stackrel{\times }{=}\xi \left(x\right)\ge 2^{-K\left(\nu \right)}\nu \left(x\right)$$⟹ln\frac{\nu \left(x\right)}{M\left(x\right)}\le ln\left(2\right)K\left(\nu \right)$

The first equality can be made exact to avoid introducing an additive constant on the right. This is possible by e.g. Sterkenberg's "Universal Prediction" Theorem 2.16. or slightly less rigorous but self-contained https://arxiv.org/abs/1111.3854. Unfortunately that result is high context; a casual reader who still wants a rigorous proof can simply substitute $\xi$ for $M$ in our theorem statement and proof then proceed.

From the assumption $\nu \in M_{\mu }^n$, we have $\mu \left(x_{1:n}\right)=\nu \left(x_{1:n}\right)$, using the telescoping property of KL divergence, we get:

$D_n={\sum }_{t=1}^n{E}_{\mu }\left[d_t\right(\cdot \left)\right]={\sum }_{x_{1:n}}\mu \left(x_{1:n}\right)ln\frac{\mu \left(x_{1:n}\right)}{M\left(x_{1:n}\right)}$

$={\sum }_{x_{1:n}}\mu \left(x_{1:n}\right)ln\frac{\nu \left(x_{1:n}\right)}{M\left(x_{1:n}\right)}\le {\sum }_{x_{1:n}}\mu \left(x_{1:n}\right)ln\left(2\right)K\left(\nu \right)$

$=ln\left(2\right)K\left(\nu \right)$

with $K\left(\nu \right)\le K\left(\mu \right)$ by definition
 

Note that we can swap $\nu$ with any other ${\nu }^{\prime }\in M_{\mu }^n$ , with $\nu$ giving us the optimal bound.

QED

We now consider the scenario where we have a sequence of independent sub-environments ${\nu }_1,...{\nu }_k$ where we switch to the next sub-environment only at particular time-indices. By constructing an environment ${\nu }^{\ast }$ that implements the switching of sub-environments, we can obtain a modular loss bound based on the kolmogorov complexity of the sequence and all of the sub environments

Proposition 2 (Modular loss bound for independent sub-environments):

Let $0=t_0<t_1<..<t_k$ be a sequence of index and r be the K complexity of the sequence,  let ${\nu }_1...{\nu }_k\in M$ be a a sequence of environments, we can construct an environment ${\nu }^{\ast }$  such that for $t_j<n\le t_{j+1}$  we have ${\nu }^{\ast }\left(x_{1:n}\right)={\nu }_j\left(x_{t_j:n}\right){\Pi }_{i=1}^{j-1}{\nu }_i\left(x_{t_{i-1}:t_i}\right)$. Then, for all environments $\mu$ that agree with ${\nu }^{\ast }$ for the first $n$ bits, we have $D_n\stackrel{+}{\le }ln\left(2\right)(r+{\sum }_{i=1}^{k}K({\nu }_i\left)\right)$ where $D_n$ is the KL divergence between $\mu \left(x\right)$ and  $M\left(x\right)$. 

Proof
We have $K\left({\nu }^{\ast }\right)\le r+{\sum }_{i=1}^{k}K\left({\nu }_i\right)$ since we can construct ${\nu }^{\ast }$ by first computing the time indices, then implement switching of each of the sub-environments ${\nu }_i$. Then, for all true environments $\mu s.t.{\nu }^{\ast }\in M_{\mu }^n,K\left(\mu \right)\ge K\left({\nu }^{\ast }\right)$ , we have

$D_n={\sum }_{x_{1:n}}\mu \left(x_{1:n}\right)ln\frac{\mu \left(x_{1:n}\right)}{M\left(x_{1:n}\right)}$

$={\sum }_{x_{1:n}}\mu \left(x_{1:n}\right)ln\frac{{\nu }^{\ast }\left(x_{1:n}\right)}{M\left(x_{1:n}\right)}$

$\le {\sum }_{x_{1:n}}\mu \left(x_{1:n}\right)ln\left(2\right)K\left({\nu }^{\ast }\right)=ln\left(2\right)K\left({\nu }^{\ast }\right)$

$\stackrel{+}{\le }ln\left(2\right)(r+{\sum }_{i=1}^{k}K({\nu }_i\left)\right)$

QED

Note: Setting some ${\nu }_j=M$ for $j>1$ indicates a kind of fractal structure of $M$ at simple indices.

Sleeping Experts with rOSI

There is a similar modular loss bound for rOSI, but now we are able to condition the "experts" that predict each segment of the sequence on the entire previous sequence, because the class  $M_{\text{refl}}^O$ of reflective oracle computable (rO-computable) measures is constructed in terms of Markov kernels, not joint distributions. Let ${\xi }^O\stackrel{\times }{\ge }{M}_{\text{refl}}^O$ be a universal "mixture" in the class constructed as in Algorithm 1 of "Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games" with the prior weight $w_{\nu }:=2^{-K\left(\nu \right)}$.

Proposition 3 (Modular loss bound for rO-computable sub-environments):

Let $0=t_0<t_1<..<t_k$ be a sequence of indices and r be the K complexity of the sequence,  let ${\nu }_1...{\nu }_k\in M_{\text{refl}}^O$ be a a sequence of environments, we can construct an environment ${\nu }^{\ast }$  such that for $t_j<n\le t_{j+1}$  we have ${\nu }^{\ast }\left(x_n|x_{<n}\right)={\nu }_j\left(x_n|x_{<n}\right)$. Then, for all environments $\mu$ that agree with ${\nu }^{\ast }$ for the first $n$ bits, we have $D_n\stackrel{+}{\le }ln\left(2\right)(r+{\sum }_{i=1}^{k}K({\nu }_i\left)\right)$ where $D_n$ is the KL divergence of ${\xi }^O$ from $\mu$ on the first $n$ bits.  

Proof: Unchanged from above.

If we do not wish to make any assumptions about a "true" environment $\mu$, it is also possible to bound the surprisal of $\xi$ on an arbitrary prefix $x_{1:n}$ by the cumulative surprisals ($-\lg$ loss) of ${\nu }_1...{\nu }_k$ along with Kolmogorov complexity terms as above. This is more in the spirit of prediction with expert advice. Note that we do not assume anything about a "true environment" $\mu$ in the following:

Proposition 4 (Uniform loss bound against rO-computable sleeping experts):

Let $0=t_0<t_1<..<t_k$ be a sequence of indices and r be the K complexity of the sequence,  let ${\nu }_1...{\nu }_k\in M_{\text{refl}}^O$ be a a sequence of environments. Then

$-\lg {\xi }^O\left(x_{1:n}\right)\stackrel{+}{\le }r+{\sum }_{i=1}^{k}K\left({\nu }_i\right)+{\sum }_{j=1}^k{\sum }_{n=t_{j-1}}^{t_j}(-\lg {\nu }_j(x_n|x_{<n}\left)\right)$  

where the additive constant is independent of the sequence $t_j$ and measures ${\nu }_j$. 

Proof: Simply note that ${\xi }^O\ge 2^{-K\left({\nu }^{\ast }\right)}{\nu }^{\ast }$, take $-\lg \left(\right)$ of both sides and expand. 

A version of Proposition 4 for an infinite but algorithmically simple sequence of switches between experts is an easy extension. Though we have not explicitly proved that ordinary Solomonoff induction fails to satisfy any of these properties, the negative results in "Universal Prediction of Selected Bits" indicate that it at least does not satisfy the infinite switching extension. 

Future work: An alternative proof by a market metaphor should be accessible by adapting a result of @SamEisenstat.