Effective sketching methods for value function approximation
This work addresses computational bottlenecks for practitioners using matrix-based learning algorithms in reinforcement learning, though it is incremental as it builds on existing sketching techniques.
The paper tackles the computational expense of high-dimensional representations in reinforcement learning by proposing a left-sided sketching method that reduces bias and enables significant computational gains, achieving up to 50% faster convergence in some domains.
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.