Bias-Optimal Incremental Problem Solving

Jürgen SchmidhuberNeurIPS 2002 · OpenReview

Introduction

In theoretical computer science, "Universal Search" algorithms (such as Levin Search) are mathematically perfect: they are guaranteed to find a solution to any verifiable problem as quickly as the best possible algorithm, up to a constant factor. However, in practice, that "constant factor" is often so massive that these optimal algorithms are rendered useless. Furthermore, traditional universal searchers suffer from "amnesia"—they start every new task entirely from scratch, failing to recognize that the solution to a complex problem often shares underlying structure with the solution to a simpler one.

To address this, researchers developed the Optimal Ordered Problem Solver (OOPS). OOPS is a framework for "bias-optimal" incremental learning that solves a sequence of tasks by searching for programs rather than states. By "freezing" successful code from simpler tasks and allowing new programs to reuse or modify the probability of these building blocks, OOPS drastically reduces the constant-time penalties of universal search. It effectively learns how to solve complex problems by first mastering simpler, foundational patterns.

The OOPS Framework

At its core, OOPS is designed to be optimal not just for a single task, but for incremental problem solving. It uses past experience to shift its search "bias" toward more promising solutions. Key components of the system include:

  • Bias-Optimality: OOPS ensures that no candidate program receives more runtime than its probability (its "bias") multiplied by the total search time.
  • Method Try: This is a recursive, multitasking search algorithm that performs a depth-first search in program space. It efficiently manages state changes and backtracking, ensuring that the overhead of managing multiple tasks does not exceed the cost of the search itself.
  • Incremental Learning & "Freezing": Once a task is solved, the successful program is "frozen" in non-modifiable memory. Future searches can then call these frozen programs as subroutines.
  • A Custom Meta-Language: The system uses a stack-based, universal programming language inspired by FORTH. It features 68 initial instructions for basic arithmetic and stack manipulation, alongside crucial meta-instructions like boostq. This allows a program prefix to temporarily rewrite the probability distribution of the instructions that follow it, effectively directing the search.

Experimental Setup: A Curriculum of Algorithms

Rather than using traditional static datasets, OOPS was evaluated on a sequence of algorithmic challenges designed to build upon one another:

  1. Context-Free Symmetry: The system was first tasked with a problem involving the language $\{1^n 2^n\}$ (placing $n$ ones followed by $n$ twos on a stack). This served to "teach" the system the fundamental concept of recursion.
  2. Towers of Hanoi: The classic puzzle of moving $n$ disks between pegs. The ultimate goal was for the system to discover a universal solver capable of handling any $n$.

Key Insights and Results

The Power of Meta-Searching and Bias Shifts

OOPS goes beyond simply searching for a solution; it allows programs to perform "metasearching." A program prefix can use the boostq instruction to increase the probability of using components from previously solved problems. By solving the symmetry problem first, the system discovered a reusable recursive template. When it moved to the Towers of Hanoi, it did not have to reinvent recursion—it merely had to find the specific disk-moving logic to plug into that existing template.

Program Space vs. State Space

Traditional AI planners typically fail on the Towers of Hanoi for $n > 15$ because the number of possible states explodes exponentially. OOPS succeeds because it searches in program space. The actual code for a recursive Hanoi solver is short and elegant, remaining the exact same size regardless of how large $n$ gets.

Quantifiable Speedup

The advantages of this incremental approach were starkly quantifiable in the results:

  • Massive Acceleration: Without the initial "symmetry" training, OOPS could not solve the Towers of Hanoi for more than 3 disks within a week of computation. With the training, it found a universal Hanoi solver in about 3 days.
  • Measurable Bias Shift: The symmetry task provided a "bias shift" that accelerated the search for the Hanoi solver by a factor of roughly 1,000.
  • Universal Generalization: Once the universal solver was found, OOPS solved all remaining Hanoi tasks (up to $n=30$) in just one additional day by simply reusing the optimal program.
  • Probability Jump: The final Hanoi solution had a probability of $0.325 \times 10^{-10}$ given the previously frozen code. If searching entirely from scratch, that probability would have been a negligible $4 \times 10^{-14}$.

Limitations and Future Work

While OOPS represents a major step forward in universal search, it has limitations. The system's performance is heavily dependent on its initial bias—the starting set of 68 instructions. If these primitives are poorly suited to a specific domain, the search will remain prohibitively slow. Furthermore, even with optimal allocation, searching program space is computationally intense; these experiments required days of computation on a 1.5 GHz machine for relatively simple symbolic tasks.

Future directions for this research include equipping OOPS with neural network primitives. Applying this framework to domains like robotics could allow for the incremental learning of complex motor skills, mirroring the incremental learning of algorithms demonstrated here.

Summary updated

Abstract

Given is a problem sequence and a probability distribution (the bias) on programs computing solution candidates. We present an optimally fast way of incrementally solving each task in the sequence. Bias shifts are computed by program prefixes that modify the distribution on their suffixes by reusing successful code for previous tasks (stored in non-modifiable memory). No tested program gets more runtime than its probability times the total search time. In illustrative experiments, ours becomes the first general system to learn a universal solver for arbitrary n disk Towers of Hanoi tasks (minimal solution size 2n - 1). It demonstrates the advantages of incremental learning by profiting from previously solved, simpler tasks involving samples of a simple context free language.
BibTeX
@inproceedings{schmidhuber2002bias,
  author = {Jürgen Schmidhuber},
  title = {{Bias-Optimal Incremental Problem Solving}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2002},
  url = {https://openreview.net/forum?id=H1Nl58bOWS},
}
Figure