mlsanityData to 7 Oct 2026

Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions

arXiv 2010.01374 ↗First posted 3 Oct 2020cs.LG cs.AI stat.MLcited by 71

Not on the map. Why?

Abstract (arXiv)

We consider the problem of local planning in fixed-horizon and discounted Markov Decision Processes (MDPs) with linear function approximation and a generative model under the assumption that the optimal action-value function lies in the span of a feature map that is available to the planner. Previous work has left open the question of whether there exist sound planners that need only poly(H,d) queries regardless of the MDP, where H is the horizon and d is the dimensionality of the features. We answer this question in the negative: we show that any sound planner must query at least min(exp(Omega(d)), Omega(2H)) samples in the fized-horizon setting and exp(Omega(d)) samples in the discounted setting. We also show that for any δ>0, the least-squares value iteration algorithm with O(H5dH+1/δ2) queries can compute a δ-optimal policy in the fixed-horizon setting. We discuss implications and remaining open questions.

Key facts. Cited by 71 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 24; 2022: 22; 2023: 13; 2024: 9; 2025: 2; 2026: 1.

71 papers.

Sort:

By area:

  1. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  2. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  3. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  4. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  5. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  7. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  8. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  9. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  10. 2022Retrieval-Augmented Reinforcement Learningcited by 53
  11. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  12. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
38 more
  1. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  2. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  3. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  4. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  5. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  6. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  7. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  8. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  9. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  10. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  11. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  12. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  13. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  14. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  15. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  16. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  17. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  18. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  19. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  20. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  21. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  22. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  23. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  24. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  25. 2023Free from Bellman Completeness: Trajectory Stitching via Model-based Return-conditioned Supervised Learningcited by 11
  26. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  27. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  28. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  29. 2022Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPscited by 8
  30. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  31. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  32. 2021TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functionscited by 7
  33. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
  34. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
  35. 2022A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximationcited by 7
  36. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  37. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  38. 2024Optimistic Information Directed Samplingcited by 7

50 most cited of 71 All 71 (JSON)