🤖 AI

Missing Bridges: Composition-Aware Active Imitation Learning

This paper introduces AALT, a composition-aware active imitation learning framework that minimizes expert effort by strategically requesting "bridge" demonstrations to maximize task connectivity in multi-task domains, achieving 100% success on 72 robot tasks with significantly fewer demonstrations and transitions than existing baselines.

Original authors: Maxwell J. Jacobson, Ahmed H Qureshi, Yexiang Xue

Published 2026-09-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maxwell J. Jacobson, Ahmed H Qureshi, Yexiang Xue

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

Robots are becoming increasingly capable of performing complex tasks, from assembling car parts to organizing shelves. However, teaching a robot to do something new usually requires a human expert to demonstrate the entire sequence of movements, a process that is slow, labor-intensive, and difficult to scale. If a robot needs to learn how to pick up a red cup from a messy table, a human might have to show it exactly how to do that specific task. If the table changes slightly, or if the robot needs to pick up a blue cup instead, the human often has to start the demonstration over again. This creates a bottleneck: the more tasks a robot needs to learn, the more time experts must spend showing it the ropes. Researchers are now exploring a smarter way to teach machines, one where the robot itself decides what it needs to learn next. Instead of passively receiving instructions, an active learner asks for specific demonstrations that will help it solve the most problems with the least amount of effort.

A team of researchers at Purdue University has developed a new method called AALT, which stands for Adaptive Agents via Latent Topologies, to solve this problem. Their work focuses on a specific challenge in robotics: how to teach a robot to handle a vast number of different scenarios when it only has a few examples to start with. Imagine a robot arm tasked with retrieving three specific colored canisters from a shelf and placing them in a specific order. The shelf might be arranged in many different ways, and the order of the canisters might change with every new work order. While there could be dozens of possible combinations of starting positions and goals, the researchers found that the robot does not need a unique demonstration for every single one. Instead, many of these tasks share common middle steps. A movement that clears a path to the left side of the shelf might be useful for retrieving a red canister, a blue one, or a green one, depending on what comes before or after it.

The researchers built a system that treats these shared movements as building blocks. They first teach the robot a small set of demonstrations, which the system organizes into a map of "hub" states. These hubs are like major intersections in a city where different paths converge or split. For example, a hub might represent a state where a shelf has been partially cleared, making it possible to reach several different items. The system then looks for the missing connections, or "bridges," between these hubs. If the robot knows how to get to a cleared shelf and how to pick up items from a cleared shelf, but it doesn't know how to clear the shelf in the first place, the system identifies that missing link as the most valuable thing to learn next. It asks the human expert to demonstrate just that specific bridge, rather than asking for a full demonstration of a complete task from start to finish.

This approach stands in contrast to older methods that ask for demonstrations based on how much they might improve the robot's general understanding of the expert's behavior. Those older methods often request long, complete demonstrations that solve only one specific problem, even if the robot could have solved many others by just learning a short connecting move. The new method, AALT, specifically looks for the short demonstrations that unlock the most new possibilities. In a simulated environment using a UR5e robot arm, the researchers tested this idea with a task involving 72 different start-and-goal combinations. The robot began with a dataset of 24 demonstrations that covered only a portion of the possible tasks. Using their new method, the robot asked for just three additional demonstrations, which totaled only five short movements. These three requests were enough to connect the existing knowledge blocks, allowing the robot to successfully solve all 72 tasks.

In comparison, the strongest existing methods tested in the same simulation required 20 demonstrations, totaling nearly 100 movements, to achieve a success rate of about 89 percent. The older methods often failed because they asked for demonstrations that were too long or too specific, leaving gaps in the robot's ability to combine behaviors. The new method succeeded because it focused on the structure of the problem, identifying the precise missing links that would allow the robot to compose its own solutions for tasks it had never seen before. The researchers found that the three bridges the robot requested were reused in many different final solutions, proving that a single short demonstration could enable a wide range of future tasks. This suggests that by asking the right questions, a robot can learn to navigate a complex world with far less human help than previously thought possible.

The study was conducted entirely in a simulated environment, meaning the results were observed on a computer model of a robot and a shelf, not on physical hardware. While the simulation was rigorous and the results were consistent across multiple trials, the researchers acknowledge that real-world conditions, such as physical friction or unexpected obstacles, might present new challenges. They also note that their method works best when tasks share meaningful intermediate steps; if a set of tasks has no common ground, this approach would not be as effective. Nevertheless, the findings offer a clear path forward for making robots more efficient learners. By shifting the focus from memorizing entire tasks to understanding how to connect behaviors, this work demonstrates that robots can become much more adaptable with significantly less training data, turning a few simple demonstrations into a vast library of capabilities.

Technical Summary: Missing Bridges: Composition-Aware Active Imitation Learning

Problem Definition

The paper addresses goal-based active imitation learning (IL) within large, structured families of start–goal tasks. In these settings, an agent begins with an incomplete dataset of expert demonstrations and operates under a limited budget to request additional demonstrations. The core challenge arises in domains where the number of possible start–goal pairs grows combinatorially (e.g., a robot retrieving specific sequences of objects from various shelf configurations), yet the solutions to these tasks often share reusable intermediate behaviors.

