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?


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 (2010) this assumption is not made.

In the paper 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. In section 6 of the extended and more technical version of the mentioned paper, Natural Actor-Critic Algorithm (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.

| improve this answer | |
  • 1
    $\begingroup$ This is the correct answer. I will note that convergence guarantees will also vary dependent on discrete vs continuous state/action spaces. $\endgroup$ – hisairnessag3 Sep 13 '19 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.