Many large MDPs can be represented compactly using a dynamic Bayesian
network. Although the structure of the value function does not retain the
structure of the process, recent work has shown that value functions in
factored MDPs can often be approximated well using a decomposed value
function: a linear combination of *restricted* basis functions, each of
which refers only to a small subset of variables. An approximate value
function for a particular policy can be computed using approximate dynamic
programming, but this approach (and others) can only produce an
approximation relative to a distance metric which is weighted by the
stationary distribution of the current policy. This type of weighted
projection is ill-suited to policy improvement. We present a new approach
to value determination, that uses a simple closed-form computation to
directly compute a least-squares decomposed approximation to the value
function *for any weights*. We then use this value determination
algorithm as a subroutine in a policy iteration process. We show that,
under reasonable restrictions, the policies induced by a factored value
function are compactly represented, and can be manipulated efficiently in a
policy iteration process. We also present a method for computing error
bounds for decomposed value functions using a variable-elimination algorithm
for function optimization. The complexity of all of our algorithms depends
on the factorization of system dynamics and of the approximate value
function.