Generalized Plans That Know Only What They Must: Certifying Policies Under Unknown Causal Structure

Generalized planning is the problem of finding one compact strategy that solves every instance of a task family, no matter how many objects it contains. A blocks-world policy such as "pick a clear block above the target and put it on the table" works for 5 blocks or 500. Current methods find such policies from tiny training instances and then prove them correct. They all assume something strong, though: a complete and correct description of what every action does. When that description must be learned from logs of someone else acting, it inherits the problem causal inference has always faced. Logs show correlation, not cause. A hidden variable that influenced both the demonstrator's choice and the outcome can make an action look as if it has effects it does not have. A planner built on that mistaken model can produce a policy that loops forever or never reaches the goal.

This proposal starts from an observation that makes the problem tractable. A generalized policy's correctness proof uses very little of the causal structure. It needs only the direction in which each action schema moves each of a handful of policy features: up, down, or not at all. The proof never needs the full causal graph. We propose to identify exactly those signs from observational logs, at the level of object types so that the answer carries over to any instance size. Signs that the data cannot determine become nondeterministic effects. Existing termination machinery for generalized planning already handles nondeterminism soundly. When no policy survives the remaining ambiguity, the method requests the smallest set of targeted experiments that would make one exist.

Core Claim

Correctness of a feature-based generalized policy depends on a small set of type-level causal queries. Each query asks whether action schema $a$, applied in context $c$, increases, decreases, or leaves unchanged feature $f$:

$$\sigma(a,f,c) = \operatorname{sign}\, \mathbb{E}\left[f_{t+1} - f_t \mid do(a_t), c_t\right],$$

where $f_t$ is the feature value at step $t$, $do(a_t)$ means the action is forced rather than chosen, and $c_t$ is the set of boolean features under which the policy rule fires. We claim three things. First, these sign queries can be identified, or certified as unidentifiable, over the whole class of causal structures consistent with the logs, without enumerating that class. Second, any sign left ambiguous can be compiled into a nondeterministic qualitative effect, which gives a qualitative numeric planning problem. That problem is solved soundly through its known equivalence to fully observable non-deterministic planning, as shown in Qualitative Numeric Planning: Reductions and Complexity. Third, because the queries are asked of object types rather than individual objects, a certificate obtained on small logged instances transfers to arbitrarily large ones under the type-level mechanism assumption formalized in Relational Structural Causal Models.

The method returns either a policy whose correctness holds in every causal structure consistent with the data, or a minimal list of interventions whose results would make such a policy exist.

Relation to Prior Work

Three generalized planners supply the policy side, and all three assume the action model is given. D2L (Learning General Planning Policies from Small Examples Without Supervision) generates features from description-logic grammars and selects a policy by weighted Max-SAT, with cycle-freeness and distance-to-goal constraints. LOOM (Generalized Planning via Abstraction: Arbitrary Numbers of Objects) abstracts object identity with quantifiers and solves the result as nondeterministic planning. Canonical abstraction (Using Abstraction for Generalized Planning) groups objects into roles and uses three-valued logic. We reuse D2L's feature grammar and Max-SAT search as the method, and the qualitative numeric planning reduction as the soundness tool. What we change is the input: a partially identified effect table instead of a complete action model. The "maybe" truth value of canonical abstraction is the closest analogue to our unknown signs. Canonical abstraction uses "maybe" for summarized objects, whereas we use it for unidentified causal effects.

Three causal-inference papers motivate the approach and supply its identification machinery, and all three are limited to single-step decisions over a fixed set of variables. Do-calculus when the True Graph Is Unknown runs causal discovery, encodes the resulting independence constraints in answer set programming, and checks whether an effect is identified across the equivalence class without listing every graph. We reuse that solver loop. We change the target query: a sign under a context rather than a full distribution. A sign is often determined even when the distribution is not, for example when every graph in the class gives a nonnegative effect. Structural Causal Bandits under Markov Equivalence prunes the actions worth trying under an unknown graph, cutting a 10-variable problem from about 20,000 arms to 54. That paper is our model for asking only the structurally necessary questions. We extend the idea from a single choice to looping, multi-step policies. Relational Structural Causal Models defines mechanisms at the type level and gives conditions under which causal knowledge transfers across object counts. However, it assumes an expert supplies the type-level graph and it addresses only prediction. We learn that graph up to equivalence and use it for planning.

One paper constrains the design. Causal Effect Identification in Cluster DAGs shows that coarse cluster-level graphs support identification only when the clusters form an acyclic graph. Planning domains are full of feedback between object roles, which seems to rule this out. We avoid the conflict by clustering time-indexed features, so that features at step $t$ cause features at step $t+1$. The unrolled graph is acyclic by construction even when the domain has feedback. The cost is that we need a stationarity assumption across time steps, and we state it explicitly.

Finally, Generalized Answer Set Planning with Incomplete Information handles unknown initial facts but assumes the action effects are known. Our uncertainty sits in the effects themselves.

Research Program

The pipeline has four stages.

Lifted causal discovery. From logs of a behavior policy on instances of several sizes, we build time-indexed, type-level variables. These are D2L features and their changes, together with the chosen action schema, pooled across objects of the same type. On these variables we run a discovery method that tolerates hidden confounders, Fast Causal Inference, which outputs a partial ancestral graph: a graph whose circle marks record undetermined edge directions and possible hidden common causes. The constraint-based choice is supported by CausalDynamics: A large-scale benchmark for structural discovery of dynamical causal models, which found that non-deep methods were competitive or better than deep ones on coupled systems.

Sign identification. For each (action schema, feature, context) triple the policy search might use, we run the answer-set identification loop. It asks whether every graph in the class admits an estimator and whether all the resulting estimates agree in sign. The answer is one of four outcomes: increase, decrease, no change, or unknown.

Robust synthesis. We extend D2L's Max-SAT encoding so that a rule's effect on a feature is the set of signs still possible. The termination constraint must then hold for every choice from those sets, which is exactly the qualitative numeric planning reading of a nondeterministic effect. The resulting policy is checked independently with an off-the-shelf nondeterministic planner via the known reduction.

Minimal experiments. When synthesis fails, we compute the smallest set of unknown signs that blocks every candidate policy. This is a minimal-hitting-set problem, analogous to the minimal intervention sets of the bandit work. We then run only those interventions, on small instances.

The analysis component asks when lifted signs are identified at all. We expect identification to fail when a hidden variable confounds the action choice with a feature change within the same type, and the experiments map how often this occurs.

Baselines

The naive reference point treats the logged transitions as the true action model. It estimates each effect sign from observed frequencies and runs unmodified D2L on the result. It uses the same logs, the same feature grammar, and the same Max-SAT solver and time limit as our method. We beat it if, on confounded domains, it produces policies that fail on large test instances, or that it labels correct when they are not, while ours does not.

The oracle upper bound is D2L given the ground-truth model. The paper reports synthesis in 2 seconds on Gripper, and policies learned from instances with 4 or 5 objects that solve instances with more than 30 objects (Learning General Planning Policies from Small Examples Without Supervision). On unconfounded domains we aim to match the oracle's coverage. On confounded domains we aim to close most of the gap between the naive baseline and the oracle. For LOOM's domains, the reported reference is that LOOM solved the full Construction range in under 360 seconds against more than 2400 seconds for LAMA-FIRST (Generalized Planning via Abstraction: Arbitrary Numbers of Objects). We will run LOOM with the oracle model as a second upper bound.

The strongest learned competitor is a graph neural network policy trained across instances, as in Learning Generalized Policies Without Supervision Using GNNs. It is trained on the same logs with a matched hyperparameter search budget. No reported result was found on Lacuna for this method on confounded or log-only versions of these domains. It must therefore be run fresh. Beating it means higher coverage on large instances, with a certificate that it cannot provide.

Two ablations isolate the key ingredients. The first keeps identification but replaces robust compilation with the single most likely graph in the class, which tests whether treating unknowns as nondeterminism matters. The second replaces the minimal experiment set with randomly chosen interventions of the same number, which tests whether targeting matters.

Why not just…?

Why not just learn an action model with standard action-model learning and hand it to D2L? When the state is fully observed and the logs come from an agent free of hidden influences, this works. It is exactly our naive baseline, and we expect it to tie our method there. It falls short when the demonstrator sees something the log does not. In that case observed effect frequencies mix causation with selection, which is the bias that Do-calculus when the True Graph Is Unknown shows arises without explicit checks for confounding paths. The confounded-domain experiments test whether this bias actually breaks generalized policies in practice. If it rarely does, the contribution shrinks to a certificate, and we will report that outcome.

Why not just run experiments in a simulator? If a cheap simulator of small instances exists, intervening everywhere and running D2L is simpler, and our method adds little beyond fewer interventions. Our target setting is one where only logs are available and experiments are costly. The targeted-versus-random ablation measures how much is saved. If savings are small, the honest conclusion is that interventions should simply be collected.

Why not just train a neural policy across instances? Neural policies give no termination guarantee. Relational Structural Causal Models reports that non-causal relational models had roughly 100 times higher error than causal relational ones when transferring across configurations. That result concerns prediction, not control, so the head-to-head comparison here is necessary rather than settled.

Why not just enumerate every graph in the class and plan conformantly? The number of graphs in an equivalence class grows super-exponentially with the number of variables. The bandit pruning result shows how much structure-aware reasoning saves even at 10 variables (Structural Causal Bandits under Markov Equivalence). We will run enumeration on the smallest domains to check that the two methods return the same answers and to measure the runtime gap.

Proposed Experiments

We use the D2L domains (Blocksworld with clear and on goals, Gripper, Spanner, Miconic, Visitall) and the LOOM domains (Logistics, Construction, Roundabout). For each domain we build a confounded variant by hiding one fluent that the demonstrator observes. For example, in Spanner the demonstrator can see which spanners are worn, and worn spanners fail silently. Logs come from instances with 4 to 10 objects. Test instances have 30 to 1,000 objects.

The metrics are coverage on large instances, the false-certification rate (policies certified correct that fail on some test instance), the fraction of domains certified without any experiments, the number of interventions requested, and synthesis time.

Three checks decide the outcome. First, on unconfounded variants our coverage should equal the oracle's. Second, on confounded variants the naive baseline should certify policies that fail, while ours should have zero false certifications. Third, the targeted interventions should be fewer than random ones needed for the same success rate. Failing the second check would show that confounding does not matter for generalized policies. That would itself be a useful negative answer to the question of whether inductive planners depend on unstated causal assumptions.