On the Computability of Solomonoff Induction and Knowledge-Seeking
This work addresses foundational issues in AI and machine learning by clarifying the computability limits of theoretical learning models, which is incremental but important for understanding algorithmic learning bounds.
The paper quantified the incomputability of Solomonoff induction by analyzing its position in the arithmetical hierarchy and derived computability bounds for knowledge-seeking agents, resulting in a limit-computable weakly asymptotically optimal reinforcement learning agent.
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.