Approximating behavioral equivalence for scaling solutions of I-DIDs

Yifeng Zeng, Prashant Doshi, Yingke Chen, Yinghui Pan, Hua Mao, Muthukumaran Chandrasekaran

    Research output: Contribution to journalArticlepeer-review

    5 Downloads (Pure)

    Abstract

    Interactive dynamic influence diagram (I-DID) is a recognized graphical framework for sequential multiagent decision making under uncertainty. I-DIDs concisely represent the problem of how an individual agent should act in an uncertain environment shared with others of unknown types. I-DIDs face the challenge of solving a large number of models that are ascribed to other agents. A known method for solving I-DIDs is to group models of other agents that are behaviorally equivalent. Identifying model equivalence requires solving models and comparing their solutions generally represented as policy trees. Because the trees grow exponentially with the number of decision time steps, comparing entire policy trees becomes intractable thereby limiting the scalability of previous I-DID techniques.

    In this article, our specific approaches focus on utilizing partial policy trees for comparison and determining the distance between updated beliefs at the leaves of the trees. We propose a principled way to determine how much of the policy trees to consider, which trades off solution quality for efficiency. We further improve on this technique by allowing the partial policy trees to have paths of differing lengths. We evaluate these approaches in multiple problem domains and demonstrate significantly improved scalability over previous approaches.
    Original languageEnglish
    Pages (from-to)511-552
    JournalKnowledge and Information Systems
    Volume49
    Issue number2
    DOIs
    Publication statusE-pub ahead of print - 30 Dec 2015

    Fingerprint Dive into the research topics of 'Approximating behavioral equivalence for scaling solutions of I-DIDs'. Together they form a unique fingerprint.

    Cite this