Finite Sample Analysis Of Two-time-scale Natural Actor-critic Algorithm

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 *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 *globa

Stats

• citations9
• S2 citations—
• github stars0
• HF likes0
• heat score7.50
• arxiv keykhodadadian2021finite

Related papers

• Finite-time Analysis Of Single-timescale Actor-critic (2022)0.00
• Non-asymptotic Convergence Analysis Of Two Time-scale (natural) Actor-critic Algorithms (2020)0.00
• A Finite Time Analysis Of Two Time-scale Actor Critic Methods (2020)0.00
• Single-timescale Actor-critic Provably Finds Globally Optimal Policy (2020)0.00
• Improving Sample Complexity Bounds For (natural) Actor-critic Algorithms (2020)0.00
• Finite-sample Analysis Of Off-policy Natural Actor-critic With Linear Function Approximation (2021)0.00
• Global Convergence Of The ODE Limit For Online Actor-critic Algorithms In Reinforcement Learning (2021)0.00
• Non-asymptotic Analysis For Single-loop (natural) Actor-critic With Compatible Function Approximation (2024)0.00