A Small Gain Analysis of Single Timescale Actor Critic
This work provides a theoretical improvement in sample complexity for actor-critic methods, which is incremental as it builds on existing analysis frameworks.
The paper tackles the problem of analyzing actor-critic methods with proportional step-sizes and single-sample critic updates, proving that it finds a stationary point and achieves a sample complexity of O(μ^{-2} ε^{-2}) for an ε-approximate stationary point, where μ is the critic's condition number.
We consider a version of actor-critic which uses proportional step-sizes and only one critic update with a single sample from the stationary distribution per actor step. We provide an analysis of this method using the small-gain theorem. Specifically, we prove that this method can be used to find a stationary point, and that the resulting sample complexity improves the state of the art for actor-critic methods to $O \left(μ^{-2} ε^{-2} \right)$ to find an $ε$-approximate stationary point where $μ$ is the condition number associated with the critic.