mlsanityData to 7 Oct 2026

An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap

arXiv 2103.12690 ↗First posted 23 Mar 2021cs.LG cs.AI stat.MLcited by 40

Not on the map. Why?

Abstract (arXiv)

A fundamental question in the theory of reinforcement learning is: suppose the optimal Q-function lies in the linear span of a given d dimensional feature mapping, is sample-efficient reinforcement learning (RL) possible? The recent and remarkable result of Weisz et al. (2020) resolved this question in the negative, providing an exponential (in d) sample size lower bound, which holds even if the agent has access to a generative model of the environment. One may hope that this information theoretic barrier for RL can be circumvented by further supposing an even more favorable assumption: there exists a constant suboptimality gap between the optimal Q-value of the best action and that of the second-best action (for all states). The hope is that having a large suboptimality gap would permit easier identification of optimal actions themselves, thus making the problem tractable; indeed, provided the agent has access to a generative model, sample-efficient RL is in fact possible with the addition of this more favorable assumption. This work focuses on this question in the standard online reinforcement learning setting, where our main result resolves this question in the negative: our hardness result shows that an exponential sample complexity lower bound still holds even if a constant suboptimality gap is assumed in addition to having a linearly realizable optimal Q-function. Perhaps surprisingly, this implies an exponential separation between the online RL setting and the generative model setting. Complementing our negative hardness result, we give two positive results showing that provably sample-efficient RL is possible either under an additional low-variance assumption or under a novel hypercontractivity assumption (both implicitly place stronger conditions on the underlying dynamics model).

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). Builds on 34 of its 58 references that are in the map. First posted on arXiv 23 Mar 2021.

Builds on

34 of 58 references.

References · 34

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  10. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
22 more
  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  3. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  4. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  5. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  6. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  7. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  8. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  9. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  10. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  11. 2020DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correctioncited by 71
  12. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  13. 2020Q-learning with Logarithmic Regretcited by 59
  14. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  15. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  16. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  17. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
  18. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 24
  19. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
  20. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  21. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  22. 2019Comments on the Du-Kakade-Wang-Yang Lower Boundscited by 16

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 17; 2023: 6; 2024: 4; 2025: 4.

40 papers.

Sort:

By area:

  1. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  2. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  3. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  4. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  5. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  6. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  7. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  8. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  9. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  10. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  11. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  12. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
28 more
  1. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  2. 2021Improving Zero-shot Generalization in Offline Reinforcement Learning using Generalized Similarity Functionscited by 17
  3. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  4. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  5. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  6. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 14
  7. 2021A Boosting Approach to Reinforcement Learningcited by 12
  8. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  9. 2023Free from Bellman Completeness: Trajectory Stitching via Model-based Return-conditioned Supervised Learningcited by 11
  10. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  11. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  12. 2022Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPscited by 8
  13. 2021TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functionscited by 7
  14. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
  15. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
  16. 2022A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximationcited by 7
  17. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  18. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  19. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  20. 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximationcited by 4
  21. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?cited by 4
  22. 2022Computational-Statistical Gaps in Reinforcement Learningcited by 3
  23. 2025Bellman Calibration for V-Learning in Offline Reinforcement Learningcited by 2
  24. 2022Linear Reinforcement Learning with Ball Structure Action Spacecited by 1
  25. 2025Fitted Q-Evaluation without Bellman Completeness via Occupancy Weightingcited by 1
  26. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
  27. 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Errorcited by 0
  28. 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizabilitycited by 0