# Target Network and Truncation Overcome The Deadly Triad in Q-Learning

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 75 references that are in the map.
- First posted on arXiv 5 Mar 2022.

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

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [The Principles of Deep Learning Theory](https://mlsanity.com/paper/2106.10165/) (2021)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2102.09318/) (2021)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity](https://mlsanity.com/paper/2002.07125/) (2020)
- [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)
- [Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.11612/) (2021)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)
- [Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games](https://mlsanity.com/paper/2112.07859/) (2021)

## Built on by (most cited first, 30 of 31)

- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation](https://mlsanity.com/paper/2210.05918/) (2022)
- [Improving Deep Reinforcement Learning by Reducing the Chain Effect of Value and Policy Churn](https://mlsanity.com/paper/2409.04792/) (2024)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation](https://mlsanity.com/paper/2405.21043/) (2024)
- [Stability of Q-Learning Through Design and Optimism](https://mlsanity.com/paper/2307.02632/) (2023)
- [Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms](https://mlsanity.com/paper/2302.01450/) (2023)
- [Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration](https://mlsanity.com/paper/2504.10865/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [A Note on Target Q-learning For Solving Finite MDPs with A Generative Oracle](https://mlsanity.com/paper/2203.11489/) (2022)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [Multi-Bellman operator for convergence of Q-learning with linear function approximation](https://mlsanity.com/paper/2309.16819/) (2023)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2312.04905/) (2023)
- [Regularized Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2401.15196/) (2024)
- [Enhancing Q-Learning with Large Language Model Heuristics](https://mlsanity.com/paper/2405.03341/) (2024)
- [Dual Approximation Policy Optimization](https://mlsanity.com/paper/2410.01249/) (2024)
- [A Switching System Theory of Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2605.11021/) (2026)
- [Target Updates May Stabilize Linear Q-Learning: Periodic and Soft Dynamics](https://mlsanity.com/paper/2606.02645/) (2026)
- [Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2402.15781/) (2024)
- [Is Exploration or Optimization the Problem for Deep Reinforcement Learning?](https://mlsanity.com/paper/2508.01329/) (2025)
- [Stability and Generalization for Bellman Residuals](https://mlsanity.com/paper/2508.18741/) (2025)
- [Periodic Regularized Q-Learning](https://mlsanity.com/paper/2602.03301/) (2026)
- [Optimistic Training and Convergence of Q-Learning -- Extended Version](https://mlsanity.com/paper/2602.06146/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.08941/) (2025)
- [Functional Critics Are Essential for Actor-Critic: From Off-Policy Stability to Efficient Exploration](https://mlsanity.com/paper/2509.22964/) (2025)
- [Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximation](https://mlsanity.com/paper/2510.01721/) (2025)
- [Continuous-time reinforcement learning: ellipticity enables model-free value function approximation](https://mlsanity.com/paper/2602.06930/) (2026)
- [Geometrically Averaged Hard Target Updates for Linear Q-Learning](https://mlsanity.com/paper/2606.10835/) (2026)

## Abstract (arXiv)

Q-learning with function approximation is one of the most empirically successful while theoretically mysterious reinforcement learning (RL) algorithms, and was identified in Sutton (1999) as one of the most important theoretical open problems in the RL community. Even in the basic linear function approximation setting, there are well-known divergent examples. In this work, we show that textittarget network and textittruncation together are enough to provably stabilize Q-learning with linear function approximation, and we establish the finite-sample guarantees. The result implies an O(ε-2) sample complexity up to a function approximation error. Moreover, our results do not require strong assumptions or modifying the problem parameters as in existing literature.