On the Computability of Solomonoff Induction and Knowledge-Seeking

ALT 2015 pp. 364-378

doi:10.1007/978-3-319-24486-0_24 /alt/2015/leike2015alt-computability/

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.

PDF ALT Semantic Scholar

Cite

Text

Leike and Hutter. "On the Computability of Solomonoff Induction and Knowledge-Seeking." International Conference on Algorithmic Learning Theory, 2015. doi:10.1007/978-3-319-24486-0_24

Markdown

[Leike and Hutter. "On the Computability of Solomonoff Induction and Knowledge-Seeking." International Conference on Algorithmic Learning Theory, 2015.](https://mlanthology.org/alt/2015/leike2015alt-computability/) doi:10.1007/978-3-319-24486-0_24

BibTeX

@inproceedings{leike2015alt-computability,
  title     = {{On the Computability of Solomonoff Induction and Knowledge-Seeking}},
  author    = {Leike, Jan and Hutter, Marcus},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2015},
  pages     = {364-378},
  doi       = {10.1007/978-3-319-24486-0_24},
  url       = {https://mlanthology.org/alt/2015/leike2015alt-computability/}
}