Bastien Dubail

Emergence of low-rank structures in Reinforcement Learning

Low-rank structure is a common implicit assumption in many modern reinforcement learning (RL) algorithms. In this talk, I will present novel insights into how such structures arise naturally from the dynamics, focusing on the problem of estimating the successor measure, a matrix representation that encodes future state occupancies and maps reward to value functions. Successor representations have attracted considerable attention among deep RL practitioners and have been claimed to exhibit better low-rank structures than say, transition matrices. Our work investigates and challenges this claim. We show that that successor measures typically do not exhibit low-rank structure, and thus introduce a variant, shifted successor measures, to enhance low-rank properties. Drawing on ideas from Markov chain analysis and matrix completion, we establish a sample complexity upper bound on the estimation of shifted successor measures. I will conclude with numerical results showing improved performance in a simple goal-conditioned RL setting.