State Combinatorial Generalization In Decision Making With Conditional Diffusion Models

Xintong Duan, Yutong He, Fahim Tajwar, Wentse Chen, Ruslan Salakhutdinov, Jeff G. Schneider

This research, published in Transactions on Machine Learning Research, addresses a fundamental challenge in robotics and autonomous systems: maintaining safe and effective decision-making when an agent encounters familiar objects in entirely novel arrangements.

Introduction: Defining Out-of-Combination Generalization

In real-world environments, the number of possible states is effectively infinite due to combinatorial complexity. While a self-driving car can be trained to interact with cyclists and buses independently, it is impossible to expose the model to every possible spatial configuration of these elements during training.

Conceptualizing Out-of-Combination (OOC) generalization across sample spaces.

The authors formalize this challenge as Out-of-Combination (OOC) generalization. Unlike standard distribution shifts that focus on changes in event frequency, OOC generalization requires an agent to handle novel mixtures of previously seen "base elements." Traditional Reinforcement Learning (RL) methods, such as Q-learning, often fail in these scenarios because their value functions produce unreliable, "hallucinated" reward predictions in regions of the state space that lack training support.

Methodology: Conditional Diffusion Models

To overcome the brittleness of value-based RL, the researchers propose using Conditioned Planning with Diffusion. Instead of relying on a potentially inaccurate value function to guide actions, they train a diffusion model to generate successful trajectories directly.

  1. Behavior Cloning via Diffusion: The model learns the manifold of successful expert behaviors in "narrow" environments (e.g., scenes containing only one type of obstacle).
  2. Conditional Architecture: A Diffusion UNet is augmented with cross-attention layers, allowing the model to be conditioned on a latent vector representing the specific combination of elements in the current scene.
  3. Trajectory Stitching: During inference, the model denoises an entire future trajectory. By conditioning on the current OOC combination, the model "stitches" together behavioral modes learned during training to navigate the new scenario zero-shot.

Key Insights: The Failure of Value Functions

A critical finding of the paper is that RL agents fail OOC tasks not due to a lack of motor skill, but due to a failure in judgment. In unsupported regions of the state space, value functions often overestimate the expected reward of dangerous actions.

Comparison of expected Q-values vs. actual returns (RTG) in unsupported states, showing significant overestimation during crashes.

As shown in the analysis of unsupported states, the "Expected Q" remains high even when the actual return (RTG) is low, particularly in crash scenarios. Diffusion models avoid this by capturing the multi-modality of successful behaviors, allowing them to satisfy multiple constraints (e.g., "avoid car" and "avoid bike") simultaneously without the need for a global value estimate.

Experimental Results

The authors evaluated their approach across three domains:

  • Maze2D: The diffusion model accurately reached goals through OOC waypoint combinations where unconditioned models failed.
  • HighwayEnv (Roundabout): In mixed-traffic scenarios (cars and bikes), the conditional diffusion model resulted in nearly 50% fewer crashes than offline RL (CQL) or online RL (PPO).
  • SMACv2: In complex multi-agent battles with heterogeneous teams, replacing a standard MAPPO agent with a conditional diffusion agent improved the team's success rate by up to 23.1%.

Conclusion and Future Work

While conditional diffusion models show remarkable zero-shot OOC generalization, challenges remain regarding inference speed. The denoising process is computationally intensive, making real-time control difficult. Future research directions include integrating faster sampling techniques, such as consistency models, and improving the robustness of encoders for base objects to handle entirely unseen elements.

Summary updated

Abstract

Many real-world decision-making problems are combinatorial in nature, where states (e.g., surrounding traffic of a self-driving car) can be seen as a combination of basic elements (e.g., pedestrians, trees, and other cars). Due to combinatorial complexity, observing all combinations of basic elements in the training set is infeasible, which leads to an essential yet understudied problem of zero-shot generalization to states that are unseen combinations of previously seen elements. In this work, we first formalize this problem and then demonstrate how existing value-based reinforcement learning (RL) algorithms struggle due to unreliable value predictions in unseen states. We argue that this problem cannot be addressed with exploration alone, but requires more expressive and generalizable models. We demonstrate that behavior cloning with a conditioned diffusion model trained on successful trajectory generalizes better to states formed by new combinations of seen elements than traditional RL methods. Through experiments in maze, driving, and multiagent environments, we show that conditioned diffusion models outperform traditional RL techniques and highlight the broad applicability of our problem formulation.
BibTeX
@misc{duan2025state,
  author = {Xintong Duan and Yutong He and Fahim Tajwar and Wentse Chen and Ruslan Salakhutdinov and Jeff G. Schneider},
  title = {{State Combinatorial Generalization In Decision Making With Conditional Diffusion Models}},
  year = {2025},
  eprint = {2501.13241},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.13241},
}
Figure