Actually the Schwartz–Zippel algorithm can easily be adapted to this case (just imagine that types are variables over $Q$, and start from testing the identity of the types appearing inside parentheses), so we can validate expressions in randomized polynomial time (and, given standard conjectures, in deterministic polynomial time as well).

Let's also explicitly describe 0th order and 1st order infra-Bayesian logic (although they are ofc segments of higher-order).

0-th order

Syntax

Let $A$ be the set of propositional variables. We define the language $L$:

• Any $a\in A$ is also in $L$
• $\perp \in L$
• $\top \in L$
• Given $p,q\in L$, $p\wedge q\in L$
• Given $p,q\in L$, $p\vee q\in L$

Notice there's no negation or implication. We define the set of judgements $J:=L\times L$. We write judgements as $p⊢q$ ("$q$ in the context of $p$"). A theory is a subset of $J$.

Semantics

Given $T\subseteq J$, a model of $T$ consists of a compact Polish space $X$ and a mapping $M:L\to \square X$. The latter is required to satisfy:

• $M\left(\perp \right)={\perp }_X$
• $M\left(\top \right)={\top }_X$
• $M(p\wedge q)=M\left(p\right)\wedge M\left(q\right)$. Here, we define $\wedge$ of infradistributions as intersection of the corresponding sets
• $M(p\vee q)=M\left(p\right)\vee M\left(q\right)$. Here, we define $\vee$ of infradistributions as convex hull of the corresponding sets
• For any $p⊢q\in T$, $M\left(p\right)⪯M\left(q\right)$

1-st order

Syntax

We define the language using the usual syntax of 1-st order logic, where the allowed operators are $\wedge$, $\vee$ and the quantifier $\exists$. Variables are labeled by types from some set $T$. For simplicity, we assume no constants, but it is easy to introduce them. For any sequence of variables $(v_1\dots v_n)$, we denote $L_v$ the set of formulae whose free variables are a subset of $v_1\dots v_n$. We define the set of judgements $J:={\bigcup }_v{L}_v\times L_v$.

Semantics

Given $T\subseteq J$, a model of $T$ consists of

• For every $t\in T$, a compact Polish space $M\left(t\right)$
• For every $p\in L_v$ where $v_1\dots v_n$ have types $t_1\dots t_n$, an element $M_v\left(p\right)$ of $X_v:=\square \left({\prod }_{i=1}^{n}M\left(t_i\right)\right)$

It must satisfy the following:

• $M_v\left(\perp \right)={\perp }_{X_v}$
• $M_v\left(\top \right)={\top }_{X_v}$
• $M_v(p\wedge q)=M_v\left(p\right)\wedge M_v\left(q\right)$
• $M_v(p\vee q)=M_v\left(p\right)\vee M_v\left(q\right)$
• Consider variables $u_1\dots u_n$ of types $t_1\dots t_n$ and variables $v_1\dots v_m$ of types $s_1\dots s_m$. Consider also some $\sigma :\{1\dots n\}\to \{1\dots m\}$ s.t. $s_{\sigma \left(i\right)}=t_i$. Given $p\in L_v$, we can form the substitution $q:=p[x_i=y_{\sigma \left(i\right)}]\in L_u$. We also have a mapping $f_{\sigma }:X_v\to X_u$ given by $f_{\sigma }(x_1\dots x_m)=(x_{\sigma \left(1\right)}\dots x_{\sigma \left(n\right)})$. We require $M_u\left(q\right)=f^{\ast }\left(M_v\right(p\left)\right)$
• Consider variables $v_1\dots v_n$ and $i\in \{1\dots n\}$. Denote $pr:X_v\to X_{v\setminus v_i}$ the projection mapping. We require $M_{v\setminus v_i}(\exists v_i:p)={pr}_{\ast }\left(M_v\right(p\left)\right)$
• For any $p⊢q\in T$, $M_v\left(p\right)⪯M_v\left(q\right)$

When using infra-Bayesian logic to define a simplicity prior, it is natural to use "axiom circuits" rather than plain formulae. That is, when we write the axioms defining our hypothesis, we are allowed to introduce "shorthand" symbols for repeating terms. This doesn't affect the expressiveness, but it does affect the description length. Indeed, eliminating all the shorthand symbols can increase the length exponentially.

Instead of introducing all the "algebrator" logical symbols, we can define $T$ as the quotient by the equivalence relation defined by the algebraic laws. We then need only two extra logical atomic terms:

• For any $n\in N$ and $\sigma \in S_n$ (permutation), denote $n:={\sum }_{i=1}^{n}1$ and require ${\sigma }^{+}\in F_{n\to n}$
• For any $n\in N$ and $\sigma \in S_n$, ${\sigma }_{\alpha }^{\times }\in F_{{\alpha }^n\to {\alpha }^n}$

