# Learning Generalized Policy Automata for Relational Stochastic Shortest Path Problems

arXiv: https://arxiv.org/abs/2204.04301 · HTML: https://mlsanity.com/paper/2204.04301/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 42 references that are in the map.
- First posted on arXiv 8 Apr 2022.

## Builds on (most cited first, 8 of 8)

- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Temporal Difference Models: Model-Free Deep RL for Model-Based Control](https://mlsanity.com/paper/1802.09081/) (2018)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [Learning Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [Action Schema Networks: Generalised Policies with Deep Learning](https://mlsanity.com/paper/1709.04271/) (2017)
- [Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning](https://mlsanity.com/paper/2007.06702/) (2020)
- [Anytime Integrated Task and Motion Policies for Stochastic Environments](https://mlsanity.com/paper/1904.13006/) (2019)
- [Hierarchical Finite State Controllers for Generalized Planning](https://mlsanity.com/paper/1911.02887/) (2019)

## Built on by (most cited first, 2 of 2)

- [General Policies, Subgoal Structure, and Planning Width](https://mlsanity.com/paper/2311.05490/) (2023)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)

## Abstract (arXiv)

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 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.