Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
Gen Li, Yuting Wei, Yuejie Chi, Yuxin Chen
Operations Research · 2024 · Volume 72 · Issue 1
Abstract
This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator). We first consider γ -discounted infinite-horizon Markov decision processes (MDPs) with state space 𝒮 S and action space 𝒜 A . Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy has yet to be determined. In particular, all prior results suffer from a severe sample size barrier in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least | 𝒮 ‖ 𝒜 | ( 1 − 𝛾 ) 2 | S ‖ A | ( 1 − γ ) 2 . The current paper overcomes this barrier by certifying the minimax optimality of two algorithms—a perturbed model-based algorithm and a conservative model-based algorithm—as soon as the sample size exceeds the order of | 𝒮 ‖ 𝒜 | 1 − 𝛾 | S ‖ A | 1 − γ (modulo some log factor). Moving beyond infinite-horizon MDPs, we further study time-inhomogeneous finite-horizon MDPs and prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level. To the best of our knowledge, this work delivers the first minimax-optimal guarantees that accommodate the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically infeasible). Funding: Y. Wei is supported in part by the Google Research Scholar Award and the National Science Foundation [Grants CCF-2106778, DMS-2147546, and DMS-2143215]. Y. Chi is supported in part by the Office of Naval Research [Grants N00014-18-1-2142 and N00014-19-1-2404] and the National Science Foundation [Grants CCF-1806154, CCF-2007911, and CCF-2106778]. Y. Chen is supported in part by the Alfred P. Sloan Foundation [research fellowship], Google [research scholar award], the Air Force Office of Scientific Research [Grants FA9550-19-1-0030 and FA9550-22-1-0198], the Office of Naval Research [Grant N00014-22-1-2354], and the National Science Foundation [Grants CCF-2221009, CCF-1907661, DMS-2014279, IIS-2218713, and IIS-2218773]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2451 .
Keywords
Machine Learning and Data Science, model-based reinforcement learning, minimaxity, policy evaluation, generative model
Enable JavaScript for citation tools and additional paper interactions.