acceptodds
Under review as a conference paper at ICLR 2027

Learning What’s Missing: Failure-Driven Skill Discovery via Predicate Bridges

Abstract

Agents deployed in new environments often fail not because they plan incorrectly, but because they lack the skills required to execute their plans. Some tasks can be solved with existing primitives, while others expose missing capabilities that must be acquired on demand. However, current approaches largely sidestep this problem: planners assume a fixed skill library, and skill discovery methods add behaviors without linking them to the cause of failure. We propose \bf Predicate Bridge Discovery (PBD), a framework that \it treats failure as supervision for learning missing skills. Given an instruction, the agent constructs a predicate program and performs bidirectional reasoning. Forward reasoning estimates which predicates are executable from the current state, while backward reasoning identifies which predicates are required for success. When these sets do not connect, their mismatch reveals a bridge gap—the minimal predicate that blocks execution. PBD learns directly from this gap. It turns the missing predicate into a parameterized skill, and adds it to the library only after it reliably achieves its effect across instances. This yields a compact, executable, and reusable skill set that grows as new failures are encountered. We evaluate PBD on BabyAI and MiniHack, spanning tasks from single-step behaviors to compositional problems that require acquiring new skills. PBD consistently converts failures into targeted skill acquisition and improves generalization to unseen bindings and tasks. These results show how agents can not only act, but identify and learn what they are missing.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Compositional Generalization, Skill Discovery, Neuro-Symbolic Planning, Hierarchical Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_8K4YOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The high-level idea is to use planning failures to motivate new skill-learning problems, in order to learn to connect a set of achievable fluents up to fluents that are crucial for achievement of the goal. This idea of spawning RL subproblems based on detected gaps in the domain is a good one.

The actual use case is kind of unclear. We're in the middle of planning for some goal, we find we can't achieve it, and then we stop to do some RL? That might be hard to motivate in any kind of real situation.

Critical strengths

The most high-level motivation is good: we really do need a way to assemble a skill library that "covers" a subdomain, and a good way to do it is by noticing and filling gaps.

Critical weaknesses

At the beginning of section 2, the paper says that when an agent fails on a task, either the existing skills may have been composed incorrectly or a capability is missing from the library. First, it's important to distinguish planning failure from execution failure. For planning failure, it might also be that the goal is infeasible, or that there has been an error in perception (that makes the goal seem infeasible). I understand most of the paper is focused on acquiring missing operators; but do you have a way of thinking about when the LLM producing the plan might have been wrong?

It would be important to also incentivize the RL problem to not make any other fluents (or at least any other fluents needed for this goal) go false.

N is in general not a set: when there are multiple ways of making a particular fluent true, it will be a general Boolean formula (without negation).

It seems like it might take very very careful curriculum design (that almost knows what the operator set needs to be) in order to be sure each new bridge problem is small and it's completely clear what needs to be learned.

Minor

  • In typical work on logic and symbolic planning, "predicate" means the name of the relation (like "On") and we use "fluent" or "atom" or "literal" to mean that relation applied to arguments (like "On(X,Y)" or "On(b1, b3)")
  • "Aeronautiques et al" is not a correct citation: the first author is Malik Ghallab, whose institution is Malik Ghallab Ecole Nationale Superieure D'ingenieur des Constructions Aeronautiques
  • "can only fail when Gis nonempty" is ambiguous; do you mean "has no other option but to fail..."?
  • What is an "environment-level checker"?
  • \vee means that both (not several) predicates must hold
Questions for authors

Exactly how do you identify "reachable support conditions"? It seems to me that there could be a huge reachable set, most of which is irrelevant for this new operator, making it end up being much too narrow.

During learning, how do you pick the set of bindings of the variables? How do you set up a reasonable set of initial states?

Do you tell the LLM what skills you do have, so that it tries to find a plan that works with those skills? There's a risk that it finds a plan with a gap in a case that you actually have the skills necessary for a different plan to accomplish the same goal.

