On Provably Efficient Reinforcement Learning with Value Function Approximation

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, the understanding of function approximation schemes is still largely missing. In this talk, we will discuss recent progress on understanding efficient RL algorithms with function approximation. In particular, we show that, RL problems whose optimal Q-values admit approximated linear representations can be provably hard, i.e., any algorithm solving this class of problems requires an exponential number of samples. Then we show that such an exponential barrier can be overcome by exploiting structures in the transition model: probably efficient algorithms exist for Markov decision processes with linear function approximation if the features encode model information. Lastly, we generalize algorithms in the linear setting to algorithms with general value function approximation.

Dr. YANG Lin is an assistant professor in the Electrical and Computer Engineering Department at the University of California, Los Angeles. His current research focus is on reinforcement learning theory and applications, learning for control, non-convex optimization, and streaming algorithms. Previously, he was a postdoc at Princeton University working with Prof. Mengdi Wang. He obtained two Ph.D. degrees (in Computer Science and in Physics & Astronomy) simultaneously, from Johns Hopkins University. Prior to that, he obtained a Bachelor's degree in Physics & Math from Tsinghua University.  He was a recipient of the Simons-Berkeley Research Fellowship and Dean Robert H. Roy Fellowship.