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

Abstract

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.

References in corpus (1)

• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?

Cited by in corpus (5)

• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Efficient Planning in Large MDPs with Weak Linear Function Approximation