mlsanityData to 7 Oct 2026

On the Model-Misspecification in Reinforcement Learning

arXiv 2306.10694 ↗First posted 19 Jun 2023cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

The success of reinforcement learning (RL) crucially depends on effective function approximation when dealing with complex ground-truth models. Existing sample-efficient RL algorithms primarily employ three approaches to function approximation: policy-based, value-based, and model-based methods. However, in the face of model misspecification (a disparity between the ground-truth and optimal function approximators), it is shown that policy-based approaches can be robust even when the policy function approximation is under a large locally-bounded misspecification error, with which the function class may exhibit a Omega(1) approximation error in specific states and actions, but remains small on average within a policy-induced state distribution. Yet it remains an open question whether similar robustness can be achieved with value-based and model-based approaches, especially with general function approximation. To bridge this gap, in this paper we present a unified theoretical framework for addressing model misspecification in RL. We demonstrate that, through meticulous algorithm design and sophisticated analysis, value-based and model-based methods employing general function approximation can achieve robustness under local misspecification error bounds. In particular, they can attain a regret bound of widetildeOleft(poly(d H)(√K + Kzeta) right), where d represents the complexity of the function class, H is the episode length, K is the total number of episodes, and zeta denotes the local bound for misspecification error. Furthermore, we propose an algorithmic framework that can achieve the same order of regret bound without prior knowledge of zeta, thereby enhancing its practical applicability.

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

Builds on

41 of 55 references.

References · 41

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  10. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  12. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
29 more
  1. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  2. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  3. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  4. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  5. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  6. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  7. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  8. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  9. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  10. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  11. 2021Adapting to Misspecification in Contextual Banditscited by 81
  12. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  13. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  14. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  15. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  16. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  17. 2017Misspecified Linear Banditscited by 41
  18. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  19. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  20. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  21. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  22. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  23. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  24. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  25. 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
  26. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  27. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  28. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
  29. 2023Low-Switching Policy Gradient with Exploration via Online Sensitivity Samplingcited by 6

Built on by

Cited by year (2026 to 7 Oct)

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

7 papers.

  1. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  2. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  3. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 6
  4. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  5. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 1
  6. 2026PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Searchcited by 0
  7. 2026Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPscited by 0