Useful Spatio-Temporal Abstractions in Reinforcement Learning?

One of the popular directions for scaling up reinforcement learning algorithms is the use of spatio-temporal abstractions. Typically this leads to hierarchical organization of both the state space and the policy space. While there has been a lot of work on learning with spatio-temporal abstractions, not much has been done on discovering useful abstractions. In this talk I will present two of our attempts at exploring this area. In the first part, I will introduce spatial abstractions derived from notions of metastability in a dynamical system. This is essentially a clustering algorithm that splits the state space along boundaries of rare transitions under a uniform random walk on the space. These clusters then induce temporal abstractions corresponding to policy fragments for transition between the metastable regions. In the second part of the talk I will present some results on using ideas from small-world networks for defining temporal abstractions. The goal is to convert the underlying problem into one of navigating on a “small-world”, with guarantees on existence of efficient solutions. The key factor in this work is that we do not attempt any careful analysis of the underlying structure, but add the temporal abstractions randomly. I will discuss some practical issues in implementing this procedure and future directions.