3 comments

We thank the reviewer for the comments and questions.

1. Precondition construction (Q1)

For the selected bridge, we take the nearest preceding subformula under SEQ, retain its atomic predicates belonging to RR, and form their conjunction as the support conditions. After removing duplicates, we prune an atom only if removing it from a copy of RR leaves the unchanged predecessor formula satisfied. Concrete objects are generalized using consistent typed variables across supports and target.

2. Learning setup(Q2&W2)

Initial-state preparation. Bindings match the template's types and binding constraints. The preceding sequence of existing skills can bring the agent to a state where the candidate's preconditions hold (Appendix D.5). For each binding, rollout initialization prepares and checks the starting state. The bridge policy starts only when all preconditions hold and the target is false; failed preparations are resampled.

Reward and preservation. The reward targets bridge achievement with a step penalty. Initiation conditions may be consumed after use. In our formal guarantee, preparation/restoration calls must preserve conditions already established for the pending call. Execution updates the actual state; available executable skills can restore conditions. Target-predicate validation measures the selected effect's success rate.

3. LLM input (Q3)

The LLM receives the instruction, predicate vocabulary, domain guidance, and grounded environment state, but not the current skill library. PBD subsequently uses the executable library to check whether the program’s required predicates can be achieved by composing existing skills.

Alternative routes. Gap diagnosis is relative to the supplied program. A different route can solve one task while leaving a required capability absent. We acquire that capability to support subsequent programs that require it.

4. Program validation and refinement (W1)

To reduce predicate-program generation errors, our implementation applies two stages of program checking and refinement:

  1. Before execution, each generated program is checked for syntax, predicate names and arities, argument format, and object grounding.
  2. During execution, if reachability checks reveal a program-level error, we send the current program, observed state, and diagnostics to the LLM for correction, with at most three attempts (Appendix E).

Gap diagnosis assumes a feasible program and correctly grounded state. Execution failures of existing policies are recorded separately. Infeasible goals or incorrect grounding require correcting the task or state description.

5. Curriculum ablation (W4)

Table 3 (Sec. 4.4) compares acquisition with and without curriculum.

Setup. PBD-direct performs discovery and training inside the target compositional environments, while PBD-curr trains bridge skills in simpler acquisition environments before reuse.

MethodMiniBossLevelSynthSeqBossLevelWoD-HardQuest-Easy
PBD-direct0.460.400.411.000.69
PBD-curr0.780.730.671.000.69

PBD-direct performs worse than PBD-curr on BabyAI but matches it on both MiniHack tasks. Thus, curriculum can improve performance, but is not required for PBD to discover and learn missing skills in these tasks.

6. Why NN Is a Set (W3)

Backward reasoning selects an operator-support explanation for the current program requirements. NN collects the ground atoms in this selected explanation; conjunctions and temporal dependencies remain in the program and support structure. G=N∖RG=N\setminus R identifies unsupported requirements of that explanation. Other explanations may use other operators and induce different requirements; NN does not represent all alternatives simultaneously.

7. Minor Comments

(1) Terminology. We use “grounded predicate” to mean a ground atom: a predicate applied to concrete object arguments. Accordingly, the elements of RR and NN are ground atoms.

(2) Author name correction. The incorrect author attribution resulted from a metadata parsing error in Google Scholar. We have corrected the bibliography entry.

(3) Failure wording. The intended statement is: for the supplied program, a nonempty gap identifies a required ground atom that is unreachable under the current symbolic skill model. This statement concerns unsupported program requirements, rather than all possible causes of execution failure.

(4) Environment-level checker. This is the domain-specific function reading predicate truth values from envirnoment state, as described in the symbolic grounding in Appendix D.2.

(5) Logical connective. Our program grammar uses ∧\wedge for conjunction. In ψ1∧ψ2\psi_1\wedge\psi_2, both subformulas must hold.

Unfortunately, the rebuttal is very densely written and I couldn't decode from it an answer to my most pressing question, which is what would an actual use case in the actual world be?

Given that, the paper doesn't seem acceptable to me.

Thank you for the follow-up.

In the real-world use case, a deployed agent can use PBD to identify which skill to learn when a new task fails. The agent may successfully carry out much of the task with its existing skills, then get stuck at a point where further progress depends on a capability it has yet to learn. With PBD, the agent can identify the requirement its current skills cannot satisfy and use that bridge gap to define what the new skill should achieve.

During routine operation, the agent can record the gap when the task fails. It can pause a training task later, during its next scheduled update, to learn the missing skill. Once it validates that the new skill reliably achieves the required condition, the agent can add it to its library. It can then combine the new skill with existing ones to retry the original task or tackle other tasks that require the same capability. Over successive updates, the agent can use failures encountered in practice to expand its skill library.

Reviewer_GyBvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Predicate Bridge Discovery (PBD), a framework for acquiring missing skills to solve language-specified tasks. An LLM converts instructions into structured programs using a predefined predicate vocabulary. The system compares forward reachability using the skill library with backward requirements derived from symbolic operators, using their mismatch to select a missing predicate as a skill-learning target. A policy is then trained with reinforcement learning to achieve this predicate, and the skill library incorporates the learned skill to allow composition. Experiments on BabyAI and MiniHack evaluate skill acquisition, reuse, and complete-task success, reporting improvements over baseline methods.

Critical strengths
  • The paper proposes an interesting way of using symbolic models for skill discovery. The bridge predicate both identifies a gap at the symbolic level and provides a training objective for the low-level skill.
  • I like the design of iteratively expanding the skill set and including empirical skill success rates in the formulation, which leaves room for probabilistic planning as a natural follow-up.
  • The empirical experiments, including baseline comparisons and ablation studies, are comprehensive within the selected domains.
Critical weaknesses
  • I have the following concerns regarding the methodology:
    • The described forward closure appears to use delete-relaxed reachability. However, individual predicates in R may be reachable without the conjunctions being jointly achievable. Consequently, calculating G=N \ R may miss a missing capability or select an inappropriate bridge when delete effects exist. I thus think it’s quite dependent on the design of other operators and predicates specific to an environment. A formal proof establishing the validity of bridge selection under clearly stated assumptions, particularly regarding delete effects, would address this concern.
    • The term “reachable support conditions” is not precisely defined, and it is unclear how the method obtains sufficiently diverse symbolic states for precondition learning. Replaying recorded prefix skills (Appendix D.5) may produce similar initiation states. Although different bindings are sampled, this does not necessarily establish diversity in the relevant predicate configurations, and it is unclear whether prefixes from different programs are used to train the same skill.
    • Following the previous point, if spurious preconditions are not filtered out, the resulting initiation region for RL may be unnecessarily restrictive.
    • The handling of multiple effects is unclear. Although the formal operator definition allows multiple effects, the learning and validation objectives focus on one bridge predicate at a time. How are additional positive and delete effects represented and validated for subsequent composition? Could a conjunction of intended effects serve as the training objective, or is the single-predicate choice related to the construction of GG, whose predicates may correspond to different operators?
    • The assumptions and limitations of the formulation should be stated more explicitly, particularly regarding conditional and delete effects.
  • The evaluation is limited to gridworld-based environments. Related work has explored Minecraft [3], ALFRED [1], continuous-control environments [2], and simulated robotic locomotion and manipulation [4]. More challenging environments with richer interacting effects would help establish whether the system remains effective with larger symbolic state spaces and when calculating G = N \ R, and training skills with the top bridge predicate in G one at a time.
  • Missing technical details hinder my understanding of the paper. The biggest question I have is how the system plans with the operators for skill composition: I guess it uses PDDL-like planning because of the learned operators and the predicate-based symbolic state space, but I cannot be sure. Moreover, the missing details on how preconditions are learned for the learned skills are also critical, since data coverage must be ensured to prune redundant preconditions.

