The Laplacian in RL: Learning Representations with Efficient Approximations

By Yifan Wu, George Tucker, Ofir Nachum. 2018

119 citations recorded by the source corpus.

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 goal-achieving RL tasks, providing evidence that our technique can be used to significantly improve the performance of an RL agent.

Subfields: Artificial Intelligence, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

Representation Matters: Offline Pretraining for Sequential Decision Making (2021, background): “Contrastive Objectives Beyond model-based representations, many previous works propose the use of contrastive losses as a way of learning useful state representations (Wu et al., 2018; Nachum et al., 2018; Srinivas et al., 2020; Stooke et al., 2020).”
Search on the Replay Buffer: Bridging Planning and Reinforcement Learning (2019, methodology): “While most methods (Florensa et al., 2019; Savinov et al., 2018b; Wu et al., 2018) simply perform RL on top of the learned representation, our method explicitly performs search using the learned metric.”
Contrastive Learning as Goal-Conditioned Reinforcement Learning (2022, methodology): “…these methods typically require additional supervision to drive representation learning (manually-specified reward functions or features), our method is more similar to prior work that estimates the discounted state occupancy measure as an inner product between learned representations [11, 131].”