Efficient, Safe, and Probably Approximately Complete Learning of Action
  Models
  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.
