  Kernel-based reinforcement learning (KBRL) stands out among reinforcement
learning algorithms for its strong theoretical guarantees. By casting the
learning problem as a local kernel approximation, KBRL provides a way of
computing a decision policy which is statistically consistent and converges to
a unique solution. Unfortunately, the model constructed by KBRL grows with the
number of sample transitions, resulting in a computational cost that precludes
its application to large-scale or on-line domains. In this paper we introduce
an algorithm that turns KBRL into a practical reinforcement learning tool.
Kernel-based stochastic factorization (KBSF) builds on a simple idea: when a
transition matrix is represented as the product of two stochastic matrices, one
can swap the factors of the multiplication to obtain another transition matrix,
potentially much smaller, which retains some fundamental properties of its
precursor. KBSF exploits such an insight to compress the information contained
in KBRL's model into an approximator of fixed size. This makes it possible to
build an approximation that takes into account both the difficulty of the
problem and the associated computational cost. KBSF's computational complexity
is linear in the number of sample transitions, which is the best one can do
without discarding data. Moreover, the algorithm's simple mechanics allow for a
fully incremental implementation that makes the amount of memory used
independent of the number of sample transitions. The result is a kernel-based
reinforcement learning algorithm that can be applied to large-scale problems in
both off-line and on-line regimes. We derive upper bounds for the distance
between the value functions computed by KBRL and KBSF using the same data. We
also illustrate the potential of our algorithm in an extensive empirical study
in which KBSF is applied to difficult tasks based on real-world data.
