TLDR: I give an overview of (i) the key problems that the learning-theoretic AI alignment research agenda is trying to solve, (ii) the insights we have so far about these problems and (iii) the research directions I know for attacking these problems. I also describe "Physicalist Superimitation" (previously knows as "PreDCA"): a hypothesized alignment protocol based on infra-Bayesian physicalism that is designed to reliably learn and act on the user's values.

I wish to thank Steven Byrnes, Abram Demski, Daniel Filan, Felix Harder, Alexander Gietelink Oldenziel, John S. Wentworth^[1] and my spouse Marcus Ogren for reviewing a draft of this article, finding errors and making helpful comments and suggestions. Any remaining flaws are entirely my fault. 

Preamble

I already described the learning-theoretic agenda (henceforth LTA) in 2018. While the overall spirit stayed similar, naturally LTA has evolved since then, with new results and research directions, and slightly different priorities. This calls for an updated exposition.

There are several reasons why I decided that writing this article is especially important at this point:

• Most of the written output of LTA focuses on the technical, mathy side. This leaves people confused about the motivation for those inquiries, and how they fit into the big picture. I find myself having to explain it again and again in private conversations, and it seems more efficient to have a written reference.
• In particular, LTA is often conflated with infra-Bayesianism. While infra-Bayesianism is a notable part, it is not the only part, and without context it's not even clear why it is relevant to alignment.
• Soares has recently argued that alignment researchers don't "stack", meaning that it doesn't help much to add more researchers to the same programme. I think that for LTA, this is not at all the case. On the contrary, there is a variety of shovel-ready problems that can be attacked in parallel. With this in mind, it's especially important to explain LTA in order to get more people on board.
• In particular, ALTER has announced a prize designed to encourage work on LTA. I expect this article to be a useful resource for researchers who decide to compete.
• It seemed important to explain Physicalist Superimitation better, and this is hard to do without the broader context.

I am fairly optimistic that LTA leads to a solution to alignment. On the other hand, it's much harder to say whether the solution will arrive in time. I think that the rate of progress relative to person-hours invested was pretty good so far, and we didn't hit any obstacle that cast doubt on the entire endeavor. At the same time, in absolute terms we still have most of the work in front of us. In the coming years, I am planning to put considerable effort into scaling up: getting more researchers on board, and hopefully accelerating progress by a significant factor.

Philosophy

The philosophy of LTA was covered in the original article, I mostly stand behind what I wrote there and don't want to repeat it. The goal of this section is merely to recap and add a couple of points.

The goal of LTA is creating a general mathematical theory of intelligent agents. There are a number of reasons why this is necessary for AI alignment:

• Having a mathematical theory enables constructing models in which we can prove that a particular AI design is aligned (or unaligned), or at least form rigorous and strongly supported conjectures (similar to the role $P\ne NP$ in cryptography). While such a proof doesn't imply absolute confidence, it does allow us to reduce the problem to becoming confident in the assumptions of the model. This is a much better situation than dealing with a sequence of heuristic steps, each of which might be erroneous and/or hiding assumptions that are not stated clearly. Of course, similarly to how in cybersecurity having a provably secure protocol doesn't protect you from e.g. someone using their birthday for a password, here too we will need to meticulously verify that the assumptions hold in the actual implementation. This might require knowledge from domains outside of theoretical computer science, e.g. physics, cognitive science, evolutionary biology etc.
• Empirical data is insufficient in itself, since without an underlying theory it's very hard to be confident about how the results extrapolate to new domains, scales, architectures and algorithms. On the other hand, the combination of theory and experiment can be extremely powerful for such extrapolation, even if the theory cannot produce quantitative predictions ab initio on its own.
• Even if we don't do any explicit calculations using the theory about the AI we are designing, merely knowing the theory leads to much better intuitions, and equips us with the right vocabulary to reason about the problem. To give an analogy, it is much easier to reason about designing engines if you're familiar with concepts such as "heat", "work", "temperature", "entropy", even if you're just reasoning informally rather than actually calculating.

After I wrote the original article about LTA, more was written about the feasibility and importance of mathematics for alignment, both by me and by others.

Why is LTA concerned specifically with agents? Aren't there AI systems which are not agents? The reason is: the sort of risks I want to address are risks that arise from AIs displaying agentic behavior (i.e. building sophisticated models of the world and using these models to construct plans that pursue unaligned goals, with catastrophic consequences), and the sort of solution I envision also relies on AIs displaying agentic behavior (i.e. building sophisticated models of the world and using these models to construct plans that pursue an aligned goal, s.t. the result is protecting humanity from unaligned AI).

Finally, I want to address a common point of confusion. Sometimes I tell someone about subproblems in LTA and they respond by trying to understand why each individual subproblem (e.g. nonrealizability, or cartesian privilege, or value ontology) is relevant to alignment. Often there are some specific ways in which the subproblem can be connected to alignment. But the more important point is that any fundamental question about intelligent agency is relevant to alignment, just because without answering this question we cannot understand intelligent agency. For any aspect of intelligent agency that we don't understand and any AI that we design, one of the two will hold: either the AI lacks this aspect, in which case it is probably insufficient to protect humanity, or the AI has this aspect but we don't understand why or how, in which case it is probably unaligned (because alignment is a small target, and significant unaccounted for phenomena are likely to make you miss).

Key Problems

The starting point of LTA is Marcus Hutter's AIXI: a simplistic model of ideal agency.

Intuitively, an "intelligent agent" is a system that builds sophisticated models of the world and uses them to construct and execute plans that lead to particular goals (see also Yudkwosky). Building models implies starting from a state of ignorance and updating on observations, which can be formalized by Bayesian probability theory. Building sophisticated models requires using Occam's razor, which can be formalized by the Solomonoff prior. Constructing and executing plans can be formalized as maximizing expected utility. Putting all these ingredients together gives us AIXI.

However, there are both important gaps both in our understanding of AIXI-like agents, and significant weaknesses in the AIXI framework itself. Solving these problems is the natural framing for the entire foundational^[2] part of LTA.

Problem 1: Computational Resource Constraints

AIXI is uncomputable. Obviously, real-world agents are not only computable but operate under strong computational resource constraints. This doesn't mean AIXI is not a useful toy model for studying the interaction of Occam's razor with Bayesian optimization or reinforcement learning. However, it is a major limitation.

One obvious attempted solution is to impose some computational resource constraints on the programs that appear in Solomonoff's prior, for example as in Schmidhuber's speed prior or in some other way. This typically leads to agents that are computable but still computationally intractable. Relatedly, a recent line of research connects the hardness of time-bounded Kolmogorov complexity with the existence of one-way functions.

On the other hand, we know some priors for which asymptotic Bayes-optimality is possible in polynomial time, for example priors supported on Markov decision processes (MDPs) with a small (i.e. polynomial in the security parameter) number of states. Some stronger feasible models are also known, e.g. MDPs with linear features or kernel-MDPs. However, all such priors have significant shortcomings:

• They require the MDP to be communicating, i.e. contain no irreversible transitions (a.k.a. "traps"). This is obviously not true in the real-world, where e.g. jumping off a cliff is often irreversible. Indeed, without this assumption approximating the Bayes-optimal policy is NP-hard, even for a small number of deterministic hypotheses.
• They usually don't embody any sort of Occam's razor.
• They are not rich enough to capture sophisticated models of the real world.

Problem 2: Frequentist Guarantees

AIXI is Bayes-optimal (by definition) but is not necessarily optimal in any sense for any particular environment. In contrast, in statistical learning theory we usually demand a frequentist guarantee, i.e. that a learning algorithm converges to optimality (in some sense) for any^[3] data source (subject to some assumptions which depend on the setting). Such guarantees are important for several reasons:

• Learning is a key ability of intelligent agents, and played a fundamental role in AI progress in recent decades. A natural way to operationalize learning is: an agent learned a fact when its behavior is optimal conditional on this fact. In other words, learning which of a set of hypotheses is true means converging to optimal behavior for the true hypothesis, i.e. precisely a frequentist guarantee. This means that a theory of frequentist guarantees tell us both which facts agents can learn and how fast they learn them (or how much data they require to learn them). These are important questions that a theory of intelligent agents has to answer. In particular, it is required to analyze the feasibility of alignment protocols: e.g. if we expect the AI to learn human values, we need to make sure it has sufficient information to learn them within a practical time frame.
• A Bayes-optimal algorithm does well on average across some large ensemble of possible universes. But in reality, we only observe one universe (which is not even in the ensemble: see Subproblem 2.3 below). Without frequentist guarantees, it's not clear why would a Bayes-optimal algorithm do especially well in our specific universe, or why should algorithms that do well in our specific universe be Bayes-optimal.
• Evolution selected humans by their performance in the ancestral environment, which involved e.g. gathering berries and running away from lions. But they turned out to perform reasonably well in very different environments that require e.g. writing code or designing rockets. This hints at the existence of some underlying frequentist guarantee as a key property of intelligent agents.

Moreover, in addition to single-agent frequentist guarantees it is desirable to derive multi-agent frequentist guarantees. Interactions between agents are quite important in the real-world, and have significance specifically for AI alignment as well (AI-human, AI-other AI, AI-acausal trade partner, to some extent human-human too). A multi-agent frequentist guarantee can take the form of convergence to a particular game-theoretic solution concept, or an asymptotic lower bound on expected utilities corresponding to some notion of game value.

There are multiple difficulties in deriving frequentist guarantees for AIXI-like agents. The first two difficulties ("traps" and "password guessing games" below) are not problems with the agent, but rather with the way conventional frequentist guarantees are defined (which are nonetheless non-trivial to solve). The third difficulty (nonrealizability) might be a problem with the way the agent is defined.

Subproblem 2.1: Traps

The most common type of frequentist guarantee in reinforcement learning (RL) is regret bounds^[4]. However, AIXI doesn't satisfy any regret bound w.r.t. the underlying hypothesis class (i.e. the class of all computable environments) because these hypotheses involve irreversible transitions (traps). For example, suppose that in environment 1 taking action A sends you to a sink state with reward $-1$, whereas taking action B sends you to a sink state with reward $+1$, and in environment 2 the opposite is true. Obviously a hypothesis class which contains both environments doesn't admit a regret bound.

This problem is especially acute in the multi-agent setting, because other agents have memory. Either it's impossible to erase memory in which case the environment is irreversible by design, or it's possible to erase memory which breaks conventional learning theory in other ways.

Subproblem 2.2: Password guessing games

What if we arbitrarily rule out traps? Consider an agent with action set $A$ and observation set $O$. Suppose that the reward is a function of the last observation only $r:O\to R$. We can specify an environment^[5] $\mu :(O\times A{)}^{\ast }\to \Delta O$ by providing a communicating MDP with state set $S$ and action set $B$ augmented by representation mappings

Here, $\alpha \left(ha\right)$ is required to be an onto mapping from $A$ to $B$ for any $h\in (O\times A{)}^{\ast }\times O$. Also, we require that for any $h\in (O\times A{)}^{\ast }$ and $o\in O$

However, this only enables a fairly weak regret bound. Naively, it seems reasonable to expect a regret bound of the form $\tilde{O}\left(K^{\alpha }{\tau }^{\beta }{T}^{\delta }\right)$ where $K$ is the Kolmogorov complexity of the MDP+representation, $\tau$ is the diameter^[6] and $T$ is the time horizon^[7], and $\alpha ,\beta ,\delta$ are constants s.t. $\delta <1$. Indeed, $K$ can be regarded as the amount of information that needs to be learned and e.g. Russo and Van Roy showed that in a bandit setting regret scales as the square root of the entropy of the prior (which also expresses the amount of information to be learned). However, this is impossible, as can be seen from the following example.

Fix $n\in N$ and $p\in \{0,1{\}}^{n+1}$ (the "password"), let the action set be $B:=\{0,1\}$ and the state space be $S:=\{0,1{\}}^{\le n}\bigsqcup \top$. We think of a state $s\in \{0,1{\}}^{\le n}$ as "the agent entered the string of bits $s$ into the terminal". The initial state is $ϵ$ (the empty string). The transition kernel works as follows:

In state $s\in \{0,1{\}}^{<n}$, taking action $i$ produces the state $si$ (i.e. the agent enters the digit $i$). In state $s\in \{0,1{\}}^n$, taking action $i$ produces the state $\top$ if $si=p$ (the agent entered the correct password) or state $ϵ$ (the agent entered an incorrect password and has to start from the beginning). In state $\top$ taking action $0$ stays in state $\top$ and taking action $1$ produces state $ϵ$ (restarts the game).

All states have reward $0$ except for the state $\top$ which has reward $1$.

Obviously the agent needs time $2^n$ to learn the correct password, in expectation w.r.t. the uniform distribution over passwords. At the same time, $K\approx n$ and $\tau =n+1$. This is incompatible with having a regret bound of the desired form.

Subproblem 2.3: Nonrealizability

As we discussed in Problem 1, a realistic agent cannot be Bayes-optimal for a prior over all computable environments. Typically, each hypothesis in the prior has to admit a computationally feasible approximately optimal policy in order for it to be feasible to approximate Bayes-optimality (in particular this has to be the case if the prior is learnable), which usually implies the hypotheses are computationally feasible to simulate^[8]. However, in this situation we can no longer assume the true environment is within the hypothesis class. Even for AIXI itself, it is not really fair to assume the environment is computable since that would exclude environments that contain e.g. other AIXIs.

A setting in which the true environment is not in the hypothesis class is known in learning theory as "nonrealizable". For offline (classification/regression) and online learning, there is a rich theory of nonrealizable learning^[9]. However, for RL (which, among classical learning theory frameworks, is the most relevant for agents), the nonrealizable setting is much less understood (although there are some results, e.g. Zanette et al).

Therefore, even if we arbitrarily assume away traps, and are willing to accept a factor of $2^K$ in the regret bound, a satisfactory theory of frequentist guarantees would require good understanding of nonrealizable RL.

This problem is also especially acute in the multi-agent case, because it's rarely the case that each agent is a realizable environment from the perspective of the other agent (roughly speaking, if Alice would simulate Bob simulating Alice, Alice would enter an infinite loop). This is known as the "grain of truth" problem^[10]. One attempt to solve the problem is by Leike, Taylor and Fallenstein, using agents that are equipped with "reflective oracles". However, there are many different reflective oracles, and the solution relies on all agents in the system to use the same one, i.e. that the design of the agents has been essentially centrally coordinated to make them compatible.

Problem 3: Value Ontology

AIXI's utility function depends on its direct observations. This is also assumed in RL theory. While this might be a legitimate type of agent, it is insufficiently general. We can easily imagine agents that place value on parameters they don't directly observe (e.g. the number of paperclips in the observable universe, or the number of people who suffer from malaria). Arguably, humans are such agents.

The obvious workaround is to translate the utility function from its original domain to observations by taking a conditional expectation. That is, suppose the utility function is $U:X\to R$ for some space $X$, let $D$ be the space of everything that is directly observed (e.g. action-observation time sequences) and suppose we have some prior over $X\times D$. Then, we can define $U^{\prime }:D\to R$ by

However, there are problems with this:

