Timezone: »

Convergent Fitted Value Iteration with Linear Function Approximation
Daniel Lizotte

Tue Dec 13 08:45 AM -- 02:59 PM (PST) @

Fitted value iteration (FVI) with ordinary least squares regression is known to diverge. We present a new method, ""Expansion-Constrained Ordinary Least Squares"" (ECOLS), that produces a linear approximation but also guarantees convergence when used with FVI. To ensure convergence, we constrain the least squares regression operator to be a non-expansion in the infinity-norm. We show that the space of function approximators that satisfy this constraint is more rich than the space of ""averagers,"" we prove a minimax property of the ECOLS residual error, and we give an efficient algorithm for computing the coefficients of ECOLS based on constraint generation. We illustrate the algorithmic convergence of FVI with ECOLS in a suite of experiments, and discuss its properties.

Author Information

Daniel Lizotte (The University of Western Ontario)

More from the Same Authors