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

arXiv: https://arxiv.org/abs/1911.07910 · HTML: https://mlsanity.com/paper/1911.07910/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2019.

## Built on by (most cited first, 17 of 17)

- [On The Effect of Auxiliary Tasks on Representation Dynamics](https://mlsanity.com/paper/2102.13089/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Which Mutual-Information Representation Learning Objectives are Sufficient for Control?](https://mlsanity.com/paper/2106.07278/) (2021)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [When Is Generalizable Reinforcement Learning Tractable?](https://mlsanity.com/paper/2101.00300/) (2021)
- [On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function](https://mlsanity.com/paper/2102.02049/) (2021)
- [Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning](https://mlsanity.com/paper/2210.02087/) (2022)
- [A Complete Characterization of Linear Estimators for Offline Policy Evaluation](https://mlsanity.com/paper/2203.04236/) (2022)
- [Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity](https://mlsanity.com/paper/2106.07814/) (2021)
- [On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits](https://mlsanity.com/paper/2303.09390/) (2023)
- [Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings](https://mlsanity.com/paper/2111.00185/) (2021)
- [Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning](https://mlsanity.com/paper/2401.12216/) (2024)
- [Bad-Policy Density: A Measure of Reinforcement Learning Hardness](https://mlsanity.com/paper/2110.03424/) (2021)
- [Pointwise or Pairwise: When Do Pairwise Losses Help Reward Learning, Provably?](https://mlsanity.com/paper/2609.37209/) (2026)

## 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.