# Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum

arXiv: https://arxiv.org/abs/2602.01505 · HTML: https://mlsanity.com/paper/2602.01505/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 33 of its 64 references that are in the map.
- First posted on arXiv 2 Feb 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Benchmarking Optimizers for Large Language Model Pretraining](https://mlsanity.com/paper/2509.01440/) (2025)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024)
- [On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost](https://mlsanity.com/paper/1907.06246/) (2019)
- [Optimistic Q-learning for average reward and episodic reinforcement learning](https://mlsanity.com/paper/2407.13743/) (2024)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)
- [Actor-Critic or Critic-Actor? A Tale of Two Time Scales](https://mlsanity.com/paper/2210.04470/) (2022)
- [Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation](https://mlsanity.com/paper/2402.01371/) (2024)

## 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.