A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms

Abstract

In this paper, we introduce a unified framework for analyzing a large family of Q-learning algorithms, based on switching system perspectives and ODE-based stochastic approximation. We show that the nonlinear ODE models associated with these Q-learning algorithms can be formulated as switched linear systems, and analyze their asymptotic stability by leveraging existing switching system theories. Our approach provides the first O.D.E. analysis of the asymptotic convergence of various Q-learning algorithms, including asynchronous Q-learning and averaging Q-learning. We also extend the approach to analyze Q-learning with linear function approximation and derive a new sufficient condition for its convergence.

arXiv commentThis paper has been accepted in NeurIPS2020

References in corpus (3)

• A Theoretical Analysis of Deep Q-Learning
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory

Cited by in corpus (5)

• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• Convex Q-Learning, Part 1: Deterministic Optimal Control
• Truncated Emphatic Temporal Difference Methods for Prediction and Control