Basis Function Discovery Using Spectral Clustering and Bisimulation Metrics

By Gheorghe Comanici, Doina Precup. 2011

18 citations recorded by the source corpus.

We study the problem of automatically generating features for function approximation in reinforcement learning. We build on the work of Mahadevan and his colleagues, who pioneered the use of spectral clustering methods for basis function construction. Their methods work on top of a graph that captures state adjacency. Instead, we use bisimulation metrics in order to provide state distances for spectral clustering. The advantage of these metrics is that they incorporate reward information in a natural way, in addition to the state transition information. We provide theoretical bounds on the quality of the obtained approximation, which justify the importance of incorporating reward information. We also demonstrate empirically that the approximation quality improves when bisimulation metrics are used instead of the state adjacency graph in the basis function construction process.

Subfields: Artificial Intelligence, Molecular Biology, Representation & Self-Supervised Learning, Signal Processing

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

1. Sergey Levine
2. Ofir Nachum
3. Doina Precup
4. Carles Gelada
5. Pablo Samuel Castro
6. Marc G. Bellemare
7. Pieter Abbeel
8. Saurabh Kumar

In Molecular Biology

1. Prakash Panangaden
2. Sherry Shanshan Ruan
3. Doina Precup
4. Ofir Nachum
5. Marc G. Bellemare
6. Gheorghe Comanici
7. Saurabh Kumar
8. Carles Gelada

In Representation & Self-Supervised Learning

1. Ofir Nachum
2. Marc G. Bellemare
3. Jacob Buckman
4. Carles Gelada
5. Saurabh Kumar
6. Prakash Panangaden
7. Sherry Shanshan Ruan
8. Doina Precup

In Signal Processing

1. Prakash Panangaden
2. Sherry Shanshan Ruan
3. Doina Precup
4. Gheorghe Comanici
5. Marc G. Bellemare
6. Jacob Buckman

Citations in the corpus

• DeepMDP: Learning Continuous Latent Space Models for Representation Learning (2019, methodology): “Other representation learning approaches take the perspective that an optimal representation contains features that allow for the linear parametrization of the optimal value function (Comanici & Precup, 2011; Mahadevan & Maggioni, 2007).”
• Representation Discovery for MDPs Using Bisimulation Metrics (2015, methodology): “We will use Theorem 2 in Comanici et al. (2012).”