Methods for evaluating Decision Problems with Limited Information

LImited Memory Influence Diagrams (LIMIDs) are general models of
decision problems for representing limited memory policies
(Lauritzen and Nilsson (2001)). The evaluation of LIMIDs can be
done by Single Policy Updating that produces a local maximum
strategy in which no single policy modification can increase the
expected utility. This paper examines the quality of the obtained
local maximum strategy and proposes three different methods for
evaluating LIMIDs. The first algorithm, Temporal Policy Updating,
resembles Single Policy Updating. The second algorithm, Greedy
Search, successively updates the policy that gives the highest
expected utility improvement. The final algorithm, Simulating
Annealing, differs from the two preceeding by allowing the search
to take some downhill steps to escape a local maximum. A careful
comparison of the algorithms is provided both in terms of the
quality of the obtained strategies, and in terms of implementation
of the algorithms including some considerations of the
computational complexity.