Existing active IL methods, particularly policy-centric approaches (e.g., Active Multi-task Fine-tuning or AMF), select demonstrations based on their expected information gain regarding the expert policy. While effective for reducing uncertainty about how to act in specific states, these methods often fail to explicitly value the compositional structure of tasks. Consequently, they may request redundant, full-task demonstrations that solve only a few specific instances, rather than requesting short "bridge" demonstrations that connect existing reusable behaviors to unlock solutions for a vast number of unseen tasks.

Methodology: Adaptive Agents via Latent Topologies (AALT)

The authors propose AALT, a composition-aware active IL method that prioritizes demonstrations based on their expected increase in start–goal connectivity rather than direct policy information gain.

1. Latent Topology Construction

AALT organizes demonstrated trajectories into a latent topology $\Gamma = (H, E)$ :

Hub States ( $H$ ): The method identifies "convergence" and "divergence" hubs in the latent space. These are states where multiple distinct trajectories converge (e.g., a shelf state after a blocker is moved) or diverge (e.g., a state from which different retrieval orders begin).
Edges ( $E$ ): Directed edges represent demonstrated behaviors connecting these hubs.
Reliability Estimation: Each edge $e$ is assigned an execution reliability $r_e \in [0, 1]$ , estimated via a Beta distribution updated by execution outcomes.

2. Acquisition Strategy: Maximizing Connectivity

Instead of querying for full tasks, AALT queries for bridge demonstrations—short trajectories connecting two existing hubs that are not yet connected.

Connectivity Metric: The method defines the support for a task $(s_0, g)$ as the reliability of the most reliable path through the topology from the start hub to a goal-satisfying hub. The global metric $C(\Gamma)$ is the expected reliability over the target task distribution.
Selection Criterion: AALT evaluates candidate bridges $e$ by calculating the connectivity gain $\Delta(e) = C(\Gamma + e) - C(\Gamma)$ . It greedily selects the bridge that maximizes this gain.
Theoretical Justification: The authors prove that connectivity gain serves as a surrogate for weighted reachability information gain. Specifically, under binary reliability assumptions, the information gain about task reachability factorizes exactly into the uncertainty of acquiring the bridge and the connectivity gain. Under soft reliability, connectivity gain provides a lower bound on this information gain.

3. Inference and Execution

At inference time, AALT:

Matches the current observation to a start hub using a learned matcher.
Plans a path to a goal-satisfying hub using Dijkstra's algorithm, weighting edges by $-\log(r_e)$ .
Executes the path using a shared diffusion policy. The policy is conditioned on the current observation, history, and the latent embeddings of the current and target hubs, generating low-level actions to traverse each edge sequentially.

Key Contributions

Composition-Aware Objective: The paper introduces a novel acquisition objective that explicitly values demonstrations for their ability to compose existing behaviors into new task solutions, contrasting with standard policy-centric information gain.
Latent Topology Framework: AALT constructs a dynamic topology of reusable hub states and behaviors, allowing the agent to reason about task reachability abstractly.
Theoretical Link: The authors formally establish the relationship between connectivity gain and reachability information gain, proving that optimizing connectivity is a valid proxy for maximizing the set of reachable tasks.
Efficient Bridge Selection: The method demonstrates that requesting short, targeted bridge demonstrations is significantly more sample-efficient than requesting full task demonstrations or using policy-uncertainty-based selection.

Experimental Results

The method was evaluated in a simulated UR5e robotic retrieval domain involving 72 start–goal tasks (combinations of 6 shelf layouts and 12 ordered work orders). The initial dataset contained 24 demonstrations covering only "intra-family" tasks (matching shelf layouts to corresponding work orders), leaving 48 cross-family tasks unsolved.

Performance: AALT achieved 100% success (72/72 tasks) using only 3 expert demonstrations (totaling 5 transitions).
Comparison:
- AMF-Full (policy-centric, full-task queries): Achieved 46.9% success after 20 demonstrations (171.6 transitions).
- AMF-Bridge (policy-centric, bridge queries): Achieved 82.5% success after 20 demonstrations.
- Random-Bridge (uniform random bridge selection): Achieved 88.6% success after 20 demonstrations.
Efficiency: AALT required significantly fewer transitions (5 vs. ~98–171) to reach perfect performance.
Failure Analysis: Baseline methods frequently failed due to a lack of acquired routes (missing connectivity), whereas AALT's failures were non-existent after the initial bridges were acquired. The three bridges acquired by AALT were reused in 18, 10, and 8 final task routes respectively, demonstrating high composability.

Significance and Claims

The paper claims that AALT represents a shift in active imitation learning from policy refinement to capability expansion. By recognizing that many complex tasks share reusable sub-behaviors, AALT identifies that the "missing links" (bridges) between these behaviors are the most valuable demonstrations to request.

The authors state that their method allows an agent to scale to combinatorial task spaces with minimal expert effort by focusing on connectivity rather than just policy uncertainty. They emphasize that while policy-centric methods are effective for learning specific behaviors, they are inefficient in structured domains where a single short demonstration can unlock a multitude of previously unsolvable tasks. The work suggests that for domains with clear compositional structures, optimizing for task reachability via latent topologies is a superior strategy for active learning.