Finite-time Analysis Of Asynchronous Q-learning Under Diminishing Step-size From Control-theoretic View

Abstract

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 \(\mathcal\{O\}\left( \sqrt\{\frac\{log k\}\{k\}\} \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 new

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keylim2022finite

Related papers

• A Discrete-time Switching System Analysis Of Q-learning (2021)8.35
• From Set Convergence To Pointwise Convergence: Finite-time Guarantees For Average-reward Q-learning With Adaptive Stepsizes (2025)0.00
• Finite-time Analysis For Double Q-learning (2020)0.00
• Deep Q-learning: Theoretical Insights From An Asymptotic Analysis (2020)10.35
• Finite-time Analysis Of Minimax Q-learning For Two-player Zero-sum Markov Games: Switching System Approach (2023)0.00
• Finite-time Error Analysis Of Soft Q-learning: Switching System Approach (2024)0.00
• Constant Stepsize Q-learning: Distributional Convergence, Bias And Extrapolation (2024)0.00
• Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35