An Asymptotic Analysis of Speedup Learning

Abstract

Based on a simple asymptotic analysis, this paper presents two observations regarding the state-of-the-art in speedup learning. First, reducing the match cost of control rules to a polynomial or even linear function of rule length does not guarantee polynomial-time problem solving or any speedup for that matter. Hence, the elimination expensive control rules is not guaranteed to solve the utility problem. Second, augmenting a problem solver's operator set with macro-operators can increase the branching factor of the problem solver's search. The overhead of this increase, even when it occurs only in a vanishingly small fraction of the problems encountered, dominates any search reduction on the remaining problems. Thus, acquiring macro-operators is guaranteed to slow down a problem solver, in the limit, unless the macros modify the topology of the search space so that sufficient search-depth reduction accompanies branching-factor increase, everywhere.