Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum
This work addresses the sample efficiency challenge in reinforcement learning for researchers and practitioners, representing an incremental improvement over existing methods.
The paper tackles the problem of achieving optimal sample complexity for single-timescale actor-critic algorithms in infinite-horizon discounted Markov decision processes, establishing an optimal sample complexity of O(ε^{-2}) to obtain an ε-optimal global policy, improving upon the prior state of the art of O(ε^{-3}).
We establish an optimal sample complexity of $O(ε^{-2})$ for obtaining an $ε$-optimal global policy using a single-timescale actor-critic (AC) algorithm in infinite-horizon discounted Markov decision processes (MDPs) with finite state-action spaces, improving upon the prior state of the art of $O(ε^{-3})$. Our approach applies STORM (STOchastic Recursive Momentum) to reduce variance in the critic updates. However, because samples are drawn from a nonstationary occupancy measure induced by the evolving policy, variance reduction via STORM alone is insufficient. To address this challenge, we maintain a buffer of small fraction of recent samples and uniformly sample from it for each critic update. Importantly, these mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability.