mlsanityData to 7 Oct 2026

Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error

arXiv 2407.13622 ↗First posted 18 Jul 2024cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

The recent work by Dong & Yang (2023) showed for misspecified sparse linear bandits, one can obtain an Oleft(εright)-optimal policy using a polynomial number of samples when the sparsity is a constant, where ε is the misspecification error. This result is in sharp contrast to misspecified linear bandits without sparsity, which require an exponential number of samples to get the same guarantee. In order to study whether the analog result is possible in the reinforcement learning setting, we consider the following problem: assuming the optimal Q-function is a d-dimensional linear function with sparsity k and misspecification error ε, whether we can obtain an Oleft(εright)-optimal policy using number of samples polynomially in the feature dimension d. We first demonstrate why the standard approach based on Bellman backup or the existing optimistic value function elimination approach such as OLIVE (Jiang et al., 2017) achieves suboptimal guarantees for this problem. We then design a novel elimination-based algorithm to show one can obtain an Oleft(Hεright)-optimal policy with sample complexity polynomially in the feature dimension d and planning horizon H. Lastly, we complement our upper bound with an widetildeOmegaleft(Hεright) suboptimality lower bound, giving a complete picture of this problem.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 31 of its 43 references that are in the map. First posted on arXiv 18 Jul 2024.

Builds on

31 of 43 references.

References · 31

  1. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  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
19 more
  1. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  2. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  3. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  4. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  5. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  6. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  7. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  8. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  9. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  10. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 45
  11. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  12. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  13. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  14. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  15. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  16. 2023Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theorycited by 12
  17. 2021TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functionscited by 7
  18. 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learningcited by 4
  19. 2023Does Sparsity Help in Learning Misspecified Linear Bandits?cited by 3

Built on by

Not cited yet.