Abstract
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 bucket- elimination 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.