Answers.Body: <p>There are different actor-critic (AC) algorithms with different convergence guarantees. For example, AC algorithms where the critic is <em>tabular</em> have different convergence guarantees than AC algorithms where the critic is a neural network (function approximation). Most convergence proofs assume that the actor and the critic operate at different time scales, but, for example, in the paper <a href="http://www.jmlr.org/papers/volume11/dicastro10a/dicastro10a.pdf" rel="nofollow noreferrer">A Convergent Online Single Time Scale Actor-Critic Algorithm</a> (2010) this assumption is not made.</p>
  
  <p>In the paper <a href="https://papers.nips.cc/paper/3258-incremental-natural-actor-critic-algorithms" rel="nofollow noreferrer">Incremental Natural Actor-Critic Algorithms</a> (2007), the authors propose four different AC algorithms that use function approximation (neural networks) to represent the critic. Three of these proposed AC algorithms are based on <a href="https://papers.nips.cc/paper/2073-a-natural-policy-gradient.pdf" rel="nofollow noreferrer">natural policy gradients</a>. In section 6 of the extended and more technical version of the mentioned paper, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.516.4121&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Natural Actor-Critic Algorithm</a> (2007), the authors prove the convergence of the parameters of the policy and value function to a <strong>local maximum</strong> of an <em>objective</em> (or <em>performance</em>) <em>function</em>, which corresponds to the <em>average reward</em> (equation 2) plus a measure of the temporal-difference (TD) error inherent in the function approximation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-13T20:02:17.670Z
Answers.Text: This is the correct answer. I will note that convergence guarantees will also vary dependent on discrete vs continuous state/action spaces.
Answers.UserDisplayName: hisairnessag3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-13T19:43:37.107Z
Answers.LastActivityDate: 2019-09-13T19:49:50.597Z
Answers.LastEditDate: 2019-09-13T19:49:50.597Z
Answers.UserDisplayName: nbro
Body: <p>From my understanding, the critic evaluates the policy (actor) following dynamic programming (DP) or approximate dynamic programming (ADP) scheme, which should converge to the optimal value function after sufficient iterations. The policy (actor) then updates its parameter w.r.t the optimal value function using gradient methods. This policy evaluation and improvement circle are repeated until neither the critic nor the actor changes anymore. </p>
  
  <p>How's guaranteed to converge as a whole? Is there any mathematical proof? Is it possible that it may converge to a local optimal point instead of a global one?</p>
  
Tags: <reinforcement-learning><actor-critic-methods><convergence>
Title: How is the actor-critic algorithm guaranteed to converge?
UserDisplayName: qiang li
ThreadText: # How is the actor-critic algorithm guaranteed to converge?
  
  (Asked by: username_0 on 2019-09-12)
  
  From my understanding, the critic evaluates the policy (actor) following dynamic programming (DP) or approximate dynamic programming (ADP) scheme, which should converge to the optimal value function after sufficient iterations. The policy (actor) then updates its parameter w.r.t the optimal value function using gradient methods. This policy evaluation and improvement circle are repeated until neither the critic nor the actor changes anymore.
  
  How's guaranteed to converge as a whole? Is there any mathematical proof? Is it possible that it may converge to a local optimal point instead of a global one?
  
  **Tags:** reinforcement-learning, actor-critic-methods, convergence
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-09-13. Score: 3
  
  There are different actor-critic (AC) algorithms with different convergence guarantees. For example, AC algorithms where the critic is *tabular* have different convergence guarantees than AC algorithms where the critic is a neural network (function approximation). Most convergence proofs assume that the actor and the critic operate at different time scales, but, for example, in the paper [A Convergent Online Single Time Scale Actor-Critic Algorithm](http://www.jmlr.org/papers/volume11/dicastro10a/dicastro10a.pdf) (2010) this assumption is not made.
  
  In the paper [Incremental Natural Actor-Critic Algorithms](https://papers.nips.cc/paper/3258-incremental-natural-actor-critic-algorithms) (2007), the authors propose four different AC algorithms that use function approximation (neural networks) to represent the critic. Three of these proposed AC algorithms are based on [natural policy gradients](https://papers.nips.cc/paper/2073-a-natural-policy-gradient.pdf). In section 6 of the extended and more technical version of the mentioned paper, [Natural Actor-Critic Algorithm](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.516.4121&rep=rep1&type=pdf) (2007), the authors prove the convergence of the parameters of the policy and value function to a **local maximum** of an *objective* (or *performance*) *function*, which corresponds to the *average reward* (equation 2) plus a measure of the temporal-difference (TD) error inherent in the function approximation.
  
  > **Comments:**
  > **username_2**: This is the correct answer. I will note that convergence guarantees will also vary dependent on discrete vs continuous state/action spaces.  
  
  ---
  
  