When an autonomous agent operates in a mission-critical environment, it must accurately predict the outcomes of its actions. Traditionally, agents learn these rules—known as action models—by observing transitions in the environment and fitting a model that maximizes statistical accuracy. However, as noted by Argaman Mordoch et al. in Learning Safe Numeric Action Models, standard machine learning approaches often yield "best guess" models. If a learned model mistakenly omits a vital precondition, the planning agent will assume an action is safe when it is actually hazardous.
In high-stakes settings, executing a plan based on an inaccurate model can cause catastrophic system failures, a risk highlighted early on by P. R. Davis et al. in Using and Re-Using Partial Plans. For instance, if a robot's internal model fails to capture complex safety risks or unmodeled hazards, its generated plans will fail during real-world execution, as discussed by Dinesh Parthasarathy et al. in C-MCTS: Safe Planning with Monte Carlo Tree Search. To prevent physical damage or system failure, we need a learning mechanism that guarantees execution soundness: any plan generated by the learned model must be guaranteed to succeed in reality.
Flipping the Bias to Inductive Pessimism
How can an agent learn a guaranteed-safe model from limited observations without trial-and-error? The key insight, pioneered by Brendan Juba et al. in Efficient, Safe, and Probably Approximately Complete Learning of Action Models, is to adopt a stance of extreme pessimism during model induction.
Instead of starting with an empty set of preconditions and adding constraints only when failures occur, a conservative learner does the exact opposite. As explained by Brendan Juba et al. in Safe Learning of Lifted Action Models, the algorithm initially assumes that every possible condition in the environment is a required precondition for an action, and that the action has no effects.
When the agent observes a successful execution of an action, it uses this empirical evidence to prune away unnecessary constraints. Specifically, if an action successfully executes in a state where a certain feature is absent, that feature cannot be a mandatory precondition. By taking the intersection of all state features present across all observed successful executions, the agent gradually shrinks the precondition set, as demonstrated in Efficient, Safe, and Probably Approximately Complete Learning of Action Models.
Why It Works: The Subset-Superset Guarantee
To understand why this approach guarantees absolute safety, consider the relationship between the learned preconditions ($\hat{P}$) and the true, hidden preconditions ($P^*$) of an action.
Because the algorithm starts by assuming all features are preconditions and only removes a feature when empirical evidence explicitly proves it is unnecessary, the learned precondition set $\hat{P}$ is guaranteed to be a superset of the true preconditions:
$$\hat{P} \supseteq P^*$$
When a planner evaluates whether an action can be executed in a given state $S$, it checks if the state satisfies the learned preconditions ($S \models \hat{P}$). Because $\hat{P}$ contains all true preconditions (plus potentially some extra, unpruned ones), any state that satisfies $\hat{P}$ must logically satisfy $P^*$:
$$S \models \hat{P} \implies S \models P^*$$
This mathematical relationship ensures that the agent will never attempt an action in a state where it might fail. In the language of version spaces—which represent the set of all models consistent with the data—this conservative estimate corresponds to extracting the lower bound of a version space, a concept formalized by Brendan Juba et al. in Action Model Learning with Guarantees. While the upper bound represents a "complete" model that preserves all possible plans, the lower bound yields a "sound" model that prioritizes safety and correctness above all else.
[ True Preconditions (P*) ] ⊆ [ Learned Preconditions (P̂) ]
▲ ▲
│ │
Must be satisfied Planner checks this
for real success before acting
Handling Partial Observability and Continuous Spaces
The power of conservative precondition estimation is its adaptability to complex, real-world domains. The core pessimistic framework has been extended across several challenging dimensions:
- Lifted Action Models: In relational domains, Brendan Juba et al. introduced the Safe Action Model (SAM) learning algorithm in Safe Learning of Lifted Action Models, which applies this conservative strategy to parameterized, lifted representations, enabling the agent to generalize safety constraints across different objects from minimal trajectories.
- Partial Observability: When an agent cannot observe the full state of the world, it risks missing hidden preconditions. To counter this, Brendan Juba et al. developed PI-SAM and EPI-SAM in Learning Safe Action Models with Partial Observability. These algorithms maintain execution soundness under partial observability by continuing to assume an action has all possible preconditions and no effects until empirical evidence explicitly proves otherwise.
- Conditional Effects: In environments where an action's outcomes depend on the context, Argaman Mordoch et al. extended conservative learning to complex domains in Safe Learning of PDDL Domains with Conditional Effects, ensuring that actions are only permitted when their preconditions are definitively supported by observed transitions.
- Numeric Domains: For environments governed by continuous variables, the authors developed N-SAM in Learning Safe Numeric Action Models. Instead of intersecting discrete features, N-SAM computes the convex hull of observed successful states to define numeric preconditions, guaranteeing that the planner only operates within safe, verified regions of the continuous state space.
The Fundamental Trade-off: Soundness vs. Completeness
The absolute safety guarantee of conservative precondition estimation comes with a distinct trade-off: incompleteness.
Because the agent requires explicit empirical evidence to remove a precondition, it remains highly cautious about unobserved states. If the training data is sparse, the learned model will retain many redundant preconditions. As a result, a valid plan might exist in reality, but the planner will be unable to discover it because it cannot verify the safety of the required transitions, as noted in Efficient, Safe, and Probably Approximately Complete Learning of Action Models and Safe Learning of PDDL Domains with Conditional Effects.
However, in mission-critical systems—where a single failure means physical destruction or catastrophic loss—sacrificing completeness to achieve total execution soundness is not just a design choice; it is a fundamental requirement.
Key Foundational Work
Efficient, Safe, and Probably Approximately Complete Learning of Action Models (2017) — contributed 3 concept elements to this direction.
Using and Re-Using Partial Plans (1977) — contributed 1 concept elements to this direction.