{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:13:03Z","timestamp":1750219983859,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T00:00:00Z","timestamp":1672358400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2022,12,30]]},"abstract":"<jats:p>Reinforcement learning (RL) is a paradigm where an agent learns to accomplish tasks by interacting with the environment, similar to how humans learn. RL is therefore viewed as a promising approach to achieve artificial intelligence, as evidenced by the remarkable empirical successes. However, many RL algorithms are theoretically not well-understood, especially in the setting where function approximation and off-policy sampling are employed. My thesis [1] aims at developing thorough theoretical understanding to the performance of various RL algorithms through finite-sample analysis.<\/jats:p><jats:p>Since most of the RL algorithms are essentially stochastic approximation (SA) algorithms for solving variants of the Bellman equation, the first part of thesis is dedicated to the analysis of general SA involving a contraction operator, and under Markovian noise. We develop a Lyapunov approach where we construct a novel Lyapunov function called the generaled Moreau envelope. The results on SA enable us to establish finite-sample bounds of various RL algorithms in the tabular setting (cf. Part II of the thesis) and when using function approximation (cf. Part III of the thesis), which in turn provide theoretical insights to several important problems in the RL community, such as the efficiency of bootstrapping, the bias-variance trade-off in off-policy learning, and the stability of off-policy control.<\/jats:p><jats:p>The main body of this document provides an overview of the contributions of my thesis.<\/jats:p>","DOI":"10.1145\/3579342.3579346","type":"journal-article","created":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T05:22:00Z","timestamp":1672982520000},"page":"12-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Unified Lyapunov Framework for Finite-Sample Analysis of Reinforcement Learning Algorithms"],"prefix":"10.1145","volume":"50","author":[{"given":"Zaiwei","family":"Chen","sequence":"first","affiliation":[{"name":"Caltech CMS"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Zaiwei Chen. \"A Unified Lyapunov Framework for Finite- Sample Analysis of Reinforcement Learning Algorithms\". In: Ph.D. thesis Georgia Institute of Technology (2022). Zaiwei Chen. \"A Unified Lyapunov Framework for Finite- Sample Analysis of Reinforcement Learning Algorithms\". In: Ph.D. thesis Georgia Institute of Technology (2022).","DOI":"10.1145\/3579342.3579346"},{"key":"e_1_2_1_2_1","article-title":"Target Network and Truncation Overcome The Deadly triad in Q-Learning","author":"Chen Zaiwei","year":"2022","unstructured":"Zaiwei Chen , John Paul Clarke , and Siva Theja Maguluri . \" Target Network and Truncation Overcome The Deadly triad in Q-Learning \". In: Major revision at SIAM Journal on Mathematics of Data Science ( 2022 ). Zaiwei Chen, John Paul Clarke, and Siva Theja Maguluri. \"Target Network and Truncation Overcome The Deadly triad in Q-Learning\". In: Major revision at SIAM Journal on Mathematics of Data Science (2022).","journal-title":"Major revision at SIAM Journal on Mathematics of Data Science ("},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2022.3172242"},{"key":"e_1_2_1_4_1","first-page":"11195","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR.","author":"Chen Zaiwei","year":"2022","unstructured":"Zaiwei Chen and Siva Theja Maguluri . \" Sample Complexity of Policy-Based Methods under Off-Policy Sampling and Linear Function Approximation\". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022 , pp. 11195 -- 11214 . Zaiwei Chen and Siva Theja Maguluri. \"Sample Complexity of Policy-Based Methods under Off-Policy Sampling and Linear Function Approximation\". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 11195--11214."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3508039"},{"key":"e_1_2_1_6_1","volume-title":"Major revision at Operations Research","author":"Zaiwei Chen","year":"2022","unstructured":"Zaiwei Chen et al. \" A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants \". In: Major revision at Operations Research ( 2022 ). Zaiwei Chen et al. \"A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants\". In: Major revision at Operations Research (2022)."},{"key":"e_1_2_1_7_1","first-page":"8223","article-title":"Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes","volume":"33","author":"Zaiwei Chen","year":"2020","unstructured":"Zaiwei Chen et al . \" Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes \". In: Advances in Neural Information Processing Systems 33 ( 2020 ), pp. 8223 -- 8234 . Zaiwei Chen et al. \"Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes\". In: Advances in Neural Information Processing Systems 33 (2020), pp. 8223--8234.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"110623","DOI":"10.1016\/j.automatica.2022.110623","article-title":"Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning","volume":"146","author":"Zaiwei Chen","year":"2022","unstructured":"Zaiwei Chen et al . \" Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning \". In: Automatica 146 ( 2022 ), p. 110623 . Zaiwei Chen et al. \"Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning\". In: Automatica 146 (2022), p. 110623.","journal-title":"Automatica"},{"key":"e_1_2_1_9_1","first-page":"21440","article-title":"Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators","volume":"34","author":"Zaiwei Chen","year":"2021","unstructured":"Zaiwei Chen et al . \" Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators \". In: Advances in Neural Information Processing Systems 34 ( 2021 ), pp. 21440 -- 21452 . Zaiwei Chen et al. \"Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators\". In: Advances in Neural Information Processing Systems 34 (2021), pp. 21440--21452.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"7897","key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1038\/s41586-021-04301-9","article-title":"Magnetic control of tokamak plasmas through deep reinforcement learning","volume":"602","author":"Jonas Degrave","year":"2022","unstructured":"Jonas Degrave et al . \" Magnetic control of tokamak plasmas through deep reinforcement learning \". In: Nature 602 . 7897 ( 2022 ), pp. 414 -- 419 . Jonas Degrave et al. \"Magnetic control of tokamak plasmas through deep reinforcement learning\". In: Nature 602.7897 (2022), pp. 414--419.","journal-title":"Nature"},{"key":"e_1_2_1_11_1","first-page":"1407","volume-title":"International Conference on Machine Learning.","author":"Lasse","year":"2018","unstructured":"Lasse Espeholt et al. \"IMPALA: Scalable Distributed Deep- RL with ImportanceWeighted Actor-Learner Architectures \". In: International Conference on Machine Learning. 2018 , pp. 1407 -- 1416 . Lasse Espeholt et al. \"IMPALA: Scalable Distributed Deep- RL with ImportanceWeighted Actor-Learner Architectures\". In: International Conference on Machine Learning. 2018, pp. 1407--1416."},{"key":"e_1_2_1_12_1","first-page":"5420","volume-title":"International Conference on Machine Learning. PMLR.","author":"Khodadadian Sajad","year":"2021","unstructured":"Sajad Khodadadian , Zaiwei Chen , and Siva Theja Maguluri . \" Finite-Sample Analysis of Off-Policy Natural Actor- Critic Algorithm\". In: International Conference on Machine Learning. PMLR. 2021 , pp. 5420 -- 5431 . Sajad Khodadadian, Zaiwei Chen, and Siva Theja Maguluri. \"Finite-Sample Analysis of Off-Policy Natural Actor- Critic Algorithm\". In: International Conference on Machine Learning. PMLR. 2021, pp. 5420--5431."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913495721"},{"key":"e_1_2_1_14_1","volume-title":"Mastering the game of Go with deep neural networks and tree search\". In: nature 529.7587","author":"David Silver","year":"2016","unstructured":"David Silver et al. \" Mastering the game of Go with deep neural networks and tree search\". In: nature 529.7587 ( 2016 ), p. 484. David Silver et al. \"Mastering the game of Go with deep neural networks and tree search\". In: nature 529.7587 (2016), p. 484."},{"key":"e_1_2_1_15_1","first-page":"2803","volume-title":"Conference on Learning Theory.","author":"Srikant R","year":"2019","unstructured":"R Srikant and Lei Ying . \" Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning\". In: Conference on Learning Theory. 2019 , pp. 2803 -- 2830 . R Srikant and Lei Ying. \"Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning\". In: Conference on Learning Theory. 2019, pp. 2803--2830."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646945.712397"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579342.3579346","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3579342.3579346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:27Z","timestamp":1750182567000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579342.3579346"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,30]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,12,30]]}},"alternative-id":["10.1145\/3579342.3579346"],"URL":"https:\/\/doi.org\/10.1145\/3579342.3579346","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2022,12,30]]},"assertion":[{"value":"2023-01-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}