Attacking the grain of truth problem using Bayes-Savage agents

[Vanessa Kosoy]

Motivated by the grain of truth problem, we propose a generalization of Bayesian inference that allows for incomplete models. Such a model can be thought of as a set of constraints on the environment which doesn’t specify it completely. This means that in addition to ordinary (probabilistic) uncertainty, another (“Knightian”) type of uncertainty is introduced. This new uncertainty is managed using Savage’s minimax regret decision rule.

Motivation

The grain of truth problem, as described by Hutter (see problem 5j) concerns the interaction between several AIXI agents. Ideally, we expect that rational agents in multi-agent scenarios should converge to behavior corresponding to some reasonable solution concept in game theory, e.g. Nash equilibrium (for the purposes of this post I completely ignore stronger desiderata such as superrationality; also purely Bayesian agents often fail to do so because of insufficient exploration but this is also a problem mostly orthogonal to grain of truth). However, it is difficult to prove anything about multi-agent scenarios of AIXI since AIXI’s prior is supported on computable environments whereas AIXI itself is uncomputable. This problem survives in bounded analogues: if we limit the computational complexity of environments included in the prior, the computational complexity of the agent itself will invariably be higher. Thus, two agents of equal power seem unable to “comprehend” each other.

There are several reasons this problems seem important to AI alignment:

1. The ability of an agent to operate in environments of complexity similar to that of the agent or even surpassing that of the agent seems an important desideratum for the mathematical formalization of intelligence. Without a formal understanding how this desideratum can be satisfied it is difficult to imagine any reliable theory of intelligent agents.

2. Arguably, self-improving agents need the capacity to understand systems that equal to themselves in complexity, more or less by definition.

3. Perhaps most importantly, IRL relies on the AI’s ability to successfully reason about a complex agent (a human), presumably an agent that cannot be emulated precisely with the AI’s computational power. CIRL relies on two-sided interaction between the AI and the human, where neither side can emulate the other. Thus, it seems impossible to prove reasonable guarantees for (C)IRL under quasi-realistic assumptions without solving the grain of truth problem.

To the best of our knowledge, the most serious attack on the problem to date is the work of Leike, Taylor and Fallenstein. They prove that Thompson samplers relatively to a reflective oracle converge to an “asymptotic” Nash equilibrium. In our opinion, it should be possible to extent that work to ensure subgame perfect and even proper equilibria and, under some assumptions, allow for “tamer” forms of exploration than Thompson sampling (Thompson sampling necessarily sacrifices many horizons until convergence). There is no doubt reflective oracles constitute significant progress towards the solution, in the sense that they clearly demonstrate the grain of truth problem is not inherently unsolvable and provide a formal framework where agents satisfying this desideratum can be studied. Nevertheless, we retain skepticism regarding the prospect of reaching the ultimate solution through developing that approach.

In our opinion, there are 3 ways in which reflective oracles are an unsatisfactory solution:

1. There are many different reflective oracles. In multi-agent scenarios, all results rely on all agents using the same reflective oracle. Realistic agents cannot use uncomputable oracles so they will have to replace them by some sort of bounded analogues. However, there is every reason to suspect these bounded analogues will also be far from unique. Thus, it’s not clear that interaction between agents using different brands of “bounded reflective oracles” will have any substantial guarantees. In fact, this lack of uniqueness seems directly related to the lack of uniqueness for Nash equilibria. Any solution for the grain of truth will have to solve equilibrium selection, but reflective oracles seem to “cheat” by implicitly selecting Nash equilibria for all possible games in advance. A more realistic model should imply some sort of negotiation process which will probably need some non-trivial assumptions to converge.

2. Multi-agent scenarios are a test case for the ability to reason about environments more complex than the agent itself, but the latter is more general than the former. We expect reasonable multi-agent behavior to arise as a special cases of some broad capability, useful in a great variety of other scenarios. However, it is not clear what physically realistic environments except multi-agent scenarios benefit from reasoning with reflective oracles. If there are few such environments, we would have to admit that either reflective oracles are an unsatisfactory model or that realistic agents need to be designed qualitatively differently in order to manage multi-agent scenarios as opposed to all other complex scenarios. In other words, in the latter case there would be uncontrived examples of AIs that solve almost any problem better than humans (including proving theorems, discovering physics, inventing nanotechnology, von Neumann probes and Dyson spheres) but that fail miserably in games. This possibility, although not impossible, appears to us less likely than the alternative.

