Chain of Thought Imitation with Procedure Cloning

Mengjiao Yang, Dale Schuurmans, Pieter Abbeel, Ofir Nachum

TL;DR

Standard imitation learning often fails to generalize because it only learns what an expert does, ignoring the "chain of thought" behind the action. This paper introduces Procedure Cloning (PC), a method that trains agents to mimic the intermediate computations (like search or planning steps) of an expert. By learning the "how" and "why," PC agents achieve significantly better generalization in complex tasks ranging from maze navigation to robotic manipulation.

What Problem Does This Paper Address?

The dominant approach to imitation learning is Behavioral Cloning (BC). In BC, we treat the problem as simple supervised learning: given an observation (input state), predict the expert's action (output).

However, this is a massive oversimplification. In the real world, experts (and even the algorithms used to generate "expert" data) don't just jump from state to action. They use internal procedures—planning, searching, or following a set of rules—to arrive at a decision. BC throws this "thought process" away, forcing the agent to memorize a direct mapping. Consequently, these agents often "brittlely" overfit to training data; if a maze layout changes slightly or a robot encounters a new object color, the agent fails because it never truly understood the logic of the task.

Comparison of Behavioral Cloning and Procedure Cloning

Methods: Procedure Cloning

To address the shortcomings of BC, the authors propose Chain of Thought Imitation via a technique called Procedure Cloning (PC). The core idea is to teach the agent to "think before it acts."

  1. Procedure Observations: Instead of just recording $(state, action)$ pairs, the researchers record the intermediate steps of the expert's algorithm. For example, if the expert uses a Breadth-First Search (BFS) to find a path, PC records the sequence of cells the BFS "visited" before deciding on the first move.
  2. Sequence Prediction: PC treats these intermediate steps as a sequence. It uses a supervised sequence model (like a Transformer or a GPT-style architecture) to predict the joint distribution of the procedure steps and the final action.
  3. Autoregressive Inference: At test time, the agent doesn't have access to the expert's tools (like a simulator or a search algorithm). Instead, it emulates the procedure. It looks at the current state, autoregressively generates its own "internal thought process" steps, and then outputs the final action based on those generated steps.

Key Insights and Ideas

  • PC vs. Auxiliary Tasks: A common trick in reinforcement and imitation learning is to use intermediate information as an "auxiliary task" (e.g., predicting the goal as a side-hustle to improve state representations). The paper shows that PC is fundamentally superior because it treats the procedure as a precursor to the action. The action is explicitly conditioned on the thought process, making the logic a core part of the decision rather than just a regularizer.
Graphical models comparing Vanilla BC, Auxiliary BC, and Procedure Cloning
  • The "Scaling Law" of Imitation: By including procedure observations, the training data becomes much richer. This allows the use of more expressive models (like Transformers) that benefit from larger datasets, leading to better generalization—similar to how Large Language Models improve with more tokens.
  • Zero-Shot Generalization: Because PC learns the logic of search/planning, it can handle environments where the expert algorithm itself might be too slow or infeasible to run (e.g., running Monte-Carlo Tree Search in a highly stochastic environment).

Datasets and Key Results

The authors evaluated PC across several diverse benchmarks, demonstrating significant improvements over traditional methods:

  • Synthetic Maze Navigation: A gridworld where the expert uses BFS. In large 32x32 mazes, vanilla BC had a 0% success rate on new layouts. Procedure Cloning achieved 100% success, effectively learning the "spirit" of the BFS algorithm.
  • Bimanual Sweeping: A high-dimensional robotic manipulation task involving two 7-DoF arms sweeping particles into bowls. PC achieved an 83.9% success rate, outperforming the previous state-of-the-art "Implicit BC" (78.2%).
  • MinAtar: A simplified version of Atari games where the expert is an MCTS algorithm. PC generalized much better than BC to "sticky actions" (stochasticity) and increased difficulty levels, even outperforming the MCTS expert it was trained on in certain noisy scenarios.
  • AntMaze (D4RL): A complex, continuous control task where an 8-DoF quadruped robot must navigate a maze, further proving PC's viability in continuous spaces.

Limitations and Future Work

While powerful, Procedure Cloning comes with trade-offs:

  • Computational Overhead: Because the agent must generate a sequence of "thoughts" before every action, inference is slower and more computationally expensive than a simple BC policy.
  • Manual Encoding: The practitioner still needs to decide how to represent the expert's internal procedure as a sequence of observations. There isn't yet a "universal" way to encode any arbitrary algorithm for PC.

Future Direction: The authors suggest that applying this to even larger-scale sequence modeling (like those used in LLMs) could bridge the gap between memoryless policies and high-level reasoning in autonomous agents.

Summary updated

Abstract

Imitation learning aims to extract high-performance policies from logged demonstrations of expert behavior. It is common to frame imitation learning as a supervised learning problem in which one fits a function approximator to the input-output mapping exhibited by the logged demonstrations (input observations to output actions). While the framing of imitation learning as a supervised input-output learning problem allows for applicability in a wide variety of settings, it is also an overly simplistic view of the problem in situations where the expert demonstrations provide much richer insight into expert behavior. For example, applications such as path navigation, robot manipulation, and strategy games acquire expert demonstrations via planning, search, or some other multi-step algorithm, revealing not just the output action to be imitated but also the procedure for how to determine this action. While these intermediate computations may use tools not available to the agent during inference (e.g., environment simulators), they are nevertheless informative as a way to explain an expert’s mapping of state to actions. To properly leverage expert procedure information without relying on the privileged tools the expert may have used to perform the procedure, we propose procedure cloning, which applies supervised sequence prediction to imitate the complete series of expert computations. This way, procedure cloning learns not only what to do (i.e., the output action), but how and why to do it (i.e., the procedure). Through empirical analysis on navigation, simulated robotic manipulation, and game-playing environments, we show that imitating the intermediate computations of an expert’s behavior enables procedure cloning to learn policies exhibiting significant generalization to unseen environment configurations, including those configurations for which running the expert’s procedure directly is infeasible.
BibTeX
@inproceedings{yang2022chain,
  author = {Mengjiao Yang and Dale Schuurmans and Pieter Abbeel and Ofir Nachum},
  title = {{Chain of Thought Imitation with Procedure Cloning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=3byEXeqlamX},
}
Figure