Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximation
This addresses the challenge of sample efficiency in reinforcement learning with nonlinear function approximation, offering a novel method that is incremental but provides strong specific gains.
The paper tackles the Q-learning problem with nonlinear function approximation by proposing a Gauss-Newton Temporal Difference (GNTD) method, achieving improved sample complexities such as O(ε^{-1}) for neural networks and O(ε^{-1.5}) for general smooth approximations, and validating it with higher rewards and faster convergence in RL benchmarks.
In this paper, a Gauss-Newton Temporal Difference (GNTD) learning method is proposed to solve the Q-learning problem with nonlinear function approximation. 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, non-asymptotic 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 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 in several RL benchmarks, where GNTD exhibits both higher rewards and faster convergence than TD-type methods.