@article{Juba_Stern_2022, title={Learning Probably Approximately Complete and Safe Action Models for Stochastic Worlds}, volume={36}, url={https://ojs.aaai.org/index.php/AAAI/article/view/21215}, DOI={10.1609/aaai.v36i9.21215}, abstractNote={We consider the problem of learning action models for planning in unknown stochastic environments that can be defined using the Probabilistic Planning Domain Description Language (PPDDL). As input, we are given a set of previously executed trajectories, and the main challenge is to learn an action model that has a similar goal achievement probability to the policies used to create these trajectories. To this end, we introduce a variant of PPDDL in which there is uncertainty about the transition probabilities, specified by an interval for each factor that contains the respective true transition probabilities. Then, we present SAM+, an algorithm that learns such an imprecise-PPDDL environment model. SAM+ has a polynomial time and sample complexity, and guarantees that with high probability, the true environment is indeed captured by the defined intervals. We prove that the action model SAM+ outputs has a goal achievement probability that is almost as good or better than that of the policies used to produced the training trajectories. Then, we show how to produce a PPDDL model based on this imprecise-PPDDL model that has similar properties.}, number={9}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Juba, Brendan and Stern, Roni}, year={2022}, month={Jun.}, pages={9795-9804} }