On the role of overparameterization in off-policy Temporal Difference learning with linear function approximation
Authors: Valentin Thomas
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
optimization
ranoverparamerizationdom matrix theory
random graphs
overparameterization

Abstract: Much of the recent successes of deep learning can be attributed to scaling up the size of the networks to the point where they often are vastly overparameterized. Thus, understanding the role of overparameterization is of increasing importance. While predictive theories have been developed for supervised learning, little is known about the Reinforcement Learning case. In this work, we take a theoretical approach and study the role of overparameterization for off-policy Temporal Difference (TD) learning in the linear setting. We leverage tools from Random Matrix Theory and random graph theory to obtain a characterization of the spectrum of the TD operator. We use this result to study the stability and optimization dynamics of TD learning as a function of the number of parameters.

On the role of overparamettrization in off-policy Temporal Difference learning with linear function approximation
Valentin Thomas
Mila, Université de Montréal
vltn. thomas t @maal. com
Abstract
Much of the recent successes of deep learning can be attributed to scaling up the size of the networks to the point where they often are vastly overparameterized. Thus, understanding the role of overparameterization is of increasing importance. While predictive theories have been developed for supervised learning, little is known about the Reinforcement Learning case. In this work, we take theoretical approach and study the role of overparameterizztion for off- off-policy Temporal Dif- ference (TD) learning in the linear setting. We leverage tools from random matrix theory and random graph theory to obtain characterization the spectrum of the TD operator. We use this result to study the stability and optimization dynamics of TD learning as a function of the number of parameters.
1 Introduction
Occam's razor principle states that among many plausible explanations, the simplest one is the most likely be true. In statisties and machine learning, this is often interpreted as models with a restricted number of parameters should be privileged as they generalize better (Akaike) 1974). This view is supported by the classical bias-variance trade-off which implies that models that are too flexible are bound to overfit (Geman et al. 1992). Yet, deep neural networks with more parameters than training data points achieved remarkable performance in many domains (LeCun et al. 1989; Krizhevsky et al. 2012) Devlin et al.) 2018). challenging this conventional wisdom. significant understanding of this apparent tension has been reached in recent years. large body of work using tools from random matrix theory has shown that, in models with random features, overparameterization does not lead to overfitting but instead better generalization (Belkin et al. 2020).. This phenomenon is known double descent and unifies the traditional and modern understanding of bias and variance. Importantly, Kuzzorskii et al. (202T) has shown that the double descent phenomenon is in large part explained by purely optimization rather than label noise. Following their insight, we mainly take an optimization approach in the rest of our paper.
While we now have theory of overparamettrrizatin in supervised learning, the theoretical analysis of overparameterrizaton in the reinforcement learning (RL) setting is largely unexplored (Xiao al., 2021]. Indeed, RL poses several new additional challenges. First, the agent has to interact with an environment whose structure may be complex. Second, each state may not be sampled with equal probability while each datapoint is usually sampled uniformly in supervised learning. In this work, we focus mainly on policy evaluation, i.e evaluating the expected return of fixed policy. More precisely, we study the behavior of Temporal Difference learning (Sutton) 1988) which has become ubiquitous for policy evaluation modern Deep RL Mnnih et al., 2013 Haarnoja et al. 2018).
Our contributions are, in the limit of large number of states and parameters: 1) We introduce a class of random graphs for which we can compute analytically the spectrum of the TD operator
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

