From Stochastic Planning to Marginal MAP
It is well known that the problems of stochastic planning and probabilistic inference are closely related. This paper makes two contributions in this context. The first is to provide an analysis of the recently developed SOGBOFA heuristic planning algorithm that was shown to be effective for problems with large factored state and action spaces. It is shown that SOGBOFA can be seen as a specialized inference algorithm that computes its solutions through a combination of a symbolic variant of belief propagation and gradient ascent. The second contribution is a new solver for Marginal MAP (MMAP) inference. We introduce a new reduction from MMAP to maximum expected utility problems which are suitable for the symbolic computation in SOGBOFA. This yields a novel algebraic gradient-based solver (AGS) for MMAP. An experimental evaluation illustrates the potential of AGS in solving difficult MMAP problems.
Main ideas ========== The paper develops the relation between solving an MDP and performing inference in a Bayesian network. The direction, however, is novel as far as I can tell: using MDP algorithms to solve an inference problem.  The first part shows that an existing MDP algorithm (ARollout)  is in fact performing a BP iteration over the DBN that represents the MDP.  In the second part, a different MDP algorithm (SOGBOFA) is used to solve a particular inference problem of choosing a subset of values with the maximal marginals (MMAP). The resulting SOGBOFA-based solver often loses to the state-of-the-art, but for harder cases it can outperform the state of the art.    The idea is interesting and the results are useful, mainly in expanding the understanding of the relation between planning and inference.   Regarding quality, I was not able to verify all details of the proofs and algorithms, but as far as I could verify the paper is technically sound.   Strength ======== Originality: I am not aware of work on using planning to solve inference problem, and on mapping an MDP solver to BP.   Significance: I like the mapping proposed by the authors, and I wonder if it can be extended to other planning algorithms, i.e., using them to solve MMAP as well.    Weaknesses ========== Clarity: the paper was very hard for me to follow. I mention some of the reasons below, but in general, more background is needed. However, I admit that this work is somewhat outside my area of expertise, and so perhaps this background is not needed for someone that is more in the field.   Examples of clarity issues: Line 91: "... to estimate values ..." - which values? Line 97: "c_{ij}" what is the j representing? Line 130: "... concrete values, ... use the expressions ..." - which values? which expressions? Line 140: "... an evaluation of the graph ..." - what do you by this? In general the paragraph starting with line 140 should be elaborated.  Also, the term "automatic differentiation" is used several times but is not explained (and a reference for it is also not provided).  Line 197: "For the purpose of this paper it suffices to consider IDs where decision nodes do not have parents and there is a single value node V." - please better explain: why is it sufficient to consider this? I think that you relax this requirement later in the paper, but if that's the case then say so explicitly, e.g., "We begin by assuming X and then relax it."    Rebuttal question: ================= I find the reduction from MMAP to SOGBOFA confusing, since usually reduction is done between problems. This raises the following question: can one reduce an MMAP problem to an MDP problem? I belive the answer is yes, in which case why should one use specifically SOGBOFA to solve this problem?    Minors: ====== Line 96: you probably want to have "if" not in math mode, to get the spacing correct.  Line 97: "... where p_i is p(x=1) ..."  - do you mean "p_1 is p(x=1)"?