However, if we do this then it's not clear whether deciding that an expression is a well-formed term can be done in polynomial time. Because, to check that the types match, we need to test the identity of algebraic expressions and opening all parentheses might result in something exponentially long.

Infra-Bayesianism can be naturally understood as semantics for a certain non-classical logic. This promises an elegant synthesis between deductive/symbolic reasoning and inductive/intuitive reasoning, with several possible applications. Specifically, here we will explain how this can work for higher-order logic. There might be holes and/or redundancies in the precise definitions given here, but I'm quite confident the overall idea is sound.

For simplicity, we will only work with crisp infradistributions, although a lot of this stuff can work for more general types of infradistributions as well. Therefore, $\square X$ will denote the space of crisp infradistribution. Given $\mu \in \square X$, $S\left(\mu \right)\subseteq \Delta X$ will denote the corresponding convex set. As opposed to previously, we will include the empty-set, i.e. there is ${\perp }_X\in \square X$ s.t. $S\left({\perp }_X\right)=\varnothing$. Given $p\in \Delta X$ and $\mu \in \square X$, $p:\mu$ will mean $p\in S\left(\mu \right)$. Given $\mu ,\nu \in \square X$, $\mu ⪯\nu$ will mean $S\left(\mu \right)\subseteq S\left(\nu \right)$.

Syntax

Let $T^{\iota }$ denote a set which we interpret as the types of individuals (we allow more than one). We then recursively define the full set of types $T$ by:

• $0\in T$ (intended meaning: the uninhabited type)
• $1\in T$ (intended meaning: the one element type)
• If $\alpha \in T^{\iota }$ then $\alpha \in T$
• If $\alpha ,\beta \in T$ then $\alpha +\beta \in T$ (intended meaning: disjoint union)
• If $\alpha ,\beta \in T$ then $\alpha \times \beta \in T$ (intended meaning: Cartesian product)
• If $\alpha \in T$ then $\left(\alpha \right)\in T$ (intended meaning: predicates with argument of type $\alpha$)

For each $\alpha ,\beta \in T$, there is a set $F_{\alpha \to \beta }^0$ which we interpret as atomic terms of type $\alpha \to \beta$. We will denote $V_{\alpha }^0:=F_{1\to \alpha }^0$. Among those we distinguish the logical atomic terms:

• ${id}_{\alpha }\in F_{\alpha \to \alpha }^0$
• $0_{\alpha }\in F_{0\to \alpha }^0$
• $1_{\alpha }\in F_{\alpha \to 1}^0$
• ${pr}_{\alpha \beta }\in F_{\alpha \times \beta \to \alpha }^0$
• $i_{\alpha \beta }\in F_{\alpha \to \alpha +\beta }^0$
• Symbols we will not list explicitly, that correspond to the algebraic properties of $+$ and $\times$ (commutativity, associativity, distributivity and the neutrality of $0$ and $1$). For example, given $\alpha ,\beta \in T$ there is a "commutator" of type $\alpha \times \beta \to \beta \times \alpha$.
• ${=}_{\alpha }\in V_{(\alpha \times \alpha )}^0$
• ${diag}_{\alpha }\in F_{\alpha \to \alpha \times \alpha }^0$
• $({)}_{\alpha }\in V_{\left(\right(\alpha )\times \alpha )}^0$ (intended meaning: predicate evaluation)
• $\perp \in V_{\left(1\right)}^0$
• $\top \in V_{\left(1\right)}^0$
• ${\vee }_{\alpha }\in F_{\left(\alpha \right)\times \left(\alpha \right)\to \left(\alpha \right)}^0$
• ${\exists }_{\alpha \beta }\in F_{(\alpha \times \beta )\to \left(\beta \right)}^0$
• ${\forall }_{\alpha \beta }\in F_{(\alpha \times \beta )\to \left(\beta \right)}^0$
• Assume that for each $n\in N$ there is some $D_n\subseteq \square \left[n\right]$: the set of "describable" infradistributions (for example, it can be empty, or consist of all distributions with rational coefficients, or all distributions, or all infradistributions; EDIT: it is probably sufficient to only have the fair coin distribution in $D_2$ in order for it to be possible to approximate all infradistributions on finite sets). If $\mu \in D_n$ then $┌\mu ┐\in V_{\left({\sum }_{i=1}^{n}1\right)}$

We recursively define the set of all terms $F_{\alpha \to \beta }$. We denote $V_{\alpha }:=F_{1\to \alpha }$.

