On the computability of Solomonoff induction and knowledge-seeking

DOI10.1007/978-3-319-24486-0_24MaRDI QIDQ2835643zbMATHOpenAlexWikidataFDO

Authors Jan Leike, Marcus Hutter

Publication date 30 November 2016

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

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

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)

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.

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?

Cites work

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

Cited in

(7)

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

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)