Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 33 of its 64 references that are in the map. First posted on arXiv 2 Feb 2026.
Builds on
33 of 64 references.
References · 33
- 2014Adam: A Method for Stochastic Optimizationcited by 36,960
- 2015Trust Region Policy Optimizationcited by 2,503
- 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2018Is Q-learning Provably Efficient?cited by 485
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
- 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
- 2017Equivalence Between Policy Gradients and Soft Q-Learningcited by 172
- 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
- 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
21 more
- 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
- 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
- 2022On the Convergence Rates of Policy Gradient Methodscited by 115
- 2021A general sample complexity analysis of vanilla policy gradientcited by 74
- 2024MARS: Unleashing the Power of Variance Reduction for Training Large Modelscited by 59
- 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
- 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
- 2025Benchmarking Optimizers for Large Language Model Pretrainingcited by 53
- 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
- 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
- 2022Finite-time analysis of single-timescale actor-criticcited by 30
- 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 22
- 2024Elementary Analysis of Policy Gradient Methodscited by 17
- 2019On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Costcited by 12
- 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
- 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8
- 2022Actor-Critic or Critic-Actor? A Tale of Two Time Scalescited by 7
- 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
- 2024On the Convergence of Single-Timescale Actor-Criticcited by 3
- 2025Q-learning with Posterior Samplingcited by 1
- 2025Policy Gradient with Tree Search: Avoiding Local Optimas through Lookaheadcited by 1
Built on by
Not cited yet.