Comments on the Du-Kakade-Wang-Yang Lower Bounds
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Nov 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 11; 2022: 2; 2023: 2; 2024: 1.
16 papers.
Sort:
- 2021On The Effect of Auxiliary Tasks on Representation Dynamicscited by 56
- 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
- 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
- 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
- 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
- 2021Which Mutual-Information Representation Learning Objectives are Sufficient for Control?cited by 28
- 2021Efficient Local Planning with Linear Function Approximationcited by 21
- 2021When Is Generalizable Reinforcement Learning Tractable?cited by 19
- 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
- 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
- 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
- 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycited by 6
4 more
- 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
- 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settingscited by 5
- 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learningcited by 4
- 2021Bad-Policy Density: A Measure of Reinforcement Learning Hardnesscited by 2
- 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning22 Jan 2024
- 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo29 May 2023
- 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits16 Mar 2023
- 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning5 Oct 2022
- 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluation8 Mar 2022
- 2021Misspecified Gaussian Process Bandit Optimization9 Nov 2021
- 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings30 Oct 2021
- 2021Bad-Policy Density: A Measure of Reinforcement Learning Hardness7 Oct 2021
- 2021Efficient Local Planning with Linear Function Approximation12 Aug 2021
- 2021Bayesian decision-making under misspecified priors with applications to meta-learning3 Jul 2021
- 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity15 Jun 2021
- 2021Which Mutual-Information Representation Learning Objectives are Sufficient for Control?14 Jun 2021
4 more
- 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap23 Mar 2021
- 2021On The Effect of Auxiliary Tasks on Representation Dynamics25 Feb 2021
- 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function3 Feb 2021
- 2021When Is Generalizable Reinforcement Learning Tractable?1 Jan 2021
- 2021On The Effect of Auxiliary Tasks on Representation Dynamicscited by 56
- 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
- 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
- 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
- 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
- 2021Which Mutual-Information Representation Learning Objectives are Sufficient for Control?cited by 28
- 2021Efficient Local Planning with Linear Function Approximationcited by 21
- 2021When Is Generalizable Reinforcement Learning Tractable?cited by 19
- 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
- 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
- 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
- 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycited by 6
12 most cited of 16 All 16 (JSON)
- 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning22 Jan 2024
- 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo29 May 2023
- 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits16 Mar 2023
- 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning5 Oct 2022
- 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluation8 Mar 2022
- 2021Misspecified Gaussian Process Bandit Optimization9 Nov 2021
- 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings30 Oct 2021
- 2021Bad-Policy Density: A Measure of Reinforcement Learning Hardness7 Oct 2021
- 2021Efficient Local Planning with Linear Function Approximation12 Aug 2021
- 2021Bayesian decision-making under misspecified priors with applications to meta-learning3 Jul 2021
- 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity15 Jun 2021
- 2021Which Mutual-Information Representation Learning Objectives are Sufficient for Control?14 Jun 2021
12 newest of 16 All 16 (JSON)