This is joint work by Vanessa Kosoy and Alexander "Diffractor" Appel. For the proofs, see 1 and 2.

TLDR: We present a new formal decision theory that realizes naturalized induction. Our agents reason in terms of infra-Bayesian hypotheses, the domain of which is the cartesian product of computations and physical states, where the ontology of "physical states" may vary from one hypothesis to another. The key mathematical building block is the "bridge transform", which, given such a hypothesis, extends its domain to "physically manifest facts about computations". Roughly speaking, the bridge transforms determines which computations are executed by the physical universe. In particular, this allows "locating the agent in the universe" by determining on which inputs its own source is executed.

0. Background

The "standard model" of ideal agency is Bayesian reinforcement learning, and more specifically, AIXI. We challenged this model before due to its problems with non-realizability, suggesting infra-Bayesianism as an alternative. Both formalisms assume the "cartesian cybernetic framework", in which (i) the universe is crisply divided into "agent" and "environment" and (ii) the two parts interact solely via the agent producing actions which influence the environment and the environment producing observations for the agent. This is already somewhat objectionable on the grounds that this division is not a clearly well-defined property of the physical universe. Moreover, once we examine the structure of the hypothesis such an agent is expected to learn (at least naively), we run into some concrete problems.

The modern understanding of the universe is that no observer plays a privileged role^[1]. Therefore, the laws of physics are insufficient to provide a cartesian description of the universe, and must, to this end, be supplemented with "bridge rules" that specify the agent's location inside the universe. That is, these bridge rules need to translate the fundamental degrees of freedom of a physical theory (e.g. quantum wavefunction) to the agent's observations (e.g. values of pixels on a camera), and translate the agent's actions (e.g. signal to robot manipulators) in the other direction^[2]. The cost of this is considerable growth in the description complexity of the hypothesis.

A possible retort is something like "how many bits can it really take to pick out the computer within the universe state and describe how to translate universe state to observations? Sure, it might be a considerable chunk of data. But, since Solomonoff induction only needs to make a kilobyte worth of predictive mistakes to learn to predict the inputs as well as any thousand-bit predictor, it should learn this sort of stuff pretty fast." This objection is addressed more later on in this post. A first counter-objection is that, for practical algorithms, this can be a bigger obstacle, especially when sample complexity scales superlinearly with description complexity. For example, the Russo-Van Roy regret bound for Thompson sampling in multi-armed bandits has the time horizon necessary to get a particular regret bound scale as the square of entropy, and the computational complexity cost can also go way up as the description complexity rises, because you need to evaluate more hypotheses more times to test them. For reinforcement learning it's even worse, as in the case of a game where an agent must enter an n-digit password and if it gets it right, it gets reward, and if it gets it wrong, it does not get reward and can try again. The learning time for this game scales as $\Omega \left(2^n\right)$, far superlinearly with description complexity.

Another assumption of AIXI is the simplicity prior, and we expect some form of this assumption to persist in computable and infra-Bayesian analogues. This reflects the intuitive idea that we expect the world to follow simple laws (or at least contain simple patterns). However, from the cartesian perspective, the "world" (i.e. the environment) is, prima facie, not simple at all (because of bridge rules)! Admittedly, the increase in complexity from the bridge rule is low compared to the cost of specifying the universe state, but once the agent learns the transition rules and bridge rule for the universe it's in, learning the state of the universe in addition doesn't seem to yield any particular unforeseen metaphysical difficulties. Further, the description complexity cost of the bridge rule seems likely to be above the description complexity of the laws of physics.

Hence, there is some disconnect between the motivation for using a simplicity prior and its implementation in a cartesian framework.

Moreover, if the true hypothesis is highly complex, it implies that the sample complexity of learning it is very high. And, as previously mentioned, the sample complexity issues are worse in practice than Solomonoff suggests. This should make us suspect that such a learning process is not properly exploiting Occam's razor. Intuitively, such an agent a-priori considers it equally plausible to discover itself to be a robot or to discover itself to be a random clump of dust in outer space, since it's about as hard to specify a bridge rule interface between the computer and observations as it is to specify a bridge rule interface between the dust clump and observations and needs a lot of data to resolve all those possibilities for how its observations connect to a world. Also, though Solomonoff is extremely effective at slicing through the vast field of junk hypotheses that do not describe the thing being predicted, once it's whittled things down to a small core of hypotheses that do predict things fairly accurately, the data to further distinguish between them may be fairly slow in coming. If there's a simple predictor of events occurring in the world but it's running malign computation, then you don't have the luxury of 500 bits of complexity wiggle room (to quickly knock out this hypothesis), because that's a factor of $2^{500}$ probability difference. Doing worst-case hypothesis testing as in KWIK learning would require a very aggressive threshold indeed, and mispredictions can be rare but important.

Furthermore, some events are simple to describe from the subjective (cartesian) point of view, but complex to describe from an objective (physical) point of view. (For example, all the pixels of the camera becoming black.) Modifying a hypothesis by positing exceptional behavior following a simple event only increases its complexity by the difficulty of specifying the event and what occurs afterwards, which could be quite low. Hence, AIXI-like agents would have high uncertainty about the consequences of observationally simple events. On the other hand, from an objective perspective such uncertainty seems irrational. (Throwing a towel on the camera should not break physics.) In other words, cartesian reasoning is biased to privilege the observer.

