The Laplacian in Reinforcement Learning: Representation Learning with Efficient Approximations

Yifan Wu
Ofir Nachum
ICLR (2019)

Abstract

The smallest eigenvectors of the graph Laplacian are well-known to provide a
succinct representation of the geometry of a weighted graph. In reinforcement
learning (RL), where the weighted graph may be interpreted as the state transition
process induced by a behavior policy acting on the environment, approximating
the eigenvectors of the Laplacian provides a promising approach to state representation learning. However, existing methods for performing this approximation
are ill-suited in general RL settings for two main reasons: First, they are computationally expensive, often requiring operations on large matrices. Second, these
methods lack adequate justification beyond simple, tabular, finite-state settings.
In this paper, we present a fully general and scalable method for approximating
the eigenvectors of the Laplacian in a model-free RL context. We systematically
evaluate our approach and empirically show that it generalizes beyond the tabular,
finite-state setting. Even in tabular, finite-state settings, its ability to approximate
the eigenvectors outperforms previous proposals. Finally, we show the potential
benefits of using a Laplacian representation learned using our method in goalachieving RL tasks, providing evidence that our technique can be used to significantly improve the performance of an RL agent.

Research Areas