Finite-Sample Analysis of Two-Time-Scale Natural Actor–Critic Algorithm
Sajad Khodadadian, Thinh T. Doan, Justin Romberg, Siva Theja Maguluri
Abstract
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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">global</i> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> -greedy sampling of the trajectory. For a fixed and small enough exploration parameter <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> , we show that the two-time-scale natural actor–critic algorithm has a rate of convergence of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\tilde{\mathcal {O}}(1/T^{1/4})$</tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> is the number of samples, and this leads to a sample complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\tilde{\mathcal {O}}(1/\delta ^{8})$</tex-math></inline-formula> samples to find a policy that is within an error of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta$</tex-math></inline-formula> from the global optimum. Moreover, by carefully decreasing the exploration parameter <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> as the iterations proceed, we present an improved sample complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\tilde{\mathcal {O}}(1/\delta ^{6})$</tex-math></inline-formula> for convergence to the global optimum.