On the computability of Solomonoff induction and knowledge-seeking

DOI10.1007/978-3-319-24486-0_24zbMATH Open1388.68252arXiv1507.04124OpenAlexW905556285WikidataQ58012195 ScholiaQ58012195MaRDI QIDQ2835643FDOQ2835643

Authors: Jan Leike, Marcus Hutter 

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1507.04124

Recommendations

• On the computability of Solomonoff induction and AIXI
• Principles of Solomonoff Induction and AIXI
• On the existence and convergence of computable universal priors
• Making Solomonoff induction effective. Or: you can learn what you can bound
• Is There an Elegant Universal Theory of Prediction?

zbMATH Keywords

complexityasymptotic optimalityexplorationcomputabilityarithmetical hierarchyAIXISolomonoff inductionuniversal Turing machinegeneral reinforcement learningknowledge-seeking agentsBayesExp

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Merging of Opinions with Increasing Information
• A formal theory of inductive inference. Part I
• Computability and Randomness
• An introduction to Kolmogorov complexity and its applications
• On the relation between descriptional complexity and algorithmic probability
• Complexity-based induction systems: Comparisons and convergence theorems
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.
• Asymptotic non-learnability of universal agents with computable horizon functions
• Universal knowledge-seeking agents
• Asymptotically optimal agents
• Universal knowledge-seeking agents
• Optimality issues of universal greedy agents with static priors
• A philosophical treatise of universal induction
• (Non-)Equivalence of Universal Priors
• New error bounds for Solomonoff prediction
• On the computability of Solomonoff induction and AIXI
• On the computability of Solomonoff induction and knowledge-seeking
• Universal knowledge-seeking agents for stochastic environments
• Universal prediction of selected bits

Cited In (7)

• Uncomputability: The problem of induction internalized
• On the computability of Solomonoff induction and AIXI
• Universal knowledge-seeking agents for stochastic environments
• Making Solomonoff induction effective. Or: you can learn what you can bound
• On the computability of Solomonoff induction and knowledge-seeking
• Absolutely no free lunches!
• Putnam's diagonal argument and the impossibility of a universal learning machine

This page was built for publication: On the computability of Solomonoff induction and knowledge-seeking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835643)