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

DOI10.1109/TAC.2022.3190032MaRDI QIDQ6080164zbMATH OpenOpenAlexFDO

Authors Sajad Khodadadian, Thinh T. Doan, Justin Romberg, Siva Theja Maguluri

Publication date 2 October 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.10506

zbMATH Keywords

actor-critic (AC)machine learningreinforcement learning (RL)two-time-scale

Mathematics Subject Classification ID

Systems theory; control (93-XX)

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 paper, we characterize the emph{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 actor-critic algorithm has a rate of convergence of $ildemathcalO(1/T^{1/4})$, where $T$ is the number of samples, and this leads to a sample complexity of $TildemathcalO(1/delt{a}^8)$ samples to find a policy that is within an error of $delta$ from the emph{global optimum}. Moreover, by carefully decreasing the exploration parameter $epsilon$ as the iterations proceed, we present an improved sample complexity of $TildemathcalO(1/delt{a}^6)$ for convergence to the global optimum.

Cited in

(4)

• Softmax policy gradient methods can take exponential time to converge
• Policy mirror descent inherently explores action space
• An approximate policy iteration viewpoint of actor-critic algorithms
• Concentration of contractive stochastic approximation: additive and multiplicative noise

This page was built for publication: Finite-Sample Analysis of Two-Time-Scale Natural Actor–Critic Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080164)