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

Abstract

The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space $\mathcal{S}$ and the action space $\mathcal{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 $|\mathcal{S}|\times |\mathcal{A}|$, which can be prohibitively large when $\mathcal{S}$ or $\mathcal{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 $\epsilon$-optimal policy (resp. Q-function) with high probability as soon as the sample size exceeds the order of $\frac{K}{(1-\gamma {)}^3{\epsilon }^2}$ (resp. $\frac{K}{(1-\gamma {)}^4{\epsilon }^2}$), up to some logarithmic factor. Here $K$ is the feature dimension and $\gamma \in (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.

References in corpus (10)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs

Cited by in corpus (2)

• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Improved Algorithms for Misspecified Linear Markov Decision Processes