Yet another failure of cartesian agents is the inability to reason about origin theories. When we learn that a particular theory explains our own existence (e.g. evolution), this serves as a mark in favor of the theory. We can then exploit this theory to make useful predictions or plans (e.g. anticipate that using lots of antibiotics will cause bacteria to develop resistance). However, for a cartesian agent the question of origins is meaningless. Such an agent perceives its own existence as axiomatic, hence there is nothing to explain.

Finally, cartesian agents are especially vulnerable to acausal attacks. Suppose we deploy a superintelligent Cartesian AI called Kappa. And, imagine a superintelligent agent Mu that inhabits some purely hypothetical universe. If Mu is motivated to affect our own (real) universe, it can run simulations of Kappa's environment. Kappa, who doesn't know a priori whether it exists in our universe or in Mu's universe, will have to seriously consider the hypothesis it is inside such a simulation. And, Mu will deploy the simulation in such manner as to make the simulation hypothesis much simpler, thanks to simpler bridge rules. This will cause Kappa to become overwhelmingly confident that it is in a simulation. If this is achieved, Mu can cause the simulation to diverge from our reality in a strategically chosen point such that Kappa is induced to take an irreversible action in Mu's favor (effectively a treacherous turn). Of course, this requires Kappa to predict Mu's motivations in some detail. This is possible if Kappa develops a good enough understanding of metacosmology.

An upcoming post by Diffractor will discuss acausal attacks in more detail.

In the following sections, we will develop a "physicalist" formalism that entirely replaces the cartesian framework, curing the abovementioned ills, though we have not yet attained the stage of proving improved regret bounds with it, just getting the basic mathematical properties of it nailed down. As an additional benefit, it allows naturally incorporating utility functions that depend on unobservables, thereby avoiding the problem of "ontological crises". At the same time, it seems to impose some odd constraints on the utility function. We discuss the possible interpretations of this.

1. Formalism

Notation

It will be more convenient to use ultradistributions rather than infradistributions. This is a purely notational choice: the decision theory is unaffected, since we are going to apply these ultradistributions to loss functions rather than utility functions. As support for this claim, Diffractor originally wrote down most of the proofs in infradistribution form, and then changing their form for this post was rather straightforward to do. In addition, for the sake of simplicity, we will stick to finite sets: more general spaces will be treated in a future article. So far, we're up to countable products of finite sets.

