# Effective sketching methods for value function approximation

arXiv: https://arxiv.org/abs/1708.01298 · HTML: https://mlsanity.com/paper/1708.01298/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2017.

## Built on by (most cited first, 3 of 3)

- [Reinforcement Learning in Dynamic Treatment Regimes Needs Critical Reexamination](https://mlsanity.com/paper/2405.18556/) (2024)
- [An MRP Formulation for Supervised Learning: Generalized Temporal Difference Learning Models](https://mlsanity.com/paper/2404.15518/) (2024)
- [Value Bonuses using Ensemble Errors for Exploration in Reinforcement Learning](https://mlsanity.com/paper/2602.12375/) (2026)

## Abstract (arXiv)

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.