Vanessa Kosoy comments on Vanessa Kosoy’s Shortform

[Vanessa Kosoy]

Master post for ideas about infra-Bayesianism.

[Vanessa Kosoy]

In the anthropic trilemma, Yudkowsky writes about the thorny problem of understanding subjective probability in a setting where copying and modifying minds is possible. Here, I will argue that infra-Bayesianism (IB) leads to the solution.

Consider a population of robots, each of which in a regular RL agent. The environment produces the observations of the robots, but can also make copies or delete portions of their memories. If we consider a random robot sampled from the population, the history they observed will be biased compared to the “physical” baseline. Indeed, suppose that a particular observation $c$ has the property that every time a robot makes it, 10 copies of them are created in the next moment. Then, a random robot will have $c$ much more often in their history than the physical frequency with which $c$ is encountered, due to the resulting “selection bias”. We call this setting “anthropic RL” (ARL).

The original motivation for IB was non-realizability. But, in ARL, Bayesianism runs into issues even when the environment is realizable from the “physical” perspective. For example, we can consider an “anthropic MDP” (AMDP). An AMDP has finite sets of actions ($A$) and states ($S$), and a transition kernel $T:A\times S\to \Delta \left(S^{\ast }\right)$. The output is a string of states instead of a single state, because many copies of the agent might be instantiated on the next round, each with their own state. In general, there will be no single Bayesian hypothesis that captures the distribution over histories that the average robot sees at any given moment of time (at any given moment of time we sample a robot out of the population and look at their history). This is because the distributions at different moments of time are mutually inconsistent.

[EDIT: Actually, given that we don’t care about the order of robots, the signature of the transition kernel should be $T:A\times S\to \Delta N^S$]

The consistency that is violated is exactly the causality property of environments. Luckily, we know how to deal with acausality: using the IB causal-acausal correspondence! The result can be described as follows: Murphy chooses a time moment $n\in N$ and guesses the robot policy $\pi$ until time $n$. Then, a simulation of the dynamics of $(\pi ,T)$ is performed until time $n$, and a single history is sampled from the resulting population. Finally, the observations of the chosen history unfold in reality. If the agent chooses an action different from what is prescribed, Nirvana results. Nirvana also happens after time $n$ (we assume Nirvana reward $1$ rather than $\infty$).

This IB hypothesis is consistent with what the average robot sees at any given moment of time. Therefore, the average robot will learn this hypothesis (assuming learnability). This means that for $n\gg \frac{1}{1-\gamma }\gg 0$, the population of robots at time $n$ has expected average utility with a lower bound close to the optimum for this hypothesis. I think that for an AMDP this should equal the optimum expected average utility you can possibly get, but it would be interesting to verify.

Curiously, the same conclusions should hold if we do a weighted average over the population, with any fixed method of weighting. Therefore, the posterior of the average robot behaves adaptively depending on which sense of “average” you use. So, your epistemology doesn’t have to fix a particular method of counting minds. Instead different counting methods are just different “frames of reference” through which to look, and you can be simultaneously rational in all of them.

[Charlie Steiner]

Could you expand a little on why you say that no Bayesian hypothesis captures the distribution over robot-histories at different times? It seems like you can unroll an AMDP into a “memory MDP” that puts memory information of the robot into the state, thus allowing Bayesian calculation of the distribution over states in the memory MDP to capture history information in the AMDP.

[Vanessa Kosoy]

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: ¹⁄₂ of robots remember $s_0{s}_1{s}_0$ and ¹⁄₂ of robots remember $s_0{s}_1{s}_1$

3rd step: ¹⁄₃ of robots remembers $s_0{s}_1{s}_0{s}_1$, ¹⁄₃ of robots remember $s_0{s}_1{s}_1{s}_0$ and ¹⁄₃ 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]

[Charlie Steiner]

Great example. At least for the purposes of explaining what I mean :) The memory AMDP would just replace the states $s_0$, $s_1$ with the memory states $\left[s_0\right]$, $\left[s_1\right]$, $[s_0,s_0]$, $[s_0,s_1]$, etc. The action takes a robot in $\left[s_0\right]$ to memory state $[s_0,s_1]$, and a robot in $[s_0,s_1]$ to one robot in $[s_0,s_1,s_0]$ and another in $[s_0,s_1,s_1]$.

(Skip this paragraph unless the specifics of what’s going on aren’t obvious: given a transition distribution $P(s^{\prime \ast }|s,\pi )$ (P being the distribution over sets of states s’* given starting state s and policy $\pi$), we can define the memory transition distribution $P(s_m^{\prime \ast }|s_m,\pi )$ given policy $\pi$ and starting “memory state” $s_m\in S^{\ast }$ (Note that this star actually does mean finite sequences, sorry for notational ugliness). First we plug the last element of $s_m$ into the transition distribution as the current state. Then for each $s^{\prime \ast }$ in the domain, for each element in $s^{\prime \ast }$ we concatenate that element onto the end of $s_m$ and collect these $s_m^{\prime }$ into a set $s_m^{\prime \ast }$, which is assigned the same probability $P\left(s^{\prime \ast }\right)$.)

So now at time t=2, if you sample a robot, the probability that its state begins with $[s_0,s_1,s_1]$ is 0.5. And at time t=3, if you sample a robot that probability changes to 0.66. This is the same result as for the regular MDP, it’s just that we’ve turned a question about the history of agents, which may be ill-defined, into a question about which states agents are in.

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?

[Vanessa Kosoy]

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.

[Charlie Steiner]

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.

(edit: The reward function in AMDPs can either be analogous to “wordly” and just sum the reward calculated at individual timesteps, or analogous to “selfish” and calculated by taking the limit of the subjective distribution over parts of the history, then applying a reward function to the expected histories.)

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?

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. In an MDP the agents just have probabilities over transitions—so maybe a clearer example is an agent that copies itself if it wins the lottery having a larger subjective transition probability of going from gambling to winning. (i.e. states are losing and winning, actions are gamble and copy, the policy is to gamble until you win and then copy).

[Vanessa Kosoy]

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?

[Charlie Steiner]

What does it mean to have an agent in the information-state?

Nevermind, I think I was just looking at it with the wrong class of reward function in mind.

[Vanessa Kosoy]

Is it possible to replace the maximin decision rule in infra-Bayesianism with a different decision rule? One surprisingly strong desideratum for such decision rules is the learnability of some natural hypothesis classes.

In the following, all infradistributions are crisp.

Fix finite action set $A$ and finite observation set $O$. For any $k\in N$ and $\gamma \in (0,1)$, let

$$M_{\gamma }^k:(A\times O{)}^{\omega }\to \Delta (A\times O{)}^k$$

be defined by

