# Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2020.

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

- [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)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [High-probability sample complexities for policy evaluation with linear function approximation](https://mlsanity.com/paper/2305.19001/) (2023)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [Finite-Time Error Bounds for Greedy-GQ](https://mlsanity.com/paper/2209.02555/) (2022)
- [PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method](https://mlsanity.com/paper/2110.06906/) (2021)
- [A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothness](https://mlsanity.com/paper/2307.15892/) (2023)
- [Regularized Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2401.15196/) (2024)
- [A Unified Off-Policy Evaluation Approach for General Value Function](https://mlsanity.com/paper/2107.02711/) (2021)
- [Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic](https://mlsanity.com/paper/2206.05733/) (2022)
- [Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximation](https://mlsanity.com/paper/2302.13087/) (2023)

## Abstract (arXiv)

Two timescale stochastic approximation (SA) has been widely used in value-based reinforcement learning algorithms. In the policy evaluation setting, it can model the linear and nonlinear temporal difference learning with gradient correction (TDC) algorithms as linear SA and nonlinear SA, respectively. In the policy optimization setting, two timescale nonlinear SA can also model the greedy gradient-Q (Greedy-GQ) algorithm. In previous studies, the non-asymptotic analysis of linear TDC and Greedy-GQ has been studied in the Markovian setting, with diminishing or accuracy-dependent stepsize. For the nonlinear TDC algorithm, only the asymptotic convergence has been established. In this paper, we study the non-asymptotic convergence rate of two timescale linear and nonlinear TDC and Greedy-GQ under Markovian sampling and with accuracy-independent constant stepsize. For linear TDC, we provide a novel non-asymptotic analysis and show that it attains an ε-accurate solution with the optimal sample complexity of O(ε-1log(1/ε)) under a constant stepsize. For nonlinear TDC and Greedy-GQ, we show that both algorithms attain ε-accurate stationary solution with sample complexity O(ε-2). It is the first non-asymptotic convergence result established for nonlinear TDC under Markovian sampling and our result for Greedy-GQ outperforms the previous result orderwisely by a factor of O(ε-1log(1/ε)).