On the computability of solomonoff induction and knowledge-seeking

Jan Leike; Marcus Hutter

doi:10.1007/978-3-319-24486-0_24

On the computability of solomonoff induction and knowledge-seeking

Jan Leike^*, Marcus Hutter

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Citations (Scopus)

Abstract

Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff’s prior M in the arithmetical hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.

Original language	English
Title of host publication	Algorithmic Learning Theory - 26th International Conference, ALT 2015
Editors	Claudio Gentile, Sandra Zilles, Kamalika Chaudhuri
Publisher	Springer Verlag
Pages	364-378
Number of pages	15
ISBN (Print)	9783319244853
DOIs	https://doi.org/10.1007/978-3-319-24486-0_24
Publication status	Published - 2015
Event	26th International Conference on Algorithmic Learning Theory, ALT 2015 - Banff, Canada Duration: 4 Oct 2015 → 6 Oct 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9355
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Conference on Algorithmic Learning Theory, ALT 2015
Country/Territory	Canada
City	Banff
Period	4/10/15 → 6/10/15

Access to Document

10.1007/978-3-319-24486-0_24

Cite this

Leike, J., & Hutter, M. (2015). On the computability of solomonoff induction and knowledge-seeking. In C. Gentile, S. Zilles, & K. Chaudhuri (Eds.), Algorithmic Learning Theory - 26th International Conference, ALT 2015 (pp. 364-378). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9355). Springer Verlag. https://doi.org/10.1007/978-3-319-24486-0_24

Leike, Jan ; Hutter, Marcus. / On the computability of solomonoff induction and knowledge-seeking. Algorithmic Learning Theory - 26th International Conference, ALT 2015. editor / Claudio Gentile ; Sandra Zilles ; Kamalika Chaudhuri. Springer Verlag, 2015. pp. 364-378 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{27983565ff944737800418a52724b0ce,

title = "On the computability of solomonoff induction and knowledge-seeking",

abstract = "Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff{\textquoteright}s prior M in the arithmetical hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.",

keywords = "AIXI, Arithmetical hierarchy, Asymptotic optimality, BayesExp, Complexity, Computability, Exploration, General reinforcement learning, Knowledge-seeking agents, Solomonoff induction, Universal turing machine",

author = "Jan Leike and Marcus Hutter",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 26th International Conference on Algorithmic Learning Theory, ALT 2015 ; Conference date: 04-10-2015 Through 06-10-2015",

year = "2015",

doi = "10.1007/978-3-319-24486-0_24",

language = "English",

isbn = "9783319244853",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "364--378",

editor = "Claudio Gentile and Sandra Zilles and Kamalika Chaudhuri",

booktitle = "Algorithmic Learning Theory - 26th International Conference, ALT 2015",

address = "Germany",

}

Leike, J & Hutter, M 2015, On the computability of solomonoff induction and knowledge-seeking. in C Gentile, S Zilles & K Chaudhuri (eds), Algorithmic Learning Theory - 26th International Conference, ALT 2015. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9355, Springer Verlag, pp. 364-378, 26th International Conference on Algorithmic Learning Theory, ALT 2015, Banff, Canada, 4/10/15. https://doi.org/10.1007/978-3-319-24486-0_24

On the computability of solomonoff induction and knowledge-seeking. / Leike, Jan; Hutter, Marcus.
Algorithmic Learning Theory - 26th International Conference, ALT 2015. ed. / Claudio Gentile; Sandra Zilles; Kamalika Chaudhuri. Springer Verlag, 2015. p. 364-378 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9355).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the computability of solomonoff induction and knowledge-seeking

AU - Leike, Jan

AU - Hutter, Marcus

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff’s prior M in the arithmetical hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.

AB - Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff’s prior M in the arithmetical hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.

KW - AIXI

KW - Arithmetical hierarchy

KW - Asymptotic optimality

KW - BayesExp

KW - Complexity

KW - Computability

KW - Exploration

KW - General reinforcement learning

KW - Knowledge-seeking agents

KW - Solomonoff induction

KW - Universal turing machine

UR - http://www.scopus.com/inward/record.url?scp=84945896812&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-24486-0_24

DO - 10.1007/978-3-319-24486-0_24

M3 - Conference contribution

SN - 9783319244853

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 364

EP - 378

BT - Algorithmic Learning Theory - 26th International Conference, ALT 2015

A2 - Gentile, Claudio

A2 - Zilles, Sandra

A2 - Chaudhuri, Kamalika

PB - Springer Verlag

T2 - 26th International Conference on Algorithmic Learning Theory, ALT 2015

Y2 - 4 October 2015 through 6 October 2015

ER -

Leike J, Hutter M. On the computability of solomonoff induction and knowledge-seeking. In Gentile C, Zilles S, Chaudhuri K, editors, Algorithmic Learning Theory - 26th International Conference, ALT 2015. Springer Verlag. 2015. p. 364-378. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-24486-0_24

On the computability of solomonoff induction and knowledge-seeking

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this