Approximating behavioral equivalence for scaling solutions of I-DIDs

Zeng, Yifeng, Doshi, Prashant, Chen, Yingke, Pan, Yinghui, Mao, Hua and Chandrasekaran, Muthukumaran (2016) Approximating behavioral equivalence for scaling solutions of I-DIDs. Knowledge and Information Systems, 49 (2). pp. 511-552. ISSN 0219-1377

Zeng et al - Approximating behavioral equivalence for scaling solutions of I-DIDs AAM.pdf - Accepted Version

Download (3MB) | Preview
Official URL:


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.

Item Type: Article
Uncontrolled Keywords: Multiagent systems, Decision making, Influence diagrams, Behavioral equivalence
Subjects: G400 Computer Science
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Paul Burns
Date Deposited: 13 Jun 2019 13:37
Last Modified: 13 Aug 2021 11:56

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics