On The Hardness of Reinforcement Learning With Value-Function Approximation (and The Lack of Understanding Thereof)

  • Nan Jiang | University of Michigan

Value-function approximation methods that operate in batch mode have foundational importance to reinforcement learning (RL). Finite sample guarantees for these methods—which provide the theoretical backbones for empirical (“deep”) RL today—crucially rely on strong representation assumptions, e.g., that the function class is closed under Bellman update. Given that such assumptions are much stronger and less desirable than the ones needed for supervised learning (e.g., realizability), it is important to confirm the hardness of learning in their absence. Such a hardness result would also be a crucial piece of a bigger picture on the tractability of various RL settings. Unfortunately, while algorithm-specific lower bound has existed for decades, the information-theoretic hardness remains a mystery. In this talk I will introduce the mathematical setup for studying value-function approximation, introduce our findings in the investigation of the hardness conjecture, and discuss connections to related results/open problems and their implications. Part of the talk will be based on work with my student Jinglin Chen accepted to ICML-19.

[SLIDES]

Speaker Details

Nan Jiang is a PhD candidate at Computer Science and Engineering in University of Michigan, advised by Satinder Singh. His primary research area is reinforcement learning, with a focus on understanding the sample efficiency of RL algorithms and developing theoretical analyses that provide practical insights. His secondary research area is spectral learning of dynamical systems from time series data. Nan received his bachelor degree in Control and Automation from Tsinghua University in 2011. He interned at MSR Redmond in 2015, and at MSR NYC in 2016. He was the winner of the Best Paper Award at AAMAS 2015, and recipient of Rackham Predoctoral Fellowship in 2016.

Series: Microsoft Research Talks