  High-dimensional representations, such as radial basis function networks or
tile coding, are common choices for policy evaluation in reinforcement
learning. Learning with such high-dimensional representations, however, can be
expensive, particularly for matrix methods, such as least-squares temporal
difference learning or quasi-Newton methods that approximate matrix step-sizes.
In this work, we explore the utility of sketching for these two classes of
algorithms. We highlight issues with sketching the high-dimensional features
directly, which can incur significant bias. As a remedy, we demonstrate how to
use sketching more sparingly, with only a left-sided sketch, that can still
enable significant computational gains and the use of these matrix-based
learning algorithms that are less sensitive to parameters. We empirically
investigate these algorithms, in four domains with a variety of
representations. Our aim is to provide insights into effective use of sketching
in practice.