3. Reflective oracles are uncomputable, although they were proven to be limit computable. Obviously realistic agents use algorithms that are not only computable but satisfy rather stringent complexity bounds.

Of the problems above, 3 seems to be the least significant since it is plausible that bounded analogues can be constructed. In any case, in our formalism it also entirely unobvious how to construct computationally feasible agents. Problem 1 might be solved if a natural class of reflective oracles is found s.t. any agent that is computable w.r.t. any oracle $O_1$ in this class is also computable w.r.t. any other oracle $O_2$ in this class, at least approximately. This is not impossible but also not straightforward. Problem 2 might be the hardest.

Incomplete Models

Although an agent cannot simulate another agent of equal power without entering an infinite loop, it might be able to observe certain facts about the other agent’s behavior. This calls for a notion of an incomplete model: a model of the environment that doesn’t yield precise probabilistic predictions but provides some constraints on what might happen.

To give a trivial example, given a sequence of two bits $b_1{b}_2$, the model might say that $b_1=\neg b_2$ without assigning any probability to $b_1=0$. Knowing only this model one has unquantifiable (Knightian) uncertainty between the possibilities $01$ and $10$. The space of probability distributions on two bit sequences is a tetrahedron, and our model corresponds to one edge of this tetrahedron.

More generally, we have some measurable event space $X$ and $\Delta X$ is the space of probability measures on $X$. A complete (Bayesian) model corresponds to some $\mu \in \Delta X$. An incomplete model corresponds to some convex set $\Phi \subseteq \Delta X$ (which can be assumed closed in the strong convergence topology). If we assign probability $p$ to model $\mu$ and $1-p$ to model $\nu$, this can be represented by the model $p\mu +(1-p)\nu$. Similarly, if we assign probability $p$ to model $\Phi$ and probability $1-p$ to model $\Psi$, this can be represented by the model

$$p\Phi +(1-p)\Psi :=\{p\mu +(1-p)\nu \mid \mu \in \Phi ,\nu \in \Psi \}$$

In ordinary Bayesian statistics, a prior is often specified by a some countable space $H$ of hypotheses (i.e. for each $x\in H$ we have ${\mu }_x\in \Delta X$; more generally $H$ can be some measurable space with a Markov kernel into $X$, but we won’t need that) and a probability measure $\zeta$ on $H$, so that the prior is $E_{x\in \zeta }\left[{\mu }_x\right]$. Similarly, we can have ${\Phi }_x\subseteq \Delta X$ and the incomplete prior

$$E_{x\in \zeta }\left[{\Phi }_x\right]:=\left\{E_{h\in \zeta }\right[{\mu }_x]\mid \mu :H\to \Delta X,\forall x\in H:{\mu }_x\in {\Phi }_x\}$$

Now consider an agent interacting with an unknown environment. The agent has a finite set $A$ of actions and a finite set $O$ of percepts. The event space is the space of “pure” (deterministic) environments $E:=(O\times A{)}^{\ast }\to O$ (its $\sigma$-algebra comes from viewing it as the inverse limit of the sequence $(O\times A{)}^{\le n}\to O$). In this context we don’t usually work with the full space of “mixed” environments $\Delta E$ but only with the quotient space of “behavioral” environments ${\Delta }_{b}E$. Here, every $\mu \in {\Delta }_{b}E$ is a partial function from $(O\times A{)}^{\ast }$ to $\Delta O$ s.t.$\mu \left(h\right)$ is defined iff $\mu$ assigns positive probability to all percepts appearing in $h$. For every $\mu \in \Delta E$, we define the corresponding ${\mu }_b\in {\Delta }_{b}E$ by

$$\mathrm{Pr}\left[{\mu }_b\right(h)=o]:={\mathrm{Pr}}_{e\sim \mu }\left[e\right(h)=o\mid \forall i\in [\left|h\right|]:h_i^O=e(h_{0:i-1}\left)\right]$$

Here, $\left|h\right|$ is defined by $h\in (O\times A{)}^{\left|h\right|}$ and $h_i^O\in O$ stands for the first element of the pair $h_i\in O\times A$. Note that the operation of taking convex linear combinations in $\Delta E$ descends to a well-defined operation in ${\Delta }_{b}E$ which we will also regard as convex linear combination (but which is not the same as taking pointwise convex linear combinations of the partial functions; instead it can be written as the result of Bayesian updating).

Priors are usually constructed from environments that are in some sense computable. There are several variants of the definition, but we will consider environments that can be represented as

$$M:(O\times A{)}^{\ast }\times \{0,1{\}}^{\omega }\stackrel{\text{alg}}{\to }O$$

Here, $\{0,1{\}}^{\omega }$ is regarded as an infinite sequence of fair coin flips and the notation $\stackrel{\text{alg}}{\to }$ means that $M$ is a Turing machine that halts with probability 1 for any fixed $h\in (O\times A{)}^{\ast }$ and $r\in \{0,1{\}}^{\omega }$ a sequence of fair coin flips. The corresponding environment is defined by

$$\mathrm{Pr}\left[{\mu }_M\right(h)=o]:={\mathrm{Pr}}_{r\sim U^{\omega }}\left[M\right(h,r)=o]$$

Here $U^{\omega }$ is the fair coin probability measure on $\{0,1{\}}^{\omega }$ (it is easy to see that the set $\{r\in \{0,1{\}}^{\omega }\mid M(h,r)=o\}$ is measurable because $M$ is a Turing machine).

Fix $U$ a prefix-free universal Turing machine and denote $H^U\subseteq \{0,1{\}}^{\ast }$ the set of programs that satisfy the halting condition above. We have $\zeta \in \Delta H^U$ defined by

$$\zeta \left(x\right):=\frac{2^{-\left|x\right|}}{{\sum }_{y\in H^U}{2}^{-\left|y\right|}}$$

For any $x\in H^U$, we can define the environment ${\mu }_x^U$:

$$Pr\left[{\mu }_x^U\right(h)=o]:={\mathrm{Pr}}_{r\sim U^{\omega }}\left[U\right(x;h,r)=o]$$

We can now define the universal prior ${\mu }^U:=E_{x\sim \zeta }\left[{\mu }_x^U\right]$.

Alternatively, we can consider environments that have an unobservable state. For any $\nu \in {\Delta }_{b}E$ we denote the domain of $\nu$ by $(O\times A{)}_{\nu }^{\ast }$. An computable environment with unobservable state corresponds to a machine

$$M:(O\times A{)}^{\ast }\times N\times \{0,1{\}}^{\omega }\stackrel{\text{alg}}{\to }O\times N$$

The corresponding ${\mu }_M\in {\Delta }_{b}E$ is defined recursively, simultaneously with ${\rho }_M:(O\times A{)}_{{\mu }_M}^{\ast }\to \Delta N$, the latter describing the probability distribution on unobservable states. Denoting ${\lambda }_{O\times A}$ the empty element of $(O\times A{)}^{\ast }$:

$${\rho }_M\left({\lambda }_{O\times A}\right):={\delta }_0$$

$$\mathrm{Pr}\left[{\mu }_M\right(h)=o]:={\mathrm{Pr}}_{\begin{array}{c}u\sim {\rho }_M\left(h\right)\\ r\sim U^{\omega }\end{array}}\left[M\right(h,u,r{)}^O=o]$$

$$\mathrm{Pr}\left[{\rho }_M\right(hoa)=u]:={\mathrm{Pr}}_{\begin{array}{c}v\sim {\rho }_M\left(h\right)\\ r\sim U^{\omega }\end{array}}\left[M\right(h,v,r{)}^{\{0,1{\}}^{\ast }}=u\mid M(h,v,r{)}^O=o]$$

For arbitrary computable environments the addition of an unobservable state gains us nothing. However, it makes a difference when imposing complexity bounds.

We now generalize these concepts to incomplete models. A computable incomplete model corresponds to an oracle machine

$$M:(O\times A{)}^{\ast }\times \{0,1{\}}^{\omega }\stackrel{\text{or}}{\to }O$$

