On the Foundations of Universal Artificial Intelligence

Abstract

The goal of the field of artificial intelligence has always been the construction of a truly intelligent systems. Understanding the overall behaviour and function of a potentially intelligent agent is key to its construction.

The leading theory in understanding the behaviour of artificial general intelligence is the theory of Universal Artificial Intelligence (UAI). According to this theory, intelligent agents will act optimally with respect to a universal Bayesian perspective. As part of this work, we have produced a textbook detailing the study and development of the field of UAI since its inception 22 years ago.

One key component of the universal Bayesian setup is the universal prior which is a belief that simple explanations are more likely correct than complex explanations. Mathematically this prior is characterised by the Kolmogorov complexity, which is a well studied measure of simplicity that has many ideal properties. In this thesis, we formally verify many of its properties through the use of mechanisation in the HOL4 theorem prover. Formal verification, we are able to attain a greater sense of certainty about the validity of Kolmogorov complexity as a measure of complexity and deepen our understanding of it through new proof techniques.

When acting in an environment, agents use many distinct action spaces. A chess-playing agent has the set of legal moves, a car driving agent uses steering, acceleration and braking, a programming agent considers the set of possible programs it can write. In this thesis, we present an information-theoretic method in which all action spaces can be unified into a single succinct action space, with the aid of recent advances in large language models. We show that under this method, the traditional setup of an agent interacting with an environment is preserved.

We go on to apply this action unification technique to a policy evaluation approach, called compress and control, which is able to take advantage of the unified structure of the actions. We show that under the action unification setup, compress and control leads to a policy evaluation that is a consistent estimator of the true value of the policy.

In the UAI framework, one of the ``free variables'' is the choice of reward space. What we mean by this is that the choice of reward space is left as an unspecified implementation detail. In this thesis, we show that the learning ability of a Bayesian agent is independent of the choice of reward space. Specifically, we demonstrate that an agent with a binary reward space can learn just as well as an arbitrary reward space. This result shows that while the choice of reward space is free, it will not have an effect on the limiting performance of the agent.

While it can be shown that the Bayesian agent AIXI satisfies the conditions of Bayesian optimality, there are many distinct possible definitions of optimality in the UAI framework. In the case of strong asymptotic optimality, it has been previously shown that no deterministic agent can achieve this. In this work we describe a stochastic agent, called Inq, which we prove is strongly asymptotically optimal. Additionally we demonstrate the performance of Inq experimentally, comparing it to BayesExp, a weak asymptotically optimal agent, and Thompson sampling, an agent which is asymptotically optimal in mean.

In this thesis we show that if an agent is asymptotically optimal, then it will eventually be incapacitated. We go on to define an agent Mentee which, while not asymptotically optimal, explores according to a safe (human) mentor policy and learns to eventually outperform the mentor while asking for advice less as time goes on. We also show that experimentally, with the help of the Mentors safe exploration, the Mentee agent can outperform asymptotically optimal agents as they will often fall into traps. Show more