Improved approximation of interactive dynamic influence diagrams using discriminative model updates

ABSTRACT

Interactive dynamic influence diagrams (I-DIDs) 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. We formalize the concept of a minimal model set, which facilitates qualitative comparisons between different approximation techniques. We then present a new approximation technique that minimizes the space of candidate models by discriminating between model updates. We empirically demonstrate that our approach improves significantly in performance on the previous clustering based approximation technique.

REFERENCES

• 1: Prashant Doshi , Yifeng Zeng , Qiongyu Chen, Graphical models for interactive POMDPs: representations and solutions, Autonomous Agents and Multi-Agent Systems, v.18 n.3, p.376-416, June 2009 [doi>10.1007/s10458-008-9064-7]
• 2: Ya'akov Gal , Avi Pfeffer, A language for modeling agents' decision making processes in games, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860618]
• 3: P. Gmytrasiewicz and P. Doshi. A framework for sequential planning in multiagent settings. JAIR, 24:49--79, 2005.
• 4: D. Koller and B. Milch. Multi-agent IDs for representing and solving games. In IJCAI, pages 1027--1034, 2001.
• 5: J. Pineau, G. Gordon, and S. Thrun. Anytime point-based value iteration for large pomdps. JAIR, 27:335--380, 2006.
• 6: D. Pynadath and S. Marsella. Minimal mental models. In AAAI, pages 1038--1044, 2007.
• 7: Bharanee Rathnasabapathy , Prashant Doshi , Piotr Gmytrasiewicz, Exact solutions of interactive POMDPs using behavioral equivalence, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160816]
• 8: S. Seuken and S. Zilberstein. Improved memory bounded dynamic programming for decentralized pomdps. In UAI, pages 2009--2015, 2007.
• 9: R. Smallwood and E. Sondik. The optimal control of partially observable markov decision processes over a finite horizon. OR, 21:1071--1088, 1973.
• 10: Dicky Suryadi , Piotr J. Gmytrasiewicz, Learning models of other agents using influence diagrams, Proceedings of the seventh international conference on User modeling, p.223-232, June 1999, Banff, Canada
• 11: J. A. Tatman and R. D. Shachter. Dynamic programming and influence diagrams. IEEE Trans. SMC, 20(2):365--379, 1990.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Performance, Theory

Keywords:
agent modeling, behaviorally equivalent, decision making