# Learning Partially Observable Deterministic Action Models

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2014.

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

- [A Survey of Optimization-based Task and Motion Planning: From Classical To Learning Approaches](https://mlsanity.com/paper/2404.02817/) (2024)
- [Learning Efficient Abstract Planning Models that Choose What to Predict](https://mlsanity.com/paper/2208.07737/) (2022)
- [Safe Learning of Lifted Action Models](https://mlsanity.com/paper/2107.04169/) (2021)
- [Goal Recognition as Reinforcement Learning](https://mlsanity.com/paper/2202.06356/) (2022)
- [MACQ: A Holistic View of Model Acquisition Techniques](https://mlsanity.com/paper/2206.06530/) (2022)
- [Planning Domain Model Acquisition from State Traces without Action Parameters](https://mlsanity.com/paper/2402.10726/) (2024)
- [Safe Learning of PDDL Domains with Conditional Effects -- Extended Version](https://mlsanity.com/paper/2403.15251/) (2024)
- [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)
- [Toward Learning POMDPs Beyond Full-Rank Actions and State Observability](https://mlsanity.com/paper/2601.18930/) (2026)
- [Learning to Act and Observe in Partially Observable Domains](https://mlsanity.com/paper/2109.06076/) (2021)
- [Synthesis of Procedural Models for Deterministic Transition Systems](https://mlsanity.com/paper/2307.14368/) (2023)
- [Enabling Robots to Identify Missing Steps in Robot Tasks for Guided Learning from Demonstration](https://mlsanity.com/paper/2311.18355/) (2023)
- [Learning Action Models with Conditional and Quantified Effects via Uncertainty-Guided Exploration](https://mlsanity.com/paper/2608.30955/) (2026)
- [NashDreamer: Model-Based Reinforcement Learning for Zero-Sum Imperfect-Information Games](https://mlsanity.com/paper/2609.01549/) (2026)

## Abstract (arXiv)

We present exact algorithms for identifying deterministic-actions effects and preconditions in dynamic partially observable domains. They apply when one does not know the action model(the way actions affect the world) of a domain and must learn it from partial observations over time. Such scenarios are common in real world applications. They are challenging for AI tasks because traditional domain structures that underly tractability (e.g., conditional independence) fail there (e.g., world features become correlated). Our work departs from traditional assumptions about partial observations and action models. In particular, it focuses on problems in which actions are deterministic of simple logical structure and observation models have all features observed with some frequency. We yield tractable algorithms for the modified problem for such domains. Our algorithms take sequences of partial observations over time as input, and output deterministic action models that could have lead to those observations. The algorithms output all or one of those models (depending on our choice), and are exact in that no model is misclassified given the observations. Our algorithms take polynomial time in the number of time steps and state features for some traditional action classes examined in the AI-planning literature, e.g., STRIPS actions. In contrast, traditional approaches for HMMs and Reinforcement Learning are inexact and exponentially intractable for such domains. Our experiments verify the theoretical tractability guarantees, and show that we identify action models exactly. Several applications in planning, autonomous exploration, and adventure-game playing already use these results. They are also promising for probabilistic settings, partially observable reinforcement learning, and diagnosis.