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

arXiv:1705.08961v1 [] 24 May 2017

Roni Stern
Ben Gurion University of the Negev
Be’er Sheva, Israel
roni.stern@gmail.com

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

1

Introduction

In classical planning problems, a model of the acting agent
and its relationship to the relevant world is given in a formal planning description language, e.g., the classical STRIPS
model [Fikes and Nilsson, 1971] or PDDL [McDermott et al.,
1998]. Planning algorithms (planners) use this model to generate a plan for achieving a given goal condition. Creating a
planning domain model, however, is acknowledged as a notoriously hard knowledge engineering task. This has motivated
much work on learning such knowledge.
One such well-studied approach is to learn a domain
model by observing the agent’s interactions with the environment. The problems that arise in such approaches, however, are frequently intractable [Kearns and Valiant, 1994;
Daniely and Shalev-Shwartz, 2016]. An alternative approach
that is commonly used in reinforcement learning is to skip the
model-learning phase and directly learn how to act by observing the agent’s past actions and observations, and by guiding
the agent towards performing exploratory actions [Kearns et
al., 2002, inter alia]. In most prior work, the agent may fail to
execute a planned action. When this occurs, the agent replans,
possibly refining an underlying domain or action model it has

Brendan Juba
Washington University in St. Louis
St. Louis, MO, 63130 USA
bjuba@wustl.edu

learned. Thus, the agent learns from both positive and negative examples.
In this work we address a different setting, in which such
execution failures must be avoided. This setting is relevant
when execution failures are very costly or when the agent
has limited computation capabilities, and thus does not have
the capability to re-plan after the plan it has tried to execute
has failed. Consider, for example, a team of nano-bots deployed inside a human body for medical target identification
and drug delivery [Cavalcanti et al., 2007]. Re-planning is
likely not possible in such nano-bots, and, of course, failing
to cure the disease is undesirable. Thus, the planning task we
focus on in this paper is how to find a plan that is safe, i.e.,
is guaranteed to achieve the goal, in a setting where a domain
model is not available. We call this problem the safe modelfree planning problem.
Since performing actions that might fail is not allowed, exploration actions cannot be performed. The only source of
information available is a set of trajectories of previously executed plans. First, we show how to learn a set of actions that
the agent can use from the given trajectories. For every such
action a, we bound the set of predicates that are a’s preconditions and effects. This bounded action model is then used
to construct a classical planning problem such that a solution
to it is a solution to our model-free problem. This approach
to solve the model-free planning problem is sound and can
be very efficient, since current classical planners are very efficient. However, it is not complete, as the planning problem
that uses the learned action model might not be solvable even
if the underlying model-free planning problem is. Nonetheless, we prove that under some assumptions, the probability
of this occurring decreases quasi-linearly with the number of
observed trajectories.
This positive result comes in contrast to the hardness of
other tasks related to model learning. For example, learning
to predict labels computed by finite-state machines [Kearns
and Valiant, 1994] or even DNF formulas [Daniely and
Shalev-Shwartz, 2016] is believed to be computationally intractable. Thus, we cannot hope to predict the values that
fluents will take merely on the basis of the fact that these can
be computed by a finite-state machine or a DNF. Similarly,
even the problems of finding memoryless policies [Littman,
1994] or finite-state policies [Meuleau et al., 1999] in simple
environments is computationally intractable. Finally, in the

standard interactive learning model, simple examples (that
would be captured by a STRIPS environment, for example)
are known to force a learner to explore an exponential number of paths in any reasonable measure of the environment’s
complexity [Kakade, 2003, Section 8.6].
The key difference between the model learning we propose
and these hardness results is that we limit our attention to
the learning of STRIPS domain models in a PAC (“Probably
Approximately Correct”) sense: we do not aim to learn an
accurate action model, only one that is sufficient for finding a
safe plan in most cases. We introduce and desribe this PAClike setting in Section 4.

2

Problem Definition

The setting we address is a a STRIPS planning domain, represented using the SAS+ formalism [Bäckström and Nebel,
1995]. A planning domain in SAS+ is defined by the tuple
D = hX , Oi, where
• X = {x1 , . . . , xn } is a set of state variables, each associated with a finite domain Dom(xi ).
• O is a set of actions, where each action a ∈ O is defined
by a tuple hpre(a), eff(a)i, where pre(a) and eff(a) are
assignments of values to state variables, i.e., a set of assignments of the form xi = v where v ∈ Dom(xi ). We
refer to O and its associated sets of preconditions and
effects as the action model of the domain.
A state is also a set of assignments of the form xi = v
such that every variable in X is assigned a single value from
its corresponding domain. As a shorthand notation, if a state
s contains an assignment xi = v we will write s(xi ) = v.
A planning problem in SAS+ is defined by the tuple Π =
hD, sI , sG i, where sI is the initial state and sG is a partial
assignment of some state variables that defines the goal. A
state s is a goal state if sG ⊆ s. For an action a and a state
s we denote by apply(s, a) the state resulting from applying
a on state s. A solution to an SAS+ planning problem is
a plan, which is a sequence of actions a1 , . . . , am such that
sG ⊆ apply(. . . apply(s, a1 ), a2 ) . . . am ).
The key challenge we address in this paper is how to solve a
SAS+ planning problem Π = hD, sI , sG i without having the
action model of D. Instead, a set of trajectories are assumed
to be given.
Definition 1 (Trajectory) A
trajectory
T
=
hs1 , a1 , s2 , a2 , . . . , an−1 , sn i is an alternating sequence
of states (s1 , . . . , sn ) and actions (a1 , . . . , an ) that starts and
ends with a state.
A trajectory represents a successful execution of a sequence
of actions by the agent. A set of trajectories may be obtained,
for example, by monitoring the acting agent when it is controlled manually by a human operator. The states in the given
trajectories are assumed to be fully observable.
Finally, we can define the safe model-free planning problem, which is the focus of this work.
Definition 2 (Safe model-free planning) Let
Π
=
hhX , Oi , sI , sG i be a planning problem and let
T = {T 1 , . . . , T m } be a set of trajectories in the

planning domain hX , Oi. The input to a safe model-free
planning problem is the tuple hX , sI , sG , T i and the task is
to generate a plan π that is a solution to Π. We denote this
safe model-free planning problem as ΠT .

3

Conservative Planning

To solve the safe model-free planning problem, we propose
to learn a conservative action model, and then use it to find
sound plans.
Following prior work on learning action models [Wang,
1995; Wang, 1994; Walsh and Littman, 2008], we partition
every observed trajectory hs1 , a1 , s2 , . . . , sn+1 i ∈ T into a
set of action triplets, where each action triplet is of the form
hsi , ai , si+1 i. Let T (a) be all the action triplets for action a.
A state s and s0 are called pre- and post-state of a, respectively, if there is an action triplet hs, a, s0 i. Following Walsh
and Littman [2008] and Wang [1994; 1995], we observe that
from the set of trajectories T we can “bound” the set of predicates in an action’s preconditions and effects, as follows.
∅ ⊆ pre(a) ⊆

\

s

(1)

s0

(2)

hs,a,s0 i∈T (a)

