# Finite-Time Error Bounds for Greedy-GQ

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 6 Sep 2022.

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

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [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)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [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)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms](https://mlsanity.com/paper/2011.05053/) (2020)
- [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)
- [Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis](https://mlsanity.com/paper/2010.13272/) (2020)
- [On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning](https://mlsanity.com/paper/1712.09652/) (2017)
- [Two Timescale Stochastic Approximation with Controlled Markov noise and Off-policy temporal difference learning](https://mlsanity.com/paper/1503.09105/) (2015)
- [Concentration bounds for two time scale stochastic approximation](https://mlsanity.com/paper/1806.10798/) (2018)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)

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

- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Regularized Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2401.15196/) (2024)

## Abstract (arXiv)

Greedy-GQ with linear function approximation, originally proposed in citemaei2010toward, is a value-based off-policy algorithm for optimal control in reinforcement learning, and it has a non-linear two timescale structure with the non-convex objective function. This paper develops its tightest finite-time error bounds. We show that the Greedy-GQ algorithm converges as fast as O(1/√T) under the i.i.d. setting and O(log T/√T) under the Markovian setting. We further design a variant of the vanilla Greedy-GQ algorithm using the nested-loop approach, and show that its sample complexity is O(log(1/ε)ε-2), which matches with the one of the vanilla Greedy-GQ. Our finite-time error bounds match with one of the stochastic gradient descent algorithms for general smooth non-convex optimization problems, despite its additonal challenge in the two time-scale updates. Our finite-sample analysis provides theoretical guidance on choosing step-sizes for faster convergence in practice, and suggests the trade-off between the convergence rate and the quality of the obtained policy. Our techniques provide a general approach for finite-sample analysis of non-convex two timescale value-based reinforcement learning algorithms.