Towards a Universal Theory of Artificial Intelligence based on Algorithmic Probability and Sequential Decisions
Keywords: Artificial intelligence, Rational agents, sequential
decision theory, universal Solomonoff induction, algorithmic
probability, reinforcement learning, computational complexity, theorem
proving, probabilistic reasoning, Kolmogorov complexity, Levin search.
Abstract: Decision theory formally solves the problem of
rational agents in uncertain worlds if the true environmental
probability distribution is known. Solomonoff's theory of universal
induction formally solves the problem of sequence prediction for
unknown distribution. We unify both theories and give strong arguments
that the resulting universal AIXI model behaves optimally in any
computable environment. The major drawback of the AIXI model is that
it is uncomputable. To overcome this problem, we construct a modified
algorithm AIXI^tl, which is still superior to any other time t and
space l bounded agent. The computation time of AIXI^tl is of the order
t x 2^l.
Contents:
- Introduction
- Rational Agents & Sequential Decisions
- Algorithmic Complexity and Universal Induction
- The Universal AIXI Model
- Time Bounds and Effectiveness
- Outlook & Discussion
Reviewer:
Great theory. Extends a major theoretical direction that lead to practical MDL and MML.
This approach may do the same thing (similar thing) wrt to decision theory
and reinforcement learning, to name a few. Obviously a definite accept ...
If claims are true, this could be the foundation of a theory which might
inspire AI and MC for years (decades?).
BibTeX Entry
@Article{Hutter:01aixi,
author = "Marcus Hutter",
number = "IDSIA-14-00",
institution = "Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA)",
title = "Towards a Universal Theory of Artificial Intelligence based on Algorithmic
Probability and Sequential Decisions",
month = sep,
year = "2001",
pages = "226--238",
address = "Manno(Lugano), CH",
journal = "Proceedings of the 12$^{th}$ European Conference on
Machine Learning (ECML-2001)",
editor = "Luc De Raedt and Peter Flach",
publisher = "Springer",
series = "Lecture Notes in Artificial Intelligence (LNAI 2167)",
keywords = "Artificial intelligence, Rational agents,
sequential decision theory, universal Solomonoff induction,
algorithmic probability, reinforcement learning, computational
complexity, theorem proving, probabilistic reasoning, Kolmogorov
complexity, Levin search.",
url = "http://www.hutter1.net/ai/paixi.htm",
url2 = "http://arxiv.org/abs/cs.AI/0012011",
ftp = "ftp://ftp.idsia.ch/pub/techrep/IDSIA-14-00.ps.gz",
categories = "I.2. [Artificial Intelligence],
I.2.3. [Deduction and Theorem Proving],
I.2.6. [Learning],
I.2.8. [Problem Solving, Control Methods and Search],
F.1.3. [Complexity Classes],
F.2. [Analysis of Algorithms and Problem Complexity]",
abstract = "Decision theory formally solves the problem of rational agents in
uncertain worlds if the true environmental probability
distribution is known. Solomonoff's theory of universal induction
formally solves the problem of sequence prediction for unknown
distribution. We unify both theories and give strong arguments
that the resulting universal AIXI model behaves optimal in any
computable environment. The major drawback of the AIXI model is
that it is uncomputable. To overcome this problem, we construct a
modified algorithm AIXI^tl, which is still superior to any
other time t and space l bounded agent. The computation time
of AIXI^tl is of the order t x 2^l.",
note = "ftp.idsia.ch/pub/techrep/IDSIA-14-00.ps.gz",
}