[
hs,a,s0 i∈T (a)

s0 \ s ⊆ eff(a) ⊆

\
hs,a,s0 i∈T (a)

Equation 1 holds because a value assignment (xi = v) cannot be a precondition of a if it is not in every pre-state
of a, and thus only value assignments that exists in all the
pre-states
of a may be preconditions of a (hence pre(a) ⊆
T
0
hs,a,s i∈T (a) s). On the other hand, the fact that a state variable xi happened to have the same value v in all the pre-states
of the observed trajectories does not necessarily mean that
(xi = v) is a precondition of a. It may even be the case that
a has no preconditions at all, and thus the “lower bound” on
an action’s precondition is ∅.
Equations 2 holds because a value assignment (xi = v)
cannot be an effect of a if it is not in every post-state of
a, and thus only value assignments that exists in all the
post-states of a may be preconditions of a (hence eff(a) ⊆
T
0
hs,a,s0 i∈T (a) s ). On the other hand, every variable that has
a value in the post-state that isSdifferent from the pre-state
then it must be an effect (hence hs,a,s0 i∈T (a) s0 \ s). We denote the “upper bound” of the preconditions by preU
T (a) and
the “lower bound” of the effects by effL
(a).
T

3.1

Compilation to Classical Planning

Next, we use the bounds in Equations 1 and 2 to compile a
safe model-free planning problem ΠT = hX , sI , sG , T i to
a classical SAS+ problem F (ΠT ), such that a solution to
F (ΠT ) is a solution to ΠT , i.e., it is a solution for the underlying planning problem Π. F (ΠT ) is defined as follows.
It has exactly the same set of state variables (X ), start state
(sI ), and goal (sG ) as ΠT . The actions of F (ΠT ) is the set
of all the actions seen in an observed trajectory. We denote
this set of actions by A(T ). The preconditions of an action
a in F (ΠT ) are defined as the “upper bound” estimate given
in Equation 1 (preU
T (a)) and the effects of a in F (ΠT ) are

defined to be the ”lower bound” estimate given in Equation 2
(effL
T (a)).
Definition 3 (Safe) An action model O0 is safe with respect
to an action model O if for every state s and action a it holds
that (1) if a is applicable in s according to O0 then it is also
applicable in s according to O, and (2) applying a to s results
in exactly the same state when using either O0 or O.
Theorem 1 The action model in F (ΠT ) is safe with respect
to the action model of Π.
Proof: Let OΠ and OF (ΠT ) be the action models of Π and
F (ΠT ), respectively. Since a is applicable in s according to
OF (ΠT ) , it means that preU
T (a) ⊆ s and consequently a is
also applicable in s according to OΠ , since pre(a) ⊆ preU
T
(Equation 1).
Now, let s0Π be the state resulting from applying a on s
according to OΠ , and let v denote the value of a state variable xi in s0Π , i.e., v = s0Π (xi ). Since effL
T (a) ⊆ eff(a), then
according to OF (ΠT ) either (xi = v) is an effect of a or a
has no effect on xi . If the former is true then s0F (ΠT ) (xi ) =
v = s0Π (xi ). Otherwise, it means that in the observed trajectories, applying a never changed the value of xi , i.e., xi was
equal to v in both the pre-state and post-state. By definition,
this means that (xi = v) is a precondition of a according to
OF (ΠT ) , and thus s(xi ) = s0F (ΠT ) (xi ) = v = s0Π (xi ). Thus,
the effects of a on s will be the same in both action models,

and hence a s0Π = s0F (ΠT ) .
Corollary 1 (Soundness) Every solution to F (ΠT ) is also a
solution to ΠT
Corollary 1 is a direct result of Theorem 1, and its practical
implication is the following algorithm for solving any safe
model-free planning problem ΠT : compile it to a classical
planning problem F (ΠT ), run an off-the-shelf classical planner, and return the resulting plan. We refer to this algorithm
as the conservative model-free planner. The conservative
model-free planner is sound, but it is not complete. There can
be planning problems that have a solution but the observed
trajectories are not sufficient to induce a corresponding compiled planning problem that is solvable. As an extreme example, if we do not receive any observed trajectories, the compiled planning problem will not have any actions in its action
model and thus will not be able to solve anything. In the next
section we show that the required number of trajectories is
actually reasonable.
Figure 1 illustrates how to generate F (ΠT ) from observed
trajectories in a simple logistic-like domain with one truck,
one package, and three possible location A, B, and C. The
state variables are TruckAt, with domain A, B, and C, and
PackageAt with domain A, B, C, and T , where T represents that the package is on the truck. The possible actions
are MoveX,Y , PickupX , and UnloadX , for every X, Y ∈
{A, B, C}.
The three tables on the left-hand side, T1 , T2 , and T3 are
three observed trajectories, where the column T represents
the value of the state variable TruckAt and the column P represents the value of the state variable PackageAt. For example, T1 represents a trajectory where the truck starts at A,

moves to B, picks up the package, moves to C, and unloads
the package there. The tables on the right-hand side of Figure 1 show the action model learned from these trajectories.
For didactic reasons, we show the action model learned given
just T1 (F (Π{T1 } )), then the action model learned given T1
and T2 (F (Π{T1 ,T2 } )), and finally the action model learned
using all three trajectories.
As can be observed, given only T1 we do not have any
knowledge of many actions such as PickA , PickC , etc.
Also, the preconditions learned for the actions MoveA,B and
MoveB,C are too restrictive, requiring that the package is
at some location (while clearly a Move action only requires
knowing the truck’s location). However, given T1 and T2 ,
these redundant preconditions are removed, and thus task that
can be achieved with the actions MoveA,B , MoveB,C , PickB ,
and UnloadC will be found by our conservative model-free
planner.

4

Learning to Perform Safe Planning

In general, we cannot guarantee that any finite number of trajectories will suffice to obtain precisely the underlying action
model. This is because, for example, if some action never
appears in a trajectory, we may not know its effects; or, if
an action is only used in a limited variety of states, it may be
impossible to distinguish its preconditions. Consequently, we
cannot guarantee a complete solution to the model-free safe
planning problem. However, as the number of trajectories increases, we can hope to learn enough of the actions accurately
enough to be able to find plans for most goals in practice. This
gives raise to a statistical view of the model-free safe planning
task (Definition 2) that follows the usual statistical view of
learning, along the lines of Vapnik and Chervonenkis [1971]
and Valiant [1984].
Definition 4 (Safe Model-Free Learning-to-Plan) We suppose that there is an arbitrary, unknown (prior) probability
distribution D over triples of the form hsI , sG , T i, where sI
is a state, sG is a goal condition, and T is a trajectory that
starts in sI and ends in a state that satisfies sG , and all trajectories are applicable in a fixed planning domain D = hX , Oi.
In the safe model-free
learning-to-plan
D
E
Dtask, we are given
E
(1) (1)
(m) (m)
a set of triplets sI , sG , T (1) , . . . , sI , sG , T (m)
drawn independently from D, and a new SAS+ planning
problem Π = hD, sI , sG i such that the initial state and goal
condition (sI , G) are from some (sI , sG , T ) drawn from D.
The task is to either output a plan for Π or, with probability
at most , return that no plan was found.
Remarks on the task formulation
We stress that D is arbitrary, and thus the conditional distribution of trajectories given a start and goal state, D(T |sI , sG ),
can also be any arbitrary distribution. For example, D
could be the distribution of trajectories obtained by running
some (unknown, sophisticated) planning algorithm on input
(sI , sG ), or produced by hand by a human domain expert.
More generally, the adversarial choice of D in our model
subsumes a model in which a trajectory T (sI , sG ) is nondeterministically and adversarially chosen to be paired with the
start state sI and goal sG . (Indeed, the distributions used in

𝑻𝟏
A

𝑻𝟐

B

C

A

B

𝐅(𝚷 𝑻𝟏 )

𝑻𝟑
C

A

B

T

C

P

T

MoveA,B

s1

T

P

A

B

a1 MoveA,B
s2

B

B

a2 PickB

s3

B

s1

T

P

A

A

a1 MoveA,B

s2

B

A

a2 MoveB,C
T

s3

C

A

a3 MoveB,C
s4

C

T

A

B

C

s1

T

P

A

A

A

C

B

C

Eff B

a2 MoveA,B

Eff C

s3

B

T

a3 UnloadB
s4

B

B

A

B

C

T

PickB

T

P

P

Pre A

Pre A

Pre B

T

Eff B

Eff B

Eff

B

UnloadC

MoveB,C

Pre B

Pre B

Pre C

T

Eff C

Eff C

Eff

C

PickB

PickA

Pre B

B

Pre B

B

Pre A A

Eff

T

Eff

T

Eff

UnloadC

T
UnloadB

MoveA,B

MoveB,C

T

A

a4 UnloadC

s5

Pre A B

Pre B

s2

P

MoveA,B

MoveB,C

a1 PickA

𝐅(𝚷 𝑻𝟏 ,𝑻𝟐 ,𝑻𝟑 )

𝐅(𝚷 𝑻𝟏, 𝑻𝟐 )

UnloadC

T

PickB

Pre C

T

Pre C

T

Pre B B

Eff

C

Eff

C

Eff

T

C

Figure 1: An example of creating F (ΠT ) from observed trajectories in a simple logistics-like domain. The left-hand side of the
figure shows the three given trajectories T1 , T2 , and T3 . The right hand side of the figure shows our conservative action model,
learned using different subsets of the trajectories T1 , T2 , and T3 together.
such a case satisfy the stronger restriction that D(T |sI , sG )
produces a deterministic outcome T (sI , sG ), which does not
necessarily hold in our model.)
We also note that our conservative model-free planner does
not actually require knowledge of the goals sG associated
with the trajectories drawn from D. Thus, our approach actually solves a more demanding task that does not provide
the goals to the learning algorithm. But, such a distribution
over goals is nevertheless a central feature in our notion of
“approximate completeness,” and features prominently in the
analysis as we discuss next.
Analysis of learning
A key question is how our certainty that a plan can be generated for a new start and goal state grows with the number
of trajectories. Let log and ln denote log2 and loge , respectively, and let d denote the largest number of values for a state
variable.
Theorem 2 Using the conservative model-free planner, it is
sufficient to observe m ≥ (2 ln d)|A| (|X | + log 2|A|
δ ) trajectories to solve the safe model-free learning-to-plan problem
with probability 1 − δ.
Proof Outline. First, Lemma 1 shows that the set of actions
used by our conservative model-free planner (A(T )) is sufficient to solve a randomly drawn problem with high probability. Then, Lemma 2 shows that under certain conditions, the
preconditions we learned for these actions (preU
L ) are not too
conservative, i.e., they are adequate for finding a plan with
high probability. Finally, we prove that with high probabil-

ity these conditions over the action model we learned indeed
hold.
Lemma 1 Let A be the set of actions such that each action
a ∈ A appears in a trajectory sampled from D with prob
and let A(T ) be the set of every action
ability at least 2|A|
that appeared in a trace. The probability that all the actions
a ∈ A appear in A(T ) is at least 1 − δ/2.
Proof: By definition, the probability that an action a ∈ A

does not exist in a trajectory drawn from D is 1 − 2|A|
. Since
the observed trajectories T are drawn independently from D

)m ≤
we have that the probability that a ∈
/ A(T ) is (1 − 2|A|
·m

e− 2|A| , using the inequality 1−x ≤ e−x . Since we assume in
Theorem 2 that m ≥ (2 ln d)|A| (|X |+log 2|A|
δ ) which is larger
than (2 ln 2)|A| log 2|A|
,
we
have
that
the
probability
that a ∈
/
δ
A(T ) is at most
·m



e− 2|A| ≤ e− 2|A| ·

(2 ln 2)|A|


log

2|A|
δ

= e− ln

2|A|
δ

=

δ
2|A|

(3)

Hence, by a union bound over a ∈ A (noting |A | ≤ |A|),
we have that A ⊆ A(T ) with probability 1 − δ/2 as needed.

Stated informally, Lemma 1 says that with high probability
we will observe all the “useful” actions, i.e., the actions used
in many trajectories. However, we may have learned preconditions for these actions that are too conservative, preventing
the planner from finding a plan even if one exists. We next
define a property of action models that states that this does
not occur frequently.

Definition 5 (Adequate) We call an action model -adequate
if, with probability at most /2, we sample a trajectory T
from D such that T contains an action triplet hs, a, s0 i where
a ∈ A and s does not satisfy preU
T.
We say that an action model is -inadequate if it is not adequate. An equivalent way to define the notion of an adequate action model is that with probability at most /2 a
trajectory is sampled in which an action a ∈ A is invoked on
a state that does not satisfy the conservative preconditions of
a we learned from the given set of trajectories (T ).
Lemma 2 If the learned action model is -adequate and
A ⊆ A(T ), then with probability 1 −  our conservative model-free planner will find a plan for a start-goal pair
(sI , sG ) sampled from D.
Proof:
Let T be the (unknown) trajectory sampled for
(sI , sG ). The probability that T uses an action that is not

in A is at most |A| · 2|A|
= /2. Thus, T contains only actions known to our planner with probability at least 1 − /2,
since we assumed that A ⊆ A(T ). Since the action model is
-adequate then with probability 1 − /2 the learned preconditions are satisfied on all of the states in T . Thus, by a union
bound, we find that with probability 1 − , our planner could
at least find T . Hence it will find a trajectory from sI to sG ,
as required.

Lemma 3 The action model used by our conservative modelfree planner is -adequate with probability at least 1 − δ/2.
Proof: Whether an action model is -adequate or not depends on the assignment of preconditions to actions. Since
there are |X | state variables each with at most d values, then
there are d|X | possible assignments of preconditions for an individual action and a total of d|X |·|A| possible preconditions
assignments for an action model . Let BAD be the subset
of these action model preconditions assignments that are not
-adequate. Clearly, BAD has size at most d|X |·|A| .
Consider a particular assignment of preconditions in an
-inadequate action model OBAD . Since OBAD is inadequate, it has a set of state-action pairs (s, a) associated
with it such that a ∈ A and a cannot be applied to s according to OBAD . The action model OBAD can only be
learned by our algorithm if none of these state-action pairs
were observed in the given trajectories T . On the other
hand, by the definition of inadequacy the probability of having a state-action pair from that list in a trajectory drawn
from D is at least /2. Thus, the probability that our algorithm will learn a particular preconditions assignment of
an -inadequate action model is at most (1 − /2)m . Since
2 ln d
2
m ≥ (2 ln d)|A| (|X | + log 2|A|
δ ) >
 (|A| · |X | + log δ ),
then (1 − /2)m is smaller than
− 2 ·m

−(ln d·(|A|·|X |+log

2
δ ))

− ln d·|A|·|X |

− ln

2
δ

e
≤e
≤e
·e
(4)
which is at most 2·d|Xδ|·|A| . Thus, by a union bound over this
set of inadequate assignments BAD, the probability that any
inadequate assignment of preconditions could be output is at
most δ/2. Thus, with probability 1 − δ, the algorithm indeed produces an assignment of preconditions that is neither
unsafe for A(T ) nor inadequate for A , as needed.


S(Π)
¬S(Π)
Marginals

P(Π)
1−
0
µ(1 − )

¬P(Π)

1
1 − µ(1 − )

Priors
µ
1−µ

Table 1: The table shows the priors, conditional probabilities,
and marginals obtained with probability 1 − δ when using
our conservative model-free planner when it is given m ≥
(2 ln d)|A|
(|X | + log 2|A|

δ ) trajectories.

4.1

Unsolvable Instances

The implication of Theorem 2 is that by observing a number
of trajectories that is quasi-linear in the number of actions and
the number of state variables, we expect our safe model-free
planner to be complete with high probability, in the sense that
if a solution exists it will be found. But what if some of the
drawn problem instances are not solvable?
Corollary 2 If the probability of drawing a solvable startgoal pair from D is µ then it is sufficient to observe m ≥
(2 ln d)|A|
(|X | + log 2|A|

δ ) trajectories (of solvable instances)
to guarantee that with probability of at least 1−δ our conservative model-free planner will solve a start-goal pair drawn
from D with probability at least µ · (1 − )
Proof: Let S(Π) be true or false if a given planning problem Π is solvable or unsolvable, respectively, and let P(Π)
be true or false if our planner returns a solution to Π or not
respectively. We aim to bound P r(P(Π)). Since our planner
is sound, P(Π) → S(Π) and so
P r(P(Π)) = P r(P(Π)∧S(Π)) = P r(P(Π)|S(Π))·P r(S(Π))
According to Theorem 2, P r(P(Π)|S(Π)) ≥ 1 −  and
P r(S(Π)) = µ by definition.

Table 1 shows the priors, conditional probabilities, and
marginals use by the proof of Corollary 2 The first row
shows the probabilities P r(P(Π)|S(Π)), P r(¬P(Π)|S(Π)),
abd P r(S(Π)); the second row shows the probabilities
P r(P(Π)|¬S(Π)), P r(¬P(Π)|¬S(Π)), and P r(¬S(Π)); and
the last row shows the marginal probabilities P r(P(Π)) and
P r(¬P(Π)).
Corollary 2 and Table 1 are valuable in that they provides
a relationship between µ, , δ, and m. Thus, we can increase
m to satisfy more demanding values of µ, , and δ and different types of error bounds. For example, consider an application that requires bounding, by some γ, the probability that
our planner outputs incorrectly that no plan exists. In other
words, an application that requires
P r(S(Π)|¬P(Π)) ≤ γ
Using Bayes’ rule and the values from Table 1, this means
that
γ · (1 − µ)
·µ
≤γ⇔≤
1 − (1 − ) · µ
µ · (1 + γ)
Plugging γ·(1−µ)
µ·(1+γ) into the sample complexity instead of  in
Theorem 2 will give the required number of trajectories to obtain a bound of γ on the probability of incorrectly outputting
that a problem is not solvable.

4.2

Limited Planner Capabilities

The given trajectories T are presumably generated by some
planning entity. Since planning in general is a hard problem,
it may be the case that the planner that generated the given set
of trajectories has drawn a solvable problem from D but was
just not able to solve it due to memory or time constraints.
Learning from such a set of trajectories does not enable
bounding the probability of solving problems in general.
What can be obtained in such cases is to bound the solving
capabilities of our conservative model-free planner with respect to the capabilities of the planner that generated the observed trajectories. Thus, instead of having µ represent the
probability that an instance is solvable, we will have µ represent the probability that an instance is solvable by the original
planner. The rest of the analysis follows exactly the same as
in the previous section.

5

Related Work

Our work relates to several well-studied types of problems:
planning under uncertainty, reinforcement learning, and domain model learning.
Planning under uncertainty. In common models for planning under uncertainty, such as Markov Decision Problems
(MDP) and Partially Observable MDPs (POMDP), the uncertainty stems from the stochastic nature of the world or
from imperfect sensors that prevent full observability of the
agent’s state. Our setting is different in that our uncertainty
only stems from not knowing the agent’s action model.
Reinforcement learning. Reinforcement learning algorithms learn how to act by interacting with the environment.
Thus, they are designed for a trial-and-error approach to learn
the domain and/or how to plan in it. Our task is to generate a
plan that must work, so a trial-and-error approach is not sufficient.
Domain model learning. Most prior work on learning a
domain model in general or a STRIPS action model from observed trajectories, such as ARMS [Yang et al., 2007] and
LOCM [Cresswell et al., 2013], learn approximate models
that do not guarantee safety. Hence, such work generally
also involves some form of trial-and-error as well, iteratively
requesting more example trajectories or interacting directly
with the environment to refine the learned model [Mourão
et al., 2012; Wang, 1994; Wang, 1994; Walsh and Littman,
2008; Levine and DeJong, 2006; Jiménez et al., 2013]. In addition, most works learn from both positive and negative examples – observing successful and failed trajectories, while
we only require successful trajectories to be provided.
Another key difference is that unlike our work, most prior
works do not provide statistical guarantees on the soundness
of the plan generated with their learned model. An exception
to this is the work of Walsh and Littman [2008], that also
discussed the problem of learning STRIPS operators from
observed trajectories and provided theoretical bounds on the
sample complexity – the number of interactions that may fail

until the resulting planner is sound and complete. By contrast, we do not assume any planning and execution loop and
do not allow failed interactions. Hence, we aim for a planning
algorithm that is guaranteed to be sound, at the cost of completeness. This difference affects their approach to learning.
They attempted to follow an optimistic assumption about the
preconditions and effects of the learned actions, in an effort
to identify inaccuracies in their action model. By contrast,
we are forced to take a pessimistic approach, as we aim for a
successful execution of the plan rather than information gathering to improve the action model.

6

Conclusions

This paper deals with a planning problem in which the planner agent has no knowledge about its actions. Instead of an
action model, the planner is given a set of observed trajectories of successfully executed plans. In this setting we introduced the safe model-free planning problem, in which the
task is to find a plan that is guaranteed to reach the goal, i.e.,
there is no tolerance for execution failure. This type of problem is important in cases where failure is costly or in cases
where the agent has no capability to replan during execution.
We showed how to use the given set of trajectories to learn
about the agent’s actions, bounding the set of predicates in the
actions’ preconditions and effects. Then, we proposed a conservative approach to solve the safe model-free problem that
is based on a translation to a classical planning problem. This
solution is sound but is not complete, as it may fail to find
a solution even if one exists. However, we prove that under
some assumptions the likelihood of finding a solution with
this approach grows linearly with the number of predicates
and quasi-linearly with the number of actions.
Future directions for safe model-free planning include
studying how to address richer underlying planning models
including parametrized actions, conditional effects, stochastic action outcomes, and partial observability. While some
of these more complex action models can be compiled away
(e.g., a problem with conditional effects can be compiled to
a problem without conditional effects [Nebel, 2000]), the resulting problem can be significantly larger. A particularly interesting direction is how to learn there lifted action model,
i.e., what can be learned from a trajectory with an action a(x)
on the action model of a(y), where a is a parameterized action and x and y are different values for the same parameter.

Acknowledgements
B. Juba was partially supported by an AFOSR Young Investigator Award. R. Stern was partially supported by the Cyber
Security Research Center at BGU.

References
[Bäckström and Nebel, 1995] Christer Bäckström and Bernhard Nebel. Complexity results for SAS+ planning. Computational Intelligence, 11(4):625–655, 1995.
[Cavalcanti et al., 2007] Adriano Cavalcanti, Bijan Shirinzadeh, Robert A Freitas Jr, and Tad Hogg. Nanorobot
architecture for medical target identification. Nanotechnology, 19(1):015103, 2007.

[Cresswell et al., 2013] Stephen N. Cresswell, Thomas L.
McCluskey, and Margaret M. West. Acquiring planning
domain models using LOCM. The Knowledge Engineering Review, 28(02):195–213, 2013.
[Daniely and Shalev-Shwartz, 2016] Amit Daniely and Shai
Shalev-Shwartz. Complexity theoretic limtations on learning DNF’s. In Proceedings of the 29th Conference on
Computational Learning Theory, volume 49 of JMLR
Workshops and Conference Proceedings, pages 1–16.
2016.
[Fikes and Nilsson, 1971] Richard E Fikes and Nils J Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial intelligence,
2(3-4):189–208, 1971.
[Jiménez et al., 2013] Sergio Jiménez, Fernando Fernández,
and Daniel Borrajo. Integrating planning, execution, and
learning to improve plan execution. Computational Intelligence, 29(1):1–36, 2013.
[Kakade, 2003] Sham M. Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of
London, 2003.
[Kearns and Valiant, 1994] Michael Kearns and Leslie
Valiant. Cryptographic limitations on learning boolean
formulae and finite automata. Journal of the ACM
(JACM), 41(1):67–95, 1994.
[Kearns et al., 2002] Michael Kearns, Yishay Mansour, and
Andrew Ng. A sparse sampling algorithm for near-optimal
planning in large Markov decision processes. Mach.
Learn., 49(2):193–208, 2002.
[Levine and DeJong, 2006] Geoffrey Levine and Gerald DeJong. Explanation-based acquisition of planning operators. In ICAPS, pages 152–161, 2006.
[Littman, 1994] Michael L. Littman. Memoryless policies:
Theoretical limitations and practical results. In From Animals to Animats 3: Proceedings of the Third International Conference on Simulation of Adaptive Behavior,
volume 3, page 238. MIT Press, 1994.
[McDermott et al., 1998] Drew McDermott, Malik Ghallab,
Adele Howe, Craig Knoblock, Ashwin Ram, Manuela
Veloso, Daniel Weld, and David Wilkins. PDDL-the planning domain definition language. Technical report, AIPS
’98 - The Planning Competition Committee, 1998.
[Meuleau et al., 1999] Nicolas Meuleau, Kee-Eung Kim,
Leslie Pack Kaelbling, and Anthony R. Cassandra. Solving POMDPs by searching the space of finite policies. In
Proceedings of the Fifteenth conference on Uncertainty in
artificial intelligence, pages 417–426. Morgan Kaufmann
Publishers Inc., 1999.
[Mourão et al., 2012] Kira Mourão, Luke S Zettlemoyer,
Ronald Petrick, and Mark Steedman. Learning STRIPS
operators from noisy and incomplete observations. In UAI,
pages 614–623, 2012.
[Nebel, 2000] Bernhard Nebel. On the compilability and
expressive power of propositional planning formalisms.

Journal of Artificial Intelligence Research, 12:271–315,
2000.
[Valiant, 1984] Leslie G. Valiant. A theory of the learnable.
Communications of the ACM, 18(11):1134–1142, 1984.
[Vapnik and Chervonenkis, 1971] V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability
and its Applications, 16(2):264–280, 1971.
[Walsh and Littman, 2008] Thomas J. Walsh and Michael L.
Littman. Efficient learning of action schemas and webservice descriptions. In the National Conference on Artificial Intelligence (AAAI), pages 714–719, 2008.
[Wang, 1994] Xuemei Wang. Learning planning operators
by observation and practice. In the International Conference on Artificial Intelligence Planning Systems (AIPS),
pages 335–340, 1994.
[Wang, 1995] Xuemei Wang. Learning by observation and
practice: An incremental approach for planning operator
acquisition. In ICML, pages 549–557, 1995.
[Yang et al., 2007] Qiang Yang, Kangheng Wu, and Yunfei
Jiang. Learning action models from plan examples using weighted MAX-SAT. Artificial Intelligence, 171(23):107–143, 2007.

