  Recent machine-learning approaches to deterministic search and
domain-independent planning employ policy learning to speed up search.
Unfortunately, when attempting to solve a search problem by successively
applying a policy, no guarantees can be given on solution quality. The problem
of how to effectively use a learned policy within a bounded-suboptimal search
algorithm remains largely as an open question. In this paper, we propose
various ways in which such policies can be integrated into Focal Search,
assuming that the policy is a neural network classifier. Furthermore, we
provide mathematical foundations for some of the resulting algorithms. To
evaluate the resulting algorithms over a number of policies with varying
accuracy, we use synthetic policies which can be generated for a target
accuracy for problems where the search space can be held in memory. We evaluate
our focal search variants over three benchmark domains using our synthetic
approach, and on the 15-puzzle using a neural network learned using 1.5 million
examples. We observe that \emph{Discrepancy Focal Search}, which we show
expands the node which maximizes an approximation of the probability that its
corresponding path is a prefix of an optimal path, obtains, in general, the
best results in terms of runtime and solution quality.
