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

2019/11/18 by Van Roy, Benjamin, Dong, Shi
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1911.07910

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.

Related

• Eluder dimension: localise it!
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Model-based Reinforcement Learning and the Eluder Dimension
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient