A Switching System Theory of Q-Learning with Linear Function Approximation

Abstract

Q-learning is a fundamental algorithmic primitive in reinforcement learning. This paper develops a new framework for analyzing linear Q-learning from a switching linear system (SLS) viewpoint, where linear Q-learning denotes Q-learning with linear function approximation. We derive a stochastic SLS representation of the linear Q-learning error and obtain a finite-time error analysis for linear Q-learning through the joint spectral radius (JSR) of the associated SLS family; the JSR is the exact worst-case exponential rate of the corresponding SLSs. The JSR-based rate is tied to the intrinsic worst-case exponential rate of the SLS representation. Moreover, we provide a JSR-based certificate for convergence of linear Q-learning, which can be less conservative than one-step norm bounds.