# A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2020.

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

- [Offline RL Without Off-Policy Evaluation](https://mlsanity.com/paper/2106.08909/) (2021)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency](https://mlsanity.com/paper/2102.02981/) (2021)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Learning Bellman Complete Representations for Offline Policy Evaluation](https://mlsanity.com/paper/2207.05837/) (2022)
- [Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints](https://mlsanity.com/paper/2212.13861/) (2022)
- [Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data](https://mlsanity.com/paper/2403.17091/) (2024)
- [Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm](https://mlsanity.com/paper/2103.09847/) (2021)
- [Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees](https://mlsanity.com/paper/2510.04088/) (2025)
- [A Complete Characterization of Linear Estimators for Offline Policy Evaluation](https://mlsanity.com/paper/2203.04236/) (2022)
- [The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regret](https://mlsanity.com/paper/2406.15753/) (2024)
- [Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol](https://mlsanity.com/paper/2502.08021/) (2025)
- [The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2406.11686/) (2024)
- [The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimation](https://mlsanity.com/paper/2307.13332/) (2023)
- [Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrability](https://mlsanity.com/paper/2405.16809/) (2024)
- [Bellman Calibration for V-Learning in Offline Reinforcement Learning](https://mlsanity.com/paper/2512.23694/) (2025)
- [The Curse of Passive Data Collection in Batch Reinforcement Learning](https://mlsanity.com/paper/2106.09973/) (2021)
- [Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity](https://mlsanity.com/paper/2310.01616/) (2023)
- [Fitted Q-Evaluation without Bellman Completeness via Occupancy Weighting](https://mlsanity.com/paper/2512.23805/) (2025)
- [The Impact of Data Distribution on Q-learning with Function Approximation](https://mlsanity.com/paper/2111.11758/) (2021)
- [A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory](https://mlsanity.com/paper/2508.07746/) (2025)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [Fitted Occupancy-Ratio Evaluation without Bellman Completeness](https://mlsanity.com/paper/2607.05375/) (2026)

## Abstract (arXiv)

Recently, Wang et al. (2020) showed a highly intriguing hardness result for batch reinforcement learning (RL) with linearly realizable value function and good feature coverage in the finite-horizon case. In this note we show that once adapted to the discounted setting, the construction can be simplified to a 2-state MDP with 1-dimensional features, such that learning is impossible even with an infinite amount of data.