when using uniform off policy sampling, 2) we derive approximations for the largest and smallest eigenvalue the non-uniform case. Furthermore, we analyze the behavior of the traditional Mean Square Bellman Error (MSBE) when learning with TD(0) and show that 3) it exhibits double descent phenomenon similar to supervised learning but with multiplicative factor depending on the discount factor in the overparameterized regime and 4) the asymptotic residual MSBE displays a peaking behavior near the interpolation threshold (when the number of parameters approaches the number of states) that is specific to RL. Finally, 5) we showcase how the non-stationarity of the policy can make the optimization of the value function unstable. All of these points are motivated theoretically and empirically validated small gridworlds MDPs.
2 Background
2.1 Value estimation
Definition: We place ourselves in the Markov Decision Process (MDP) setting (Puterman) 2014) defined by {S, A, Pan-sa r; 7; Po)) where S and A denote the finite state and action spaces, Psa-ts E RRSS--A is the environment transition probability matrix and r E RISH-AI de- notes the (deterministie) reward vector. Y [0, 1[ is the discount factor, and lastly, Po is the initial state distribution. For a given policy л. i.c a distribution over actions given a state, the goal of value estimation is to be able to estimate the expected discounted return q=(s,a) a) Ep a "'r,,,
a). This quantity is also known as the state-action value or the O-function. Furthermore, it can be written as the solution of the Bellman equation (Bell-) man 1954 q" (x, = r(s,a) a) + 7'E,,, [9 (5', a')] By defining Pa | [S]+AA] the state-action to state-action transition matrix, we can write it in matrix form
= s, 8,00
(1) Linear function approximation: While Equation ① can be solved efficiently when r, P known and when n = |S| |A|] is not too large, in many cases this cannot be computed. One solution to introduce parameter vector 0 E Rp and feature matrix & E R= and optimize to approx- imate q" as q" x 40. This is referred to as the Linear Function Approximation (LFA) setting.
q"' -r---pP
Temporal Difference with LFA: Estimating the Q-function in the Linear Function Approximation setting can done using the well-known algorithm TD(0) (Sutton) 1988) whose expected update is
0.+1 02 t E(r 7P=00, -.0.)
where E is the off-policy distribution matrix, a X n diagonal matrix with positive entries summing to 1, weighting each state-action by their probability of being sampled. Contrary to gradient descent with an appropriate step-size, TD(0) is not guaranteed to converge as the matrix 4b T EI,, yP y might have a negative eigenvalue. This phenomenon is known as the deadly triad as it can only happen when we are (i) off- oof-colicy (ii) using function approximation and (iii) bootstrapping on the
next value as TD(0) does (Bird 1995 Tsitsiklis & Van Roy 1997 Van Hasselt al., 2018).
2.2 Random Matrix Theory
Extremely relevant in the study of least squares with random features are matrices from the Wishart distribution (Wishart 1928). These matrices can be written as _ for a n x p matrix with entries of zero mean, unit variance and bounded 4th moment sampled independently and identically distributed. In that case, when p, n - do and the ratio converges to a finite limit ni P/n = =J0, +ool, the empirical spectral distribution converges to the Marchenko-Pastur (Mareenko & Pastur 1967) (MP) distribution whose density can be written as
Wishart matrices:
du(x=) max (1- 1/,,0) (o) (x)dr= 2mp (or > (Amax x:) 1 Amane) (2) (x)
(3)
where 1a(-) is the indicator function, valued 1 if E A, 0 otherwise and max (1 1/2, 0} o00) (z) are the eigenvalues, which exist when p 2 n, Amax = (1 + vp) the largest, and X X
(1 2 the smallest non-zero eigenvalue.
Note that we study here the expectation Bellman equation, not the optimality Bellman equation which would feature max operator over the next action.
2

---

Wigner (1955) historically introduced and studied symmetric n x n matrices of the form W where W Waj, 1 2 J are sampled i.dd from law of mean 0 and unit variance
Wigner-type matrices:
for i 2 1 vn W has a real spectrum which converges to the semi-cirele distribution dp(x))
V4 22
2.2 dr. When non-symmetric, the spectrum converges to the complex unit disk(= E
2
C,
[2| I
Tao et al. 2010).
2.3 Random graphs
Random graphs are useful models infer structural spectral properties of typical graphs. The ear- liest theoretical analyses of random graphs that we are aware of were done independently by [Erdös] et al. (1960) and Gilbert (1959). The model introduced in Brdōs al. (1960) random graph where each of the n nodes is connected at random to d others. The second model (Gilbert 1959) is slightly different as each node is independently connected any other with probability μ e e|0, 1[. We refer to the first one as the d-regular vedōs-Rényi model G(n, (n, d) and the second one as the Erdös- Pedōs-Rééni--Gee Reiss-Renn--ibber G(n, p)) model.
Given the adjacency matrix A, with A; = 1 if is connected to j. is possible to construct a matrix P by renormalizing the rows of A so that P is stochastic matrix (positive entries and rows summing to 1). P corresponds to the Markov transition matrix of a random walk on the graph and is connected the (lomaii-or Laplacian L by L I, P. For many classes of random graphs.
the spectrum of these quantities is known (Zhao 2012 Tran et al. 2010
3 Spectrum of TD: from random graphs to spiked models
3.1 From Ordinary Least Squares to TD(0)
Random matrix models have been used in supervised learning, especially in the simple least squares model (Cun et al. 1991 Hastic et al. [019 Derezinski et al. 2020). to explain phenomena arising in deep learning. Indeed, while much simpler than large neural networks, these models can shed light on the optimization and generalization behavior of vastly overparameterized models (Pennington Bahri 2017, Wei et al. 2022). something that most traditional complexity measures could not (Zhang et al. 2021 Dziugaite et al., (022)).
Using gradient descent on least square problem, our parameter update can be written as
0241 - 0" = (Ip 7 T2) (0. - 0*)
(4)
for 4 P the feature matrix and 0* the solution found by gradient descent. When choosing the learning rate 17 optimally, the convergence rate is expressed as Amax/Aminn for X respectively
Amax/> man
Amax. the smallest, resp. largest, non-zero eigenvalue of TT (Nsstrrvv 2003
When & has i.i.d entries with zero mean, unit variance and bounded 4th moment, as we will consider in the rest of this paper, 1 T & follows the Wishart distribution. In particular, we have analytical expressions for the asymptotic minimum and maximum eigenvalue (section 2.2]. When
2 2 1. This function has asymptotes at 1, for p = on) or n o(p) and diverges when = p. This peak-shaped function can also be observed empirically in more complex models such as kernel methods (Poggio et al., 2019) and neural networks in the limit of infinite width as they are in the Neural Tangent Kernel regime (Lee et al.,
limp,n+to p/n- = p. we have Amss/Ati. + (i-v
2017 Jacot et al. 2018).
However, when using TD(0), presented in section 2.1 the feature covariance matrix & T would be replaced by & "(I,, 7 While Xiao et al. (022)) derived worst-case bounds for overparameterizee TD, their dependency of the overparamerization ratio p p/n is not obvious. In this work we chose to use tools for random matrix theory for modeling the behavior of TD. While we can model & as an i.i.d matrix, it is not obvious how model E and pD in realistic manner that would still allow us to characterize the spectrum of the TD operator 4 'II,, P d.
and an additional light tail decay condition, weaker than the bounded 4-th moment one both in probability and almost surely.
Tao & Vu 2012)
3

---

2 [aml the (modulus) ordered eigenvalues of its For general E and P no closed form solution for the spectrum exists. We believe this is one of the key reasons why overparameterization
Temporal Difference learning has not been studied extensively. Thus, finding good typical models for p is of utmost importance, and the next section will introduce a class of models for which the spectrum of TD can be computed.
3.2 p as the Markov transition matrix of a random graph
In RL, PT is the Markov transition matrix of random walk when sampling from æ. We will assume in the rest of the paper that the Markov chain is irreducible and aperiodic so that P has a unique stationary distribution denoted d..
As we wish to understand the expected behavior of the TD algorithm, we propose in this subsection a simple yet expressive model of P that will allow us to do so. As random graphs are used to model properties of typical graphs, a candidate for model of P would be to take the Markov transition matrix of random graph. However, random graphs, at least the Errōs-Rényi(-Gilbert type ones, are not able natively to take into account the impact of π, most importantly the fact that some state-actions are visited more often than others under dx the stationary distribution of x. In this subsection, we propose simple model for PT, denoted by P which is the Markov transition matrix of a (n, μ)) graph deformed by d..
Let us start with an undirected graph of the type (4). To take into account the state-action visitation d,, we construct the diagonal matrix D so that D = diag(d,)) Now, we define the deformed adjacency matrix A x as A A nAD, where A is the original adjacency matrix. revert back to the original case A= A. This construction keeps the
When d, is uniform, same edges as in the original graph but re-weights them by how likely d, would visit that state- action. We can informally write the Markov transition matrix associated with this deformed graph 4 1 1,,d +X* where (i) d is deterministic rank one matrix associated to the eigenvalue 1 as I 1 and (ii) X = -V "(I-")
# yn WD,, is stochastic matrix of null expectation as 1 W vn a Wigner-type matrix with zero mean and unit variance. It can be tempting to understand under which conditions the stochastic part becomes negligible and what it entails. As we will see shortly, this setting will reveal itself to be of importance when studying the spectrum of TD.
Definition 1 (Asymptotically well well-connected graphs). We say a graph G is asymptotically well- connected |A2l E o(1) for = A Da2 Markov transition malrix.
The choice for the name of Definition I comes from the fact that the second smallest eigenvalue of the Laplacian is related to the presence of bottlenecks in the graph through Cheeger's 's inequal- ity (Cheeger 1970).
Example. Graphs of the type G(n, 14) (resp. G(n, d)) are asymptotically well-connected their expected degree d nu (resp. d) grows to too with n, i. 1 E o(d) (Zhao 2012 Tran al. 2010
Proposition 3.1. For the de-demomedd G(n, p)) graph studied above, assuming pa 1, dd + X", then the graph is asymptotically well-connected if in nllo E o(vd).
This again generalizes the uniform case as, when dı is uniform, the condition becomes equivalent to 1 E o(d) as in the example. In the non-uniform case, this condition entails that either d spreads efficiently across states, the degree d rises fast enough that those states are still visited sufficiently often. Note that the asymptotically well-connected condition is also satisfied we use longer back-ups of length h such that l grows with to +oo, i.e o(k) for the TD update. See Lemma B. 2 for details.
In those cases, we have
D = 1. + o(1
(5)
This approximation is particularly interesting it asymptotically conserves the left and right eigen- vectors, d and 1,, of the original pd associated to the eigenvalue 1. Furthermore, if all state- actions are reachable, the sequence of matrix power iterates of p (P*)* converges to 1,
'Derivation can be found in Appendix.

---

While we are not the first to use tools from graph theory in the context of RL. related works we are aware of (Mahadevan & Maggioni 2007 Machado et 2017 2018 Wu at. 2018) take a differ- ent approach and leverage eigenvectors of the Markov transition matrix (or Laplacian) to construct better representations for the value function or use them as options. contrast, we use spectral properties of pa to study the convergence of Temporal Difference learning.
3.3 Spiked Wishart model for TD with uniform sampling
Now that we have a simple random graph model for P", we focus on estimating the spectrum of 4 E(,, - >P*) For simplicity, we assume the off-policy sampling is done uniformly, i.e E = L While this assumption is not realistic in most RL settings, it is still of interest in the context of dynamic programming where we have access all the states.
Proposition 3.2 (Spiked MP). If pr² < the spectrum of _ (In - (P") converges to the Marchenko-Pase law with parameter p. When pr² ž 1, there is a phase transition (Baik et al. 2005 for the minimum non-zero eigenvalue X which separates from bulk and converges
min
0.8
X Xilked
- 70 7)
(6)
p/n-tp
Note that the phase transition is smooth as for p = 1/7², Aspiked (V -112-112 1)3.
Vast overparameterriation and tabular case: An interesting regime is when p > 7 1. In that case, the maximum eigenvalue of the MP law and the spiked one differ by factor H = T-y² the effective horizon of the problem, as limp-sso Amax/ - - In the tabular regime, = I,, As P has eigenvalues in [-1, 1], the eigenvalues of I >P are in [1 71 + 7/. This would give a worst case ratio of T which, up to factor 1 + S 2, is the same as the vastly overparameterized case above. As these eigenvalues govern the optimization speed of TD, the vastly overparameterized case and the tabular can be thought of as comparable.
1
3.4 Non-uniform off- off-policy sampling
In the previous subsection were able to characterize the spectrum of O ->Tjo assuming = a II. In this subsection we analyze the more general case where E is not uniform. However by doing so, lose guarantees and must resort to approximations. First, we analyze the eigenvalues
1
of (I, ). rather, in the limit of large n, the eigenvalues of E(T, ).
Lemma 3.1. Iff= di aiig.E...... En) is non-singular, the eigenvalues of ( satisfy
secular equation (Golub 1973)
E dx(i) &
t=1
This expression is another form of the characteristic polynomial of a matrix whose roots are its eigenvalues. However, this form enables us to derive approximations more easily. In particular, for the least visited state-action m arg min;:.1..... Ei, if &m & E + m, we have for X R &m i * m. From this assumption, we derive an approximation for the minimum eigenvalue of E(L, - P
that - E.
1
Lmin Em 1- (m)
(8)
This eigenvalue is inferior to S. and reflects the interaction between the off-policy distribution and the discount factor. At worst, if d, mostly visits state m, it will be close to &m (1 - ?) which is the product of the minimum eigenvalues E and I, -P= A similar expression can be derived for the maximum eigenvalue under similar assumptions.
Now, again reasoning approximately, if that eigenvalue was very small compared to the other ones who would form bulk of similar values, we could expect & T[I,, >P*) o have similar spiking behavior as before. However, in that case, the spiking eigenvalue would be
x B nemim (p
(9)
n-mmm
5

---

While less simple than the estimators developed in the last subsection, we will see in Section 5 thatt it still accurately predicts the smallest non-zero eigenvalue.
Optimizing with Temporal Difference learning
4.1 Decomposition of the error
Using results about the spectrum of the TD operator shown in the last section, we analyze the behavior of the Mean Square Bellman Error LMSBE( (q:) 2/1r + 7P* qu qell during the
optimization. In particular, assuming 4 E[,, ?P') is non-singular for
DdTD ( EI,, -- PT - ETrr p q"' = (I,, PP*) - pf
QID =
the q-value asymptotically reached by TD(0), can decompose this enoor into two components. Lemma 4.1 (Decomposition of the error). For qr = +6, where 0₂ is updated with TD(O) (eq. (2). have the following decomposition
q: ll
bl l/q:
9m l22 ||r 7 qnD
qrol==
(10)
where x x
Ex is the 2-norm in metric E.
Following Bottou & Bousquet (007 we refer to ||q qmDl2 the approximation enror and ||r 7 3mPaqm qTD QTD /l= as the estimation error. The factor < I comes from bounding the spectral norm of (I, ?P*) in metric E. Beyond this factor, we are not exactly in the same setting (Bottou & Bousquet, 2007) the asymptotic TD(0) value estimate qTD may not be the one reaching the lowest estimation error, as known in the RL community (Scherrer 2010)). Indeed, TD(O) finds the minimum of the Mean Square Projected Bellman Error (MSPBE) but not of the MSBE (Sutton & Barto 2018). However in practice it is common to minimize the MSBE as it does not require expensive projection step.
4.2 The ordinary behavior of the approximation error
In this subsection, we take look at the approximation error, i.e how efficiently we converge to QTD- Proposition 4.1. Let assume that + E(I, -P"" is diagonalizable QAQ-1, and that its spectrum is real and positive. Denoting by A and Amax its smallest non-zero and largest eigenvalues, for x Awas
Amax//A x
<
K²2 1<2//0 9rdl2
(11)
Amax/ t +
where K (() when p and K (Q) when p where the condition number.
The assumptions above can seem strong however they are verified under our model (cf Section (33)). This is slightly more general version of the linear convergence of gradient descent, however, the TD operator may not be diagonalizable in an orthonormal basis, we incur an additional factor K22
4.3 The singular behavior of the estimation error
Now turn attention to the second term; the estimation error which is the residual error after + +o0 steps. In supervised learning, we expect this error to be the usual bias our algorithm and thus decrease as p/n increases until
for which the bias would reach 0 as it is possible to interpolate the data. However, reinforcement learning, the behavior of this term can quite different, in particular it can be non monotonous.
Proposition 4.2. Let assume P satisfies the well-comnected property, propert ie that it is asymptotically rank one
2x (TT,r) (()r)+((-)))))))) - )2g TH 1, (d [r)2 II,
lim 00 P/a-tp
[1 -P" pm r|] ||
(d (T)
1-ap

---

where II is the orthogonal projector onto the span of d in norm E: II 4 =Φ) I, IT is its complement, and p = II,,
Φ T
II
When 7 0. i.e we just perform reward regression, this equal to |TT, r which is exactly the residual error in that our representation cannot capture. When > 1, 111 0 so the limit is zero as we expect from a model able to interpolate the data. However, there is a behavior here not present in supervised learning. When P ~ 1, which we can expect when I1 is closer to identity, i. p close to but less than n, a peaking behavior of the estimation error can happen.
Replacing II by its expectation IIn above can lead to an equation simpler to analyze, albeit biased (p) (1 - p) (|| + TP
2 1- rd r) + (d 1- -2-)))
(12)
This phenomenon might appear counter-intuitive as we would expected our error to decrease with p. We provide few insights to make sense of this, First, when 7 increases, so does the scale of the Q-function, so we can expect our errors to get bigger. Second, using random features & informally has a smoothing effect, stronger when is small, which causes the reduction in magnitude from - - to I- This can be observed in the proof in appendix. Finally, peaking behaviors of TT such as this one have been observed in the community (Scherrer 2010 but not theoretically explained in general setting as far as we know.
4.4 Beyond stationary sampling
Until now, we always mentioned n as the number of state-action pairs with the assumption that E was non-singular, i.e that our off-policy sampling visited all the state-actions. Here, we take closer look at what happens when this not the case. In particular, we study a simple toy model where we assume E only visits miis(t) states at time with uniform probability. This simply changes all the n by Tyyis in the previous results. As often observed during training, at f = O, æ might start as a more exploratory policy (Nivis (1 0) high) and over time converges on more deterministic solution (Nvvs()) (t) low). This can be problematic when performing TD learning with a fixed stepsize 1/. In that case, under the spiked model developed in Section 3.3 2/ A'ax or equivalently
we need to ensure 1) S (11+////n(()))
(t) 2 (V²-1))
(13)
As niis (t) can typically decrease, this condition can be broken and thus TD learning will diverge. We conjecture this phenomenon may be related to the popularity of adaptive step size methods in RL over fixed step size ones.
5 Experiments
In all the experiments we use & i.i.d with normal entries. Per the universality property, our theoretical results hold for all distributions satisfying the hypotheses in Section 2.2
Study of the spectral distribution: On Figure D we validate the theory and approximations of Section 3 For an asymmetric random graph n 4000, l = 1/2, the spectrum of P (a) has an eigenvalue at and the rest of order 1/v= (Bordenave et al., 2012). As predicted, the spectrum of the TD operator matches closely spiked MP distribution (b). When the graph does not satisfy the well-connected property, for instance on a rooms domain (n = 4096, л stochastic (c) the spectral distribution is more complex (d). The relative error on X is respectively 0.3% and 2%. Despite this, we show that the empirical and theoretical (eq. (9) values for Xtt and Amax the 4 rooms domain (n = 256) closely match, both for E uniform or highly ill-conditioned with evenly spaced & so that max; & 2000. While (b) and (d) show how violating the asymptotically well- min; E connected property breaks our spiked MP distribution result, we show on (e) and (f) that the extreme eigenvalues, which the ones that matter for optimization results, still well predicted, even in more complex settings.
$ 'when II, by rotational invariance Φ; we TT[T]- = pI,, thus E. = p. We sampled (a]s)) Uniform(O, 1] and renormalized.
7

---

0.5
Sylkk
10"
Imagineey (Mr)
0.4
10
0.000
0.3
10
0.2
Tramieical
0.1
Eneaikkal Juss
0.0
Aon Gibeols
16
Eigenvalues
p-pin
(a) X(P) random graph
(c) XTTD) random graph
(c) ((D) for I (4 rooms)
0.5
0.2
Splic vi
+
Imaginary
0.0
0.3
-022
0.2
0.1
-1.0
Real
0.0
10"4
10
12
10
(b) A(P") rooms
Egenvalues
p-pin
(d) X(TD) 4 rooms
(1 A(T)) for I. rooms)
Figure 1: (a) and (b): scatterplot of the spectra of the Markov transition matrix for G p)) graph and the rooms domain. (c) and (d): spectral distribution for the TD operator for = 2. When the well-connected assumption verified (a), the spectral distribution a spiked (x) Marchenko-Par Pastur (MP) law (in orange) (c). When the assumption is violated and p øé 1, (b), the distribution bleeds out of the MP support, yet the minimum eigenvalue is still close to the spike (d). On (e) and (f) we compare our prediction of the extreme eigenvalues X and Amax of the TD operator on the 4 rooms domain (Sutton et al. 1999) (b) function of p/n. We plot the empirical extreme eigenvalues (dotted) vs (e) MP theoretical ones (eqs. 3 6 for uniform and (f) approximation in eq. (9) for E\\ non-uniform. Shaded areas a 95% confidence interval when randomizing & and a (10 seeds).
0023
0025
0022
1203
0.35
0:35
R.22
0.000
00100
0.000
6000
0.00
0.00
0.50
3.00
1.0
(a) 7 0.1, d 0.08
(b) 0.98, di_ 0.02
(c) 0.98, d,. Rz 0.07
Figure 2: Value of the MSBE as function of the ratio p/n for various iterations T during optimiza- tion. T' +oo corresponds to the asymptotic solution found by TD(0) (eq. (IO). We use uniform sampling (E I.)) On (a), for low 7 we observe a behavior similar to supervised learning where the residual error decreases and reaches ( at p is small. (c) As d r is higher, the peaking terms T- are non-neglig, Shaded areas are a 99% confidence interval over randomness of tn and & (100 seeds).
(b) displays similar behavior as the term d
Optimization behavior TD: On Figure 2 we discuss the results of Section 4 We use again a 4 rooms domain with a fixed stochastic policy and study the Bellman eπror during training. On all subfigures of Figure 2 we observe that for p >> or p < 1, the optimization faster as the curves for low T are much closer to the asymptotic solution T +oo (computed analytically) than for p = 1. This is in line with the result of section 4.2 for a spiked model: the ratio of eigenvalues which governs the optimization speed is Amax/X / + for & and to T- for > 1 while it diverges for p + 1. This leads classical double descent phenomenon on (a)

---

t-03
13
4.22
10
0.5
100
2.82
02
10
1.0
e-greediness
(b) Probability of divergence given step size and greediness.
(a) d, 4 rooms for different
Figure 3: (a): Example of the discounted state distribution in a small rooms domain for varying e-greedy policies. (b) The probability of divergence TD as function of the step size 7) and the c-greediness. For each point we report the probability it leads to divergence computed over 100 random T: from yellow (0%) black (100%).
and (b) purely due optimization as predicted by Kuzborskij al. (2021). On (a) and (b) because either 7 or d r small, the terms order I-7ø are negligible and thus it behaves similarly to supervised learning. On (c), the term Impp dominates and we observe the peaking behavior of the
estimation error (Section 4.3
Furthermore on Figure in appendix we study how our model and match the observed peaking behavior.
its approximation of Section 3.3
Stability and non-stationarity: On Figure 3l we highlight how E can affect the convergence of TD (p = 200). For this, we use a small 4 rooms (n 144) environment and compute an optimal deter- ministic policy =². Then, by varying the of e-greedy policy based x², we analyze which combination of step size 1) and e would lead to convergence. On (a). we show the discounted state distribution for various e where larger lead to more exploration. While our theoretical argument in Section 4.4 was about the number of visited states, we take here more general and realistic approach where the state visitation is controlled by the greediness of our policy. Typically, during the optimization of value based method, is annealed to 0 and the policy becomes more determin- istic. On (b) we show the probability of diverging (averaged over 100 samples of b) measured by computing the spectral radius of our iteration matrix. As predicted, for a fixed when decreases, we might go through a phase transition where the iteration, stable at beginning, becomes unstable.
Conclusion
In this work, we have analyzed the spectral distribution of the Temporal Difference operator when using random features and modeling the Markov transition matrix as the one of a random graph. This characterization allowed us to make predictive theories for the optimization error and stability of TD. Notably we are able to predict how fast we converge and whether the solution found is accurate as a function of the ratio between the number of parameters and the number of state-action pairs. In particular, we highlighted and theoretically explained several phenomena specific to reinforcement learning such as the peaking behavior of the estimation error of TD or how changing the policy might cause divergence when using fixed step size, even in the on-policy setting.
Important directions for future work include: (i) improving the model for pa through careful anal- ysis of more expressive random graphs, (ii) derive non-asymptotic results using the fluctuations of the extreme eigenvalues the MP law (Baik al., 2005) (iii) extend our results neural networks in the Neural Tangent Kernel regime and finally (iv) study the behavior of policy optimization algo- rithms.
where the bottom right state with reward of leads back to the initial state the top left.

---

Acknowledgments
We thank Alexandre Piché for useful comments on an earlier version of this paper.
References
Hirotugu Akaike. A new look the statistical model identification. IEEE transactions on automatic control, 1966)716-723, 1974.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 33(5):1643-1697, 2005.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Mikhail Belkin, Daniel Hsu, and Xu. Two models of double descent for weak features. SIAM
Journal on Mathematics of Data Science, 2(4):1167-118) 2020.
Richard Bellman. The theory of dynamic programming. Bulletin of the American Mathematical Society, 5036)1503-515, 1954.
Charles Bordenave, Pietro Caputo, and Djalil Chafai. Circular law theorem for random markov matrices. Probability Theory and Related Fields, 152(3):751-779, 2012.
Léon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, vol- ume 20. Curran Associates, Inc., 2007. URL https: http:::://ppooceeddeeeeoo neurips. cc/
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymp- totic theory of independence. Oxford university press, 2013.
Andrei Z Broder and Anna R Karlin. Bounds on the cover time. Journal of Theoretical Probability, 2(1):101-120, 1989.
Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis, Princeton Univ. Press, Princeton, N. J..:pp 195-199., 1970.
Romain Couillet and Zhenyu Liao. Random Matrix Methods for Machine Learning: When Theory meets Applications. 2021.
Yann Le Cun, Ido Kanter, and Sara Solla. Eigenvalues of covariance matrices: Application to neural-network learning, Phys. Rev. Lett., 66:2396-2399, May 1991. doi: 10. 10.1103/PhysRevLet 66.2396. bttps:::
aps www.s/o.ss.aa.ooooooo.oo.ooo...s http:///...../////eeeeeeeeeeeeee
2399996
Michal Derezinski, Feynman T Liang and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. Advances in neural information processing systems, 33:5152-5164, 2020.
Jacob Devlin, Ming-Wos Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: Arxiv-1110.04805,, 2018.
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M Roy. In search of robust measures of generaliza- tion. Advances in Neural Information Processing Systems, 33:11723-1173, 2020.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural Networks and the Bias/Variance Dilemma. Neural Computation, 4(1):1-58, 1992. ISSN 0869-7667. doi: 10.1 10.1162/neco. 1992.4.1.1. htttp:://c...rgg//// http:///oo.og///////// 626 neco. 992.4.1.1
10

---

Edgar N Gilbert. Random graphs. The Annals of Mathematical Statistics, 30(4):1141-1144, 1959.
Gene H Golub. Some modified matrix eigenvalue problems. SIAM review, 15(2):318-3335 1973.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint vrXiv:1903.08566 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- cralization in neural networks. Advances in neural information processing systems, 31, 2018.
Alex Krizhevsky, Πly Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Wein- berger (eds.), Advances Neural Information Processing Systems, volume 25. Curran Asso- ciates, Inc., 2012. URL
Iija Kuzhorskij, Csaba Szepesvári, Omar Rivasplata, Amal Rannen-Trike Trinen and Razvan Pascanu. On the role optimization double descent: A least squares study. Advances in Neural Information Processing Systems, 34, 2021.
Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1(4):541- 551, 1989. doi: 10. 10.116///cco.1989 19.4.1.4.41..
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint 17 171.00065,, 2017.
Marlos C. Machado, Marc G. Bellemare, and Michael Bowling. A Laplacian framework for op- tion discovery in reinforcement learning. In Doina Precup and Yee Whye Teh (eds.), Pro- ceedings of the 34th International Conference on Machine Learning, volume 70 of Proceed- ings of Machine Learning Research, pp. 2295-2304. PMLR, 06-11 Aug 2017. URL https:
//proceedings.. ml. www..p.esssvvve. http:///mmaaaaoooo at.iddoolaa........... html
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL met/Eee Beet/Eozun?id=3kBB2.
Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learn- ing representation and control in markov decision processes. J. Mach. Learn. Res., 8:2169-2231, 2007. URL (ttt:ttp:///d] acm. wwtp cfm.ccmmmmc..... 11tp:/emmm..mmmm11111111111
Vladimir A Marčenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik, 144):457, 1967.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Yurii Nesterov.
Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In International Conference on Machine Learning, pp. 2798-2806. PMLR, 2017.
Tomaso Poggio, Gil Kur, and Andrzej Banburski. Double descent in the condition number. arXiv preprint 19/1 2019.

---

Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley Sons, 2014.
Bruno Scherrer. Should one compute the temporal difference fix point or minimize the bellman residual? the unified oblique projection view. arXiv preprint arXiv:1011.4362. 2010.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, (12 211, 1999.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
Terence Tao and Van Vu. Random matrices: The universality phenomenon for wigner ensembles. arXiv preprint arXiv: Arxiv-1202.00m 2012.
Terence Tao, Van Vu, and Manjunath Krishnapur. Random matrices: Universality of esds and the circular law. The Annals of Probability, 38(5):2023-25) 2063,2206,2220 2010.
Linh Tran, Van Vu, and Ke Wang. Sparse random graphs: Eigenvalues and eigenvectors. arXiv preprint arxiv: Arxiv-1011.6644 2010.
John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffferenc learning with function approximation. In Advances in neural information processing systems, pp. 1075-1081, 1997.
Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Mo- dayil. Deep reinforcement learning and the deadly triad. arXiv preprint / 2018.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a toy: Random matrix models predict how real-world neural representations generalize. arXiv preprint arXiv: Arxiv-2003.06176 2022.
Eugene Wigner. Characteristic vectors of bordered matrices with infinite dimensions. Annals of Mathematics, 62(3):548-566 1955. ISSN 0003486X. URL. http: www. jstor.strrooo.. org/ stable/1970079
John Wishart. The generalised product moment distribution in samples from normal multivariate population. Biometrika, pp. 32-52, 1928.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with efficient approximations. arXiv preprint 1810:1810.045888 2018.
Chenjun Xiao, Bo Dai, Jincheng Mei, Oscar A Ramirez, Ramki Gummadi, Chris Harris, and Dale Schuurmans. Understanding and leveraging overparameterizztion in recursive value estimation. In International Conference on Learning Representations, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115. 2021.
Yufei Zhao. Spectral distributions of random graphs. 2012.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
12

---

(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is a theoretical model for TD(0) in the linear setting. As such we do not think there are any applications with societal impact to be foreseen.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Some finer details can be found in the proofs in appendices.
(b) Did you include complete proofs of all theoretical results? [Yes] Statements such as Lemmas or propositions have a full proof in appendix. Informal statements and approximations have derivation in appendix where make clear what the approxi- mation/asssumption is.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] Colab notebooks are supplied to reproduce the figures.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Used public Colab notebook compute.
4. If you using existing assets (c.g., code, data, models) curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'l re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zAiKmpq_coK", "reviewer": "Reviewer_3zWt", "summary": "This paper investigate the role of optimization in value approximation with linear value function approximators leveraging tools from random matrix theory and random graph theory. The authors characterize the spectrum of the TD operator, and show that the resulting learning process demonstrates clear signatures of the double descent phase-transition near the critically parameterized cut-off.", "questions": "I think this paper is quite well-written as it is. I will update here if questions arise.", "limitations": "One of the issues that complicate the analysis of TD is the interplay between the sampling distribution, the transition matrix, and the function approximator itself. I think this work did a fantastic job.\n\nIt would obviously be beneficial to extend the analysis here to neural networks. However, I am not sure if the NTK regime is the best place as the authors indicated in the discussion because over-parameterized ReLU is just one way the network could be parameterized and it is known to contain bias towards low-complexity functions. Recent work [^2] [^3] have shown empirically how such issues could be addressed by modifying the parameterization itself.\n\nTherefore instead of working with MLPs as they are, over-parameterized or not, the analysis offered here might just as well be abstract enough that it offers more insight than an analysis focused on particular types of overparameterized neural networks.\n\n[^2]: Achiam, J., Knight, E. and Abbeel, P. (2019) ‘Towards Characterizing Divergence in Deep Q-Learning’, arXiv [cs.LG]. Available at: http://arxiv.org/abs/1903.08894.\n\n[^3]: Yang, G., Ajay, A. and Agrawal, P. (2021) ‘Overcoming The Spectral Bias of Neural Value Approximation’, in International Conference on Learning Representations.", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, and all of the proofs are correct as far as I understand. The result is relevant and is a necessary extension of the analysis on overparameterization in the supervised learning regime [^1]. \n\nA notable technical contribution is the introduction of a class of models for which the spectrum of TD can be computed. The experimental result is clearly presented and offers useful insight. The figures on the evolution of the maximum and minimum singular values, as well as the overall distribution in response to parameterization ratio and different types of graph clearly convey the main point of the paper.\n\n[^1]: Kuzborskij and Szepesvári (no date) ‘On the role of optimization in double descent: A least squares study’, Advances in engineering education [Preprint].", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uKBFxuaERUy", "reviewer": "Reviewer_MGtX", "summary": "This paper studies the largely unexplored area of the overparameterization in RL and TD learning. ", "questions": "Overall, the paper is well written and includes interesting results. Some comments to improve the paper are as follows. Please clarify them in the paper.  \n1) This paper addresses off-policy TD learning. It is not clear until eq (2). It would be better to put more emphasis on that the paper considers off-policy TD.\n2) Eq (2) would be be TD-learning because it does not include any samples. It is a determininstic algorithm . \n3) Needs some changes in expressions: e.g. \"0 mean\" can be replaced with \"zero mean.\" What is the meaning of spectrum of TD?\n4) What is the meaning of overparameterization in TD? Please clarify it in the paper. \n5) Overall, the paper is written based on languages used in deep learning fields. It would be better to consider readability for people in RL areas. \n6) More discussions are needed: why do we study spectrum of TD? ", "limitations": "The work includes interesting results, but the writing should be more syetematic for general readers. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThis paper studies the largely unexplored area of the overparameterization in RL and TD learning. \nIt is a unique contribution, and the paper is well written. \n\nWeaknesses: \nThe work includes interesting results, but the writing should be more syetematic for general readers. \nThe presentation is rather sloppy. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cnG-PBoqatg", "reviewer": "Reviewer_EBEx", "summary": "This paper uses ideas from Random matrix theory to study the spectrum of the TD update operator under strong assumptions on the MDP graph. In doing so, the authors focus on the over-parameterized case where the number of parameters in the linear function approximation exceeds the total number of distinct (s, a) pairs. \n\n", "questions": "* Proposition 4.1 assumes that the spectrum of the relevant matrix is real and positive but this can be easily violated which is the main challenge in going from least squares to the TD version. \n\n* In Proposition 4.2, again how can you justify assuming that the transition matrix is rank one just by taking the limit? This seems to be assuming away the main complexity of MDPs and lack of any structure in the graphs.\n\n* There is a blurb about Wigner type matrices in Page 3, but I don't notice anything related in the rest of the paper. \n\n  \n", "limitations": "Adequate", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* Paper is well motivated and proposes making use of results from random matrix theory to analyze the spectrum of the TD operator.\n\nWeaknesses:\n\n* Section 3.2 appears weak, and unfortunately the assumptions here are very strong and a critical part of the paper. The justification for modeling the $P^\\pi$ as a modification of a random graph is very unclear to me (Section 3.2) and this seems to be a key ingredient of the entire analysis.\n\n* Motivation for several of the assumptions is clearly tractability but unclear takeaways from the analysis. This includes assumptions like random features, rank one transition matrix. The former seems okay but the latter is too strong and the justifications for this are very hand-wavy and unclear.\n\n* Analysis of value estimation for TD learning under linear approximation has also been considered by Xiao et. al at ICLR 2022: https://openreview.net/forum?id=shbAgEsk3qM which the authors should discuss.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BEHdllGkkX3", "reviewer": "Reviewer_72Nh", "summary": "This paper introduces a random graph model allowing to study the stability and optimization properties of the TD algorithm in RL. More specifically, this paper applies tools from random matrix theory to study the spectral distribution of the (projected) TD(0) operator and uses this understanding to study the behavior of the approximation and estimation error in different regimes of over- and under-parametrization as the size of the system diverges.", "questions": "My main question concerns the weakness highlighted above: I think the authors should stress in which sense the model they observe is a relevant one to the RL community, as else it might be perceived as being reverse-engineered.\n\nIf this is not possible this point should be discussed much more clearly in the conclusion as a limitation.", "limitations": "Depending on the answer to the previous question, the authors might have to address much more precisely the applicative limitations of the model being investigated.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written, clearly introduces the reader to the fundamental concepts of random matrix theory that are needed to understand the results, and presents such results in a clear way. The paper addresses an important theoretical issue: understanding the role of overparametrization in RL, and does so, although under some relatively strong assumptions, discussing a nontrivial case and presenting some theoretical understanding of a previously unexplained phenomenon.. From a first reading of the supplementary material, the technical part of the paper seems sound. The numerics solidly corroborate the findings of the paper and hint to a new direction of research.\n\nThe main weakness of the paper is the significance: the model of random graph being investigated seems a bit artificial: it seems unclear from a first reading how many relevant problems in RL can be captured in this setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept