Agents built from language models are usually fine-tuned on one expert demonstration per task. If every demonstration of "heat a mug" fetches the mug from the same cabinet and uses the same appliance, the agent never learns that another route exists. When that cabinet is locked or that mug is missing at test time, it stalls. Classical planning has studied a remedy for this brittleness: algorithms that return a small set of plans that are both cheap enough and genuinely different from one another. So far, those plan sets are only handed to a human or an executor at decision time. We propose to use them instead as a training-data factory. A symbolic planner, run over the formal task descriptions behind a simulator, generates many valid and structurally distinct plans per task. The simulator replays them to discard plans the formal model got wrong. A policy is then trained to treat the surviving set as a bag of acceptable answers, not as k separate targets to average.
The bet is specific and falsifiable. Structural diversity in training data should matter most exactly where single-trajectory training fails: when an action or object that every expert demonstration relied on becomes unavailable. The improvement should come from what the selected plans avoid depending on, not from having more plans. A random set of k valid plans of the same size and cost should do measurably worse at recovering from blockages than a set chosen to maximize differences in the actions used.
Where the gap is
The two directions have so far touched only at their edges. Distant supervision is the practice of generating labels automatically by aligning raw data with an existing structured source. In Mintz et al., that meant pairing Freebase relations with Wikipedia sentences, which reached 67.6% precision on 10,000 extracted relations and required machinery to absorb label noise. Its modern descendant in agent training is back-annotation. CodePlan has a teacher model write a pseudocode plan between each of 2M WebInstruct prompts and their answers, and reports a 25.1% average relative gain across 13 benchmarks. It writes exactly one plan per instance, and that plan is never executed, so plan errors go uncaught.
Peng et al. constrains our design and also motivates it. They show that agents fine-tuned on teacher trajectories memorize interface strings: an Interface Reliance score of 15.5 in ALFWorld, and AgentLM-14b falling from 61.2% to 4.4% on WebShop when actions are renamed. Their remedy, training across action aliases, injects only lexical diversity. No one has tested whether diversity in which subgoals, objects, and routes a plan uses has the analogous effect on robustness to the environment itself.
On the planning side, three papers supply the method we reuse. Katz et al., Reshaping Diverse Planning introduce Forbid Iterative, which repeatedly reformulates a task to forbid the action multisets already found. With k=5 it covers 1,143 of 1,276 tasks, against 615 for the next competitor. Katz et al., Bounding Quality separate candidate generation under a cost bound from subset selection. They prove selection is NP-complete but find greedy selection near-optimal for their bounded-quality variant, running in under 1.2 seconds against hundreds for an exact integer program. Zhong et al. add beam-search selection that trades quality against diversity and gains 6.28% over greedy on minimum pairwise distance. Speck et al. motivate the whole effort: plain "k cheapest plans" mostly yields reorderings of commutative actions, so a single blocked action defeats all k.
Two systems already sample many plans with language models, but only at inference time. Tree-Planner merges N sampled plans into a prefix-sharing action tree and backtracks on failure. Yet 54.5% of its failures occur because no correct plan was sampled at all. CoPiC generates a pool of executable Python planning programs and selects among them with a 1.1B selector. Neither system turns its alternatives into training data for the base policy. The closest prior work therefore splits the idea in half. CodePlan does automated supervision with one unverified plan per task, and Peng et al. do diversity-augmented supervision with only lexical diversity. We combine verified structural diversity with automated supervision, and we evaluate it on blockage recovery, a test neither paper runs.
Core Claim
Training on a selected, simulator-verified portfolio of action-set-diverse plans per task improves a fine-tuned agent's success on test episodes where the expert's route is blocked. The gain exceeds what equally many valid but randomly chosen plans provide, and it comes at no loss on unblocked episodes. The gain also requires a training loss that treats the portfolio as a set of acceptable continuations.
Research Program
The pipeline has three stages, each mirroring a stage of classic distant supervision.
The first stage is alignment. ALFWorld's text games are generated from symbolic, PDDL-style task specifications (Shridhar et al.), so the formal domain plays the role of the knowledge base. Each training task is handed to Forbid Iterative over a cost bound of the optimal cost times $q_m$, which produces a candidate pool of action-multiset-distinct plans. We run the same pipeline in VirtualHome (Puig et al.) using its executable program representation. The second domain has more genuinely alternative ways to complete household activities, such as different furniture or appliances.
The second stage is denoising by execution. Every candidate is replayed in the simulator, and plans that fail are dropped. This is our analogue of the false positives Mintz et al. had to model statistically; here we can remove them exactly. We log the rejection rate, which measures how far the formal model is from the simulator.
The third stage is selection and training. From the verified pool we select k plans by greedy maximization of the minimum pairwise Jaccard distance over action multisets, keeping the expert plan as the anchor. We start with greedy because Katz et al. found it near-optimal for bounded-quality selection, and we test Zhong et al.'s beam search as an ablation instead of assuming it is needed. The k plans are merged into a prefix tree, borrowing Tree-Planner's structure but using it for training rather than inference. Let $h_t$ be an observation history reached along some branch of the tree, and let $A(h_t)$ be the set of next actions that continue at least one verified plan from that point. The policy $\pi$ is trained with a multiple-instance objective:
$$\mathcal{L} = -\sum_{t} \log \sum_{a \in A(h_t)} \pi(a \mid h_t),$$
This rewards putting probability on any valid continuation. Ordinary fine-tuning would push the policy toward the average of k targets that disagree at the branch points. The construction directly echoes how distant-supervision relation extractors aggregated over a bag of sentences instead of trusting each one.
To test robustness, we build blocked test splits for ALFWorld and VirtualHome. For each unseen-layout test task we disable the specific object instance or receptacle the expert plan first depends on. If the task becomes unsolvable, it is excluded; this is checked with the planner. Results are reported separately for blocked and unblocked episodes, and we also report Peng et al.'s Interface Reliance score under their PIPE renaming protocol. Policies are open 7B-scale models of the kind CodePlan fine-tuned, so model scale stays comparable across conditions.
Baselines
The naive reference point is standard trajectory fine-tuning on ALFWorld's single expert trajectory per task. We give it two budget-matched variants. One repeats the expert trajectory to match the total tokens of the k-plan condition. The other uses k times as many distinct tasks generated from the formal domain, so that the comparison isolates diversity per task from total data volume. Peng et al. report this style of training reaching IR = 15.5 in ALFWorld. The file contains no absolute ALFWorld success rate for it, so we will measure it ourselves.
The strongest data-diversity competitor is Peng et al.'s diversity-augmented training on action aliases. It is the only existing method that adds diversity to agent fine-tuning data. We run it on the same tasks and token budget, and also in combination with ours, because the two kinds of diversity could add or could be redundant. Beating it means higher success on blocked episodes at matched IR. Ours need not beat it on IR, since it targets renaming directly.
The strongest inference-time competitor is CoPiC, which reports an average 19.14% success-rate improvement over AdaPlanner and Reflexion on ALFWorld, together with a 79.39% reduction in token cost. We run it with its published frontier generator and also report our policy with and without Tree-Planner-style backtracking. Our claim is not that a fine-tuned 7B policy beats a frontier-model program search in absolute success. The claim is that it closes a meaningful part of the gap on blocked episodes at a small fraction of the inference cost. We will report both success and tokens per episode so readers can judge the trade.
Three ablations isolate the key ingredients. The first is the random-k ablation: k plans drawn uniformly from the same verified pool, with matched cost distribution. The second replaces our generator with a top-k planner, which yields reorderings in the sense of Speck et al. The third trains on the same portfolio with per-trajectory cross-entropy instead of the set objective. Every condition gets the same number of gradient steps, the same learning-rate sweep of four values selected on an unblocked validation split, and three seeds.
Why not just…?
Why not just sample many plans from a language model at high temperature and keep the ones that execute? This is the most serious alternative, and it may work. Tree-Planner's 54.5% missing-correct-plan rate shows that unguided sampling often fails to find a valid plan at all, and nothing makes the plans it does find avoid the same objects. Still, rejection sampling followed by our selection step is a legitimate generator. We include it as a condition: a sampled pool of the same size, verified and then greedily selected. If it matches the planner-generated pool, the conclusion is that the selection criterion and set objective carry the effect while the symbolic planner is merely convenient. We would report that and recommend the language-model generator for domains without a formal model.
Why not just use a top-k planner? Speck et al. show that its plans mostly permute commutative actions, so every plan depends on the same objects and a single blockage defeats them all. Our top-k ablation tests the prediction directly. It should match random-k or single-plan training on blocked episodes, while the action-set-diverse portfolio should not.
Why not just add more single-expert tasks? If the benefit came only from data volume, the k-times-more-tasks baseline would equal our method. It might well do so on unblocked episodes, which is why we split the evaluation. Our prediction is that it does not on blocked episodes, because no amount of single-route data shows the policy an alternative route for the same goal.
Why not just use greedy selection and skip the selection question? We agree, and greedy is our default because of Katz et al.'s near-optimality result. Beam search appears only as an ablation. If it brings no gain in downstream success, we drop it.
Decisive Checks
The idea fails if, on the blocked splits, the diverse portfolio does not beat the random-k ablation with matched size and cost by more than seed variance. In that case diversity per se is not doing the work. Among the blocked episodes, the gain should also concentrate in those whose disabled object or receptacle is avoided by at least one training plan for related tasks. We will test this by regressing per-episode recovery on that coverage indicator. If the gain is uniform rather than concentrated, the mechanism is something other than learned alternative routes. Finally, the set objective must beat per-trajectory cross-entropy on the same portfolio. If it does not, the multiple-instance framing is unnecessary and the contribution reduces to a data-selection recipe. That would still be worth reporting, but it would be a smaller claim than the one made here.
References
- Distant supervision for relation extraction without labeled data
- CodePlan: Unlocking Reasoning Potential in Large Language Models by Scaling Code-form Planning
- What Do Agents Learn from Trajectory-SFT: Semantics or Interfaces?
- Reshaping Diverse Planning
- Bounding Quality in Diverse Planning
- Bi-Criteria Diverse Plan Selection via Beam Search Approximation
- Symbolic Top-k Planning
- Tree-Planner: Efficient Close-loop Task Planning with Large Language Models
- Code Driven Planning with Domain-Adaptive Selector
- ALFWorld: Aligning Text and Embodied Environments for Interactive Learning
- VirtualHome: Simulating Household Activities via Programs