Representation Discovery for MDPs Using Bisimulation Metrics

By Sherry Shanshan Ruan, Gheorghe Comanici, Prakash Panangaden, Doina Precup. 2015

20 citations recorded by the source corpus.

We provide a novel, flexible, iterative refinement algorithm to automatically construct an approximate statespace representation for Markov Decision Processes (MDPs). Our approach leverages bisimulation metrics, which have been used in prior work to generate features to represent the state space of MDPs.We address a drawback of this approach, which is the expensive computation of the bisimulation metrics. We propose an algorithm to generate an iteratively improving sequence of state space partitions. Partial metric computations guide the representation search and provide much lower space and computational complexity, while maintaining strong convergence properties. We provide theoretical results guaranteeing convergence as well as experimental illustrations of the accuracy and savings (in time and memory usage) of the new algorithm, compared to traditional bisimulation metric computation.

Subfields: Reinforcement Learning, Representation & Self-Supervised Learning

How researchers see this paper

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

In Reinforcement Learning

In Representation & Self-Supervised Learning

Citations in the corpus

DeepMDP: Learning Continuous Latent Space Models for Representation Learning (2019, methodology): “Furthermore, state aggregation techniques, whether based on bisimulation or other methods (Abel et al., 2017; Li et al., 2006; Singh et al., 1995; Givan et al., 2003; Jiang et al., 2015; Ruan et al., 2015), suffer from poor compatibility with function approximation methods.”
A Geometric Perspective on Optimal Representations for Reinforcement Learning (2019, methodology): “…the celebrated proto-value functions (Mahadevan and Maggioni, 2007), a number of works (we note Dayan, 1993; Petrik, 2007; Mahadevan and Liu, 2010; Ruan et al., 2015; Bar-reto et al., 2017) have used characteristics of the transition structure of the MDP to generate representations; these are the…”
Scalable methods for computing state similarity in deterministic Markov Decision Processes (2019, methodology): “…properties render them appealing for planning and learning, and they have previously been used for state aggregation (Ferns, Panangaden, and Precup 2004; Ferns et al. 2006), policy transfer (Castro and Precup 2010), representation discovery (Ruan et al. 2015), and exploration (Santara et al. 2019).”