Abstract: Based on work with Bastien Dubail and Stefan Stojanovic Abstract: Low-dimensional structure underlies many modern reinforcement learning (RL) algorithms. In steady state, Markov dynamics are trivially low-dimensional: after mixing, the dynamics are essentially rank one. But RL is concerned with finite-horizon problems, raising a natural question: how much low-dimensional structure is already present at finite horizons, before mixing? We study this question through the successor measure. While the successor measure itself need not be approximately low-rank, we show that low-rank structure naturally emerges after shifting it by only a small number of transitions. We characterize both this emerging structure and our ability to learn it efficiently through a new notion of spectral recoverability. To control this quantity, we introduce Type II Poincaré inequalities, a new class of functional inequalities for Markov chains that connect low-rank structure to local mixing. These inequalities show how mixing at different spatial and temporal scales determines when a compact representation of the dynamics emerges. This perspective naturally reveals a hierarchy of timescales in Markov dynamics and leads to new hierarchical RL algorithms that exploit it.

Bio: Alexandre Proutiere is a professor at the Decision and Control Systems division in the EECS school at KTH, Royal Institute of Technology. His research interests are Machine Learning and AI, reinforcement learning, unsupervised learning, statistics, stochastic processes, control; applications to communication and social networks, cybersecurity.