Foundations ofUniversal Induction
and Intelligent Agents
Marcus Hutter
Canberra, ACT, 0200, Australia
http://www.hutter1.net/

ANU

RSISE

NICTA

Marcus Hutter-2-

Universal Induction & Intelligence

Abstract
The dream of creating artiﬁcial devices that reach or outperform human
intelligence is many centuries old. This lecture series presents theelegant parameter-free theory, developed in [Hut05], of an optimal
reinforcement learning agent embedded in an arbitrary unknown
environment that possesses essentially all aspects of rational intelligence.
The theory reduces all conceptual AI problems to pure computationalquestions.
How to perform inductive inference is closely related to the AI problem.
The lecture series covers Solomonoﬀ’s theory, elaborated on in [Hut07],
which solves the induction problem, at least from a philosophical andstatistical perspective.
Both theories are based on Occam’s razor quantiﬁed by Kolmogorov
complexity; Bayesian probability theory; and sequential decision theory.

Marcus Hutter-3-

Universal Induction & Intelligence

Relation between ML & RL & (U)AI
Universal Artificial Intelligence
Covers all Reinforcement Learning problem types

Statistical
Machine Learning
Mostly i.i.d. dataclassification,
regression,clustering

RL Problems& Algorithms
Stochastic,
unknown,
non-i.i.d.
environments

Artificial
Intelligence
Traditionallydeterministic,
known world /planning problem

Marcus Hutter-4-

Universal Induction & Intelligence

TABLE OF CONTENTS
1. PHILOSOPHICAL ISSUES
2. BAYESIAN SEQUENCE PREDICTION
3. UNIVERSAL INDUCTIVE INFERENCE
4. UNIVERSAL ARTIFICIAL INTELLIGENCE
5. APPROXIMATIONS AND APPLICATIONS
6. FUTURE DIRECTION, WRAP UP, LITERATURE

Marcus Hutter-5-

Universal Induction & Intelligence

PHILOSOPHICAL ISSUES• Philosophical Problems• What is (Artiﬁcial) Intelligence?
• How to do Inductive Inference?
• How to Predict (Number) Sequences?
• How to make Decisions in Unknown Environments?
• Occam’s Razor to the Rescue• The Grue Emerald and Conﬁrmation Paradoxes• What this Lecture Series is (Not) About

Marcus Hutter-6-

Universal Induction & Intelligence

Philosophical Issues: Abstract
I start by considering the philosophical problems concerning artiﬁcial
intelligence and machine learning in general and induction in particular.
I illustrate the problems and their intuitive solution on various (classical)
induction examples. The common principle to their solution is Occam’s
simplicity principle. Based on Occam’s and Epicurus’ principle, Bayesian
probability theory, and Turing’s universal machine, Solomonoﬀ
developed a formal theory of induction. I describe the sequential/online
setup considered in this lecture series and place it into the wider
machine learning context.

Marcus Hutter-7-

Universal Induction & Intelligence

What is (Artiﬁcial) Intelligence?
Intelligence can have many faces ⇒ formal deﬁnition diﬃcult• reasoning• creativity• association• generalization• pattern recognition• problem solving• memorization• planning• achieving goals• learning• optimization• self-preservation• vision• language processing• classiﬁcation•••induction
deduction...

What is AI?

Thinking

Actinghumanly

Cognitive
Science

Turing test,
Behaviorism

rationally

Laws
Thought

Doing theRight Thing

Collection of 70+ Defs of Intelligence
http://www.vetta.org/
definitions-of-intelligence/

Real world is nasty: partially unobservable,
uncertain, unknown, non-ergodic, reactive,
vast, but luckily structured, ...

Marcus Hutter-8-

Universal Induction & Intelligence

Informal Deﬁnition of (Artiﬁcial) IntelligenceIntelligence measures an agent’s ability to achieve goals
in a wide range of environments. [S. Legg and M. Hutter]
Emergent: Features such as the ability to learn and adapt, or tounderstand, are implicit in the above deﬁnition as these capacities
enable an agent to succeed in a wide range of environments.
The science of Artiﬁcial Intelligence is concerned with the constructionof intelligent systems/artifacts/agents and their analysis.
What next? Substantiate all terms above: agent, ability, utility, goal,
success, learn, adapt, environment, ...

Marcus Hutter-9-

Universal Induction & Intelligence

On the Foundations of Artiﬁcial Intelligence• Example: Algorithm/complexity theory: The goal is to ﬁnd fastalgorithms solving problems and to show lower bounds on their
computation time. Everything is rigorously deﬁned: algorithm,
Turing machine, problem classes, computation time, ...
• Most disciplines start with an informal way of attacking a subject.
With time they get more and more formalized often to a point
where they are completely rigorous. Examples: set theory, logicalreasoning, proof theory, probability theory, inﬁnitesimal calculus,
energy, temperature, quantum ﬁeld theory, ...
• Artiﬁcial Intelligence: Tries to build and understand systems that
act intelligently, learn from experience, make good predictions, areable to generalize, ... Many terms are only vaguely deﬁned or there
are many alternate deﬁnitions.

Marcus Hutter- 10 -

Universal Induction & IntelligenceInduction→Prediction→Decision→Action
Induction infers general models from speciﬁc observations/facts/data,
usually exhibiting regularities or properties or relations in the latter.
Having or acquiring or learning or inducing a model of the environment
an agent interacts with allows the agent to make predictions and utilize
them in its decision process of ﬁnding a good next action.

ExampleInduction: Find a model of the world economy.
Prediction: Use the model for predicting the future stock market.
Decision: Decide whether to invest assets in stocks or bonds.
Action: Trading large quantities of stocks inﬂuences the market.

Marcus Hutter- 11 -

Universal Induction & Intelligence

