🤖 AI

Learning Bilevel Policies over Symbolic World Models for Long-Horizon Planning

The paper introduces BISON, a system that combines low-level neural imitation learning with high-level symbolic abstractions to create bilevel policies capable of efficiently solving long-horizon planning tasks with large numbers of objects, outperforming existing end-to-end methods in scalability and efficiency.

Original authors: Dillon Z. Chen, Till Hofmann, Toryn Q. Klassen, Sheila A. McIlraith

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dillon Z. Chen, Till Hofmann, Toryn Q. Klassen, Sheila A. McIlraith

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to clean a messy room. If you just show the robot a video of someone cleaning, it might learn how to pick up a specific sock or fold a specific shirt. But if you ask it to clean a room with 100 different items, or if the items move around while it's working, that simple "copycat" approach often fails. It gets overwhelmed.

This paper introduces a new way to teach robots called BISON. Think of BISON as a "Manager and Worker" system that combines the best of two different teaching styles.

The Two-Team Approach

The authors realized that robots need two different types of "brains" working together:

The Worker (Low-Level Policy): This is the muscle memory. It's like a highly skilled dancer who knows exactly how to move their arms and fingers to grab a cup without dropping it. The robot learns this by watching many videos (demonstrations) of people doing the physical tasks. In the paper, this is a neural network that handles the messy, continuous details of the real world.
The Manager (High-Level Policy): This is the strategic planner. It doesn't care about how to move the fingers; it cares about what to do next. It thinks in symbols and logic, like a chess player or a project manager. It says, "First, pick up the red block. Then, move to the table. Then, place it."

The Problem: Usually, these two don't talk well. The "Worker" is too dumb to plan a long sequence, and the "Manager" is too abstract to know how to actually move the robot's arm.

The BISON Solution: BISON teaches the Manager by looking at the Worker's past successes. It takes the messy videos of the robot moving things, translates them into a simple, symbolic story (like a comic strip), and then teaches the Manager to write a script based on that story.

How It Works: The "Recipe" Analogy

Imagine you want to teach a robot to bake a cake, but you only have videos of a human baker doing it.

Watching the Video (Low-Level Data): You record the baker mixing, pouring, and baking. This is the "Low-Level" data.
Summarizing the Story (Abstraction): BISON looks at the video and ignores the tiny details (like the exact speed of the whisk). Instead, it creates a summary: "Step 1: Mix ingredients. Step 2: Pour into pan. Step 3: Bake." This is the "High-Level" story.
Learning the Rules (Goal Regression): The system looks at the goal ("We want a cake") and works backward. It asks, "To get a cake, we needed to bake. To bake, we needed to pour." It turns this backward thinking into a set of simple "If-Then" rules.
- Rule: "IF we have batter AND an empty pan, THEN pour."
- Rule: "IF we have a pan in the oven, THEN wait."
Generalizing (The Magic Trick): This is the paper's biggest claim. Most robots fail if you give them a recipe for 1 cake and then ask them to bake 100 cakes. BISON's rules are written with "variables" (like "IF we have any batter..."). This means the Manager can handle 1 cake, 10 cakes, or even 10,000 cakes without needing new training. It's like having a recipe that says "Add flour" instead of "Add 2 cups of flour for this specific bowl."

Why It's Better Than the Competition

The paper tested BISON against other methods, including:

VLA (Vision-Language-Action) models: These are like giant AI chatbots that try to see the world and act. The paper found these struggled badly with long tasks and got confused easily.
End-to-End Neural Networks: These try to learn everything at once. They are like a student trying to memorize every single step of a 100-page book. They work okay for short tasks but fail when the task gets long or the number of objects increases.
Traditional Symbolic Planners: These are very logical but can't handle the messy, unpredictable real world (like a block falling over unexpectedly).

BISON's Wins:

Longer Tasks: It can plan much further ahead than the others.
More Objects: While other methods crashed when the number of objects went above 6 or 10, BISON handled environments with many more objects.
Speed: The "Manager" part of BISON is so efficient that, if you ignore the time it takes to actually move the robot's arm, it can solve a planning problem with 10,000 objects in under a minute. That's like planning a wedding for 10,000 guests instantly.

