{"data":{"id":"10.48550/arxiv.2106.11692","type":"dois","attributes":{"doi":"10.48550/arxiv.2106.11692","prefix":"10.48550","suffix":"arxiv.2106.11692","identifiers":[{"identifier":"2106.11692","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"2106.11692"}],"creators":[{"name":"Yang, Yunchang","nameType":"Personal","givenName":"Yunchang","familyName":"Yang","affiliation":[],"nameIdentifiers":[]},{"name":"Wu, Tianhao","nameType":"Personal","givenName":"Tianhao","familyName":"Wu","affiliation":[],"nameIdentifiers":[]},{"name":"Zhong, Han","nameType":"Personal","givenName":"Han","familyName":"Zhong","affiliation":[],"nameIdentifiers":[]},{"name":"Garcelon, Evrard","nameType":"Personal","givenName":"Evrard","familyName":"Garcelon","affiliation":[],"nameIdentifiers":[]},{"name":"Pirotta, Matteo","nameType":"Personal","givenName":"Matteo","familyName":"Pirotta","affiliation":[],"nameIdentifiers":[]},{"name":"Lazaric, Alessandro","nameType":"Personal","givenName":"Alessandro","familyName":"Lazaric","affiliation":[],"nameIdentifiers":[]},{"name":"Wang, Liwei","nameType":"Personal","givenName":"Liwei","familyName":"Wang","affiliation":[],"nameIdentifiers":[]},{"name":"Du, Simon S.","nameType":"Personal","givenName":"Simon S.","familyName":"Du","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning"}],"publisher":"arXiv","container":{},"publicationYear":2021,"subjects":[{"lang":"en","subject":"Machine Learning (cs.LG)","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)"}],"contributors":[],"dates":[{"date":"2021-06-22T11:52:04Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2021-06-23T00:18:39Z","dateType":"Updated","dateInformation":"v1"},{"date":"2022-03-16T09:29:18Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2022-03-17T00:24:04Z","dateType":"Updated","dateInformation":"v2"},{"date":"2021-06","dateType":"Available","dateInformation":"v1"},{"date":"2021","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"2","rightsList":[{"rights":"Creative Commons Attribution Non Commercial Share Alike 4.0 International","rightsUri":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-nc-sa-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"In this paper, we present a reduction-based framework for conservative bandits and RL, in which our core technique is to calculate the necessary and sufficient budget obtained from running the baseline policy. For lower bounds, we improve the existing lower bound for conservative multi-armed bandits and obtain new lower bounds for conservative linear bandits, tabular RL and low-rank MDP, through a black-box reduction that turns a certain lower bound in the nonconservative setting into a new lower bound in the conservative setting. For upper bounds, in multi-armed bandits, linear bandits and tabular RL, our new upper bounds tighten or match existing ones with significantly simpler analyses. We also obtain a new upper bound for conservative low-rank MDP.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4yMTA2LjExNjkyPC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MjEwNi4xMTY5MjwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5ZYW5nLCBZdW5jaGFuZzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+WXVuY2hhbmc8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+WWFuZzwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5XdSwgVGlhbmhhbzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+VGlhbmhhbzwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5XdTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5aaG9uZywgSGFuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5IYW48L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+Wmhvbmc8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+R2FyY2Vsb24sIEV2cmFyZDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+RXZyYXJkPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkdhcmNlbG9uPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPlBpcm90dGEsIE1hdHRlbzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+TWF0dGVvPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlBpcm90dGE8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+TGF6YXJpYywgQWxlc3NhbmRybzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+QWxlc3NhbmRybzwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5MYXphcmljPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPldhbmcsIExpd2VpPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5MaXdlaTwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5XYW5nPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkR1LCBTaW1vbiBTLjwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+U2ltb24gUy48L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+RHU8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPkEgUmVkdWN0aW9uLUJhc2VkIEZyYW1ld29yayBmb3IgQ29uc2VydmF0aXZlIEJhbmRpdHMgYW5kIFJlaW5mb3JjZW1lbnQgTGVhcm5pbmc8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMjE8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChjcy5MRyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChzdGF0Lk1MKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IENvbXB1dGVyIGFuZCBpbmZvcm1hdGlvbiBzY2llbmNlczwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxkYXRlcz4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMjEtMDYtMjJUMTE6NTI6MDRaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMjEtMDYtMjNUMDA6MTg6MzlaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAyMi0wMy0xNlQwOToyOToxOFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAyMi0wMy0xN1QwMDoyNDowNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIxLTA2PC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJQcmVwcmludCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDx2ZXJzaW9uPjI8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbGljZW5zZXMvYnktbmMtc2EvNC4wLyIgcmlnaHRzSWRlbnRpZmllclNjaGVtZT0iU1BEWCIgcmlnaHRzSWRlbnRpZmllcj0iQ0MtQlktTkMtU0EtNC4wIj5DcmVhdGl2ZSBDb21tb25zIEF0dHJpYnV0aW9uIE5vbiBDb21tZXJjaWFsIFNoYXJlIEFsaWtlIDQuMCBJbnRlcm5hdGlvbmFsPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0PgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+SW4gdGhpcyBwYXBlciwgd2UgcHJlc2VudCBhIHJlZHVjdGlvbi1iYXNlZCBmcmFtZXdvcmsgZm9yIGNvbnNlcnZhdGl2ZSBiYW5kaXRzIGFuZCBSTCwgaW4gd2hpY2ggb3VyIGNvcmUgdGVjaG5pcXVlIGlzIHRvIGNhbGN1bGF0ZSB0aGUgbmVjZXNzYXJ5IGFuZCBzdWZmaWNpZW50IGJ1ZGdldCBvYnRhaW5lZCBmcm9tIHJ1bm5pbmcgdGhlIGJhc2VsaW5lIHBvbGljeS4gRm9yIGxvd2VyIGJvdW5kcywgd2UgaW1wcm92ZSB0aGUgZXhpc3RpbmcgbG93ZXIgYm91bmQgZm9yIGNvbnNlcnZhdGl2ZSBtdWx0aS1hcm1lZCBiYW5kaXRzIGFuZCBvYnRhaW4gbmV3IGxvd2VyIGJvdW5kcyBmb3IgY29uc2VydmF0aXZlIGxpbmVhciBiYW5kaXRzLCB0YWJ1bGFyIFJMIGFuZCBsb3ctcmFuayBNRFAsIHRocm91Z2ggYSBibGFjay1ib3ggcmVkdWN0aW9uIHRoYXQgdHVybnMgYSBjZXJ0YWluIGxvd2VyIGJvdW5kIGluIHRoZSBub25jb25zZXJ2YXRpdmUgc2V0dGluZyBpbnRvIGEgbmV3IGxvd2VyIGJvdW5kIGluIHRoZSBjb25zZXJ2YXRpdmUgc2V0dGluZy4gRm9yIHVwcGVyIGJvdW5kcywgaW4gbXVsdGktYXJtZWQgYmFuZGl0cywgbGluZWFyIGJhbmRpdHMgYW5kIHRhYnVsYXIgUkwsIG91ciBuZXcgdXBwZXIgYm91bmRzIHRpZ2h0ZW4gb3IgbWF0Y2ggZXhpc3Rpbmcgb25lcyB3aXRoIHNpZ25pZmljYW50bHkgc2ltcGxlciBhbmFseXNlcy4gV2UgYWxzbyBvYnRhaW4gYSBuZXcgdXBwZXIgYm91bmQgZm9yIGNvbnNlcnZhdGl2ZSBsb3ctcmFuayBNRFAuPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/2106.11692","contentUrl":null,"metadataVersion":1,"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-23T07:07:38.000Z","registered":"2022-02-23T07:07:39.000Z","published":"2021","updated":"2022-03-17T02:18:32.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.2106.11692","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}