Comments on the Du-Kakade-Wang-Yang Lower Bounds

11/18/2019

∙

by   Benjamin Van Roy, et al.

∙

0

∙

share

Du, Kakade, Wang, and Yang recently established intriguing lower bounds on sample complexity, which suggest that reinforcement learning with a misspecified representation is intractable. Another line of work, which centers around a statistic called the eluder dimension, establishes tractability of problems similar to those considered in the Du-Kakade-Wang-Yang paper. We compare these results and reconcile interpretations.