Abstract
Speedup learning seeks to improve the efficiency of search-based problem solvers. In this paper, we propose a new theoretical model of speedup learning which captures systems that improve problem solving performance by solving a user-given set of problems. We also use this model to motivate the notion of "batch problem solving," and argue that it is more congenial to learning than sequential problem solving. Our theoretical results are applicable to all serially decomposable domains. We empirically validate our results in the domain of Eight Puzzle.
Introduction
Search-based problem solvers, such as those designed for the Rubik’s Cube or the Eight Puzzle, are often computationally expensive due to the massive state spaces they must explore. Speedup learning is the branch of machine learning dedicated to reducing this search time by making solvers more efficient over time.
Historically, most speedup learning models were supervised, requiring a teacher to provide both the problems and their optimal solutions. Furthermore, these systems typically learned sequentially, solving one problem entirely before moving to the next. This approach is prone to inefficiency; if a system makes an incorrect assumption about the domain's structure—such as the order in which subgoals should be solved—it may spend significant time backtracking through a single difficult problem before identifying the error. This paper introduces a theoretical framework for unsupervised speedup learning that utilizes "batch problem solving" to overcome these limitations.
Theoretical Framework and Methods
The proposed model is based on the Probably Approximately Correct (PAC) learning framework. It relies on three key components:
- Unsupervised Practice: The learner is provided with a "domain theory" (the rules of the environment) and a set of unsolved problems. It utilizes a complete but inefficient solver, such as Iterative Deepening Depth-First Search, to generate its own solutions for learning.
- Serial Decomposability: Building on the work of Richard Korf, the model assumes the domain can be broken into subgoals that can be solved sequentially without disturbing previously satisfied subgoals.
- The Batch-Learn Algorithm: Instead of sequential processing, this algorithm evaluates a "batch" of problems simultaneously. This allows the system to use multiple examples as a filter for domain hypotheses. If a macro-operator learned for one problem fails to work for the same feature in another problem within the batch, the algorithm immediately identifies the current feature ordering as incorrect and discards it.
Empirical Validation: The Eight Puzzle
The primary domain used for empirical evaluation is the Eight Puzzle, a 3x3 sliding tile puzzle. This domain is a classic AI benchmark because it possesses a high branching factor and is serially decomposable, making it a rigorous test for speedup learning algorithms.
In the Eight Puzzle, the learner must discover a "macro-table"—a set of move sequences (macros) that solve specific tiles in a specific order. Unlike previous approaches that assumed the order of subgoals was pre-defined, the Batch-Learn algorithm learns the optimal ordering of features alongside the macros themselves.
Key Results
The paper offers both theoretical and empirical evidence for the efficacy of batch learning:
- PAC-Learning Guarantee: The author proves that for serially decomposable domains, the Batch-Learn algorithm is a true PAC-learning algorithm. It is guaranteed to produce an approximately correct solver with high probability using a polynomial number of examples.
- Sample Efficiency: While theoretical worst-case estimates suggested the Eight Puzzle would require approximately 780 examples to learn, the batch algorithm successfully learned the full macro-table and correct feature ordering using only 23 examples.
- Complexity Reduction: Once the macro-table is acquired, problem-solving becomes extremely fast. The learning process represents a jump in average asymptotic complexity, moving from an exponential-time solver to a polynomial-time one.
Conclusion and Future Work
Prasad Tadepalli’s research demonstrates that unsupervised practice on a batch of problems can significantly accelerate the acquisition of domain knowledge. By using multiple problems to prune the hypothesis space, the Batch-Learn algorithm avoids the pitfalls of sequential backtracking.
However, the model currently faces limitations regarding representational constraints. It assumes states are vectors of discrete features, which may not easily translate to relational domains like the "Blocks World." Additionally, the algorithm is specifically biased toward serially decomposable domains. Future research may focus on tightening the theoretical bounds of sample complexity and extending these methods to more complex, non-linear domains.
Summary updated