mlsanityData to 14 Oct 2026

Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model

arXiv 2105.14016 ↗First posted 28 May 2021cs.LG cs.IT math.ITcited by 18

Not on the map. Why?

Abstract (arXiv)

The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space S and the action space A are both finite, to obtain a nearly optimal policy with sampling access to a generative model, the minimax optimal sample complexity scales linearly with |S|×|A|, which can be prohibitively large when S or A is large. This paper considers a Markov decision process (MDP) that admits a set of state-action features, which can linearly express (or approximate) its probability transition kernel. We show that a model-based approach (resp.~Q-learning) provably learns an varepsilon-optimal policy (resp.~Q-function) with high probability as soon as the sample size exceeds the order of fracK(1-γ)3varepsilon2 (resp.~fracK(1-γ)4varepsilon2), up to some logarithmic factor. Here K is the feature dimension and γ∈(0,1) is the discount factor of the MDP. Both sample complexity bounds are provably tight, and our result for the model-based approach matches the minimax lower bound. Our results show that for arbitrarily large-scale MDP, both the model-based approach and Q-learning are sample-efficient when K is relatively small, and hence the title of this paper.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 34 of its 70 references that are in the map. First posted on arXiv 28 May 2021.

Builds on

34 of 70 references.

References · 34

  1. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  8. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  9. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  10. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  11. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  12. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
22 more
  1. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  2. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  3. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  4. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  5. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  6. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  7. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  8. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  9. 2018Efficient Exploration through Bayesian Deep Q-Networkscited by 67
  10. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  11. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  12. 2017Spectral Method and Regularized MLE Are Both Optimal for Top-K Rankingcited by 47
  13. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  14. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  15. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  16. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  17. 2020Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Datacited by 23
  18. 2018State Aggregation Learning from Markov Transition Datacited by 20
  19. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  20. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  21. 2020Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?cited by 9
  22. 2020Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 5; 2024: 1; 2025: 2; 2026: 3.

18 papers.

Sort:

By area:

  1. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  2. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  3. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  4. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  5. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  6. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
  7. 2022Near-optimal Policy Identification in Active Reinforcement Learningcited by 7
  8. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  9. 2023Reinforcement Learning with Function Approximation: From Linear to Nonlinearcited by 4
  10. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  11. 2023Multi-agent Policy Reciprocity with Theoretical Guaranteecited by 1
  12. 2023Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Groupingcited by 1
6 more
  1. 2024The Limits of Transfer Reinforcement Learning with Latent Low-rank Structurecited by 1
  2. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  3. 2026Active Learning for Stochastic Contextual Linear Banditscited by 1
  4. 2023On the Benefits of Leveraging Structural Information in Planning Over the Learned Modelcited by 0
  5. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximationcited by 0
  6. 2026Theoretical Foundations of max@k Reinforcement Learningcited by 0