  Actor-critic algorithms are widely used in reinforcement learning, but are
challenging to mathematically analyse due to the online arrival of non-i.i.d.
data samples. The distribution of the data samples dynamically changes as the
model is updated, introducing a complex feedback loop between the data
distribution and the reinforcement learning algorithm. We prove that, under a
time rescaling, the online actor-critic algorithm with tabular parametrization
converges to an ordinary differential equation (ODE) as the number of updates
becomes large. The proof first establishes the geometric ergodicity of the data
samples under a fixed actor policy. Then, using a Poisson equation, we prove
that the fluctuations of the data samples around a dynamic probability measure,
which is a function of the evolving actor model, vanish as the number of
updates become large. Once the ODE limit has been derived, we study its
convergence properties using a two time-scale analysis which asymptotically
de-couples the critic ODE from the actor ODE. The convergence of the critic to
the solution of the Bellman equation and the actor to the optimal policy are
proven. In addition, a convergence rate to this global minimum is also
established. Our convergence analysis holds under specific choices for the
learning rates and exploration rates in the actor-critic algorithm, which could
provide guidance for the implementation of actor-critic algorithms in practice.
