Learning Behaviors in Agents Systems with Interactive Dynamic Influence Diagrams

Ross Conroy, Yifeng Zeng, Marc Cavazza, Yingke ChenIJCAI 2015

Introduction

In multiagent systems, optimal decision-making hinges on the ability to predict the actions of other agents. Interactive Dynamic Influence Diagrams (I-DIDs) provide a robust graphical framework for this by explicitly modeling an opponent’s beliefs and decision processes over time. However, a significant "knowledge bottleneck" exists: traditionally, I-DIDs require domain experts to manually code these opponent models. In complex, dynamic environments like Real-Time Strategy (RTS) games, human behavior is often too nuanced for static, hard-coded rules. This paper introduces a data-driven approach to automatically learn agent behaviors from replay data, specifically utilizing StarCraft combat scenarios.

Methodology: Learning Policy Trees

The core of the proposed framework is the automated construction of Policy Trees from historical data. These trees represent an agent's sequence of actions and observations over a specific planning horizon.

Example of a Policy Tree representing agent actions (attack/escape) based on observations (see/don't see).

Behavioral Compatibility Test (BCT)

A primary challenge in learning from replay data is "sparsity"—the data often lacks observations for every possible situation. To address missing branches in the policy tree, the authors developed the Behavioral Compatibility Test (BCT). Rather than filling gaps randomly, BCT evaluates whether a missing node is statistically compatible with an existing one. If two nodes exhibit similar behavioral patterns in response to observations, the algorithm "borrows" the known branch to complete the tree. This allows the agent to generalize from limited data by identifying common tactical patterns.

I-DID Integration

Once the policy trees are learned, they are integrated into the I-DID framework. The subject agent then uses these models to solve for its own optimal actions, accounting for the predicted behavior of its opponents.

Experimental Evaluation

The approach was tested in two environments:

  1. UAV Benchmark: A standard multiagent planning problem used to compare learned models against manually-built "Exact" models.
  2. StarCraft Replay Data: 1v1 combat scenarios (Terran Goliath vs. Goliath). Replay data was processed using the BWAPI library to extract human and NPC behavior patterns.

Key Results and Insights

The experiments yielded several critical insights:

  • Performance of BCT: In UAV simulations, the BCT-based approach consistently outperformed random fill-in methods. As shown in the performance metrics, the BCT approach approaches the performance of "Exact" manually crafted models as the number of training simulations increases.
  • Data-Driven Advantage: Interestingly, learned models sometimes outperformed "Exact" models. While manual models often assume a broad distribution of opponent types, the data-driven approach focuses on the actual strategies prevalent in the environment, leading to more specialized and effective decision-making.
Average reward performance of the BCT approach compared to random fill-ins and exact models as training simulations increase.
  • Efficiency: The BCT algorithm operates with polynomial complexity relative to data size, offering a scalable alternative to more computationally intensive Bayesian nonparametric methods.

Conclusion

By replacing manual expert modeling with automated behavior learning via Policy Trees and the Behavioral Compatibility Test, this research mitigates the knowledge bottleneck in I-DID frameworks. The results in StarCraft demonstrate that agents can effectively learn complex strategies from sparse data, achieving high rewards in competitive multiagent settings. Future work will focus on transitioning from offline replay learning to online, incremental model updates during live encounters.

Summary updated

BibTeX
@inproceedings{conroy2015learning,
  author = {Ross Conroy and Yifeng Zeng and Marc Cavazza and Yingke Chen},
  title = {{Learning Behaviors in Agents Systems with Interactive Dynamic Influence Diagrams}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure