Approximate Solutions of Interactive Dynamic Influence Diagrams Using Model Clustering

Interactive dynamic influence diagrams (I-DIDs) offer atransparent and semantically clear representation for the sequentialdecision-making problem over multiple time steps inthe presence of other interacting agents. Solving I-DIDs exactlyinvolves knowing the solutions of possible models ofthe other agents, which increase exponentially with the numberof time steps. We present a method of solving I-DIDsapproximately by limiting the number of other agents' candidatemodels at each time step to a constant. We do this byclustering the models and selecting a representative set fromthe clusters. We discuss the error bound of the approximationtechnique and demonstrate its empirical performance.