Example 1: Probability of Sunrise Tomorrow
What is the probability p(1|1d ) that the sun will rise tomorrow?
(d = past # days sun rose, 1 =sun rises. 0 = sun will not rise)• p is undeﬁned, because there has never been an experiment that
tested the existence of the sun tomorrow (ref. class problem).
• The p = 1, because the sun rose in all past experiments.
• p = 1 − ϵ, where ϵ is the proportion of stars that explode per day.
• p = d+1
d+2 , which is Laplace rule derived from Bayes rule.
• Derive p from the type, age, size and temperature of the sun, eventhough we never observed another star with those exact properties.
Conclusion: We predict that the sun will rise tomorrow with highprobability independent of the justiﬁcation.

Marcus Hutter- 12 -

Universal Induction & Intelligence

Example 2: Digits of a Computable Number• Extend 14159265358979323846264338327950288419716939937?
• Looks random?!
• Frequency estimate: n = length of sequence. ki = number ofoccured i =⇒ Probability of next digit being i is ni . Asymptoticallyi1→n
10 (seems to be) true.
• But we have the strong feeling that (i.e. with high probability) the
next digit will be 5 because the previous digits were the expansionof π.
• Conclusion: We prefer answer 5, since we see more structure in thesequence than just random digits.

Marcus Hutter- 13 -

Universal Induction & Intelligence

Example 3: Number Sequences
Sequence: x1 , x2 , x3 , x4 , x5 , ...
1,
2,
3,
4,
?, ...
• x5 = 5, since xi = i for i = 1..4.
• x5 = 29, since xi = i4 − 10i3 + 35i2 − 49i + 24.
Conclusion: We prefer 5, since linear relation involves less arbitrary
parameters than 4th-order polynomial.
Sequence: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,?
• 61, since this is the next prime• 60, since this is the order of the next simple group
Conclusion: We prefer answer 61, since primes are a more familiar
concept than simple groups.
On-Line Encyclopedia of Integer Sequences:
http://www.research.att.com/∼njas/sequences/

Marcus Hutter- 14 -

Universal Induction & Intelligence

Occam’s Razor to the Rescue• Is there a unique principle which allows us to formally arrive at a
prediction which- coincides (always?) with our intuitive guess -or- even better,- which is (in some sense) most likely the best or correct answer?
• Yes! Occam’s razor: Use the simplest explanation consistent withpast data (and use it for prediction).
• Works! For examples presented and for many more.
• Actually Occam’s razor can serve as a foundation of machinelearning in general, and is even a fundamental principle (or maybe
even the mere deﬁnition) of science.
• Problem: Not a formal/mathematical objective principle.
What is simple for one may be complicated for another.

Marcus Hutter- 15 -

Universal Induction & Intelligence

Grue Emerald Paradox
Hypothesis 1: All emeralds are green.
Hypothesis 2: All emeralds found till y2020 are green,
thereafter all emeralds are blue.
• Which hypothesis is more plausible? H1! Justiﬁcation?
• Occam’s razor: take simplest hypothesis consistent with data.
is the most important principle in machine learning and science.

Marcus Hutter- 16 -

Universal Induction & IntelligenceConﬁrmation Paradox(i) R → B is conﬁrmed by an R-instance with property B(ii) ¬B → ¬R is conﬁrmed by a ¬B-instance with property ¬R.
(iii) Since R → B and ¬B → ¬R are logically equivalent,
R → B is also conﬁrmed by a ¬B-instance with property ¬R.
Example: Hypothesis (o): All ravens are black (R=Raven, B=Black).
(i) observing a Black Raven conﬁrms Hypothesis (o).
(iii) observing a White Sock also conﬁrms that all Ravens are Black,since a White Sock is a non-Raven which is non-Black.
This conclusion sounds absurd!

What’s the problem?

Marcus Hutter- 17 -

Universal Induction & Intelligence

What This Lecture Series is (Not) About
Dichotomies in Artiﬁcial Intelligence & Machine Learning
scope of this lecture series(machine) learning
statisticaldecision ⇔ prediction
classiﬁcation
sequential / non-iid
online learning
passive prediction
Bayes ⇔ MDL
uninformed / universal
conceptual/mathematical issues
exact/principled
supervised learning
exploitation

⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔

scope of other lecture seriess(GOFAI) knowledge-based
logic-based
induction ⇔ action
regression
independent identically distributed
oﬄine/batch learning
active learning
Expert ⇔ Frequentist
informed / problem-speciﬁccomputational issues
heuristic
unsupervised ⇔ RL learning
exploration

Marcus Hutter- 18 -

Universal Induction & Intelligence

BAYESIAN SEQUENCE PREDICTION• Sequential/Online Prediction – Setup• Uncertainty and Probability• Frequency Interpretation: Counting• Objective Uncertain Events & Subjective Degrees of Belief• Bayes’ and Laplace’s Rules• The Bayes-mixture distribution• Predictive Convergence• Sequential Decisions and Loss Bounds• Generalization: Continuous Probability Classes• SummaryMarcus Hutter- 19 -

Universal Induction & Intelligence

Bayesian Sequence Prediction: Abstract
The aim of probability theory is to describe uncertainty. There arevarious sources and interpretations of uncertainty. I compare thefrequency, objective, and subjective probabilities, and show that they all
respect the same rules, and derive Bayes’ and Laplace’s famous andfundamental rules. Then I concentrate on general sequence prediction
tasks. I deﬁne the Bayes mixture distribution and show that theposterior converges rapidly to the true posterior by exploiting somebounds on the relative entropy. Finally I show that the mixture predictor
is also optimal in a decision-theoretic sense w.r.t. any bounded loss
function.

Marcus Hutter- 20 -

Universal Induction & Intelligence

Sequential/Online Prediction – Setup
In sequential or online prediction, for times t = 1, 2, 3, ...,
our predictor p makes a prediction ytp ∈ Ybased on past observations x1 , ..., xt−1 .
Thereafter xt ∈ X is observed and p suﬀers Loss(xt , ytp ).
The goal is to design predictors with small total loss or cumulative∑T
Loss1:T (p) := t=1 Loss(xt , ytp ).
Applications are abundant, e.g. weather or stock market forecasting.
Example:Loss(x,y) }{umbrella
Y = sunglasses

X = {sunny , rainy}
0.1
0.0

0.3
1.0

Setup also includes: Classiﬁcation and Regression problems.

Marcus Hutter- 21 -

Universal Induction & Intelligence

Uncertainty and Probability
The aim of probability theory is to describe uncertainty.
Sources/interpretations for uncertainty:• Frequentist: probabilities are relative frequencies.
(e.g. the relative frequency of tossing head.)• Objectivist: probabilities are real aspects of the world.
(e.g. the probability that some atom decays in the next hour)• Subjectivist: probabilities describe an agent’s degree of belief.
(e.g. it is (im)plausible that extraterrestrians exist)

Marcus Hutter- 22 -

Universal Induction & Intelligence

Frequency Interpretation: Counting• The frequentist interprets probabilities as relative frequencies.
• If in a sequence of n independent identically distributed (i.i.d.)experiments (trials) an event occurs k(n) times, the relative
frequency of the event is k(n)/n.
• The limit limn→∞ k(n)/n is deﬁned as the probability of the event.
• For instance, the probability of the event head in a sequence ofrepeatedly tossing a fair coin is 12 .
• The frequentist position is the easiest to grasp, but it has several
shortcomings:• Problems: deﬁnition circular, limited to i.i.d, reference classproblem.

Marcus Hutter- 23 -

Universal Induction & Intelligence

Objective Interpretation: Uncertain Events• For the objectivist probabilities are real aspects of the world.
• The outcome of an observation or an experiment is notdeterministic, but involves physical random processes.
• The set Ω of all possible outcomes is called the sample space.
• It is said that an event E ⊂ Ω occurred if the outcome is in E.
• In the case of i.i.d. experiments the probabilities p assigned toevents E should be interpretable as limiting frequencies, but theapplication is not limited to this case.
• (Some) probability axioms:p(Ω) = 1 and p({}) = 0 and 0 ≤ p(E) ≤ 1.
p(A ∪ B) = p(A) + p(B) − p(A ∩ B).
p(B|A) = p(A∩B)
p(A) is the probability of B given event A occurred.

Marcus Hutter- 24 -

Universal Induction & Intelligence

Subjective Interpretation: Degrees of Belief• The subjectivist uses probabilities to characterize an agent’s degreeof belief in something, rather than to characterize physical random
processes.
• This is the most relevant interpretation of probabilities in AI.
• We deﬁne the plausibility of an event as the degree of belief in theevent, or the subjective probability of the event.
• It is natural to assume that plausibilities/beliefs Bel(·|·) can be repr.
by real numbers, that the rules qualitatively correspond to common
sense, and that the rules are mathematically consistent. ⇒• Cox’s theorem: Bel(·|A) is isomorphic to a probability functionp(·|·) that satisﬁes the axioms of (objective) probabilities.
• Conclusion: Beliefs follow the same rules as probabilities

Marcus Hutter- 25 -

Universal Induction & Intelligence

Bayes’ Famous RuleLet D be some possible data (i.e. D is event with p(D) > 0) and{Hi }i∈I be a countable complete class of mutually exclusive hypotheses∪(i.e. Hi are events with Hi ∩ Hj = {} ∀i ̸= j and i∈I Hi = Ω).
Given: p(Hi ) = a priori plausibility of hypotheses Hi (subj. prob.)
Given: p(D|Hi ) = likelihood of data D under hypothesis Hi (obj. prob.)
Goal: p(Hi |D) = a posteriori plausibility of hypothesis Hi (subj. prob.)p(D|Hi )p(Hi )Solution: p(Hi |D) = ∑i∈I p(D|Hi )p(Hi )Proof: From the deﬁnition of conditional probability and∑∑∑p(Hi |...) = 1 ⇒p(D|Hi )p(Hi ) =p(Hi |D)p(D) = p(D)
i∈I

i∈I

i∈I

Marcus Hutter- 26 -

Universal Induction & Intelligence

Example: Bayes’ and Laplace’s Rule
Assume data is generated by a biased coin with head probability θ, i.e.
Hθ :=Bernoulli(θ) with θ ∈ Θ := [0, 1].
Finite sequence: x = x1 x2 ...xn with n1 ones and n0 zeros.
Sample inﬁnite sequence: ω ∈ Ω = {0, 1}∞
Basic event: Γx = {ω : ω1 = x1 , ..., ωn = xn } = set of all sequences
starting with x.
Data likelihood: pθ (x) := p(Γx |Hθ ) = θn1 (1 − θ)n0 .
Bayes (1763): Uniform prior plausibility: p(θ) := p(Hθ ) = 1∫1∑( 0 p(θ) dθ = 1 instead i∈I p(Hi ) = 1)

Evidence: p(x) =∫1p (x)p(θ) dθ =0 θ

∫1n1 !n0 !
n1
n0
θ
(1
−
θ)
dθ
=
(n0 +n1 +1)!
0

Marcus Hutter- 27 -

Universal Induction & Intelligence

Example: Bayes’ and Laplace’s Rule
Bayes: Posterior plausibility of θafter seeing x is:p(x|θ)p(θ)(n+1)! n1p(θ|x) ==θ (1−θ)n0
p(x)n1 !n0 !
.
Laplace: What is the probability of seeing 1 after having observed x?
p(x1)
n1 +1
p(xn+1 = 1|x1 ...xn ) =
=
p(x)
n+2
Laplace believed that the sun had risen for 5000 years = 1’826’213 days,
1
so he concluded that the probability of doomsday tomorrow is 1826215.

Marcus Hutter- 28 -

Universal Induction & Intelligence

Exercise: Envelope Paradox• I oﬀer you two closed envelopes, one of them contains twice theamount of money than the other. You are allowed to pick one andopen it. Now you have two options. Keep the money or decide forthe other envelope (which could double or half your gain).
• Symmetry argument: It doesn’t matter whether you switch, theexpected gain is the same.
• Refutation: With probability p = 1/2, the other envelope contains
twice/half the amount, i.e. if you switch your expected gainincreases by a factor 1.25=(1/2)*2+(1/2)*(1/2).
• Present a Bayesian solution.

Marcus Hutter- 29 -

Universal Induction & Intelligence

Notation: Strings & Probabilities
Strings: x = x1 x2 ...xn with xt ∈ X and x1:n := x1 x2 ...xn−1 xn andx<n := x1 ...xn−1 .
Probabilities: σ(x1 ...xn ) is the probability that an (inﬁnite) sequence
starts with x1 ...xn .
Conditional probability:
σn := σ(xn |x<n ) = σ(x1:n )/σ(x<n ),σ(x1 ...xn ) = σ(x1 )·σ(x2 |x1 )·...·σ(xn |x1 ...xn−1 ).
True data generating distribution: µMarcus Hutter- 30 -

Universal Induction & Intelligence

The Bayes-Mixture Distribution ξ• Assumption: The true (objective) environment µ is unknown.
• Bayesian approach: Replace true probability distribution µ by aBayes-mixture ξ.
• Assumption: We know that the true environment µ is contained insome known countable (in)ﬁnite set M of environments.
• The Bayes-mixture ξ is deﬁned as∑
ξ(x) :=wν ν(x) with

∑

ν∈M

ν∈M

wν = 1,wν > 0 ∀ν

• The weights wν may be interpreted as the prior degree of belief thatthe true environment is ν, or k ν = ln wν−1 as a complexity penalty(preﬁx code length) of environment ν.
• Then ξ(x) could be interpreted as the prior subjective belief
probability in observing x.

Marcus Hutter- 31 -

Universal Induction & Intelligence

Relative Entropy
Relative entropy: D(p||q) :=Properties: D(p||q) ≥ 0

∑

pi
p
ln
i i
qi

and D(p||q) = 0 ⇔ p = q

Instantaneous relative entropy: dt (x<t ) :=

∑
xt ∈X

Total relative entropy: Dn :=µ(xt |x<t )µ(xt |x<t ) ln
ξ(xt |x<t )

∑n

−1
E[d
]
≤
ln
w
t
µ
t=1

E[f ] =Expectation of f w.r.t. the true distribution µ, e.g.
If f : X → IR, then E[f ] :=n∑x1:n µ(x1:n )f (x1:n ).

Proof based on dominance or universality: ξ(x) ≥ wµ µ(x).

Marcus Hutter- 32 -

Universal Induction & Intelligence

Proof of the Entropy Bound
Dn ≡

n ∑
∑
t=1 x<tn ∑∑µ(xt |x<t )(a)µ(x<t )·dt (x<t ) =µ(x1:t ) ln=
ξ(xt |x<t )
t=1 x
1:t

n
∏
∑
µ(xt |x<t ) (c) ∑µ(x1:n ) (d)(b)=µ(x1:n ) ln=µ(x1:n ) ln
≤ ln wµ−1
ξ(xt |x<t )ξ(x1:n )
x
x
t=1
1:n

1:n

(a) Insert def. of dt and used chain rule µ(x<t )·µ(xt |x<t ) = µ(x1:t ).
∑∑(b) x1:t µ(x1:t ) = x1:n µ(x1:n ) and argument of log is independentof xt+1:n . The t sum can now be exchanged with the x1:n sum andtransforms to a product inside the logarithm.
(c) Use chain rule again for µ and ξ.
(d) Use dominance ξ(x) ≥ wµ µ(x).

Marcus Hutter- 33 -

Universal Induction & Intelligence

Predictive Convergence
Theorem: ξ(xt |x<t ) → µ(xt |x<t ) rapid w.p.1 for t → ∞Proof: D∞ ≡
=⇒

∑∞

t→∞

−1
E[d
]
≤
ln
w
and dt ≥ 0
tµt=1

dt −→ 0⇐⇒ξt → µt .

Fazit: ξ is excellent universal predictor if unknown µ belongs to M.
How to choose M and wµ ? Both as large as possible?! More later.

Marcus Hutter- 34 -

Universal Induction & Intelligence

Sequential Decisions
A prediction is very often the basis for some decision. The decision
results in an action, which itself leads to some reward or loss.
Let Loss(xt , yt ) ∈ [0, 1] be the received loss when taking action yt ∈ Yand xt ∈ X is the tth symbol of the sequence.
For instance, decision Y = {umbrella, sunglasses} based on weather
forecasts X = {sunny, rainy}.
Losssunny rainyumbrella

0.1

0.3

sunglasses

0.0

1.0

The goal is to minimize the µ-expected loss. More generally we deﬁnethe Λσ prediction scheme, which minimizes the σ-expected loss:∑
Λσyt := arg min
σ(xt |x<t )Loss(xt , yt )
yt ∈Y

xt

Marcus Hutter- 35 -

Universal Induction & Intelligence

Loss Bounds• Deﬁnition: µ-expected loss when Λσ predicts the tth symbol:∑
Losst (Λσ )(x<t ) := xt µ(xt |x<t )Loss(xt , ytΛσ )• Losst (Λµ/ξ ) made by the informed/universal scheme Λµ/ξ .
Losst (Λµ ) ≤ Losst (Λ) ∀t, Λ.
• Theorem: 0 ≤ Losst (Λξ )−Losst (Λµ ) ≤• Total Loss1:n (Λσ ) :=∑xt |ξt −µt | ≤

√

w.p.1

2dt −→ 0∑nt=1 E[Losst (Λσ )].

√• Theorem: Loss1:n (Λξ ) − Loss1:n (Λµ ) ≤ 2Dn + 2 Loss1:n (Λµ )Dn• Corollary: If Loss1:∞ (Λµ ) is ﬁnite, then Loss1:∞ (Λξ ) is ﬁnite, andLoss1:n (Λξ )/Loss1:∞ (Λµ ) → 1 if Loss1:∞ (Λµ ) → ∞.
• Remark: Holds for any loss function ∈ [0, 1] with no assumptions(like i.i.d., Markovian, stationary, ergodic, ...) on µ ∈ M.

Marcus Hutter- 36 -

Universal Induction & Intelligence

Proof of Instantaneous Loss Bounds
Abbreviations: X = {1, ..., N }, N = |X |, i = xt , yi = µ(xt |x<t ),ΛξΛµzi = ξ(xt |x<t ), m = yt , s = yt , ℓxy = Loss(x, y).
∑
∑
Λξ
Λµ
This and deﬁnition of yt and yt and i zi ℓis ≤ i zi ℓij ∀j implies
Losst (Λξ ) − Losst (Λµ ) ≡

∑

(a) ∑

yi ℓim ≤(yi − zi )(ℓis − ℓim )
i
i
i
√
∑
(b) ∑
(c) ∑
√
yi
≤
|yi −zi |·|ℓis −ℓim | ≤|yi − zi | ≤yi ln≡ 2dt (x<t )
zi
i
i
i

(a) We added

yi ℓis −∑∑i zi (ℓim − ℓis ) ≥ 0.

(b) |ℓis − ℓim | ≤ 1 since ℓ ∈ [0, 1].
(c) Pinsker’s inequality (elementary, but not trivial)Marcus Hutter- 37 -

Universal Induction & Intelligence

Generalization: Continuous Classes M
In statistical parameter estimation one often has a continuous
hypothesis class (e.g. a Bernoulli(θ) process with unknown θ ∈ [0, 1]).
∫∫
M := {νθ : θ ∈ IRd }, ξ(x) := dθ w(θ) νθ (x),dθ w(θ) = 1
IRd

IRd

Under weak regularity conditions [CB90,H’03]:n
Theorem: Dn (µ||ξ) ≤ ln w(µ)−1 + d2 ln 2π+ O(1)

where O(1) depends on the local curvature (parametric complexity) ofln νθ , and is independent n for many reasonable classes, including all
stationary (k th -order) ﬁnite-state Markov processes (k = 0 is i.i.d.).
Dn ∝ log(n) = o(n) still implies excellent prediction and decision for[RH’07]
most n.

Marcus Hutter- 38 -

Universal Induction & Intelligence

Bayesian Sequence Prediction: Summary• The aim of probability theory is to describe uncertainty.
• Various sources and interpretations of uncertainty:
frequency, objective, and subjective probabilities.
• They all respect the same rules.
• General sequence prediction: Use known (subj.) Bayes mixture∑ξ = ν∈M wν ν in place of unknown (obj.) true distribution µ.
• Bound on the relative entropy between ξ and µ.
⇒ posterior of ξ converges rapidly to the true posterior µ.
• ξ is also optimal in a decision-theoretic sense w.r.t. any bounded
loss function.
• No structural assumptions on M and ν ∈ M.

Marcus Hutter- 39 -

Universal Induction & Intelligence

UNIVERSAL INDUCTIVE INFERENCE• Foundations of Universal Induction• Bayesian Sequence Prediction and Conﬁrmation• Convergence and Decisions• How to Choose the Prior – Universal• Kolmogorov Complexity• How to Choose the Model Class – Universal• The Problem of Zero Prior• Reparametrization and Regrouping Invariance• The Problem of Old Evidence / New Theories• Universal is Better than Continuous Class• More Bounds / Stuﬀ / Critique / Problems• Summary / Outlook / Literature

Marcus Hutter- 40 -

Universal Induction & Intelligence

Universal Inductive Inference: Abstract
Solomonoﬀ completed the Bayesian framework by providing a rigorous,
unique, formal, and universal choice for the model class and the prior. I
will discuss in breadth how and in which sense universal (non-i.i.d.)sequence prediction solves various (philosophical) problems of traditional
Bayesian sequence prediction. I show that Solomonoﬀ’s model possesses
many desirable properties: Strong total and weak instantaneous bounds, and in contrast to most classical continuous prior densities has no zerop(oste)rior problem, i.e. can conﬁrm universal hypotheses, isreparametrization and regrouping invariant, and avoids the old-evidence
and updating problem. It even performs well (actually better) in
non-computable environments.

Marcus Hutter- 41 -

Universal Induction & IntelligenceInduction Examples
Sequence prediction: Predict weather/stock-quote/... tomorrow, basedon past sequence. Continue IQ test sequence like 1,4,9,16,?
Classiﬁcation: Predict whether email is spam.
Classiﬁcation can be reduced to sequence prediction.
Hypothesis testing/identiﬁcation: Does treatment X cure cancer?
Do observations of white swans conﬁrm that all ravens are black?
These are instances of the important problem of inductive inference ortime-series forecasting or sequence prediction.
Problem: Finding prediction rules for every particular (new) problem ispossible but cumbersome and prone to disagreement or contradiction.
Goal: A single, formal, general, complete theory for prediction.
Beyond induction: active/reward learning, fct. optimization, game theory.

Marcus Hutter- 42 -

Universal Induction & Intelligence

Foundations of Universal Induction
Ockhams’ razor (simplicity) principle
Entities should not be multiplied beyond necessity.
Epicurus’ principle of multiple explanations
If more than one theory is consistent with the observations, keep
all theories.
Bayes’ rule for conditional probabilities
Given the prior belief/probability one can predict all future probabilities.
Turing’s universal machine
Everything computable by a human using a ﬁxed procedure canalso be computed by a (universal) Turing machine.
Kolmogorov’s complexity
The complexity or information content of an object is the lengthof its shortest description on a universal Turing machine.
Solomonoﬀ’s universal prior=Ockham+Epicurus+Bayes+Turing
Solves the question of how to choose the prior if nothing is known.
⇒ universal induction, formal Occam, AIT,MML,MDL,SRM,...

Marcus Hutter- 43 -

Universal Induction & Intelligence

Bayesian Sequence Prediction and Conﬁrmation• Assumption: Sequence ω ∈ X ∞ is sampled from the “true”
probability measure µ, i.e. µ(x) := P[x|µ] is the µ-probability that
ω starts with x ∈ X n .
• Model class: We assume that µ is unknown but known to belong toa countable class of environments=models=measures
M = {ν1 , ν2 , ...}.
[no i.i.d./ergodic/stationary assumption]• Hypothesis class: {Hν : ν ∈ M} forms a mutually exclusive andcomplete class of hypotheses.
• Prior: wν := P[Hν ] is our prior belief in Hν
∑∑⇒ Evidence: ξ(x) := P[x] = ν∈M P[x|Hν ]P[Hν ] = ν wν ν(x)must be our (prior) belief in x.
ν ]P[Hν ]⇒ Posterior: wν (x) := P[Hν |x] = P[x|HP[x]is our posterior beliefin ν (Bayes’ rule).

Marcus Hutter- 44 -

Universal Induction & Intelligence

When is a Sequence Random?
a) Is 0110010100101101101001111011 generated by a fair coin ﬂip?
b) Is 1111111111111111111111111111 generated by a fair coin ﬂip?
c) Is 1100100100001111110110101010 generated by a fair coin ﬂip?
d) Is 0101010101010101010101010101 generated by a fair coin ﬂip?
• Intuitively: (a) and (c) look random, but (b) and (d) look unlikely.
• Problem: Formally (a-d) have equal probability ( 12 )length .
• Classical solution: Consider hypothesis class H := {Bernoulli(p) :p ∈ Θ ⊆ [0, 1]} and determine p for which sequence has maximum
likelihood =⇒ (a,c,d) are fair Bernoulli( 12 ) coins, (b) not.
• Problem: (d) is non-random, also (c) is binary expansion of π.
• Solution: Choose H larger, but how large? Overﬁtting? MDL?
• AIT Solution: A sequence is random iﬀ it is incompressible.

Marcus Hutter- 45 -

Universal Induction & Intelligence

What does Probability Mean?
Naive frequency interpretation is circular:• Probability of event E is p := limn→∞ knn(E) ,n = # i.i.d. trials, kn (E) = # occurrences of event E in n trials.
• Problem: Limit may be anything (or nothing):
e.g. a fair coin can give: Head, Head, Head, Head, ... ⇒ p = 1.
• Of course, for a fair coin this sequence is “unlikely”.
For fair coin, p = 1/2 with “high probability”.
• But to make this statement rigorous we need to formally know what“high probability” means.
Circularity!
Also: In complex domains typical for AI, sample size is often 1.
(e.g. a single non-iid historic weather data sequences is given).
We want to know whether certain properties hold for this particular seq.

Marcus Hutter- 46 -

Universal Induction & Intelligence

How to Choose the Prior?
The probability axioms allow relating probabilities and plausibilities ofdiﬀerent events, but they do not uniquely ﬁx a numerical value for each
event, except for the sure event Ω and the empty event {}.
We need new principles for determining values for at least some basis
events from which others can then be computed.
There seem to be only 3 general principles:• The principle of indiﬀerence — the symmetry principle• The maximum entropy principle• Occam’s razor — the simplicity principle
Concrete: How shall we choose the hypothesis space {Hi } and theirprior p(Hi ) –or– M = {ν} and their weight wν .

