Target Network and Truncation Overcome the Deadly Triad in \(\boldsymbol{Q}\)-Learning
Zaiwei Chen, John-Paul Clarke, Siva Theja Maguluri · SIAM Journal on Mathematics of Data Science · 2023
Abstract. [Formula: see text]-learning with function approximation is one of the most empirically successful while theoretically mysterious reinforcement learning (RL) algorithms and was identified in [R. S. Sutton, in European Conference on Computational Learning Theory, Springer, New York, 1999, pp. 11–17] as one of the most important theoretical open problems in the RL community. Even in the basic setting where linear function approximation is used, there are well-known divergent examples. In this work, we propose a stable online variant of [Formula: see text]-learning with linear function approximation that uses target network and truncation and is driven by a single trajectory of Markovian samples. We present the finite-sample guarantees of the algorithm, which imply a sample complexity of [Formula: see text] up to a function approximation error. Importantly, we establish the results under minimal assumptions and do not modify the problem parameters to achieve stability.