An MCMC Approach to Solving Hybrid Factored MDPs

Abstract

Hybrid approximate linear programming (HALP) has recently emerged as a promising framework for solving large factored Markov decision processes (MDPs) with discrete and continuous state and ac-tion variables. Our work addresses its major com-putational bottleneck – constraint satisfaction in large structured domains of discrete and continuous variables. We analyze this problem and propose a novel Markov chain Monte Carlo (MCMC) method for finding the most violated constraint of a relaxed HALP. This method does not require the discretiza-tion of continuous variables, searches the space of constraints intelligently based on the structure of factored MDPs, and its space complexity is linear in the number of variables. We test the method on a set of large control problems and demonstrate im-provements over alternative approaches. 1