Influence Diagrams With Memory States: Representation and Algorithms

• Main Authors: WU, Xiaojian, KUMAR, Akshat, ZILBERSTEIN, Shlomo
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2011
• Subjects: Artificial Intelligence and Robotics; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/2206; https://ink.library.smu.edu.sg/context/sis_research/article/3206/viewcontent/Influence_Diagrams_With_Memory_States__Representation_and_Algorithms.pdf
• Institution: Singapore Management University

Influence diagrams (IDs) offer a powerful framework for decision making under uncertainty, but their applicability has been hindered by the exponential growth of runtime and memory usage--largely due to the no-forgetting assumption. We present a novel way to maintain a limited amount of memory to inform each decision and still obtain near-optimal policies. The approach is based on augmenting the graphical model with memory states that represent key aspects of previous observations--a method that has proved useful in POMDP solvers. We also derive an efficient EM-based message-passing algorithm to compute the policy. Experimental results show that this approach produces highquality approximate polices and offers better scalability than existing methods.