Previous Work: Best General Methods Need Proof Searchers!

Neither Levin's universal search [22] nor its incremental extension, the Optimal Ordered Problem Solver [38,40], nor Solomonoff's recent ideas [50] are `universal enough' for such general setups, and our earlier self-modifying online learning systems [29,32,46,45,47] are not necessarily optimal. Hutter's recent AIXI model [15] does execute optimal actions in very general environments evolving according to arbitrary, unknown, yet computable probabilistic laws, but only under the unrealistic assumption of unlimited computation time. AIXI's asymptotically optimal, space/time-bounded cousin AIXI(t,l) [15] may be the system conceptually closest to the one pesented here. In discrete cycle $k=1,2,3, ldots$ of AIXI(t,l)'s lifetime, action $y(k)$ results in perception $x(k)$ and reward $r(k)$, where all quantities may depend on the complete history. Using a universal computer such as a Turing machine [52], AIXI(t,l) needs an initial offline setup phase (prior to interaction with the environment) to examine all proofs of length at most $l_P$, filtering out those that identify programs (of maximal size $l$ and maximal runtime $t$ per cycle) which not only could interact with the environment but which for all possible interaction histories also correctly predict a lower bound of their own expected reward. In cycle $k$, AIXI(t,l) then runs all programs identified in the setup phase (at most $2^l$), finds the one with highest self-rating, and executes its corresponding action. The problem-independent setup time (where almost all of the work is done) is $O(l_P 2^{l_P})$, and the online computation time per cycle is $O(t 2^l)$.

AIXI(t,l) is related to Hutter's `fastest' algorithm for all well-defined problems (HSEARCH [16]) which also uses a general proof searcher, and also is asymptotically optimal in a certain sense. Assume discrete input/output domains $X/Y$, a formal problem specification $f: X rightarrow Y$ (say, a functional description of how integers are decomposed into their prime factors), and a particular $x in X$ (say, an integer to be factorized). HSEARCH orders all proofs of an appropriate axiomatic system by size to find programs $q$ that for all $z in X$ provably compute $f(z)$ within time bound $t_q(z)$. Simultaneously it spends most of its time on executing the $q$ with the best currently proven time bound $t_q(x)$. It turns out that HSEARCH is as fast as the fastest algorithm that provably computes $f(z)$ for all $z in X$, save for a constant factor smaller than $1 + epsilon$ (arbitrary $epsilon > 0$) and an $f$-specific but $x$-independent additive constant [16]. That is, HSEARCH and AIXI(t,l) boast an optimal order of complexity. This somewhat limited notion of optimality, however, can be misleading despite its wide use in theoretical computer science, as it hides the possibly huge but problem-independent constants which could make AIXI(t,l) and HSEARCH practically infeasible.

Back to Goedel machine home page