Analysis of the Results: Benefits of Metasearching

The final 10-token Hanoi solution demonstrates the benefits of incremental learning: it greatly profits from rewriting the search procedure with the help of information conveyed by the earlier recursive solution to the $1^n2^n$-problem. How?

The prefix (c3 dec boostq) (probability 0.003) prepares the foundations: Instruction c3 pushes 3; dec decrements this; boostq takes the result 2 as an argument (interpreted as an address) and thus boosts the probabilities of all components of the 2nd frozen program, which happens to be the previously found universal $1^n2^n$-solver. This causes an online bias shift on the space of possible suffixes: it greatly increases the probability that defnp, calltp, endnp, will appear in the remainder of the online-generated program. These instructions in turn are helpful for building (on the data stack ds) the double-recursive procedure generated by the suffix (defnp c4 calltp c3 c5 calltp endnp), which essentially constructs (on data stack $ds$) a 4-argument procedure that returns nothing if its input argument is 0, otherwise decrements the top input argument, calls the instruction xAD whose code is 4, then calls itself on a copy of the top 4 arguments, then calls mvdsk whose code is 5, then calls xSA whose code is 3, then calls itself on another copy of the top 4 arguments, then makes yet another (unnecessary) argument copy, then returns (compare the standard Hanoi solution).

The total probability of the final solution, given the previous codes, is calculated as follows: since $n_Q=73$, given the boosts of c3, c4, c5, by2, dec, boostq, we have probability $( \frac{1+73}{7 * 73})^3$ for the prefix (c3 dec boostq); since this prefix further boosts defnp, c1, calltp, c2, endnp, we have probability $( \frac{1+73}{12 * 73})^7$ for the suffix (defnp c4 calltp c3 c5 calltp endnp). That is, the probability of the complete 10-symbol code is $9.3 * 10^{-11}$. On the other hand, the probability of the essential Hanoi-specific suffix (defnp c4 calltp c3 c5 calltp endnp), given just the initial boosts, is only $( \frac{1+73}{7 * 73})^3 ( \frac{1}{7 * 73})^4 = 4.5 * 10^{-14}$, which explains why it was not quickly found without the help of the solution to an easier problem set. (Without any initial boosts its probability would actually have been similar: $(\frac{1}{73})^7=9 * 10^{-14}$.) This would correspond to a search time of several years, as opposed to a few days.

So in this particular setup the simple recursion for the $1^n2^n$-problem indeed provided useful incremental training for the more complex Hanoi recursion, speeding up the search by a factor of 1000 or so.

On the other hand, the search for the universal solver for all $1^n2^n$-problems (first found with instance $n=6$) did not at all profit from solutions to earlier solved tasks (although instances $n>6$ did profit).

Note that the time spent by the final 10-token Hanoi solver on increasing the probabilities of certain instructions and on constructing executable code on the data stack (less than 50 time steps) quickly becomes negligible as the Hanoi instance size grows. In this particular application, most time is spent on executing the code, not on constructing it.

Once the universal Hanoi solver was discovered, why did the solution of the remaining Hanoi tasks substantially increase the total time (by roughly 25 %)? Because the sheer runtime of the discovered, frozen, near-optimal program on the remaining tasks was already comparable to the previously consumed search time for this program, due to the very nature of the Hanoi task: Recall that a solution for $n=30$ takes more than a billion mvdsk operations, and that for each mvdsk several other instructions need to be executed as well. Note that experiments with traditional reinforcement learners [24] rarely involve problems whose solution sizes exceed a few thousand steps.

Note also that we could continue to solve Hanoi tasks up to $n>40$. The execution time required to solve such instances with an optimal solver greatly exceeds the search time required for finding the solver itself. There it does not matter much whether OOPS already starts with a prewired Hanoi solver, or first has to discover one, since the initial search time for the solver becomes negligible anyway.

Of course, different initial bias can yield dramatically different results. For example, using hindsight we could set to zero the probabilities of all 73 initial instructions (most are unnecessary for the 30 Hanoi tasks) except for the 7 instructions used by the Hanoi-solving suffix, then make those 7 instructions equally likely, and thus obtain a comparatively high Hanoi solver probability of $(\frac{1}{7})^7 = 1.2 * 10^{-6}$. This would allow for finding the solution to the 10 disk Hanoi problem within less than an hour, without having to learn easier tasks first (at the expense of obtaining a nonuniversal initial programming language). The point of this experimental section, however, is not to find the most reasonable initial bias for particular problems, but to illustrate the basic functionality of the first general, near-bias-optimal, incremental learner.

Back to OOPS main page