• In order to have reasonable computational complexity and frequentist guarantees, we will need to make assumptions about the utility function. While such assumptions can be natural for $U$, they make much less sense for $U^{\prime }$ unless we can somehow justify them via the prior over $X\times D$. Without a theory that explicitly talks about $U$ and $D$ it is impossible to know whether such justification is possible.
• Even if $U^{\prime }$ satisfies the required assumptions, a frequentist guarantee about $U^{\prime }$ does not necessarily imply an analogous frequentist guarantee about $U$. That's because the transformation above involves taking expected value which implicitly mixes different "possible universes", while a frequentist guarantee is supposed to refer to a particular universe.
• Different agents have different observation spaces and there is no natural joint prior on all of them. This means it's impossible to talk about different agents having "aligned" preferences.

Therefore, it is desirable to have a theory in which it is possible to explicitly talk about utility functions with domains other than observations. (See also de Blanc.)

Problem 4: Cartesian Privilege

The formalization of Occam's razor in AIXI relates to the description complexity of hypotheses represented in terms of the agent's actions $A$ and observations $O$ (as functions $(O\times A{)}^{\ast }\to \Delta O$). However, this is not how Occam's razor is used in science. When we talk about a "simple" or "elegant" scientific theory, we refer to the equations governing the fundamental degrees of freedom on that theory (e.g. particles, or fields or strings), not to the equations that would be needed to describe the RGB values of points on a person's retina. Indeed, expressing physics via the latter equations would be horrifically complicated.

In other words, AIXI-like agents believe they occupy a privileged position in the universe, which has various pathological consequences. See "infra-Bayesian physicalism" for more discussion and Demski and Garrabrant for related prior work.

Problem 5: Descriptive Agent Theory

The framing of AIXI is: given certain subjective choices (e.g. universal Turing machine and utility function), what is an ideal agent? However, in the real-world agents are not ideal. Moreover, we want to be able to understand which systems are agents, and what kind of agents they are, without already assuming e.g. a specific utility function. In particular, such a theory would have applications to:

• Value learning, by regarding humans as agents.
• Studying "accidental" formation of agents, e.g. via evolution or as mesa-optimizers (related: Wentworth's selection theorems programme).

Legg and Hutter defined an intelligence measure that for every policy produces a number determining its intelligence, s.t. AIXI has maximal intelligence. The measure is essentially the policy's expected utility w.r.t. the Solomonoff prior. This allows us to talk how close any given system is to an ideal agent. However, it suffers from two major limitations (in addition to the other problems of AIXI discussed before):

• It depends on the choice of universal Turning machine (UTM). While the same is true of everything in algorithmic information theory, usually we have theorems that limit this dependence. For example, Kolmogorov complexity only changes by $O\left(1\right)$ when we switch to a different UTM. On the other hand, the Legg-Hutter measure doesn't have any such property (except in the asymptotic in which it approaches 0, which is pretty meaningless).
• It depends on the choice of utility function. Technically, they don't make an explicit choice but instead assume the reward is one of the observation channels. In practice, this is a choice (and a very restrictive one).

Moreover, naive attempts to ascribe a utility function to a policy run into difficulties. Specifically, any policy can arguably be ascribed a utility function which rewards following precisely this policy. With respect to such a utility function, the policy is Bayes-optimal for any prior. Armstrong and Mindermann have argued on the basis of this type of reasoning that ascribing a utility function is essentially impossible in a purely behaviorist framework (but I argue the opposite, see Direction 17.5 below).

Nonproblem: Expected Utility

Finally, I want to briefly discuss one issue which I don't consider a key problem. Namely, the reliance of AIXI on expected utility maximization.

Expected utility is often justified by coherence theorems such as von Neumann–Morgenstern (VNM) and Savage. These theorems are indeed important: they show that a small number of natural assumptions produce a fairly narrow mathematical object (expected utility). This should indeed increase our credence in expected utility as a useful model. Often, objections are put forward that argue with individual assumptions. IMO these objections miss the point: a coherence theorem is a piece of evidence, not a completely watertight proof that expected utility is philosophically correct. And, if expected utility is philosophically correct, such a watertight proof is still not something we should expect to exist (what would it even look like?)

The more important justification of expected utility is the large body of work it supports: control theory, game theory, reinforcement learning theory etc. The methodology I believe in is, start with plausible assumptions and try to build a theory. If the theory that results is rich, has synergy with other bodies of knowledge, has explanatory power, is useful in practice, each of these is evidence that it's on the right track. (And if we failed to build such a theory, we probably also learned something.)

Another objection that is often raised is "humans have no utility function". This is ostensibly supported by research in behavioral economics which shows that humans behave irrationally. I consider this deeply unconvincing. For one thing, I suspect that a large part of that research doesn't replicate. But even putting that aside, the interesting thing about irrational behavior is that we recognize it as irrational: i.e. learning about it makes you behave differently (unless it's so minor that it isn't worth the effort). This already indicates that this irrationality is better viewed not as a fundamental fact about human preferences, but as some combination of:

• Computational or informational resource constraints
• Error terms that vanish in the relevant asymptotic regime
• Random noise or some other effect that's not part of the cognitive algorithm

All of this is not to say that expected utility cannot be questioned. Rather that a productive objection would be to either come up with a demonstrably superior alternative, or at least a good argument why some extremely concrete problem cannot be solved without an alternative to expected utility. Lacking that, the best strategy is to press forward unless and until we encounter such a problem.

Now, we actually do have examples where deviating from purist VNM in specific ways is useful, e.g.:

• Infra-Bayesianism, where the conventional notion of "expectation" is replaced by some non-linear concave functional.
• Taylor's quantilization, where instead of maximizing expected utility we sample a random choice out of some top fraction of choices.
• Nash bargaining, where we maximize the product of several expected utilities (see also Garrabrant's "geometric rationality" sequence).

However, these examples came about from studying various concrete problems, not from arguing with the VNM model per se. Moreover, all of these examples can still be mathematically recast in VNM form: infra-Bayesianism can be regarded as a VNM zero-sum game (against "Murphy"), quantilization and Nash bargaining can be regarded as special cases of infra-Bayesianism (as will be discussed in an upcoming article by Appel). Therefore, even here the theory built around the VNM model remains useful.

Research Directions

This section focuses entirely on the foundational part of the programme. I will mention some of the applied part in the next section (although different applications are also possible, e.g. studying quantilization or IDA), but for the most part I believe the foundational part to be the top priority.

In the following, I roughly grouped the research directions by the problems they are trying to address. However, the real relationship between directions and problems is many-to-many: a single direction can have implications on many problems. Moreover, there are many connections between the different directions. And, even for directions that are not especially connected at present, if they are successful, we will be faced with the task of merging them into a unified theory.

Subproblem 1.1: Frugal Universal (Infra-)Prior

One part of solving Problem 1 (computational resource constraints) is finding a prior (more precisely a family of priors) with the following properties:

• Formalizes Occam's razor, i.e. assigns higher probability to hypotheses that are simpler to describe.
• Sufficiently rich to contain sophisticated models applicable to the real-world.
• The (approximately) optimal policy for each hypothesis is feasible to find. Possible operationalization of "feasible": polynomial time in history length and description length of hypothesis.
• If we assume away traps, there is a feasible learning algorithm with a good regret bound. Possible operationalization: polynomial time in history length, regret bound similar to what was described in section "Problem 2.2" above. (This desideratum is probably strictly stronger than the previous bullet point.)

More generally, we might want an infra-prior (see Direction 3 below), or a metacognitive (infra-)prior (see Direction 6 below), or a physicalist infra-prior (see Direction 18 below) with analogous properties.

Direction 1: Frugal Compositional Languages

The time complexity of finding the optimal policy for a generic (tabular) MDP scales with its number of states. The same is true of the sample complexity of learning an unknown generic MDP. However, the number of states in a sophisticated model of the real world has to be enormous. For example, if I reason about the world as it's comprised of $n$ objects with $m$ possible states each, the over number of states is already $m^n$.

Therefore, any realistic RL algorithm has to exploit some structure in its environment. For example, the environment might be comprised of spatially separated parts, or different processes happening on different spatial scales, or different processing happening on different temporal scales. We want to find an appropriate compositional language for describing such structure.

The compositional language used by AIXI is that of programs for some fixed UTM. This language is very powerful, but also unfeasible to work with, because programs can consume arbitrarily large amounts of computational resources or even fail to halt altogether. Imposing ad hoc computational resource bounds also doesn't work well, perhaps because such bounds are extraneous to the compositional properties of the language.

Arguably we need some new "frugal" compositional language. Here are the candidate starting points I currently know. It is possible that the right answer will involve combining several of them.

Direction 1.1: Compositional Polytope-MDPs

Compositional polytope-MDPs is a language with two operations: union of asynchronous noninteracting parts and time hierarchy. Importantly, the optimal policy is computable in time polynomial in description length. The time hierarchy operation also offers a natural formalization for the notion of "instrumental values".

Further research might involve:

• Incorporating the state/action representation into the semantics.
• Proving regret bounds for hypotheses classes based on this language, first with arbitrary and then with computationally efficient algorithms.
• Extending the language with more operations.
• Creating an infra-Bayesian version.

Direction 1.2: String Machines (for RL)

String machines is a category-theoretic framework that allows constructing automata and transducers from string diagrams^[11] (that can be probabilistic). In particular, it can be used to describe MDPs. In fact, there is a version of it that allows constructing arbitrary Turing machines, but there are natural ways to "throttle" to expressiveness of the language.

Further research might involve:

• Understanding the expressiveness of the language better, in terms of complexity classes and maybe parameterized complexity classes. [EDIT: See also initial foray using filtered string machines.]
• In particular, understanding how it depends on the categories used.
• Studying control/learning algorithms for hypotheses based on the language.

Direction 1.3: Infra-Bayesian Logic

Infra-Bayesian logic is a sort of higher-order logic where the semantics has infradistributions instead of sets corresponding to predicates, and can be viewed as a synthesis of logic and probability theory. In particular, it is fairly natural for describing infra-(PO)MDPs because the main part of the latter is the transition infrakernel.

However, the semantics are not fully defined because of some technical difficulties. There is also a first-order version which is fully defined but seems less natural for describing RL hypotheses. Finally, there are hints that propositional infra-Bayesian logic might be more computationally tractable than classical propositional logic, but it's as yet unclear.

Direction 2: Deep Learning Theory

It seems plausible that deep learning algorithms (e.g. transformers) are already learning algorithms for the frugal universal prior. Therefore, building a rigorous theory of deep learning (in particular, its inductive biases and generalization properties) is another potential path to understanding this prior and its properties.

While this is a relevant research direction, I don't prioritize it for two reasons:

• It already receives a lot of attention in mainstream academia (some examples, another interesting approach is singular learning theory).
• Substantial breakthroughs here might have major capability implications. (Although this is a consideration that might be relevant to some other directions in LTA as well.)

Nevertheless, it is a type of research that has implications on LTA and alignment researchers can reasonably consider to participate in it, if they feel especially well positioned for it and have the discipline and judgement required to self-censor if necessary.

Subproblem 2.3: Nonrealizability

The research directions below are different ways to get frequentist guarantees in the nonrealizable setting, but they are not necessarily mutually incompatible. In addition to exploring each approach separately, it can be interesting to study various combinations.

Direction 3: Infra-Bayesian RL

Infra-Bayesian RL (IBRL) is a way to combine reinforcement learning theory with imprecise probabilities which produces a specific kind of frequentist guarantee in the nonrealizable setting (infra-Bayesian regret). A rough summary of the results we got in this framework so far:

• There is a dynamically consistent update rule for a notion of imprecise beliefs that generalizes credal sets (infradistributions). This rule is equivalent to the one described by Gilboa and Schmeidler but we represented it using different mathematical language (concave functional or convex set, related by Legendre-Fenchel duality, instead of an order on functions).
• Newcombian environments (where naive causality is violated) can be represented as causal infra-Bayesian laws.
• Infra-Bayesian laws can express a very large variety of possible frequentist desiderata.
• Miscellaneous results about the mathematical properties of infradistributions, e.g. topological, information-theoretic and category-theoretic
• An analysis of regret for an infra-Bayesian generalization of stochastic linear bandits. This is an upcoming paper: "Imprecise Multi-Armed Bandits" (IMAB).

In particular, the result about Newcombian environments and also infra-Bayesian physicalism (see Direction 18 below) are two products of infra-Bayesianism that I don't see, at present, how to reproduce with any of the alternative approaches to nonrealizability.

Directions for further research include:

• (Direction 3.1) Extending the results of IMAB to full-fledged IBRL. In particular, it might be interesting to get a result that subsumes Tian et al as a special case.
• (Direction 3.2) Finding an infra-Bayesian analogue for Russo-Van Roy ("eluder") dimension. [EDIT: We did even better, namely, created infra-Bayesian decision-estimation theory.]
• (Direction 3.3) Analyzing the computational complexity of learning in the IMAB setting.
• (Direction 3.4) Studying versions of the IMAB setting with non-crisp infradistributions.

Direction 4: Exploiting properties of simplicity priors

In general, Bayesian inference has only fairly weak guarantees in the nonrealizable setting. However, simplicity priors might produce stronger guarantees. In particular, Lattimore, Hutter and Gavane (LHG) showed^[12] that (a specific version of) Solomonoff induction converges to predicting a deterministic computable subsequence even when the full sequence is uncomputable.

Directions for further research include:

• (Direction 4.1) Generalizing LHG to stochastic subsequences (this is stated as an open problem in the paper).
• (Direction 4.2) Nonrealizable guarantees for RL with a Solomonoff prior.
• (Direction 4.3) Generalizing LHG to bounded versions of the Solomonoff prior, e.g. a version with bounded space complexity (this might be easier to study than bounded time complexity, since PSPACE is in some ways a simpler class than P, e.g. APSPACE = NPSPACE = PSPACE).

Direction 5: Agnostic RL

The conventional approach to nonrealizability in offline and online learning is to replace convergence to the true hypothesis with convergence to the hypothesis closest to the truth. Similarly, in RL, given some natural metric or divergence $d$ on the space of environments, we can try to prove regret bounds of the form

Here, $T$ is the time horizon, $H$ is the hypothesis class and ${\mu }^{\ast }$ is the true environment.

That is, we allow a sublinear term (as in the realizable case) and a linear term which scales with the distance of ${\mu }^{\ast }$ from $H$. Indeed, a result of this form was proven in Zanette et al, although in a model-free setting (i.e. instead of the environments themselves they consider their corresponding state-action value functions, although their divergence also depends directly on the environment).

At least superficially, a potential drawback of this approach is that Bayes-optimality doesn't imply this "agnostic" regret bound (AFAICT), as opposed to ordinary regret bound of the realizable setting. There is also no immediately obvious agnostic analogue of Bayesian regret. However, we can rectify this by recasting the setting in IBRL language. Indeed, for any $\mu \in H$ it is possible to construct a (non-crisp) infra-Bayesianian law^[13] ${\Lambda }_{\mu }$ s.t., for any policy $\pi$ and $f:(O\times A{)}^{\ast }\to [0,1]$:

Notice that when $d$ is total variation distance, we can take ${\Lambda }_{\mu }=\mu$.  

Then, learning the hypothesis class $\{{\Lambda }_{\mu }\mid \mu \in H\}$ is equivalent to agnostically learning $H$. Moreover, IBRL does have Bayesian regret, and a notion of Bayes-optimality that implies infra-Bayesian regret bounds, which thereby carries over to agnostic RL.

A few examples of directions for further research:

• (Direction 5.1) Finding an agnostic version of the regret bound in Jin, Liu and Miryoosefi (their bound uses the so called Bellman-Eluder dimension of the hypothesis class, as opposed to the much more restrictive linear dimension of Zanette et al.)
• (Direction 5.2) Studying model-based agnostic regret bounds^[14].
• (Direction 5.3) Combining agnostic results with other IBRL results, e.g. with IMAB.

Subproblem 1.2/2.1: Traps

Allowing traps in the environment creates two different problems:

• (Subproblem 1.2) Bayes-optimality becomes intractable in a very strong sense (even for a small number of deterministic MDP hypotheses with small number of states).
• (Subproblem 2.1) It's not clear how to to talk about learnability and learning rates.

It makes some sense to consider these problems together, but different direction emphasize different sides.

Direction 6: Metacognitive Agents

This research direction is motivated not only by traps, but also by producing especially strong frequentist guarantees via metacognition (a form of self-improvement). More speculatively, this model might be also applicable to humans (and related specifically to conscious reasoning), which makes it relevant to superimitation (see relevant section below). It was originally called Turing RL, but that name seems incorrect now because "RL" assumes learnability (no traps).

In a metacognitive agent, in addition to the usual "external" interfaces (actions and observations), there is also an "internal" interface that allows the agent to execute arbitrary programs and observe their outputs. This allows us to use a learning algorithm to form subjective beliefs about computations. The beliefs can be entangled with the agent's beliefs about the external world.

For example, let $\Lambda$ be the set of all lambda terms. Then our agent might have a belief $\Theta$ over $\Gamma :=2^{\Lambda \times \Lambda }$ that refers to the relation of $\beta$-equivalence on $\Lambda$. In a Bayesian framework $\Theta$ is a distribution, and the agent might also have a belief about the external world that takes the form of an RL environment that depends on a point in the support of $\Theta$. In an infra-Bayesian framework, $\Theta$ is an infradistribution and there is an appropriate way to define a notion of "law" s.t. $\Theta$ is its marginal^[15].

However, it might be more interesting to put all beliefs about the world "inside quotation". Indeed, let $\zeta$ be a prior about the external world that a program can sample from: for example the unnormalized Solomonoff prior. Given a $\beta$-equivalence oracle, we can sample this prior using some oracle machine $M$ (since such an oracle allows to instantly know whether a given program produces given output). Since any point in $\Gamma$ has the right type signature to serve as such an oracle, we can construct a kernel $Z$ from $\Gamma$ into the external world s.t. $Z\left(y\right)$ is defined by plugging the oracle $y$ into $M$. We can then combine any $\Theta$ with $Z$ (i.e. form the semidirect product $\Theta ⋉Z$) to obtain the overall belief.

Notice that this setting is inherently nonrealizable, since the ground truth about $\Gamma$ is uncomputable. On the other hand, the nonrealizability of the external world can in principle be circumvented, because we have computationally simple hypotheses of the form "the external world behaves according to program $P$". Moreover, even "the external world is sampled from the unnormalized Solomonoff prior" is a computationally simple hypothesis. Hence, as long as the world is computable, we can describe it exactly modulo uncertainty about computations.

While the external world can contain irreversible transitions, it seems reasonable to employ an approximation in which executing most^[16] programs doesn't have irreversible harmful side-effects. As a consequence, if the agent survives long enough, it can learn most facts about computations. In the "quoted prior" setting, it will then use what it learned about computations to approximate Bayes-optimal behavior in the external world, which addresses subproblem 1.2. Moreover, since some hypotheses assert quoted priors about computations, it can arguably use what it learned to improve its own learning algorithm.

This framework is closely related to MIRI's notion of "logical uncertainty". Hence, it makes sense to compare it Garrabrant's logical induction (LI). While LI might turn out to have a useful role in this framework, in itself, LI doesn't address some key relevant questions:

• LI is focused entirely on epistemology, and the guarantee it satisfies reflects that. On the other hand, we are interested in the agent's performance as measured by achieving goals (expected utility) in the external world, and want guarantees that reflect it.
• The guarantees of LI are purely asymptotic, without especially useful rates on convergence. Indeed, LI assumes learning from a fixed sequence of theorems that are revealed to the algorithm, which is bound to be astronomically inefficient. On the other hand, a metacognitive agent should decide which programs to run online in some manner that guarantees good sample complexity.
• LI in its present form is not concerned with computational complexity, while we are ultimately interested in models that are computationally feasible (although it might be useful to consider more or less realistic models of computational resource constraints).
• LI doesn't use what it has learned to improve its own learning process.

There are several potential starting points for research into metacognitive agents:

Direction 6.1: Bayesian planning via query-based learning of computations

Arguably tree automata and more generally string machines are a natural class of hypotheses about computations. Therefore, we can try building on existing research in automata inference^[17]. This field is infamous for its many impossibility results, but there is one model of learning that has been quite successful. Namely, learning automata assuming two types of allowed queries:

• Running the unknown automaton on specific input.
• Stating a hypothesis automaton, and receiving a counterexample if the hypothesis is false. (By "counterexample", we mean an input on which the hypothesis automaton produces a different answer from the true automaton.)

That is, algorithms exist that guarantee convergence to a correct automaton with a number of queries that is polynomial in minimal automaton size.

In our setting, the first type of query can be implemented by running a specific program. The second type of query cannot be implemented directly, but is effectively available in various natural setups. For example:

• If we are interested in PAC-learning w.r.t. a known distribution over programs, we can implement the counterexample query by sampling from the distribution and testing the hypothesis on the sample.
• If we want the algorithm to answer a sequence of questions of the form "predict the output of this program", we can implement the counterexample query by answering according to the current hypothesis, which leads to a polynomial mistake bound.

Therefore, it is a natural question whether we can implement Bayesian planning by some protocol of this type, assuming (for starters) that it is possible to efficiently sample from the prior. For example, assume that the hypothesis about computations translates to a hypothetical infra-Bayesian coarsening (or Bayesian approximation?) of the prior for which optimal planning is feasible. Assume also that there if resulting policy performs less well than promised on the true prior, there is some way to produce a counterexample to the hypothesis about computations. Then, counterexample queries are effectively available. 

Automata learning might also be feasible in a setting where the automaton generates a sequence that we need to predict. (At least for a deterministic automaton this is trivial because the sequence is periodic.) Speculatively, the amount of available computational resources can be treated as defining a "sequence" (possibly related to "logical time") and this can be exploited to get guarantees even when the prior cannot be sampled efficiently.

Direction 6.2: Expressiveness of string machines

String machines are a potential starting point for finding a frugal universal prior for metacognitive agents. In order to strike the right balance between "frugality" and "universality" we need to understand the expressiveness of the string language and the computational complexity of evaluating string machines (or answering more complicated questions about string machines) under various assumptions. In particular, parameterized complexity theory might be relevant here, since there seem to be more relevant parameters than just description size (e.g. the number of meta-vertex levels we allow).

Direction 6.3: Query learning of string machines

We can also study the sample complexity of learning string machines in the two-type query model above. While existing results guarantee learning with a number of queries polynomial in the number of states of an automaton, we would like query complexity to scale well with the description size of an automaton in string language. More general string machines are not even automata.

Direction 7: Approximation algorithms for Bayesian planning

Subproblem 1.2 comes from an NP-hardness result, but that still leaves room for studying approximation algorithms. There are many NP-hard optimization problems for which we have conjectured optimal approximation ratios (e.g. based on the PCP theorem or the unique games conjecture). It is conceivable that we can prove a result of this form for Bayesian planning. Some approaches:

• (Direction 7.1) Fix a prior $\zeta$ over set of MDPs with state set $S$ and action set $A$, and an arbitrary stationary policy ${\pi }_0:S\to A$. Let ${\pi }^{\ast }$ be the (unknown) Bayes-optimal policy. For any policy $\pi$ we can consider the approximation ratio

• (Direction 7.2) Finding the Bayes-optimal policy is NP-hard, but is it NP-easy? If it is e.g. PSPACE-hard then it seems significantly less likely that we can get optimal approximation results.

Direction 8: Expanding Safety Envelope

The Expanding Safety Envelope (XSE) is an approach to traps which can be summarized as follows:

• Assume there is some a priori known safe baseline policy, or more generally a non-empty set of known safe actions at every state reachable by these actions.
• Exploring the known safe actions might be sufficient to discover new safe actions. Exploring the new safe actions might be sufficient to discover even more safe actions, etc.
• Therefore, we can study guarantees that compare asymptotic performance to the policy which is optimal among those restricted to discoverable safe actions.

One significant limitation of this approach is, when using a rich prior, discovery of new safe actions can at best be approximate. While we can study variants where we sometimes try risky actions, guaranteeing any sort of optimality there is likely to be intractable. However, maybe it is feasible to require that, whenever the posterior admits an approximation (e.g. in the sense of total variation distance) by a prior with iteratively discoverable safe actions, we get a corresponding lower bound on the performance of our algorithm starting from this point.

Better regret bounds for simple priors

This section is a grab bag of research directions about improving regret bound theory for simple hypothesis classes based on MDPs. They are not directly related to AIXI, but rather fit perfectly within classical RL theory^[18]. However, it seems plausible that they are necessary pieces of the bigger puzzle (i.e. for a full solution of Problem 2).

Direction 9: Unifilar MDPs

[EDIT: What I called "unifilar MDP" is already known in the literature under the name "regular decision process" (RDP): see Ronca and De Giacomo. Notably, Subproblem 2.2 (password games) already emerges in learning RDPs with small number of states. Ronca and De Giacomo address it by assuming that the uniformly random policy has a high probability to reach every RDP state: a condition which is clearly insufficiently general, but does serve as an interesting starting point.]

Most of RL theory literature focuses on learning an MDP with a known state space, implicitly assume a known representation. Ortner et al prove a regret bound in a setting with unknown representation, but it scales with the cardinality of the set of possible representations. For real-world agents, I expect this cardinality to be something like doubly-exponentially large, so their bound is extremely weak. 

As a first step towards a better theory of representation learning, I propose the following setting. Fix action set $A$ and observation set $O$. Then, a unifilar MDP (UMDP: combination of MDP and unifilar hidden Markov model) $M$ consists of the following data: the state set $S$, the initial observation distribution ${\beta }_0\in \Delta O$, the state initialization function $\iota :O\to S$, the response kernel $\rho :S\times A\to \Delta O$ and the transition function $T:S\times A\times O\to S$. The interaction of a policy $\pi$ with a UMDP works as follows: