It is believed that a model-based approach for reinforcement learning (RL) is the key to reduce sample complexity. However, the understanding of the sample optimality of model-based RL is still largely missing, even for the linear case. This work considers sample complexity of finding an $\epsilon$-optimal policy in a Markov decision process (MDP) that admits a linear additive feature representation, given only access to a generative model. We solve this problem via a plug-in solver approach, which builds an empirical model and plans in this empirical model via an arbitrary plug-in solver. We prove that under the anchor-state assumption, which implies implicit non-negativity in the feature space, the minimax sample complexity of finding an $\epsilon$-optimal policy in a $\gamma$-discounted MDP is $O(K/(1-\gamma)^3\epsilon^2)$, which only depends on the dimensionality $K$ of the feature space and has no dependence on the state or action space. We further extend our results to a relaxed setting where anchor-states may not exist and show that a plug-in approach can be sample efficient as well, providing a flexible approach to design model-based algorithms for RL.

Weaknesses: Despite the near-optimal sample complexity bounds presented in the paper, the paper seems to fall short significantly on novelty and significance issue. Details below: Discussion on related work: The pitch of the paper is made in a way which suggests that there are no results on model-based RL when function approximation is used. However, recently, there have been many papers which look at model-based algorithms: Wen et al 2019 (which is cited in the paper) is said to be a model-based method whereas it clearly studies model-based RL. If one looks at the corresponding LQR like problems, effectively all results are model-based. Pires and Szepesvari (COLT 2016) discuss policy error bounds in model based RL.

The paper provides nice near-optimal sample complexity results for a setting of feature-based MBRL. The results are nontrivial extensions of previous tabular results. On the other hand, it requires a pretty strong anchor-state assumption, which to some extent limits the significance of the results.

It is believed that a model-based approach for reinforcement learning (RL) is the key to reduce sample complexity. However, the understanding of the sample optimality of model-based RL is still largely missing, even for the linear case. This work considers sample complexity of finding an \epsilon -optimal policy in a Markov decision process (MDP) that admits a linear additive feature representation, given only access to a generative model. We solve this problem via a plug-in solver approach, which builds an empirical model and plans in this empirical model via an arbitrary plug-in solver. We prove that under the anchor-state assumption, which implies implicit non-negativity in the feature space, the minimax sample complexity of finding an \epsilon -optimal policy in a \gamma -discounted MDP is O(K/(1-\gamma) 3\epsilon 2), which only depends on the dimensionality K of the feature space and has no dependence on the state or action space. We further extend our results to a relaxed setting where anchor-states may not exist and show that a plug-in approach can be sample efficient as well, providing a flexible approach to design model-based algorithms for RL.