mlsanityData to 7 Oct 2026

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

arXiv 2203.02628 ↗First posted 5 Mar 2022cs.LG math.OC stat.MLcited by 31

Not on the map. Why?

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.

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

Builds on

28 of 75 references.

References · 28

  1. 2018Is Q-learning Provably Efficient?cited by 485
  2. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  4. 2021The Principles of Deep Learning Theorycited by 169
  5. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  6. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  7. 2020Batch Value-function Approximation with Only Realizabilitycited by 103
  8. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  9. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  10. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  11. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  12. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
16 more
  1. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  2. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  3. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  4. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  5. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  6. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  7. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  8. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  9. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  10. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  11. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  12. 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
  13. 2020Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noisecited by 17
  14. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  15. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
  16. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 4; 2024: 6; 2025: 10; 2026: 8.

31 papers.

Sort:

By area:

  1. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  2. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  3. 2024Improving Deep Reinforcement Learning by Reducing the Chain Effect of Value and Policy Churncited by 16
  4. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  5. 2024Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximationcited by 10
  6. 2023Stability of Q-Learning Through Design and Optimismcited by 7
  7. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 6
  8. 2025Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iterationcited by 6
  9. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  10. 2022A Note on Target Q-learning For Solving Finite MDPs with A Generative Oraclecited by 4
  11. 2023Multi-Bellman operator for convergence of Q-learning with linear function approximationcited by 3
  12. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
19 more
  1. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
  2. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  3. 2024Enhancing Q-Learning with Large Language Model Heuristicscited by 2
  4. 2026A Switching System Theory of Q-Learning with Linear Function Approximationcited by 2
  5. 2026Target Updates May Stabilize Linear Q-Learning: Periodic and Soft Dynamicscited by 2
  6. 2024Regularized Q-Learning with Linear Function Approximationcited by 1
  7. 2024Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximationcited by 1
  8. 2024Dual Approximation Policy Optimizationcited by 1
  9. 2025Is Exploration or Optimization the Problem for Deep Reinforcement Learning?cited by 1
  10. 2025Stability and Generalization for Bellman Residualscited by 1
  11. 2026Optimistic Training and Convergence of Q-Learning -- Extended Versioncited by 1
  12. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  13. 2025Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximationcited by 0
  14. 2025Functional Critics Are Essential for Actor-Critic: From Off-Policy Stability to Efficient Explorationcited by 0
  15. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  16. 2026Periodic Regularized Q-Learningcited by 0
  17. 2026Continuous-time reinforcement learning: ellipticity enables model-free value function approximationcited by 0
  18. 2026Geometrically Averaged Hard Target Updates for Linear Q-Learningcited by 0
  19. 2026Limiting-Kernel Q(λ): Bridging Short and Long Horizonscited by 0