# Fastest Convergence for Q-learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2017.

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

- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Stability of Q-Learning Through Design and Optimism](https://mlsanity.com/paper/2307.02632/) (2023)
- [Markov Chain Variance Estimation: A Stochastic Approximation Approach](https://mlsanity.com/paper/2409.05733/) (2024)
- [Asymptotic Analysis of Sample-averaged Q-learning](https://mlsanity.com/paper/2410.10737/) (2024)
- [Optimistic Training and Convergence of Q-Learning -- Extended Version](https://mlsanity.com/paper/2602.06146/) (2026)
- [Regularized Q-learning through Robust Averaging](https://mlsanity.com/paper/2405.02201/) (2024)

## Abstract (arXiv)

The Zap Q-learning algorithm introduced in this paper is an improvement of Watkins' original algorithm and recent competitors in several respects. It is a matrix-gain algorithm designed so that its asymptotic variance is optimal. Moreover, an ODE analysis suggests that the transient behavior is a close match to a deterministic Newton-Raphson implementation. This is made possible by a two time-scale update equation for the matrix gain sequence. The analysis suggests that the approach will lead to stable and efficient computation even for non-ideal parameterized settings. Numerical experiments confirm the quick convergence, even in such non-ideal cases. A secondary goal of this paper is tutorial. The first half of the paper contains a survey on reinforcement learning algorithms, with a focus on minimum variance algorithms.