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

• Learning Near Optimal Policies with Low Inherent Bellman Error
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• 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
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Provably Efficient Exploration in Policy Optimization
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Which Mutual-Information Representation Learning Objectives are Sufficient for Control?
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• When Is Generalizable Reinforcement Learning Tractable?
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Efficient Local Planning with Linear Function Approximation
• Bad-Policy Density: A Measure of Reinforcement Learning Hardness