Variational Planning for Graph-based MDPs
Qiang Cheng, Qiang Liu, Feng Chen, Alexander Ihler · 2013
Markov Decision Processes (MDPs) are extremely useful for modeling and solv-ing sequential decision making problems. Graph-based MDPs provide a compact representation for MDPs with large numbers of random variables. However, the complexity of exactly solving a graph-based MDP usually grows exponentially in the number of variables, which limits their application. We present a new varia-tional framework to describe and solve the planning problem of MDPs, and derive both exact and approximate planning algorithms. In particular, by exploiting the graph structure of graph-based MDPs, we propose a factored variational value iter-ation algorithm in which the value function is first approximated by the multiplica-tion of local-scope value functions, then solved by minimizing a Kullback-Leibler (KL) divergence. The KL divergence is optimized using the belief propagation algorithm, with complexity exponential in only the cluster size of the graph. Ex-perimental comparison on different models shows that our algorithm outperforms existing approximation algorithms at finding good policies. 1