Optimal control using sparse-matrix belief propagation

Abstract

The optimal control framework is a mathematical formulation by means of which many decision making problems can be represented and solved by finding optimal policies or controls. We consider the class of optimal control problems that can be formulated as a probabilistic inference on a graphical model, known as Kullback- Leibler (KL) control problems. In particular, we look at the recent progress on exploiting parallelisation facilitated by the graphics processing units (GPU) to solve such inference tasks, considering the recently introduced sparse-matrix belief propagation framework [1]. The sparse-matrix belief propagation algorithm was reported to deliver significant improvements in performance with respect to traditional loopy belief propagation, when tested on grid Markov random fields. We develop our approach in the context of the KL-stag hunt game, a multi-agent, grid-like game which shows two different behavior regimes [2]. We first describe how to transform the original problem into a pairwise Markov random field, amenable to inference using sparse-matrix belief propagation and, second, we perform an experimental evaluation. Our results show that the use of GPUs can bring notable performance improvements to the optimal control computations in the class of KL control problems. However, our results also suggest that the improvements of sparse-matrix belief propagation may be limited by the concrete form of the Markov random field factors, specially on models with high sparsity within a factor, and variables with high cardinality.