  As an important type of reinforcement learning algorithms, actor-critic (AC)
and natural actor-critic (NAC) algorithms are often executed in two ways for
finding optimal policies. In the first nested-loop design, actor's one update
of policy is followed by an entire loop of critic's updates of the value
function, and the finite-sample analysis of such AC and NAC algorithms have
been recently well established. The second two time-scale design, in which
actor and critic update simultaneously but with different learning rates, has
much fewer tuning parameters than the nested-loop design and is hence
substantially easier to implement. Although two time-scale AC and NAC have been
shown to converge in the literature, the finite-sample convergence rate has not
been established. In this paper, we provide the first such non-asymptotic
convergence rate for two time-scale AC and NAC under Markovian sampling and
with actor having general policy class approximation. We show that two
time-scale AC requires the overall sample complexity at the order of
$\mathcal{O}(\epsilon^{-2.5}\log^3(\epsilon^{-1}))$ to attain an
$\epsilon$-accurate stationary point, and two time-scale NAC requires the
overall sample complexity at the order of
$\mathcal{O}(\epsilon^{-4}\log^2(\epsilon^{-1}))$ to attain an
$\epsilon$-accurate global optimal point. We develop novel techniques for
bounding the bias error of the actor due to dynamically changing Markovian
sampling and for analyzing the convergence rate of the linear critic with
dynamically changing base functions and transition kernel.