• If $f\in F_{\alpha \to \beta }^0$ then $f\in F_{\alpha \to \beta }$
• If $f_1\in F_{{\alpha }_1\to {\beta }_1}$ and $f_2\in F_{{\alpha }_2\to {\beta }_2}$ then $f_1\times f_2\in F_{{\alpha }_1\times {\alpha }_2\to {\beta }_1\times {\beta }_2}$
• If $f_1\in F_{{\alpha }_1\to {\beta }_1}$ and $f_2\in F_{{\alpha }_2\to {\beta }_2}$ then $f_1+f_2\in F_{{\alpha }_1+{\alpha }_2\to {\beta }_1+{\beta }_2}$
• If $f\in F_{\alpha \to \beta }$ then $f^{-1}:F_{\left(\beta \right)\to \left(\alpha \right)}$
• If $f\in F_{\alpha \to \beta }$ and $g\in F_{\beta \to \gamma }$ then $g\circ f\in F_{\alpha \to \gamma }$

Elements of $V_{\left(\alpha \right)}$ are called formulae. Elements of $V_{\left(1\right)}$ are called sentences. A subset of $V_{\left(1\right)}$ is called a theory.

Semantics

Given $T\subseteq V_{\left(1\right)}$, a model $M$ of $T$ is the following data. To each $\alpha \in T$, there must correspond some compact Polish space $M\left(t\right)$ s.t.:

• $M\left(0\right)=\varnothing$
• $M\left(1\right)=pt$ (the one point space)
• $M(\alpha +\beta )=M\left(\alpha \right)\bigsqcup M\left(\beta \right)$
• $M(\alpha \times \beta )=M\left(\alpha \right)\times M\left(\beta \right)$
• $M\left(\right(\alpha \left)\right)=\square M\left(\alpha \right)$

To each $f\in F_{\alpha \to \beta }$, there must correspond a continuous mapping $M\left(f\right):M\left(\alpha \right)\to M\left(\beta \right)$, under the following constraints:

• $0$, $1$, $id$, $pr$, $i$, $diag$ and the "algebrators" have to correspond to the obvious mappings.
• $M\left({=}_{\alpha }\right)={\top }_{{diag}_{M\left(\alpha \right)}}$. Here, ${diag}_X\subseteq X\times X$ is the diagonal and ${\top }_C\in \square X$ is the sharp infradistribution corresponding to the closed set $C\subseteq X$.
• Consider $\alpha \in T$ and denote $X:=M\left(\alpha \right)$. Then, $M\left(\right({)}_{\alpha })={\top }_{\square X}⋉{id}_{\square X}$. Here, we use the observation that the identity mapping ${id}_{\square X}$ can be regarded as an infrakernel from $\square X$ to $X$.
• $M\left(\perp \right)={\perp }_{pt}$
• $M\left(\top \right)={\top }_{pt}$
• $S\left(M\right(\vee \left)\right(\mu ,\nu \left)\right)$ is the convex hull of $S\left(\mu \right)\cup S\left(\nu \right)$
• Consider $\alpha ,\beta \in T$ and denote $X:=M\left(\alpha \right)$, $Y:=M\left(\beta \right)$ and $pr:X\times Y\to Y$ the projection mapping. Then, $M\left({\exists }_{\alpha \beta }\right)\left(\mu \right)={pr}_{\ast }\mu$.
• Consider $\alpha ,\beta \in T$ and denote $X:=M\left(\alpha \right)$, $Y:=M\left(\beta \right)$ and $pr:X\times Y\to Y$ the projection mapping. Then, $p:M\left({\forall }_{\alpha \beta }\right)\left(\mu \right)$ iff ${pr}_{\ast }^{-1}\left(p\right)\subseteq S\left(\mu \right)$.
• $M(f_1\times f_2)=M\left(f_1\right)\times M\left(f_2\right)$
• $M(f_1+f_2)=M\left(f_1\right)\bigsqcup M\left(f_2\right)$
• $M\left(f^{-1}\right)\left(\mu \right)=M\left(f{)}^{\ast }\right(\mu )$. Notice that pullback of infradistributions is always defined thanks to adding $\perp$ (the empty set infradistribution).
• $M(g\circ f)=M\left(g\right)\circ M\left(f\right)$
• $M(┌\mu ┐)=\mu$

Finally, for each $\varphi \in T$, we require $M\left(\varphi \right)={\top }_{pt}$.

Semantic Consequence

Given $\varphi \in V_{\left(1\right)}$, we say $M\models \varphi$ when $M\left(\varphi \right)={\top }_{pt}$. We say $T\models \varphi$ when for any model $M$ of $T$, $M\models \varphi$. It is now interesting to ask what is the computational complexity of deciding $T\models \varphi$. [EDIT: My current best guess is co-RE]

