# Efficient, Safe, and Probably Approximately Complete Learning of Action Models

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2017.

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

- [Safe Learning of Lifted Action Models](https://mlsanity.com/paper/2107.04169/) (2021)
- [Learning Interpretable Temporal Properties from Positive Examples Only](https://mlsanity.com/paper/2209.02650/) (2022)
- [Discovering User-Interpretable Capabilities of Black-Box Planning Agents](https://mlsanity.com/paper/2107.13668/) (2021)
- [Differential Assessment of Black-Box AI Agents](https://mlsanity.com/paper/2203.13236/) (2022)
- [Planning Domain Model Acquisition from State Traces without Action Parameters](https://mlsanity.com/paper/2402.10726/) (2024)
- [Neuro-Symbolic Imitation Learning: Discovering Symbolic Abstractions for Skill Learning](https://mlsanity.com/paper/2503.21406/) (2025)
- [A Domain-Independent Agent Architecture for Adaptive Operation in Evolving Open Worlds](https://mlsanity.com/paper/2306.06272/) (2023)
- [Learning First-Order Symbolic Planning Representations That Are Grounded](https://mlsanity.com/paper/2204.11902/) (2022)
- [Safe Learning of PDDL Domains with Conditional Effects -- Extended Version](https://mlsanity.com/paper/2403.15251/) (2024)
- [Foundations of a Developmental Design Paradigm for Integrated Continual Learning, Deliberative Behavior, and Comprehensibility](https://mlsanity.com/paper/2502.13935/) (2025)
- [Action Model Learning with Guarantees](https://mlsanity.com/paper/2404.09631/) (2024)
- [Integrating Reinforcement Learning, Action Model Learning, and Numeric Planning for Tackling Complex Tasks](https://mlsanity.com/paper/2502.13006/) (2025)
- [On the Parallels Between Evolutionary Theory and the State of AI](https://mlsanity.com/paper/2505.23774/) (2025)
- [Is the Rush to Machine Learning Jeopardizing Safety? Results of a Survey](https://mlsanity.com/paper/2111.14324/) (2021)
- [Autonomous Assessment of Generalizability of AI Agent Capabilities](https://mlsanity.com/paper/2512.16733/) (2025)
- [RAMP: Hybrid DRL for Online Learning of Numeric Action Models](https://mlsanity.com/paper/2604.08685/) (2026)

## Abstract (arXiv)

In this paper we explore the theoretical boundaries of planning in a setting where no model of the agent's actions is given. Instead of an action model, a set of successfully executed plans are given and the task is to generate a plan that is safe, i.e., guaranteed to achieve the goal without failing. To this end, we show how to learn a conservative model of the world in which actions are guaranteed to be applicable. This conservative model is then given to an off-the-shelf classical planner, resulting in a plan that is guaranteed to achieve the goal. However, this reduction from a model-free planning to a model-based planning is not complete: in some cases a plan will not be found even when such exists. We analyze the relation between the number of observed plans and the likelihood that our conservative approach will indeed fail to solve a solvable problem. Our analysis show that the number of trajectories needed scales gracefully.