On the Computability of AIXI

Jan Leike, Marcus Hutter
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:239-248, 2015.

Abstract

How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. In this paper, we quantify this using the arithmetical hierarchy, and prove upper and corresponding lower bounds for incomputability. We show that AIXI is not limit computable, thus it cannot be approximated using finite computation. Our main result is a limit-computable $\varepsilon$-optimal version of AIXI with infinite horizon that maximizes expected rewards.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-leike15a, title = {On the Computability of {AIXI}}, author = {Leike, Jan and Hutter, Marcus}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {239--248}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/leike15a/leike15a.pdf}, url = {https://proceedings.mlr.press/r13/leike15a.html}, abstract = {How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. In this paper, we quantify this using the arithmetical hierarchy, and prove upper and corresponding lower bounds for incomputability. We show that AIXI is not limit computable, thus it cannot be approximated using finite computation. Our main result is a limit-computable $\varepsilon$-optimal version of AIXI with infinite horizon that maximizes expected rewards.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T On the Computability of AIXI %A Jan Leike %A Marcus Hutter %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-leike15a %I PMLR %P 239--248 %U https://proceedings.mlr.press/r13/leike15a.html %V R13 %X How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. In this paper, we quantify this using the arithmetical hierarchy, and prove upper and corresponding lower bounds for incomputability. We show that AIXI is not limit computable, thus it cannot be approximated using finite computation. Our main result is a limit-computable $\varepsilon$-optimal version of AIXI with infinite horizon that maximizes expected rewards. %Z Reissued by PMLR on 04 October 2026.
APA
Leike, J. & Hutter, M.. (2015). On the Computability of AIXI. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:239-248 Available from https://proceedings.mlr.press/r13/leike15a.html. Reissued by PMLR on 04 October 2026.

Related Material