# Stability of Q-Learning Through Design and Optimism

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 60 references that are in the map.
- First posted on arXiv 5 Jul 2023.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Regularized Q-learning](https://mlsanity.com/paper/2202.05404/) (2022)
- [A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms](https://mlsanity.com/paper/1912.02270/) (2019)
- [Zap Q-Learning With Nonlinear Function Approximation](https://mlsanity.com/paper/1910.05405/) (2019)
- [Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning](https://mlsanity.com/paper/2002.10301/) (2020)
- [Full Gradient DQN Reinforcement Learning: A Provably Convergent Scheme](https://mlsanity.com/paper/2103.05981/) (2021)
- [A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions](https://mlsanity.com/paper/1502.01953/) (2015)
- [Fastest Convergence for Q-learning](https://mlsanity.com/paper/1707.03770/) (2017)
- [Data-Driven Optimal Control of Affine Systems: A Linear Programming Perspective](https://mlsanity.com/paper/2203.12044/) (2022)

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

- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Convex Q Learning in a Stochastic Environment: Extended Version](https://mlsanity.com/paper/2309.05105/) (2023)
- [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)
- [DASA: Delay-Adaptive Multi-Agent Stochastic Approximation](https://mlsanity.com/paper/2403.17247/) (2024)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)
- [Reinforcement Learning Design for Quickest Change Detection](https://mlsanity.com/paper/2403.14109/) (2024)
- [Optimistic Training and Convergence of Q-Learning -- Extended Version](https://mlsanity.com/paper/2602.06146/) (2026)

## Abstract (arXiv)

Q-learning has become an important part of the reinforcement learning toolkit since its introduction in the dissertation of Chris Watkins in the 1980s. The purpose of this paper is in part a tutorial on stochastic approximation and Q-learning, providing details regarding the INFORMS APS inaugural Applied Probability Trust Plenary Lecture, presented in Nancy France, June 2023. The paper also presents new approaches to ensure stability and potentially accelerated convergence for these algorithms, and stochastic approximation in other settings. Two contributions are entirely new: 1. Stability of Q-learning with linear function approximation has been an open topic for research for over three decades. It is shown that with appropriate optimistic training in the form of a modified Gibbs policy, there exists a solution to the projected Bellman equation, and the algorithm is stable (in terms of bounded parameter estimates). Convergence remains one of many open topics for research. 2. The new Zap Zero algorithm is designed to approximate the Newton-Raphson flow without matrix inversion. It is stable and convergent under mild assumptions on the mean flow vector field for the algorithm, and compatible statistical assumption on an underlying Markov chain. The algorithm is a general approach to stochastic approximation which in particular applies to Q-learning with "oblivious" training even with non-linear function approximation.