Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm
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 $\tilde{\mathcal{O}}(1/T^{1/4})$, where $T$ is the number of samples, and this leads to a sample complexity of $\Tilde{\mathcal{O}}(1/\delta^{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 $\Tilde{\mathcal{O}}(1/\delta^{6})$ for convergence to the global optimum.
Code (0)
등록된 구현이 없습니다.
Tasks
Vocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
Greedy-GQ is an off-policy two timescale algorithm for optimal control in reinforcement learning. This paper develops the first finite-sample analysis for the Greedy-GQ algorithm with linear function approximation under …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
As an important type of reinforcement learning algorithms, actor-critic (AC) and natural actor-critic (NAC) algorithms are often executed in two ways for finding optimal policies. In the first nested-loop design, actor's…
A Finite-Time Analysis of Two Time-Scale Actor-Critic Methods
Actor-critic (AC) methods have exhibited great empirical success compared with other reinforcement learning algorithms, where the actor uses the policy gradient to improve the learning policy and the critic uses temporal…
Vocal Bursts Valence PredictionA Finite Time Analysis of Two Time-Scale Actor Critic Methods
Actor-critic (AC) methods have exhibited great empirical success compared with other reinforcement learning algorithms, where the actor uses the policy gradient to improve the learning policy and the critic uses temporal…
Vocal Bursts Valence PredictionFinite-Time Error Bounds for Greedy-GQ
Greedy-GQ with linear function approximation, originally proposed in \cite{maei2010toward}, is a value-based off-policy algorithm for optimal control in reinforcement learning, and it has a non-linear two timescale struc…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)