Learning ranking functions for efficient search

Graduation date: 2011This dissertation explores algorithms for learning ranking functions to efficiently solve search problems, with application to automated planning. Specifically, we consider the frameworks of beam search, greedy search, and randomized search, which all aim to maintain tractability at the cost of not guaranteeing completeness nor optimality. Our learning objective for each of these frameworks is to induce a linear ranking function for guiding the search that performs nearly as well as unconstrained search, hence gaining computational efficiency without seriously sacrificing optimality.\ud We first investigate the problem of learning ranking functions to guide beam search, with a focus on learning feature weights given a set of features. We present a theoretical analysis of the problem's computational complexity that identifies the core efficient and hard subclasses. In addition we study online learning algorithms for the problem and analyze their convergence properties. The algorithms are applied to automated planning, showing that our approach is often able to outperform an existing state-of-the-art planning heuristic as well as a recent approach to learning such heuristics.\ud Next, we study the problem of automatically learning both features and weights to guide greedy search. We present a new iterative learning algorithm based on RankBoost, an efficient boosting algorithm for ranking and demonstrate strong empirical results in the domain of automated planning.\ud Finally, we consider the problem of learning randomized policies for guiding randomized greedy search with restarts. We pose this problem in the framework of reinforcement learning and investigate policy-gradient algorithms for learning both features and weights. The results show that in a number of domains this approach is significantly better than those obtained for deterministic greedy search