Learning Probably Approximately Complete and Safe Action Models for Stochastic Worlds

Brendan Juba, Roni Stern

Introduction

In the field of AI planning, an agent's ability to navigate and manipulate its environment depends heavily on its "action model"—a formal representation of how specific actions change the state of the world. While learning these models in deterministic environments is a well-understood challenge, real-world scenarios are rarely so predictable. Most environments are stochastic, where an action might lead to several different outcomes with varying probabilities.

Traditionally, these probabilities are either specified by hand—a process prone to human error—or learned through Reinforcement Learning (RL). However, RL often produces models optimized for a single goal. General-purpose planning requires a model that can solve any arbitrary goal. This paper introduces SAM+, an algorithm designed to learn reliable, general-purpose action models for stochastic worlds using only a set of previously executed trajectories.

The Challenge of Stochastic Planning

In stochastic environments, even minor errors in probability estimation can compound over a sequence of actions, leading to plans that fail in practice. The authors identify three primary requirements for a learned model:

  1. Efficiency: It must be computable in polynomial time.
  2. Accuracy: It must be "Probably Approximately Complete" (PAC), meaning it captures enough of the world's dynamics to find solutions if they exist.
  3. Safety: It must ensure that any plan deemed successful by the model has a high probability of succeeding in the real world.

Methodology: The SAM+ Algorithm

SAM+ evolves the previous Safe Action Model (SAM) framework to handle the complexities of the Probabilistic Planning Domain Description Language (PPDDL).

Imprecise PPDDL (PPDDL-IP)

Rather than forcing the learner to commit to a single, potentially incorrect probability (e.g., "Action A succeeds with 0.72 probability"), SAM+ utilizes Imprecise PPDDL. This representation uses probability intervals (e.g., "[0.70, 0.74]"). These intervals capture the inherent uncertainty that arises when learning from finite data. As the agent observes more data, these intervals shrink, reflecting increased confidence.

Learning Preconditions and Effects

SAM+ learns the structure of actions through two distinct processes:

  • Precondition Learning: The algorithm identifies the necessary conditions for an action by analyzing the intersection of all states where that action was successfully initiated in the training data.
  • Statistical Interval Estimation: To determine the effects of an action, SAM+ tracks the frequency of state changes. It employs the Azuma-Hoeffding inequality to calculate confidence intervals. If data is sparse, the interval remains wide (pessimistic); as more trajectories are observed, the model converges toward the true probability.

The Independence Assumption

To maintain computational tractability and avoid the "curse of dimensionality," SAM+ assumes that the effects of an action on different variables (fluents) are independent. While this is a simplification of complex real-world physics, it allows the algorithm to scale effectively to large state spaces.

Theoretical Guarantees

The core contribution of this work lies in its formal proofs regarding the reliability of the learned models:

  • Safety: The authors prove that with high probability, the true real-world transition probabilities fall within the intervals learned by SAM+.
  • Completeness: They demonstrate that if a policy exists that can achieve a goal in the real world, a corresponding policy will exist within the learned PPDDL-IP model.
  • Computational Complexity: The algorithm is highly efficient, running in $O((m + |A|)|F|)$ time, where $m$ is the number of trajectories, $|A|$ is the number of actions, and $|F|$ is the number of fluents.

Results and Discussion

While primarily a theoretical contribution, the authors illustrate the algorithm's utility using the Coffee domain, a standard planning benchmark. The results show that SAM+ can compute a model that is "adequate" for planning with a bounded number of trajectories.

Furthermore, the paper provides a mechanism to convert these "Imprecise" models back into standard PPDDL models (using interval midpoints). This ensures compatibility with existing off-the-shelf planners while maintaining "approximate safety," meaning the model's success predictions will not wildly deviate from real-world performance.

Limitations and Future Work

Despite its strengths, SAM+ has areas for further development:

  • Correlated Effects: The current independence assumption may fail in domains where variables are tightly coupled (e.g., a robot's X and Y coordinates). Future iterations may treat related fluents as single vector-valued entities.
  • Lifted Representations: While the current proofs focus on grounded domains (specific objects), extending the logic to "lifted" domains (general rules for object types) is a key next step.
  • Continuous Spaces: SAM+ is currently limited to discrete, Boolean states. Adapting the interval-based learning approach to continuous environments remains an open research challenge.

Summary updated

Abstract

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.
BibTeX
@inproceedings{juba2022learning,
  author = {Brendan Juba and Roni Stern},
  title = {{Learning Probably Approximately Complete and Safe Action Models for Stochastic Worlds}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21215},
}
Figure