Pith. sign in

REVIEW 3 major objections 5 minor 36 references

Learning Lifted Action Models From Traces of Incomplete Actions and States

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read SYNTH recovers hidden planning domains from partial traces, proving that omitted action arguments and missing state predicates can be learned exactly.

desk verdict Genuinely new variant of action-model learning with a clean algorithm and strong experiments, but the main completeness theorem rests on an uncharacterized 'suitable traces' condition that the experiments tune around. read the letter →

arxiv 2508.21449 v1 pith:EBHUENEQ submitted 2025-08-29 cs.AI

Niklas Jansen , Jonas Gösgens , Hector Geffner This is my paper · ORCID
classification cs.AI
keywords liftedactionmodellearningSTRIPS+partialobservabilityimplicitargumentsconjunctivequeriesclassicalplanningstate-actiontracesSYNTH
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tackles a realistic gap: a planning agent often observes only action labels like "up" and tile positions, not the full STRIPS state such as the blank cell or all action arguments a STRIPS model requires. It introduces STRIPS+, a variant where missing action arguments are left implicit and recovered by preconditions that uniquely determine them. The learning algorithm SYNTH builds those preconditions as a stratified sequence of conjunctive queries, one implicit variable at a time, then learns the remaining preconditions and effects. The paper proves completeness and, for a suitable finite set of traces from a stratified hidden domain, that the learned domain generates exactly the same state-action traces as the hidden domain. Experiments on STRIPS+ translations of thirteen standard planning domains reach 100% verification on sampled state-action pairs, including on four domains where selected state predicates are removed from the traces.

What carries the argument

The carrying object is the stratified conjunctive query Q(x,y,z), a conjunction of lifted atoms built one subquery at a time: each subquery Qi(x,y,zi) determines the value of a new implicit variable zi given x and the previously fixed z variables. SYNTH's EXPAND routine conjoins candidate atoms until TEST returns a unique grounding in every observed state-action pair, discarding queries that are invalid, not determined, or subsumed by an already-known variable. This query acts as a referring expression that recovers the hidden action arguments; the same bindings then let the algorithm read off the remaining universal and existential preconditions and the add/delete effects. Stratification is

What would settle it

Generate a trace from a hidden stratified STRIPS+ domain in which every observed state-action pair has a unique grounding for each implicit variable, but some invalid candidate precondition happens to be true in all observed applications and is never seen as false. Run SYNTH on that trace, then test the learned domain on a new instance where the same precondition is false. If the learned domain applies the action incorrectly, then the 'suitable traces' condition in Theorem 2 is doing essential work and must be characterized rather than assumed.

Watch

Extended reading notes

Core claim

The central claim is that a lifted action model can be learned exactly from traces in which states omit some predicates and actions reveal only a minimal set of arguments. STRIPS+ makes this precise by allowing action schemas a(x) to carry implicit arguments z whose values are determined by the explicit arguments x through the precondition formula; the formula must be a simple, stratified conjunctive query, so implicit values can be computed one z variable at a time. SYNTH learns, for each observed action, a maximal valid query that denotes the same object tuple as the hidden precondition in every trace state where the action applies, then learns the remaining preconditions and the add/delet

Load-bearing premise

The whole guarantee rests on the input traces being rich enough: every hidden implicit argument must appear with all its possible denotations, and every wrong candidate precondition must be contradicted by at least one observed state-action pair; the hidden domain must also be layered so each missing argument can be pinned down one at a time.

Editorial extensions

If this is right

  • If Theorem 2 holds, traces collected by an agent that sees only action labels and partial state information are sufficient to reconstruct the underlying lifted STRIPS+ model exactly, not approximately.
  • The learned domain is interchangeable with the hidden one: any trace produced from an instance of the hidden domain is a trace of the learned instance, and vice versa.
  • Predicates that are artefacts of STRIPS encodings, such as blank, clear, ontable, in-lift, and on, can be dropped from observations and either recovered implicitly or replaced by quantified negated preconditions.
  • Because the STRIPS+ translation roughly halves the number of observed action arguments, the same traces are more compact than full STRIPS traces yet still support exact learning.
  • SYNTH also learns referring expressions that are valid but unused in the final model, indicating it recovers more state-dependent functions than the minimal action model needs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's 'suitable traces' condition is not characterized explicitly; identifying it would yield a teaching dimension or sample-complexity bound for lifted action-model learning.
  • The stratification restriction may be more restrictive than necessary: domains where implicit variables can only be determined jointly, rather than one at a time, fall outside the guarantee and would need a different query synthesis strategy.
  • The authors point toward Atari-like pixel states; if SYNTH's query synthesis generalizes to cell-color representations, it could offer a transparent, lifted alternative to neural world models in model-based RL.
  • Unused z variables learned by SYNTH, such as 'the other room' in Gripper, suggest the algorithm could also serve as a source of candidate state features for abstraction or options beyond the action model itself.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces STRIPS+, a variant of STRIPS in which some action arguments are implicit and preconditions may use a limited form of existential quantification, and studies the task of learning a lifted STRIPS+ domain from state-action traces in which both states and actions are incomplete. The proposed algorithm, SYNTH, learns for each action a stratified conjunction of conjunctive queries that determine the implicit arguments, then adds extra preconditions and effects that are valid over the observed traces. The authors claim correctness and completeness for the stratified fragment (Theorem 2) and report 100% verification rates on STRIPS+ translations of several classical planning domains, including settings with selected predicates removed from the observed states. The main weakness is that Theorem 2 is conditional on an uncharacterized notion of a 'suitable finite set of traces,' and the experiments select trace length and instance size until SYNTH succeeds, so the completeness claim is not established as stated.

Significance. If the central claim were established, this would be a meaningful advance: it extends lifted action-model learning from full STRIPS traces to the more realistic setting of minimal action arguments and partially observable state predicates, and the stratified-query formulation gives a tractable handle on implicit arguments. The paper is also commendable for making code and data publicly available and for grounding the semantics in a precise STRIPS+ definition. However, the advertised correctness/completeness result rests on a 'suitable traces' premise that is not characterized, and the empirical evaluation verifies only finitely many sampled state-action pairs after tuning the training data until success. The contribution is therefore currently a promising heuristic algorithm with a conditional theorem, rather than a proven complete learner for the stratified STRIPS+ fragment.

major comments (3)
  1. [Section 6.3, Theorem 2] The theorem states equivalence 'for a suitable finite set of traces T' but never characterizes suitability. The proof sketch asserts that any invalid precondition will be rendered invalid through a single state in a trace and that there are finitely many such candidates, but finiteness of candidates does not imply that one finite trace set can witness every invalid precondition across all instances of the hidden domain. Without a bound or a checkable property of T (e.g., a covering condition on reachable states or a PAC-style sample bound), the completeness claim is conditional on an unspecified oracle. This is load-bearing: Section 6.2 builds Q' from atoms true in all observed states, so an invalid precondition that is true in all observed states but false in an unobserved reachable state makes the learned domain strictly more restrictive than the hidden one, breaking the 'vice versa' d
  2. [Section 7, Analysis paragraph] The paper states that 'Both the length of the traces and the size of the instances used to generate the traces were selected so that SYNTH outputs the correct domains.' This confirms that the uncharacterized 'suitable traces' condition is doing substantial work: the algorithm is not shown to succeed for arbitrary traces, and no failure characterization or sample-complexity bound is provided. The abstract and conclusions nevertheless claim correctness and completeness without this caveat. The authors should either characterize suitability, provide a procedure that checks it, or explicitly reframe the theoretical claim as conditional and the experimental result as a heuristic demonstration.
  3. [Section 7, Verification and Table 1] The empirical verification samples a finite number of state-action pairs (#SA) and reports 100% correctness, but this cannot substantiate the universal semantic equivalence asserted in Theorem 2. A finite sample can miss rare states in which the learned preconditions diverge from the hidden domain. Moreover, the verification compares the learned DL with the STRIPS+ translation D, not with the original STRIPS domain D', and the hidden domains themselves are generated by a translation process using preconditions and traces from D'. The evaluation is therefore a useful consistency check, but it does not provide evidence for the quantified 'any instance' claim in Theorem 2. Please state the verification's role as a sanity check rather than a proof of equivalence.
minor comments (5)
  1. [Definition 6] The trace notation 's0, a0, s1, a2, . . .' appears to have a typo: the second action should be a1, not a2.
  2. [Algorithm 2] The variable Q is used both for the input query Q(x,y,zi) and for the local set of candidate atoms in the first line of EXPAND. This shadowing makes the pseudocode hard to read; please rename the local set, e.g., Cand.
  3. [Section 6.1, Maximality] The maximality condition is stated informally ('n is maximal; i.e., no other determined variables can be pushed into z...') and the lexicographic ordering of atoms is introduced only in prose. Since the greedy search depends on this ordering, the paper should state formally what maximality means and whether the returned query depends on the chosen ordering; Theorem 1 does not address order dependence.
  4. [Throughout] There are several typographical slips, including 'exapansion' in Algorithm 2's explanation and 'lef t' in the c-Puzzle analysis. Also, the notation Q(x,y,zi) is used both for the partial query prefix and for the full conjunction; a consistent notation such as Q_{<=i} would help.
  5. [Section 8, c-Puzzle] The analysis says the predicate blank 'does not need to be contained in the states' for learning to succeed. This is a nice observation, but it would be useful to state precisely when a predicate can be omitted: the n-puzzle paragraph notes that the same removal fails for the n-puzzle, and the boundary between the two cases is left implicit.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; the formal result is conditional on an uncharacterized 'suitable traces' premise, and the empirical evaluation is self-referential, but the derivation chain does not reduce to its inputs by construction.

full rationale

The paper's central theorem (Theorem 2) states that for a 'suitable finite set of traces T' the learned domain DL is equivalent to the hidden domain D. The proof sketch relies on the assertion that 'any invalid precondition will be rendered invalid through a single state in a trace.' This is a trace-completeness condition that is left uncharacterized, but it is not a circular definition: 'suitable' is not defined in terms of DL, and the theorem is a standard-type conditional guarantee in learning theory. The query-learning algorithm SYNTH constructs preconditions and effects from observed traces without fitting parameters to a target quantity; the learned model is then verified against the hidden domain on held-out states, which is an external comparison. The main weakness is in the experimental pipeline: hidden STRIPS+ domains are obtained from STRIPS domains using a translation tool described as 'a simplification of the query learning component of SYNTH.' Thus the test domains are generated by the same query-discovery logic that SYNTH implements, making the empirical evaluation self-referential. This is a methodological limitation, not a circularity in the formal derivation. Self-citations to the authors' prior SIFT work concern the well-formedness assumption and atom-pattern representations, and are not load-bearing evidence for the main theorem. Overall, no step reduces by construction to its inputs; the score reflects only the minor self-referential benchmark generation and the informal 'suitable traces' premise.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The ledger shows what the paper assumes rather than proves. The central structural assumption is stratification (each implicit argument determinable one at a time), which enables the greedy query synthesis but excludes many natural preconditions. The most consequential entry is the uncharacterized 'suitable traces' condition in Theorem 2, which is effectively an existence assumption: the guarantees hold when someone supplies traces rich enough to refute all wrong hypotheses, and the experiments obtain such traces by manual tuning of instance size and trace length. The closed-world assumption is also load-bearing for the negated-precondition queries that recover removed predicates. Notably there are no invented entities: no new particles, forces, or objects; STRIPS+ is a language restriction drawing on PDDL :vars, and the implicit z variables and existential y variables are variables within the planning language whose denotations are grounded in observed atoms.

free parameters (3)
  • trace length #L per domain = 250 to 10000 depending on domain (Table 1)
    Chosen manually per domain; Section 7 Analysis states the lengths were selected so that SYNTH outputs the correct domains, and that learning fails with shorter traces.
  • instance size #O per domain = 5 to 63 objects (Table 1)
    Chosen manually per domain for the same reason; the n-puzzle requires a 5x5 instance while the c-puzzle works at 4x4, showing sensitivity to the instance size.
  • lexicographic atom ordering in EXPAND = lexicographic order over lifted atoms
    Implementation choice (Section 6.1). The paper asserts all successful maximal queries denote the same unique tuple of objects, but no proof of ordering independence is given, so correctness could depend on this choice.
assumptions (7)
  • domain assumption Hidden precondition formulas are 'simple': each y variable appears exactly once in the query.
    Definition 4, Section 5.1. Restricts the target fragment so satisfiability is easy; every STRIPS problem fits but many realistic preconditions (e.g., sharing variables across atoms) do not.
  • domain assumption Hidden precondition formulas are 'stratified': the implicit z variables are determinable one at a time, in a fixed order, from the x variables and the previously determined z variables.
    Definition 5, Section 5.1. This is the structural condition that makes SYNTH's greedy, lexicographic construction tractable and is essential to Theorem 1; if a hidden variable requires two atoms jointly to be determined in a non-stratifiable way, the fragment excludes it.
  • domain assumption Action effects are well-formed: the complement of each effect is an (explicit or implicit) precondition, so no action adds a true atom or deletes a false one.
    Section 4, following SIFT (Gösgens, Jansen, Geffner 2024). Needed so that observed flips of atoms between consecutive states can be attributed to effects.
  • domain assumption Closed-world reading of states: an atom absent from the observed state is false, making negated preconditions like forall y. not at(y,z) usable to identify empty cells.
    Section 6.4. Used to recover the blank in the c-puzzle without the blank predicate; fails in settings with genuine partial observability or noise, and is the reason the n-puzzle variant cannot recover the blank.
  • ad hoc to paper There exists a finite trace set T that refutes every invalid candidate precondition and exhibits every determined z-variable denotation; this 'suitability' is not characterized.
    Theorem 2, Section 6.3 ('For a suitable finite set of traces T...'). The paper gives no lower bound, distribution, or test for this condition, and Section 7 shows empirically that short traces or small instances break the learning.
  • domain assumption The STRIPS-to-STRIPS+ translation used to generate hidden domains is semantically correct.
    Section 7 (Translation into STRIPS+): a simplification of SYNTH's query learning decides which arguments become implicit z variables. The learned domains are verified against this translation, not against the original STRIPS domains, so an error in the translation would propagate through the evaluation.
  • domain assumption States in traces are reachable and the observed predicates are noise-free and complete for the predicates that are observed.
    Section 3 and Definition 6. All experiments use deterministic random traces from a known instance with no noise; the problem with corrupted observations is out of scope.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Lifted Action Models From Traces of Incomplete Actions and States." pith.science (2026). https://pith.science/paper/EBHUENEQ

@misc{pith2026250821449,
  author       = {Pith},
  title        = {Pith review of: Learning Lifted Action Models From Traces of Incomplete Actions and States},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EBHUENEQ}},
  note         = {Machine review of arXiv:2508.21449}
}
read the original abstract

Consider the problem of learning a lifted STRIPS model of the sliding-tile puzzle from random state-action traces where the states represent the location of the tiles only, and the actions are the labels up, down, left, and right, with no arguments. Two challenges are involved in this problem. First, the states are not full STRIPS states, as some predicates are missing, like the atoms representing the position of the ``blank''. Second, the actions are not full STRIPS either, as they do not reveal all the objects involved in the actions effects and preconditions. Previous approaches have addressed different versions of this model learning problem, but most assume that actions in the traces are full STRIPS actions or that the domain predicates are all observable. The new setting considered in this work is more ``realistic'', as the atoms observed convey the state of the world but not full STRIPS states, and the actions reveal the arguments needed for selecting the action but not the ones needed for modeling it in STRIPS. For formulating and addressing the learning problem, we introduce a variant of STRIPS, which we call STRIPS+, where certain STRIPS action arguments can be left implicit in preconditions which can also involve a limited form of existential quantification. The learning problem becomes the problem of learning STRIPS+ models from STRIPS+ state-action traces. For this, the proposed learning algorithm, called SYNTH, constructs a stratified sequence (conjunction) of precondition expressions or ``queries'' for each action, that denote unique objects in the state and ground the implicit action arguments in STRIPS+. The correctness and completeness of SYNTH is established, and its scalability is tested on state-action traces obtained from STRIPS+ models derived from existing STRIPS domains.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 35 canonical work pages

  1. [1]

    Aineto, D., and Scala, E. 2024. Action model learning with guarantees. arXiv preprint arXiv:2404.09631

    work page Pith review arXiv 2024

  2. [2]

    J.; and Onaindia, E

    Aineto, D.; Celorrio, S. J.; and Onaindia, E. 2019. Learning action models with minimal observability. Artificial Intelligence 275:104--137

    work page 2019

  3. [3]

    Arora, A.; Fiorino, H.; Pellier, D.; M \'e tivier, M.; and Pesty, S. 2018. A review of learning planning action models. The Knowledge Engineering Review 33

    work page 2018

  4. [4]

    Asai, M., and Fukunaga, A. 2018. Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary. In AAAI

    work page 2018

  5. [5]

    Asai, M.; Kajino, H.; Fukunaga, A.; and Muise, C. 2022. Classical planning in deep latent space. Journal of Artificial Intelligence Research 74:1599--1686

    work page 2022

  6. [6]

    Bachor, P., and Behnke, G. 2024. Learning planning domains from non-redundant fully-observed traces: Theoretical foundations and complexity analysis. In Proc. AAAI , 20028--20035

    work page 2024

  7. [7]

    Balyo, T.; Suda, M.; Chrpa, L.; S afr \'a nek, D.; Gocht, S.; Dvo r \'a k, F.; Bart \'a k, R.; and Youngblood, G. M. 2024. Planning domain model acquisition from state traces without action parameters. arXiv preprint arXiv:2402.10726

    work page Pith review arXiv 2024

  8. [8]

    Behnke, G., and Bercher, P. 2024. Envisioning a domain learning track for the ipc. In Proc. ICAPS Workshop on the International Planning Competition

    work page 2024

