CISE Seminar: April 5, 2019 – Mengdi Wang, Princeton University

Recent years have witnessed increasing empirical successes in reinforcement learning. However, many statistical questions about reinforcement learning are not well understood even in the most basic setting. For example, how many sample transitions are needed and sufficient for estimating a near-optimal policy for Markov decision problem (MDP)?  In the first part, we survey recent advances on the methods and complexity for Markov decision problems (MDP) with finitely many state and actions – a most basic model for reinforcement learning. In the second part we study the statistical state compression of general finite-state Markov processes. We propose a spectral state compression method for learning state features and aggregation structures from data. The state compression method is able to “ sketch” a black-box Markov process from its empirical data, for which both minimax statistical guarantees and scalable computational tools are provided. In the third part, we propose a bilinear primal-dual pi learning method for learning the optimal policy of MDP, which utilizes given state features. The method is motivated from a saddle point formulation of the Bellman equation. Its sample complexity depends only on the number of parameters and is variant with respect to the dimension of the problem, making high-dimensional reinforcement learning possible using “small” data.