Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables.
 MDPs and POMDPS, widely used for planning under uncertainty can also be represented by influence diagrams.
 The time and space complexity of computing the maximum expected utility (MEU) and its maximizing policy is exponential in the induced width of the underlying graphical model, which is often prohibitively large due to the growth of the information set under the sequence of decisions.
 In this paper, we develop a weighted mini-bucket approach for bounding the MEU.  These bounds can be used as a stand-alone approximation that can be improved as a function of a controlling i-bound parameter .
They can also be used as heuristic  functions to guide search, especially for planning 
 such as MDPs and POMDPs.
 We evaluate the scheme empirically against state-of-the-art, thus illustrating its potential.
 An influence diagram (ID) BID4 ) is a graphical model for sequential decision-making under uncertainty that compactly captures the local structure of the conditional independence of probability functions and the additivity of utility functions. Its structure is captured by a directed acyclic graph (DAG) over nodes representing the variables (decision and chance variables). The standard query on an ID is finding the maximum expected utility (MEU) and the corresponding optimal policy for each decision, subject to the history of observations and decisions.Computing the MEU is recognized as one of the hardest tasks over graphical models, and hence recent work aims at developing anytime bounding schemes that tighten the bounds if more time and memory is available. Often, the target is to incorporate such bounds as heuristic functions to guide search algorithms. In this paper, we focus on computing the upper bound of MEU for a single agent sequential decision making problem with no-forgetting assumptions. We build on the methodology of weighted mini-bucket with costshifting that was used in the past for bounding probabilistic queries such as the partition function, Maximum A Posteriori (MAP) and Marginal MAP (MMAP) BID0 BID12 BID5 BID14 BID13 ). We presented a new bounding scheme for influence diagrams, called WMBE-ID, which computes upper bounds of the MEU by interleaving variable elimination with optimizing partial decomposition within each variable's bucket. Compared with the previous approaches, our proposed upper bounding scheme produces high quality upper bounds in shorter time bounds. This is instrumental for our plan to Table 2 : The performance of the bounding schemes on individual instances. n is the number of variables, f is the number of functions, k is the maximum domain size, s is the maximum scope size, w is the constrained induced width. We show the (time, upper bound) for various i-bounds and number of iterations for algorithms updating the costs or weights. WMBE-U is the mini-bucket elimination with uniform weights, WMBE-UC preforms cost shifting without optimizing the weight, WMBE-WC optimizes both weights and costs, JGDID is the fully decomposed bound over a join graph that optimizes both weights and costs, MBE is the simple mini-bucket elimination, and MBE-Re is mini-bucket elimination with relaxed variable ordering. MBE, MBE-RE, and WMBE-U do not optimize the bound. The best upper bounds are highlighted. Table 3 : Comparing the ratio of time and quality of upper bounds against JGDID(i=1). WMBE-UC and WMBE-WC were provided with i-bound 10 and 15 with the number of iteration fixed to 5, and JGDID were provided i-bound 1 and 10 with the maximum number iteration limited by 100. All the quantities are normalized by the statistics of JGDID(i=1). DISPLAYFORM0 use such bounds as a heuristic evaluation function for search algorithms for solving influence diagrams.
This paper introduces an elimination based heuristic function for sequential decision making, suitable for guiding AND/OR search algorithms for solving influence diagrams. generalizes minibuckets inference heuristic to influence diagrams.