previous  home  search  LaTeX (52kb)   PostScript (189kb)   PDF (204kb)   Html/Gif   contact    up    next  

Towards a Universal Theory of Artificial Intelligence based on Algorithmic Probability and Sequential Decisions


Author: Marcus Hutter (2000)
Comments: 13 pages
Subj-class: Artificial Intelligence; Learning;

ACM-class:  

I.2; F.1.3; E.4
Reference: Proceedings of the 12th European Conference on Machine Learning (ECML-2001) 226-238
Report-no: IDSIA-14-00 and cs.AI/0012011
Paper: LaTeX (52kb)  -  PostScript (189kb)  -  PDF (204kb)  -  Html/Gif
Slides: PostScript - PDF
Discussion in the AGI mailing list (2002, 2003)

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:

  1. Introduction
  2. Rational Agents & Sequential Decisions
  3. Algorithmic Complexity and Universal Induction
  4. The Universal AIXI Model
  5. Time Bounds and Effectiveness
  6. 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?).
 previous  home  search  LaTeX (52kb)   PostScript (189kb)   PDF (204kb)   Html/Gif   contact    up    next  

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",
}
      
 previous  home  search  LaTeX (52kb)   PostScript (189kb)   PDF (204kb)   Html/Gif   contact    up    next