|
Abstract:
|
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 a large barrier (up to some log factor). In this talk, we break this barrier by certifying the minimax optimality of model-based reinforcement learning as soon as the sample size exceeds the order of SA/(1-gamma). 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).
|