Refs:

  • [1] Language-guided Skill Learning with Temporal Variational Inference
  • [2] Skill Discovery for Exploration and Planning using Deep Skill Graphs
  • [3] Voyager: An Open-Ended Embodied Agent with Large Language Models
  • [4] Language Guided Skill Discovery
Questions for authors
  • How are the program and symbolic operators used to plan and compose skills? How does this planning procedure account for delete effects?
  • How does (G=N∖RG=N \setminus R) handle delete effects? How are skill preconditions derived and redundant conditions removed?
  • Does the system handle operators with multiple effects, including effects beyond the selected bridge predicate?
  • How are object bindings represented in the RL policy? Is one policy learned per skill and conditioned on the bindings? What are the network’s input and output spaces?
2 comments

We thank the reviewer for the feedback. We clarify the methodology and address your concerns and questions below.

1. Planning and Skill Composition (Q1)

The LLM-generated program specifies the subgoals, their order, and which conditions must hold together. Each skill in the library has a symbolic operator (preconditions → effects) linked to its executable policy.

Forward reasoning computes reachable predicates and records their producing skills and object bindings. Backward reasoning identifies the requirements of the next unfinished subgoal. When no gap is found, PBD traces the dependencies to construct and execute an ordered skill sequence. This uses our PBD planner, with no external PDDL solver. Reasoning resumes from the updated state when execution returns; a gap initiates bridge-skill acquisition.

2. Delete effects and formal guarantees (Q1&Q2)

Scope and delete effects. Assume accurate operators with positive preconditions, unconditional add/delete effects, and RR computed to a fixed point. For requirements in RR, consider their first recorded producers and recursively their prerequisites. Set aside initially true facts preserved by all calls. The other prerequisites admit this ordering: once the first condition holds, each subsequent one has an existing library skill requiring only established conditions and invariant facts, establishing the next condition, and preserving the earlier ones. The joint stage goal obeys the same rule. Conditions may be consumed after use or restored before later use; reasoning resumes from the updated state.

Guarantee and proof. Under this structure, Q⊆RQ\subseteq R iff the current library can jointly establish the stage requirements QQ. Necessity: s0⊆Rs_0\subseteq R, and closure includes every applicable operator's add effects, so (s∖del⁡(o))∪add⁡(o)⊆R(s\setminus\operatorname{del}(o))\cup\operatorname{add}(o)\subseteq R whenever pre⁡(o)⊆s⊆R\operatorname{pre}(o)\subseteq s\subseteq R. Induction covers all executable sequences. For sufficiency, induct on the recorded order in which predicates first enter RR. Initial facts already hold; a producer requiring only invariant facts is immediately callable. Otherwise, its first prerequisite was recorded earlier and is achievable by induction. The specified preparation skills then establish the remaining prerequisites: each is callable from the established conditions and preserves them. The producer therefore executes with all prerequisites jointly true. Apply the same construction to QQ; invariant-only goals already hold. Thus p∈G=N∖Rp\in G=N\setminus R is unsupported by the modeled library, and an empty gap admits a supporting composition within this scope.

3. Precondition construction (Q2)

For the selected bridge, we take the nearest preceding subformula under SEQ, retain its atomic predicates belonging to RR, and form their conjunction as the support conditions. After removing duplicates, we prune an atom only if removing it from a copy of RR leaves the unchanged predecessor formula satisfied. Concrete objects are generalized using consistent typed variables across supports and target.

4. Multi-effect handling (Q3)

Each new skill registers its validated bridge predicate as its learned effect. Other observed positive/delete changes enter the updated state. The operator format permits multiple effects; additional guarantees require corresponding model or validation support. Conjunctive training is a possible extension, outside the reported single-target protocol. Predicates in GG can arise from different operators or stages, so they need not form one skill's joint effect.

5. Skill learning and policy inputs (Q4)