The "Open World" Advantage

The paper also highlights that BISON works in "open worlds." Imagine a robot in a room where new objects might appear out of nowhere, or objects might teleport.

Old methods often break because they were trained on a specific set of objects.
BISON uses its symbolic "If-Then" rules. If a new object appears, the Manager just checks: "Is there a rule for this object?" If the rule says "If there is a red block, pick it up," the robot will pick up the new red block immediately, even if it never saw that specific block before.

Summary

In simple terms, BISON is a system that teaches a robot to be both a skilled worker and a smart manager. It watches the worker do the job, summarizes the job into simple logical rules, and then uses those rules to plan ahead for tasks of any size. It's faster, smarter, and more flexible than current methods, allowing robots to handle complex, long-term goals with many moving parts without getting lost.

Technical Summary: Learning Bilevel Policies over Symbolic World Models for Long-Horizon Planning

Problem Statement

The paper addresses the challenge of building embodied AI agents capable of reliably solving long-horizon planning problems in continuous state and action spaces with varying numbers of objects. While imitation learning from demonstrations has proven effective for low-level (LL) motor control and manipulation, it struggles to generate efficient long-horizon plans. Conversely, high-level (HL) symbolic planners are effective for long-horizon reasoning but often fail to generalize to settings with varying sensory modalities, partial observability, and complex low-level dynamics.

The authors formulate the problem as learning a goal-conditioned policy $\pi(all | s_{ll}, g_{hl})$ that chooses low-level actions ( $a_{ll}$ ) to achieve high-level goals ( $g_{hl}$ ). The learning inputs consist of:

LL Demonstrations: Trajectories of states and actions paired with HL goals.
Abstraction Language ( $D$ ): A domain theory defining predicates and action schemas.
Labelling Function ( $L$ ): A mapping from LL observations to HL symbolic states.

The objective is to learn a policy that generalizes to unseen states and goals in a zero-shot manner, handling arbitrary numbers of objects and open-world conditions.

Methodology

The authors propose BISON, a system that learns bilevel policies $(\pi_{hl}, \pi_{ll})$ by combining neural imitation learning with symbolic abstraction and inductive generalization.

1. Bilevel Policy Architecture

The system decomposes the problem into two distinct policies:

High-Level (HL) Policy ( $\pi_{hl}$ ): A symbolic policy that operates on abstract states ( $s_{hl}$ ) and goals ( $g_{hl}$ ) to propose HL actions ( $a_{hl}$ ).
Low-Level (LL) Policy ( $\pi_{ll}$ ): A neural policy (Graph Neural Network) that takes the current LL state ( $s_{ll}$ ), the proposed HL action ( $a_{hl}$ ), and the goal ( $g_{hl}$ ) to output continuous LL actions ( $a_{ll}$ ).

The policies are composed such that $\pi(all | s_{ll}, g_{hl}) = \sum_{a_{hl}} \pi_{ll}(all | s_{ll}, a_{hl}, g_{hl}) \cdot \pi_{hl}(a_{hl} | L(s_{ll}), g_{hl})$ .

2. Learning the High-Level Policy ( $\pi_{hl}$ )

The HL policy is learned from LL demonstrations via a three-step process (illustrated in Figure 2):

Construct HL Traces: The labelling function $L$ is applied to LL demonstrations to extract abstract HL traces (sequences of HL states and actions).
Goal Regression: The authors apply goal regression (a pre-image rewriting technique) to these traces. This computes the minimal conditions under which an action achieves a goal. By regressing goals backward through action traces, the system extracts ground condition-action rules.
Inductive Generalisation: The ground rules are lifted to first-order logic by replacing specific objects with variables. This results in a compact set of Condition $\mapsto$ Action rules with priority values based on goal proximity. These rules are interpretable and can generalize to arbitrary numbers of objects.