We require that the machine halts with probability 1 for any oracle. The values returned by the oracle represent “Knightian coin flips.” For any $K\subseteq N$, we can define ${\mu }_{MK}\in {\Delta }_{b}E$ by

$$\mathrm{Pr}\left[{\mu }_{MK}\right(h)=o]:={\mathrm{Pr}}_{r\sim U^{\omega }}\left[M^K\right(h,r)=o]$$

The notation $M^K$ signifies we are running the machine $M$ with the oracle $K$.

We define the incomplete model

$${\Phi }_M:=\left\{E_{K\sim \xi }\right[{\mu }_{MK}]\mid \xi \in \Delta 2^N\}$$

The $\sigma$-algebra on $2^N$ is defined by regarding it as an infinite product: $2^N\cong {\prod }_{n\in N}\{0,1\}$.

Taking $\overline{U}$ a universal oracle machine and $H^{\overline{U}}$ the set of programs for $\overline{U}$ that satisfy the our halting condition, we can define ${\Phi }_x\subseteq {\Delta }_{b}E$ for any $x\in H^{\overline{U}}$ in the obvious way. We define $\overline{\zeta }\in \Delta H^{\overline{U}}$ by

$$\overline{\zeta }\left(x\right):=\frac{2^{-\left|x\right|}}{{\sum }_{y\in H^{\overline{U}}}{2}^{-\left|y\right|}}$$

This allows us defining the “universal incomplete prior” ${\Phi }^{\overline{U}}:=E_{x\in \overline{\zeta }}\left[{\Phi }_x\right]$.

We also can represent computable incomplete models with unobservable states

$$M:(O\times A{)}^{\ast }\times N\times \{0,1{\}}^{\omega }\stackrel{\text{or}}{\to }O\times N$$

${\Phi }_M$ is defined analogously.

It is straightforward to impose complexity bounds on these objects, e.g. by limiting the time, space, number of random coins or number of oracle queries $M$ is allowed to use as a function of $\left|h\right|$.

Hutter observes that it’s unknown whether Solomonoff induction can correctly predict relationships betweens bits in a sequence that contains uncomputable information (see problem 4g). To deal with similar issues in online learning one can use “sleeping experts” (see also subsequence induction). Here, we deal with much more general scenarios than sleeping experts by including incomplete models in our prior.

Bayes-Savage Agents

Consider an agent that has to choose from a finite strategy set $S$. The utility function of the agent is $u:S\times X\to R$. If the agent’s beliefs are described by a complete model $\mu \in \Delta X$, the standard decision rule is maximizing expected utility:

$$s\left(\mu \right):=\underset{s\in S}{argmax}{E}_{w\sim \mu }\left[u\right(s,w\left)\right]$$

For an incomplete model $\Phi \subseteq \Delta X$, we propose using the minimax regret decision rule:

$$s\left(\Phi \right):=\underset{s\in \Delta S}{argmax}\underset{\mu \in \Phi }{min}\left(E_{w\sim \mu }\right[u(s,w)]-\underset{t\in S}{max}{E}_{w\sim \mu }[u(t,w)\left]\right)$$

We call agents following this rule “Bayes-Savage” agents.

Note that we lost nothing by requiring $\Phi$ to be convex since the minimum in the above equation is of a concave function and therefore is always attained in an extreme point (so if we started from a non-convex subset of $\Delta X$, we might as well have replaced it with its convex hull).

As opposed to expected utility maximization, minimax regret might demand randomization. This is perhaps not surprising since if we expect our agents to produce Nash equilibria, there must be randomization in their decision rule (e.g. in reflective oracles this randomization comes from the oracle itself). In fact, this decision rule can be interpreted as selecting a Nash equilibrium in a game where the strategies of the opponent (who we dub Metanoia) are $\mu \in \Phi$, the agent’s utility function is $E_{w\sim \mu }\left[u\right(s,w\left)\right]$ and Metanoia’s utility function is the agent’s regret

$$R(s,\mu ):=\underset{t\in S}{max}{E}_{w\sim \mu }\left[u\right(t,w\left)\right]-E_{w\sim \mu }\left[u\right(s,w\left)\right]$$

