# A Note on Target Q-learning For Solving Finite MDPs with A Generative Oracle

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

## Key facts

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

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Target-Based Temporal Difference Learning](https://mlsanity.com/paper/1904.10945/) (2019)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Periodic Q-Learning](https://mlsanity.com/paper/2002.09795/) (2020)

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

- [Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation](https://mlsanity.com/paper/2411.00610/) (2024)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [Event Tables for Efficient Experience Replay](https://mlsanity.com/paper/2211.00576/) (2022)
- [Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithms](https://mlsanity.com/paper/2605.01778/) (2026)

## Abstract (arXiv)

Q-learning with function approximation could diverge in the off-policy setting and the target network is a powerful technique to address this issue. In this manuscript, we examine the sample complexity of the associated target Q-learning algorithm in the tabular case with a generative oracle. We point out a misleading claim in [Lee and He, 2020] and establish a tight analysis. In particular, we demonstrate that the sample complexity of the target Q-learning algorithm in [Lee and He, 2020] is widetildemathcal O(|mathcal S|2|mathcal A|2 (1-γ)-5varepsilon-2). Furthermore, we show that this sample complexity is improved to widetildemathcal O(|mathcal S||mathcal A| (1-γ)-5varepsilon-2) if we can sequentially update all state-action pairs and widetildemathcal O(|mathcal S||mathcal A| (1-γ)-4varepsilon-2) if γ is further in (1/2, 1). Compared with the vanilla Q-learning, our results conclude that the introduction of a periodically-frozen target Q-function does not sacrifice the sample complexity.