  Temporal Difference (TD) algorithms are widely used in Deep Reinforcement
Learning (RL). Their performance is heavily influenced by the size of the
neural network. While in supervised learning, the regime of
over-parameterization and its benefits are well understood, the situation in RL
is much less clear. In this paper, we present a theoretical analysis of the
influence of network size and $l_2$-regularization on performance. We identify
the ratio between the number of parameters and the number of visited states as
a crucial factor and define over-parameterization as the regime when it is
larger than one. Furthermore, we observe a double descent phenomenon, i.e., a
sudden drop in performance around the parameter/state ratio of one. Leveraging
random features and the lazy training regime, we study the regularized
Least-Square Temporal Difference (LSTD) algorithm in an asymptotic regime, as
both the number of parameters and states go to infinity, maintaining a constant
ratio. We derive deterministic limits of both the empirical and the true
Mean-Squared Bellman Error (MSBE) that feature correction terms responsible for
the double descent. Correction terms vanish when the $l_2$-regularization is
increased or the number of unvisited states goes to zero. Numerical experiments
with synthetic and small real-world environments closely match the theoretical
predictions.