Applications

As usual, let $A$ be a finite set of actions and $O$ be a finite set of observation. Require that for each $o\in O$ there is ${\sigma }_o\in T^{\iota }$ which we interpret as the type of states producing observation $o$. Denote ${\sigma }_{\ast }:={\sum }_{o\in O}{\sigma }_o$ (the type of all states). Moreover, require that our language has the nonlogical symbols $s_0\in V_{\left({\sigma }_{\ast }\right)}^0$ (the initial state) and, for each $a\in A$, $K_a\in F_{{\sigma }_{\ast }\to \left({\sigma }_{\ast }\right)}^0$ (the transition kernel). Then, every model defines a (pseudocausal) infra-POMDP. This way we can use symbolic expressions to define infra-Bayesian RL hypotheses. It is then tempting to study the control theoretic and learning theoretic properties of those hypotheses. Moreover, it is natural to introduce a prior which weights those hypotheses by length, analogical to the Solomonoff prior. This leads to some sort of bounded infra-Bayesian algorithmic information theory and bounded infra-Bayesian analogue of AIXI.

re: #5, that doesn't seem to claim that we can infer U given their actions, which is what the impossibility of deducing preferences is actually claiming.

You misunderstand the intent. We're talking about inverse reinforcement learning. The goal is not necessarily inferring the unknown $U$, but producing some behavior that optimizes the unknown $U$. Ofc if the policy you're observing is optimal then it's trivial to do so by following the same policy. But, using my approach we might be able to extend it into results like "the policy you're observing is optimal w.r.t. certain computational complexity, and your goal is to produce an optimal policy w.r.t. higher computational complexity."

(Btw I think the formal statement I gave for 5 is false, but there might be an alternative version that works.)

