Approximate Inference for Stochastic Planning in Factored Spaces
This work addresses the problem of efficient stochastic planning for researchers and practitioners in AI, offering incremental improvements through a new categorization and algorithm.
The paper tackles the challenge of approximate inference in stochastic planning by proposing a categorization based on information flow direction and approximation type, which unifies prior work and reveals forward Belief Propagation's advantage over mean field variational inference methods. It introduces collapsed state variational inference (CSVI) as a novel algorithm that provides a tighter approximation and achieves comparable performance to forward BP in large stochastic planning problems.
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.