mlsanityData to 7 Oct 2026

Exponential Hardness of Reinforcement Learning with Linear Function Approximation

arXiv 2302.12940 ↗First posted 25 Feb 2023cs.LG cs.AI cs.CCcited by 4

Not on the map. Why?

Abstract (arXiv)

A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterpart in supervised learning, linear regression, can be solved both statistically and computationally efficiently. Therefore, it was quite surprising when a recent work citekane2022computational showed a computational-statistical gap for linear reinforcement learning: even though there are polynomial sample-complexity algorithms, unless NP = RP, there are no polynomial time algorithms for this setting. In this work, we build on their result to show a computational lower bound, which is exponential in feature dimension and horizon, for linear reinforcement learning under the Randomized Exponential Time Hypothesis. To prove this we build a round-based game where in each round the learner is searching for an unknown vector in a unit hypercube. The rewards in this game are chosen such that if the learner achieves large reward, then the learner's actions can be used to simulate solving a variant of 3-SAT, where (a) each variable shows up in a bounded number of clauses (b) if an instance has no solutions then it also has no solutions that satisfy more than (1-ε)-fraction of clauses. We use standard reductions to show this 3-SAT variant is approximately as hard as 3-SAT. Finally, we also show a lower bound optimized for horizon dependence that almost matches the best known upper bound of exp(√H).

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 26 of its 41 references that are in the map. First posted on arXiv 25 Feb 2023.

Builds on

26 of 41 references.

References · 26

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  11. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  12. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
14 more
  1. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  2. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  3. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  4. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  5. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  6. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  7. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  8. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  9. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  10. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  11. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  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. 2022Computational-Statistical Gaps in Reinforcement Learningcited by 3

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 2.

4 papers.

  1. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  2. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  3. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  4. 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizabilitycited by 0