Marcus Hutter- 47 -

Universal Induction & IntelligenceIndiﬀerence or Symmetry Principle
Assign same probability to all hypotheses:1p(Hi ) = |I|
for ﬁnite Ip(Hθ ) = [Vol(Θ)]−1 for compact and measurable Θ.
∧⇒ p(Hi |D) ∝ p(D|Hi ) = classical Hypothesis testing (Max.Likelihood).
Prev. Example: Hθ =Bernoulli(θ) with p(θ) = 1 for θ ∈ Θ := [0, 1].
Problems: Does not work for “large” hypothesis spaces:(a) Uniform distr. on inﬁnite I = IN or noncompact Θ not possible!
(b) Reparametrization: θ ; f (θ). Uniform in θ is not uniform in f (θ).
Example: “Uniform” distr. on space of all (binary) sequences {0, 1}∞ :p(x1 ...xn ) = ( 12 )n ∀n∀x1 ...xn ⇒ p(xn+1 = 1|x1 ...xn ) = 12 always!
Inference so not possible (No-Free-Lunch myth).
Predictive setting: All we need is p(x).

Marcus Hutter- 48 -

Universal Induction & Intelligence

Occam’s Razor — The Simplicity Principle• Only Occam’s razor (in combination with Epicurus’ principle) is
general enough to assign prior probabilities in every situation.
• The idea is to assign high (subjective) probability to simple events,and low probability to complex events.
• Simple events (strings) are more plausible a priori than complex
ones.
• This gives (approximately) justice to both Occam’s razor andEpicurus’ principle.

Marcus Hutter- 49 -

Universal Induction & IntelligencePreﬁx Sets/Codes
String x is (proper) preﬁx of y:⇐⇒

Set P is preﬁx-free or a preﬁx code

∃ z(̸= ϵ) such that xz = y.

:⇐⇒no element is a proper
preﬁx of another.

Example: A self-delimiting code (e.g. P = {0, 10, 11}) is preﬁx-free.

Kraft Inequality
For a preﬁx code P we have

∑

−ℓ(x)
2
≤ 1.
x∈P

Conversely, let l1 , l2 , ... be a countable sequence of natural numbers∑ −lk≤ 1 is satisﬁed. Then there exists
such that Kraft’s inequality k 2
a preﬁx code P with these lengths of its binary code.

Marcus Hutter- 50 -

Universal Induction & Intelligence

Proof of the Kraft-Inequality
Proof ⇒: Assign to each x ∈ P the interval Γx := [0.x, 0.x + 2−ℓ(x) ).
Length of interval Γx is 2−ℓ(x) .
Intervals are disjoint, since P is preﬁx free, hence
∑
∑
−ℓ(x)
2
=
Length(Γx ) ≤ Length([0, 1]) = 1
x∈P

x∈P

⇐: Idea: Choose l1 , l2 , ... in increasing order. Successively chop oﬀ
intervals of lengths 2−l1 , 2−l2 , ... from left to right from [0, 1) anddeﬁne left interval boundary as code.

Marcus Hutter- 51 -

Universal Induction & Intelligence

Priors from Preﬁx Codes• Let Code(Hν ) be a preﬁx code of hypothesis Hν .
• Deﬁne complexity Kw(ν) :=Length(Code(Hν ))• Choose prior wν = p(Hν ) = 2−Kw(ν)∑⇒ ν∈M wν ≤ 1 is semi-probability (by Kraft).
• How to choose a Code and hypothesis space M ?
• Praxis: Choose a code which is reasonable for your problem
and M large enough to contain the true model.
• Theory: Choose a universal code and consider “all” hypotheses ...

Marcus Hutter- 52 -

Universal Induction & Intelligence

Kolmogorov Complexity K(x)K. of string x is the length of the shortest (preﬁx) program producing x:
K(x) := minp {l(p) : U (p) = x},

U = universal TM

For non-string objects o (like numbers and functions) we deﬁneK(o) := K(⟨o⟩), where ⟨o⟩ ∈ X ∗ is some standard code for o.
+ Simple strings like 000...0 have small K,
irregular (e.g. random) strings have large K.
• The deﬁnition is nearly independent of the choice of U .
+ K satisﬁes most properties an information measure should satisfy.
+ K shares many properties with Shannon entropy but is superior.
− K(x) is not computable, but only semi-computable from above.
K is an excellent universal complexity measure,
Fazit:
suitable for quantifying Occam’s razor.

Marcus Hutter- 53 -

Universal Induction & Intelligence

Schematic Graph of Kolmogorov Complexity
Although K(x) is incomputable, we can draw a schematic graphMarcus Hutter- 54 -

Universal Induction & Intelligence

The Universal Prior• Quantify the complexity of an environment ν or hypothesis Hν by
its Kolmogorov complexity K(ν).
• Universal prior: wν = wνU := 2−K(ν) is a decreasing function in
the model’s complexity, and sums to (less than) one.
⇒ Dn ≤ K(µ) ln 2, i.e. the number of ε-deviations of ξ from µ or lΛξfrom lΛµ is proportional to the complexity of the environment.
• No other semi-computable prior leads to better prediction (bounds).
• For continuous M, we can assign a (proper) universal prior (notdensity) wθU = 2−K(θ) > 0 for computable θ, and 0 for uncomp. θ.
• This eﬀectively reduces M to a discrete class {νθ ∈ M : wθU > 0}
which is typically dense in M.
• This prior has many advantages over the classical prior (densities).

Marcus Hutter- 55 -

Universal Induction & Intelligence

The Problem of Zero Prior= the problem of conﬁrmation of universal hypotheses
Problem: If the prior is zero, then the posterior is necessarily also zero.
Example: Consider the hypothesis H = H1 that all balls in some urn or
all ravens are black (=1) or that the sun rises every day.
Starting with a prior density as w(θ) = 1 implies that prior P[Hθ ] = 0
for all θ, hence posterior P [Hθ |1..1] = 0, hence H never gets conﬁrmed.
3 non-solutions: deﬁne H = {ω = 1∞ } | use ﬁnite population | abandon
strict/logical/all-quantiﬁed/universal hypotheses in favor of soft hyp.
Solution: Assign non-zero prior to θ = 1⇒

P[H|1n ] → 1.

Generalization: Assign non-zero prior to all “special” θ, like 12 and 16 ,which may naturally appear in a hypothesis, like “is the coin or die fair”.
Universal solution: Assign non-zero prior to all comp. θ, e.g. wθU = 2−K(θ)

Marcus Hutter- 56 -

Universal Induction & Intelligence

Reparametrization Invariance√• New parametrization e.g. ψ = θ, then the ψ-density√′
w (ψ) = 2 θ w(θ) is no longer uniform if w(θ) = 1 is uniform⇒ indiﬀerence principle is not reparametrization invariant (RIP).
• Jeﬀrey’s and Bernardo’s principle satisfy RIP w.r.t. diﬀerentiablebijective transformations ψ = f −1 (θ).
• The universal prior wθU = 2−K(θ) also satisﬁes RIP w.r.t. simple
computable f .
(within a multiplicative constant)Marcus Hutter- 57 -

Universal Induction & Intelligence

Regrouping Invariance• Non-bijective transformations:E.g. grouping ball colors into categories black/non-black.
• No classical principle is regrouping invariant.
• Regrouping invariance is regarded as a very important and desirable
property. [Walley’s (1996) solution: sets of priors]• The universal prior wθU = 2−K(θ) is invariant under regrouping, andmore generally under all simple [computable with complexity O(1)]even non-bijective transformations. (within a multiplicative constant)• Note: Reparametrization and regrouping invariance hold forarbitrary classes and are not limited to the i.i.d. case.

Marcus Hutter- 58 -

Universal Induction & Intelligence

Universal Choice of Class M• The larger M the less restrictive is the assumption µ ∈ M.
• The class MU of all (semi)computable (semi)measures, although
only countable, is pretty large, since it includes all valid physics
theories. Further, ξU is semi-computable [ZL70].
• Solomonoﬀ’s universal prior M (x) := probability that the output ofa universal TM U with random input starts with x.
∑• Formally: M (x) := p : U (p)=x∗ 2−ℓ(p) where the sum is over all(minimal) programs p for which U outputs a string starting with x.
• M may be regarded as a 2−ℓ(p) -weighted mixture over all
deterministic environments νp . (νp (x) = 1 if U (p) = x∗ and 0 else)• M (x) coincides with ξU (x) within an irrelevant multiplicative constant.

Marcus Hutter- 59 -

Universal Induction & Intelligence

The Problem of Old Evidence / New Theories• What if some evidence E =xb (e.g. Mercury’s perihelion advance) is
known well-before the correct hypothesis/theory/model H =µb
(Einstein’s general relativity theory) is found?
• How shall H be added to the Bayesian machinery a posteriori?
• What should the “prior” of H be?
• Should it be the belief in H in a hypothetical counterfactual worldin which E is not known?
• Can old evidence E conﬁrm H?
• After all, H could simply be constructed/biased/ﬁtted towards“explaining” E.

Marcus Hutter- 60 -

Universal Induction & Intelligence

Solution of the Old-Evidence Problem• The universal class MU and universal prior wνU formally solves thisproblem.
• The universal prior of H is 2−K(H) independent of M and ofwhether E is known or not.
• Updating M is unproblematic, and even not necessary whenstarting with MU , since it includes all hypothesis (including yet
unknown or unnamed ones) a priori.

Marcus Hutter- 61 -

Universal Induction & Intelligence

Universal is Better than Continuous M• Although νθ () and wθ are incomp. for cont. classes M for most θ,
ξ() is typically computable. (exactly as for Laplace or numerically)+⇒ Dn (µ||M ) < Dn (µ||ξ)+K(ξ) ln 2 for all µ• That is, M is superior to all computable mixture predictors ξ basedon any (continuous or discrete) model class M and weight w(θ),
save an additive constant K(ξ) ln 2 = O(1), even if environment µ
is not computable.
• While Dn (µ||ξ) ∼ d2 ln n for all µ ∈ M,
Dn (µ||M ) ≤ K(µ) ln 2 is even ﬁnite for computable µ.
Fazit: Solomonoﬀ prediction works also in non-computable environments

Marcus Hutter- 62 -

Universal Induction & Intelligence

Convergence
andLoss
Bounds∑×∞• Total (loss) bounds: n=1 E[hn ] < K(µ) ln 2, where√√∑ht (ω<t ) := a∈X ( ξ(a|ω<t ) − µ(a|ω<t ))2 .
• Instantaneous i.i.d. bounds: For i.i.d. M with continuous, discrete,
and universal prior, respectively:
× 1
× 1
−1
E[hn ] < n ln w(µ) and E[hn ] < n ln wµ−1 = n1 K(µ) ln 2.

• Bounds for computable environments: Rapidly M (xt |x<t ) → 1 onevery computable sequence x1:∞ (whichsoever, e.g. 1∞ or the digitsof π or e), i.e. M quickly recognizes the structure of the sequence.
• Weak instantaneous bounds: valid for all n and x1:n and x̄n ̸= xn :
×
×
−K(n)
2
< M (x̄n |x<n ) < 22K(x1:n ∗)−K(n)n × −K(n)• Magic instance numbers: e.g. M (0|1 ) = 2→ 0, but spikes
up for simple n. M is cautious at magic instance numbers n.
• Future bounds / errors to come: If our past observations ω1:n
containa lot of information
about µ, we make few errors in future:∑∞+t=n+1 E[ht |ω1:n ] < [K(µ|ω1:n )+K(n)] ln 2

Marcus Hutter- 63 -

Universal Induction & Intelligence

More Stuﬀ / Critique / Problems• Prior knowledge y can be incorporated by using “subjective” priorUwν|y= 2−K(ν|y) or by preﬁxing observation x by y.
• Additive/multiplicative constant fudges and U -dependence is often(but not always) harmless.
• Incomputability: K and M can serve as “gold standards” which
practitioners should aim at, but have to be (crudely) approximatedin practice (MDL [Ris89], MML [Wal05], LZW [LZ76], CTW [WSTT95],
NCD [CV05]).
• The Minimum Description Length Principle:
M (x) ≈ 2−KU (x) ≈ 2−KT (x) . Predict y of highest M (y|x) is
approximately same as MDL: Predict y of smallest KT (xy).

Marcus Hutter- 64 -

Universal Induction & Intelligence

Universal Inductive Inference: Summary
Universal Solomonoﬀ prediction solves/avoids/meliorates many problemsof (Bayesian) induction. We discussed:+ general total bounds for generic class, prior, and loss,+ i.i.d./universal-speciﬁc instantaneous and future bounds,+ the Dn bound for continuous classes,+ indiﬀerence/symmetry principles,+ the problem of zero p(oste)rior & conﬁrm. of universal hypotheses,+ reparametrization and regrouping invariance,+ the problem of old evidence and updating,+ that M works even in non-computable environments,+ how to incorporate prior knowledge,− the prediction of short sequences,− the constant fudges in all results and the U -dependence,− M ’s incomputability and crude practical approximations.

Marcus Hutter- 65 -

Universal Induction & Intelligence

Outlook• Relation to Prediction with Expert Advice• Relation to the Minimal Description Length (MDL) Principle• Generalization to Active/Reinforcement learning (AIXI)Open Problems• Prediction of selected bits
• Convergence of M on Martin-Loef random sequences• Better instantaneous bounds for M• Future bounds for Bayes (general ξ)Marcus Hutter- 66 -

Universal Induction & Intelligence

UNIVERSAL RATIONAL AGENTS• Rational agents• Sequential decision theory• Reinforcement learning• Value function• Universal Bayes mixture and AIXI model• Self-optimizing and Pareto-optimal policies• Environmental Classes• The horizon problem• Computational Issues

Marcus Hutter- 67 -

Universal Induction & Intelligence

Universal Rational Agents: Abstract
Sequential decision theory formally solves the problem of rational agentsin uncertain worlds if the true environmental prior probability distribution
is known. Solomonoﬀ’s theory of universal induction formally solves the
problem of sequence prediction for unknown prior distribution.
Here we combine both ideas and develop an elegant parameter-freetheory of an optimal reinforcement learning agent embedded in anarbitrary unknown environment that possesses essentially all aspects ofrational intelligence. The theory reduces all conceptual AI problems topure computational ones.
There are strong arguments that the resulting AIXI model is the mostintelligent unbiased agent possible. Other discussed topics are relations
between problem classes, the horizon problem, and computational issues.

Marcus Hutter- 68 -

Universal Induction & Intelligence

The Agent Model
Most if not all AI problems can beformulated within the agent
framework
r1 | o1 r2 | o2 r3 | o3 r4 | o4 r5 | o5 r6 | o6







work

y1

Agent
p

tape ...

y2

y3

...

H
YH
HH
H

work

Environtape ...
ment q

PP
1



PP


PP

q
P
y4

y5

y6

...

Marcus Hutter- 69 -

Universal Induction & Intelligence

Rational Agents in Deterministic Environments- p : X ∗ → Y ∗ is deterministic policy of the agent,p(x<k ) = y1:k with x<k ≡ x1 ...xk−1 .
- q : Y ∗ → X ∗ is deterministic environment,q(y1:k ) = x1:k with y1:k ≡ y1 ...yk .
- Input xk ≡ rk ok consists of a regular informative part ok
and reward rk ∈ [0..rmax ].
pq- Value Vkm:= rk + ... + rm ,pq
optimal policy pbest := arg maxp V1m,
Lifespan or initial horizon m.

Marcus Hutter- 70 -

Universal Induction & Intelligence

Agents in Probabilistic Environments
Given history y1:k x<k , the probability that the environment leads toperception xk in cycle k is (by deﬁnition) σ(xk |y1:k x<k ).
Abbreviation (chain rule)σ(x1:m |y1:m ) = σ(x1 |y1 )·σ(x2 |y1:2 x1 )· ... ·σ(xm |y1:m x<m )The average value of policy p with horizon m in environment σ isdeﬁned as∑
1
Vσp := m(r1 + ... +rm )σ(x1:m |y1:m )|y1:m =p(x<m )x1:m

The goal of the agent should be to maximize the value.

Marcus Hutter- 71 -

Universal Induction & Intelligence

Optimal Policy and Valueσ

The σ-optimal policy p

∗
pσ
p
p
:= arg maxp Vσ maximizes Vσ ≤ Vσ := Vσ .

Explicit expressions for the action yk in cycle k of the σ-optimal policy
pσ and their value Vσ∗ are
∑
∑
∑
max
... max(rk + ... +rm )·σ(xk:m |y1:m x<k ),yk = arg max
yk

xk

1
Vσ∗ = m
max
y1

