mlsanityData to 14 Oct 2026

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

arXiv 2011.01075 ↗First posted 2 Nov 2020cs.LG cs.AI stat.MLcited by 25

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 4; 2023: 2; 2024: 4; 2025: 5; 2026: 2.

25 papers.

Sort:

By area:

  1. 2021Offline RL Without Off-Policy Evaluationcited by 151
  2. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  3. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 71
  4. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiencycited by 56
  5. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  6. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  7. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  8. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraintscited by 15
  9. 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Datacited by 11
  10. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
  11. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  12. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
13 more
  1. 2024The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regretcited by 6
  2. 2025Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocolcited by 6
  3. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  4. 2023The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimationcited by 3
  5. 2024Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrabilitycited by 3
  6. 2025Bellman Calibration for V-Learning in Offline Reinforcement Learningcited by 3
  7. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  8. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  9. 2025Fitted Q-Evaluation without Bellman Completeness via Occupancy Weightingcited by 2
  10. 2021The Impact of Data Distribution on Q-learning with Function Approximationcited by 1
  11. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  12. 2026A Unifying View of Coverage in Linear Off-Policy Evaluationcited by 1
  13. 2026Fitted Occupancy-Ratio Evaluation without Bellman Completenesscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2020Batch Value-function Approximation with Only Realizability
  2. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation
  3. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  4. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning
  5. 2026On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents
  6. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
  7. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
  8. 2021Continuous Doubly Constrained Batch Reinforcement Learning