  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.