We denote $R_{+}:=[0,\infty )$. Given a finite set $X$, a contribution on $X$ is $\theta :X\to R_{+}$ s.t. ${\sum }_x\theta \left(x\right)\le 1$ (it's best to regard it as a measure on $X$). The space of contributions is denoted ${\Delta }^{c}X$. Given $f:X\to R$ and $\theta \in {\Delta }^{c}X$, we denote $\theta \left(f\right):={\sum }_x\theta \left(x\right)f\left(x\right)$. There is a natural partial order on contributions: ${\theta }_1\le {\theta }_2$ when $\forall x\in X:{\theta }_1\left(x\right)\le {\theta }_2\left(x\right)$. Naturally, any distribution is in particular a contribution, so $\Delta X\subseteq {\Delta }^{c}X$. A homogenous ultracontribution (HUC) on $X$ is non-empty closed convex $\Theta \subseteq {\Delta }^{c}X$ which is downward closed w.r.t. the partial order on ${\Delta }^{c}X$. The space of HUCs on $X$ is denoted ${\square }^{c}X$. A homogenous ultradistribution (HUD) on $X$ is a HUC $\Theta$ s.t. $\Theta \cap \Delta X\ne \varnothing$. The space of HUDs on $X$ is denoted $\square X$. Given $f:X\to R$ and $\Theta \in {\square }^{c}X$, we denote $\Theta \left(f\right):={max}_{\theta \in \Theta }\theta \left(f\right)$.

Given $s:X\to Y$, $s_{\ast }:{\square }^{c}X\to {\square }^{c}Y$ is the pushforward by $s$:

$$s_{\ast }\Theta :=\{s_{\ast }\theta \mid \theta \in \Theta \}$$

$$\left(s_{\ast }\theta \right)\left(y\right):=\sum _{x\in s^{-1}\left(y\right)}\theta \left(x\right)$$

Given $\Xi :X\to {\square }^{c}Y$, ${\Xi }_{\ast }:{\square }^{c}X\to {\square }^{c}Y$ is the pushforward by $\Xi$:

$${\Xi }_{\ast }\Theta :=\{{\kappa }_{\ast }\theta \mid \theta \in \Theta ,\kappa :X\to {\Delta }^{c}Y,\forall x\in X:\kappa (x)\in \Xi (x\left)\right\}$$

$$\left({\kappa }_{\ast }\theta \right)\left(y\right):=\sum _{x\in X}\theta \left(x\right)\kappa (x;y)$$

${pr}_X:X\times Y\to X$ is the projection mapping and ${pr}_{-Y}:={pr}_X$. We slightly abuse notation by omitting the asterisk in pushforwards by these.

Given $\Theta \in {\square }^{c}X$ and $\Xi :X\to {\square }^{c}Y$, $\Theta ⋉\Xi \in {\square }^c(X\times Y)$ is the semidirect product:

$$\Theta ⋉\Xi :=\{\kappa ⋉\theta \mid \theta \in \Theta ,\kappa :X\to {\Delta }^{c}Y,\forall x\in X:\kappa (x)\in \Xi (x\left)\right\}$$

$$(\kappa ⋉\theta )(x,y):=\theta \left(x\right)\kappa (x;y)$$

We will also use the notation $\Xi ⋊\Theta \in {\square }^c(Y\times X)$ for the same HUC with $X$ and $Y$ flipped. And, for $\Lambda \in {\square }^{c}Y$, $\Theta ⋉\Lambda \in {\square }^c(X\times Y)$ is the semidirect product of $\Theta$ with the constant ultrakernel whose value is $\Lambda$^[3].

For more discussion of HUDs, see previous article, where we used the equivalent concept of "cohomogenous infradistribution".

Notation Reference

If you got lost somewhere and wanted to scroll back to see some definition, or see how the dual form of this with infradistributions works, that's what this section is for.

$\theta$ is a contribution, a measure with 1 or less measure in total. The dual concept is an a-measure $(\lambda \mu ,b)$ with $\lambda +b=1$.

$\Theta$ is a HUC (homogenous ultracontribution) or HUD (homogenous ultradistribution), a closed convex downwards closed set of contributions. The dual concepts are cohomogenous inframeasure and cohomogenous infradistribution, respectively.

${\Delta }^{c}X,{\square }^{c}X,\square X$ are the spaces of contributions, homogenous ultracontributions, and homogenous ultradistributions respectively.

$\theta \left(f\right),\Theta \left(f\right)$ are the expectations of functions $f:X\to [0,1]$, defined in the usual way. For $\theta$, it's just the expectation of a function w.r.t. a measure, and for $\Theta$, it's $\Theta \left(f\right):={max}_{\theta \in \Theta }\theta \left(f\right)$, to perfectly parallel a-measures evaluating functions by just taking expectation, and inframeasures evaluating functions via ${min}_{(m,b)\in \Psi }m\left(f\right)+b$.

$\le$ is the ordering on contributions/HUC's/HUD's, which is the function ordering, where $\theta \le {\theta }^{\prime }$ iff for all $f:X\to [0,1]$, $\theta \left(f\right)\le {\theta }^{\prime }\left(f\right)$, and similar for the HUC's. Inframeasures are equipped with the opposite ordering.

$s_{\ast }\Theta$ is the pushforward along the function $s:X\to Y$. This is a standard probability theory concept which generalizes to all the infra and ultra stuff.

${\Xi }_{\ast }\Theta$ is the pushforward of $\Theta$ along the ultrakernel $\Xi :X\to {\square }^{c}Y$. This is just the generalization to infra and ultra stuff of the ability to push a probability distribution on $X$ through a probabilistic function $X\to \Delta Y$ to get a probability distribution on $Y$.

$\Theta ⋉\Xi$ is the semidirect product of $\Theta$ and $\Xi$, an element of ${\square }^c(X\times Y)$. This is the generalization of the ability to take a probability distribution on $X$, and a probabilistic kernel $X\to \Delta Y$, and get a joint distribution on $X\times Y$.

$A,O$ are the set of actions and observations.

$N$ is the time horizon.

$R$ is the space of programs, $\Sigma$ is the space of outputs.

$\Gamma ={\Sigma }^R$ is the space of functions from programs to the results they output. An element of $\Gamma$ can be thought of as the state of the "computational universe", for it specifies what all the programs do.

$H$ is the space of histories, action-observation sequences that can end at any point, ending with an observation.

$D$ is the space of destinies, action-observation sequences that are as long as possible, going up to the time horizon.

$C$ is a relation on $\Gamma \times D$ that says whether a computational universe is consistent with a given destiny. A very important note is that this is not the same thing as "the policy is consistent with the destiny" (the policy's actions are the same as what the destiny advises). This is saying something more like "if the destiny has an observation that the computer spat out result 1 when run on computation A, then that is only consistent with mathematical universes which have computation A outputting result 1". Except we don't want to commit to the exact implementation details of it, so we're leaving it undefined besides just "it's a relation"

$\Phi$ is the space of "physics outcomes", it can freely vary depending on the hypothesis. It's not a particular fixed space.

$\Theta$ is the variable typically used for physicalist hypotheses, elements of $\square (\Gamma \times \Phi )$. Your uncertainty over the joint distribution over the computational universe and the physical universe.

$G$ is the code of the program-which-is-the-agent. So, $G\left(h\right)$ would be the computation that runs what the agent does on history $h$, and returns its resulting action.

${\text{el}}^{\Gamma }$ is the subset of the space $\Gamma \times 2^{\Gamma }$ consisting of $(y,\alpha )$ pairs s.t. $y\in \alpha$. The $y$ can be thought of as the mathematical universe, and $\alpha$ can be thought of as the set of mathematical universes that are observationally indistinguishable from it.

${\chi }_A$ is the indicator function that's 1 on the set $A$, and 0 everywhere else. It can be multiplied by a measure, to get the restriction of a measure to a particular set.

$\text{Br}\left(\Theta \right)$ is the bridge transform of $\Theta$, defined in definition 1.1, an ultracontribution over the space ${\text{el}}^{\Gamma }\times \Phi$.

$H_{y\alpha }$ is the set of instantiated histories, relative to mathematical universe $y$, and set of observationally indistinguishable universes $\alpha$. It's the set of histories $h$ where all the "math universes" in $\alpha$ agree on how the agent's source code reacts to all the prefixes of $h$, and where the history $h$ can be extended to some destiny that's consistent with math universe $y$. Ie, for a history to be in here, all the prefixes have to be instantiated, and it must be consistent with the selected math universe.

Setting

As in the cartesian framework, we fix a finite set $A$ of actions and a finite set $O$ of observations. We assume everything happens within a fixed finite^[4] time horizon $N\in N.$ We assume that our agent has access to a computer^[5] on which it can execute some finite^[4:1] set of programs $R$ with outputs in a finite alphabet $\Sigma$. Let $\Gamma :={\Sigma }^R$ be the set of "possible computational universes"^[6]. We denote $H:=(A\times O{)}^{<N}$ (the set of histories) and $D:=(A\times O{)}^{N-1}\times A$ (the set of "destinies").

To abstract over the details of how the computer is operated, we assume a relation $C\subseteq D\times \Gamma$ whose semantics is, $dCy$ (our notation for $(d,y)\in C$) if and only if destiny $d$ is a priori consistent with computational universe $y$. For example, suppose some $a\in A$ implies a command to execute program $r\in R,$and if $o\in O$ follows $a$, it implies observing the computer return output $i\in \Sigma$ for $r$. Then, if $d$ contains the substring $ao$ and $dCy$, it must be the case that $y\left(r\right)=i$.

A physicalist hypothesis is a pair $(\Phi ,\Theta$), where $\Phi$ is a finite^[4:2] set representing the physical states of the universe and $\Theta \in \square (\Gamma \times \Phi )$ represents a joint belief about computations and physics. By slight abuse of notation we will refer to such $\Theta$ as a physicalist hypothesis, understanding $\Phi$ to be implicitly specified. Our agent will have a prior over such hypotheses, ranging over different $\Phi$.

Two questions stand out to us at this point. The first is, what is the domain over which our loss function should be defined? The second is, how do we define the counterfactuals corresponding to different policies $\pi :H\to A$? The answers to both questions turn out to require the same mathematical building block.

For the first question, we might be tempted to identify $\Phi$ as our domain. However, prima facie this doesn't make sense, since $\Phi$ is hypothesis-dependent. This is the ontological crisis problem: we expect the agent's values to be defined within a certain ontology which is not the best ontology for formulating the laws of the physical universe. For example, a paperclip maximizer might benefit from modeling the universe in terms of quantum fields rather than paperclips. In principle, we can circumvent this problem by requiring our $\Phi$ to be equipped with a mapping $\nu :\Phi \to {\Phi }_0,$where ${\Phi }_0$ is the "axiological" ontology. However, this $\nu$ is essentially a bridge rule, carrying with it all the problems of bridge rules: acausal attack is performed by the adversarial hypothesis imprinting the "axiological rendering" of the target universe on the microscopic degrees of freedom of the source universe in order to have a low-complexity $\Phi \to {\Phi }_0$ function; the analogue of the towel-on-camera issue is that, once you've already coded up your uncertainty over math and physics, along with how to translate from physics to the ontology of value, it doesn't take too much extra complexity to tie "axiologically-simple" results (the analogue of low-complexity observations) to physics-simple results (the analogue of a low-complexity change in what happens), like "if all the paperclips are red, the fine-structure constant doubles in value".

Instead, we will take a computationalist stance: value is a not property of physical states or processes, but of the computations realized by physical processes. For example, if our agent is "selfish" in the sense that, rewards/losses are associated purely with subjective histories, the relevant computation is the agent's own source code. Notice that, for the program-which-is-the-agent $G$, histories are input. Hence, given loss function $l:H\to R$ we can associate the loss $l\left(h\right)$ with the computation $G\left(h\right)$. Admittedly, there is an implicit assumption that the agent has access to its own source code, but modal decision theory made the same assumption. For another example, if our agent is a diamond maximizer, then the relevant computations are simulations of the physics used to define "diamonds". A more concrete analogue of this is worked out in detail in section 3, regarding Conway's Game of Life.

For the second question, we might be tempted to follow updateless decision theory: counterfactuals correspond to conditioning on $G=\pi$. Remember, G is the code of the agent. However, this is not "fair" since it requires the agent to be "responsible" for copies of itself instantiated with fake memories. Such a setting admits no learning-theoretic guarantees, since learning requires trusting your own memory. (Moreover, the agent also has to be able to trust the computer.) Therefore our counterfactuals should only impose $G\left(h\right)=\pi \left(h\right)$ when $h$ is a "real memory", which we against interpret through computationalism: $h$ is real if and only if, $G\left(h^{\prime }\right)$ is physically realized for any prefix $h^{\prime }$ of $h$.

Both of our answers requires a formalization of the notion "assuming hypothesis $\Theta$, this computation is physically realized". More precisely, we should allow for computations to be realized with certain probabilities, and more generally allow for ultradistributions over which computations are realized. We will now accomplish this formalization.

Bridge transform

Given any set $A$, we denote ${el}^A=\left\{\right(a,B)\in A\times 2^A\mid a\in B\}.$ $supp$ stands for "support" and ${\chi }_A$ is the characteristic function of $A$.

Definition 1.1: Let $\Gamma ,\Phi$ be finite sets and $\Theta \in {\square }^c(\Gamma \times \Phi )$. The bridge transform of $\Theta$ is ${Br}_{\Gamma }\left(\Theta \right)\in {\square }^c(\Gamma \times 2^{\Gamma }\times \Phi )$ s.t. $\theta \in {Br}_{\Gamma }\left(\Theta \right)$ if and only if

• $supp\theta \subseteq {el}^{\Gamma }\times \Phi$

• for any $s:\Gamma \to \Gamma$, ${pr}_{\Gamma \times \Phi }{\chi }_{{el}^{\Gamma }\times \Phi }(s\times {id}_{2^{\Gamma }\times \Phi }{)}_{\ast }\theta \in \Theta$.

We will use the notation $Br\left(\Theta \right)$ when $\Gamma$ is obvious from the context.

Notice that we are multiplying by ${\chi }_{{el}^{\Gamma }\times \Phi }$, not pushforwarding.

The $2^{\Gamma }$ variable of the bridge transform denotes the "facts about computations realized by physics". In particular, if this $\alpha \in 2^{\Gamma }$ takes the form $\{y\in \Gamma \mid \forall r\in R_0:y(r)=y_0(r\left)\right\}$ for some $R_0\subseteq R$ and $y_0\in {\Sigma }^{R_0}$, then we may say that the computations $R_0$ are "realized" and the computations $R\setminus R_0$ are "not realized". More generally, talking only about which computations are realized is imprecise since $\alpha$ might involve "partial realization" and/or "entanglement" between computations (i.e. not be of the form above).

Intuitively, this definition expresses that the "computational universe" can be freely modified as long as the "facts known by physics" are preserved. However, that isn't what originally motivated the definition. The bulk of its justification comes from its pleasing mathematical properties, discussed in the next section.

A physicalist agent should be equipped with a prior over physicalist hypotheses. For simplicity, suppose it's a discrete Bayesian prior (it is straightforward to generalize beyond this): hypothesis ${\Theta }_i$ is assigned probability $\zeta \left(i\right)$ and ${\sum }_i\zeta \left(i\right)=1$. Then, we can consider the total bridge transform of the prior. It can't be given by mixing the hypotheses together and applying the bridge transform, because every hypothesis has its own choice of $\Phi$, its own ontology, so you can't mix them before applying the bridge transform. You have to apply the bridge transform to each component first, forget about the choice of $\Phi$ via projecting it out, and then mix them afterwards. This receives further support from Proposition 2.13 which takes an alternate possible way of defining the bridge transform for mixtures (extend all the hypotheses from $\Gamma \times {\Phi }_i$ to $\Gamma \times {⨆}_i{\Phi }_i$ in the obvious way so you can mix them first) and shows that it produces the same result.

Definition 1.2: $$Br(\zeta ⋉\Theta ):=\sum _i\zeta \left(i\right){pr}_{{el}^{\Gamma }}Br\left({\Theta }_i\right)\in \square {el}^{\Gamma }$$

Evaluating policies

Given $A\subseteq X$, ${\top }_A\in \square X$ is defined as $\{\theta \in {\Delta }^{c}X\mid supp\theta \subseteq A\}$. I.e., it's total uncertainty over which point in $A$ will be selected.

We need to assume that $R$ contains programs representing the agent itself. That is, there is some $M\in N$, $dec:{\Sigma }^M\to A$ and for each $h\in H$, $┌G\left(h\right)┐\in R^M$. Pretty much, if you have large numbers of actions available, and a limited number of symbols in your language, actions (and the outputs of other programs with a rich space of outputs) can be represented be m-tuples of programs, like "what's the first bit of this action choice" and "what's the second bit of this action choice" and so on. So, $M$ is just how many bits you need, $dec$ is the mapping from program outputs to the actual action, and $┌G\left(h\right)┐$ is the m-tuple of of programs which implements the computation "what does my source code do on input history $h$". The behavior of the agent in a particular mathematical universe is given by taking each program in $┌G\left(h\right)┐$, using the mathematical universe to figure out what each of the programs outputs, and then using $dec$ to convert that bitstring to an action.

Definition 1.3: Given $y\in \Gamma$ and $h\in H$, we define $G^y\left(h\right)\in A$ to be $dec\left(a\right)$ for $a\in {\Sigma }^M$ given by $a_i:=y(┌G(h\left){┐}_i\right)$.

We can now extract counterfactuals from any $\Lambda \in \square {el}^{\Gamma }.$ Specifically, given any policy $\pi$ we define some $C^{\pi }\subseteq {el}^{\Gamma }$ (the set of stuff consistent with behaving according to $\pi$, for a yet-to-be-defined notion of consistency) and define the counterfactual as $\Lambda \cap {\top }_{C^{\pi }}$. We could use the "naive" definition:

Definition 1.4: $C_{naive}^{\pi }$ is the set of all $(y,\alpha )\in {el}^{\Gamma }$ s.t. for any $h\in H$, $G^y\left(h\right)=\pi \left(h\right)$.

Per discussion above, it seems better to use a different definition. We will use the notation $h⊏g$ to mean "$h$ is a proper prefix of $g$" and $h⊑g$ to mean "$h$ is a prefix of $g$",

Definition 1.5: Given $(y,\alpha )\in {el}^{\Gamma }$, let $H_{y\alpha }$ be the set of all $h\in H$ s.t. the following two conditions hold:

1. For all $ga\in H\times A$ and $y^{\prime }\in \Gamma$ where $ga⊏h$ and $y^{\prime }\in \alpha$, $G^{y^{\prime }}\left(g\right)=a$.

2. $h⊏d$ for some $d\in D$ s.t. $dCy$.

$C_{fair}^{\pi }$ is the set of all $(y,\alpha )\in {el}^{\Gamma }$ s.t. for any $h\in H_{y\alpha }$, $G^y\left(h\right)=\pi \left(h\right)$.

Here, condition 1 says that we only "take responsibility" for the action on a particular history when the history was actually observed (all preceding evaluations of the agent are realized computations). Condition 2 says that we only "take responsibility" when the computer is working correctly.

At this stage, Definition 1.5 should be regarded as tentative, since we only have one result so far that validates this definition, namely that the set of $(y,\alpha )$ in $C_{\text{fair}}^{\pi }$ only depends on what the policy $\pi$ does on possible inputs, instead of having the set depending on what the policy does on impossible inputs where one of the past memorized actions is not what the policy would actually do. We hope to rectify this in future articles.

Putting everything together: given a loss function $L:{el}^{\Gamma }\to R$, which depends on how the mathematical universe is, and which computations are realized or not-realized, the loss of policy $\pi$ is given by just applying the bridge transform to coax the hypotheses into the appropriate form, intersecting with the set of possibilities consistent with the agent behaving according to a policy, and evaluating the expectation of the loss function, as detailed below.

$$L^{\text{pol}}(\pi ,\zeta ):=\left(Br\right(\zeta ⋉\Theta )\cap {\top }_{C_{fair}^{\pi }})\left(L\right)$$

Evaluating agents

So far we regarded the agent's source code $G$ and the agent's policy $\pi$ as independent variables, and explained how to evaluate different policies given fixed $G$. However, in reality the policy is determined by the source code. Therefore, it is desirable to have a way to evaluate different codes. We achieve this using an algorithmic information theory approach.

We also want to allow the loss function to depend on $G$. That is, we postulate $L:(R^M{)}^H\times {el}^{\Gamma }\to R$. Specifically, since $R^M$ can be thought of as the space of actions, $(R^M{)}^H$ is basically the space of policies. In section 3 we will see why in some detail, but for now think of the difference between "maximizing my own happiness" and "maximizing Alice's happiness": the first is defined relative to the agent (depends on $G$) whereas the second is absolute (doesn't depend on $G$). In particular, for a selfish agent that just cares about its own observations, its loss function must reference its own source code.

Definition 1.6: Denote $G^{\ast }:H\to A$ the policy actually implemented by $G$. Fix $\xi \in \Delta (A^H$). The physicalist intelligence of $G$ relative to the baseline policy mixture $\xi$, prior $\zeta$ and loss function $L$ is defined by:

$$g(G\mid \xi ;\zeta ,L):=-\log {Pr}_{\pi \sim \xi }\left[L^{\text{pol}}\right(┌G┐,\pi ,\zeta )\le L^{\text{pol}}(┌G┐,G^{\ast },\zeta \left)\right]$$

Notice that $L^{\text{pol}}$ depends on $┌G┐$ in two ways: through the direct dependence of $L$ on $┌G┐$ and through $C_{fair}^{\pi }$.

In particular, it makes sense to choose $\zeta$ and $\xi$ as simplicity priors.

There is no obvious way to define "physicalist AIXI", since we cannot have $g=\infty$. For one thing, $g$ is not even defined for uncomputable agents. In principle we could define it for non-uniform agents, but then we get a fixpoint problem that doesn't obviously have a solution: finding a non-uniform agent $G$ s.t. $L^{\text{pol}}(┌G┐,G^{\ast },\zeta )={min}_{\pi }{L}^{\text{pol}}(┌G┐,\pi ,\zeta )$. On the other hand, once we spell out the infinitary ($N=\infty$) version of the formalism, it should be possible to prove the existence of agents with arbitrarily high finite $g$. That's because our agent can use quining to access its own source code $┌G┐$, and then brute force search a policy ${\pi }_{ϵ}^{\ast }$ with $L^{\text{pol}}(┌G┐,{\pi }_{ϵ}^{\ast },\zeta )<{inf}_{\pi :H\to A}{L}^{\text{pol}}(┌G┐,\pi ,\zeta )+ϵ$.

2. Properties of the bridge transform

In this section we will not need to assume $\Gamma$ is of the form ${\Sigma }^R$: unless stated otherwise, it will be any finite set.

Sanity test

Proposition 2.1: For any $\Gamma$, $\Phi$ and $\Theta \in {\square }^c(\Gamma \times \Phi )$, $Br\left(\Theta \right)$ exists and satisfies ${pr}_{\Gamma \times \Phi }Br\left(\Theta \right)=\Theta$. In particular, if $\Theta \in \square (\Gamma \times \Phi )$ then $Br\left(\Theta \right)\in \square ({el}^{\Gamma }\times \Phi )$.

Downwards closure

Roughly speaking, the bridge transform tell us which computations are physically realized. But actually it only bounds it from one side: some computations are definitely realized but any computation might be realized. One explanation for why it must be so is: if you looked at the world in more detail, you might realize that there are small-scale, previously invisible, features of the world which depend on novel computations. There is a direct tension between bounding both sides (i.e. being able to say definitively that a computation isn't instantiated) and having the desirable property that learning more about the small-scale structure of the universe narrows down the uncertainty. To formalize this, we require the following definitions:

Definition 2.1: Let $X$ be a partially ordered set (poset). Then the induced partial order on ${\Delta }^{c}X$ is defined as follows. Given $\theta ,\eta \in {\Delta }^{c}X$, $\theta ⪯\eta$ if and only if for any monotonically non-decreasing function $f:X\to R_{+}$, $\theta \left(f\right)\le \eta \left(f\right)$.

This is also called the stochastic order (which is standard mathematical terminology). Intuitively, $\theta ⪯\eta$ means that $\eta$ has its measure further up in the poset than $\theta$ does. To make that intuition formal, we can also characterize the induced order as follows:

Proposition 2.2: Let $X$ be a poset, $\theta ,\eta \in {\Delta }^{c}X$. Then, $\theta ⪯\eta$ if and only if there exists $\kappa :X\to \Delta X$ s.t.:

• For all $x\in X$, $y\in supp\kappa \left(x\right)$: $x\le y$.

• ${\kappa }_{\ast }\theta \le \eta$

Proposition 2.3: Let $X$ be a poset, $\theta ,\eta \in {\Delta }^{c}X$. Then, $\theta ⪯\eta$ if and only if there exists $\kappa :X\to \Delta X$ s.t.:

• For all $x\in X$, $y\in supp\kappa \left(x\right)$: $x\ge y$.

• $\theta \le {\kappa }_{\ast }\eta$

Or, in words, you can always go from $\theta$ to $\eta$ by moving probability mass upwards from where it was, since $\kappa \left(x\right)$ is always supported on the set of points at-or-above $x$.

We can now state the formalization of only bounding one side of the bridge transform. Let ${el}^{\Gamma }\times \Phi$ be equipped with the following order. $(y,\alpha ,x)\le (y^{\prime },{\alpha }^{\prime },x^{\prime })$ if and only if $y=y^{\prime }$, $x=x^{\prime }$ and $\alpha \subseteq {\alpha }^{\prime }$. Then:

Proposition 2.4: For any $\Gamma$, $\Phi$ and $\Theta \in {\square }^c(\Gamma \times \Phi )$, $Br\left(\Theta \right)$ is downwards closed w.r.t. the induced order on ${\Delta }^c({el}^{\Gamma }\times \Phi )$. That is, if $\theta \in Br\left(\Theta \right)$ and $\eta ⪯\theta$ then $\eta \in Br\left(\Theta \right)$.

Simple special case

Let's consider the special case where there's only one program, which can produce two possible outputs, a 0 and a 1. And these two outputs map to two different distributions over physics outcomes in $\Phi$. Intuitively, if the computation isn't realized/instantiated, the distribution over physics outcome should be identical, while if the computation is realized/instantiated, it should be possible to look at the physics results to figure out how the computation behaves. The two probability distributions may overlap some intermediate amount, in which case it should be possible to write the two probability distributions as a mixture between a probability distribution that behaves identically regardless of the program output (the "overlap" of the two distributions), and a pair of probability distributions corresponding to the two different program outputs which are disjoint. And the total variation distance ($d_{\text{TV}}\left(\varphi \right(0),\varphi (1\left)\right)$) between the two probability distributions is connected to the size of the distribution overlap. Proposition 2.5 makes this formal.

Proposition 2.5: Consider a finite set $X$, ${\varphi }_{?}\in \Delta X$, ${\varphi }_{!}:\{0,1\}\to \Delta X$, $p\in [0,1]$ and $\varphi :=(1-p){\varphi }_{?}+p{\varphi }_{!}$. Then, $p\ge d_{\text{TV}}\left(\varphi \right(0),\varphi (1\left)\right)$. Conversely, consider any $\varphi :\{0,1\}\to \Delta X$. Then, there exist ${\varphi }_{?}\in \Delta X$ and ${\varphi }_{!}:\{0,1\}\to \Delta X$ s.t. $\varphi =(1-p){\varphi }_{?}+p{\varphi }_{!}$ for $p:=d_{\text{TV}}\left(\varphi \right(0),\varphi (1\left)\right)$.

The bridge transform should replicate this same sort of analysis. We can interpret the case of "total uncertainty over math, but knowing how physics turns out conditional on knowing how math turns out" by ${\top }_{\Gamma }⋉\varphi$ for some $\varphi :\Gamma \to \Delta \Phi$. Taking the special case where $\Gamma =\{0,1\}$ for one program that can output two possible answers, it should return the same sort of result, where the two probability distributions can be decomposed into their common overlap, and non-overlapping pieces, and the overlapping chunk of probability measure should be allocated to the event "the computation is not instantiated", while the disjoint ones should be allocated to the event "the computation is instantiated". As it turns out, this does indeed happen, with the same total-variation-distance-based upper bound on the probability that the computation is unrealized (namely, $1-d_{\text{TV}}\left(\varphi \right(0),\varphi (1\left)\right)$)

Proposition 2.6: Consider any $\Phi$ and $\varphi :\{0,1\}\to \Delta \Phi$. Denote $U:=\{0,1\}\times \left\{\right\{0,1\left\}\right\}\times \Phi$ (the event "program is unrealized"). Let $\Lambda :=Br({\top }_{\{0,1\}}⋉\varphi )$. Then,

$$\Lambda \left({\chi }_U\right)=1-d_{\text{TV}}\left(\varphi \right(0),\varphi (1\left)\right)$$

Bound in terms of support

If the physical state is $x\in \Phi$, then it is intuitively obvious that the physically manifest facts about the computational universe $y\in \Gamma$ must include the fact that $(y,x)\in supp\Theta$. Formally:

Proposition 2.7: If $X$ is a poset and $\Theta \in {\square }^{c}X$, then ${\Theta }^{\downarrow }$ will denote downward closure of $\Theta$. For any $\Gamma$, $\Phi$ and $\Theta \in {\square }^c(\Gamma \times \Phi )$ if $(y,\alpha ,x)\in suppBr\left(\Theta \right)$ and $y^{\prime }\in \alpha$, then $(y^{\prime },x)\in supp\Theta$. Moreover, define ${sus}^{\Theta }:\Phi \to 2^{\Gamma }$ by ${sus}^{\Theta }\left(x\right):=\{y\in \Gamma \mid (y,x)\in supp\Theta \}$. Then, $Br\left(\Theta \right)\subseteq (\Theta ⋉{sus}^{\Theta }{)}^{\downarrow }$ (we slightly abuse notation by treating ${sus}^{\Theta }$ as a mapping $\Gamma \times \Phi \to 2^{\Gamma }$ that doesn't depend on the first argument, and also playing loose with the order of factors in the set on which our HUCs live).

Putting that into words, all the $(\alpha ,x)$ that are in the support of the bridge transform have $\alpha$ being a subset of the support of $\Theta$ restricted to $x$. The bridge transform knows not to provide $\alpha$ sets which are too large. Further, the bridge transform is smaller/has more information than the transform that just knows about what the support of $\Theta$ is.

Idempotence

Imagine replacing the physical state space $\Phi$ by the space of manifest facts $2^{\Gamma }$. Intuitively, the latter should contain the same information about computations as the former. Therefore, if we apply the bridge transform again after making such a replacement, we should get the same thing. Given any set $X$, we denote ${id}_X:X\to X$ the identity mapping and ${diag}_X:X\to X\times X$ the diagonal mapping.

Proposition 2.8: For any $\Gamma$, $\Phi$ and $\Theta \in {\square }^c(\Gamma \times \Phi )$

$$Br\left({pr}_{\Gamma \times 2^{\Gamma }}Br\right(\Theta \left)\right)=\left[\right({id}_{\Gamma }\times {diag}_{2^{\Gamma }}{)}_{\ast }{pr}_{\Gamma \times 2^{\Gamma }}Br\left(\Theta \right){]}^{\downarrow }$$

Refinement

If we refine a hypothesis (i.e. make it more informative) in the ultradistribution sense, the bridge transform should also be more refined:

Proposition 2.9: For any $\Gamma$, $\Phi$ and ${\Theta }_1,{\Theta }_2\in {\square }^c(\Gamma \times \Phi )$, if ${\Theta }_1\subseteq {\Theta }_2$ then $Br\left({\Theta }_1\right)\subseteq Br\left({\Theta }_2\right)$.

Another way of refining a hypothesis is refining the ontology, i.e. moving to a richer state space. For example, we can imagine one hypothesis that describes the world in terms of macroscopic objects and another hypothesis that describes the worlds in term of atoms which are otherwise perfectly consistent with each other. In this case, we also expect the bridge transform to become more refined. This desiderata is where the downwards closure comes from, because it's always possible to pass to a more detailed view of the world and new computations could manifest then. It's also worth noting that, if you reduce your uncertainty about math, or physics, or move to a more detailed state space, that means more computations are instantiated, and the loss goes down as a result.

Proposition 2.10: For any $\Gamma$, ${\Phi }_1$, ${\Phi }_2$, $t:{\Phi }_2\to {\Phi }_1$ and $\Theta \in {\square }^c(\Gamma \times {\Phi }_2)$

$$({id}_{{el}^{\Gamma }}\times t{)}_{\ast }Br(\Theta )\subseteq Br(({id}_{\Gamma }\times t{)}_{\ast }\Theta )$$

In general, when we refine the ontology, the manifest facts can become strictly refined: the richer state "knowns more" about computations than the poorer state. However, there is a special case when we don't expect this to happen, namely when the rich state depends on the computational universe only through the poor state. Roughly speaking, in this case once we have the poor state we can sample the rich state without evaluating any more programs. To formalize this, it is convenient to introduce pullback of HUCs, which is effectively the probabilistic version of taking a preimage.

Definition 2.2: Let $X,Y$ be finite sets and $t:X\to Y$ a mapping. We define the pullback^[7] operator $t^{\ast }:{\square }^{c}Y\to {\square }^{c}X$ by

$$t^{\ast }\Theta :=\{\theta \in {\Delta }^{c}X\mid t_{\ast }\theta \in \Theta \}$$

Proposition 2.11: Consider any $\Gamma$, ${\Phi }_1$, ${\Phi }_2$, $t:{\Phi }_2\to {\Phi }_1$, $\Xi :{\Phi }_1\to {\square }^c{\Phi }_2$ and $\Theta \in {\square }^c(\Gamma \times {\Phi }_1)$ s.t. $t\Xi ={id}_{{\Phi }_1}$. Then,

$$({id}_{{el}^{\Gamma }}\times \Xi {)}_{\ast }Br(\Theta )\subseteq Br(({id}_{\Gamma }\times \Xi {)}_{\ast }\Theta )\subseteq ({id}_{{el}^{\Gamma }}\times t{)}^{\ast }Br(\Theta )$$

In particular,

$${pr}_{{el}^{\Gamma }}Br\left(\Theta \right)={pr}_{{el}^{\Gamma }}Br\left(\right({id}_{\Gamma }\times \Xi {)}_{\ast }\Theta )$$

In other words, we can think of ${\Phi }_1$ as the coarse-grained version, and ${\Phi }_2$ as the fine-grained version, and $t$ as the coarse-graining function, and $\Xi$ as the function mapping a coarse grained state to some uncertainty over what the corresponding fine-grained state is. $\Theta$ is your starting uncertainty over computations and the coarse-grained state. Then, in order from most to least informative, you could apply $\Xi$ after the bridge transform, apply $\Xi$ before the bridge transform, or pull back along $t$ after the bridge transform (because the pullback is the most uninformative inverse, in a sense). But all this stuff only affects the information about the fine-grained state ${\Phi }_2$. If you were to forget about that, the data about computations and how they're instantiated is the same no matter whether you do the bridge transform with the coarse state, or try your best to fill in what the fine state is first, because the "fill in the fine state" function doesn't depend on your uncertainty about computations, so it doesn't contain any more information about how math is connected to physics than the original coarse-grained view had.

Mixing hypotheses

In general, we cannot expect the bridge transform to commute with taking probabilistic mixtures. For example, let $\Gamma =\{0,1\}$, $\Phi =\{0,1\}$, ${\Theta }_1={\top }_{\{00,11\}}$, ${\Theta }_2={\top }_{\{}$