  Stochastic planning can be reduced to probabilistic inference in large
discrete graphical models, but hardness of inference requires approximation
schemes to be used. In this paper we argue that such applications can be
disentangled along two dimensions. The first is the direction of information
flow in the idealized exact optimization objective, i.e., forward vs backward
inference. The second is the type of approximation used to compute this
objective, e.g., Belief Propagation (BP) vs mean field variational inference
(MFVI). This new categorization allows us to unify a large amount of isolated
efforts in prior work explaining their connections and differences as well as
potential improvements. An extensive experimental evaluation over large
stochastic planning problems shows the advantage of forward BP over several
algorithms based on MFVI. An analysis of practical limitations of MFVI
motivates a novel algorithm, collapsed state variational inference (CSVI),
which provides a tighter approximation and achieves comparable planning
performance with forward BP.
