Partitioned Linear Programming Approximations for MDPs
  Approximate linear programming (ALP) is an efficient approach to solving
large factored Markov decision processes (MDPs). The main idea of the method is
to approximate the optimal value function by a set of basis functions and
optimize their weights by linear programming (LP). This paper proposes a new
ALP approximation. Comparing to the standard ALP formulation, we decompose the
constraint space into a set of low-dimensional spaces. This structure allows
for solving the new LP efficiently. In particular, the constraints of the LP
can be satisfied in a compact form without an exponential dependence on the
treewidth of ALP constraints. We study both practical and theoretical aspects
of the proposed approach. Moreover, we demonstrate its scale-up potential on an
MDP with more than 2^100 states.
