The smallest eigenvectors of the graph Laplacian are well-known to provide asuccinct representation of the geometry of a weighted graph. In reinforcementlearning (RL), where the weighted graph may be interpreted as the statetransition process induced by a behavior policy acting on the environment,approximating the eigenvectors of the Laplacian provides a promising approachto state representation learning. However, existing methods for performing thisapproximation are ill-suited in general RL settings for two main reasons:First, they are computationally expensive, often requiring operations on largematrices. Second, these methods lack adequate justification beyond simple,tabular, finite-state settings. In this paper, we present a fully general andscalable method for approximating the eigenvectors of the Laplacian in amodel-free RL context. We systematically evaluate our approach and empiricallyshow that it generalizes beyond the tabular, finite-state setting. Even intabular, finite-state settings, its ability to approximate the eigenvectorsoutperforms previous proposals. Finally, we show the potential benefits ofusing a Laplacian representation learned using our method in goal-achieving RLtasks, providing evidence that our technique can be used to significantlyimprove the performance of an RL agent.