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.
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:
- UAV Benchmark: A standard multiagent planning problem used to compare learned models against manually-built "Exact" models.
- 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.
- 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