{"data":{"id":"10.48550/arxiv.2005.12900","type":"dois","attributes":{"doi":"10.48550/arxiv.2005.12900","prefix":"10.48550","suffix":"arxiv.2005.12900","identifiers":[{"identifier":"2005.12900","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"2005.12900"}],"creators":[{"name":"Li, Gen","nameType":"Personal","givenName":"Gen","familyName":"Li","affiliation":[],"nameIdentifiers":[]},{"name":"Wei, Yuting","nameType":"Personal","givenName":"Yuting","familyName":"Wei","affiliation":[],"nameIdentifiers":[]},{"name":"Chi, Yuejie","nameType":"Personal","givenName":"Yuejie","familyName":"Chi","affiliation":[],"nameIdentifiers":[]},{"name":"Chen, Yuxin","nameType":"Personal","givenName":"Yuxin","familyName":"Chen","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model"}],"publisher":"arXiv","container":{},"publicationYear":2020,"subjects":[{"lang":"en","subject":"Machine Learning (cs.LG)","subjectScheme":"arXiv"},{"lang":"en","subject":"Information Theory (cs.IT)","subjectScheme":"arXiv"},{"lang":"en","subject":"Optimization and Control (math.OC)","subjectScheme":"arXiv"},{"lang":"en","subject":"Statistics Theory (math.ST)","subjectScheme":"arXiv"},{"lang":"en","subject":"Machine Learning (stat.ML)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2020-05-26T17:53:18Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2020-05-27T00:22:08Z","dateType":"Updated","dateInformation":"v1"},{"date":"2020-06-17T17:50:39Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2020-06-18T00:21:39Z","dateType":"Updated","dateInformation":"v2"},{"date":"2020-09-03T02:02:42Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2020-09-04T00:07:12Z","dateType":"Updated","dateInformation":"v3"},{"date":"2021-12-25T21:39:28Z","dateType":"Submitted","dateInformation":"v4"},{"date":"2021-12-28T01:20:57Z","dateType":"Updated","dateInformation":"v4"},{"date":"2022-09-15T15:16:01Z","dateType":"Submitted","dateInformation":"v5"},{"date":"2022-09-16T00:19:37Z","dateType":"Updated","dateInformation":"v5"},{"date":"2022-09-16T00:48:47Z","dateType":"Submitted","dateInformation":"v6"},{"date":"2022-09-19T00:05:04Z","dateType":"Updated","dateInformation":"v6"},{"date":"2023-03-17T16:08:00Z","dateType":"Submitted","dateInformation":"v7"},{"date":"2023-03-20T00:17:22Z","dateType":"Updated","dateInformation":"v7"},{"date":"2023-04-17T15:37:59Z","dateType":"Submitted","dateInformation":"v8"},{"date":"2025-03-18T00:47:52Z","dateType":"Updated","dateInformation":"v8"},{"date":"2020-05","dateType":"Available","dateInformation":"v1"},{"date":"2020","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"8","rightsList":[{"rights":"Creative Commons Attribution 4.0 International","rightsUri":"https://creativecommons.org/licenses/by/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"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 $\\mathcal{S}$ and action space $\\mathcal{A}$. Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is 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 $\\frac{|\\mathcal{S}||\\mathcal{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 $\\frac{|\\mathcal{S}||\\mathcal{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).","descriptionType":"Abstract"},{"description":"accepted Operations Research","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4yMDA1LjEyOTAwPC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MjAwNS4xMjkwMDwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5MaSwgR2VuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5HZW48L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+TGk8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+V2VpLCBZdXRpbmc8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPll1dGluZzwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5XZWk8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+Q2hpLCBZdWVqaWU8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPll1ZWppZTwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5DaGk8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+Q2hlbiwgWXV4aW48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPll1eGluPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkNoZW48L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPkJyZWFraW5nIHRoZSBTYW1wbGUgU2l6ZSBCYXJyaWVyIGluIE1vZGVsLUJhc2VkIFJlaW5mb3JjZW1lbnQgTGVhcm5pbmcgd2l0aCBhIEdlbmVyYXRpdmUgTW9kZWw8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMjA8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChjcy5MRyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5JbmZvcm1hdGlvbiBUaGVvcnkgKGNzLklUKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPk9wdGltaXphdGlvbiBhbmQgQ29udHJvbCAobWF0aC5PQyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5TdGF0aXN0aWNzIFRoZW9yeSAobWF0aC5TVCk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChzdGF0Lk1MKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IENvbXB1dGVyIGFuZCBpbmZvcm1hdGlvbiBzY2llbmNlczwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IE1hdGhlbWF0aWNzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMC0wNS0yNlQxNzo1MzoxOFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMC0wNS0yN1QwMDoyMjowOFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIwLTA2LTE3VDE3OjUwOjM5WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIwLTA2LTE4VDAwOjIxOjM5WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMjAtMDktMDNUMDI6MDI6NDJaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMjAtMDktMDRUMDA6MDc6MTJaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2NCI+MjAyMS0xMi0yNVQyMTozOToyOFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2NCI+MjAyMS0xMi0yOFQwMToyMDo1N1o8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InY1Ij4yMDIyLTA5LTE1VDE1OjE2OjAxWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InY1Ij4yMDIyLTA5LTE2VDAwOjE5OjM3WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjYiPjIwMjItMDktMTZUMDA6NDg6NDdaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjYiPjIwMjItMDktMTlUMDA6MDU6MDRaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2NyI+MjAyMy0wMy0xN1QxNjowODowMFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2NyI+MjAyMy0wMy0yMFQwMDoxNzoyMlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InY4Ij4yMDIzLTA0LTE3VDE1OjM3OjU5WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InY4Ij4yMDI1LTAzLTE4VDAwOjQ3OjUyWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMjAtMDU8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlRleHQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8dmVyc2lvbj44PC92ZXJzaW9uPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHA6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LzQuMC8iIHJpZ2h0c0lkZW50aWZpZXJTY2hlbWU9IlNQRFgiIHJpZ2h0c0lkZW50aWZpZXI9IkNDLUJZLTQuMCI+Q3JlYXRpdmUgQ29tbW9ucyBBdHRyaWJ1dGlvbiA0LjAgSW50ZXJuYXRpb25hbDwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPlRoaXMgcGFwZXIgaXMgY29uY2VybmVkIHdpdGggdGhlIHNhbXBsZSBlZmZpY2llbmN5IG9mIHJlaW5mb3JjZW1lbnQgbGVhcm5pbmcsIGFzc3VtaW5nIGFjY2VzcyB0byBhIGdlbmVyYXRpdmUgbW9kZWwgKG9yIHNpbXVsYXRvcikuIFdlIGZpcnN0IGNvbnNpZGVyICTOsyQtZGlzY291bnRlZCBpbmZpbml0ZS1ob3Jpem9uIE1hcmtvdiBkZWNpc2lvbiBwcm9jZXNzZXMgKE1EUHMpIHdpdGggc3RhdGUgc3BhY2UgJFxtYXRoY2Fse1N9JCBhbmQgYWN0aW9uIHNwYWNlICRcbWF0aGNhbHtBfSQuIERlc3BpdGUgYSBudW1iZXIgb2YgcHJpb3Igd29ya3MgdGFja2xpbmcgdGhpcyBwcm9ibGVtLCBhIGNvbXBsZXRlIHBpY3R1cmUgb2YgdGhlIHRyYWRlLW9mZnMgYmV0d2VlbiBzYW1wbGUgY29tcGxleGl0eSBhbmQgc3RhdGlzdGljYWwgYWNjdXJhY3kgaXMgeWV0IHRvIGJlIGRldGVybWluZWQuIEluIHBhcnRpY3VsYXIsIGFsbCBwcmlvciByZXN1bHRzIHN1ZmZlciBmcm9tIGEgc2V2ZXJlIHNhbXBsZSBzaXplIGJhcnJpZXIsIGluIHRoZSBzZW5zZSB0aGF0IHRoZWlyIGNsYWltZWQgc3RhdGlzdGljYWwgZ3VhcmFudGVlcyBob2xkIG9ubHkgd2hlbiB0aGUgc2FtcGxlIHNpemUgZXhjZWVkcyBhdCBsZWFzdCAkXGZyYWN7fFxtYXRoY2Fse1N9fHxcbWF0aGNhbHtBfXx9eygxLc6zKV4yfSQuIFRoZSBjdXJyZW50IHBhcGVyIG92ZXJjb21lcyB0aGlzIGJhcnJpZXIgYnkgY2VydGlmeWluZyB0aGUgbWluaW1heCBvcHRpbWFsaXR5IG9mIHR3byBhbGdvcml0aG1zIC0tIGEgcGVydHVyYmVkIG1vZGVsLWJhc2VkIGFsZ29yaXRobSBhbmQgYSBjb25zZXJ2YXRpdmUgbW9kZWwtYmFzZWQgYWxnb3JpdGhtIC0tIGFzIHNvb24gYXMgdGhlIHNhbXBsZSBzaXplIGV4Y2VlZHMgdGhlIG9yZGVyIG9mICRcZnJhY3t8XG1hdGhjYWx7U318fFxtYXRoY2Fse0F9fH17MS3Os30kIChtb2R1bG8gc29tZSBsb2cgZmFjdG9yKS4gTW92aW5nIGJleW9uZCBpbmZpbml0ZS1ob3Jpem9uIE1EUHMsIHdlIGZ1cnRoZXIgc3R1ZHkgdGltZS1pbmhvbW9nZW5lb3VzIGZpbml0ZS1ob3Jpem9uIE1EUHMsIGFuZCBwcm92ZSB0aGF0IGEgcGxhaW4gbW9kZWwtYmFzZWQgcGxhbm5pbmcgYWxnb3JpdGhtIHN1ZmZpY2VzIHRvIGFjaGlldmUgbWluaW1heC1vcHRpbWFsIHNhbXBsZSBjb21wbGV4aXR5IGdpdmVuIGFueSB0YXJnZXQgYWNjdXJhY3kgbGV2ZWwuIFRvIHRoZSBiZXN0IG9mIG91ciBrbm93bGVkZ2UsIHRoaXMgd29yayBkZWxpdmVycyB0aGUgZmlyc3QgbWluaW1heC1vcHRpbWFsIGd1YXJhbnRlZXMgdGhhdCBhY2NvbW1vZGF0ZSB0aGUgZW50aXJlIHJhbmdlIG9mIHNhbXBsZSBzaXplcyAoYmV5b25kIHdoaWNoIGZpbmRpbmcgYSBtZWFuaW5nZnVsIHBvbGljeSBpcyBpbmZvcm1hdGlvbiB0aGVvcmV0aWNhbGx5IGluZmVhc2libGUpLjwvZGVzY3JpcHRpb24+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJPdGhlciI+YWNjZXB0ZWQgT3BlcmF0aW9ucyBSZXNlYXJjaDwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/2005.12900","contentUrl":null,"metadataVersion":5,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-02-25T21:43:30.000Z","registered":"2022-02-25T21:43:31.000Z","published":"2020","updated":"2025-03-18T04:09:31.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.2005.12900","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}