A new perspective on algorithms for optimizing policies under uncertainty
Rina Dechter · 2000
The paper takes a fresh look at algorithms for maximizing expected utility over a set of policies, that is, a set of possible ways of reacting to observations about an uncertain state of the world. Using the bucketelimination framework, we characterize the complexity of this optimization task by graph-based parameters, and devise an improved variant of existing algorithms. The improvement is shown to yield a dramatic gain in complexity when the probabilistic subgraph (of the influence diagram) is sparse, regardless of the complexity introduced by its utility subgraph. Introduction Influence diagram (IDs) (Howard & Matheson 1984) are a popular framework for decision analysis. They subsume finite horizon factored observable and partially observable, Markov decision processes (MDPs, POMDPs) used to model planning problems under uncertainty (Boutilier, Dean, & Hanks 1999). The paper presents a bucket elimination algorithm for computing a sequence of policies which maximize the...