Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

We establish last-iterate convergence rates for off-policy actor--critic methods in reinforcement learning under a single-loop, single-timescale implementation and a broad class of policy updates, including approximate policy iteration and natural policy gradient methods. We prove the first $\smash{\tilde{\mathcal{O}}(\epsilon^{-2})}$ sample complexity guarantee for finding an $\epsilon$-optimal policy, assuming only the existence of a policy that induces an irreducible and aperiodic Markov chain. This stands in stark contrast to the existing literature, where an $\smash{\tilde{\mathcal{O}}(\epsilon^{-2})}$ sample complexity is achieved only through nested-loop updates and/or under strong, algorithm-dependent exploratory assumptions, uniformly across all policies. Our analysis is based on a coupled Lyapunov framework which establishes a geometric convergence rate of the actor, an $\smash{\tilde{\mathcal{O}}(1/T)}$ convergence rate for the critic, and combines the two Lyapunov drift inequalities through a cross-domination property. Our framework naturally handles coupled and potentially unbounded iterates, Markovian noise and time-varying evaluation targets. We believe it to be of independent interest, and applicable to other coupled iterative algorithms.