Speeding Up Exact Solutions of Interactive Dynamic Influence Diagrams Using Action Equivalence

Interactive dynamic influence diagrams (I-DIDs) are graphical models for  sequential  decision making  in  partially observable  settings shared  by other  agents.  Algorithms  for solving  I-DIDs  face the challenge  of an  exponentially  growing space  of candidate  models ascribed to  other agents, over time. Previous  approach for exactly   solving I-DIDs groups together  models having similar solutions into behaviorally  equivalent  classes  and  updates these  classes.   We present a  new method that, in addition  to aggregating behaviorally equivalent  models, further groups  models that  prescribe identical actions at a single time step. We show how to update these augmented classes  and prove  that  our  method is  exact.   The new  approach   enables us to bound the aggregated model space by the cardinality of   other  agents'  actions. We  evaluate  its  performance and  provide   empirical results in support.