Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation

• URL: http://arxiv.org/abs/2406.01762v1
• Date: Mon, 3 Jun 2024 20:05:04 GMT
• Title: Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation
• Authors: Yudan Wang, Yue Wang, Yi Zhou, Shaofeng Zou,
• Abstract summary: Actor-critic (AC) is a powerful method for learning an optimal policy in reinforcement learning. AC converges to an $epsilon+varepsilon_textcritic$ neighborhood of stationary points with the best known sample complexity. This paper analyzes the convergence of both AC and NAC algorithms with compatible function approximation.
• Score: 18.77565744533582
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Actor-critic (AC) is a powerful method for learning an optimal policy in reinforcement learning, where the critic uses algorithms, e.g., temporal difference (TD) learning with function approximation, to evaluate the current policy and the actor updates the policy along an approximate gradient direction using information from the critic. This paper provides the \textit{tightest} non-asymptotic convergence bounds for both the AC and natural AC (NAC) algorithms. Specifically, existing studies show that AC converges to an $\epsilon+\varepsilon_{\text{critic}}$ neighborhood of stationary points with the best known sample complexity of $\mathcal{O}(\epsilon^{-2})$ (up to a log factor), and NAC converges to an $\epsilon+\varepsilon_{\text{critic}}+\sqrt{\varepsilon_{\text{actor}}}$ neighborhood of the global optimum with the best known sample complexity of $\mathcal{O}(\epsilon^{-3})$, where $\varepsilon_{\text{critic}}$ is the approximation error of the critic and $\varepsilon_{\text{actor}}$ is the approximation error induced by the insufficient expressive power of the parameterized policy class. This paper analyzes the convergence of both AC and NAC algorithms with compatible function approximation. Our analysis eliminates the term $\varepsilon_{\text{critic}}$ from the error bounds while still achieving the best known sample complexities. Moreover, we focus on the challenging single-loop setting with a single Markovian sample trajectory. Our major technical novelty lies in analyzing the stochastic bias due to policy-dependent and time-varying compatible function approximation in the critic, and handling the non-ergodicity of the MDP due to the single Markovian sample trajectory. Numerical results are also provided in the appendix.

Related papers

• Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms [49.19842488693726]
  We establish the global convergence of the actor-critic algorithm with a significantly improved sample complexity of $O(epsilon-3)$. Our findings provide theoretical support for many algorithms that rely on constant step sizes.
  arXiv  Detail & Related papers  (2024-10-11T14:46:29Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation [15.319335698574932]
  We show the first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sampling. Results on Open GymAI continuous control tasks.
  arXiv  Detail & Related papers  (2022-02-28T15:16:23Z)
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation [5.543220407902113]
  We develop a novel variant of off-policy natural actor-critic algorithm with linear function approximation. We establish a sample complexity of $mathcalO(epsilon-3)$, outperforming all the previously known convergence bounds of such algorithms.
  arXiv  Detail & Related papers  (2021-05-26T13:35:42Z)
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms [58.57004511121862]
  Actor-critic (AC) and natural actor-critic (NAC) algorithms are often executed in two ways for finding optimal policies. We show that two time-scale AC requires the overall sample complexity at the order of $mathcalO(epsilon-2.5log3(epsilon-1))$ to attain an $epsilon$-accurate stationary point. We develop novel techniques for bounding the bias error of the actor due to dynamically changing Markovian sampling.
  arXiv  Detail & Related papers  (2020-05-07T15:42:31Z)
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods [87.69128666220016]
  We provide a non-asymptotic analysis for two time-scale actor-critic methods under non-i.i.d. setting. We prove that the actor-critic method is guaranteed to find a first-order stationary point. This is the first work providing finite-time analysis and sample complexity bound for two time-scale actor-critic methods.
  arXiv  Detail & Related papers  (2020-05-04T09:45:18Z)
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms [58.57004511121862]
  This paper characterizes the convergence rate and sample complexity of AC and NAC under Markovian sampling. We show that AC and NAC attain orderwise performance improvement over PG and NPG under infinite horizon due to the incorporation of critic.
  arXiv  Detail & Related papers  (2020-04-27T17:11:06Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  This paper provides the first theoretical convergence analysis for two fundamental RL algorithms of policy gradient (PG) and temporal difference (TD) learning. Under general nonlinear function approximation, PG-AMSGrad with a constant stepsize converges to a neighborhood of a stationary point at the rate of $mathcalO(log T/sqrtT)$. Under linear function approximation, TD-AMSGrad with a constant stepsize converges to a neighborhood of the global optimum at the rate of $mathcalO(log T/sqrtT
  arXiv  Detail & Related papers  (2020-02-15T00:26:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.