Initial-state preparation. Bindings match the template's types and binding constraints. The preceding sequence of existing skills can bring the agent to a state where the candidate's preconditions hold (Appendix D.5). For each binding, rollout initialization prepares and checks the starting state. The bridge policy starts only when all preconditions hold and the target is false; failed preparations are resampled.

One shared policy. Instances share the same skill template and differ in their object bindings. Each sample retains its binding and target, while all samples jointly update one binding-conditioned policy for the skill. The binding vector encodes the bound objects' attributes and relevant target information.

Network inputs and outputs. The policy takes observation history, agent status, and an object-binding vector as input and outputs action probabilities and a scalar value estimate.

6. Evaluation scope

Our evaluation covers discrete skill acquisition in BabyAI and MiniHack, including object dependencies, inventory changes, tool use, hazards, and combat. Application elsewhere requires appropriate predicate grounding and skill interfaces; our empirical conclusions concern these two benchmarks.

I thank the authors for their rebuttal. Their response addresses Q4 and clarifies how PBD constructs preconditions and handles additional effects. However, my main concerns about skill composition remain.

Even in a discrete domain, a skill can achieve its target while making another predicate false. PBD observes these changes after execution, but each learned skill registers only its target predicate as an effect. It remains unclear how reliably the planner can construct an executable sequence when one skill undoes a condition needed later. I also remain concerned that deriving a skill’s preconditions from the preceding stage of a single program can retain conditions that the skill does not require. One way to reduce spurious preconditions might be to use multiple programs in which the same skill succeeds and, after lifting their object bindings, take the intersection of the predicates supporting the skill in those programs.

For a future submission, I encourage the authors to explore domains where these interactions make skill composition more challenging. I am not requesting additional experiments for the current submission. The paper would also be clearer if it included the policy details from the response to Q4 and pseudocode showing how the PBD planner uses skill preconditions and effects to construct an executable sequence from the LLM-generated program.

I find the use of bridge predicates to identify and train missing skills interesting. Given my remaining concerns about composition and the limited scope of the evaluation, I will maintain my score.

Reviewer_ngvHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Predicate Bridge Discovery uses predefined conditions and language-model-generated plans to identify missing skills. It learns and tests these skills across different instances before adding them to its library. BabyAI and MiniHack experiments report improved success on tasks combining multiple skills and examine skill reuse, training choices, and errors in state information.

Critical strengths

The overall pipeline improves compositional task success across both benchmarks, with PBD outperforming the reported baselines on all five compositional tasks. Good empirical support for the method's practical effectiveness.

I liked to see that success increases as the skill library grows, and execution records show previously learned skills being used again. Because the library is frozen during evaluation, these results support reuse across new task instances (Tables 4-5; Figures 4,7).

Critical weaknesses

Insufficient evidence: the experiments do not clearly establish the benefit of bidirectional reasoning. The direct comparison with a simpler selector covers only one MiniHack setting (Table 7). Other comparisons differ in planning support, demonstrations, and training setup, making it difficult to determine how much improvement comes from the proposed discovery mechanism.

L156-161: Backward reasoning requires operators describing skills that have not yet been learned, but how these operators are obtained is not sufficiently explained. The planner prompts also provide substantial task guidance (Appendix E), making unclear how much of the diagnosis is supplied in advance.

Questions for authors

Can PBD reliably distinguish a missing skill from an incorrect plan? How does it handle conflicting conditions, actions that undo earlier conditions, or alternative ways to reach the goal?

Could you compare PBD with simpler rules for choosing which skill to learn, using the same planner, predicate checker, demonstrations, training starting states, and budget across the main tasks? This would clarify the benefit of the bidirectional reasoning.

Which domain knowledge, complete state information, and task guidance are provided to PBD, and do the baselines receive the same information?

2 comments

Thank you for reviewing our work. We address the concerns below.

1. Program checking and missing-skill diagnosis (Q1)

