A Variational Perturbative Approach to Planning in Graph-based Markov
  Decision Processes
  Coordinating multiple interacting agents to achieve a common goal is a
difficult task with huge applicability. This problem remains hard to solve,
even when limiting interactions to be mediated via a static interaction-graph.
We present a novel approximate solution method for multi-agent Markov decision
problems on graphs, based on variational perturbation theory. We adopt the
strategy of planning via inference, which has been explored in various prior
works. We employ a non-trivial extension of a novel high-order variational
method that allows for approximate inference in large networks and has been
shown to surpass the accuracy of existing variational methods. To compare our
method to two state-of-the-art methods for multi-agent planning on graphs, we
apply the method different standard GMDP problems. We show that in cases, where
the goal is encoded as a non-local cost function, our method performs well,
while state-of-the-art methods approach the performance of random guess. In a
final experiment, we demonstrate that our method brings significant improvement
for synchronization tasks.
