{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T21:11:28Z","timestamp":1780089088399,"version":"3.54.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,5,29]]},"abstract":"<jats:p>\n                    In this work, we present the first\n                    <jats:italic toggle=\"yes\">finite-time analysis<\/jats:italic>\n                    of Q-learning with\n                    <jats:italic toggle=\"yes\">time-varying learning policies<\/jats:italic>\n                    (i.e., on-policy sampling) for discounted Markov decision processes under\n                    <jats:italic toggle=\"yes\">minimal assumptions,<\/jats:italic>\n                    requiring only the existence of a policy that induces an\n                    <jats:italic toggle=\"yes\">irreducible<\/jats:italic>\n                    Markov chain over the state space. We establish a last-iterate convergence rate for E[||Q\n                    <jats:sub>k<\/jats:sub>\n                    - Q\n                    <jats:sup>*<\/jats:sup>\n                    ||\n                    <jats:sub>\u221e<\/jats:sub>\n                    <jats:sup>2<\/jats:sup>\n                    ], which implies a sample complexity of order O(1\/\u03be\n                    <jats:sup>2<\/jats:sup>\n                    ) for achieving E[||Q\n                    <jats:sub>k<\/jats:sub>\n                    - Q\n                    <jats:sup>*<\/jats:sup>\n                    ||\n                    <jats:sub>\u221e<\/jats:sub>\n                    ]\\le \u03be. This rate matches that of off-policy Q-learning, but with a worse dependence on exploration-related parameters. We also derive an explicit finite-time rate for E[||Q\n                    <jats:sup>\u03c0<\/jats:sup>\n                    <jats:sub>k<\/jats:sub>\n                    - Q\n                    <jats:sup>*<\/jats:sup>\n                    ||\n                    <jats:sub>\u221e<\/jats:sub>\n                    <jats:sup>2<\/jats:sup>\n                    ], where \u03c0\n                    <jats:sub>k<\/jats:sub>\n                    denotes the learning policy at iteration\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    . Together, these results highlight the exploration--exploitation trade-off in on-policy Q-learning. While exploration is weaker than in off-policy methods, on-policy learning enjoys an exploitation advantage since the learning policy itself converges to an optimal one. Numerical experiments corroborate our theoretical findings.\n                  <\/jats:p>\n                  <jats:p>\n                    From a technical perspective, the combination of rapidly time-varying learning policies, which induce time-inhomogeneous Markovian noise, and minimal exploration assumptions presents significant analytical challenges. To address these challenges, we develop a Poisson-equation-based decomposition of the Markovian noise associated with a\n                    <jats:italic toggle=\"yes\">lazy<\/jats:italic>\n                    transition matrix, separating it into a martingale-difference term and residual terms. We then control the residual terms through a sensitivity analysis of the Poisson equation solution with respect to both the Q-function estimate and the learning policy. These techniques may facilitate the analysis of other reinforcement learning algorithms with rapidly time-varying learning policies, such as single-timescale actor--critic methods and learning-in-games algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3805624","type":"journal-article","created":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:34:18Z","timestamp":1780086858000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1972-8582","authenticated-orcid":false,"given":"Phalguni","family":"Nanda","sequence":"first","affiliation":[{"name":"Edwardson School of Industrial Engineering, Purdue University, West Lafayette, Indiana, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9915-5595","authenticated-orcid":false,"given":"Zaiwei","family":"Chen","sequence":"additional","affiliation":[{"name":"Edwardson School of Industrial Engineering, Purdue University, West Lafayette, Indiana, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543846"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/137926.137932"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Dynamic policy programming","volume":"13","author":"Azar Mohammad Gheshlaghi","year":"2012","unstructured":"Mohammad Gheshlaghi Azar, Vicen\u00e7 G\u00f3mez, and Hilbert J. Kappen. 2012. Dynamic policy programming. J. Mach. Learn. Res., Vol. 13, 1 (Nov. 2012), 3207\u20133245.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_4_1","volume-title":"Sur les op\u00e9rations dans les ensembles abstraits et leur application aux \u00e9quations int\u00e9grales. Fund. math","author":"Banach Stefan","year":"1922","unstructured":"Stefan Banach. 1922. Sur les op\u00e9rations dans les ensembles abstraits et leur application aux \u00e9quations int\u00e9grales. Fund. math, Vol. 3, 1 (1922), 133-181."},{"key":"e_1_2_1_5_1","volume-title":"arXiv preprint arXiv:2303.08631","author":"Barber David","year":"2023","unstructured":"David Barber. 2023. Smoothed Q-learning. arXiv preprint arXiv:2303.08631 (2023)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974997"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2012.08.014"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2013.6580117"},{"key":"e_1_2_1_9_1","volume-title":"Neuro-Dynamic Programming","author":"Bertsekas Dimitri P","unstructured":"Dimitri P Bertsekas and John N Tsitsiklis. 1996. Neuro-Dynamic Programming. Athena Scientific."},{"key":"e_1_2_1_10_1","volume-title":"Conference On Learning Theory. 1691-1692","author":"Bhandari Jalaj","year":"2018","unstructured":"Jalaj Bhandari, Daniel Russo, and Raghav Singal. 2018. A finite-time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory. 1691-1692."},{"key":"e_1_2_1_11_1","volume-title":"Stochastic Approximation: A Dynamical Systems Viewpoint.","author":"Borkar Vivek S","year":"2009","unstructured":"Vivek S Borkar. 2009. Stochastic Approximation: A Dynamical Systems Viewpoint. Vol. 48. Springer."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012997331639"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/stsy.2022.0097"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"1078","DOI":"10.1137\/22M1499261","article-title":"Target network and truncation overcome the deadly triad in Q-learning","volume":"5","author":"Chen Zaiwei","year":"2023","unstructured":"Zaiwei Chen, John-Paul Clarke, and Siva Theja Maguluri. 2023a. Target network and truncation overcome the deadly triad in Q-learning. SIAM Journal on Mathematics of Data Science, Vol. 5, 4 (2023), 1078-1101.","journal-title":"SIAM Journal on Mathematics of Data Science"},{"key":"e_1_2_1_15_1","volume-title":"International Conference on Learning Representations.","author":"Chen Ziyi","year":"2021","unstructured":"Ziyi Chen, Shaocong Ma, and Yi Zhou. 2021. Sample efficient stochastic policy extra-gradient algorithm for zero-sum Markov game. In International Conference on Learning Representations."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.0249"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"75826","DOI":"10.52202\/075280-3313","article-title":"A finite-sample analysis of payoff-based independent learning in zero-sum stochastic games","volume":"36","author":"Chen Zaiwei","year":"2023","unstructured":"Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, and Adam Wierman. 2023b. A finite-sample analysis of payoff-based independent learning in zero-sum stochastic games. Advances in Neural Information Processing Systems, Vol. 36 (2023), 75826-75883.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673491"},{"key":"e_1_2_1_19_1","volume-title":"International Conference on Machine Learning. PMLR, 3794-3834","author":"Chen Ziyi","year":"2022","unstructured":"Ziyi Chen, Yi Zhou, Rong-Rong Chen, and Shaofeng Zou. 2022. Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis. In International Conference on Machine Learning. PMLR, 3794-3834."},{"key":"e_1_2_1_20_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Devraj Adithya M","year":"2017","unstructured":"Adithya M Devraj and Sean Meyn. 2017. Zap Q-learning. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"R. Douc E. Moulines P. Priouret and P. Soulier. 2018. Markov Chains. Springer International Publishing. https:\/\/books.google.com\/books?id=QaZ-DwAAQBAJ","DOI":"10.1007\/978-3-319-97704-1"},{"key":"e_1_2_1_22_1","first-page":"1","article-title":"Learning rates for Q-learning","volume":"5","author":"Even-Dar Eyal","year":"2003","unstructured":"Eyal Even-Dar and Yishay Mansour. 2003. Learning rates for Q-learning. Journal of Machine Learning Research, Vol. 5, Dec (2003), 1-25.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_23_1","volume-title":"Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning","author":"Azar Mohammad Gheshlaghi","year":"2013","unstructured":"Mohammad Gheshlaghi Azar, R\u00e9mi Munos, and Hilbert J Kappen. 2013. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, Vol. 91, 3 (2013), 325-349."},{"key":"e_1_2_1_24_1","volume-title":"Hoeffding's inequality for uniformly ergodic Markov chains. Statistics & probability letters","author":"Glynn Peter W","year":"2002","unstructured":"Peter W Glynn and Dirk Ormoneit. 2002. Hoeffding's inequality for uniformly ergodic Markov chains. Statistics & probability letters, Vol. 56, 2 (2002), 143-146."},{"key":"e_1_2_1_25_1","volume-title":"Boundedness of iterates in Q-learning. Systems & control letters","author":"Gosavi Abhijit","year":"2006","unstructured":"Abhijit Gosavi. 2006. Boundedness of iterates in Q-learning. Systems & control letters, Vol. 55, 4 (2006), 347-349."},{"key":"e_1_2_1_26_1","volume-title":"International Conference on Machine Learning. PMLR, 1352-1361","author":"Haarnoja Tuomas","year":"2017","unstructured":"Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. 2017. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning. PMLR, 1352-1361."},{"key":"e_1_2_1_27_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 3718-3726","author":"Haque Shaan Ul","year":"2025","unstructured":"Shaan Ul Haque and Siva Theja Maguluri. 2025. Stochastic approximation with unbounded Markovian noise: A general-purpose theorem. In International Conference on Artificial Intelligence and Statistics. PMLR, 3718-3726."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3016100.3016191"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Tommi Jaakkola Michael I Jordan and Satinder P Singh. 1994. Convergence of stochastic iterative dynamic programming algorithms. In Advances in neural information processing systems. 703-710.","DOI":"10.21236\/ADA276517"},{"key":"e_1_2_1_30_1","volume-title":"Is Q-learning provably efficient? Advances in neural information processing systems","author":"Jin Chi","year":"2018","unstructured":"Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. 2018. Is Q-learning provably efficient? Advances in neural information processing systems, Vol. 31 (2018)."},{"key":"e_1_2_1_31_1","volume-title":"Finite sample analysis of two-time-scale natural actor-critic algorithm","author":"Khodadadian Sajad","year":"2022","unstructured":"Sajad Khodadadian, Thinh T Doan, Justin Romberg, and Siva Theja Maguluri. 2022a. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Trans. Automat. Control (2022)."},{"key":"e_1_2_1_32_1","volume-title":"International Conference on Machine Learning. PMLR, 10997-11057","author":"Khodadadian Sajad","year":"2022","unstructured":"Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. 2022b. Federated reinforcement learning: Linear speedup under Markovian sampling. In International Conference on Machine Learning. PMLR, 10997-11057."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2024.3355326"},{"key":"e_1_2_1_35_1","first-page":"15556","article-title":"A unified switching system perspective and convergence analysis of Q-learning algorithms","volume":"33","author":"Lee Donghwan","year":"2020","unstructured":"Donghwan Lee and Niao He. 2020. A unified switching system perspective and convergence analysis of Q-learning algorithms. Advances in Neural Information Processing Systems, Vol. 33 (2020), 15556-15567.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012903437976"},{"key":"e_1_2_1_37_1","volume-title":"Markov Chains and Mixing Times","author":"Levin David A","unstructured":"David A Levin and Yuval Peres. 2017. Markov Chains and Mixing Times. Vol. 107. American Mathematical Soc."},{"key":"e_1_2_1_38_1","first-page":"1","article-title":"End-to-end training of deep visuomotor policies","volume":"17","author":"Levine Sergey","year":"2016","unstructured":"Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. 2016. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, Vol. 17, 39 (2016), 1-40.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_39_1","first-page":"7031","volume-title":"Advances in Neural Information Processing Systems","volume":"33","author":"Li Gen","year":"2020","unstructured":"Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. 2020. Sample complexity of asynchronous Q-learning: sharper analysis and variance reduction. In Advances in Neural Information Processing Systems, Vol. 33. Curran Associates, Inc., 7031-7043."},{"key":"e_1_2_1_40_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 2207-2261","author":"Li Xiang","year":"2023","unstructured":"Xiang Li, Wenhao Yang, Jiadong Liang, Zhihua Zhang, and Michael I Jordan. 2023. A statistical analysis of Polyak-Ruppert averaged Q-learning. In International Conference on Artificial Intelligence and Statistics. PMLR, 2207-2261."},{"key":"e_1_2_1_41_1","volume-title":"Linear Q-learning does not diverge in $mathcalL^2$: Convergence rates to a bounded set. Preprint arXiv:2501.19254","author":"Liu Xinyu","year":"2025","unstructured":"Xinyu Liu, Zixuan Xie, and Shangtong Zhang. 2025. Linear Q-learning does not diverge in $mathcalL^2$: Convergence rates to a bounded set. Preprint arXiv:2501.19254 (2025)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390240"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2024.3409647"},{"key":"e_1_2_1_44_1","volume-title":"Human-level control through deep reinforcement learning. nature","author":"Mnih Volodymyr","year":"2015","unstructured":"Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. 2015. Human-level control through deep reinforcement learning. nature, Vol. 518, 7540 (2015), 529-533."},{"key":"e_1_2_1_45_1","volume-title":"Markov chains. Number 2","author":"Norris James R","unstructured":"James R Norris. 1998. Markov chains. Number 2. Cambridge university press."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/3600270.3602281"},{"key":"e_1_2_1_47_1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman Martin L","unstructured":"Martin L Puterman. 2014. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2021.3078754"},{"key":"e_1_2_1_49_1","volume-title":"Conference on Learning Theory. PMLR, 3185-3205","author":"Qu Guannan","year":"2020","unstructured":"Guannan Qu and Adam Wierman. 2020. Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Conference on Learning Theory. PMLR, 3185-3205."},{"key":"e_1_2_1_50_1","volume-title":"A stochastic approximation method. The Annals of Mathematical Statistics","author":"Robbins Herbert","year":"1951","unstructured":"Herbert Robbins and Sutton Monro. 1951. A stochastic approximation method. The Annals of Mathematical Statistics (1951), 400-407."},{"key":"e_1_2_1_51_1","volume-title":"Online Q-learning using connectionist systems","author":"Rummery Gavin A","year":"1994","unstructured":"Gavin A Rummery and Mahesan Niranjan. 1994. Online Q-learning using connectionist systems. University of Cambridge, Department of Engineering, Cambridge, UK, Vol. 37 (1994)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_2_1_53_1","volume-title":"Nature","volume":"550","author":"Silver David","year":"2017","unstructured":"David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. 2017. Mastering the game of Go without human knowledge. Nature, Vol. 550, 7676 (2017), 354."},{"key":"e_1_2_1_54_1","volume-title":"Convergence results for single-step on-policy reinforcement-learning algorithms. Machine learning","author":"Singh Satinder","year":"2000","unstructured":"Satinder Singh, Tommi Jaakkola, Michael L Littman, and Csaba Szepesv\u00e1ri. 2000. Convergence results for single-step on-policy reinforcement-learning algorithms. Machine learning, Vol. 38 (2000), 287-308."},{"key":"e_1_2_1_55_1","volume-title":"Conference on Learning Theory. 2803-2830","author":"Srikant R","year":"2019","unstructured":"R Srikant and Lei Ying. 2019. Finite-time error bounds for linear stochastic approximation and TD-learning. In Conference on Learning Theory. 2803-2830."},{"key":"e_1_2_1_56_1","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton Richard S","year":"2018","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement Learning: An Introduction. MIT press."},{"key":"e_1_2_1_57_1","first-page":"1064","article-title":"The asymptotic convergence-rate of Q-learning","author":"Szepesv\u00e1ri Csaba","year":"1998","unstructured":"Csaba Szepesv\u00e1ri. 1998. The asymptotic convergence-rate of Q-learning. In Advances in Neural Information Processing Systems. 1064-1070.","journal-title":"Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_58_1","volume-title":"Annual conference on artificial intelligence. Springer, 335-346","author":"Tokic Michel","year":"2011","unstructured":"Michel Tokic and G\u00fcnther Palm. 2011. Value-difference based exploration: Adaptive control between \u03b5-greedy and softmax. In Annual conference on artificial intelligence. Springer, 335-346."},{"key":"e_1_2_1_59_1","volume-title":"Asynchronous stochastic approximation and Q-learning. Machine learning","author":"Tsitsiklis John N","year":"1994","unstructured":"John N Tsitsiklis. 1994. Asynchronous stochastic approximation and Q-learning. Machine learning, Vol. 16, 3 (1994), 185-202."},{"key":"e_1_2_1_60_1","volume-title":"Stochastic approximation with cone-contractive operators: Sharp $ell_infty$-bounds for $Q$-learning. Preprint arXiv:1905.06265","author":"Wainwright Martin J","year":"2019","unstructured":"Martin J Wainwright. 2019a. Stochastic approximation with cone-contractive operators: Sharp $ell_infty$-bounds for $Q$-learning. Preprint arXiv:1905.06265 (2019)."},{"key":"e_1_2_1_61_1","volume-title":"Variance-reduced Q-learning is minimax optimal. Preprint arXiv:1906.04697","author":"Wainwright Martin J","year":"2019","unstructured":"Martin J Wainwright. 2019b. Variance-reduced Q-learning is minimax optimal. Preprint arXiv:1906.04697 (2019)."},{"key":"e_1_2_1_62_1","volume-title":"Near sample-optimal reduction-based policy learning for average reward MDP. Preprint arXiv:2212.00603","author":"Wang Jinghan","year":"2022","unstructured":"Jinghan Wang, Mengdi Wang, and Lin F Yang. 2022. Near sample-optimal reduction-based policy learning for average reward MDP. Preprint arXiv:2212.00603 (2022)."},{"key":"e_1_2_1_63_1","volume-title":"Machine learning","author":"Watkins Christopher JCH","year":"1992","unstructured":"Christopher JCH Watkins and Peter Dayan. 1992. Q-learning. Machine learning, Vol. 8, 3-4 (1992), 279-292."},{"key":"e_1_2_1_64_1","first-page":"1","article-title":"The blessing of heterogeneity in federated Q-learning: Linear speedup and beyond","volume":"26","author":"Woo Jiin","year":"2025","unstructured":"Jiin Woo, Gauri Joshi, and Yuejie Chi. 2025. The blessing of heterogeneity in federated Q-learning: Linear speedup and beyond. Journal of Machine Learning Research, Vol. 26, 26 (2025), 1-85.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_65_1","first-page":"17617","article-title":"A finite-time analysis of two time-scale actor-critic methods","volume":"33","author":"Wu Yue Frank","year":"2020","unstructured":"Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. 2020. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, Vol. 33 (2020), 17617-17628.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_66_1","volume-title":"Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning","author":"Xia Eric","year":"2024","unstructured":"Eric Xia, Koulik Khamaru, Martin J Wainwright, and Michael I Jordan. 2024. Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning. IEEE Transactions on Information Theory (2024)."},{"key":"e_1_2_1_67_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 811-819","author":"Xu Tengyu","year":"2021","unstructured":"Tengyu Xu and Yingbin Liang. 2021. Sample complexity bounds for two timescale value-based reinforcement learning algorithms. In International Conference on Artificial Intelligence and Statistics. PMLR, 811-819."},{"key":"e_1_2_1_68_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 1576-1584","author":"Yang Kunhe","year":"2021","unstructured":"Kunhe Yang, Lin Yang, and Simon Du. 2021. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics. PMLR, 1576-1584."},{"key":"e_1_2_1_69_1","volume-title":"International Conference on Machine Learning. PMLR, 41613-41646","author":"Zhang Shangtong","year":"2023","unstructured":"Shangtong Zhang, Remi Tachet Des Combes, and Romain Laroche. 2023a. On the convergence of SARSA with linear function approximation. In International Conference on Machine Learning. PMLR, 41613-41646."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3579601"},{"key":"e_1_2_1_71_1","volume-title":"Constant stepsize Q-learning: Distributional convergence, bias and extrapolation. Preprint arXiv:2401.13884","author":"Zhang Yixuan","year":"2024","unstructured":"Yixuan Zhang and Qiaomin Xie. 2024. Constant stepsize Q-learning: Distributional convergence, bias and extrapolation. Preprint arXiv:2401.13884 (2024)."},{"key":"e_1_2_1_72_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. PMLR, 5476-5477","author":"Zhang Zihan","year":"2023","unstructured":"Zihan Zhang and Qiaomin Xie. 2023. Sharper model-free reinforcement learning for average-reward Markov decision processes. In The Thirty Sixth Annual Conference on Learning Theory. PMLR, 5476-5477."},{"key":"e_1_2_1_73_1","first-page":"8668","article-title":"Finite-sample analysis for SARSA with linear function approximation","author":"Zou Shaofeng","year":"2019","unstructured":"Shaofeng Zou, Tengyu Xu, and Yingbin Liang. 2019. Finite-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems. 8668-8678.","journal-title":"Advances in Neural Information Processing Systems."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3805624","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:38:41Z","timestamp":1780087121000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3805624"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,29]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,29]]}},"alternative-id":["10.1145\/3805624"],"URL":"https:\/\/doi.org\/10.1145\/3805624","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,29]]},"assertion":[{"value":"2026-05-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}