How is the actor-critic algorithm guaranteed to converge?

Question

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?

Answer 1

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.