AI RESEARCH
Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum
arXiv CS.LG
•
ArXi:2602.01505v2 Announce Type: replace We establish an optimal sample complexity of $O(\epsilon^{-2})$ for obtaining an $\epsilon$-optimal global policy using a single-timescale actor-critic (AC) algorithm in infinite-horizon discounted Marko decision processes (MDPs) with finite state-action spaces, improving upon the prior state of the art of $O(\epsilon^{-3})$. Our approach applies STORM (STOchastic Recursive Momentum) to reduce variance in the critic updates.