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-ε 1-ε 2, the actor error θ k-θ* is O (n 0 3/4 over k 1 over sqrt ε 2+ (1 over n 0) 1/4 1/4 (1 over ε 1)+ (1 over n 0) 1/4) for all k at least 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.