Show all 36 references
  1. [9]

    Bonet, B., and Geffner, H. 2020. Learning first-order symbolic representations for planning from the structure of the state space. In Proc. ECAI

    2020

  2. [10]

    Brafman, R., and Tennenholtz, M. 2003. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. The Journal of Machine Learning Research 3:213--231

    2003

  3. [11]

    Burchi, M., and Timofte, R. 2025. Learning transformer-based world models with contrastive predictive coding. In Proc. Int. Conf. on Learning Representations (ICLR)

    2025

  4. [12]

    Callanan, E.; De Venezia, R.; Armstrong, V.; Paredes, A.; Kang, J.; Chakraborti, T.; and Muise, C. 2022. Macq: A unified library for action model acquisition. In Proc. ICAPS (Demonstrations)

    2022

  5. [13]

    Cresswell, S., and Gregory, P. 2011. Generalised domain model acquisition from action traces. Proc. ICAPS 42--49

    2011

  6. [14]

    N.; McCluskey, T

    Cresswell, S. N.; McCluskey, T. L.; and West, M. M. 2013. Acquiring planning domain models using locm. The Knowledge Engineering Review 28(2):195--213

    2013

  7. [15]

    Diuk, C.; Cohen, A.; and Littman, M. L. 2008. An object-oriented representation for efficient reinforcement learning. In Proceedings of the 25th international conference on Machine learning , 240--247

    2008

  8. [16]

    Geffner, H., and Bonet, B. 2013. A Concise Introduction to Models and Methods for Automated Planning . Morgan & Claypool Publishers

    2013

  9. [17]

    Ghallab, M.; Nau, D.; and Traverso, P. 2016. Automated planning and acting . Cambridge U.P

    2016

  10. [18]

    G \"o sgens, J.; Jansen, N.; and Geffner, H. 2024. Learning lifted strips models from action traces alone: A simple, general, and scalable solution. arXiv preprint arXiv:2411.14995

    2024 arXiv

  11. [19]

    Gregory, P., and Cresswell, S. 2015. Domain model acquisition in the presence of static relations in the lop system. In Proc. ICAPS , volume 25, 97--105

    2015

  12. [20]

    Hafner, D.; Lillicrap, T.; Norouzi, M.; and Ba, J. 2021. Mastering atari with discrete world models. In Proc. Int. Conf. on Learning Representations (ICLR)

    2021

  13. [21]

    Haslum, P.; Lipovetzky, N.; Magazzeni, D.; and Muise, C. 2019. An Introduction to the Planning Domain Definition Language . Morgan & Claypool

    2019

  14. [22]

    Jansen, N., and Gösgens, J. 2025. Synth implementation used for the experiments. https://doi.org/10.5281/zenodo.16792702

    2025 doi

  15. [23]

    Lamanna, L.; Saetti, A.; Serafini, L.; Gerevini, A.; Traverso, P.; et al. 2021. Online learning of action models for pddl planning. In IJCAI , 4112--4118

    2021

  16. [24]

    E.; and Traverso, P

    Lamanna, L.; Serafini, L.; Saetti, A.; Gerevini, A. E.; and Traverso, P. 2025. Lifted action models learning from partial traces. Artificial Intelligence 339

    2025

  17. [25]

    S.; Juba, B.; and Stern, R

    Le, H. S.; Juba, B.; and Stern, R. 2024. Learning safe action models with partial observability. In Proc. AAAI , 20159--20167

    2024

  18. [26]

    Lindsay, A. 2021. Reuniting the locm family: An alternative method for identifying static relationships. In Proc. ICAPS 2021 KEPS Workshop

    2021

  19. [27]

    McDermott, D.; Ghallab, M.; Howe, A.; Knoblock, C.; Ram, A.; Veloso, M.; Weld, D.; and Wilkins, D. 1998. PDDL -- T he P lanning D omain D efinition L anguage. Technical Report CVC TR-98-003/DCS TR-1165, Yale Center for Computational Vision and Control, New Haven, CT

    1998

  20. [28]

    Micheli, V.; Alonso, E.; and Fleuret, F. 2023. Transformers are sample-efficient world models. In Int. Conf. on Learning Representations (ICLR)

    2023

  21. [29]

    P.; and Steedman, M

    Mour \ a o, K.; Zettlemoyer, L.; Petrick, R. P.; and Steedman, M. 2012. Learning strips operators from noisy and incomplete observations. In Proc. UAI , 614--623

    2012

  22. [30]

    D.; Bonet, B.; Romero, J.; and Geffner, H

    Rodriguez, I. D.; Bonet, B.; Romero, J.; and Geffner, H. 2021. Learning first-order representations for planning from black box states: New results. In Proc. KR , 539--548

    2021

  23. [31]

    S., and Barto, A

    Sutton, R. S., and Barto, A. 2018. Reinforcement learning: an introduction . The MIT Press. 2nd edition

    2018

  24. [32]

    R.; and Srivastava, S

    Verma, P.; Marpally, S. R.; and Srivastava, S. 2021. Asking the right questions: Learning interpretable action models through query answering. In Proc. AAAI , 12024--12033

    2021

  25. [33]

    Xi, K.; Gould, S.; and Thi \'e baux, S. 2024. Neuro-symbolic learning of lifted action models from visual traces. In Proceedings of the International Conference on Automated Planning and Scheduling , volume 34, 653--662

    2024

  26. [34]

    Yang, Q.; Wu, K.; and Jiang, Y. 2007. Learning action models from plan examples using weighted max-sat. Artificial Intelligence 171(2-3):107--143

    2007

  27. [35]

    S.; Pasula, H.; and Kaelbling, L

    Zettlemoyer, L. S.; Pasula, H.; and Kaelbling, L. P. 2005. Learning planning rules in noisy stochastic worlds. In AAAI , 911--918

    2005

  28. [36]

    H., and Kambhampati, S

    Zhuo, H. H., and Kambhampati, S. 2013. Action-model acquisition from noisy plan traces. In Proc. IJCAI

    2013

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.