We investigate the sample efficiency of reinforcement learning in a $\gamma$-discounted infinite-horizon Markov decision process (MDP) with state space S and action space A, assuming access to a generative model. Despite a number of prior work tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is yet to be determined. In particular, prior results suffer from a sample size barrier, in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least $ |S| |A| / (1-\gamma)^2 $ (up to some log factor). The current paper overcomes this barrier by certifying the minimax optimality of model-based reinforcement learning as soon as the sample size exceeds the order of $ |S| |A| / (1-\gamma) $ (modulo some log factor). More specifically, a perturbed model-based planning algorithm provably finds an $\epsilon$-optimal policy with an order of $ |S| |A| / ((1-\gamma)^3\epsilon^2) $ samples (up to log factor) for any $0 < \epsilon < 1/(1-\gamma)$. Along the way, we derive improved (instance-dependent) guarantees for model-based policy evaluation. To the best of our knowledge, this work provides the first minimax-optimal guarantee in a generative model that accommodates the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically impossible).

Weaknesses: The significance of "breaking the barrier" is somewhat suspicious since it appears to be relevant only when there is a lower bound assumption on the accuracy epsilon, which is a bit strange since we want the accuracy to be high, so the error epsilon to be low. In particular, it doesn't appear to improve on previous results if we make epsilon a constant, for example. EDIT: Thank you to the authors for your response. Here is a bit more explanation of my concern. My comment was inspired by thinking about what are the conditions under which the new bound derived by the authors is actually a strict improvement over the previous bound.

The reviewers appreciated the efforts made by the authors in the rebuttal and updated their reviews accordingly. The reviewers are now all positive about the paper. They are aware that the improvements of the results concern specific regimes for \epsilon, \gamma, but appreciate the results on this fundamental problem. We recommend the paper for acceptance and encourage the authors to account for the reviewers' comments when preparing the camera-ready version of the paper.

We investigate the sample efficiency of reinforcement learning in a \gamma -discounted infinite-horizon Markov decision process (MDP) with state space S and action space A, assuming access to a generative model. Despite a number of prior work tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is yet to be determined. In particular, prior results suffer from a sample size barrier, in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least S A / (1-\gamma) 2 (up to some log factor). The current paper overcomes this barrier by certifying the minimax optimality of model-based reinforcement learning as soon as the sample size exceeds the order of S A / (1-\gamma) (modulo some log factor). More specifically, a perturbed model-based planning algorithm provably finds an \epsilon -optimal policy with an order of S A / ((1-\gamma) 3\epsilon 2) samples (up to log factor) for any 0 \epsilon 1/(1-\gamma) .