Search papers, labs, and topics across Lattice.
This paper analyzes constant-stepsize Q-learning by representing the Bellman maximization error as a stochastic policy, leading to a switched linear conditional-mean recursion. The authors show that the Q-learning error's drift rate is governed by the joint spectral radius (JSR) of the direct switching family, which can be smaller than the standard row-sum rate. They then derive a finite-time final-iterate bound using a JSR-induced Lyapunov function and provide a computable quadratic-certificate version.
Q-learning converges faster than previously thought, thanks to a tighter bound derived from a novel stochastic switching system representation of the Bellman error.
Q-learning is one of the most fundamental algorithms in reinforcement learning. We analyze constant-stepsize Q-learning through a direct stochastic switching system representation. The key observation is that the Bellman maximization error can be represented exactly by a stochastic policy. Therefore, the Q-learning error admits a switched linear conditional-mean recursion with martingale-difference noise. The intrinsic drift rate is the joint spectral radius (JSR) of the direct switching family, which can be strictly smaller than the standard row-sum rate. Using this representation, we derive a finite-time final-iterate bound via a JSR-induced Lyapunov function and then give a computable quadratic-certificate version.