$$M_{\gamma }^k\left(h|d\right):=(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^n\left[\right[h=d_{n:n+k}\left]\right]$$

In other words, this kernel samples a time step $n$ out of the geometric distribution with parameter $\gamma$, and then produces the sequence of length $k$ that appears in the destiny starting at $n$.

For any continuous^[1] function $D:\square (A\times O{)}^k\to R$, we get a decision rule. Namely, this rule says that, given infra-Bayesian law $\Lambda$ and discount parameter $\gamma$, the optimal policy is

$${\pi }_{D\Lambda }^{\ast }:=\arg \underset{\pi :O^{\ast }\to A}{max}D\left(M_{\gamma \ast }^k\Lambda \right(\pi \left)\right)$$

The usual maximin is recovered when we have some reward function $r:(A\times O{)}^k\to R$ and corresponding to it is

$$D_r\left(\Theta \right):=\underset{\theta \in \Theta }{min}{E}_{\theta }\left[r\right]$$

Given a set $H$ of laws, it is said to be learnable w.r.t.$D$ when there is a family of policies $\{{\pi }_{\gamma }{\}}_{\gamma \in (0,1)}$ such that for any $\Lambda \in H$

$$\underset{\gamma \to 1}{lim}\left(\underset{\pi }{max}D\right(M_{\gamma \ast }^k\Lambda \left(\pi \right))-D(M_{\gamma \ast }^k\Lambda \left({\pi }_{\gamma }\right))=0$$

For $D_r$ we know that e.g. the set of all communicating^[2] finite infra-RDPs is learnable. More generally, for any $t\in [0,1]$ we have the learnable decision rule

$$D_r^t:=t\underset{\theta \in \Theta }{max}{E}_{\theta }\left[r\right]+(1-t)\underset{\theta \in \Theta }{min}{E}_{\theta }\left[r\right]$$

This is the “mesomism” I taked about before.

Also, any monotonically increasing $D$ seems to be learnable, i.e. any $D$ s.t. for ${\Theta }_1\subseteq {\Theta }_2$ we have $D\left({\Theta }_1\right)\le D\left({\Theta }_2\right)$. For such decision rules, you can essentially assume that “nature” (i.e. whatever resolves the ambiguity of the infradistributions) is collaborative with the agent. These rules are not very interesting.

On the other hand, decision rules of the form $D_{r_1}+D_{r_2}$ are not learnable in general, and so are decision rules of the form $D_r+D^{\prime }$ for $D^{\prime }$ monotonically increasing.

Open Problem: Are there any learnable decision rules that are not mesomism or monotonically increasing?

A positive answer to the above would provide interesting generalizations of infra-Bayesianism. A negative answer to the above would provide an interesting novel justification of the maximin. Indeed, learnability is not a criterion that was ever used in axiomatic constructions of decision theory^[3], AFAIK.

1. ^

   We can try considering discontinuous functions as well, but it seems natural to start with continuous. If we want the optimal policy to exist, we usually need $D$ to be at least upper semicontinuous.

2. ^

   There are weaker conditions than “communicating” that are sufficient, e.g. “resettable” (meaning that the agent can always force returning to the initial state), and some even weaker conditions that I will not spell out here.

3. ^

   I mean theorems like VNM, Savage etc.

[Vanessa Kosoy]

Ambidistributions

I believe that all or most of the claims here are true, but I haven’t written all the proofs in detail, so take it with a grain of salt.

Ambidistributions are a mathematical object that simultaneously generalizes infradistributions and ultradistributions. It is useful to represent how much power an agent has over a particular system: which degrees of freedom it can control, which degrees of freedom obey a known probability distribution and which are completely unpredictable.

Definition 1: Let $X$ be a compact Polish space. A (crisp) ambidistribution on $X$ is a function $Q:C\left(X\right)\to R$ s.t.

1. (Monotonocity) For any $f,g\in C\left(X\right)$, if $f\le g$ then $Q\left(f\right)\le Q\left(g\right)$.

2. (Homogeneity) For any $f\in C\left(X\right)$ and $\lambda \ge 0$, $Q\left(\lambda f\right)=\lambda Q\left(f\right)$.

3. (Constant-additivity) For any $f\in C\left(X\right)$ and $c\in R$, $Q(f+c)=Q\left(f\right)+c$.

Conditions 1+3 imply that $Q$ is 1-Lipschitz. We could introduce non-crisp ambidistributions by dropping conditions 2 and/​or 3 (and e.g. requiring 1-Lipschitz instead), but we will stick to crisp ambidistributions in this post.

The space of all ambidistributions on $X$ will be denoted $♡X$.^[1] Obviously, $\square X\subseteq ♡X$ (where $\square X$ stands for (crisp) infradistributions), and likewise for ultradistributions.

Examples

Example 1: Consider compact Polish spaces $X,Y,Z$ and a continuous mapping $F:X\times Y\to Z$. We can then define $F^{♡}\in ♡Z$ by

$$F^{♡}\left(u\right):=\underset{\theta \in \Delta X}{max}\underset{\eta \in \Delta Y}{min}{E}_{\theta \times \eta }[u\circ F]$$

That is, $F^{♡}\left(u\right)$ is the value of the zero-sum two-player game with strategy spaces $X$ and $Y$ and utility function $u\circ F$.

Notice that $F$ in Example 1 can be regarded as a Cartesian frame: this seems like a natural connection to explore further.

Example 2: Let $A$ and $O$ be finite sets representing actions and observations respectively, and $\Lambda :\{O^{\ast }\to A\}\to \square (A\times O{)}^{\ast }$ be an infra-Bayesian law. Then, we can define ${\Lambda }^{♡}\in ♡(A\times O{)}^{\ast }$ by

$${\Lambda }^{♡}\left(u\right):=\underset{\pi :O^{\ast }\to A}{max}{E}_{\Lambda \left(\pi \right)}\left[u\right]$$

In fact, this is a faithful representation: $\Lambda$ can be recovered from ${\Lambda }^{♡}$.

Example 3: Consider an infra-MDP with finite state set $S$, initial state $s_0\in S$ and transition infrakernel $T:S\times A\to \square S$. We can then define the “ambikernel” $T^{♡}:S\to ♡S$ by

$$T^{♡}(s;u):=\underset{a\in A}{max}{E}_{T(s,a)}\left[u\right]$$

Thus, every infra-MDP induces an “ambichain”. Moreover:

Claim 1: $♡$ is a monad. In particular, ambikernels can be composed.

This allows us defining

$$\varphi \left(\gamma \right):=(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^n\left(T^{♡}{)}^n\right(s_0)$$

This object is the infra-Bayesian analogue of the convex polytope of accessible state occupancy measures in an MDP.

Claim 2: The following limit always exists:

$${\varphi }^{\ast }:=\underset{\gamma \to 1}{lim}\varphi \left(\gamma \right)$$

Legendre-Fenchel Duality

Definition 3: Let $D$ be a convex space and $A_1,A_2\dots A_n,B\subseteq D$. We say that $B$ occludes $(A_1\dots A_n)$ when for any $(a_1\dots a_n)\in A_1\times \dots \times A_n$, we have

$$CH(a_1\dots a_n)\cap B\ne \varnothing$$

Here, $CH$ stands for convex hull.

We denote this relation $A_1\dots A_n⊢B$. The reason we call this “occlusion” is apparent for the $n=2$ case.

Here are some properties of occlusion:

1. For any $1\le i\le n$, $A_1\dots A_n⊢A_i$.

2. More generally, if $c\in \Delta \{1\dots n\}$ then $A_1\dots A_n⊢{\sum }_i{c}_i{A}_i$.

3. If $\Phi ⊢A$ and $\Phi \subseteq \Psi$ then $\Psi ⊢A$.

4. If $\Phi ⊢A$ and $A\subseteq B$ then $\Phi ⊢B$.

5. If $A_1\dots A_n⊢B$ and $A_i^{\prime }\subseteq A_i$ for all $1\le i\le n$, then $A_1^{\prime }\dots A_n^{\prime }⊢B$.

6. If $\Phi ⊢A_i$ for all $1\le i\le n$, and also $A_1\dots A_n⊢B$, then $\Phi ⊢B$.

Notice that occlusion has similar algebraic properties to logical entailment, if we think of $A\subseteq B$ as ”$B$ is a weaker proposition than $A$”.

Definition 4: Let $X$ be a compact Polish space. A cramble set^[2] over $X$ is $\Phi \subseteq \square X$ s.t.

1. $\Phi$ is non-empty.

2. $\Phi$ is topologically closed.

3. For any finite ${\Phi }_0\subseteq \Phi$ and $\Theta \in \square X$, if ${\Phi }_0⊢\Theta$ then $\Theta \in \Phi$. (Here, we interpret elements of $\square X$ as credal sets.)

Question: If instead of condition 3, we only consider binary occlusion (i.e. require $|{\Phi }_0|\le 2)$, do we get the same concept?

Given a cramble set $\Phi$, its Legendre-Fenchel dual ambidistribution is

$$\hat{\Phi }\left(f\right):=\underset{\Theta \in \Phi }{max}{E}_{\Theta }\left[f\right]$$

Claim 3: Legendre-Fenchel duality is a bijection between cramble sets and ambidistributions.

Lattice Structure

Functionals

The space $♡X$ is equipped with the obvious partial order: $Q\le P$ when for all $f\in C\left(X\right),$ $Q\left(f\right)\le P\left(f\right)$. This makes $♡X$ into a distributive lattice, with

$$(P\wedge Q)\left(f\right)=min\left(P\right(f),Q(f\left)\right)$$$$(P\vee Q)\left(f\right)=max\left(P\right(f),Q(f\left)\right)$$

This is in contrast to $\square X$ which is a non-distributive lattice.

The bottom and top elements are given by

$$\perp \left(f\right)=\underset{x\in X}{min}f\left(x\right)$$$$\top \left(f\right)=\underset{x\in X}{max}f\left(x\right)$$

Ambidistributions are closed under pointwise suprema and infima, and hence $♡X$ is complete and satisfies both infinite distributive laws, making it a complete Heyting and co-Heyting algebra.

$♡X$ is also a De Morgan algebra with the involution

$$\overline{Q}\left(f\right):=-Q(-f)$$

For $X\ne \varnothing$, $♡X$ is not a Boolean algebra: $\Delta X\subseteq ♡X$ and for any $\theta \in \Delta X$ we have $\overline{\theta }=\theta$.

One application of this partial order is formalizing the “no traps” condition for infra-MDP:

Definition 2: A finite infra-MDP is quasicommunicating when for any $s\in S$

$$\underset{\gamma \to 1}{lim}(1-\gamma )\sum _{n=0}^{\infty }{\gamma }^n\left(T^{♡}{)}^n\right(s_0)\le \underset{\gamma \to 1}{lim}(1-\gamma \left)\sum _{n=0}^{\infty }{\gamma }^n\right(T^{♡}{)}^n\left(s\right)$$

Claim 4: The set of quasicommunicating finite infra-MDP (or even infra-RDP) is learnable.

Cramble Sets

Going to the cramble set representation, $\hat{\Phi }\le \hat{\Psi }$ iff $\Phi \subseteq \Psi$.

$\Phi \wedge \Psi$ is just $\Phi \cap \Psi$, whereas $\Phi \vee \Psi$ is the “occlusion hall” of $\Phi$ and $\Psi$.

The bottom and the top cramble sets are

$$\perp =\left\{{\top }_{\square }\right\}$$$$\top =\square X$$

Here, ${\top }_{\square }$ is the top element of $\square X$ (corresponding to the credal set $\Delta X)$.

The De Morgan involution is

$$\overline{\Phi }=\{\Theta \in \square X\mid \forall \Xi \in \Phi :\Theta \cap \Xi \ne \varnothing \}$$

Operations

Definition 5: Given $X,Y$ compact Polish spaces and a continuous mapping $h:X\to Y$, we define the pushforward $h_{\ast }:♡X\to ♡Y$ by

$$h_{\ast }(Q;f):=Q(f\circ h)$$

When $h$ is surjective, there are both a left adjoint and a right adjoint to $h_{\ast }$, yielding two pullback operators $h_{min}^{\ast },h_{max}^{\ast }:♡Y\to ♡X$:

$$h_{min}^{\ast }(Q;f):=\underset{g\in C\left(Y\right):g\circ h\ge f}{min}Q\left(g\right)$$$$h_{max}^{\ast }(Q;f):=\underset{g\in C\left(Y\right):g\circ h\le f}{max}Q\left(g\right)$$

Given $Q\in ♡X$ and $P\in ♡Y$ we can define the semidirect product $Q⋉P\in ♡(X\times Y)$ by

$$(Q⋉P)\left(f\right):=Q(\lambda x.P(\lambda y.f(x,y)\left)\right)$$

There are probably more natural products, but I’ll stop here for now.

Polytopic Ambidistributions

Definition 6: The polytopic ambidistributions ${♡}_{\text{pol}}X$ are the (incomplete) sublattice of $♡X$ generated by $\Delta X$.

Some conjectures about this:

• For finite $X$, an ambidistributions $Q$ is polytopic iff there is a finite polytope complex $C$ on $R^X$ s.t. for any cell $A$ of $C$, $Q{|}_C$ is affine.

• For finite $X$, a cramble set $\Phi$ is polytopic iff it is the occlusion hall of a finite set of polytopes in $\Delta X$.

• $\varphi \left(\gamma \right)$ and ${\varphi }^{\ast }$ from Example 3 are polytopic.

1. ^

   The non-convex shape $♡$ reminds us that ambidistributions need not be convex or concave.

2. ^

   The expression “cramble set” is meant to suggest a combination of “credal set” with “ambi”.

[Vanessa Kosoy]

There is a formal analogy between infra-Bayesian decision theory (IBDT) and modal updateless decision theory (MUDT).

Consider a one-shot decision theory setting. There is a set of unobservable states $S$, a set of actions $A$ and a reward function $r:A\times S\to [0,1]$. An IBDT agent has some belief $\beta \in \square S$^[1], and it chooses the action $a^{\ast }:=\arg {max}_{a\in A}{E}_{\beta }[\lambda s.r(a,s\left)\right]$.

We can construct an equivalent scenario, by augmenting this one with a perfect predictor of the agent (Omega). To do so, define $S^{\prime }:=A\times S$, where the semantics of $(p,s)$ is “the unobservable state is $s$ and Omega predicts the agent will take action $p$”. We then define $r^{\prime }:A\times S^{\prime }\to [0,1]$ by $r^{\prime }(a,p,s):=1_{a=p}r(a,s)+1_{a\ne p}$ and ${\beta }^{\prime }\in \square S^{\prime }$ by $E_{{\beta }^{\prime }}\left[f\right]:={min}_{p\in A}{E}_{\beta }[\lambda s.f(p,s\left)\right]$ (${\beta }^{\prime }$ is what we call the pullback of $\beta$ to $S^{\prime }$, i.e we have utter Knightian uncertainty about Omega). This is essentially the usual Nirvana construction.

The new setup produces the same optimal action as before. However, we can now give an alternative description of the decision rule.

For any $p\in A$, define ${\Omega }^p\in \square S^{\prime }$ by $E_{{\Omega }^p}\left[f\right]:={min}_{s\in S}f(p,s)$. That is, ${\Omega }^p$ is an infra-Bayesian representation of the belief “Omega will make prediction $p$”. For any $u\in [0,1]$, define $R^u\in \square S^{\prime }$ by $E_{R^u}\left[f\right]:={min}_{\mu \in \Delta S^{\prime }:E_{\mu }\left[r\right(p,s\left)\right]\ge u}{E}_{\mu }\left[f\right(p,s\left)\right]$. $R^u$ can be interpreted as the belief “assuming Omega is accurate, the expected reward will be at least $u$”.

We will also need to use the order $⪯$ on $\square X$ defined by: $\varphi ⪯\psi$ when $\forall f\in [0,1{]}^X:E_{\varphi }[f]\ge E_{\psi }[f]$. The reversal is needed to make the analogy to logic intuitive. Indeed, $\varphi ⪯\psi$ can be interpreted as ”$\varphi$ implies $\psi$“^[2], the meet operator $\wedge$ can be interpreted as logical conjunction and the join operator $\vee$ can be interpreted as logical disjunction.

Claim:

$a^{\ast }=\arg {max}_{a\in A}max\{u\in [0,1]\mid {\beta }^{\prime }\wedge {\Omega }^a⪯R^u\}$

(Actually I only checked it when we restrict to crisp infradistributions, in which case $\wedge$ is intersection of sets and $⪯$ is set containment, but it’s probably true in general.)

Now, ${\beta }^{\prime }\wedge {\Omega }^a⪯R^u$ can be interpreted as “the conjunction of the belief ${\beta }^{\prime }$ and ${\Omega }^a$ implies $R^u$”. Roughly speaking, “according to ${\beta }^{\prime }$, if the predicted action is $a$ then the expected reward is at least $u$”. So, our decision rule says: choose the action that maximizes the value for which this logical implication holds (but “holds” is better thought of as “is provable”, since we’re talking about the agent’s belief). Which is exactly the decision rule of MUDT!

---

1. ↩︎

   Apologies for the potential confusion between $\square$ as “space of infradistrubutions” and the $\square$ of modal logic (not used in this post).

2. ↩︎

   Technically it’s better to think of it as ”$\psi$ is true in the context of $\varphi$”, since it’s not another infradistribution so it’s not a genuine implication operator.

[Vanessa Kosoy]

Master post for ideas about infra-Bayesian physicalism.

Other relevant posts:

• Incorrigibility in IBP

• PreDCA alignment protocol

[Vanessa Kosoy]

Here is a modification of the IBP framework which removes the monotonicity principle, and seems to be more natural in other ways as well.

First, let our notion of “hypothesis” be $\Theta \in {\square }^c(\Gamma \times 2^{\Gamma })$. The previous framework can be interpreted in terms of hypotheses of this form satisfying the condition

$${pr}_{\Gamma \times 2^{\Gamma }}Br\left(\Theta \right)=\Theta$$

(See Proposition 2.8 in the original article.) In the new framework, we replace it by the weaker condition

$$Br\left(\Theta \right)\supseteq ({id}_{\Gamma }\times {diag}_{2^{\Gamma }}{)}_{\ast }\Theta$$

This can be roughly interpreted as requiring that (i) whenever the output of a program P determines whether some other program Q will run, program P has to run as well (ii) whenever programs P and Q are logically equivalent, program P runs iff program Q runs.

The new condition seems to be well-justified, and is also invariant under (i) mixing hypotheses (ii) taking joins/​meets of hypotheses. The latter was not the case for the old condition. Moreover, it doesn’t imply that $\Theta$ is downward closed, and hence there is no longer a monotonicity principle^[1].

The next question is, how do we construct hypotheses satisfying this condition? In the old framework, we could construct hypotheses of the form $\Xi \in {\square }^c(\Gamma \times \Phi )$ and then apply the bridge transform. In particular, this allows a relatively straightforward translation of physics theories into IBP language (for example our treatment of quantum theory). Luckily, there is an analogous construction in the new framework as well.

First notice that our new condition on $\Theta$ can be reformulated as requiring that

• $supp\Theta \subseteq {el}^{\Gamma }$

• For any $s:\Gamma \to \Gamma$ define ${\tau }_s:{\Delta }^c{el}^{\Gamma }\to {\Delta }^c{el}^{\Gamma }$ by ${\tau }_s\theta :={\chi }_{{el}^{\Gamma }}(s\times {id}_{2^{\Gamma }}{)}_{\ast }$. Then, we require ${\tau }_s\Theta \subseteq \Theta$.

For any $\Phi$, we also define ${\tau }_s^{\Phi }:{\Delta }^c({el}^{\Gamma }\times \Phi )\to {\Delta }^c({el}^{\Gamma }\times \Phi )$ by

$${\tau }_s^{\Phi }\theta :={\chi }_{{el}^{\Gamma }\times \Phi }(s\times {id}_{2^{\Gamma }\times \Phi }{)}_{\ast }$$

Now, for any $\Xi \in {\square }^c(\Gamma \times \Phi )$, we define the “conservative bridge transform^[2]” $CBr\left(\Xi \right)\in {\square }^c(\Gamma \times 2^{\Gamma }\times \Phi )$ as the closure of all ${\tau }_s^{\Phi }\theta$ where $\theta$ is a maximal element of $Br\left(\Xi \right).$ It is then possible to see that $\Theta \in {\square }^c(\Gamma \times 2^{\Gamma })$ is a valid hypothesis if and only if it is of the form ${pr}_{\Gamma \times 2^{\Gamma }}CBr\left(\Xi \right)$ for some $\Phi$ and $\Xi \in {\square }^c(\Gamma \times \Phi )$.

1. ^

   I still think the monotonicity principle is saying something about the learning theory of IBP which is still true in the new framework. Namely, it is possible to learn that a program is running but not possible to (confidently) learn that a program is not running, and this limits the sort of frequentist guarantees we can expect.

2. ^

   Intuitively, it can be interpreted as a version of the bridge transform where we postulate that a program doesn’t run unless $\Xi$ contains a reason while it must run.

[Vanessa Kosoy]

Two thoughts about the role of quining in IBP:

• Quine’s are non-unique (there can be multiple fixed points). This means that, viewed as a prescriptive theory, IBP produces multi-valued prescriptions. It might be the case that this multi-valuedness can resolve problems with UDT such as Wei Dai’s 3-player Prisoner’s Dilemma and the anti-Newcomb problem^[1]. In these cases, a particular UDT/​IBP (corresponding to a particular quine) loses to CDT. But, a different UDT/​IBP (corresponding to a different quine) might do as well as CDT.

• What to do about agents that don’t know their own source-code? (Arguably humans are such.) Upon reflection, this is not really an issue! If we use IBP prescriptively, then we can always assume quining: IBP is just telling you to follow a procedure that uses quining to access its own (i.e. the procedure’s) source code. Effectively, you are instantiating an IBP agent inside yourself with your own prior and utility function. On the other hand, if we use IBP descriptively, then we don’t need quining: Any agent can be assigned “physicalist intelligence” (Definition 1.6 in the original post, can also be extended to not require a known utility function and prior, along the lines of ADAM) as long as the procedure doing the assigning knows its source code. The agent doesn’t need to know its own source code in any sense.

1. ^

   @Squark is my own old LessWrong account.

[Vanessa Kosoy]

Physicalist agents see themselves as inhabiting an unprivileged position within the universe. However, it’s unclear whether humans should be regarded as such agents. Indeed, monotonicity is highly counterintuitive for humans. Moreover, historically human civilization struggled a lot with accepting the Copernican principle (and is still confused about issues such as free will, anthropics and quantum physics which physicalist agents shouldn’t be confused about). This presents a problem for superimitation.

What if humans are actually cartesian agents? Then, it makes sense to consider a variant of physicalist superimitation where instead of just seeing itself as unprivileged, the AI sees the user as a privileged agent. We call such agents “transcartesian”. Here is how this can be formalized as a modification of IBP.

In IBP, a hypothesis is specified by choosing the state space $\Phi$ and the belief $\Theta \in \square (\Gamma \times \Phi )$. In the transcartesian framework, we require that a hypothesis is augmented by a mapping $\tau :\Phi \to (A_0\times O_0{)}^{\le \omega }$, where $A_0$ is the action set of the reference agent (user) and $O_0$ is the observation set of the reference agent. Given $G_0$ the source code of the reference agent, we require that $\Theta$ is supported on the set

$$\left\{\right(y,x)\in \Gamma \times \Phi |ha⊑\tau \left(x\right)⟹a=G_0^y\left(h\right)\}$$

That is, the actions of the reference agent are indeed computed by the source code of the reference agent.

Now, instead of using a loss function of the form $L:{el}^{\Gamma }\to R$, we can use a loss function of the form $L:(A_0\times O_0{)}^{\le \omega }\to R$ which doesn’t have to satisfy any monotonicity constraint. (More generally, we can consider hybrid loss functions of the form $L:(A_0\times O_0{)}^{\le \omega }\times {el}^{\Gamma }\to R$ monotonic in the second argument.) This can also be generalized to reference agents with hidden rewards.

As opposed to physicalist agents, transcartesian agents do suffer from penalties associated with the description complexity of bridge rules (for the reference agent). Such an agent can (for example) come to believe in a simulation hypothesis that is unlikely from a physicalist perspective. However, since such a simulation hypothesis would be compelling for the reference agent as well, this is not an alignment problem (epistemic alignment is maintained).

[Vanessa Kosoy]

Up to light editing, the following was written by me during the “Finding the Right Abstractions for healthy systems” research workshop, hosted by Topos Institute in January 2023. However, I invented the idea before.

In order to allow $R$ (the set of programs) to be infinite in IBP, we need to define the bridge transform for infinite $\Gamma$. At first, it might seem $\Gamma$ can be allowed to be any compact Polish space, and the bridge transform should only depend on the topology on $\Gamma$, but that runs into problems. Instead, the right structure on $\Gamma$ for defining the bridge transform seems to be that of a “profinite field space”: a category I came up with that I haven’t seen in the literature so far.

The category $PFS$ of profinite field spaces is defined as follows. An object $F$ of $PFS$ is a set $ind\left(F\right)$ and a family of finite sets ${F_{\alpha }}_{\alpha \in ind\left(F\right)}$. We denote $Tot\left(F\right):={\prod }_{\alpha }{F}_{\alpha }$. Given $F$ and $G$ objects of $PFS$, a morphism from $F$ to $G$ is a mapping $f:Tot\left(F\right)\to Tot\left(G\right)$ such that there exists $R\subseteq ind\left(F\right)\times ind\left(G\right)$ with the following properties:

• For any $\alpha \in ind\left(F\right)$, the set $R\left(\alpha \right):=\beta \in ind\left(G\right)\mid (\alpha ,\beta )\in R$ is finite.

• For any $\beta \in ind\left(G\right)$, the set $R^{-1}\left(\beta \right):=\alpha \in ind\left(F\right)\mid (\alpha ,\beta )\in R$ is finite.

• For any $\beta \in ind\left(G\right)$, there exists a mapping $f_{\beta }:{\prod }_{\alpha \in R^{-1}\left(\beta \right)}{F}_{\alpha }\to G_{\beta }$ s.t. for any $x\in Tot\left(F\right)$, $f(x{)}_{\beta }:=f_{\beta }({pr}_{\beta }^R\left(x\right))$ where ${pr}_{\beta }^R:Tot\left(F\right)\to {\prod }_{\alpha \in R^{-1}\left(\beta \right)}{F}_{\alpha }$ is the projection mapping.

The composition of $PFS$ morphisms is just the composition of mappings.

It is easy to see that every $PFS$ morphism is a continuous mapping in the product topology, but the converse is false. However, the converse is true for objects with finite $ind$ (i.e. for such objects any mapping is a morphism). Hence, an object $F$ in $PFS$ can be thought of as $Tot\left(F\right)$ equipped with additional structure that is stronger than the topology but weaker than the factorization into $F_{\alpha }$.

The name “field space” is inspired by the following observation. Given $F$ an object of $PFS$, there is a natural condition we can impose on a Borel probability distribution on $Tot\left(F\right)$ which makes it a “Markov random field” (MRF). Specifically, $\mu \in \Delta Tot\left(F\right)$ is called an MRF if there is an undirected graph $G$ whose vertices are $ind\left(F\right)$ and in which every vertex is of finite degree, s.t.$\mu$ is an MRF on $G$ in the obvious sense. The property of being an MRF is preserved under pushforwards w.r.t.$PFS$ morphisms.

[Vanessa Kosoy]

Infra-Bayesian physicalism is an interesting example in favor of the thesis that the more qualitatively capable an agent is, the less corrigible it is. (a.k.a. “corrigibility is anti-natural to consequentialist reasoning”). Specifically, alignment protocols that don’t rely on value learning become vastly less safe when combined with IBP:

• Example 1: Using steep time discount to disincentivize dangerous long-term plans. For IBP, “steep time discount” just means, predominantly caring about your source code running with particular short inputs. Such a goal strongly incentives the usual convergent instrumental goals: first take over the world, then run your source code with whatever inputs you want. IBP agents just don’t have time discount in the usual sense: a program running late in physical time is just as good as one running early in physical time.

• Example 2: Debate. This protocol relies on a zero-sum game between two AIs. But, the monotonicity principle rules out the possibility of zero-sum! (If $L$ and $-L$ are both monotonic loss functions then $L$ is a constant). So, in a “debate” between IBP agents, they cooperate to take over the world and then run the source code of each debater with the input “I won the debate”.

• Example 3: Forecasting/​imitation (an IDA in particular). For an IBP agent, the incentivized strategy is: take over the world, then run yourself with inputs showing you making perfect forecasts.

The conclusion seems to be, it is counterproductive to use IBP to solve the acausal attack problem for most protocols. Instead, you need to do PreDCA or something similar. And, if acausal attack is a serious problem, then approaches that don’t do value learning might be doomed.

[Vanessa Kosoy]

Infradistributions admit an information-theoretic quantity that doesn’t exist in classical theory. Namely, it’s a quantity that measures how many bits of Knightian uncertainty an infradistribution has. We define it as follows:

Let $X$ be a finite set and $\Theta$ a crisp infradistribution (credal set) on $X$, i.e. a closed convex subset of $\Delta X$. Then, imagine someone trying to communicate a message by choosing a distribution out of $\Theta$. Formally, let $Y$ be any other finite set (space of messages), $\theta \in \Delta Y$ (prior over messages) and $K:Y\to \Theta$ (communication protocol). Consider the distribution $\eta :=\theta ⋉K\in \Delta (Y\times X)$. Then, the information capacity of the protocol is the mutual information between the projection on $Y$ and the projection on $X$ according to $\eta$, i.e. $I_{\eta }({pr}_X;{pr}_Y)$. The “Knightian entropy” of $\Theta$ is now defined to be the maximum of $I_{\eta }({pr}_X;{pr}_Y)$ over all choices of $Y$, $\theta$, $K$. For example, if $\Theta$ is Bayesian then it’s $0$, whereas if $\Theta ={\top }_X$, it is $\ln |X|$.

Here is one application^[1] of this concept, orthogonal to infra-Bayesianism itself. Suppose we model inner alignment by assuming that some portion $ϵ$ of the prior $\zeta$ consists of malign hypotheses. And we want to design e.g. a prediction algorithm that will converge to good predictions without allowing the malign hypotheses to attack, using methods like confidence thresholds. Then we can analyze the following metric for how unsafe the algorithm is.

Let $O$ be the set of observations and $A$ the set of actions (which might be “just” predictions) of our AI, and for any environment $\tau$ and prior $\xi$, let $D_{\tau }^{\xi }\left(n\right)\in \Delta (A\times O{)}^n$ be the distribution over histories resulting from our algorithm starting with prior $\xi$ and interacting with environment $\tau$ for $n$ time steps. We have $\zeta =ϵ\mu +(1-ϵ)\beta$, where $\mu$ is the malign part of the prior and $\beta$ the benign part. For any ${\mu }^{\prime }$, consider $D_{\tau }^{ϵ{\mu }^{\prime }+(1-ϵ)\beta }\left(n\right)$. The closure of the convex hull of these distributions for all choices of ${\mu }^{\prime }$ (“attacker policy”) is some ${\Theta }_{\tau }^{\beta }\left(n\right)\in \Delta (A\times O{)}^n$. The maximal Knightian entropy of ${\Theta }_{\tau }^{\beta }\left(n\right)$ over all admissible $\tau$ and $\beta$ is called the malign capacity of the algorithm. Essentially, this is a bound on how much information the malign hypotheses can transmit into the world via the AI during a period of $n$. The goal then becomes finding algorithms with simultaneously good regret bounds and good (in particular, at most polylogarithmic in $n$) malign capacity bounds.

---

1. ↩︎

   This is an idea I’m collaborating on with Johannes Treutlein.

[Vanessa Kosoy]

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.

We will work with homogenous ultracontributions (HUCs). $\square X$ will denote the space of HUCs over $X$. Given $\mu \in \square X$, $S\left(\mu \right)\subseteq {\Delta }^{c}X$ will denote the corresponding convex set. 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:

• ${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$

• ${\wedge }_{\alpha }\in F_{\left(\alpha \right)\times \left(\alpha \right)\to \left(\alpha \right)}^0$ [EDIT: Actually this doesn’t work because, except for finite sets, the resulting mapping (see semantics section) is discontinuous. There are probably ways to fix this.]

• ${\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$ [EDIT: Actually this doesn’t work because, except for finite sets, the resulting mapping (see semantics section) is discontinuous. There are probably ways to fix this.]

• Assume that for each $n\in N$ there is some $D_n\subseteq \square \left[n\right]$: the set of “describable” ultracontributions [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 ultracontributions 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:

• $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 ultradistribution 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)$

• $S\left(M\right(\wedge \left)\right(\mu ,\nu \left)\right)$ is the intersection 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 for all $q\in {\Delta }^c(X\times Y)$, if ${pr}_{\ast }q=p$ then $q:\mu$.

• $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 )$.

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

[Vanessa Kosoy]

Let’s also explicitly describe 0th order and 1st order infra-Bayesian logic (although they are should be 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 $\varphi ,\psi \in L$, $\varphi \wedge \psi \in L$

• Given $\varphi ,\psi \in L$, $\varphi \vee \psi \in L$

Notice there’s no negation or implication. We define the set of judgements $J:=L\times L$. We write judgements as $\varphi ⊢\psi$ (”$\psi$ in the context of $\varphi$”). 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(\varphi \wedge \psi )=M\left(\varphi \right)\wedge M\left(\psi \right)$. Here, we define $\wedge$ of infradistributions as intersection of the corresponding sets

• $M(\varphi \vee \psi )=M\left(\varphi \right)\vee M\left(\psi \right)$. Here, we define $\vee$ of infradistributions as convex hull of the corresponding sets

• For any $\varphi ⊢\psi \in T$, $M\left(\varphi \right)⪯M\left(\psi \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 quantifiers $\forall$ and $\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 $\varphi \in L_v$ where $v_1\dots v_n$ have types $t_1\dots t_n$, an element $M_v\left(\varphi \right)$ of $\square X_v$, where $X_v:=\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(\varphi \wedge \psi )=M_v\left(\varphi \right)\wedge M_v\left(\psi \right)$

• $M_v(\varphi \vee \psi )=M_v\left(\varphi \right)\vee M_v\left(\psi \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 m\}\to \{1\dots n\}$ s.t. $s_i=t_{\sigma i}$. Given $\varphi \in L_v$, we can form the substitution $\psi :=\varphi [v_i=u_{\sigma \left(i\right)}]\in L_u$. We also have a mapping $f_{\sigma }:X_u\to X_v$ given by $f_{\sigma }(x_1\dots x_n)=(x_{\sigma \left(1\right)}\dots x_{\sigma \left(m\right)})$. We require $M_u\left(\psi \right)=f^{\ast }\left(M_v\right(\varphi \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:\varphi )={pr}_{\ast }\left(M_v\right(\varphi \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 that $p:M_{v\setminus v_i}(\forall v_i:\varphi )$ if an only if, for all $q\in \Delta X_v$ s.t ${pr}_{\ast }q=p$, $q:{pr}_{\ast }\left(M_v\right(\varphi \left)\right)$

• For any $\varphi ⊢\psi \in T$, $M_v\left(\varphi \right)⪯M_v\left(\psi \right)$

[Vanessa Kosoy]

There is a special type of crisp infradistributions that I call “affine infradistributions”: those that, represented as sets, are closed not only under convex linear combinations but also under affine linear combinations. In other words, they are intersections between the space of distributions and some closed affine subspace of the space of signed measures. Conjecture: in 0-th order logic of affine infradistributions, consistency is polynomial-time decidable (whereas for classical logic it is ofc NP-hard).

To produce some evidence for the conjecture, let’s consider a slightly different problem. Specifically, introduce a new semantics in which $\square X$ is replaced by the set of linear subspaces of some finite dimensional vector space $V$. A model $M$ is required to satisfy:

• $M\left(\perp \right)=0$

• $M\left(\top \right)=V$

• $M(\varphi \wedge \psi )=M\left(\varphi \right)\cap M\left(\psi \right)$

• $M(\varphi \vee \psi )=M\left(\varphi \right)+M\left(\psi \right)$

• For any $\varphi ⊢\psi \in T$, $M\left(\varphi \right)\subseteq M\left(\psi \right)$

If you wish, this is “non-unitary quantum logic”. In this setting, I have a candidate polynomial-time algorithm for deciding consistency. First, we transform $T$ into an equivalent theory s.t. all judgments are of the following forms:

• $a=\perp$

• $a=\top$

• $a⊢b$

• Pairs of the form $c=a\wedge b$, $d=a\vee b$.

Here, $a,b,c,d\in A$ are propositional variables and “$\varphi =\psi$” is a shorthand for the pair of judgments $\varphi ⊢\psi$ and $\psi ⊢\varphi$.

Second, we make sure that our $T$ also satisfies the following “closure” properties:

• If $a⊢b$ and $b⊢c$ are in $T$ then so is $a⊢c$

• If $c=a\wedge b$ is in $T$ then so are $c⊢a$ and $c⊢b$

• If $c=a\vee b$ is in $T$ then so are $a⊢c$ and $b⊢c$

• If $c=a\wedge b$, $d⊢a$ and $d⊢b$ are in $T$ then so is $d⊢c$

• If $c=a\vee b$, $a⊢d$ and $b⊢d$ are in $T$ then so is $c⊢d$

Third, we assign to each $a\in A$ a real-valued variable $x_a$. Then we construct a linear program for these variables consisting of the following inequalities:

• For any $a\in A$: $0\le x_a\le 1$

• For any $a⊢b$ in $T$: $x_a\le x_b$

• For any pair $c=a\wedge b$ and $d=a\vee b$ in $T$: $x_c+x_d=x_a+x_b$

• For any $a=\perp$: $x_a=0$

• For any $a=\top$: $x_a=1$

Conjecture: the theory is consistent if and only if the linear program has a solution. To see why it might be so, notice that for any model $M$ we can construct a solution by setting

$$x_a:=\frac{dimM\left(a\right)}{dimM\left(\top \right)}$$

I don’t have a full proof for the converse but here are some arguments. If a solution exists, then it can be chosen to be rational. We can then rescale it to get integers which are candidate dimensions of our subspaces. Consider the space of all ways to choose subspaces of these dimensions s.t. the constraints coming from judgments of the form $a⊢b$ are satisfied. This is a moduli space of poset representations. It is easy to see it’s non-empty (just let the subspaces be spans of vectors taken from a fixed basis). By Proposition A.2 in Futorny and Iusenko it is an irreducible algebraic variety. Therefore, to show that we can also satisfy the remaining constraints, it is enough to check that (i) the remaining constraints are open (ii) each of the remaining constraints (considered separately) holds at some point of the variety. The first is highly likely and the second is at least plausible.

The algorithm also seems to have a natural extension to the original infra-Bayesian setting.

[Vanessa Kosoy]

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.

[Vanessa Kosoy]

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.

[Vanessa Kosoy]

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

[Vanessa Kosoy]

Master post for ideas about metacognitive agents.

[Vanessa Kosoy]

Sort of obvious but good to keep in mind: Metacognitive regret bounds are not easily reducible to “plain” IBRL regret bounds when we consider the core and the envelope as the “inside” of the agent.

Assume that the action and observation sets factor as $A=A_0\times A_1$ and $O=O_0\times O_1$, where $(A_0,O_0)$ is the interface with the external environment and $(A_1,O_1)$ is the interface with the envelope.

Let $\Lambda :\Pi \to \square (\Gamma \times (A\times O{)}^{\omega })$ be a metalaw. Then, there are two natural ways to reduce it to an ordinary law:

• Marginalizing over $\Gamma$. That is, let ${pr}_{-\Gamma }:\Gamma \times (A\times O{)}^{\omega }\to (A\times O{)}^{\omega }$ and ${pr}_0:(A\times O{)}^{\omega }\to (A_0\times O_0{)}^{\omega }$ be the projections. Then, we have the law ${\Lambda }^{?}:=({pr}_0{pr}_{-\Gamma }{)}_{\ast }\circ \Lambda$.

• Assuming “logical omniscience”. That is, let ${\tau }^{\ast }\in \Gamma$ be the ground truth. Then, we have the law ${\Lambda }^{!}:={pr}_{0\ast }(\Lambda \mid {\tau }^{\ast })$. Here, we use the conditional defined by $\Theta \mid A:=\{\theta \mid A\mid \theta \in \arg {max}_{\Theta }Pr[A\left]\right\}$. It’s easy to see this indeed defines a law.

However, requiring low regret w.r.t. neither of these is equivalent to low regret w.r.t $\Lambda$:

• Learning ${\Lambda }^{?}$ is typically no less feasible than learning $\Lambda$, however it is a much weaker condition. This is because the metacognitive agents can use policies that query the envelope to get higher guaranteed expected utility.

• Learning ${\Lambda }^{!}$ is a much stronger condition than learning $\Lambda$, however it is typically infeasible. Requiring it leads to AIXI-like agents.

Therefore, metacognitive regret bounds hit a “sweep spot” of stength vs. feasibility which produces a genuinely more powerful agents than IBRL^[1].

1. ^

   More precisely, more powerful than IBRL with the usual sort of hypothesis classes (e.g. nicely structured crisp infra-RDP). In principle, we can reduce metacognitive regret bounds to IBRL regret bounds using non-crsip laws, since there’s a very general theorem for representing desiderata as laws. But, these laws would have a very peculiar form that seems impossible to guess without starting with metacognitive agents.

[Vanessa Kosoy]

Formalizing the richness of mathematics

Intuitively, it feels that there is something special about mathematical knowledge from a learning-theoretic perspective. Mathematics seems infinitely rich: no matter how much we learn, there is always more interesting structure to be discovered. Impossibility results like the halting problem and Godel incompleteness lend some credence to this intuition, but are insufficient to fully formalize it.

Here is my proposal for how to formulate a theorem that would make this idea rigorous.

(Wrong) First Attempt

Fix some natural hypothesis class for mathematical knowledge, such as some variety of tree automata. Each such hypothesis $\Theta$ represents an infradistribution over $\Gamma$: the “space of counterpossible computational universes”. We can say that $\Theta$ is a “true hypothesis” when there is some $\theta$ in the credal set $\Theta$ (a distribution over $\Gamma$) s.t. the ground truth ${{\rm Y}}^{\ast }\in \Gamma$ “looks” as if it’s sampled from $\theta$. The latter should be formalizable via something like a computationally bounded version of Marin-Lof randomness.

We can now try to say that ${{\rm Y}}^{\ast }$ is “rich” if for any true hypothesis $\Theta$, there is a refinement $\Xi \subseteq \Theta$ which is also a true hypothesis and “knows” at least one bit of information that $\Theta$ doesn’t, in some sense. This is clearly true, since there can be no automaton or even any computable hypothesis which fully describes ${{\rm Y}}^{\ast }$. But, it’s also completely boring: the required $\Xi$ can be constructed by “hardcoding” an additional fact into $\Theta$. This doesn’t look like “discovering interesting structure”, but rather just like brute-force memorization.

(Wrong) Second Attempt

What if instead we require that $\Xi$ knows infinitely many bits of information that $\Theta$ doesn’t? This is already more interesting. Imagine that instead of metacognition /​ mathematics, we would be talking about ordinary sequence prediction. In this case it is indeed an interesting non-trivial condition that the sequence contains infinitely many regularities, s.t. each of them can be expressed by a finite automaton but their conjunction cannot. For example, maybe the $n$-th bit in the sequence depends only the largest $k$ s.t.$2^k$ divides $n$, but the dependence on $k$ is already uncomputable (or at least inexpressible by a finite automaton).

However, for our original application, this is entirely insufficient. This is because in the formal language we use to define $\Gamma$ (e.g. combinator calculus) has some “easy” equivalence relations. For example, consider the family of programs of the form “if 2+2=4 then output 0, otherwise...”. All of those programs would output 0, which is obvious once you know that 2+2=4. Therefore, once your automaton is able to check some such easy equivalence relations, hardcoding a single new fact (in the example, 2+2=4) generates infinitely many “new” bits of information. Once again, we are left with brute-force memorization.

(Less Wrong) Third Attempt

Here’s the improved condition: For any true hypothesis $\Theta$, there is a true refinement $\Xi \subseteq \Theta$ s.t. conditioning $\Theta$ on any finite set of observations cannot produce a refinement of $\Xi$.

There is a technicality here, because we’re talking about infradistributions, so what is “conditioning” exactly? For credal sets, I think it is sufficient to allow two types of “conditioning”:

• For any given observation $A$ and $p\in (0,1]$, we can form $\{\theta \in \Theta \mid \theta (A)\ge p\}$.

• For any given observation $A$ s.t. ${min}_{\theta \in \Theta }\theta \left(A\right)>0$, we can form $\left\{\right(\theta \mid A)\mid \theta \in \Theta \}$.

This rules-out the counterexample from before: the easy equivalence relation can be represented inside $\Theta$, and then the entire sequence of “novel” bits can be generated by a conditioning.

Alright, so does ${{\rm Y}}^{\ast }$ actually satisfy this condition? I think it’s very probable, but I haven’t proved it yet.

[Vanessa Kosoy]

Recording of a talk I gave in VAISU 2023.

[Vanessa Kosoy]

Here is the sketch of a simplified model for how a metacognitive agent deals with traps.

Consider some (unlearnable) prior $\zeta$ over environments, s.t. we can efficiently compute the distribution $\zeta \left(h\right)$ over observations given any history $h$. For example, any prior over a small set of MDP hypotheses would qualify. Now, for each $h$, we regard $\zeta \left(h\right)$ as a “program” that the agent can execute and form beliefs about. In particular, we have a “metaprior” $\xi$ consisting of metahypotheses: hypotheses-about-programs.

For example, if we let every metahypothesis be a small infra-RDP satisfying appropriate assumptions, we probably have an efficient “metalearning” algorithm. More generally, we can allow a metahypothesis to be a learnable mixture of infra-RDPs: for instance, there is a finite state machine for specifying “safe” actions, and the infra-RDPs in the mixture guarantee no long-term loss upon taking safe actions.

In this setting, there are two levels of learning algorithms:

• The metalearning algorithm, which learns the correct infra-RDP mixture. The flavor of this algorithm is RL in a setting where we have a simulator of the environment (since we can evaluate $\zeta \left(h\right)$ for any $h$). In particular, here we don’t worry about exploitation/​exploration tradeoffs.

• The “metacontrol” algorithm, which given an infra-RDP mixture, approximates the optimal policy. The flavor of this algorithm is “standard” RL with exploitation/​exploration tradeoffs.

In the simplest toy model, we can imagine that metalearning happens entirely in advance of actual interaction with the environment. More realistically, the two needs to happen in parallel. It is then natural to apply metalearning to the current environmental posterior rather than the prior (i.e. the histories starting from the history that already occurred). Such an agent satisfies “opportunistic” guarantees: if at any point of time, the posterior admits a useful metahypothesis, the agent can exploit this metahypothesis. Thus, we address both parts of the problem of traps:

• The complexity-theoretic part (subproblem 1.2) is addressed by approximating the intractable Bayes-optimality problem by the metacontrol problem of the (coarser) metahypothesis.

• The statistical part (subproblem 2.1) is addressed by opportunism: if at some point, we can easily learn something about the physical environment, then we do.

[Vanessa Kosoy]

Jobst Heitzig asked me whether infra-Bayesianism has something to say about the absent-minded driver (AMD) problem. Good question! Here is what I wrote in response:

Philosophically, I believe that it is only meaningful to talk about a decision problem when there is also some mechanism for learning the rules of the decision problem. In ordinary Newcombian problems, you can achieve this by e.g. making the problem iterated. In AMD, iteration doesn’t really help because the driver doesn’t remember anything that happened before. We can consider a version of iterated AMD where the driver has a probability $0<ϵ\ll 1$ to remember every intersection, but they always remember whether they arrived at the right destination. Then, it is equivalent to the following Newcombian problem:

• With probability $1-2ϵ$, counterfactual A happens, in which Omega decides about both intersections via simulating the driver in counterfactuals B and C.

• With probability $ϵ$, counterfactual B happens, in which the driver decides about the first intersection, and Omega decides about the second intersection via simulating the driver in counterfactual C.

• With probability $ϵ$, counterfactual C happens, in which the driver decides about the second intersection, and Omega decides about the first intersection via simulating the driver in counterfactual B.

For this, an IB agent indeed learns the updateless optimal policy (although the learning rate carries an ${ϵ}^{-1}$ penalty).

[Vanessa Kosoy]

The following was written by me during the “Finding the Right Abstractions for healthy systems” research workshop, hosted by Topos Institute in January 2023. However, I invented the idea before.

Here’s an elegant diagrammatic notation for constructing new infrakernels out of given infrakernels. There is probably some natural category-theoretic way to think about it, but at present I don’t know what it is.

By “infrakernel” we will mean a continuous mapping of the form $X\to \square Y$, where $X$ and $Y$ are compact Polish spaces and $\square Y$ is the space of credal sets (i.e. closed convex sets of probability distributions) over $Y$.

Syntax

• The diagram consists of child vertices, parent vertices, squiggly lines, arrows, dashed arrows and slashes.

• There can be solid arrows incoming into the diagram. Each such arrow $a$ is labeled by a compact Polish space $D\left(a\right)$ and ends on a parent vertex $t\left(a\right)$. And, $s\left(a\right)=\perp$ (i.e. the arrow has no source vertex).

• There can be dashed and solid arrows between vertices. Each such arrow $a$ starts from a child vertex $s\left(a\right)$ and ends on a parent vertex $t\left(a\right)$. We require that $P\left(s\right(a\left)\right)\ne t\left(a\right)$ (i.e. they should not be also connected by a squiggly line).

• There are two types of vertices: parent vertices (denoted by a letter) and child vertices (denoted by a letter or number in a circle).

  • Each child vertex $v$ is labeled by a compact Polish space $D\left(v\right)$ and connected (by a squiggly line) to a unique parent vertex $P\left(v\right)$. It may or may not be crossed-out by a slash.

  • Each parent vertex $p$ is labeled by an infrakernel $K_p$ with source $S_1\times \dots \times S_k$ and target $T_1\times \dots \times T_l$ where each $S_i$ is corresponds to a solid arrow $a$ with $t\left(a\right)=p$ and each $T_j$ is $D\left(v\right)$ for some child vertex $v$ with $P\left(v\right)=p$. We can also add squares with numbers where solid arrows end to keep track of the correspondence between the arguments of $K_p$ and the arrows.

    • If $s\left(a\right)=\perp$ then the corresponding $S_i$ is $D\left(a\right)$.

    • If $s\left(a\right)=v\ne \perp$ then the corresponding $S_i$ is $D\left(v\right)$.

Semantics

• Every diagram $D$ represents an infrakernel $K_D$.

  • The source space of $K_D$ is a product $X_1\times \dots \times X_n$, where each $X_i$ is $D(a$) for some solid arrow $a$ with $s\left(a\right)=\perp$.

  • The target space of $K_D$ is a product $Y_1\times \dots \times Y_m$, where each $Y_j$ is $D\left(v\right)$ for some non-crossed-out child vertex.

• The value of the $K_D$ at a given point $x$ is defined as follows. Let $\tilde{Y}:={\prod }_{v}D\left(v\right)$ (a product that includes the cross-out vertices). Then, $K_D\left(x\right)$ is the set of all the marginal distributions of distributions $\mu \in \Delta \tilde{Y}$ satisfying the following condition. Consider any parent vertex $p$. Let $a_1,a_2\dots a_k$ be the (dashed or solid) arrows s.t.$s\left(a_i\right)\ne \perp$ and $t\left(a_i\right)=p$. For each $i$ s.t., choose any $y_i\in D\left(s\right(a_i\left)\right)$. We require that $K_p(x,y)$ contains the marginal distribution of $\mu \mid y$. Here, the notation $K_p(x,y)$ means we are using the components of $x$ and $y$ corresponding to solid arrows $a$ with $t\left(a\right)=p$.

[Vanessa Kosoy]

Two deterministic toy models for regret bounds of infra-Bayesian bandits. The lesson seems to be that equalities are much easier to learn than inequalities.

Model 1: Let $A$ be the space of arms, $O$ the space of outcomes, $r:A\times O\to R$ the reward function, $X$ and $Y$ vector spaces, $H\subseteq X$ the hypothesis space and $F:A\times O\times H\to Y$ a function s.t. for any fixed $a\in A$ and $o\in O$, $F(a,o):H\to Y$ extends to some linear operator $T_{a,o}:X\to Y$. The semantics of hypothesis $h\in H$ is defined by the equation $F(a,o,h)=0$ (i.e. an outcome $o$ of action $a$ is consistent with hypothesis $h$ iff this equation holds).

For any $h\in H$ denote by $V\left(h\right)$ the reward promised by $h$:

$$V\left(h\right):=\underset{a\in A}{max}\underset{o\in O:F(a,o,h)=0}{min}r(a,o)$$

Then, there is an algorithm with mistake bound $\dim X$, as follows. On round $n\in N$, let $G_n\subseteq H$ be the set of unfalsified hypotheses. Choose $h_n\in S$ optimistically, i.e.

$$h_n:=\arg \underset{h\in G_n}{max}V\left(h\right)$$

Choose the arm $a_n$ recommended by hypothesis $h_n$. Let $o_n\in O$ be the outcome we observed, $r_n:=r(a_n,o_n)$ the reward we received and $h^{\ast }\in H$ the (unknown) true hypothesis.

If $r_n\ge V\left(h_n\right)$ then also $r_n\ge V\left(h^{\ast }\right)$ (since $h^{\ast }\in G_n$ and hence $V\left(h^{\ast }\right)\le V\left(h_n\right)$) and therefore $a_n$ wasn’t a mistake.

If $r_n<V\left(h_n\right)$ then $F(a_n,o_n,h_n)\ne 0$ (if we had $F(a_n,o_n,h_n)=0$ then the minimization in the definition of $V\left(h_n\right)$ would include $r(a_n,o_n)$). Hence, $h_n\notin G_{n+1}=G_n\cap \ker T_{a_n,o_n}$. This implies $\dim span\left(G_{n+1}\right)<\dim span\left(G_n\right)$. Obviously this can happen at most $\dim X$ times.

Model 2: Let the spaces of arms and hypotheses be

$$A:=H:=S^d:=\{x\in R^{d+1}\mid \parallel x\parallel =1\}$$

Let the reward $r\in R$ be the only observable outcome, and the semantics of hypothesis $h\in S^d$ be $r\ge h\cdot a$. Then, the sample complexity cannot be bound by a polynomial of degree that doesn’t depend on $d$. This is because Murphy can choose the strategy of producing reward $1-ϵ$ whenever $h\cdot a\le 1-ϵ$. In this case, whatever arm you sample, in each round you can only exclude ball of radius $\approx \sqrt{2ϵ}$ around the sampled arm. The number of such balls that fit into the unit sphere is $\Omega \left({ϵ}^{-\frac{1}{2}d}\right)$. So, normalized regret below $ϵ$ cannot be guaranteed in less than that many rounds.

[Vanessa Kosoy]

One of the postulates of infra-Bayesianism is the maximin decision rule. Given a crisp infradistribution $\Theta$, it defines the optimal action to be:

$$a^{\ast }\left(\Theta \right):=\arg \underset{a}{max}\underset{\mu \in \Theta }{min}{E}_{\mu }\left[U\right(a\left)\right]$$

Here $U$ is the utility function.

What if we use a different decision rule? Let $t\in [0,1]$ and consider the decision rule

$$a_t^{\ast }\left(\Theta \right):=\arg \underset{a}{max}\left(t\underset{\mu \in \Theta }{min}{E}_{\mu }\right[U\left(a\right)]+(1-t\left)\underset{\mu \in \Theta }{max}{E}_{\mu }\right[U\left(a\right)\left]\right)$$

For $t=1$ we get the usual maximin (“pessimism”), for $t=0$ we get maximax (“optimism”) and for other values of $t$ we get something in the middle (we can call “$t$-mism”).

It turns out that, in some sense, this new decision rule is actually reducible to ordinary maximin! Indeed, set

$${\mu }_t^{\ast }:=\arg \underset{\mu }{max}{E}_{\mu }\left[U\right(a_t^{\ast }\left)\right]$$

$${\Theta }_t:=t\Theta +(1-t){\mu }_t^{\ast }$$

Then we get

$$a^{\ast }\left({\Theta }_t\right)=a_t^{\ast }\left(\Theta \right)$$

More precisely, any pessimistically optimal action for ${\Theta }_t$ is $t$-mistically optimal for $\Theta$ (the converse need not be true in general, thanks to the arbitrary choice involved in ${\mu }_t^{\ast }$).

To first approximation it means we don’t need to consider $t$-mistic agents since they are just special cases of “pessimistic” agents. To second approximation, we need to look at what the transformation of $\Theta$ to ${\Theta }_t$ does to the prior. If we start with a simplicity prior then the result is still a simplicity prior. If $U$ has low description complexity and $t$ is not too small then essentially we get full equivalence between “pessimism” and $t$-mism. If $t$ is small then we get a strictly “narrower” prior (for $t=0$ we are back at ordinary Bayesianism). However, if $U$ has high description complexity then we get a rather biased simplicity prior. Maybe the latter sort of prior is worth considering.