Computing bounds on expected utilities for optimal policies based
on limited information
Dennis Nilsson, Aalborg University, Denmark and Royal Veterinary and Agricultural University, Denmark
Michael Höhle, Royal Veterinary and Agricultural University, Denmark
2001
A LImited Memory Influence Diagram (LIMID) is a multi-stage decision problem in which the traditional assumption of no forgetting is relaxed. The LIMID representation is particular suitable for approximating multi-stage decision problems where exact evaluation is impossible. Such problems include most real-world applications of influence diagrams and partially observable Markov decision processes (POMDPs). This paper uses the notion of LIMIDs to construct upper and lower bounds for multi-stage decision problems. The bounds are computed incrementally by manipulating the available information when making the decisions. We provide examples of the process on several large decision problems.
