Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum
Poster C: Tuesday -- 11:00 - 12:30
Navdeep Kumar, Tehila Dahan, Lior Cohen, Ananyabrata Barua, Giorgia Ramponi, Kfir Yehuda Levy, Shie Mannor
Keywords: Single-timescale actor-critic, Discounted markov decision processes, Sample complexity, Variance reduction, Storm momentum
Single-timescale actor–critic algorithms, where the actor and critic are updated simultaneously using comparable step sizes, are widely used in reinforcement learning due to their practical efficiency. However, the best known global convergence guarantee for discounted Markov decision processes (MDPs) requires $O(\epsilon^{-3})$ samples to obtain an $\epsilon$-optimal policy, leaving a gap from the known lower bound of $O(\epsilon^{-2})$. In this work, we close this gap and establish an optimal sample complexity of $O(\epsilon^{-2})$ for single-timescale actor–critic in infinite-horizon discounted tabular MDPs. Our analysis identifies critic variance as the main bottleneck limiting prior convergence rates. To control this variance, we incorporate STORM-based recursive momentum into the critic updates together with a slowly evolving critic sampling distribution to manage the additional bias caused by nonstationary policy-dependent data. The resulting analysis is challenging due to the strong coupling between actor, critic, and momentum recursions operating at different time scales. We develop refined recursions, construct a new Lyapunov function, and establish an ODE-domination argument to analyze the coupled dynamics. Our results show that variance reduction enables both actor and critic to use step sizes of order $O(k^{-1/2})$, improving upon prior work and yielding the optimal global convergence rate.