{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T09:55:16Z","timestamp":1740131716395,"version":"3.37.3"},"reference-count":69,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"8","license":[{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100004853","name":"Chinese University of Hong Kong (CUHK) Direct Grant for Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004853","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NIH","award":["R01 NS121913"],"award-info":[{"award-number":["R01 NS121913"]}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-19-1-2404"],"award-info":[{"award-number":["N00014-19-1-2404"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["CCF-2106778"],"award-info":[{"award-number":["CCF-2106778"]}]},{"name":"NSF","award":["DMS-2311127"],"award-info":[{"award-number":["DMS-2311127"]}]},{"name":"NSF","award":["CCF-2106778","DMS-2147546\/2015447"],"award-info":[{"award-number":["CCF-2106778","DMS-2147546\/2015447"]}]},{"name":"NSF CAREER Award","award":["DMS-2143215"],"award-info":[{"award-number":["DMS-2143215"]}]},{"name":"Google Research Scholar Award"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1109\/tit.2024.3394685","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T17:36:19Z","timestamp":1714412179000},"page":"5969-5999","source":"Crossref","is-referenced-by-count":0,"title":["High-Probability Sample Complexities for Policy Evaluation With Linear Function Approximation"],"prefix":"10.1109","volume":"70","author":[{"given":"Gen","family":"Li","sequence":"first","affiliation":[{"name":"Department of Statistics, The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5955-3289","authenticated-orcid":false,"given":"Weichen","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Statistics and Data Science, Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6766-5459","authenticated-orcid":false,"given":"Yuejie","family":"Chi","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2532-0038","authenticated-orcid":false,"given":"Cong","family":"Ma","sequence":"additional","affiliation":[{"name":"Department of Statistics, The University of Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Rinaldo","sequence":"additional","affiliation":[{"name":"Department of Statistics and Data Science, The University of Texas at Austin, Austin, UT, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1488-4647","authenticated-orcid":false,"given":"Yuting","family":"Wei","sequence":"additional","affiliation":[{"name":"Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9868.00389"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2018.1527225"},{"key":"ref3","first-page":"2","article-title":"Model selection for offline reinforcement learning: Practical considerations for healthcare settings","volume-title":"Proc. 6th Mach. Learn. Healthcare Conf.","author":"Tang"},{"issue":"1","key":"ref4","first-page":"809","article-title":"Policy evaluation with temporal differences: A survey and comparison","volume":"15","author":"Dann","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/ICDH55609.2022.00010"},{"volume-title":"Reinforcement Learning: An Introduction","year":"2018","author":"Sutton","key":"ref6"},{"volume-title":"Dynamic Programming and Optimal Control","year":"2017","author":"Bertsekas","key":"ref7"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/9.580874"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2024"},{"key":"ref10","first-page":"486","article-title":"A theoretical analysis of deep Q-learning","volume-title":"Proc. 2nd Learn. Dyn. Control Conf.","author":"Fan"},{"issue":"1","key":"ref11","first-page":"4809","article-title":"Regularized policy iteration with nonparametric function spaces","volume":"17","author":"Farahmand","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref12","article-title":"Optimal policy evaluation using kernel-based temporal difference methods","author":"Duan","year":"2021","journal-title":"arXiv:2109.12002"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.1995.478953"},{"key":"ref14","article-title":"A brief survey of deep reinforcement learning","author":"Arulkumaran","year":"2017","journal-title":"arXiv:1708.05866"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.1309"},{"key":"ref16","first-page":"23009","article-title":"Sample-efficient reinforcement learning for linearly-parameterized MDPs with a generative model","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"34","author":"Wang"},{"key":"ref17","first-page":"16671","article-title":"Sample-efficient reinforcement learning is feasible for linearly realizable MDPs with limited revisiting","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"34","author":"Li"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00115009"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2023.2450"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.12079"},{"key":"ref21","first-page":"2803","article-title":"Finite-time error bounds for linear stochastic approximation and TD learning","volume-title":"Proc. Conf. Learn. Theory","author":"Srikant"},{"key":"ref22","first-page":"1347","article-title":"Linear stochastic approximation: How far does constant step-size and iterate averaging go?","volume-title":"Proc. Int. Conf. Artif. Intell. Statist.","author":"Lakshminarayanan"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-377-6.50013-X"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553501"},{"key":"ref25","first-page":"1199","article-title":"Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning","volume-title":"Proc. Conf. Learn. Theory","author":"Dalal"},{"key":"ref26","first-page":"811","article-title":"Sample complexity bounds for two timescale value-based reinforcement learning algorithms","volume-title":"Proc. Int. Conf. Artif. Intell. Statist.","author":"Xu"},{"key":"ref27","first-page":"9747","article-title":"Non-asymptotic analysis for two time-scale TDC with general smooth function approximation","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"34","author":"Wang"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5779"},{"key":"ref29","first-page":"2144","article-title":"Finite time analysis of linear two-timescale stochastic approximation with Markovian noise","volume-title":"Proc. Conf. Learn. Theory","author":"Kaledin"},{"key":"ref30","first-page":"4704","article-title":"Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"32","author":"Gupta"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.0179"},{"key":"ref32","first-page":"1064","article-title":"The asymptotic convergence-rate of Q-learning","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Szepesv\u00e1ri"},{"key":"ref33","article-title":"Is temporal difference learning optimal? An instance-dependent analysis","author":"Khamaru","year":"2020","journal-title":"arXiv:2003.07337"},{"key":"ref34","first-page":"4863","article-title":"Is Q-learning provably efficient?","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Jin"},{"key":"ref35","first-page":"49","article-title":"Least-squares temporal difference learning","volume-title":"Proc. ICML","author":"Boyan"},{"key":"ref36","first-page":"5186","article-title":"Near-optimal time and sample complexities for solving Markov decision processes with a generative model","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Sidford"},{"key":"ref37","first-page":"67","article-title":"Model-based reinforcement learning with a generative model is minimax optimal","volume-title":"Proc. 33rd Conf. Learn. Theory","author":"Agarwal"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3027316"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2023.2451"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1051027873"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-99-8277-6"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012997331639"},{"key":"ref44","article-title":"On linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration","author":"Mou","year":"2020","journal-title":"arXiv:2004.04719"},{"key":"ref45","first-page":"451","article-title":"Non-asymptotic analysis of stochastic approximation algorithms for machine learning","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"24","author":"Moulines"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"ref47","first-page":"10633","article-title":"Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Xu"},{"key":"ref48","first-page":"17617","article-title":"A finite-time analysis of two time-scale actor-critic methods","volume-title":"Proc. NIPS","author":"Wu"},{"key":"ref49","first-page":"759","article-title":"Eligibility traces for off-policy policy evaluation","volume-title":"Proc. 17th Int. Conf. Mach. Learn.","author":"Precup"},{"key":"ref50","first-page":"652","article-title":"Doubly robust off-policy value evaluation for reinforcement learning","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Jiang"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3162335"},{"key":"ref52","first-page":"2139","article-title":"Data-efficient off-policy policy evaluation for reinforcement learning","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Thomas"},{"key":"ref53","first-page":"9668","article-title":"Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"32","author":"Xie"},{"issue":"1","key":"ref54","first-page":"6742","article-title":"Double reinforcement learning for efficient off-policy evaluation in Markov decision processes","volume":"21","author":"Kallus","year":"2020","journal-title":"J. Mach. Learn. Res."},{"key":"ref55","first-page":"6551","article-title":"Off-policy evaluation via the regularized Lagrangian","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"33","author":"Yang"},{"key":"ref56","first-page":"2701","article-title":"Minimax-optimal off-policy evaluation with linear function approximation","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Duan"},{"key":"ref57","first-page":"5084","article-title":"Is pessimism provably efficient for offline RL?","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Jin"},{"key":"ref58","first-page":"27395","article-title":"Policy finetuning: Bridging sample-efficient offline and online reinforcement learning","volume-title":"Proc. Int. Conf. Adv. Neural Inf. Process. Syst.","volume":"34","author":"Xie"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1214\/23-aos2342"},{"key":"ref60","first-page":"19967","article-title":"Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Shi"},{"key":"ref61","first-page":"11702","article-title":"Bridging offline reinforcement learning and imitation learning: A tale of pessimism","volume-title":"Proc. Int. Conf. Adv. Neural Inf. Process. Syst.","volume":"34","author":"Rashidinejad"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3120096"},{"key":"ref63","article-title":"Optimal Oracle inequalities for solving projected fixed-point equations","author":"Mou","year":"2020","journal-title":"arXiv:2012.05299"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1137\/21m1468668"},{"issue":"21","key":"ref65","first-page":"1609","article-title":"A convergent O(n) algorithm for off-policy temporal-difference learning with linear function approximation","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"21","author":"Sutton"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1952.tb01393.x"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1007\/b13794"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v16-1624"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1561\/2200000048"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielam\/18\/10599340\/10509733-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/10599340\/10509733.pdf?arnumber=10509733","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T06:05:01Z","timestamp":1721282701000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10509733\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8]]},"references-count":69,"journal-issue":{"issue":"8"},"URL":"https:\/\/doi.org\/10.1109\/tit.2024.3394685","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"type":"print","value":"0018-9448"},{"type":"electronic","value":"1557-9654"}],"subject":[],"published":{"date-parts":[[2024,8]]}}}