  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.
