Interactive dynamic influence diagrams

ABSTRACT

Partially Observable Markov Decision Processes (POMDPs) emerged as the primary framework for decision-theoretic planning in single agent settings. Solutions to POMDPs are optimal plans which are conditional on future observations. Dynamic Influence Diagrams (DIDs) are computational representations of POMDPs which compute solutions for finite time horizons in an on-line fashion. Interactive POMDPs (I-POMDPs) [5] generalize POMDPs to multi-agent settings by including models of other agents in the state space. Interactive DIDs (I-DIDs), presented in this paper, are computational representations of I-POMDPs, and thus generalizations of DIDs. DIDs are themselves temporal generalizations of influence diagrams [6].

REFERENCES

• 1: R. J. Aumann and A. Heifetz. Incomplete information. In R. Aumann and S. Hart, editors, Handbook of Game Theory with Economic Applications, Volume III, Chapter 43. Elsevier, 2002.
• 2: P. Battigalli and G. Bonano. Recent results on belief, knowledge and the epistemic foundations of game theory. Technical Report 98--14, University of California, Davis - Department of Economics, 1998.
• 3: P. Battigalli and M. Siniscalchi. Hierarchies of conditional beliefs and interactive epistemology in dynamic games. Journal of Economic Theory, (88):188--230, 1999.
• 4: C. Boutilier, T. Dean, and S. Hanks. Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial intelligence Research, 11:1--94, 1999.
• 5: P. Gmytrasiewicz and P. Doshi. A framework for sequential planning in multiagent settings. Journal of Artificial Intelligence Research, 24:49--79, 2005. http://jair.org/contents/v24.html.
• 6: R. A. Howard and J. E. Matheson. Influence diagrams. In R. A. Howard and J. E. Matheson, editors, Readings on Principles and Applications of Decision Analysis, pages 721--762. Strategic Decisions Group, Menlo Park, CA, 1984.
• 7: J. B. Kadane and P. D. Larkey. Subjective probability and the theory of games. Management Science, 28(2):113--120, Feb. 1982.
• 8: Leslie Pack Kaelbling , Michael L. Littman , Anthony R. Cassandra, Planning and acting in partially observable stochastic domains, Artificial Intelligence, v.101 n.1-2, p.99-134, May 1998 [doi>10.1016/S0004-3702(98)00023-X]
• 9: G. E. Monahan. A survey of partially observable markov decision processes: Theory, models, and algorithms. Management Science, pages 1--16, 1982.
• 10: R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.