{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T17:50:41Z","timestamp":1772301041559,"version":"3.50.1"},"reference-count":68,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"1","license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2007911"],"award-info":[{"award-number":["CCF-2007911"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["DMS-2015447"],"award-info":[{"award-number":["DMS-2015447"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2106778"],"award-info":[{"award-number":["CCF-2106778"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2142"],"award-info":[{"award-number":["N00014-18-1-2142"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-18-1-0303"],"award-info":[{"award-number":["W911NF-18-1-0303"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1806154"],"award-info":[{"award-number":["CCF-1806154"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2007911"],"award-info":[{"award-number":["CCF-2007911"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2106778"],"award-info":[{"award-number":["CCF-2106778"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["61971266"],"award-info":[{"award-number":["61971266"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research (AFOSR) Young Investigator Program (YIP) Award","doi-asserted-by":"publisher","award":["FA9550-19-1-0030"],"award-info":[{"award-number":["FA9550-19-1-0030"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"ONR","doi-asserted-by":"publisher","award":["N00014-19-1-2120"],"award-info":[{"award-number":["N00014-19-1-2120"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"ARO YIP Award","doi-asserted-by":"publisher","award":["W911NF-20-1-0097"],"award-info":[{"award-number":["W911NF-20-1-0097"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"ARO YIP Award","doi-asserted-by":"publisher","award":["W911NF-18-1-0303"],"award-info":[{"award-number":["W911NF-18-1-0303"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2106739"],"award-info":[{"award-number":["CCF-2106739"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1907661"],"award-info":[{"award-number":["CCF-1907661"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS-1900140"],"award-info":[{"award-number":["IIS-1900140"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS-2100158"],"award-info":[{"award-number":["IIS-2100158"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1109\/tit.2021.3120096","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T17:30:04Z","timestamp":1634319004000},"page":"448-473","source":"Crossref","is-referenced-by-count":30,"title":["Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction"],"prefix":"10.1109","volume":"68","author":[{"given":"Gen","family":"Li","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1488-4647","authenticated-orcid":false,"given":"Yuting","family":"Wei","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6766-5459","authenticated-orcid":false,"given":"Yuejie","family":"Chi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8427-1021","authenticated-orcid":false,"given":"Yuantao","family":"Gu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9256-5815","authenticated-orcid":false,"given":"Yuxin","family":"Chen","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref1","first-page":"7031","article-title":"Sample complexity of asynchronous $Q$-learning: Sharper analysis and variance reduction","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"33","author":"Li"},{"key":"ref2","first-page":"3185","article-title":"Finite-time analysis of asynchronous stochastic approximation and $Q$-learning","volume-title":"Proc. Conf. Learn. Theory","author":"Qu"},{"issue":"3","key":"ref3","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00992698","article-title":"$Q$-learning","volume":"8","author":"Watkins","year":"1992","journal-title":"Mach. Learn."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1038\/nature14236"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-021-05961-4"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993306"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.21236\/ADA276517"},{"key":"ref8","article-title":"Stochastic approximation with cone-contractive operators: Sharp $\\ell_{\\infty}$\n-bounds for $Q$\n-learning","author":"Wainwright","year":"2019","journal-title":"arXiv:1905.06265"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44581-1_39"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2012.08.014"},{"key":"ref11","article-title":"Reinforcement learning with a near optimal rate of convergence","author":"Azar","year":"2011"},{"key":"ref12","article-title":"Variance-reduced $Q$\n-learning is minimax optimal","author":"Wainwright","year":"2019","journal-title":"arXiv:1906.04697"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00115009"},{"key":"ref14","first-page":"1064","article-title":"The asymptotic convergence-rate of $Q$\n-learning","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Szepesv\u00e1ri"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/b13794"},{"key":"ref16","volume-title":"Dynamic Programming and Optimal Control","author":"Bertsekas","year":"2017"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v20-4039"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5368-1"},{"key":"ref19","article-title":"Finite-sample analysis of stochastic approximation using smooth convex envelopes","author":"Chen","year":"2020","journal-title":"arXiv:2002.00874"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2005.08.011"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2024"},{"key":"ref22","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":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/20M1331524"},{"key":"ref24","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":"ref25","first-page":"315","article-title":"Accelerating stochastic gradient descent using predictive variance reduction","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Johnson"},{"key":"ref26","first-page":"1049","article-title":"Stochastic variance reduction methods for policy evaluation","volume-title":"Proc. 34th Int. Conf. Mach. Learn.","volume":"70","author":"Du"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.50"},{"key":"ref28","article-title":"Reanalysis of variance reduced temporal difference learning","author":"Xu","year":"2020","journal-title":"arXiv:2001.01898"},{"key":"ref29","article-title":"Learning from delayed rewards","author":"Watkins","year":"1989"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/s0363012997331639"},{"key":"ref31","first-page":"996","article-title":"Finite-sample convergence rates for $Q$\n-learning and indirect algorithms","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Kearns"},{"key":"ref32","first-page":"6296","article-title":"Tightening the dependence on horizon in the sample complexity of $Q$\n-learning","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Li"},{"key":"ref33","article-title":"Finite-time analysis for double $Q$\n-learning","author":"Xiong","year":"2020","journal-title":"arXiv:2009.14257"},{"key":"ref34","article-title":"Is $Q$\n-learning minimax optimal? A tight sample complexity analysis","author":"Li","year":"2021","journal-title":"arXiv:2102.06548"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2022.110623"},{"key":"ref36","first-page":"10555","article-title":"A finite-time analysis of $Q$\n-learning with neural network function approximation","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Xu"},{"key":"ref37","article-title":"A theoretical analysis of deep $Q$\n-learning","author":"Fan","year":"2019","journal-title":"arXiv:1901.00137"},{"key":"ref38","first-page":"8058","article-title":"Provably efficient $Q$\n-learning with function approximation via distribution shift error checking Oracle","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Du"},{"key":"ref39","article-title":"Agnostic $Q$\n-learning with function approximation in deterministic systems: Tight bounds on approximation error and sample complexity","author":"Du","year":"2020","journal-title":"arXiv:2002.07125"},{"key":"ref40","first-page":"11312","article-title":"Neural temporal-difference and $Q$\n-learning converges to global optima","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Cai"},{"key":"ref41","first-page":"6995","article-title":"Sample-optimal parametric $Q$\n-learning using linearly additive features","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Yang"},{"key":"ref42","article-title":"Momentum $Q$\n-learning with finite-sample convergence guarantee","author":"Weng","year":"2020","journal-title":"arXiv:2007.15418"},{"key":"ref43","article-title":"Provably-efficient double $Q$\n-learning","author":"Weng","year":"2020","journal-title":"arXiv:2007.05034"},{"key":"ref44","first-page":"3111","article-title":"$Q$\n-learning with nearest neighbors","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Shah"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143955"},{"key":"ref46","first-page":"2411","article-title":"Speedy $Q$\n-learning","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Ghavamzadeh"},{"key":"ref47","article-title":"$Q$\n-learning with uniformly bounded variance: Large discounting is not a barrier to fast learning","author":"Devraj","year":"2020","journal-title":"arXiv:2002.10301"},{"key":"ref48","first-page":"4863","article-title":"Is $Q$\n-learning provably efficient?","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Jin"},{"key":"ref49","article-title":"$Q$\n-learning with UCB exploration is sample efficient for infinite-horizon MDP","volume-title":"Proc. Int. Conf. Learn. Represent.","author":"Wang"},{"key":"ref50","first-page":"8002","article-title":"Provably efficient $Q$\n-learning with low switching cost","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Bai"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaac034"},{"key":"ref52","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":"ref53","first-page":"4706","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.","author":"Gupta"},{"key":"ref54","first-page":"1626","article-title":"Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Doan"},{"key":"ref55","article-title":"Finite time analysis of linear two-timescale stochastic approximation with Markovian noise","author":"Kaledin","year":"2020","journal-title":"arXiv:2002.01268"},{"key":"ref56","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":"ref57","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.12079"},{"key":"ref58","article-title":"Target-based temporal difference learning","author":"Lee","year":"2019","journal-title":"arXiv:1904.10945"},{"key":"ref59","article-title":"Multi-agent reinforcement learning in time-varying networked systems","author":"Lin","year":"2020","journal-title":"arXiv:2006.06555"},{"key":"ref60","article-title":"On linear stochastic approximation: Fine-grained Polyak-ruppert and non-asymptotic concentration","author":"Mou","year":"2020","journal-title":"arXiv:2004.04719"},{"key":"ref61","first-page":"8665","article-title":"Finite-sample analysis for SARSA with linear function approximation","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Zou"},{"key":"ref62","article-title":"Model-based reinforcement learning with a generative model is minimax optimal","author":"Agarwal","year":"2019","journal-title":"arXiv:1906.03804"},{"key":"ref63","article-title":"Breaking the sample size barrier in model-based reinforcement learning with a generative model","author":"Li","year":"2020","journal-title":"arXiv:2005.12900"},{"key":"ref64","first-page":"2818","article-title":"Sample complexity of episodic fixed-horizon reinforcement learning","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Dann"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-019-00140-7"},{"key":"ref66","article-title":"Convergence rates of accelerated Markov gradient descent with applications in reinforcement learning","author":"Doan","year":"2020","journal-title":"arXiv:2002.02873"},{"key":"ref67","volume-title":"Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues","volume":"31","author":"Br\u00e9maud","year":"2013"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9660615\/09570295.pdf?arnumber=9570295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T01:43:01Z","timestamp":1706060581000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9570295\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":68,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.1109\/tit.2021.3120096","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1]]}}}