Approximate Solution for Interactive Dynamic Influence Diagrams Based on Belief-Behavior Graphs

Interactive Dynamic Influence Diagrams (I-DIDs) constitute a graphic model for multi-agent decision making under uncertainty, but solving them is provably intractable. Algorithms for solving I-DIDs face the challenge of an exponentially growing space of candidate models ascribed to other agents, over time. Pruning behaviorally equivalent models is one way toward minimizing the model set, but composing behavioral equivalence classes is a complex process as we need to compare all solutions of possible models of other agents in the merge operation. In this paper, we seek a more efficient way to construct behavioral equivalence classes using belief-behavior Graph (BBG). We present a method of solving I-DIDs approximately that reduces the candidate model space by clustering models that are likely to be -behavioral equivalence and selecting a representative one from each cluster. We discuss the complexity of the approximation technique and demonstrate its empirical performance.