Influence Diagrams with Memory States: Representation and Algorithms

Xiaojian Wu, Akshat Kumar, and Shlomo Zilberstein. Influence Diagrams with Memory States: Representation and Algorithms. Proceedings of the Second International Conference on Algorithmic Decision Theory (ADT), Rutgers University, 2011.

Abstract

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 high-quality approximate polices and offers better scalability than existing methods.

Bibtex entry:

@inproceedings{WKZadt11,
  author	= {Xiaojian Wu and Akshat Kumar and Shlomo Zilberstein},
  title		= {Influence Diagrams with Memory States: Representation and Algorithms},
  booktitle     = {Proceedings of the Second International Conference on Algorithmic 
                   Decision Theory},
  year		= {2011},
  pages		= {},
  address       = {Rutgers University, USA},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/WKZadt11.html}
}

shlomo@cs.umass.edu