Incorrect plans and conflicting conditions. We check generated programs in two stages: (1) before execution, we validate syntax, predicate names and arities, argument format, and object grounding; (2) during execution, if reachability checks reveal a program-level error, we send the current program, observed state, and diagnostics to the LLM for correction, with at most three attempts (Appendix E). Conflicting conditions required at the same stage also indicate that the program needs correction. PBD's missing-skill diagnosis assumes a valid program and correctly grounded state.

Delete effects. PBD updates the actual state after each skill and repeats reasoning when the sequence returns. Executable sequences of existing skills can restore still-required conditions. A required condition outside the recomputed RR exposes a new bridge-learning target. Stage completion checks that all active conditions hold jointly in the observed state.

Alternative routes. PBD expands a reusable library to support the supplied program. A different route may solve one task while leaving this program's required capability missing. Learning it increases library coverage for subsequent programs that need it.

2. Selection comparison (Q2&W1)

Setup. We extend the controlled WoD comparison (Table 7) to one archived state each from BabyAI BossLevel and MiniBossLevel. WoD requires picking up a wand before attacking; BabyAI requires dropping the held object before picking up another.PBD uses bidirectional reasoning to select a missing prerequisite, whereas frontier-only directly selects the unsupported active-frontier predicate. Only the selector changes; the initial library, starting state, and all planning, training, and validation settings are fixed.

SettingSelectorSelected BridgeTarget Predicate Validation SR
MiniHack-WoDPBDInInventory(wand)93.1%
MiniHack-WoDFrontier-onlyMonsterDead(Minotaur)0.0%
BabyAI-BossLevelPBDHandEmpty()100%
BabyAI-BossLevelFrontier-onlyHoldingObj(ball)1.0%
BabyAI-MiniBossLevelPBDHandEmpty()100%
BabyAI-MiniBossLevelFrontier-onlyHoldingObj(ball)9.4%

Validation SR is measured over successfully initialized rollouts. Each BabyAI row aggregates 32 rollouts per training seed across three seeds.

Takeaway. Across these controlled settings, bidirectional reasoning identifies what to learn first: it traces the blocked subgoal back to the missing enabling skill, yielding substantially higher validation success than directly training the downstream frontier target.

3. Information Provided to PBD and the Baselines (Q3)

PBD's inputs. The program generator receives the instruction, initial map/state, predicate definitions, program grammar, and examples (Appendix E). The domain-specific checker supplies grounded predicate facts (Appendix D.2). These inputs describe the task; PBD determines the missing capability from the current state and skill library.

Baseline inputs. Voyager receives instructions, environment observations, API guidance, retrieved skills, and execution/critic feedback. It uses the same ordered curriculum and frozen-library evaluation as PBD, while generating its own subgoals and executable code. IL/RL use benchmark observations with demonstrations/rewards; HRL receives symbolic state features and the same frozen executable library.

4. Operator descriptions and task guidance (W2)

OO contains symbolic operator descriptions; KK contains validated executable skills. In the implementation, backward reasoning reads current library interfaces, while the program supplies requirements that may lack an executable skill. A new candidate interface is constructed from its program-derived supports and selected bridge effect, then paired with a policy admitted after validation. This explains how a symbolic transition can be specified before its policy exists. The prompt does not label which capability is missing from the current library.

Thanks for the additional comparisons and implementation details.

The comparisons use one archived starting state per environment and measure predicate-validation success. Their implications for full-task performance across the main benchmarks remain less clear. Any available matched full-task results would help clarify this contribution.

Some example tracing the program, operator preconditions, reachable predicates, and selected bridge would also help distinguish supplied domain knowledge from information inferred by PBD, and clarify which guidance is shared with the baselines.

The responses clarify that diagnosis is relative to the supplied program and that the formal guarantee requires strong assumptions. The manuscript should state this scope explicitly and clarify whether those assumptions are checked for learned skills or assumed when interpreting the results.

I will retain my weak reject recommendation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.