Approximate Solutions of Interactive Dynamic Influence Diagrams Using epsilon-Behavioral Equivalence
Muthukumaran Chandrasekaran, Prashant Doshi, Yifeng Zeng · ISAIM · 2010
Interactive dynamic influence diagrams (I-DID) are graphical models for sequential decision making in uncertain 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. Pruning the behaviorally equivalent models is one way toward identifying a minimal model set. We further reduce the complexity by pruning models that are approximately behaviorally equivalent. Toward this, we redefine behavioral equivalence in terms of the distribution over the subject agent’s future action-observation paths, and introduce the notion of ǫ-behavioral equivalence. We present a new approximation method that reduces the candidate models by pruning models that are ǫ-behaviorally equivalent with representative ones.