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 Discussionin 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:

- 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?).

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

@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 |