UC Irvine

Graphical models provide a unified framework for modeling and reasoning about complex tasks. Example tasks include probabilistic inference and sequential decision making under uncertainty. Influence diagrams extend Bayesian networks with decision variables and utility functions to model the interaction between an agent and a system aiming to capture the agent's preferences. The standard task is to compute the maximum expected utility (MEU) over the influence diagram and a corresponding maximizing sequence of policies. However, finding the MEU is intractable, and it is one of the most challenging tasks in graphical models. Therefore, the goal of this dissertation is the development of decomposition bounds for influence diagrams. Computing upper bounds on the MEU is desirable also because upper bounds can facilitate anytime-solutions by acting as heuristics to guide search or sampling-based methods. Most earlier approaches for upper bounding the MEU relied on polynomial reductions to other standard tasks in graphical models. However, such reductions are ineffective in practice since they highly inflate the problem size that needs to be solved. In this dissertation, we present two direct bounding methods for IDs. The first builds on the algebraic framework for influence diagrams, called valuation algebra. Using this framework, we extend two earlier decomposition bounds to the MEU task. The second method provides upper bounds by exploiting an exponentiated utility form of the MEU which can be bounded by a conventional task (i.e., marginal MAP) over a standard probabilistic graphical model. This enables the use of two variational decomposition bounds for the well known marginal MAP task, yielding what we call exponentiated utility bounds for the MEU. For both cases (using valuation algebra and using exponentiated utilities), we present two kinds of message passing algorithms derived from bounding schemes on the marginal MAP task. One is the generalized dual decomposition algorithm, which propagates messages over a join-graph decomposition of an ID. The other is a weighted mini-bucket algorithm that propagates messages over the mini-bucket tree decomposition. We evaluated all the algorithms empirically and compared them against earlier approaches over four synthetic benchmark domains. The empirical evaluation results show that our direct bounding schemes generate upper bounds that are orders of magnitude tighter than previous methods. In addition, the exponentiated schemes turn out to be, overall, far more effective. We also evaluated our algorithms on the well-known system administration domain and observed that one of the exponentiated algorithms exhibited a remarkable performance generating upper bounds that are within a factor of two from the exact MEU.