Leike, JanHutter, Marcus2016-06-14October 4-9783319244853http://hdl.handle.net/1885/103397Solomonoff 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.17/12 Fixed and entered. 15Dec15 Problem uploading documentAuthor/s retain copyright201510.1007/978-3-319-24486-0_242016-06-14