Target Network and Truncation Overcome the Deadly Triad in Q-Learning

DOI10.1137/22M1499261MaRDI QIDQ6148353zbMATH OpenOpenAlexFDO

Authors Zaiwei Chen, John-Paul B. Clarke, Siva Theja Maguluri

Publication date 11 January 2024

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.02628

zbMATH Keywords

\(Q\)-learningfinite-sample analysislinear function approximationreinforcement learning

Mathematics Subject Classification ID

Stochastic approximation (62L20) Learning and adaptive systems in artificial intelligence (68T05) Artificial neural networks and deep learning (68T07) Computational aspects of data analysis and big data (68T09) Markov and semi-Markov decision processes (90C40)

Abstract: $Q$-learning with function approximation is one of the most empirically successful while theoretically mysterious reinforcement learning (RL) algorithms, and was identified in Sutton (1999) as one of the most important theoretical open problems in the RL community. Even in the basic linear function approximation setting, there are well-known divergent examples. In this work, we show that extit{target network} and extit{truncation} together are enough to provably stabilize $Q$-learning with linear function approximation, and we establish the finite-sample guarantees. The result implies an $O(epsilo{n}^{-2})$ sample complexity up to a function approximation error. Moreover, our results do not require strong assumptions or modifying the problem parameters as in existing literature.

Recommendations

• A generalization error for Q-learning
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Q-Learning with Linear Function Approximation
• A finite time analysis of temporal difference learning with linear function approximation
• Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning

Cites work

• \({\mathcal Q}\)-learning
• A concentration bound for contractive stochastic approximation
• A distribution-free theory of nonparametric regression
• A Stochastic Approximation Method
• An analysis of temporal-difference learning with function approximation
• An upper bound on the loss from approximate optimal-value functions
• Asynchronous stochastic approximation and Q-learning
• Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning
• Finite-time bounds for fitted value iteration
• scientific article; zbMATH DE number 5957269 (Why is no real title available?)
• scientific article; zbMATH DE number 1321699 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On the Convergence of Stochastic Iterative Dynamic Programming Algorithms
• Reinforcement learning. An introduction
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning

Cited in

(1)

• Balanced Q-learning: combining the influence of optimistic and pessimistic targets

This page was built for publication: Target Network and Truncation Overcome the Deadly Triad in \(\boldsymbol{Q}\)-Learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148353)