Exploiting Model Equivalences for Solving Interactive Dynamic Influence
  Diagrams
  We focus on the problem of sequential decision making in partially observable
environments shared with other agents of uncertain types having similar or
conflicting objectives. This problem has been previously formalized by multiple
frameworks one of which is the interactive dynamic influence diagram (I-DID),
which generalizes the well-known influence diagram to the multiagent setting.
I-DIDs are graphical models and may be used to compute the policy of an agent
given its belief over the physical state and others models, which changes as
the agent acts and observes in the multiagent setting.
  As we may expect, solving I-DIDs is computationally hard. This is
predominantly due to the large space of candidate models ascribed to the other
agents and its exponential growth over time. We present two methods for
reducing the size of the model space and stemming its exponential growth. Both
these methods involve aggregating individual models into equivalence classes.
Our first method groups together behaviorally equivalent models and selects
only those models for updating which will result in predictive behaviors that
are distinct from others in the updated model space. The second method further
compacts the model space by focusing on portions of the behavioral predictions.
Specifically, we cluster actionally equivalent models that prescribe identical
actions at a single time step. Exactly identifying the equivalences would
require us to solve all models in the initial set. We avoid this by selectively
solving some of the models, thereby introducing an approximation. We discuss
the error introduced by the approximation, and empirically demonstrate the
improved efficiency in solving I-DIDs due to the equivalences.
