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

arXiv: https://arxiv.org/abs/2105.14016 · HTML: https://mlsanity.com/paper/2105.14016/

## 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 (most cited first, 30 of 34)

- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Efficient Exploration through Bayesian Deep Q-Networks](https://mlsanity.com/paper/1802.04412/) (2018)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Efficient Learning in Non-Stationary Linear Markov Decision Processes](https://mlsanity.com/paper/2010.12870/) (2020)
- [Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient](https://mlsanity.com/paper/2011.04019/) (2020)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [State Aggregation Learning from Markov Transition Data](https://mlsanity.com/paper/1811.02619/) (2018)

## Built on by (most cited first, 18 of 18)

- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [High-probability sample complexities for policy evaluation with linear function approximation](https://mlsanity.com/paper/2305.19001/) (2023)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [Near-optimal Policy Identification in Active Reinforcement Learning](https://mlsanity.com/paper/2212.09510/) (2022)
- [Improved Algorithms for Misspecified Linear Markov Decision Processes](https://mlsanity.com/paper/2109.05546/) (2021)
- [Reinforcement Learning with Function Approximation: From Linear to Nonlinear](https://mlsanity.com/paper/2302.09703/) (2023)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Multi-agent Policy Reciprocity with Theoretical Guarantee](https://mlsanity.com/paper/2304.05632/) (2023)
- [Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping](https://mlsanity.com/paper/2306.12981/) (2023)
- [The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure](https://mlsanity.com/paper/2410.21601/) (2024)
- [Distributionally Robust Online Markov Game with Linear Function Approximation](https://mlsanity.com/paper/2511.07831/) (2025)
- [Active Learning for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2605.24803/) (2026)
- [On the Benefits of Leveraging Structural Information in Planning Over the Learned Model](https://mlsanity.com/paper/2303.08856/) (2023)
- [Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2603.09208/) (2026)
- [Theoretical Foundations of max@k Reinforcement Learning](https://mlsanity.com/paper/2607.17823/) (2026)

## 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.