Bad Universal Priors and Notions of Optimality

Jan Leike, Marcus Hutter
; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1244-1259, 2015.

Abstract

A big open question of algorithmic information theory is the choice of the universal Turing machine (UTM). For Kolmogorov complexity and Solomonoff induction we have invariance theorems: the choice of the UTM changes bounds only by a constant. For the universally intelligent agent AIXI (Hutter, 2005) no invariance theorem is known. Our results are entirely negative: we discuss cases in which unlucky or adversarial choices of the UTM cause AIXI to misbehave drastically. We show that Legg-Hutter intelligence and thus balanced Pareto optimality is entirely subjective, and that every policy is Pareto optimal in the class of all computable environments. This undermines all existing optimality properties for AIXI. While it may still serve as a gold standard for AI, our results imply that AIXI is a \emphrelative theory, dependent on the choice of the UTM.

Cite this Paper


BibTeX
@InProceedings{pmlr-v40-Leike15, title = {Bad Universal Priors and Notions of Optimality}, author = {Jan Leike and Marcus Hutter}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {1244--1259}, year = {2015}, editor = {Peter Grünwald and Elad Hazan and Satyen Kale}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Leike15.pdf}, url = {http://proceedings.mlr.press/v40/Leike15.html}, abstract = {A big open question of algorithmic information theory is the choice of the universal Turing machine (UTM). For Kolmogorov complexity and Solomonoff induction we have invariance theorems: the choice of the UTM changes bounds only by a constant. For the universally intelligent agent AIXI (Hutter, 2005) no invariance theorem is known. Our results are entirely negative: we discuss cases in which unlucky or adversarial choices of the UTM cause AIXI to misbehave drastically. We show that Legg-Hutter intelligence and thus balanced Pareto optimality is entirely subjective, and that every policy is Pareto optimal in the class of all computable environments. This undermines all existing optimality properties for AIXI. While it may still serve as a gold standard for AI, our results imply that AIXI is a \emphrelative theory, dependent on the choice of the UTM.} }
Endnote
%0 Conference Paper %T Bad Universal Priors and Notions of Optimality %A Jan Leike %A Marcus Hutter %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Leike15 %I PMLR %J Proceedings of Machine Learning Research %P 1244--1259 %U http://proceedings.mlr.press %V 40 %W PMLR %X A big open question of algorithmic information theory is the choice of the universal Turing machine (UTM). For Kolmogorov complexity and Solomonoff induction we have invariance theorems: the choice of the UTM changes bounds only by a constant. For the universally intelligent agent AIXI (Hutter, 2005) no invariance theorem is known. Our results are entirely negative: we discuss cases in which unlucky or adversarial choices of the UTM cause AIXI to misbehave drastically. We show that Legg-Hutter intelligence and thus balanced Pareto optimality is entirely subjective, and that every policy is Pareto optimal in the class of all computable environments. This undermines all existing optimality properties for AIXI. While it may still serve as a gold standard for AI, our results imply that AIXI is a \emphrelative theory, dependent on the choice of the UTM.
RIS
TY - CPAPER TI - Bad Universal Priors and Notions of Optimality AU - Jan Leike AU - Marcus Hutter BT - Proceedings of The 28th Conference on Learning Theory PY - 2015/06/26 DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Leike15 PB - PMLR SP - 1244 DP - PMLR EP - 1259 L1 - http://proceedings.mlr.press/v40/Leike15.pdf UR - http://proceedings.mlr.press/v40/Leike15.html AB - A big open question of algorithmic information theory is the choice of the universal Turing machine (UTM). For Kolmogorov complexity and Solomonoff induction we have invariance theorems: the choice of the UTM changes bounds only by a constant. For the universally intelligent agent AIXI (Hutter, 2005) no invariance theorem is known. Our results are entirely negative: we discuss cases in which unlucky or adversarial choices of the UTM cause AIXI to misbehave drastically. We show that Legg-Hutter intelligence and thus balanced Pareto optimality is entirely subjective, and that every policy is Pareto optimal in the class of all computable environments. This undermines all existing optimality properties for AIXI. While it may still serve as a gold standard for AI, our results imply that AIXI is a \emphrelative theory, dependent on the choice of the UTM. ER -
APA
Leike, J. & Hutter, M.. (2015). Bad Universal Priors and Notions of Optimality. Proceedings of The 28th Conference on Learning Theory, in PMLR 40:1244-1259

Related Material