yk+1

∑
x1

xk+1

max
y2

∑
x2

ym

xm

... maxym

Keyword: Expectimax tree/algorithm.

∑xm(r1 + ... +rm )·σ(x1:m |y1:m ).

Marcus Hutter- 72 -

Universal Induction & Intelligence

Expectimax Tree/Algorithm
r Vσ∗ (yx<k ) = max Vσ∗ (yx<k yk )yk@max
| {z @}
action yk with max value.
@
yk = 0yk = 1∑@∗q@q Vσ (yx<k yk ) = [rk + Vσ∗ (yx1:k )]σ(xk |yx<k yk )
xk
A
A
E
E
|{z}
A
|{z}
A σ expected reward r and observation o .
kkok= 0 A ok= 1
A
ok= 0  ok= 1
rk= ... A rk= ... rk= ...  rk= ...AAq
Aq Vσ∗ (yx1:k ) = max Vσ∗ (yx1:k yk+1 )
q
q
yk+1
A yk+1 A yk+1 A yk+1 A
max
max
max
max

A

A

A

⌣
⌣
⌣
 A
 A
 A
 ⌣ AA

···

···

···

···

···

···

···

···

Marcus Hutter- 73 -

Universal Induction & Intelligence

Known environment µ• Assumption: µ is the true environment in which the agent operates• Then, policy pµ is optimal in the sense that no other policy for an
agent leads to higher µAI -expected reward.
• Special choices of µ: deterministic or adversarial environments,
Markov decision processes (mdps), adversarial environments.
• There is no principle problem in computing the optimal action yk aslong as µAI is known and computable and X , Y and m are ﬁnite.
• Things drastically change if µAI is unknown ...

Marcus Hutter- 74 -

Universal Induction & Intelligence

The Bayes-mixture distribution ξ
Assumption: The true environment µ is unknown.
Bayesian approach: The true probability distribution µAI is not learned
directly, but is replaced by a Bayes-mixture ξ AI .
Assumption: We know that the true environment µ is contained in someknown (ﬁnite or countable) set M of environments.
The Bayes-mixture ξ is deﬁned as∑wν ν(x1:m |y1:m )ξ(x1:m |y1:m ) :=
ν∈M

with

∑

wν = 1,wν > 0 ∀νν∈M

The weights wν may be interpreted as the prior degree of belief that thetrue environment is ν.
Then ξ(x1:m |y1:m ) could be interpreted as the prior subjective belief
probability in observing x1:m , given actions y1:m .

Marcus Hutter- 75 -

Universal Induction & Intelligence

Questions of Interest• It is natural to follow the policy pξ which maximizes Vξp .
• If µ is the true environment the expected reward when followingξpξ
policy p will be Vµ .
• The optimal (but infeasible) policy pµpµyields reward Vµ ≡ Vµ∗ .

•pξ
Are there policies with uniformly larger value than Vµ ?

•pξHow close is Vµ to Vµ∗ ?

• What is the most general class M and weights wν .

Marcus Hutter- 76 -

Universal Induction & Intelligence

A universal choice of ξ and M• We have to assume the existence of some structure on theenvironment to avoid the No-Free-Lunch Theorems [Wolpert 96].
• We can only unravel eﬀective structures which are describable by(semi)computable probability distributions.
• So we may include all (semi)computable (semi)distributions in M.
• Occam’s razor and Epicurus’ principle of multiple explanations tell
us to assign high prior belief to simple environments.
• Using Kolmogorov’s universal complexity measure K(ν) for
environments ν one should set wν ∼ 2−K(ν) , where K(ν) is thelength of the shortest program on a universal TM computing ν.
• The resulting AIXI model [Hutter:00] is a uniﬁcation of (Bellman’s)sequential decision and Solomonoﬀ’s universal induction theory.

Marcus Hutter- 77 -

Universal Induction & Intelligence

The AIXI Model in one Line
complete & essentially unique & limit-computable∑∑∑
AIXI: ak := arg max... max[rk + ... + rm ]2−length(p)
ak

ok rk

am

om rm

p : U (p,a1 ..am )=o1 r1 ..om rmk=now, action, observation, reward, U niversal TM, program, m=lifespanAIXI is an elegant mathematical theory of AI
Claim: AIXI is the most intelligent environmental independent, i.e.
universally optimal, agent possible.
Proof: For formalizations, quantiﬁcations, and proofs, see [Hut05].
Applications: Strategic Games, Function Optimization, Supervised
Learning, Sequence Prediction, Classiﬁcation, ...
In the following we consider generic M and wν .

Marcus Hutter- 78 -

Universal Induction & Intelligence

Pareto-Optimality of pξ
Policy pξ is Pareto-optimal in the sense that there is no other policy pppξ
with Vν ≥ Vν for all ν ∈ M and strict inequality for at least one ν.

Self-optimizing Policies
Under which circumstances does the value of the universal policy pξ
converge to optimum?
pξVν → Vν∗for horizon m → ∞for all ν ∈ M.

(1)

The least we must demand from M to have a chance that (1) is true isthat there exists some policy p̃ at all with this property, i.e.
∃p̃ : Vνp̃ → Vν∗for horizon m → ∞for all ν ∈ M.

(2)Main result: (2) ⇒ (1): The necessary condition of the existence of aself-optimizing policy p̃ is also suﬃcient for pξ to be self-optimizing.

Marcus Hutter- 79 -

Universal Induction & Intelligence

Environments w. (Non)Self-Optimizing Policies

Marcus Hutter- 80 -

Universal Induction & Intelligence

Particularly Interesting Environments• Sequence Prediction, e.g. weather√ or stock-market prediction.
∗pξStrong result: Vµ − Vµ = O(

K(µ)
m ),

m =horizon.

• Strategic Games: Learn to play well (minimax) strategic zero-sum
games (like chess) or even exploit limited capabilities of opponent.
• Optimization: Find (approximate) minimum of function with as few
function calls as possible. Diﬃcult exploration versus exploitation
problem.
• Supervised learning: Learn functions by presenting (z, f (z)) pairs
and ask for function values of z ′ by presenting (z ′ , ?) pairs.
Supervised learning is much faster than reinforcement learning.
AIξ quickly learns to predict, play games, optimize, and learn supervised.

Marcus Hutter- 81 -

Universal Induction & Intelligence

Future Value and the Right Discounting• Eliminate the arbitrary horizon parameterm by discounting the∑∞
rewards rk ; γk rk with Γk := i=k γi < ∞ and letting m → ∞:
πσ
Vkγ
:=
∑
1
lim
(γk rk +...+γm rm )σ(xk:m |y1:m x<k )|y1:m =p(x<m )Γk m→∞ x
k:m• If there exists a self-optimizing policy for M, then pξ ispξ µ k→∞∗µπ̃k ν k→∞∗ν
self-optimizing: If ∃π̃k ∀ν : Vkγ−→ Vkγ ⇒ Vkγ −→ Vkγ.
• Standard geometric discounting: γk = γ k with 0 < γ < 1.
Problem: Most environments do not possess self-optimizing policies
under this discounting, since eﬀective horizon heff
k is ﬁnite.
• Power discounting: γk = k −2 ⇒ heffk ∼ k = agent’s age.
Universal discounting: γk = 2−K(k) ⇒ heffk ∼ Ackermann(k)• Result: Policy pξ is self-optimizing for ergodic mdps if γk+1
γk → 1.

Marcus Hutter- 82 -

Universal Induction & Intelligence

Universal Rational Agents: Summary• Setup: Agents acting in general probabilistic environments withreinforcement feedback.
• Assumptions: True environment µ belongs to a known class ofenvironments M, but is otherwise unknown.
• Results: The Bayes-optimal policy pξ based on the Bayes-mixture∑ξ = ν∈M wν ν is Pareto-optimal and self-optimizing if M admits
self-optimizing policies.
• Application: The class of ergodic mdps admits self-optimizing
policies.
• New: Policy pξ with unbounded eﬀective horizon is the ﬁrst purely
Bayesian self-optimizing consistent policy for ergodic mdps.
• Learn: The combined conditions Γk < ∞ and γk+1
γk → 1 allow a
consistent self-optimizing Bayes-optimal policy based on mixtures.

Marcus Hutter- 83 -

Universal Induction & Intelligence

Universal Rational Agents: Remarks• We have developed a parameterless AI model based on sequential
decisions and algorithmic probability.
• We have reduced the AI problem to pure computational questions.
• AIξ seems not to lack any important known methodology of AI,
apart from computational aspects.
• There is no need for implementing extra knowledge, as this can belearned by presenting it in ok in any form.
• The learning process itself is an important aspect of AI.
• Noise or irrelevant information in the inputs do not disturb the AIξsystem.
• Philosophical questions: relevance of non-computational physics(Penrose), number of wisdom Ω (Chaitin), consciousness, social
consequences.

Marcus Hutter- 84 -

Universal Induction & Intelligence

Universal Rational Agents: Outlook• Continuous classes M.
• Restricted policy classes.
• Non-asymptotic bounds.
• Tighter bounds by exploiting extra properties of the environments,
like the mixing rate of mdps.
• Search for other performance criteria [Hutter:00].
• Instead of convergence of the expected reward sum, study
convergence with high probability of the actually realized rewardsum.
• Other environmental classes (separability concepts, downscaling).

Marcus Hutter- 85 -

Universal Induction & Intelligence

APPROXIMATIONS & APPLICATIONS• Universal Similarity Metric• Universal Search• Time-Bounded AIXI Model• Brute-Force Approximation of AIXI
• A Monte-Carlo AIXI Approximation• Feature Reinforcement Learning• Comparison to other approaches• Future directions, wrap-up, references.

Marcus Hutter- 86 -

Universal Induction & Intelligence

Approximations & Applications: Abstract
Many fundamental theories have to be approximated for practical use.
Since the core quantities of universal induction and universal intelligence
are incomputable, it is often hard, but not impossible, to approximate
them. In any case, having these “gold standards” to approximate(top→down) or to aim at (bottom→up) is extremely helpful in building
truly intelligent systems. The most impressive direct approximation of
Kolmogorov complexity to-date is via the universal similarity metricapplied to a variety of real-world clustering problems. A couple ofuniversal search algorithms ((adaptive) Levin search, FastPrg, OOPS,
Goedel-machine, ...) that ﬁnd short programs have been developed andapplied to a variety of toy problem. The AIXI model itself has been
approximated in a couple of ways (AIXItl, Brute Force, Monte Carlo,
Feature RL). Some recent applications will be presented. The Lecture
Series concludes by comparing various learning algorithms along various
dimensions, pointing to future directions, wrap-up, and references.

Marcus Hutter- 87 -

Universal Induction & Intelligence

Conditional Kolmogorov Complexity
Question: When is object=string x similar to object=string y?
Universal solution: x similar y ⇔ x can be easily (re)constructed from y⇔ Kolmogorov complexity K(x|y) := min{ℓ(p) : U (p, y) = x} is small
Examples:+1) x is very similar to itself (K(x|x) = 0)+

2) A processed x is similar to x (K(f (x)|x) = 0 if K(f ) = O(1)).
e.g. doubling, reverting, inverting, encrypting, partially deleting x.
3) A random string is with high probability not similar to any otherstring (K(random|y) =length(random)).
The problem with K(x|y) as similarity=distance measure is that it isneither symmetric nor normalized nor computable.

Marcus Hutter- 88 -

Universal Induction & Intelligence

The Universal Similarity Metric [CV’05]• Symmetrization and normalization leads to a/the universal metric d:max{K(x|y), K(y|x)}0 ≤ d(x, y) :=≤ 1
max{K(x), K(y)}• Every eﬀective similarity between x and y is detected by d
• Use K(x|y) ≈ K(xy)−K(y) and K(x) ≡ KU (x) ≈ KT (x) (coding )T=⇒ computable approximation: Normalized compression distance:
KT (xy) − min{KT (x), KT (y)}d(x, y) ≈. 1
max{KT (x), KT (y)}• For T choose Lempel-Ziv or gzip or bzip(2) (de)compressor in theapplications below.
• Theory: Lempel-Ziv compresses asymptotically better than any
probabilistic ﬁnite state automaton predictor/compressor.

Marcus Hutter- 89 -

Universal Induction & Intelligence

Tree-Based Clustering [CV’05]• If many objects x1 , ..., xn need to be compared, determine the
Similarity matrix: Mij = d(xi , xj ) for 1 ≤ i, j ≤ n• Now cluster similar objects.
• There are various clustering techniques.
• Tree-based clustering: Create a tree connecting similar objects,• e.g. quartet method (for clustering)• Applications: Phylogeny of 24 Mammal mtDNA,
50 Language Tree (based on declaration of human rights),
composers of music, authors of novels, SARS virus, fungi,
optical characters, galaxies, ...
[Cilibrasi&Vitanyi’05]

Marcus Hutter- 90 -

Universal Induction & Intelligence

Genomics & Phylogeny: Mammals [CV’05]
Evolutionary tree built from complete mammalian mtDNA of 24 species:
Carp
Cow
BlueWhale
FinbackWhaleCat
BrownBear
PolarBear
GreySeal
HarborSeal
Horse
WhiteRhino
GibbonGorillaHuman
Chimpanzee
PygmyChimp
Orangutan
SumatranOrangutan
HouseMouse
Rat
Opossum
Wallaroo
Echidna
Platypus

Ferungulates

Eutheria

Primates

Eutheria - Rodents
Metatheria
Prototheria

Language Tree (Re)construction
SLAVIC

based on “The Universal Declaration of
Human Rights” in 50 languages.
BALTICALTAICROMANCECELTICGERMANICUGROFINNIC

Basque [Spain]
Hungarian [Hungary]
Polish [Poland]
Sorbian [Germany]
Slovak [Slovakia]
Czech [Czech Rep]
Slovenian [Slovenia]
Serbian [Serbia]
Bosnian [Bosnia]
Croatian [Croatia]
Romani Balkan [East Europe]
Albanian [Albany]
Lithuanian [Lithuania]
Latvian [Latvia]
Turkish [Turkey]
Uzbek [Utzbekistan]
Breton [France]
Maltese [Malta]
OccitanAuvergnat [France]
Walloon [Belgique]
English [UK]French [France]
Asturian [Spain]
Portuguese [Portugal]
Spanish [Spain]
Galician [Spain]
Catalan [Spain]
Occitan [France]
Rhaeto Romance [Switzerland]
Friulian [Italy]
Italian [Italy]
Sammarinese [Italy]
Corsican [France]
Sardinian [Italy]
Romanian [Romania]
Romani Vlach [Macedonia]
Welsh [UK]Scottish Gaelic [UK]Irish Gaelic [UK]German [Germany]
Luxembourgish [Luxembourg]
Frisian [Netherlands]
Dutch [Netherlands]
Afrikaans
Swedish [Sweden]
Norwegian Nynorsk [Norway]
Danish [Denmark]Norwegian Bokmal [Norway]
Faroese [Denmark]Icelandic [Iceland]
Finnish [Finland]
Estonian [Estonia]

Marcus Hutter- 92 -

Universal Induction & Intelligence

Universal Search• Levin search: Fastest algorithm forinversion and optimization problems.
• Theoretical application:
Assume somebody found a non-constructive
proof of P=NP, then Levin-search is a polynomial
time algorithm for every NP (complete) problem.
• Practical (OOPS) applications (J. Schmidhuber)
Maze, towers of hanoi, robotics, ...
• FastPrg: The asymptotically fastest and shortest algorithm for all
well-deﬁned problems.
• AIXItl: Computable variant of AIXI.
• Human Knowledge Compression Prize: (50’000=
C)Marcus Hutter- 93 -

Universal Induction & Intelligence

The Time-Bounded AIXI Model (AIXItl)
An algorithm pbest has been constructed for which the following holds:• Let p be any (extended chronological) policy• with length ℓ(p) ≤ ˜l and computation time per cycle t(p) ≤ t̃
• for which there exists a proof of length ≤ lP that p is a valid
approximation.
• Then an algorithm pbest can be constructed, depending on ˜l,t̃ andlP but not on knowing p• which is eﬀectively more or equally intelligent according to ≽c thanany such p.
• The size of pbest is ℓ(pbest ) = O(ln(˜l· t̃·lP )),• the setup-time is tsetup (pbest ) = O(lP2 ·2lP ),• the computation time per cycle is tcycle (pbest ) = O(2l̃ · t̃).

Marcus Hutter- 94 -

Universal Induction & Intelligence

Brute-Force Approximation of AIXI
• Truncate expectimax tree depth to a small ﬁxed lookahead h.
Optimal action computable in time |Y ×X |h × time to evaluate ξ.
• Consider mixture over Markov Decision Processes (MDP) only, i.e.
∑∏mξ(x1:m |y1:m ) = ν∈M wν t=1 ν(xt |xt−1 yt ). Note: ξ is not MDP• Choose uniform prior over wµ .
Then ξ(x1:m |y1:m ) can be computed in linear time.
• Consider (approximately) Markov problems
with very small action and perception space.
• Example application: 2×2 Matrix Games like Prisoner’S Dilemma,
Stag Hunt, Chicken, Battle of Sexes, and Matching Pennies. [PH’06]

Marcus Hutter- 95 -

Universal Induction & Intelligence

AIXI Learns to Play 2×2 Matrix Games• Repeated prisoners dilemma.

Loss matrix• Game unknown to AIXI.
Must be learned as well

avg. p. round cooperation ratio• AIXI behaves appropriately.
1
0.8

AIXI vs. random
AIXI vs. tit4tat
AIXI vs. 2−tit4tat
AIXI vs. 3−tit4tat
AIXI vs. AIXIAIXI vs. AIXI2

0.6
0.4
0.2
0
0

20

40

60
t

80

100

Marcus Hutter- 96 -

Universal Induction & Intelligence

A Monte-Carlo AIXI Approximation
Consider class of Variable-Order Markov Decision Processes.
The Context Tree Weighting (CTW) algorithm can eﬃciently mix(exactly in essentially linear time) all prediction suﬃx trees.
a1Monte-Carlo approximation of expectimax tree:
Upper Conﬁdence Tree (UCT) algorithm:• Sample observations from CTW distribution.
• Select actions with highest upper conﬁdence bound.
• Expand tree by one leaf node (per trajectory).
• Simulate from leaf node further down using (ﬁxed) playout policy.
• Propagate back the value estimates for each node.
Repeat until timeout.
[VNHS’09]
o1

o2

a2

a3

o3

o4

future reward estimate

Guaranteed to converge to exact value.
Extension: Predicate CTW not based on raw obs. but features thereof.

Marcus Hutter- 97 -

Universal Induction & Intelligence

Monte-Carlo AIXI Applications

Norm. Av. Reward per Trial

1

Normalized Learning Scalability

0100[Joel Veness et al. 2009]

Experience
1000

10000

Optimum
Tiger
4x4 Grid
1d Maze
Extended Tiger
TicTacToe
Cheese Maze
Pocman*1000001000000

Marcus Hutter- 98 -

Universal Induction & Intelligence

Feature Reinforcement Learning (FRL)
Goal: Develop eﬃcient general purpose intelligent agent.
State-of-the-art: (a) AIXI: Incomputable theoretical solution.
(b) MDP: Eﬃcient limited problem class.
(c) POMDP: Notoriously diﬃcult. (d) PSRs: Underdeveloped.
Idea: ΦMDP reduces real problem to MDP automatically by learning.
Accomplishments so far: (i) Criterion for evaluating quality of reduction.
(ii) Integration of the various parts into one learning algorithm.
(iii) Generalization to structured MDPs (DBNs)ΦMDP is promising path towards the grand goal & alternative to (a)-(d)Problem: Find reduction Φ eﬃciently (generic optimization problem?)Marcus Hutter- 99 -

