State Combinatorial Generalization In Decision Making With Conditional Diffusion Models

Xintong Duan, Yutong He, Fahim Tajwar, Wentse Chen, Russ Salakhutdinov, Jeff SchneiderSubmission to ICLR 2025 · Rejected

The Challenge of Combinatorial Complexity

Real-world decision-making is inherently combinatorial. A self-driving car, for instance, must navigate environments filled with various basic elements—pedestrians, bicycles, trucks, and trees. While an AI might encounter many of these elements individually during training, it is practically impossible to expose it to every possible combination of these elements.

This paper introduces the problem of State Combinatorial Generalization: the ability of an AI to handle "Out-of-Combination" (OOC) states. These are scenarios where the individual elements are familiar to the agent, but their specific combination has never been seen before.

Defining Out-of-Combination States

Traditional reinforcement learning (RL) agents often freeze or crash when encountering these novel mixtures. Standard RL relies on learning a "Value Function" (Q-value) that predicts future rewards based on the current state. In unseen state combinations, these value functions fall "out of support," leading the agent to make wild, unreliable guesses rather than safe decisions.

Why Traditional RL Fails: Value Function Hallucination

The authors argue that the failure of current RL to achieve zero-shot generalization in OOC scenarios stems from brittle value estimations. A striking visualization in the paper demonstrates that in OOC states, RL agents (like CQL) predict high success rates even when they are on the verge of crashing. Because they "memorized" high rewards from pure training environments, they incorrectly map those expectations to new, dangerous combinations, effectively hallucinating safety.

Value Function Hallucination in Unseen States

A common RL mantra to fix this is "more exploration." However, the authors argue that for OOC scenarios, exploration alone is insufficient because the combinatorial state space is exponentially large. Instead, we need more expressive models that understand the underlying "grammar" of how basic elements compose a scene.

The Solution: Conditioned Diffusion Models

To bridge this gap, the researchers propose using Conditioned Diffusion Models for planning, shifting from a value-based approach to a generative one:

  1. Trajectory-Based Planning: Instead of evaluating single actions step-by-step, the model learns to generate entire sequences of future state-action pairs (trajectories) simultaneously.
  2. Behavior Cloning (BC): The diffusion model is trained on successful trajectories from an expert (or a basic RL agent like PPO) operating in "pure" environments (e.g., traffic with only cars or only bikes).
  3. Cross-Attention Conditioning: To make the model aware of the specific "mix" of elements in a new state, the architecture incorporates a cross-attention layer. This allows the model to attend to a latent vector representing the current combination of environmental elements.
  4. Manifold Interpolation: Theoretically, well-trained diffusion models concentrate probability mass on a "linear manifold" of valid combinations. When the model sees a car and a bike together for the first time, it can compose the "avoid car" behavior with the "pass bike" behavior by interpolating between known, physically plausible trajectories.

Experimental Results

The authors evaluated their diffusion-based approach across three distinct domains, demonstrating significant improvements over traditional RL:

  • Driving Safety (HighwayEnv): In a roundabout driving simulator, training involved traffic consisting of only cars or only bicycles. Testing involved a novel mixture of both. The conditioned diffusion model achieved nearly 50% fewer crashes and higher overall rewards than PPO or CQL baselines.
  • Multi-Agent Combat (SMACv2): In the StarCraft Multi-Agent Challenge, the model was trained on teams of identical units but tested on random mixtures (e.g., Stalkers, Zealots, and Colossi). In this "Hard" OOC setup, standard MAPPO performance dropped by over 55%. By replacing just one MAPPO agent with a diffusion-based agent, the team's success rate improved by 16.7% (in 3v3) and 23.1% (in 5v5).
  • Zero-Shot Navigation (Maze2D): The agent was tasked with reaching a goal through specific waypoints. When tested on start/end/waypoint combinations never seen together during training, the diffusion model accurately generated successful paths, whereas unconditioned models failed to reach the goal.

Limitations and Future Directions

While conditioned diffusion models offer a powerful new paradigm for combinatorial generalization, the authors note a few limitations:

  • Computational Cost: Planning with diffusion requires multiple "denoising" steps to generate a trajectory, making it significantly slower and more computationally intensive than a single forward pass of a standard neural network policy.
  • Unseen Base Objects: The model excels at new combinations of seen things, but it still struggles with entirely new objects (e.g., encountering a scooter when it has only ever seen cars and bikes).
  • Multi-Agent Coordination: Interestingly, replacing all agents in a StarCraft team with independent diffusion models hurt performance, as they lost the collaborative, centralized policy learned by standard multi-agent RL. Future work will need to explore multi-agent diffusion coordination to maintain team synergy.

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 $\textit{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 expert 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 Russ Salakhutdinov and Jeff 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