  We present and analyze the Krylov-Bellman Boosting (KBB) algorithm for policy
evaluation in general state spaces. It alternates between fitting the Bellman
residual using non-parametric regression (as in boosting), and estimating the
value function via the least-squares temporal difference (LSTD) procedure
applied with a feature set that grows adaptively over time. By exploiting the
connection to Krylov methods, we equip this method with two attractive
guarantees. First, we provide a general convergence bound that allows for
separate estimation errors in residual fitting and LSTD computation. Consistent
with our numerical experiments, this bound shows that convergence rates depend
on the restricted spectral structure, and are typically super-linear. Second,
by combining this meta-result with sample-size dependent guarantees for
residual fitting and LSTD computation, we obtain concrete statistical
guarantees that depend on the sample size along with the complexity of the
function class used to fit the residuals. We illustrate the behavior of the KBB
algorithm for various types of policy evaluation problems, and typically find
large reductions in sample complexity relative to the standard approach of
fitted value iterationn.
