A Concentration Bound for Two-Timescale Actor-Critic Algorithm

Significant research effort has been directed in recent years towards establishing both asymptotic and non-asymptotic convergence guarantees for two-timescale actor–critic algorithms, where the actor recursion is run on a slower timescale than the critic recursion. This work derives a uniform all-time concentration bound for the actor–critic algorithm with function approximation in the long-run average-reward setting. This bound helps us analyze the behavior of the actor parameter with high probability. We show that, after some finite time, the actor parameter enters a safe region and remains within it thereafter with high probability. Specifically, with probability at least $1-{\epsilon }_1-{\epsilon }_2$, the actor error $\mathrm{\parallel }{\theta }_k-{\theta }^{\ast }\mathrm{\parallel }$ is $O(\frac{n_0^{3\mathrm{/}4}}{k}\frac{1}{\sqrt{{\epsilon }_2}}+{\left(\frac{1}{n_0}\right)}^{1\mathrm{/}4}{\log }^{1\mathrm{/}4}\left(\frac{1}{{\epsilon }_1}\right)+{\left(\frac{1}{n_0}\right)}^{1\mathrm{/}4})$ for all $k\ge n_0$ and sufficiently large $n_0$. We also present experimental results demonstrating that the aforementioned actor error diminishes with the number of actor-parameter updates.