Finite-Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm

• 成果类型: Article
• 署名作者: Khodadadian, Sajad; Doan, Thinh T.; Romberg, Justin; Maguluri, Siva Theja
• 署名单位: University System of Georgia; Georgia Institute of Technology; Virginia Polytechnic Institute & State University; Virginia Polytechnic Institute & State University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3190032
• 发表日期: 2023
• 页码: 3273-3284
• 关键词: Actor-critic (AC); Machine Learning; reinforcement learning (RL); two-time-scale

摘要

Actor-critic style two-time-scale algorithms are one of the most popular methods in reinforcement learning, and have seen great empirical success. However, their performance is not completely understood theoretically. In this article, we characterize the global convergence of an online natural actor-critic algorithm in the tabular setting using a single trajectory of samples. Our analysis applies to very general settings, as we only assume ergodicity of the underlying Markov decision process. In order to ensure enough exploration, we employ an epsilon-greedy sampling of the trajectory. For a fixed and small enough exploration parameter epsilon, we show that the two-time-scale natural actorcritic algorithm has a rate of convergence of (O) over tilde (1/T 1/4), where T is the number of samples, and this leads to a sample complexity of (O) over tilde (1/delta(8)) samples to find a policy that is within an error of delta from the global optimum. Moreover, by carefully decreasing the exploration parameter epsilon as the iterations proceed, we present an improved sample complexity of (O) over tilde (1/delta(6)) for convergence to the global optimum.