PALO: A probabilistic hill-climbing algorithm

Many learning systems search through a space of possible performance elements, seeking an element whose expected utility, over the distribution of problems, is high. As the task of finding the globally optimal element is often intractable, many practical learning systems instead hill-climb to a local optimum. Unfortunately, even this is problematic as the learner typically does not know the underlying distribution of problems, which it needs to determine an element's expected utility. This paper addresses the task of approximating this hill-climbing search when the utility function can only be estimated by sampling. We present a general algorithm, PALO, that returns an element that is, with provably high probability, essentially a local optimum. We then demonstrate the generality of this algorithm by presenting three distinct applications that respectively find an element whose efficiency, accuracy or completeness is nearly optimal. These results suggest approaches to solving the utility problem from explanation-based learning, the multiple extension problem from nonmonotonic reasoning and the tractability/completeness tradeoff problem from knowledge representation.