(And as pointed out elsewhere, it isn't Stuart's thesis, it's a well known and basic result in the decision theory / economics / philosophy literature.)

I am referring to this and related work by Armstrong.

Ah, okay, I see what you mean. Like how preferences are divisible into "selfish" and "worldly" components, where the selfish component is what's impacted by a future simulation of you that is about to have good things happen to it.

...I brought up the histories->states thing because I didn't understand what you were getting at, so I was concerned that something unrealistic was going on. For example, if you assume that the agent can remember its history, how can you possibly handle an environment with memory-wiping?

AMDP is only a toy model that distills the core difficulty into more or less the simplest non-trivial framework. The rewards are "selfish": there is a reward function $r:(S\times A{)}^{\ast }\to R$ which allows assigning utilities to histories by time discounted summation, and we consider the expected utility of a random robot sampled from a late population. And, there is no memory wiping. To describe memory wiping we indeed need to do the "unrolling" you suggested. (Notice that from the cybernetic model POV, the history is only the remembered history.)

For a more complete framework, we can use an ontology chain, but (i) instead of $A\times O$ labels use $A\times M$ labels, where $M$ is the set of possible memory states (a policy is then described by $\pi :M\to A$), to allow for agents that don't fully trust their memory (ii) consider another chain with a bigger state space $S^{\prime }$ plus a mapping $p:S^{\prime }\to N^S$ s.t. the transition kernels are compatible. Here, the semantics of $p\left(s\right)$ is: the multiset of ontological states resulting from interpreting the physical state $s$ by taking the viewpoints of different agents $s$ contains.

In fact, to me the example is still somewhat murky, because you're talking about the subjective probability of a state given a policy and a timestep, but if the agents know their histories there is no actual agent in the information-state that corresponds to having those probabilities.

I didn't understand "no actual agent in the information-state that corresponds to having those probabilities". What does it mean to have an agent in the information-state?

I'm not quite sure what are you trying to say here, probably my explanation of the framework was lacking. The robots already remember the history, like in classical RL. The question about the histories is perfectly well-defined. In other words, we are already implicitly doing what you described. It's like in classical RL theory, when you're proving a regret bound or whatever, your probability space consists of histories.

I'm still confused about what you mean by "Bayesian hypothesis" though. Do you mean a hypothesis that takes the form of a non-anthropic MDP?

Yes, or a classical RL environment. Ofc if we allow infinite state spaces, then any environment can be regarded as an MDP (whose states are histories). That is, I'm talking about hypotheses which conform to the classical "cybernetic agent model". If you wish, we can call it "Bayesian cybernetic hypothesis".

Also, I want to clarify something I was myself confused about in the previous comment. For an anthropic Markov chain (when there is only one action) with a finite number of states, we can give a Bayesian cybernetic description, but for a general anthropic MDP we cannot even if the number of states is finite.

Indeed, consider some $T:S\to \Delta N^S$. We can take its expected value to get $ET:S\to R_{+}^S$. Assuming the chain is communicating, $ET$ is an irreducible non-negative matrix, so by the Perron-Frobenius theorem it has a unique-up-to-scalar maximal eigenvector $\eta \in R_{+}^S$. We then get the subjective transition kernel:

$$ST(t\mid s)=\frac{ET(t\mid s){\eta }_t}{{\sum }_{t^{\prime }\in S}ET(t^{\prime }\mid s){\eta }_{t^{\prime }}}$$

Now, consider the following example of an AMDP. There are three actions $A:=\{a,b,c\}$ and two states $S:=\{s_0,s_1\}$. When we apply $a$ to an $s_0$ robot, it creates two $s_0$ robots, whereas when we apply $a$ to an $s_1$ robot, it leaves one $s_1$ robot. When we apply $b$ to an $s_1$ robot, it creates two $s_1$ robots, whereas when we apply $b$ to an $s_0$ robot, it leaves one $s_0$ robot. When we apply $c$ to any robot, it results in one robot whose state is $s_0$ with probability $\frac{1}{2}$ and $s_1$ with probability $\frac{1}{2}$.

Consider the following two policies. ${\pi }_a$ takes the sequence of actions $cacaca\dots$ and ${\pi }_b$ takes the sequence of actions $cbcbcb\dots$. A population that follows ${\pi }_a$ would experience the subjective probability $ST(s_0\mid s_0,c)=\frac{2}{3}$, whereas a population that follows ${\pi }_b$ would experience the subjective probability $ST(s_0\mid s_0,c)=\frac{1}{3}$. Hence, subjective probabilities depend on future actions. So, effectively anthropics produces an acausal (Newcomb-like) environment. And, we already know such environments are learnable by infra-Bayesian RL agents and, (most probably) not learnable by Bayesian RL agents.

I'm not sure what do you mean by that "unrolling". Can you write a mathematical definition?

Let's consider a simple example. There are two states: $s_0$ and $s_1$. There is just one action so we can ignore it. $s_0$ is the initial state. An $s_0$ robot transition into an $s_1$ robot. An $s_1$ robot transitions into an $s_0$ robot and an $s_1$ robot. How will our population look like?

0th step: all robots remember $s_0$

1st step: all robots remember $s_0{s}_1$

2nd step: 1/2 of robots remember $s_0{s}_1{s}_0$ and 1/2 of robots remember $s_0{s}_1{s}_1$

3rd step: 1/3 of robots remembers $s_0{s}_1{s}_0{s}_1$, 1/3 of robots remember $s_0{s}_1{s}_1{s}_0$ and 1/3 of robots remember $s_0{s}_1{s}_1{s}_1$

There is no Bayesian hypothesis a robot can have that gives correct predictions both for step 2 and step 3. Indeed, to be consistent with step 2 we must have $Pr\left[s_0{s}_1{s}_0\right]=\frac{1}{2}$ and $Pr\left[s_0{s}_1{s}_1\right]=\frac{1}{2}$. But, to be consistent with step 3 we must have $Pr\left[s_0{s}_1{s}_0\right]=\frac{1}{3}$, $Pr\left[s_0{s}_1{s}_1\right]=\frac{2}{3}$.

In other words, there is no Bayesian hypothesis s.t. we can guarantee that a randomly sampled robot on a sufficiently late time step will have learned this hypothesis with high probability. The apparent transition probabilities keep shifting s.t. it might always continue to seem that the world is complicated enough to prevent our robot from having learned it already.

Or, at least it's not obvious there is such a hypothesis. In this example, $\frac{Pr\left[s_0{s}_1{s}_1\right]}{Pr\left[s_0{s}_1{s}_0\right]}$ will converge to the golden ratio at late steps. But, do all probabilities converge fast enough for learning to happen, in general? I don't know, maybe for finite state spaces it can work. Would definitely be interesting to check.

[EDIT: actually, in this example there is such a hypothesis but in general there isn't, see below]

Notice that Eliezer's definition + the universal prior is essentially the same as the computationally unbounded variant of my definition of goal-directed intelligence, if you fix the utility function and prior. I think that when you're comparing different utility functions in your definition of strategy-stealing, it's better to emulate my definition and correct by the description complexity of the utility function. Indeed, if you have an algorithm that works equally well for all utility functions but contains a specification of the utility function inside its source code, then you get "spurious" variance if you don't correct for it (usually superior algorithms would also have to contain a specification of the utility function, so the more complex the utility function the less of them will be).