LIMIDs of decision problems

We introduce the notion of LImited Memory Influence Diagram (LIMID) to describe multi-stage decision problems where the traditional assumption of no forgetting is relaxed. This can be relevant in situations with multiple decision makers or when decisions must be prescribed under memory constraints, such as e.g. in partially observed Markov decision processes (POMDPs). We give an algorithm for improving any given strategy by local computation of single policy updates. We investigate conditions for the resulting strategy to be optimal. As a consequence we also obtain an efficient algorithm for solving traditional influence diagrams. Key words: Influence diagram; junction tree; local computation; message passing; optimal strategies; partially observed Markov decision process, POMDP, single policy updating. 1 Introduction This article is concerned with finding optimal strategies in multi-stage decision problems involving uncertainty. In accordance with classical decision theo...