Universal Induction & Intelligence

Markov Decision Processes (MDPs)
a computationally tractable class of problems
MDP• MDP Assumption: State st := ot and rt are  Example
s1 - 
s3 r2
probabilistic functions of ot−1 and at−1 only. -r1 6 
?
r4 • Further Assumption:


3
4 
2
r
s
s
State=observation space § is ﬁnite and small.
 • Goal: Maximize long-term expected reward.
• Learning: Probability distribution is unknown but can be learned.
• Exploration: Optimal exploration is intractable
but there are polynomial approximations.
• Problem: Real problems are not of this simple form.

Marcus Hutter- 100 -

Universal Induction & Intelligence

Map Real Problem to MDP
Map history ht := o1 a1 r1 ...ot−1 to state st := Φ(ht ), for example:
Games: Full-information with static opponent: Φ(ht ) = ot .
Classical physics: Position+velocity of objects = position at two
time-slices: st = Φ(ht ) = ot ot−1 is (2nd order) Markov.
I.i.d. processes of unknown probability (e.g. clinical trials ≃ Bandits),∑nFrequency of obs. Φ(hn ) = ( t=1 δot o )o∈O is suﬃcient statistic.
Identity: Φ(h) = h is always suﬃcient, but not learnable.

Find/Learn Map AutomaticallyΦbest := arg minΦ Cost(Φ|ht )• What is the best map/MDP? (i.e. what is the right Cost criterion?)• Is the best MDP good enough? (i.e. is reduction always possible?)• How to ﬁnd the map Φ (i.e. minimize Cost) eﬃciently?

Marcus Hutter- 101 -

Universal Induction & IntelligenceΦMDP: Computational Flow
Transition Pr. T̂ exploration
e
e
T̂
,
R̂
bonus
Reward est. R̂@frequency estimate
Bellman @
R


 @




Feature Vec. Φ̂
6Cost(Φ|h) minimization

History h
6reward r observation oEnvironment(Q̂) V̂alue
implicit?
Best Policy p̂
action a?

Marcus Hutter- 102 -

Universal Induction & IntelligenceIntelligent Agents in PerspectiveUniversal AI(AIXI)



C J @

C J @

C
J
@

C
J

@
Feature RL (ΦMDP/DBN/..)
@

@

C
J

C
J
@

J
@


 C

Learning
Planning
Complexity
Information




@
@
Search – Optimization – Computation – Logic – KR
Agents = General Framework, Interface = Robots,Vision,LanguageMarcus Hutter- 103 -

Universal Induction & Intelligence

Properties of Learning Algorithms
pomdp

learning

NO
YES
YES

NO
NO
no

NO yesYES YESYES YES

Logic Planners
RL with Split Trees
Pred.w. Expert Advice
OOPS
Market/Economy RL

yes/no YES yes
yes YES no
yes/no YES –yes/no no–
yes/no no NO

YES nono YES yesNO
yes YES YES YES
yes/no yes
NO YES NO
yes/no YES YES YES YES
no/yes yes yes/no YES YES

SPXI
AIXI
AIXItlMC-AIXI-CTW
Feature RL
Humanno YES –YESNO YES YES yes
no/yes YES YES YES
yes/no yes YES YES
yes/no YES yes
yes
yes
yes yes no/yes

YES
YES
YES
yes
no

YES
YES
yes
yes
yes
NO

activegeneralization

YES
NO
NO

convergence

yes/no yes –YESno/yes NO NO no/yes
no/yes YES NO no/yes

data
eﬃcient
exploration

Value/Policy iteration
TD w. func.approx.
Direct Policy Search

Algorithm

timeeﬃcient

globaloptimum

Properties

Comparison of AIXI to Other Approaches

YES NO YES NOYES YES YES YESYES YES YES YES
NO yes/no YES YES
yes
yes YES YESYES YES YES YES

Marcus Hutter- 104 -

Universal Induction & Intelligence⋆= yes, ·= no,•= debatable,? = unknown.
Intelligence Test

Valid

Informative

Wide Range

GeneralDynamic

Unbiased

Fundamental

FormalObjective

Fully Defined

Universal

Practical

Test vs. Def.

Machine Intelligence Tests & Deﬁnitions

Turing Test
Total Turing Test
Inverted Turing Test
Toddler Turing Test
Linguistic Complexity
Text Compression Test
Turing Ratio
Psychometric AI
Smith’s Test
C-Test
AIXI

•
•
•
•
•
•
•
⋆
•
•
⋆

·
·
•
·
⋆
⋆
⋆
⋆
⋆
⋆
⋆

·
·
·
·
•
⋆
⋆
•
⋆
⋆
⋆

·
·
·
·
·
•
⋆
⋆
•
•
⋆

•
•
•
•
·
·
?
?
·
·
⋆

·
·
·
·
·
•
?
•
?
⋆
⋆

·
·
·
·
·
•
?
·
⋆
⋆
⋆

·
·
·
·
•
⋆
?
•
⋆
⋆
⋆

·
·
·
·
•
⋆
?
•
⋆
⋆
⋆

•
•
•
·
·
⋆
·
•
·
⋆
⋆

·
·
·
·
•
•
?
·
?
⋆
⋆

•
·
•
•
•
⋆
?
•
•
⋆
·

T
T
T
T
T
T
T/D
T/D
T/D
T/D
D

Marcus Hutter- 105 -

Universal Induction & Intelligence

Common Criticisms• AIXI is obviously wrong.
(intelligence cannot be captured in a few simple equations)• AIXI is obviously correct. (everybody already knows this)• Assuming that the environment is computable is too strong.
• All standard objections to strong AI also apply to AIXI.
(free will, lookup table, Lucas/Penrose Goedel argument)• AIXI doesn’t deal with X or cannot do X.
(X = consciousness, creativity, imagination, emotion, love, soul, etc.)• AIXI is not intelligent because it cannot choose its goals.
• Universal AI is impossible due to the No-Free-Lunch theorem.
See [Legg:08] for refutations of these and more criticisms.

Marcus Hutter- 106 -

Universal Induction & Intelligence

General Murky & Quirky AI Questions• Does current mainstream AI research has anything todo with AI?
• Are sequential decision and algorithmic probability theory
all we need to well-deﬁne AI?
• What is (Universal) AI theory good for?
• What are robots good for in AI?
• Is intelligence a fundamentally simple concept?
(compare with fractals or physics theories)• What can we (not) expect from super-intelligent agents?
• Is maximizing the expected reward the right criterion?
• Isn’t universal learning impossible due to the NFL theorems?

Marcus Hutter- 107 -

Universal Induction & Intelligence

Next Steps• Address the many open theoretical questions (see Hutter:05).
• Bridge the gap between (Universal) AI theory and AI practice.
• Explore what role logical reasoning, knowledge representation,
vision, language, etc. play in Universal AI.
• Determine the right discounting of future rewards.
• Develop the right nurturing environment for a learning agent.
• Consider embodied agents (e.g. internal↔external reward)• Analyze AIXI in the multi-agent setting.

Marcus Hutter- 108 -

Universal Induction & Intelligence

The Big Questions• Is non-computational physics relevant to AI? [Penrose]• Could something like the number of wisdom Ω prevent a simple
solution to AI? [Chaitin]• Do we need to understand consciousness before being able tounderstand AI or construct AI systems?
• What if we succeed?

Marcus Hutter- 109 -

Universal Induction & Intelligence

Wrap Up• Setup: Given (non)iid data D = (x1 , ..., xn ), predict xn+1
• Ultimate goal is to maximize proﬁt or minimize loss
• Consider Models/Hypothesis Hi ∈ M• Max.Likelihood: Hbest = arg maxi p(D|Hi ) (overﬁts if M large)• Bayes: Posterior probability of Hi is p(Hi |D) ∝ p(D|Hi )p(Hi )• Bayes needs prior(Hi )• Occam+Epicurus: High prior for simple models.
• Kolmogorov/Solomonoﬀ: Quantiﬁcation of simplicity/complexity• Bayes works if D is sampled from Htrue ∈ M• Bellman equations tell how to optimally act in known environments• Universal AI = Universal Induction + Sequential Decision Theory• Practice = approximate, restrict, search, optimize, knowledgeMarcus Hutter- 110 -

Universal Induction & Intelligence

Literature[CV05]

R. Cilibrasi and P. M. B. Vitányi. Clustering by compression. IEEE
Trans. Information Theory, 51(4):1523–1545, 2005.

[Hut05] M. Hutter. Universal Artificial Intelligence: Sequential Decisions
based on Algorithmic Probability. Springer, Berlin, 2005.
[Hut07] M. Hutter. On universal prediction and Bayesian confirmation.
Theoretical Computer Science, 384(1):33–48, 2007.
[LH07]

S. Legg and M. Hutter. Universal intelligence: a definition ofmachine intelligence. Minds & Machines, 17(4):391–444, 2007.

[Hut09] M. Hutter. Feature reinforcement learning: Part I: Unstructured
MDPs. Journal of Artificial General Intelligence, 1:3–24, 2009.
[VNHS09] J. Veness, K. S. Ng, M. Hutter, and D. Silver. A Monte Carlo AIXI
approximation. Technical report, NICTA, Australia, 2009.

Marcus Hutter

Thanks!

- 111 -

Universal Induction & Intelligence

Questions?

Details:

Jobs: PostDoc and PhD positions at RSISE and NICTA, Australia

Projects at http://www.hutter1.net/

A Uniﬁed View of Artiﬁcial Intelligence==
Decision Theory= Probability + Utility Theory++
Universal Induction = Ockham + Bayes + Turing

Open research problems at www.hutter1.net/ai/uaibook.htm
Compression contest with 50’000=
C prize at prize.hutter1.net