  Several goal-oriented problems in the real-world can be naturally expressed
as Stochastic Shortest Path Problems (SSPs). However, the computational
complexity of solving SSPs makes finding solutions to even moderately sized
problems intractable. Currently, existing state-of-the-art planners and
heuristics often fail to exploit knowledge learned from solving other
instances. This paper presents an approach for learning \emph{Generalized
Policy Automata} (GPA): non-deterministic partial policies that can be used to
catalyze the solution process. GPAs are learned using relational, feature-based
abstractions, which makes them applicable on broad classes of related problems
with different object names and quantities. Theoretical analysis of this
approach shows that it guarantees completeness and hierarchical optimality.
Empirical analysis shows that this approach effectively learns broadly
applicable policy knowledge in a few-shot fashion and significantly outperforms
state-of-the-art SSP solvers on test problems whose object counts are far
greater than those used during training.
