Definition: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Input: Many large MDPs can be represented compactly using a dynamic Bayesian network. Although the structure of the value function does not re tain the structure of the process, recent work has suggested that value functions in factored MDPs can often be approximated well using a factored value function: a linear combination of restr icted basis functions, each of which refers only to a small subset of variables. An approximate fac tored value function for a particular policy can be computed using approximate dynamic pro gramming, but this approach (and others) can only produce an approximation relative to a dis tance metric which is weighted by the station ary distribution of the current policy. This type of weighted projection is ill-suited to policy im provement. We present a new approach to value determination, that uses a simple closed-form computation to compute a least-squares decom posed approximation to the value function for any weights directly. We then use this value de termination algorithm as a subroutine in a pol icy iteration process. We show that, under rea sonable restrictions, the policies induced by a factored value function can be compactly repre sented as a decision list, 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 the system dynamics and of the approximate value function.
Output:
Policy Iteration for Factored MDPs