# Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 42 references that are in the map.
- First posted on arXiv 30 Mar 2021.

## Builds on (most cited first, 22 of 22)

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1802.04477/) (2018)
- [Finite-Sample Analysis of Proximal Gradient TD Algorithms](https://mlsanity.com/paper/2006.14364/) (2020)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [Reanalysis of Variance Reduced Temporal Difference Learning](https://mlsanity.com/paper/2001.01898/) (2020)
- [On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence](https://mlsanity.com/paper/1411.3224/) (2014)
- [Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise](https://mlsanity.com/paper/2005.10175/) (2020)
- [Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting](https://mlsanity.com/paper/1809.08926/) (2018)
- [On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning](https://mlsanity.com/paper/1712.09652/) (2017)
- [A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation](https://mlsanity.com/paper/1909.04299/) (2019)
- [SVRG for Policy Evaluation with Fewer Gradient Evaluations](https://mlsanity.com/paper/1906.03704/) (2019)
- [Variance Reduction for Deep Q-Learning using Stochastic Recursive Gradient](https://mlsanity.com/paper/2007.12817/) (2020)

## Built on by (most cited first, 7 of 7)

- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Finite-Time Error Bounds for Greedy-GQ](https://mlsanity.com/paper/2209.02555/) (2022)
- [Regularized Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2401.15196/) (2024)
- [Finite-Time Error Bounds for Distributed Linear Stochastic Approximation](https://mlsanity.com/paper/2111.12665/) (2021)
- [Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Sets](https://mlsanity.com/paper/2510.19950/) (2025)

## Abstract (arXiv)

Greedy-GQ is a value-based reinforcement learning (RL) algorithm for optimal control. Recently, the finite-time analysis of Greedy-GQ has been developed under linear function approximation and Markovian sampling, and the algorithm is shown to achieve an ε-stationary point with a sample complexity in the order of O(ε-3). Such a high sample complexity is due to the large variance induced by the Markovian samples. In this paper, we propose a variance-reduced Greedy-GQ (VR-Greedy-GQ) algorithm for off-policy optimal control. In particular, the algorithm applies the SVRG-based variance reduction scheme to reduce the stochastic variance of the two time-scale updates. We study the finite-time convergence of VR-Greedy-GQ under linear function approximation and Markovian sampling and show that the algorithm achieves a much smaller bias and variance error than the original Greedy-GQ. In particular, we prove that VR-Greedy-GQ achieves an improved sample complexity that is in the order of O(ε-2). We further compare the performance of VR-Greedy-GQ with that of Greedy-GQ in various RL experiments to corroborate our theoretical findings.