Before revision:  We show that the projection-free TD learning equipped with a two-layer ReLU network of any width exceeding poly( , 1/\epsilon) converges to the true value function with error \epsilon given poly( , 1/\epsilon) iterations or samples, where is an upper bound on the RKHS norm of the value function induced by the neural tangent kernel. Our sample complexity and overparameterization bounds are based on a drift analysis of the network parameters as a stopped random process in the lazy training regime .
After revision:  We show that the projection-free TD learning equipped with a two-layer ReLU network of any width exceeding poly( , 1/\epsilon) converges to the true value function with error \epsilon given poly( , 1/\epsilon) iterations or samples, where We consider two practically used algorithms, projection-free and max-norm regularized Neural TD learning, and establish the first convergence bounds for these algorithms. An interesting observation from our results is that max-norm regularization can dramatically improve the performance of TD learning algorithms, both in terms of sample complexity and overparameterization. In particular, we prove that max-norm regularization appears to be more effective than \ell_2-regularization, again both in terms of sample complexity and overparameterization bounds are based on a drift analysis of the network parameters as a stopped random process in the lazy training regime .