Equivalently (i.e. yielding the same Nash equilibria), we can make it a zero-sum game by taking negative regret to be the agent’s utility function (it makes no difference since the other term depends only on Metanoia). Note that the $\mu$ attaining the minimum is not the Nash equilibrium strategy for the Metanoia but only a pure best response to a Nash equilibrium: the former would be a mixed strategy.

In most interesting settings the agent’s strategy involves making a sequence of actions between which it receives additional information. The strategy of a Bayesian agent in this case can be regarded as performing a Bayesian update after each observation and computing and optimal policy for the rest of time using the maximal expected utility rule applied to the posterior. On the other hand, the policy of a Bayes-Savage agent cannot be decomposed in this way, i.e., the policy after making an observation is not the result of applying the minimax regret rule to the incomplete posterior. We deal with this “dynamic inconsistency” simply by requiring the entire policy to be determined in advance (“updatelessly”). In practical implementations we will likely need some approximate decoupling from distant “branches” in order to make the algorithm feasible, but we leave this issue for later.

In the sequential setting, the Metanoia game is naturally regarded as having extensive form. In particular, the Nash equilibrium condition is too weak to always ensure reasonable behavior, since there might be agent information sets that are never reached in Nash equilibrium. Therefore, we need to make the decision rule more stringent by requiring e.g. quasi-perfect or proper equilibrium. We leave working out the details for later.

As a simple example for a setting where the minimax regret rule yields reasonable behavior, consider a stochastic $k$-armed bandit played for $n$ time steps. Here $X=R^{kn}$, each $w\in X$ representing a vector of payoffs for all arms and time steps.$\Phi$ is the convex hull of all i.i.d. distributions satisfying an appropriate moment condition. Clearly the minimax regret rule leads to behavior qualitatively similar to the UCB algorithm (at least assuming the correct handling of special information sets as suggested above).

This stands in sharp contrast to the minimax decision rule:

$$s_{\text{mm}}\left(\Phi \right):=\underset{s\in \Delta S}{argmax}\underset{\mu \in \Phi }{min}{E}_{w\sim \mu }\left[u\right(s,w\left)\right]$$

The latter leads to undefined behavior for stochastic bandits since there is no way to guarantee any payoff above the minimum, even if good payoffs were observed on previous time steps.

Finally, a Bayes-Savage agent for ${\Phi }^{\overline{U}}$ is a natural counterpart of AIXI in this setting. We hope that for these agents strong game-theoretic guarantees can be derived.

Discussion

We think that there is a reasonable chance the concepts outlined in this essay can lead to solving the grain of truth problem. This will require much further work. Specifically, we suggest to continue the research in approximately the following order:

• Better understanding of minimax regret in the sequential setting, including the definition of quasi-perfect or proper strategies.

• Proving convergence of Bayes-Savage agents to policies satisfying appropriate regret guarantees. That is, given an environment $\mu$ that does not appear explicitly in the prior but which satisfies $\mu \in \Phi$ for $\Phi$ that appears in the prior, we expect the agent to converge to a policy $\pi$ whose loss w.r.t. the best response ${\pi }_{\mu }$ to $\mu$ is no greater than the maximin regret for $\Phi$.

• Better understanding the relationship of the minimax regret rule to game theory e.g. whether the minimax regret rule can allow a better justification of Nash equilibria than best response (i.e. in a Nash equilibrium all strategies are best responses but not all best responses preserve the Nash equilibrium; maybe minimax regret allows doing better?)

• Deriving game-theoretic guarantees for AIXI-like Bayes-Savage agents from the generic regret guarantees above. Presumably, this requires for each agent in the game describing a specific computable incomplete model consistent with the behavior of the other agents (which cannot be complete but should be sufficiently strong in some sense). In general, we expect being able to prove e.g. convergence to iteratively undominated strategies under fairly general conditions and convergence to Nash equilibria (preferably e.g. proper equilibria) under some assumptions on the game (e.g. time discount falling sufficiently slowly).

• Looking for Bayes-Savage agents of bounded complexity. Here the algorithm by Koller and Megiddo for two-player zero-sum extensive games with perfect recall might be relevant (in our case the game tree is at least exponentially big w.r.t. horizon length, but such inefficient agents can be a good starting point towards understand bounded agents in general).