Action Model Learning with Guarantees

This paper studies the problem of action model learning with full observability. Following the learning by search paradigm by Mitchell, we develop a theory for action model learning based on version spaces that interprets the task as search for hypotheses that are consistent with the learning samples. Our theoretical findings are instantiated in an online algorithm that maintains a compact representation of all solutions of the problem. Among this range of solutions, we bring attention to action models approximating the actual transition system from below (sound models) and from above (complete models). We show how to manipulate the output of our learning algorithm to build deterministic and non-deterministic formulations of the sound and complete models and prove that, given enough examples, both formulations converge into the very same true model. Our experiments reveal their usefulness over a range of planning domains.