mlsanityData to 7 Oct 2026

Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting

arXiv 2105.08024 ↗First posted 17 May 2021cs.LG cs.IT math.ITcited by 27

Not on the map. Why?

Abstract (arXiv)

Low-complexity models such as linear function representation play a pivotal role in enabling sample-efficient reinforcement learning (RL). The current paper pertains to a scenario with value-based linear representation, which postulates the linear realizability of the optimal Q-function (also called the "linear Qstar problem"). While linear realizability alone does not allow for sample-efficient solutions in general, the presence of a large sub-optimality gap is a potential game changer, depending on the sampling mechanism in use. Informally, sample efficiency is achievable with a large sub-optimality gap when a generative model is available but is unfortunately infeasible when we turn to standard online RL settings. In this paper, we make progress towards understanding this linear Qstar problem by investigating a new sampling protocol, which draws samples in an online/exploratory fashion but allows one to backtrack and revisit previous states in a controlled and infrequent manner. This protocol is more flexible than the standard online RL setting, while being practically relevant and far more restrictive than the generative model. We develop an algorithm tailored to this setting, achieving a sample complexity that scales polynomially with the feature dimension, the horizon, and the inverse sub-optimality gap, but not the size of the state/action space. Our findings underscore the fundamental interplay between sampling protocols and low-complexity structural representation in RL.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 42 of its 75 references that are in the map. First posted on arXiv 17 May 2021.

Builds on

42 of 75 references.

References · 42

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  12. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
30 more
  1. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  2. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  5. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  6. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  7. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  8. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  9. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  10. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  11. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  12. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  13. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  14. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  15. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  16. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  17. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  18. 2020Q-learning with Logarithmic Regretcited by 59
  19. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  20. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  21. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  22. 2018Balanced Linear Contextual Banditscited by 30
  23. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  24. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  25. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  26. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  27. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19
  28. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  29. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  30. 2021An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximationcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 7; 2023: 6; 2024: 6; 2025: 1; 2026: 3.

27 papers.

Sort:

By area:

  1. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  2. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  3. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  4. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  5. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  6. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  7. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  8. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  9. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  10. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  11. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  12. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
15 more
  1. 2023Sample Efficient Deep Reinforcement Learning via Local Planningcited by 9
  2. 2022Towards Painless Policy Optimization for Constrained MDPscited by 8
  3. 2022A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximationcited by 7
  4. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  5. 2024Unraveling the Interplay between Carryover Effects and Reward Autocorrelations in Switchback Experimentscited by 6
  6. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  7. 2021Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Spacecited by 4
  8. 2023Reinforcement Learning with Function Approximation: From Linear to Nonlinearcited by 4
  9. 2025Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Functioncited by 4
  10. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  11. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
  12. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
  13. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamicscited by 0
  14. 2026Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Explorationcited by 0
  15. 2026Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPscited by 0