# Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic View

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 54 references that are in the map.
- First posted on arXiv 25 Jul 2022.

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

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Never Give Up: Learning Directed Exploration Strategies](https://mlsanity.com/paper/2002.06038/) (2020)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [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)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Cryptocurrency Portfolio Management with Deep Reinforcement Learning](https://mlsanity.com/paper/1612.01277/) (2016)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [A Discrete-Time Switching System Analysis of Q-learning](https://mlsanity.com/paper/2102.08583/) (2021)
- [Periodic Q-Learning](https://mlsanity.com/paper/2002.09795/) (2020)
- [Final Iteration Convergence Bound of Q-Learning: Switching System Approach](https://mlsanity.com/paper/2205.05455/) (2022)

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

- [A Switching System Theory of Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2605.11021/) (2026)
- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)
- [Sign-Separated Asymmetric Finite-Time Error Analysis of Q-Learning](https://mlsanity.com/paper/2605.16103/) (2026)
- [Finite-Time Analysis of Simultaneous Double Q-learning](https://mlsanity.com/paper/2406.09946/) (2024)

## Abstract (arXiv)

Q-learning has long been one of the most popular reinforcement learning algorithms, and theoretical analysis of Q-learning has been an active research topic for decades. Although researches on asymptotic convergence analysis of Q-learning have a long tradition, non-asymptotic convergence has only recently come under active study. The main goal of this paper is to investigate new finite-time analysis of asynchronous Q-learning under Markovian observation models via a control system viewpoint. In particular, we introduce a discrete-time time-varying switching system model of Q-learning with diminishing step-sizes for our analysis, which significantly improves recent development of the switching system analysis with constant step-sizes, and leads to (Oleft( √fraclog kk right)) convergence rate that is comparable to or better than most of the state of the art results in the literature. In the mean while, a technique using the similarly transformation is newly applied to avoid the difficulty in the analysis posed by diminishing step-sizes. The proposed analysis brings in additional insights, covers different scenarios, and provides new simplified templates for analysis to deepen our understanding on Q-learning via its unique connection to discrete-time switching systems.