Preface and scope
Legg studies ideal agents that learn in unknown computable environments, how their performance might define intelligence, and what is lost when the agents must be computable. The dissertation combines theoretical definitions and proofs with a separate empirical study of temporal-difference learning. AIXI and the universal intelligence score are mathematical ideals; they are not directly executable algorithms or practical intelligence tests.
1. Nature and Measurement of Intelligence
What should be measured? The survey compares theories and definitions of human, animal, and machine intelligence. Legg extracts a shared emphasis on achieving goals across varied environments, while recognizing that any test depends on its interface, motivation, task distribution, and intended subject.
Human psychometric tests, the Turing test, task competitions, and complexity-based sequence tests each capture something narrower than unrestricted adaptive performance. A machine can be specialized to a test without exhibiting broad competence. The sequence-test examples are retained; the chapter motivates a general formal measure rather than establishing a universally accepted definition. [102, 103, 104, 172]


2. Universal Artificial Intelligence
From prediction to action. Bayesian inference updates hypotheses after observations. Solomonoff induction mixes computable explanations with a preference for short programs; its ideal predictor has strong convergence guarantees under a computable data-generating distribution, but evaluating the universal prior is incomputable.
An interactive agent must also consider how actions affect future observations and rewards. AIXI combines a universal mixture over environments with sequential decision theory, selecting actions for expected future reward. The chapter develops the prior, agent–environment interaction, value functions, and optimality notions. Pareto optimality excludes uniform domination across environments. Self-optimization concerns asymptotic performance and requires appropriate environment classes; neither property guarantees quick learning or good behavior in every possible environment. [78, 155, 156]
Equations p41-extra-15–p55-2























Equations p59-1–p66-1
















main(){while(1)printf("1");}3. Taxonomy of Environments
Where can optimal behavior be learned? The taxonomy separates passive processes from environments affected by actions, including Markov processes, MDPs, partially observed models, bandits, classification, repeated games, and sequence prediction. Some classes are special cases of others; others can be reduced by changing action and observation spaces.
The ergodic MDP argument supports self-optimization for several restricted classes. Unrestricted sequence prediction admits adversarial constructions, and universal-agent guarantees depend on the exact problem class and reward formulation. Even where a self-optimizing agent exists, convergence in the limit says nothing about whether its learning time is useful. The taxonomy figure distinguishes these relations and assumptions. [98, 78]
Equations p70-extra-1–p83-1
































4. Universal Intelligence Measure
A proposed universal score. Measure an agent’s expected cumulative reward across computable, reward-summable environments, weighting each environment by a simplicity prior derived from Kolmogorov complexity. This turns the informal ambition of broad goal achievement into a precise mathematical quantity. The corresponding ideal Bayesian agent maximizes that quantity.
The score is incomputable and depends on the reference machine used to describe environments. Its broad coverage does not remove that choice. The chapter compares illustrative agents, evaluates desirable properties of intelligence measures, and responds to objections about computability, rewards, behavioral definitions, embodiment, and human-specific notions of understanding. These are arguments for a particular formalization, not empirical proof that one scalar captures every useful meaning of intelligence. Reward must remain specified by the task rather than freely set by the agent. [104]
Equations p89-1–p96-1





Equation p98-1


5. Limits of Computational Agents
Limits of computable prediction. For any computable predictor, a computable sequence can be constructed that defeats it. Predictors able eventually to predict every computable sequence below a description-length bound do exist, but their own descriptions must grow roughly with that bound. Some simple sequences are difficult to predict because generating them can require extreme computation.
A further incompleteness result limits what a fixed sufficiently expressive, consistent formal system can prove about very powerful predictors. These are worst-case results about broad classes and eventual correctness, not evidence that practical learning on restricted data is impossible. The proposed direction is to constrain both environment generation and the learner’s resources, and to study learning speed as well as asymptotic success. [97]
Equations p114-1–p118-3





6. Temporal Difference Updating without a Learning Rate
An empirical learning rule. Starting from a squared-error objective for state values, the derivation replaces TD(λ)’s manually chosen learning rate with a transition-dependent expression involving visit counts and eligibility traces. The resulting HL(λ) rule still requires other choices, including discounting and the treatment of old observations. It is not parameter-free.
Experiments cover 21-state and 51-state random walks, a random 50-state Markov process, changing rewards, and a continuing Windy Gridworld. In the reported comparisons, HL updates improve learning or final value estimates relative to the tuned TD baselines. The reinforcement-learning variants HLS and HLQ replace updates in Sarsa and Watkins’ Q-learning; HLS costs about 1.7 times as much per step as the compared Sarsa implementation. The nonstationary experiment also reveals a tradeoff between rapid adaptation and final accuracy.
All eight experimental figures and three algorithms are retained. The evidence is limited to these small tabular settings. Convergence proofs, episodic extensions, broader tasks, and function approximation are left for future work; the reported success does not establish general superiority. [83, 164, 165, 179]
Equations p126-1–p126-3




Equations p127-1–6.9



























![Figure 6.7.: [Windy Gridworld] S marks the start state and G the goal state, at which the agent jumps back to S with a reward of 1. Small arrows indicate an upward wind of one row per time step. The large arrows indicate a wind of two rows per time step.](https://storage.literature.yihao.one/media/sha256/f4/f495f1dd672f62a1d0a80ff4690d0903bb98aa94bc184e8a0b8c0e392f5d8b48.webp)


7. Discussion
Implications in 2008. The discussion considers whether powerful general machines are possible and examines theoretical design, biological inspiration, and artificial evolution as research paths. Formal ideals can organize questions without supplying a practical construction. Evolutionary approaches also depend on useful fitness functions, representations, diversity, and computational resources.
Legg argues that the potential benefits and hazards justify studying safe goal specification before very powerful systems arrive. This is a forward-looking discussion from the dissertation’s time, not an experimental result or a current forecast. The thesis provides neither a demonstrated superintelligent machine nor a guarantee that maximizing a specified reward produces desirable real-world behavior. [51]
Appendix A. Notation and Conventions
The notation guide defines equality and approximation conventions, sets and intervals, binary strings and sequences, probability notation, algorithms, and additive or multiplicative comparisons of complexity. Its role is to make the mathematical assumptions in the chapters precise; unnumbered preserved equations are labeled by their PDF page and order in this edition.
Appendix B. Ergodic MDPs Admit Self-optimising Agents
The proof formalizes stationary policies, transition matrices, reward vectors, and long-run average value in a finite ergodic MDP. It analyzes the limiting behavior of stationary Markov chains, establishes the existence of an optimal stationary policy, and controls the effect of estimated transition probabilities.
An agent can spend an initial period gathering data and then exploit a policy optimized for its estimated model. With an appropriate balance, estimation error and the fraction of time spent exploring vanish, yielding convergence of expected average value. The conclusion depends on the appendix’s ergodicity and finite-state assumptions and is asymptotic. The complete displayed derivation is retained for inspection. [12, 78]
Equations p160-extra-9–p173-3









































































Appendix C. Definitions of Intelligence
The collection gathers definitions from reference works, psychologists, and artificial-intelligence researchers. Recurrent themes include learning, reasoning, adaptation, problem solving, and effective goal pursuit, but the definitions emphasize different abilities and contexts. The appendix is historical supporting material for the thesis’s chosen definition, not a claim that all authors endorse the later universal intelligence formula. [102]