Gauss--Newton Temporal Difference Learning With Nonlinear Function Approximation

In this article, a Gauss-Newton temporal difference (GNTD) learning method is proposed to solve the $Q$ -learning problem with nonlinear function approximations. In each iteration, our method takes one Gauss-Newton (GN) step to optimize a variant of mean-squared Bellman error (MSBE), where target networks are adopted to avoid double sampling. Inexact GN steps are analyzed so that one can safely and efficiently compute the GN updates by cheap matrix iterations. Under mild conditions, nonasymptotic finite-sample convergence to the globally optimal $Q$ function is derived for various nonlinear function approximations. In particular, for neural network parameterization with ReLU activation, GNTD achieves an improved sample complexity of $\tilde {\mathcal {O}}(\varepsilon ^{-1})$ , as opposed to the $\mathcal {\mathcal {O}}(\varepsilon ^{-2})$ sample complexity of the existing neural temporal difference (TD) methods. An $\tilde {\mathcal {O}}(\varepsilon ^{-1.5})$ sample complexity of GNTD is also established for general smooth function approximations. We validate our method via extensive experiments on several reinforcement learning (RL) benchmarks, where GNTD exhibits both higher rewards and faster convergence than TD-type methods.