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 (8)

• 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
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Which Mutual-Information Representation Learning Objectives are Sufficient for Control?
• Bad-Policy Density: A Measure of Reinforcement Learning Hardness