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

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 vertical bar S vertical bar x vertical bar A vertical bar, 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 epsilon-optimal policy (resp. Q-function) with high probability as soon as the sample size exceeds the order of K/(1-gamma)(4) epsilon(2) (resp. K/(1-gamma)(4) epsilon(2)), up to some logarithmic factor. Here K is the feature dimension and gamma is an element of (0, 1) is the discount factor of the MDP. The results is applicable to the tabular MDPs by taking the coordinate basis with K = vertical bar S vertical bar x vertical bar A vertical bar. 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.