The resulting HL policy is a set of first-order rules. Execution involves finding the applicable rule with the lowest priority value (highest priority) that satisfies the current state and unachieved goal conditions.

3. Learning the Low-Level Policy ( $\pi_{ll}$ )

The LL policy is implemented as a Graph Neural Network (GNN) with fewer than 33,000 parameters.

Input Encoding: The GNN encodes the LL state (agent state and object states), the HL action schema, and the HL goal facts.
Architecture: It utilizes message passing between object nodes, action nodes, and a global node to aggregate information.
Training: The GNN is trained via imitation learning (behavior cloning) on the dataset of tuples $\langle s_{ll}, a_{hl}, g_{hl}, a_{ll} \rangle$ derived from the demonstrations, minimizing the Mean Squared Error (MSE) between predicted and ground-truth actions.

4. Theoretical Guarantees

The paper establishes the Nondeterministic Downward Refinement Property (NDRP), ensuring that any solution to the HL problem can be refined into a solution for the LL problem. Furthermore, Theorem 1 proves that under conditions of C-bounded goal independence (where goal components can be achieved independently in any order with bounded policy size), the learned HL policy generalizes to problems with arbitrarily many objects and horizons.

Key Contributions

BISON System: An approach to learn bilevel policies $(\pi_{hl}, \pi_{ll})$ from LL demonstrations paired with HL goals, utilizing a domain theory and labelling function.
Symbolic HL Learning: The application of goal regression and inductive generalisation to learn compact, expressive HL policies. These policies are represented as first-order condition-action rules, enabling operation in open-world and partially observable environments and generalization to arbitrary object counts.
Efficient LL Learning: The realization of LL policies via a compact GNN (under 33k parameters) conditioned on HL actions.
Empirical Validation: Extensive experiments (21,600 episodes) on extended MetaWorld benchmarks demonstrating superior efficiency, generalization, and long-horizon planning capabilities compared to Vision-Language-Action (VLA) models, end-to-end methods, and symbolic planning baselines.

Experimental Results

The authors evaluated BISON against 8 baselines (including SmolVLA, PureNN, PddlNN, and various replanning strategies) across 8 environments with varying uncertainty (exogenous, endogenous, state uncertainty).

Generalization: BISON successfully generalized to environments with more objects (up to 10) and longer horizons than seen in training (3 objects), outperforming end-to-end GNN baselines whose performance degraded significantly beyond 6 objects.
Robustness: BISON achieved the highest average success rates across most environments, particularly in complex scenarios where replanning baselines struggled or failed.
Efficiency: BISON demonstrated superior time and memory efficiency in both training and inference compared to end-to-end and replanning methods.
Scalability: When ignoring LL execution, BISON's symbolic HL policies solved planning problems with 10,000 objects in under a minute, significantly outperforming the state-of-the-art PDDL planner LAMA, which struggled with a few hundred objects.
VLA Performance: Pretrained VLA models (SmolVLA) failed to solve any tasks in the benchmarks, highlighting the difficulty of applying them directly to long-horizon, multi-object manipulation without specific architectural adaptations.

Significance and Claims

The paper claims that BISON offers a novel solution to the long-standing challenge of long-horizon planning by effectively bridging the gap between neural imitation learning and symbolic reasoning.

Search-Free Planning: Unlike traditional bilevel planning systems that search for HL plans over symbolic abstractions before refining them, BISON inductively generalizes HL policies directly from demonstrations, eliminating the need for search during execution.
Open-World Capability: The encoding of policies as first-order, condition-action rules facilitates planning in open-world environments and handles partial observability, addressing limitations of purely symbolic planners.
Efficiency and Scalability: The approach produces compact policies that are computationally efficient and capable of scaling to massive numbers of objects, a capability often lacking in both pure neural and pure symbolic approaches.

The authors acknowledge limitations, noting that the approach inherits the dependency on the quality of the HL abstraction (whether learned or given) and does not guarantee optimality for the LL policies. However, they assert that the method provides a robust framework for embodied agents to solve complex, long-horizon tasks with varying object counts.