SpringerLink
Log in

On the Computability of Solomonoff Induction and Knowledge-Seeking

  • Conference paper
  • First Online:
Algorithmic Learning Theory (ALT 2015)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 9355))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Blackwell, D., Dubins, L.: Merging of opinions with increasing information. The Annals of Mathematical Statistics, 882–886 (1962)

    Google Scholar 

  2. Gács, P.: On the relation between descriptional complexity and algorithmic probability. Theoretical Computer Science 22(1–2), 71–93 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  3. Hutter, M.: A theory of universal artificial intelligence based on algorithmic complexity. Technical Report cs.AI/0004001 (2000). http://arxiv.org/abs/cs.AI/0004001

  4. Hutter, M.: New error bounds for Solomonoff prediction. Journal of Computer and System Sciences 62(4), 653–667 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  5. Hutter, M.: Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. Springer (2005)

    Google Scholar 

  6. Lattimore, T.: Theory of General Reinforcement Learning. PhD thesis, Australian National University (2013)

    Google Scholar 

  7. Lattimore, T., Hutter, M.: Asymptotically optimal agents. In: Kivinen, J., Szepesvári, C., Ukkonen, E., Zeugmann, T. (eds.) ALT 2011. LNCS, vol. 6925, pp. 368–382. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  8. Lattimore, T., Hutter, M., Gavane, V.: Universal prediction of selected bits. In: Kivinen, J., Szepesvári, C., Ukkonen, E., Zeugmann, T. (eds.) ALT 2011. LNCS, vol. 6925, pp. 262–276. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  9. Leike, J., Hutter, M.: Bad universal priors and notions of optimality. In: Conference on Learning Theory (2015)

    Google Scholar 

  10. Leike, J., Hutter, M.: On the computability of AIXI. In: Uncertainty in Artificial Intelligence (2015)

    Google Scholar 

  11. Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science, 3rd edn. Springer (2008)

    Google Scholar 

  12. Nies, A.: Computability and Randomness. Oxford University Press (2009)

    Google Scholar 

  13. Orseau, L.: Optimality issues of universal greedy agents with static priors. In: Hutter, M., Stephan, F., Vovk, V., Zeugmann, T. (eds.) Algorithmic Learning Theory. LNCS, vol. 6331, pp. 345–359. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  14. Orseau, L.: Universal knowledge-seeking agents. In: Kivinen, J., Szepesvári, C., Ukkonen, E., Zeugmann, T. (eds.) ALT 2011. LNCS, vol. 6925, pp. 353–367. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  15. Orseau, L.: Asymptotic non-learnability of universal agents with computable horizon functions. Theoretical Computer Science 473, 149–156 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  16. Orseau, L.: Universal knowledge-seeking agents. Theoretical Computer Science 519, 127–139 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  17. Orseau, L., Lattimore, T., Hutter, M.: Universal knowledge-seeking agents for stochastic environments. In: Jain, S., Munos, R., Stephan, F., Zeugmann, T. (eds.) ALT 2013. LNCS, vol. 8139, pp. 158–172. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  18. Rathmanner, S., Hutter, M.: A philosophical treatise of universal induction. Entropy 13(6), 1076–1136 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  19. Solomonoff, R.: A formal theory of inductive inference. Parts 1 and 2. Information and Control 7(1), 1–22 and 224–254 (1964)

    Google Scholar 

  20. Solomonoff, R.: Complexity-based induction systems: Comparisons and convergence theorems. IEEE Transactions on Information Theory 24(4), 422–432 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  21. Wood, I., Sunehag, P., Hutter, M.: (Non-)equivalence of universal priors. In: Dowe, D.L. (ed.) Solomonoff Festschrift. LNCS, vol. 7070, pp. 417–425. Springer, Heidelberg (2013)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Australian National University, Canberra, Australia

    Jan Leike & Marcus Hutter

Authors
  1. Jan Leike
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcus Hutter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jan Leike .

Editor information

Editors and Affiliations

  1. University of California, La Jolla, California, USA

    Kamalika Chaudhuri

  2. UNIV DEL INSUBRIA, 21100 VARESE, Italy

    CLAUDIO GENTILE

  3. REGINA, Saskatchewan, Canada

    Sandra Zilles

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Leike, J., Hutter, M. (2015). On the Computability of Solomonoff Induction and Knowledge-Seeking. In: Chaudhuri, K., GENTILE, C., Zilles, S. (eds) Algorithmic Learning Theory. ALT 2015. Lecture Notes in Computer Science(), vol 9355. Springer, Cham. https://doi.org/10.1007/978-3-319-24486-0_24

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-24486-0_24

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-24485-3

  • Online ISBN: 978-3-319-24486-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation