On Double Descent in Reinforcement Learning with LSTD and Random Features
Authors: David Brellmann
Eloïse Berthier
David Filliat
Goran Frehse
Venue: ICLR 2024 poster (2024)
Keywords: Regularized Least-Square Temporal Difference
double descent
over-parameterization
random features
Primary area: reinforcement learning
TL;DR: We show a performance drop of TD algorithms when the ratio of network parameters to visited states is around one, leading to a double descent phenomenon, and that this can be mitigated with increased $l_2$-regularization or by visiting all states.

Abstract: 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.

Published as a conference paper at ICLR 2024
ON DOUBLE DESCENT IN REINFORCEMENT LEARNING WITH LSTD AND RANDOM FEATURES
David Brellmann, Eloise Berthier, David Filliat & Goran Frehse U2IS, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, FRANCE (firss name. last name @ensta -paris.......
ABSTRACT
Temporal Difference (TD) algorithms are widely used in Deep Reinforcement Learning (RL). Their performance heavily influenced by the size of the neu- ral network. While in supervised learning, the regime of rreetearamtttizattoon and its benefits are well understood, the situation in RL much less clear. this paper, we present theoretical analysis of the influence of network size and (2-reullarization on performance. We identify the ratio between the number parameters and the number of visited states as crucial factor and define over- parameterization as the regime when is larger than one. Furthermore, we ob- serve double descent phenomenon, i.e., sudden drop in performance around the parameter/state ratio of one. Leveraging random features and the lazy train- ing regime, study the regularized Least-Squared Temporal Difference (LSTD) algorithm in an asymptotic regime, as both the number of parameters and states go infinity, maintaining a constant ratio. We derive deterministic limits of both the empirical and the true Mean-Squared Bellman Error (MSBE) that feature cor- rection terms responsible for the double descent. Correction terms vanish when the Iz-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.
INTRODUCTION
In recent years, neural networks have seen increased use in Reinforcement Learning (RL) (Mnih al., 2015; Schulman et al., 2017; Haarnoja al., 2018). While they can outperform traditional RL algorithmss on challenging tasks, their theoretical understanding remains limited. Even for super- vised learning. which can be considered a special case of RL with discount factor equal to zero, deep neural networks are still far from being fully understood despite significant research efforts (Arora Fanden-Eijnden, 2018; Lee et al., 2019; Bietti & Mairal,
et al., 2019; Mei et al., 2018; Rotskoff 2019: Cao et al., 2019). The difficulty is further exacerbated in RL by myriad of new challenges that limit the scope of these works, such as the absence of true targets or the non-i.i.d nature of the collected samples (Kumar al., 2020; Luo al., 2020; Lyle et al., 2021; Dong et al., 2020). Temporal-Differene (TD) methods are widely used RI. algorithms that frequently use neural net- works, are simple, and efficient in practice. We use the regularized Least-squares Temporal Dif- ference (LSTD) algorithm (Bradtke & Barto, 1996), which is easier to analyze since it doesn't tt use gradient descent, and because it converges the same solution other TD algorithms (Bradtke & Barto, 1996; Boyan, 1999; Berthier et al., 2022).
Theoretical studies of TD algorithms often explore asymptotic regimes where the number of sam- ples n + oc while the number of model parameters N remains constant (Tsitsiklis & Van Roy, 1996; Sutton, 1988). When TD learning algorithms are applied neural networks, it commonly assumed that the number of parameters N - oc with either a fixed or infinite number of samples without providing details on the relative magnitudes Lu, 2022; Berthier et al., 2022; Xiao et al., 2021). Inspired by advancements in supervised learn- ing (Louart et al., 2018; Liao et al., 2020), we apply Random Matrix tools and propose a novel double asymptotic regime where the number of parameters N and the number of distinct visited states m go to infinity, maintaining a constant ratio, called model complexity. We use a linear model and nonlinear random features (RF) (Rahimi & Recht, 2007) approximate overparameterized
these parameters (Cai et al., 2019; Agazzi &

---

Published as a conference paper at ICLR 2024
10a
MSBE
10
10
0.5
1.5
2
N/m
(a) Taxi-v3
(b) MSBE as a function of N/m
Figure 1: As the model complexity N/m (for N parameters, m7 distinet visited states) increases, the MSBE first shows a U-shaped curve, peaking around the interpolation threshold (N = m.. Double descent refers to the phenomenon for N/m > 1 where the MSBE drops once again. Continuous lines (red) indicate the theoretical values from Theorem 5.3, the crosses (blue) are numerical results averaged over 30 instances with their standard deviations after the learning with regularized LSTD on Taxi-v3 for 0.95, À 10-9 5000, = 310.
single-hidden-laye network the lazy training regime (Chizat et al., 2019). The results of our theoretical and empirical analyses are outlined below.
Contributions. We make the following contributions, taking step towards better theoretical understanding of the influence of model complexity N/m and Iz-regularization on the performance of Temporal Difference algorithms:
1. We propose novel double asymptotic regime, where the number of parameters N and distinct visited states m go infinity while maintaining a constant ratio. This leads to precise assessment of the performance in both wver-parameterized (N/m > 1) and under-parramtterized regimes (N/m < 1). This is a nontrivial extension existing work in supervised learning since several properties essential to proofs, such the positive def- initeness key matrices, are voided by discount factor in RL.
2. In the phase transition around N/m Error (MSBE), as illustrated in figure 1, i.e., a double descent phenomenon similar to what has been reported in supervised learning (Mei & Montanari, 2022; Liao et al., 2020).
observe peak in the Mean-Squared Bellman
3. We identify the resolvent of non-symmetric positive-definic matrix that emerges as crucial factor in the performance analysis of TD learning algorithms terms of the MSBE and we provide its deterministic limit form in the double asymptotic regime.
4. We derive analytical equations for both the asymptotic empirical MSBE on the collected transitions and the asymptotic true MSBE. The deterministic forms expose correction terms that we experimentally associate with the double descent phenomenon. We show that the correction terms vanish the /z-regularization increased or N/m goes infinity. We also show that the influence of the Ig-regularizzttoo parameter decreases as N/m increases.
5. Our theory closely matches empirical results on range of both toy and small real-world Markov Reward Processes where m and N are fixed, but for which the asymptotic regime still gives accurate predictions. Notably, we observe a peak the true MSBE around N/m = that is not observed in the empirical MSBE. Correction terms, and therefore the difference between true and empirical MSBE, empirically vanish when the number of unvisited states goes to zero.
2 RELATED WORK
We review three related approaches to study neural networks in supervised learning or RL. Further technical results from the literature cited where relevant throughout the paper.
Neural Tangent Kernel (NTK) regime. In the NTK regime, one considers that infinitely wide neural networks, with appropriate scaling and initial conditions, behave like the linearization of the
2

---

Published as a conference paper at ICLR 2024
neural network around its initialization (Jacot et al., 2018). However, as highlighted by Chizat et al. (2019), this behavior is not specific to neural networks and is not so much due to over- parameterization than to implicit choice of scaling. In such a scenario, neural networks can be modeled as a random feature model (Rahimi & Recht, 2007); we adopt this technique in order to abstract from the learning dynamics. The NTK regime was also considered in RI., in both finite and infinite state space, to prove the convergence of infinite-width neural TD learning algorithms towards the global optimum of the MSBE (Cai al., 2019; Agazzi & Lu, 2022; Liu al., 2019).
Mean-Field regime. Under appropriate initial conditions and scaling, the mean-field analysis models the neural network and its induced feature representation with an empirical distribution, which, at the infinite-width limit, corresponds to a population distribution. The evolution of such a population distribution is characterized by partial differential equation (PDE) known as the conti- nuity equation and captures Stochastic Gradient Descent (SGD) dynamics Wasserstein gradient flow of the objective function (Chizat & Bach, 2018; Rotskoff & Vanden- Vanden-Eijnden, 2018; Mei al., 2018). Although more challenging than the NTK regime, the mean-field regime is more realis- tic since the weights are not restricted to staying in their initial regions (Chizat et al., 2019). The mean-field regime was studied in RL to prove the convergence of fefinite-witth neural TD learning algorithms towards the global optimum of the MSBE (Zhang et al., 2021; Agazzi & Lu, 2022).
Double Asymptotic regime. In the above regimes, the number of data points is negligible com- pared to the number parameters since N grows to infinity. However, this is rarely the case in practice, which is why the double descent phenomenon can not be explained with the previous regimes (Zhang et al., 2020; Belkin et al., 2018). The double descent phenomenon is characterized by peak near the interpolation threshold (N n). For this reason, many studies in supervised learning consider a double asymptotic regime (Mei & Montanari, 2022; Louart et al., 2018; Liao al., 2020; Belkin al., 2020), where both n, NN go to infinity while maintaining their ratio con- stant. In the above work, techniques from Random Matrix theory are used to derive precise de- scription of the phase transition between under-(N n) and over-(N the double descent phenomenon. Our work extends this approach from supervised learning to RL. Since several key properties from supervised learning are voided by the discount factor, the analysis is substantially more involved in the case of RL. Thomas (2022) investigated off-policy linear TD methods the limit of large number of states and parameters on a transition matrix of rank 1, and observed a peaking behavior in the MSBE. We consider more general setting the on on-policy setting and a different ratio in the double asymptotic regime without making assumptions about the rank of the transition matrix.
12) parameterization and
3 PRELIMINARIES
Notations. We define [n] = (1.2.....nn) For a real matrix A, [A]s denotes its (i, (i. entry. For A with real eigenvalues, we denote with Umin ( (A) the smallest and Vmmxx (A) the largest eigenvalue. The symmetric part of A is (AA) = A+4" The operator norm of a A is written ||]] The norm induced by A on a vector v is || = or Au and ||o/|| depicts the Euclidean norm of v. 1)) denotes the standard Gaussian distribution.
2
Markoy Reward Processes. We consider Markov Reward Process (MRP) (S, (,r,,),,, where S IR is the state space: P S S - [0. 1] is the transition kerell (stochastic kernel) and s") denotes the probability of transitioning to state s' from state 8; r S x S + IR is the reward function; and 7 E [0, 1) the discount factor. For notational convenience, the state space described by the state matrix
dx where each column of S, written S, represents a state in S. The transition probability matrix associated with the stochastic kernel P is P R (|(] The goal is to learn the value function V S + R. which maps each state s to the expected discounted sum of rewards when starting from and following the dynamics of the MRP defined by P as = s]. It is well-known that the value function is the
V(s) := Ep - k 81+1).
unique fixed toint of Bellman's equation
V = r -
(I)
where V E S is a vector whose i-th element is the value function of the i-th state S; and F e R|S| the vector containing the expected rewards, for which r; [r(r for all i E [[]]].
3

---

Published as a conference paper at ICLR 2024
Linear Function Approximation. In practice, equation cannot be solved since P is unknown and {S] is too large. One common solution is to use Linear Function Approximation (LFA). Using a parameter vector
IN and a feature matrix Es E R RNx[S whose columns are the feature vectors for every state, V is approximated by V E In Deep RL, the neural network learns both the feature vectors and the parameter vector. For given feature matrix, the learning process based on equation amounts finding a parameter vector 0 that minimizes the Mean-Squared Bellman error (MSBE)
MS || + + 2
where π E IR is the stationary distribution induced by the MRP and D E ||SsX is its diagonal matrix. Since F + PP 0 may not lie in the span of the bases Es, there may not be a parameter vector 0 that brings the MSBE to zero.
Linear Temporal-Differenee Methods. Linear Cemporal-Differenee (TD) methods are LFA methods that try to minimize the MSBE in equation 2 by replacing the second occurrence of 0 in equation 2 with an auxiliary vector u, minimizing on u and then finding 0 close to u (Dann et al., 2014):
u arg min WERN
| 1 |
DJu DT
(projection step),
(3)
0" arg min ES - BERN
(fixed-point step).
(4)
The projection step (equation 3) implies that TD methods actually minimize the Mean-Square Pro- jected Bellman eπrоr (MSPBE) rather than the MSBE (Dann et al., 2014). In our asymptotic regime, as the number of features N - oo, the class of representable value functions becomes richer, and the MSBPE converges to the MSBE (Cai et al., 2019; Agazzi & Lu, 2022).
4 SYSTEM MODEL
We now describe the key elements on which we base our asymptotic analysis of the MSBE in TD learning: Random features, the regularized LSTD algorithm, and the double asymptotic regime.
4.1 REGULARIZED LSTD WITH RANDOM FEATURES
Random Features. We consider value function approximation using the Random Feature (RF) mapping RF S + N defined for all s E S as
RF(s) (Ws))
(5)
where a: : + is -i-Licchhitz continuous and applied component-wise; W = ( E Nxd is a random weight matrix fixed throughout training for which W E Nxd has independent and identically distributed (o00 1) entries, and oo IR. - R is K,-Lipschitz continuous and applied component-wise. From the perspective neural networks, the N random features can be seen as N outputs from mungle-hidden-laeee
neural network. In asymptotic regime, this simplification becomes even more accurate as the number of features N of the single layer grows towards infinity and we enter into the lazy training regime, where weights barely deviate from their random initial values (Chizat et al., 2019). In the literature on Deep Learning and double descent, large-width neural networks are often modeled using asymptotic random features (Louart al., 2018; Liao et al., 2020; Mei & Montanari, 2022), including in RL (Cai et al., 2019; Agazzi & Lu, 2022; Liu et al., 2019). In the following, we denote the random feature matrix of any state matrix A E Rdxp as ΣA where RF is applied column-wise, i.c., ΣA (WA).
Sample Matrices and Empirical MSBE. We assume that the transition probability matrix P is unknown during the training phase. Instead, have dataset of transitions consisting of states, rewards, and next-states drawn from the MRP, i.c., Durain {( ri, s() 1"- where s ~ P(s..) -). We consider the on-policy setting, where Dumin is derived from a sample path of the MRP or its stationary distribution л. We collect the states and rewards in the sample matrices
X, [81,..., sn) Rd
(ri,..., rn]"" E ER"
X" i ..1 E Rdxx.
(6)
4

---

Published as a conference paper at ICLR 2024
Let S [ S be the set of distinct states in Duans which call visited states, and let [ Let $ E Rdxm be the state matrix of S, i.e., each column S, of S describes a state S. We denote by Eg E RN*m Σx, E I Nx", and Σx; E RN** the random feature matrices of Š, x,, and X respectively. For the proof of our results, it will be mathematically advantageous to express Σx, and Σx; as the product of E with auxiliary matrices Ün E Rm*x and V, m2"x" as follows:
Σx. VnIgU, and Σx: V
(7)
Each column i of vnū, is one-hot vector, where the j-th element equals 1 if the i-th state 8, of Xn is $3. and similarly for vnV, and X Since P is unknown, we aim to find @ that minimizes the empirical version of the MSBE (equation obtained with transitions collected in Drain
MSBE(O) J. || + 0 Σx, 011?
(8)
which uses the Euclidean norm since the distribution reflected by the samples. Assumming glob- ally stable MRP, a fixed number of features, and all states being visited, MSBF(() converges to co. This follows from
MS with probability 1, as the number of collected transitions the law of large numbers (Stachurski, 2009). In our analysis, we will also consider the case where oo without visiting all states, i.c., m [S], such that there can be a significant difference between MSBE(O) and MSBE(O).
Regularized Least-Square Temporal-Differene Methods. Regularized Least-Square Temporal-Differenne (LSTD) Methods (Bradtke & Barto, 1996) are linear TD methods that solve empirical regularized version of equation and with transitions collected in Dusin-
arg min ||r + + 0 Σx, ull + Am,nl/uu/??
MERN
0 arg min | u
Xx 012
(10)
DERN
where Am, >> is the effective 12- Ie-reuularization parameter, introduced to mitigate overfitting (Hoff- man et al., 2011; Chen et al., 2013). It is well known that for Am,n 0 and with the number of samples n + oc, the fixed point the approximation equation 9 and 10 equals the fixed point of
equation 3 and 4 with probability one. Solving the fixed-point of the linear system approximation given by equation 9 and 10 gives
i Σx_ Σx. -xxx] + Am.n Σx.r.
(11)
Under appropriate learning rates, linear TD methods based on gradient- converge towards the same fixed-point Ô (Robbins & Monro, 1951; Dann et al., 2014; Sutton & Barto, 2018). Besides reducing overfitting, an appropriate Am, ensures that Σx, EXx, -x;;]] +mm,n IN is invertible.
4.2 DOUBLE ASYMPTOTIC REGIME AND RESOLVENT IN LSTD
We study the regularized LSSD in the following double asymptotic regime: Assumption (Double Asymptotic Regime). As N, m, d + oc, we have:
1. < lim min {
d m lim max {
m
m S
m
m
[ST
m
oc.
2. There exists Ks, K, such that lim sj ||| < Ks and r(--)) is bounded by Ky-
In order to use Random Matrix tools, we rewrite equation 11 as (see proof in Lemma L.9)
Σx, >xx;] Σx.
Ama.
(12)
mn
mn
Instead of the effective l beregularization parameter Am, we will use its scaled version À Amm in the remainder this paper. We observe that Ô ma Σx, Qm (A)r depends on the resolvent
Q (A)
Σx.
TT Σx. + AIn -Ex; 1"
= m [1(ú, - VV.) T + XI
mm
(13)
5

---

Published as a conference paper at ICLR 2024
when 2 (Ü, -V. + VI, is invertible, which in general may not be the case. We can guarantee invertibility if the empirical transition model matrix Am RR
Am. ÜÜ, ~V,)"
(14)
has a positive-definite symmetric part (see Appendix H for a formal proof), For the remainder of the paper, we therefore make the following assumption on Am:
Assumption (Bounded Eigenspectrum). There exist < Emiu < Emax such that for every m, all
the eigenvalues of H(A., (Am) are in [Smin: Smax]-
Note that the above assumption is satisfied for regularized pathwise LSTD (Lazaric et al., 2012), and also for sufficiently large n (see Appendix H).
5 ASYMPTOTIC ANALYSIS OF REGULARIZED LSTD
In this section, we present our main theoretical results, which characterize the true and empirical MSBE under Assumptions and 2.
5.1 AN EQUIVALENT DETERMINISTIC RESOLVENT
The resolvent Qm (A) (in equation 13) plays significant role in the performance of regularized LSTD since 0 v m. Eg Qm To assess the asymptotic MSBF(() and true MSBE((0). we first find deterministic equivalent for the resolvent Qm. (A). A natural deterministic equivalent would be [QQ (A)]. ) but it involves integration without having a closed form expression (due to the matrix inverse) and is inconvenient for practical computation. Leveraging Random Matrix tools, the following Theorem 5.1 proposes an asymptotic form that is i. close to Ew [Qm (A)] under Assumptions and 2, and it. numerically more accessible (for the proof, see Appendix E).
Theorem 5,1 (Asymptotic Deterministic Resolvent). Under Assumptions 1 (double asymptotic regime) and (bounded spectrumi) let and let the deterministic resolvent m (A) E gaxn be
Qm N 1 1+8 (Ü, VVn) V LSú + AI
(15)
where the deterministic Gram feature matrix Dg E Rm is
+ Ew- () (w $)
(16)
and the correction factor is the unique, positive, solution to
8 m Tr (U, (in m + (U, -V) NZn [.).
N 1
(17)
Then limm-roe [Ew (Q Qm (A)ll = 0. The correction 8 diminishes as N or X grows (see Lemma J.3 and J.4).
1 Remark 1. Since ō - O when N/m + oc, the correction factor T48 arises from our asymp- totic regime, which keeps the ratio N/m asymptotically constant (see Lemma J.1 for existence and uniqueness). Similar correction factors arise in related Random Matrix literature, which, however, mostly deals with positive semi semi-definite matrices (Couillet & Debbah, 2011; Liu et al., 2019; Liao et al., 2020). Our problem exceeds this frame, so we prove the result, including existence and uniqueness, with somewhat more involved analysis based on the eigenspectrum of the products of matrices with nositive-defintte symmetric part and skew- wem-symmtttic matrices (see Appendix J).
Remark 2. For the case of supervised learning, comparable proposition is presented by Louart et al. (2018, Theorem 1). It constitutes a special case of Theorem 5.1 with y = 0. which corresponds to the case where we learn the reward function.
necessarily real, which renders many tools from the related Random Matrix literature not applicable. e.g., Stieltjes transforms would provide information on the eigenspectrun density of matrices based on the trace of their resolvents.
Remark 3. Note that the eigenvalues of (m)

---

Published as a conference paper at ICLR 2024
5.2 ASYMPTOTIC EMPIRICAL -AAN-SQURRED BELLMAN ERROR
TD methods learn by minimizing the empirical MSBE (equation 8) and, under appropriate learning rates, converge towards the empirical MSBE of LSTD, mentioned in Section 4. It is straightfor- ward to show that this leads to an optimal MSBE( = X² ||Q (A)rll (see Appendix F). Using concentration arguments for Gaussian distributions and Lipschitz applications, well as Theo- rem 5.1, we derive the following deterministic form (see proof in Appendix F).
Theorem 5.2 (Asymptotic Empirical MSBE). Under the conditions of Theorem 5.1, the deterministic asymptotic empirical MSBE MSBE(() = X² n Qm)/||11 + Å, with second or- der correction factor
X² (M(
v. Q.Qm())) |IQm (1)r1 where
(18)
n 1- (M)
V
N 1
n 2 gÜn.
and L N 1+8 (Un Vvn) TT SUn VV))
(19)
148
As N, m, d + oo with asymptotic constant ratio N/m, MSBE(() MSBE 0
0.8 0.
Remark 4. As N/m + oo, we find MSBE 0 0.
Remark 5. In supervised learning, comparable proposition presented by Louart et al. (2018,
Theorem 3). It is special case of Theorem 5.2 with O, where we learn the reward function r.
5.3 ASYMPTOTIC MEAN-SQUARED BELLMAN ERROR
While the empirical MSBE only takes states from the data set into account, the true MSBE (equa- tion 2) involves all states in S. To extend the convergence results from the previous section this case, we require some further notations. Using decomposition similar to equation 7, we express Ex, and Ex; as a product of the random feature matrix of the entire state space Es E R (S) with Un E Rlsixn and V, E IR S|xn instead of Eg U.., Vn. We obtain a decomposition of the transition model matrix A, (U,, 7 VV,)". A, LSTD as model-based RI. Tsitsiklis & Van Roy (1996) and Nedić & Bertsekas (2003) showed that [An] + DT [[s] PP] as + oc. The bound on the difference ||A,, DT [I[s] >P] || as function of was studied by Tagorti & Scherrer (2015), We make the following assumption on this norm:
used by Boyan (1999) to interpret
Assumption 3. As m + co, we have ||A, - D -111 O
Using an approach similar to that of Theorem 5.2, plus a detailed analysis of operator norms, we obtain the following deterministic form of the asymptotic MSBE (proof in Appendix G):
Theorem 5.3 (Asymptotic MSBE). Under Assumptions 2, and 3, the deterministic asymptotic INN ti 1+6 P V m 1+5 $ Pm
2
MSBE is M)
r+
+
D.
with second-order correction factor
N Tr(Ap (A e 20 -V,
A
Q1Q (1)r where
(20)
1- 1- Tr (A)
V s m 148
s, Ap [1ss] - P (is) - -P), and θ5 = S Qm (A).
(21)
As N, m, d + oo with asymptotic constant ratio N/m, MSBE MSBE
G.
Remark 6. Like the empirical M) in Theorem 5.2, the true MSBE θ) is also influenced by the correction terms and A. Note that in asymptotic regimes where N/m + oo or X + 20, the correction terms vanish. When N/m + oc, MSBE(() is independent of X as shown in details in Appendix C.
Remark 7. When all states have been visited, the common subexpressions in the second-order correction factors Å and A dominate so that A, A become similar (for a proof, see Lemma G.8).
7

---

Published as a conference paper at ICLR 2024
10a
À =
10-3
10a
À =
10
A = 10
10
10*
10a
10
109
10
1.5
0.5
0.5
1.5
N/m
N/m
N/m
Figure 2: The correction factor 8 is decreasing function of the number of parameters N. For a small (z-regularization parameter X, we observe a sharp decrease near the interpolation threshold (N for m distinct visited states). As increases, the function becomes smoother and smaller (note the different scales of the y-axis). is computed with equation 17 on Taxi-v3 with 7 0.95, 310,n n 5000.
A 10
10
À
10
10a
10a
10a
MSBE
10'
10
10
10
10
10
0.5
1
1.5
0.5
1.5
2
0.5
1.5
2
N/m
N/m
N/m
Figure 3: The double descent phenomenon occurs in the true MSBE (red) of regularized LSTD, peaking around the interpolation threshold (N m for N parameters, distinct visited states) when the empirical MSBE (blue) vanishes. It diminishes as the Iz-regularization pa- rameter increases. Continuous lines indicate the theoretical values from Theorem 5.2 and The- orem 5.3. the crosses are numerical results averaged over 30 instances after the learning with regu- larized LSTD in Taxi-v3 with 0.95, m = 310, n 5000.
NUMERICAL EXPERIMENTS
In this section, we provide an empirical evaluation, including a discussion of the behavior of the correction factor 8 from Theorem 5.1, and its impact the empirical and true MSBE from Theo- rem 5.2 and Theorem 5.3. Additional experiments can be found in Appendix A.
Experimental Setup. We use the recursive regularized LSTD implementation Dann et al. (2014) on three MRPs: synthetic ergodic MRP (500 states); gridworld MRP (400 states) ob- tained from a random policy a 20 x 20 gridworld (Ahmed, 2018); and a Taxi-v3 MRP (356 states) obtained from learned policy in OpenAl gym Taxi-v3 (Towers et al., 2023) (Figure la). In all cases, states are described by d-Gaussian vectors where d = 50. For the random features, W is drawn from Gaussian distribution and a--) max(0,-) -) is the ReLU function. For all experi- ments, Dimin := {(,,, Tj h is derived from a sample path n transitions with the same seed (42). For each instance i, sample random features using the seed i. The following graphs show averages over 30 instances.
Correction Factor vs. Model Complexity. The correction factor (equation 17) plays a key role in the asymptotic MSBE and MSBE. Figure 2 shows 8 as function of the model complexity N/m and for different values of the regularization parameter X. It confirms that, as stated in Theorem 5. 8 is decreasing function of N/m. For small X. we observe sharp decrease at the interpolation threshold (N = m). E.g., for
10 falls from an order of 10? in under-parameterized models (N < m) to order of 10' in wer-pparamteriized models (N m). For larger values of X, decreases more smoothly and has smaller values. Further experiments on the behavior 5 and experiments for other environments are provided in Appendix A.
8

---

Published as a conference paper at ICLR 2024
10a
10a
MSBE
MSBE
10*
10"
10
0
0.5
1
1.5
2
0
0.5
1 1.5
2
N/m
N/m
Figure 4: With more distinct states m visited, the double descent in the MSBE diminishes, disappearing for m = |S]. MSBE from The- orem 5.3 (lines) and avg. numerical results over 30 instances (crosses) in synthetic ergodic MRP for m 0.86|S] (purple), m = 0.998 S (ma- roon), and m = |8| (green) with y 0.95, [S], 3000.
Figure 5: The discount factor has little effect on the double descent in the MSBE. Results in the Gridworld MRP for y = 0 (purple), (maroon), ? 0.95 (green). and & 0.99 (or- 5000. MSBE from Theorem 5.3 (lines) and avg. numerical results over 30 instances (crosses).
0.5
ange) with m 386,
Double Descent Behavior. As a consequence of the sharp transition the correction factor for small (g-regularization parameters, as discussed above, Theorem 5.2 and Theorem 5.3 predict a change in behavior of the empirical MSBE and true MSBE between the under- and overparam- eterized regimes. Figure shows both MSBE and MSBE N/m with different -e-rguulaiization penalties in Taxi-v3. Despite the fact that the equations for MSBE and MSBE were derived for the asymptotic case N + oc, we observe an almost perfect match with the numerically evaluated original definitions in equation and equation For small X, the true MSBE exhibits a peak around the interpolation threshold N = m, leading to a double de- scent phenomenon. In contrast, the empirical MSBÉ close to its minimum N m and almost constant for N 2 m, so no double descent is observed. While for the Taxi-v3, the empirical MSBE necessarily the case in other environments, where the em-
function of the model complexity
smaller than the true MSBE, this pirical MSBE can be larger overall than the true MSBE (see further experiments in Appendix A). For larger X, the double descent in the true MSBE disappears and the difference between the true MSBE and the empirical MSBE is less pronounced, although it may not vanish. Appendix shows similar double descent phenomenon for the Mean-Supn -eann-Squreed Value Error. All the above observations are accordance with established results in supervised learning (Liao et al., 2020).
Impact of the Number of Unvisited States and the Discount Factor 7 Once all states have been visited, MSBE and MSBE: have similar behavior, with peak at the interpolation threshold (N = m)) see also Remark 7. The experiments in Figure 4 depict this behavior. They also illustrate that the double descent phenomenon diminishes the number of distinct unvisited states goes to zero. The experiments in Figure illustrate that the discount factor y has little impact on the double descent phenomenon.
CONCLUSION
In this work, we have analyzed the performance of regularized LSTD with random features in novel double asymptotic regime, where the number of parameters N and distinct visited states m go infinity with a constant ratio. We have established deterministic limit forms for both the empirical MSBE and true MSBE that feature correction terms. We have observed that these correction terms are responsible for a double descent phenomenon in the true MSBE, similar to supervised learning, resulting in a sudden drop in performance for N = m. The correction terms vanish, and so does the double descent phenomenon when the lg-regularization is increased or the number unvisited states goes to zero. Directions for future work include study of the off-policy setting, extending our results beyond one hidden layer to deep neural networks, and going beyond policy evaluation in order investigate other RI. algorithms, such L-Leanning

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENTS
This work was supported by Ecole Polytechnique. We also thank Zhenyu Liao for his helpful dis- cussions on this work.
REFERENCES
Andrea Agazzi and Jianfeng Lu. -efforal- learning with nonlinear function approxima- tion: lazy training and mean field regimes. In Mathematical and Scientific Machine Learning, pp. 37-74, 2022.
Zafarali Ahmed. emdp. https: /tttts::/giiee htggggtthhhug.go com/ za httmm/aaaaaaliii /emdd, 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-graine analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-332, 2019.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias trade-of. arXiv preprint arXiv: 1 1812.11118 321, 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal Mathematics of Data Science, 114):1167-1180, 2020.
Eloïse Berthier, Ziad Kobeissi, and Francis Bach. A non-asymptotic analysis of non-parametric temporal-difference learning. Advances in Neural Information Processing Systems, 35:7599- 7613, 2022.
Alberto Bictti and Julien Mairal. On the inductive bias neural tangent kernels. Advances in Neural Information Processing Systems, 32, 2019.
Justin A. Boyan.
Least-squares temporal difference learning. In International Conference on Machine Learning, pp. 49-56, 1999.
Steven J. Bradtke and Andrew G. Barto. Linear least-squares algorithms for temporal difference learning, Machine Learning, 22(1):33-57, 1996.
Qi Cai, Zhuoran Yang. Jason D. Lee, and Zhaoran Wang. Neural temporal-different learning converges global optima. Advances in Neural Information Processing Systems, 32, 2019.
Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xun Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: 198, 2019.
Shenglei Chen, Geng Chen, and Rujjun Gu. An efficient L2-norm regularized least-squares temporal difference learning algorithm. Knowledge-Baade -ased Systems, 45:94-99, 2013.
Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in Neural Information Processing Systems, 31, 2018.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Romain Couillet and Merouane Debbah. Random Matrix Methods for Wireless Communications. Cambridge University Press, 2011.
Christoph Dann, Gerhard Neumann, Jan Peters, et al. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 15:809-883. 88099-883,000 2014.
Kefan Dong, Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International Conference on Machine Learning, pp. 2627-2637, 2020.
10

---

The Annals of Published as a conference paper at ICLR 2024
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Soft actor-critic algo- rithms and applications. CoRR. 2018.
Matthew Hoffman, Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Regular- ized least squares temporal difference learning with nested L2 and L1 penalization. In European Workshop on Reinforcement Learning, pp. 10. Springer, 2011.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2012.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemne:: Convergence and gen- eralization in neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Aviral Kumar, Rishabh Agarwal, Dibya Ghosh, and Sergey Levine. Implicit under-parametenn pateeerrrrameeiizzation inhibits data-efficient deep reinforcement learning. International Conference on Learning Representations, 2020.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. simite-sample analysis of least- squares policy iteration. Journal of Machine Learning Research, 13:3041-3074, 2012.
Michel Ledoux. The Concentration of Measure Phenomenon. American Mathematical Soc., 2001.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in Neural Information Processing Systems, 32, 2019.
Zhenyu Liao, Romain Couillet, and Michael W. Mahoney. A random matrix analysis of random fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent. Advances Neural Information Processing Systems, 33:13939-13950, 2020.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimiza- tion attains globally optimal policy. Advances in Neural Information Processing Systems, 32, 2019.
Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks. The Annals of Applied Probability, 28(2): 190-1248, 2018.
Xufang Luo, Qi Meng. Di He, Wei Chen, and Yunhong Wang. 14r: Promoting deep reinforcement learning by the indicator for expressive representations. IJCAL, 2020.
Clare Lyle, Mark Rowland, and Will Dabney. Understanding and preventing capacity loss in rein- forcement learning. In International Conference on Learning Representations, 2021.
Song Mci and Andrea Montanari. The generalization error random features regression: Precise asymptotics and the double descent curve. Communications Pure and Applied Mathematics, 75(4):667-766, 2022.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665-E777), 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves. Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-332 2015.
A. Nedié and Dimitri P. Bertsekas. Least squares policy evaluation algorithms with linear function approximation. Discrete Event Dynamic Systems, 13(1-2):79-110, 2003.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 20, 2007.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Mathematical Statistics, pp. 400-407, 1951.

---

Published as a conference paper at ICLR 2024
Grant Rotskoff and Eric Vanden-Eijnder Parameters interacting particles: long time convergence and asymptotic error scaling of neural networks. Advances Neural Information Processing Systems, 31, 2018.
Bernhard Schölkopf and Alexander Smola. Learning with kemels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint urXiv:1707.06347 2017.
John Stachurski. Economic dynamics: theory and computation. MIT Press, 2009.
Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3(1):9-44, 1988.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Manel Tagorti and Bruno Scherrer. On the rate of convergence and error bounds for LSTD(A). In International Conference on Machine Learning, pp. 1521-1529, PMLR, 2015.
Terence Tao. Topics in Random Matrix Theory, volume 132. American Mathematical Soc., 2012.
Valentin Thomas. On the role of overparameteriiztton in off-policy temporal difference learning with linear function approximation. Advances Neural Information Processing Systems, 35: -7722037224, 2022.
Mark Towers, Jordan K. Terry, Ariel Kwiatkowski, John U. Balis, Gianluca de Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Arjun K.G., Markus Krimmel, Rodrigo Perez- Vicente, An- drea Pierré, Sander Schulhoff, Jun Jet Tai, Andrew Tan Jin Shen, and Omar G. Younis. Gymma- sium, March 2023. URL https:///////. zenodo. org/ wwwgg//eerr///111 012000///112225..20
John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-difference learning with function approximation. Advances in Neural Information Processing Systems, 9, 1996.
Chenjun Xiao, Bo Dai, Jincheng Mei, Oscar A Ramirez, Ramki Gummadi, Chris Harris, and Dale Schuurmans. Understanding and leveraging overparameteriizaioon in recursive value estimation. In International Conference on Learning Representations, 2021.
Roy D. Yates. A framework for uplink power control in cellular radio systems. IEEE Journal on Selected Areas in Communications, 13(7):1341-1344 1995.
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.
Yufeng Zhang, Qi Cai, Zhuoran Yang. Yongxin Chen, and Zhaoran Wang. Can temporal-different and Q-learning learn representation? A mean-field theory. Advances in Neural Information Processing Systems, 13:9968-- 2020.
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL EXPERIMENTS
This appendix shows additional empirical results which cannot be put the main body due to space limitations.
A.1 IN THE DOUBLE ASYMPTOTIC REGIME
Like Figure 2 in Section 6, Figure 6 depicts the correction factor (equation 17) as a function of the complexity model N/ m in synthetic ergodic and Gridworld MRPs. shows a similar behavior than for the one observed in Taxi-v3 in Figure 2.
10
10-9
104
10
10
10
10
10a
10
10
10
0.5
1
1.5
0.5
1
1.5
2
0.5
1.5
2
N/m
N/m
N/w
(a) Synthetic Ergodic MRP
10
À 10
10a
10
10-6
10-3
10
10
10a
10
10
10
0.5
1
1.5
2
0.5
1.5
2
0.5
1.5
2
N/m
N/m
N/m
(b) Gridworld MRP
Figure 6: The correction factor 5 is decreasing function of the number of parameters N. For small læ-regularization parameter we observe sharp decrease near the interpolation threshold (N = m, for m distinct visited states). As À increases, the function becomes smoother and smaller (note the different scales of the y-axis). computed with equation 17 in synthetic ergodic and Girdworld MRPs with = 0.95, m 499, 3000 and = 0.95, m = 386, 5000, respectively.
Figure depicts 8 as a function of the Iz-regularization parameter for different ratio N/m. It confirms 8 decreases monotonically the lz-regularization parameter À increases, as stated by Lemma J.4. Furthermore, we observe the impact of regularization parameter becomes less sig- nificant the model complexity N/m increases. Indeed, N/m increases, we observe a larger initially flat region and smaller values of 6.
13

---

Published as a conference paper at ICLR 2024
108
10c
10a
10
c 0.25
0.5
10
10
10-1
10
c=
10 4
10-4
10-4
10
10 9
3
10a
10
10
10
10-9
10-3
10a
10
10 3
10
X
À
(a) Synthetic Ergodic MRP
10c
10c
10a
10
0.25
0.5
10a
10a
10-1
10-2 2
10-4
10 10-4
10-4
10
10
10 3
10
10
10
10a
10
10a
10T
10
10
A
À
(b) Gridworld MRP
106
10a
10a
10
0.5
10
10
10-1
10 2
10-4
10
10-4
10
10 10-9
10a
10
9
10 33
10a
10
10-3
10a
10
10a
A
A
(c) Taxi-v3 MRP
Figure 7: The correction factor 8 is a decreasing function of the Ig-regularization parameter
X. As the model complexity = N/m increases, the impact of regularization parameter becomes less significant (note the different scales of the y-axis). is computed with equation 17 in synthetic ergodic, Girdworld and Taxi-v3 MRPs with = 0.95, m = 499, n = 3000, = 0.95, m 386, n 5000 and 7 0.95, 310, 5000, respectively.
14

---

Published as a conference paper at ICLR 2024
A.2 DOUBLE DESCENT BEHAVIOR
Figure shows both MSBE and MSBE as a function of the model complexity N/m with different Iz-regularization penalties in synthetic ergodic and Gridworld MRPs. Both MSBE and MSBE depict a similar double descent behavior for small À than in Figure 3 in Section 6. We observe the empirical MSBE is not necessarily lower for over peeamaaraettre (N >> m) models.
10
10
À 10
MSBE
109
10
10
10
10-1
10-1
0.5
1
1.5
2
0.5
1.5
2
0.5
1.5
2
N N/m
N/m
N/m
(a) Synthetic Ergodic MRP
10a
10
10
10-9
À 10
X 10
100
10
10
MSBE
10-1
10
10
10
10 -2
10
0.5
0.5
1.5
N/m
N/m
N/m
(b) Gridworld
Figure The double descent phenomenon occurs in the true MSBE (red) of regularized LSTD, peaking around the interpolation threshold (N m for N parameters, m distinct visited states) when the empirical MSBE (blue) vanishes. It diminishes as the Iz-regularization pa- rameter increases. Continuous lines indicate the theoretical values from Theorem 5.2 and The- orem 5.3, the crosses are numerical results averaged over 30 instances after the learning with reg- ularized LSTD in synthetic ergodic and Gridworld MRPs with = 0.95, d 50, = 3000 and n 5000, respectively.
15

---

Published as a conference paper at ICLR 2024
A.3 IMPACT OF THE NUMBER OF UNVISITED STATES AND OF THE DISCOUNT FACTOR
Like Figure 4, Figure depicts the behavior of the true MSBE for different numbers of distinct visited states and shows that the number of distinct unvisited states goes to zero, the double descent phenomenon diminishes.
10a
A 10
10a
10
10a
À 10
MSBE
10
10
10
10
10
10
10-1
10-1
10-1
0.5
1.5
0.5
1.5
2
0.5
1.5
2
N/m
N/m
N/m
(a) Synthetic Ergodic MRP
0.86|8| (purple), 0.998 (maroon),
[S] (green).
10
10
10a
10
10
À
MSBE
10
10
10
10
10
10-2
0.5
1
1.5
0.5
1.5
2
0.5
1.5
2
N/m
N N/m
N/m
(b) Gridworld MRP for m 0.59|S| (purple), m S| (maroon), m = 0.97 (green).
10a
A 10
10a
À 10
10a
A
10
MSBE
10a
10a
10a
10a
101
10
1
10a
10a
0.5
1.5
2
0.5
1.5
2
0.5
1.5
2
N/m
N/m.
N/m.
(c) Taxi-v3 MRP for 0.57[S| (purple), 0.79 (maroon),
0.87| (green).
Figure 9: With more distinct states m visited, the double descent the MSBE diminishes, disappearing for
(S]. Continuous lines indicate the theoretical values of MSBE from Theo- rem 5.3 for different numbers of distinct visited states m.; the crosses are numerical results averaged over 30 instances after the learning with regularized LSTD in synthetic ergodic, Gridworld and Taxi- v3 MRPs with = 0.95, d = 50.
Figure 10 describes the impact of the discount factor 7 the double descent phenomenon, and shows it remains true for all 7-
16

---

Published as a conference paper at ICLR 2024
10'
A 10
10'
A
10
10
MSBE
10
10
10
10
10
3
10
0.5
1.5
2
0.5
1.5
2
0.5
1.5
2
N/m
N/m
N N/m
(a) Synthetic Ergodic MRP
10a
10a
10a
A 10-9
10-6
À 10-3
MSBE
10
10
10
10
10
10-4
0.5
0.5
2
0.5
1.5
N N/Tr m
N/m
N/m
(b) Gridworld MRP
10a
10a
10a
A = 10-9
10
À 10
MSBE
10a
10
10
10
10 11
10 -1
0.5
1
1.5
2
0.5
1.5
2
0
0.5
1.5
2
N/m
N/m
N/m
(c) Taxi-v3 MRP
Figure 10: The discount factor has little effect on the double descent in the MSBE, Continuous lines indicate the theoretical values of MSBE from Theorem 5.3 for ? 0 (purple), 7 0.5 (maroon), 7 0.95 (green), and 7 0.99 (orange); the crosses numerical results averaged over 30 instances after the learning with regularized LSTD in synthetic ergodic, Gridworld and Taxi-v3 MRPs for d 50, 3000, d 50, 5000 and d 50, 5000, respectively.
17

---

Published as a conference paper at ICLR 2024
A.4 IMPACT OF THE 12- S0-REGLLARIZATION PARAMETER ON THE MSBE
Figure 11 and Figure 12 depict the empirical MSBE and the true MSBE as function of the 1z- regularization parameter. In supervised learning, the training error is an increasing function of the 2-- regularization parameter À (Liao al., 2020), whereas the discount factor induces more intricated behavior in RL as described by Figure 11.
10
MSBE
0.5
0.5
0.5
10-1
0.25
0.5
10
9
10
10a
10
99
10
10a
10
10
9
10 3
10
A
(a) Synthetic Ergodic MRP
-10
-10
10
MSBE
4
4
2
2
10-2
2
10
10
3
10
10
10
3
10
10
10
10a
10
10"
10
(b) Gridworld MRP
MSBE
0.5
10
r=1
r
20
20
20
10
10
10
0.25
10a
0
0
0
10
10
10
10
10
10a
10
10
10a
10
10
10
A
(c) Taxi-v3 MRP
Figure 11: MSBE not an increasing function the lzrrgulariizatinn parameter X. Continuous
lines indicate the theoretical values of MSBE from Theorem 5.2 for 1000 (purple). (maroon), and n 5000 (green): the crosses are numerical results averaged over 30 instances after the learning with regularized LSTD in synthetic ergodic, Gridworld and Taxi-v3 MRPs for = 50, n 3000, = 50, n = 5000 and 50, n 5000, respectively. Note that the y-axis has logarithmic scale for N/m
3000
In Figure 12 at the interpolation threshold (N = m), we observe that as increases, MSBE de- creases and does the peak observed in the previous experiments. For other ratios. the true MSBE depicts complex behaviors that may differ between under- and over-parameterized models and de- pends the environment. Yet, both empirical and true MSBE show similar and opposite trends for the same Am.a. ma regardless of the number of samples n and distinct visited states m. In practice,
the effective Iz-regularization parameter Am, is tuned. This suggests that it depends on both the number of transitions collected n and the number of distinct visited states m, and not just on the number of samples as it is commonly suggested (Hoffman et al., 2011; Chen et al., 2013).
18

---

Published as a conference paper at ICLR 2024
10a
0.8
0.8
0.8
MSBE
0.6
0.6
0.6
0.4
0.4
100
0.4
2
0.2
0.25
0.2
0.5
0.2
0
10
10
10
10
9
10
103
10
10-3 3
10a
10
9
10
10
X
X
(a) Synthetic Ergodic MRP
10a
0.3
0.3
0.3
MSBE
0.2
0.2
10"
0.2
0.1
0.1
0.1
10 2
0
0
10
10
10
10
10
10a
10
10-3
10a
10
10
10a
À
À
(b) Gridworld MRP
30
30
10a
F=1
MSBE
20
20
20
10a
10
10
10a
10
0
0
10
10
10
10a
10
10a
10
10a
A
A
(c) Taxi-v3 MRP
Figure 12: At the interpolation threshold (r N/m 1), as increases, MSBE decreases and so does the double descent phenomenon. Continuous lines indicate the theoretical values of MSBE from Theorem 5.3 for 1000 (purple), 3000 (maroon), and 5000 (green); the crosses are numerical results averaged over 30 instances after the learning with regularized LSTD in synthetic ergodic, Gridworld and Taxi-v3 MRPs for d 50, 3000, d 50, 5000 and d = 50, n 5000, respectively. Note that the y-axis has a logarithmic scale for r = N/m 1.
19

---

Published as a conference paper at ICLR 2024
A.5 IMPACT OF THE BECOND-ORDER CORRECTION FACTOR A IN THE TRUE MSBE
Figure 13 depicts A in Theorem 5.3 as a function of the model complexity N/m for small 22- regularization parameter (A 10-9). shows the double descent phenomenon in the true MSBE is mainly due to the second-order correction term A.
10
100
10
10
10
10a
10 2
10
10"
0.5
1
1.5
2
0.5
1.5
2
0.5
1.5
N/m
N/m
N/m
Synthetic Ergodic MRP
(b) Gridworld MRP
(c) Taxi-v3 MRP
Figure 13: The double descent phenomenon in the true MSBE is mainly due to the second- order correction term A. A is computed with equation 20 in synthetic ergodic, Girdworld, and Taxi-v3 MRPs with = 10 99 7 = 0.95, m 499, n = 3000, À = 10-9 7 = 0.95, m = 386, n = 5000 and À 10 7 0.95, m 310, 5000, respectively.
B MEAN-SQUARED VALUE ERROR
In this section, we study the Mean-Squaree Value Error (MSVE) and observes similar double descent behavior than the one observed for the MSBE. The MSVE defined as
MSVE(()
V >50 D.
(22)
Using similar approach than for Theorem 5.3, we obtain the following deterministic form of the asymptotic MSVE:
Corollary B.0.1 (Asymptotic MSVE). Under Assumptions 2, and 3, the deterministic asymptotic N 1 Qm (A)r
MSVE is MSVE(()
V
D. + A, with second-order correction
va 1+4
factor
N Dr 1 20.
Vs) 11 (A)r
A
(23)
Qm) Qm))
As N, m. d + oo with asymptotic constant ratio N/m, MSVE(()
MSVE 0.9 O.
Proof. Using D Im P D= PP D I ~ D, PP and a with similar proof than for Theorem 5.3, we find Corollary B.0.1.
D
Remark 8. Like MSBE(O) in Theorem 5.3, the MSVE(() is also influenced by the correction terms 8 and A. Note that in asymptotic regimes where N/m - oo or > sc, the correction terms vanish. When N/m + oc, MSVE(@) is independent of X as shown in details in Appendix C.
Figure 14 shows both the empirical MSVE and the true MSVE function of the model complex- ity N/m with different l2 Igregulaaizztton penalties À in the synthetic ergodic, Girdworld and Taxi MRPs. Like the true MSBE, observe almost perfect match with the numerically evaluated original definition equation 22.
For small X, like for the true MSBE, the true MSVE exhibits peak around the interpolation thresh- old N = m, leading to a double descent phenomenon. contrast, the empirical MSVE close to its minimum at N
and almost constant for N m, so no double descent is observed. Un- like than for the true MSBE, observe that the empirical MSVE is always smaller than the true
20

---

Published as a conference paper at ICLR 2024
MSVE. For larger X, the double descent in the true MSVE disappears and the difference between the true MSVE and the empirical MSVE less pronounced, although it may not vanish.
A 10
10
10
10
101
10
MSVE
109
100
100
10
10
10
0.5
1
1.5
2
0.5
1
1.5
2
0
0.5
1.5
2
N/m
N/m
N
Toy Ergodic MRP
10a
10a
10a
10
10
MSVE
10
100
10
10-1
10-1
10-1
0.5
2
0.5
1.5
N/m
N/m
/m
(b) Gridworld
10a
10
10a
10
10a
10
MSVE
10"
10
10
0.5
1
1.5
2
0.5
1
1.5
2
0
0.5
1.5
2
N/m
N/m
N/m
Taxi-v3
The double descent phenomenon occurs in the true MSVE (red) of regularized LSTD, peaking around the interpolation threshold (N m for N parameters, distinct visited states) when the empirical MSVE (blue) vanishes. It diminishes as the Izrreuularization parameter À increases. Continuous lines indicate the theoretical values from Corollary B. the crosses are numerical results averaged over 30 instances after the learning with regularized LSTD in synthetic ergodic, Gridworld and Taxi MRPs with ? 0.95, 50, n 3000, 5000 and 5000, respectively.
Figure 14:
C REFORMULATION OF THE MAIN RESULTS
Let C be a compact set such that S C C. We extend the stationary distribution π on C by setting T(s) 0 for E SYC. We denote by (C, т) the set of squared integrable fune- tions [ + R with respect to the distribution क on C, and the norm on I,²(C, πτ) defined || ( (S.f) = f (dr). The Frobenius norm of matrix A is denoted as || = ((A A) TTAAA)
21

---

Published as a conference paper at ICLR 2024
In this section, we aim to reformulate the results from Section 5 in feature space derived from the eigendecomposition of Ps. The section is organized into three subsections: Section C.I introduce the asymptotic feature space, we reformulate the results of Section 5 in the new feature space in Section C.2 and we provide the proofs for these results in Section C.3.
C.I ASYMPTOTIC FEATURE SPACE
Asymptotic Feature Space. Both Theorem 5.2 and Theorem 5.3 use either the deterministic Gram feature matrix & (defined in equation 16) the deterministic Gram feature matrix &s that are given by the continuous kernel function + C x C - IR defined as
(s,, x = (w [o(w"s) aww" s')] [)]"()
Since & is continuous and C' is compact, the Mercer's theorem states (Schölkopf & Smola, 2002) that
M
M
(8 8') = Σ (xp(()) = Σ (i()))x(s));
(24)
==1
where {v; M and ( are the eigenvalues and eigenfunctions of the Sillbet-SSchiitt integral operators Ta (², - L2( + (s)) Sn. ((s, (() and fwi(-)
(T) [i= the rescaled eigenfunction. {w)(-)) forms an orthogonal basis in (C, m). Usually, M is infinite. In the following of this section, we will find convenient to define a vector representation of functions in the asymptotic feature space defined by the feature map {w;}Mr i-=- For any state matrix A Rdxp, denote by SA Mx the feature matrices of A so that [Ralis = (A,), for A, the jth column A. With those new notations, we can decompose & and $5
T g = g=
and
S = 2--ss
Regularized LSTD the Asymptotic Feature Space. Let up RM the weight vector returned by the regularized LSTD with the rescaled lz-regularization parameter X m61+)) for the asymptotic features [w transitions collected in Imain:
N
1 vn
A
+ X
m(L+5)
IM
N
where
A = -V,)
(25)
Second- Correction Factor in the Asymptotic Feature Space. order correction function defined as
Let fa(-) be the second-
fa (B) X m (1+-)²2
B
A X
m(1+6)
IM
N2
A+A (+
m((+0)
Ins
1-1 1
A
N
F
From the definition of fa (B), it directly follows that (A 0 as N/m 00 as co.
C.2 REFORMULATION THE MAIN RESULTS
C.2.1 EMPIRICAL MEAN-SQUARED BELLMAN ERROR
Theorem C.I (Asymptotic Empirical MSBE). Under the conditions of Theorem 5.1, the deterministic asymptotic empirical MSBE is
M) | + vovoll (V.
As N, m, d + oo with asymptotic constant ratio N/m,
() MSBE(() 0.5 0.
22

---

Published as a conference paper at ICLR 2024
Remark 9. The lest-hand term |r + - vol" in MSBE( depicts the empiri- cal MSBE for the regularized LSTD the asymptotic features {wi) M with the rescaled 12- regularization parameter X ( transitions collected in Duain-
Remark 10. As N/m increases, the inftuence of the l2 lz-regularization parameter decreases.
Remark 11. As N/m - oc, MSBE
C.2.2 MEAN-SQUARED BELLMAN ERROR
Theorem C.2 (Asymptotic MSBE). Under Assumptions 1, 2, and 3, the deterministic asymptotic MSBE is
MSBE(O) = =|rr+ + 7 -2 I D.. + (Lss - -
As N, N,m,a d + with asymptotic constant ratio N/m,
MSBE(O)- MSBE
0.
Remark 12. The left-hand term ||r + +yPP - 2 2 in MSBE depicts the true MSBE D.
for the regularized LSTD the asymptotic features {wi)i= with the rescaled lz-regularization parameter X mm(++)) transitions collected in Dinain-
1M
Remark 13. As N/m increuses, the influence of the Iz-regularization parameter decreases. Remark 14. As N/m - oc. MSBE(O) ()) converges to the MSBE of va without the l2 regularization parameter.
C.2.3 MEAN-SQUARED VALUE ERROR
Corollary C.2.1 (Asymptotic MSVE). Under Assumptions 2, and 3, the deterministic asymptotic MSVE
() = ||V ng D. + (D((D))
As N,m,d d + oo with asymptotic constant ratio N/m,
MSVE(Ø) (SVE(() a.e
Remark 15. The left-hand term V - -2rroll? MSVE(() depicts the MSVE for the reg-
ularized LSTD in the asymptotic features {wi (w with the rescaled lz-regularization parameter
mm(++)) on transitions collected in D
N
Remark 16. As N/m increases, the inftuence of the Iz-rgullaizzation parameter À decreases.
Remark 17. As N/m oc, MSVE(() converges the MSVE of va without the la regularization parameter.
C.3 PROOFS OF RESULTS FOUND IN SECTION C.2
Theorem C.3 (Asymptotic Empirical MSBE). Under the conditions of Theorem 5.1, the deterministic asymptotic empirical MSBE is
()) || 2x 2 voll (()'
As N, d + with asymptotic constant ratio N/m,
MSBE( MSBE 0 0.5
Proof. We have
x Q 12)
r +1 V. 22 n N
= + 52 voll?
23

---

Published as a conference paper at ICLR 2024
For Å, we have
Tr (mm()))
= (2ml))(Un (U, -V,, (m)7)
-m 148
m(1+5) N
(v,)" 525 A mLL+5)
IM
A 1
Ind
-17
ag (U, - -V,))
N
N
ml(+8)
> A + 1 IM
Tr ( (2) 4 Qm (1))
N² 1 Tr - [Va)" mm)
m (I+077
(A A + x m((++)
IM
-11'
A
mil++1 I
A
N
N
= A + A mm TM
A
and
1| (A)r m(1+8)
||00| 1
Theorem C.4 (Asymptotic MSBE), Under Assumptions 2, and 3, the deterministic asymptotic MSBE is
MSBE(0) = ||| -P - -2 D. + (1s)
As N, m,m,d d + do with asymptotic constant ratio N/m,
MSBE(() MSBE 0.. 0.
Proof. We can rewrite
Tr (A
1 Tr [[A ml1+5) [M]
-T A' -
m(2+0) IM] 1
.N
[T|s] Pl (1++5)) IM]] F.D.''
I+0
N
I
Tr (Appss = Nx4 + - 2 F.D.''
m 140
and
Tr VV,)
= # Tr Ap A A(A+ m(1+8) [M] -1(2ss
N 1 Tr [ - - D [|s) - -P|2 A m(1+
IMs] 1
m I+
N
m 148 - - [T - PIn? A mL
N IMs]
F.Dx
Therefore,
Tr (Ap OsV.OT 20, -V.) Us + Vs!)
N 1 i
| - P [|s] - PIN A A + m(
IM -1
=
F.D.
= x²
||s|| A A 1 1
F.D.
24

---

Published as a conference paper at ICLR 2024
D EVALUATION OF Ds OR D
The evaluation D = E [ow"" S)) o(w" $)] or 2s Em ( 3)"o(""s) s)] naturally boils down to the evaluation of its individual entries and thus to the calculus, for arbitrary vectors a, E IRd
(2x)- f (((((e)) a ())(((()))))))) bb) =1ball dw.
@ Blo(ww aa)((w"))) (lo((""))o(uu"
(26)
The evaluation of equation 26 can be obtained through various integration tricks for a wide family of mappings yp-) and activation functions (.). We provide in Table (found in Louart et (2018))
the values of $ for w ~ (o, IJ) (i.e., for (t() = t) and for a set of activation functions a()) not necessarily satisfying the Lipschitz continuity, In experiments in Section 6, we focus only on the ReLU function, i.e., (t) max(t, 0).
Table 1: Values of aab for w NO0, Ia), (aa = ab Ta]loT
(Louart et al., 2018).
(t)
a
max(t, 0)
||||||
(Z(a, b) arccos (L((a, b)) + / L)a,
2n
[t]
|||||||||||
((a, b) arcsin(L((a,.
/1 <<a,))
(t)
2 aresin
2a
1 (c>0)
2r (a b))
2
sign(()
2 Larcsin(<(a,) b))
cos(t)
exp( [||a||2 [[bll)) cosh bb)
sin(()
exp
(1|a|22 [[]l))) si
25

---

Published as a conference paper at ICLR 2024
E PROOF OF THEOREM 5.1
Under Assumptions and 2, this section is dedicated to prove the asymptotic equivalence between E[Qm(A) and
@m (2) = m + (U. (V.
AI
defined in Theorem 5.1, when N, + c0. In order to prove Theorem 5.1, we shall proceed by in- troducing an intermediary resolvent Qm (A) (defined in equation 27), and show subsequently under Assumptions 1 and 2 that
|E (m (m - and 1| - 1m + 0,
N, co.
In order to simplify the notations, we denote by Qm the resolvent Qm (A). The first half of the proof dedicated to Lemma E. which proposes a first characterization of TE[Qm.] by Qm as N, m + oo under Assumptions and 2. This preliminary step is classical in studying resolvents in Random Matrix literature (Louart et al., 2018; Liao et al., 2020) as the direct comparison of [[ to Qm with the implicit (equation 17) may be cumbersome.
Lemma E.1. Under Assumptions 1 and 2, let X and let (m) E Ruxn be the resolvent defined as
vVn) N (Vn) + Ahn
(A)
(27)
m +
for the deterministic Gram feature matrix
$ (ol S) o(w" $)}.
and
TT((U, (,
(28)
where
Q-())
(ū,= o (3 o + AIn
(29)
m
for which W- IR (N-)x depicts the submatrix of the weight matrix W (defined in equation 5) without the first row. Then,
lim |E (m (A)] Qm = 0.
Remark 18. Firstly, can note that is uniformly bounded. ( S)[P=] and from Lemma K.2, have
Since 1 Tr((3)) m
1 m
(T)()))= Loa Pr
( (o(w=$)12 =t) dt =
/ 2t Pr
1 (lo(w))) > dt O(.).
m
(30)
We deduce that
(())=-V,)''a
&
- Tr( (+( (31)
where we used [Tr(AB)] S |||] Tr(B) for non-negative definite matrix B together with Lemma 1.1 which asserts the operator norm of the resolvent Q_ is uniformly bounded. Further-
more both [[al)l and VVV, are upper bounded by 1.
Proof. We decompose the matrix E/
N Σ
=
Σ ooo!!
(32)
i=1
26

---

Published as a conference paper at ICLR 2024
where 0, o w., R for which w, R denotes the i-th row of W (defined in equation 5).
Using the resolvent identity (Lemma L.2), we write
E(Qu
E
Q
--1- m
-nn
(Ün vV,)
"
E
Eg
U,
Qm
m
N
NN
ElQm - Vvn² 1 Ü a
1
Σ
E
m (Ü, >Vn'' pm
im1
N (()(",--V)"' T. Qm
Σ
E
Q
-
Qu
t
I o UUQ- TVa m
where the last equality is obtained with the Sherman identity (Lemmaa L.4) for
Q 1 Ü, - "E) -
-V) + Ml
(33)
independent of og and thus w,, Exploiting this independence, we decompose
E[Qm]
Qm
(34)
N
E (U,
UUNa I+am Σ
Q-i(U
E
~V.)"
Qm
+
(Ü, V o U -V²))² o, a) Q
@m
m 0
1 U QU, (U.
(35)
E Q-i( -
$ U.
m
++0
Ün - vV.) o, Ü,Q 1 (0. Q
E
1
1=1
=Za
(36)
The last equality is obtained by exploiting the Sherman identity (Lemma L.4) in reverse on the rightmost term, and from the independence of Q-, and a for the second right-hand term. We want to prove that both Z1 and Ze have a vanishing spectral norm under Assumptions and 2. With both the resolvent identity (Lemma L.2) and the Sherman identity (Lemma L.4), rewrite Z
Z
1
Σ
E(Q. Q-il(nn-7in u..
m
1
2=1
1
E U. (V. Qm
m² 1 ++a
N
1
Σ
E Qm TfQm(t
ÜU, - -V.-v,,) T 15 Ú Qm
m² 1 1
1
E Q m (Ü, -V, -
(Ün V
2 1
where D E N is diagonal matrix for which, for all E [N], we have
D. = (1 _ -.
(37)
27

---

Published as a conference paper at ICLR 2024
With similar proof than for Lemma I.1, show there exists k such that, for all m,
have ||2ml || I K @.. and then
1 + a (Ün - -V,) B Qm =
m N (I, AQm)
-
m (1+ Ak
(38)
N
Furthermore, from Lemma E.4, we have
QmiUn V = -
(39)
m
Therefore, by combining both equation 38 and equation 39, we conclude that 2 has a vanishing spectral norm, i.e.,
Σ RIQm - - Qm
(40)
m
m
We want to show now that Zz has also vanishing operator norm. For E [N], by setting
B: mm (Ün -v.) T o: m
a O',TU.Q -V,) (
and
C C C-=-
decompose Ze with its symmetric and its akew-symmetrie part
N
Z2
E
Qm
Ün, -V-) o
1 -0.
1 a m
m
i=1
N
E
[
1+ a.
t=1
1
N
B.C + C.B.
N
B.C. C,B."
E
E
1
1
2
1=1
For the symmetric part, we use the relations deduce that
(B) 2 and C,) 00
BBB"T - = B.C + C.B. 3 B.B. + C.C.T,
where < is the Loewner order for semi-posiitive-defiite matrices. For the skew-symmetric part, we observe that |E C C,B = || E B - C, for -1 With a similar reasoning than above, using the relations (B,+iC.(B,+tiC)) > 0 -B,, (B.-iC.)(B,-iC)) deduce the relation
-B, - C.C. Bi - C,B = BB + C.C.F
From those relations, for both the symmetric and skew-symmetric parts, we have
Σ
Q
Ü ÜÜn
vvn) T
U, (0. a) )
I+am m
N
c.O. 1)
1
Σ
B.B.
B
ΣE
1+a
(41)
From Lemma 1.4, we know there exists real K¹ Qm... 0 such that, for all m, we have
1
Q
- 7 v T T
$ kk..
Vm
28

---

Published as a conference paper at ICLR 2024
At this point,
N
E
B
2
Qm (Un -V.) प. (Ü, -V,) ath (0,
E
vm
Vm
E
Qm ÜÜn (Un->Va)
DID (Ün- >V,) Qt
$ Vm.Q Q... | D11l,
where D2 NxN a diagonal matrix for which, for all i [N], we have
D2j: (-oTU..- - >V,) a. -a)
From both Lemma K.5 and union bound, we have
Pr D2ll > t) Pr
max
[22] +t
< CNe C.N.e-ommall min(t,
ISISN
for some c, C' > 0 independent of m and N. We have thus
E ( |2 =
max ISiSN
D3).
=
Pr
DD > t dt ISiSN
max
Pr
max ISiSN
D22i > dt
2
21CNe cm min(t, dl
21CNE amt? dt + J 20CNe cmtt dt
21CNE - cmd? dt + (
<
21CNe -mnt dt
J0
j
1
2C
00
tNe 1² dt +
1 20 000
tNNe -dt
Jo
m² c² Jo
m
m
We deduce that
N
Σ
E
B
O
m
m
In addition, with similar proof than for Lemma 1.4, can show there exists real Ky > such that, for all m, we have
| m
ZTU
$ K
V
1+a
where 22T is the Cholesky decomposition of T
g. Therefore,
E
1
C.T.
Σ E
U T.
mym
i=1
1 N
+ Ü U m
mm
m
0
m
29

---

Published as a conference paper at ICLR 2024
From equation 41 and above, deduce that Zz vanishes under the operator nom, i.e.,
Z2 =
(42)
Vm
Using both equation 40 and equation 42 into equation 36, we conclude that
| [ Qml
(43)
To get Theorem 5.1, we start from Lemma E.1 and we show that
llQm (A) (A)l 0,
as N, m - 00.
Theorem E.2 (Asymptotic Deterministic Resolvent). Under Assumptions I and les X 0 and
let Qm(A) E xn be the resolvent defined as
N 1
(m)
1 (V. A
where 8 is the correction factor defined as the unique positive solution to
VV, -T D Nt, }
1 Ir "
N 1 (Ü,
5 =
+
Then,
Ew [qm (2)] - -mm\)=|(
lim m=00
Proof. From Lemma J.I in Appendix J, we know that exists and the unique positive solution of equation 17 under Assumptions 1 and 2. From Lemma E.1 we have first asymptotic equivalent of Ew [Qm] given by
N 1 (Ūn (vn
Qm =
BzÜn + AI
1
where
TT((Un, - "' U,,
since
lim EE [Qm] Qm 0.
In order to finish the proof of the Theorem, we want to show that
lim Qm Qmll 0. m-
(44)
From the resolvent identity (Lemma L.2), we have
N
la
Qm Ü (vn- @ uzūnQ
1 Qmll
(45)
(1 8) (x)
Let 2TT be the Cholesky decomposition of $s.- With a similar proof than for Lemma I.4, we can show there exists real K"
such that, for all m, we have
Q
VitaV Qm (Ü, (U,-~v))
vV.)
Z S SKz
Similarly, we can show there exists real
Q such that, for all m. we have
ZTT
< k
1
30

---

Published as a conference paper at ICLR 2024
Therefore,
5) + @ (Un- "3 v(
+ Kg Ro Q K'
As consequence, in order to prove equation 44, it remains to prove that
lim
a 6 0.
m7 700
We decompose Ja as
1
Ja
81
Tr Tr((U,
Un E[Q - Qml)
(46)
m
1 Tr((Un
vVn) D [[Q-] mml)
Ir((Un, vV.) Vv)" Qm
Qml)
m
m
=21
=Z2
(47)
To show Z1 vanishes, we write a as
1 Tr((U, - T. m
1 - Tr(((,, ~V,) U.E. 1 ---10 +-+(((;-><))) ([(U,n-VV))0 &.) B[Qml]).
There exists real K such that
1 TT((U,, -
K -EQ-I-E[QQ..) m.]]
m
since both ||ū,||| and V. are upper bounded by 1, ( definite matrix B, and from equation 30 that uniformly bounds have
< A Tr for non-negative
Tr + g). From Lemma E.4,
N m N
--11|
E 1Qm. - Q-11I
1Qm
m
m
E
Qm(ún -nvn)= DE
m² N
o
where D E NNN is a diagonal matrix for which, for all E [N], we have
D. 1+ [1+ m
of vv))
As consequence, by combining the results above and from Lemma E.I, we conclude for Z₁ that
7
Tr((On - >,, "
fml
m
Using the vanishing result of Zi into equation 47 and applying the resolvent identity (Lemma L.2) on Zz. we get
la 8l < N
a 10- 5
Tr((U,, - "V
40
1
(1
+ 8)(1 + a)
V
which implies that
Ja 81 (1 N
1
1 - "o, = =0 (01
m (1 + () + a)
m
It remains show
1 N
lim sup 700 m m (1 + (1+8)(1+0) a
Tr((ú, - "0, (. <1
31

---

and Published as a conference paper at ICLR 2024
0" A. Z, Q Let the matrices B (Un B
By
AI
mm16 148
N I+a B Alm where A. = Ün - V²)² is the empirical transition model
m
matrix defined in equation 14. Using the Cauchy-Schwarz Schwarz inequality, we write
N 1
(m..Q.B......
m. m (1 + 6) + a)
1 N
Tr( Q ('))
m m (1 8)(1 + a3)
N
N 1
Tr(B', Q B
m m (1+
m m (1 a))
21
2/2
We observe that ==
1 Tr(BnQm) Q(( m
1 Tr TT Q QmQ. 'm)) )
m N 1
X Tr(B',Q',,
Tr (IB.O BT) m
m (1 + ()+
Since HBB,)) is least semi-positive-deffnie under Assumption we have
(T(B', = Tr(Q = TT. 20.
As consequence we have
1 N m m (1+8)2
Ir (B BTT < 8
Tr Q
5
1+6
1 8
To prove I+8 < 1, it remains to show that 6 < cc. With similar proof than for Lemma I.I, can show there exists a real KQ > such that, for all m, we have l|Qm ll I KQ. and thus
1 Tr(BQQm.
2
5= =
TT (( U.Q I TT( $ 11Q... (0) - (T < oa
where we used for the first inequality the relation [T((AB) S |||| (B) for non non-negative definite matrix B. Furthermore, from equation 30, 1 Tr 4 is bounded under Assumptions 1 and 2, and
both | and V |l are upper bounded by We thus conclude for Z that
1 N
lim sup
Tr
1.
(48)
m m (1 + 5)2
With similar arguments, we can show for Z? that
IN
lim sup m m a1+
Tr Q BT)
<
which concludes the proof that
la aa
8l = -
(49)
m
Using the result above with equation 45, we get
N
1
Qm Ün, - vV.) "0sūnQm
ll Qmll
la
5
m (1 5) a
0
m
which concludes the proof.
32

---

Published as a conference paper at ICLR 2024
Lemma E.3. Under Assumptions I and 2, let D RNN be the diagonal matrix defined in equa- tion 37 for which, for all E [N), we have
D;
(50)
m
Then
E
DII O(1.
Proof. Let a is uniformly bounded, i.e., there exists real Ka such that a I Ka- From both Lemma K.5 and the union bound, have
, (A)l) defined in equation 28. From equation 31,
Pr DII 1+ +(+++))=BB max D; D:>1+a+1) S CNN -cm -em min(t,
ISISN
for some C' > O independent of m and N. Therefore,
E
D E
max D:
=
Pr
max D; > 1 dt ISISN
ISTSN
2(1+Ka)
000
max D; 2t Di>t)dt dt
Pr
max D; >t dt + ISISN
Pr
2((-Ka)
ISISN
0c
$ 2(1 + Ka) +
CNe on min
dt
2(1+K.)
22 Ka)
CNe
1+KK
CN
2(1 K.)
-Cm(LLKaa)
cm
O1).
Lemma E.A. Under Assumptions I and 2, les D NxN be the diagonal matrix defined in equa- tion 37 for which, for all E [N], we have
D: = m
OfU Vo, -r..
Then
E
Qm Ü., - VVn) T T DE D. m
00
Proof. From Lemma 1.4, there exists K2 such that, for all m, have - QU,
VV.) T Eg < 2K% and
I Vm
EgUnn Qm K Therefore,
||
E
Qm - v., " DE UÜ Qm
< 22K D|]
m
From Lemma E.3, we have
E =
As consequence, we deduce that
Qm m (Ü, - 2 -
(51)
m
n
33

---

Published as a conference paper at ICLR 2024
F PROOF OF THEOREM 5.2
This section is dedicated to find an asymptotic deterministic limit of the empirical MSBE(() (equa- tion 8) under Assumptions and 2. First, observe that the empirical MSBE depends on the quadratic form r Qm m (A) Qm (A)r since
1 r +
O)
E X
0 Σ 011
(52)
n
1
Σxn -nEx: '' Ex, Qm (2)r
(53)
n
mn
(Ex, - --Eix( 3 Ex. + A1, _ -Exx. - ~xEx; "xxx))'xx+
Exx Q (A)r
(54)
X²
Q (A)r1
(55)
We determine in Theorem 5.2 deterministic limit of MSBE () by combining Theorem 5.1, which provides asymptotically more tractable approximation of Ew [Qm(X] under the form of fixed- point equation, with concentration arguments. Theorem 5.2 is corollary of Lemma F.2 and of the concentration result of Lemma K.2 in Section K. Both Lemma F.4 and Lemma F.5 are key Lemma used the proof of Theorem 5.2 and Theorem 5.3.
To simplify the notations, we denote the matrix Qm as the resolvent Qm (defined in equation 13). We define the matrix V E Rm as
N
1
S m
S
+ δ
B| - (
Furthermore, the notation A B O1-11
means that A|
(
Theorem F.1 (Asymptotic Empirical MSBE). Under the conditions of Theorem 5.1, the deterministic asymptotic empirical MSBE is
MSBE 2/2 Qm(())) A,
with second- order correction factor
(m (1)r
(m)
where
L
=
0T v DÜn and v = (Ū, - Vn))
L - - Vv))
As N, N,m,d d + do with asymptotic constant ratio N/m,
MSBE ( MSBE
Proof. From equation 55, we have
2 QQ m r|
X r -T Q...
MSBE(()
From Lemma K.6, we have
2 T
X² T TTE "TEQQTQQ Qmlr 21)
Pr
TT
Qur
Ce Sen--nnmt mm?
for some C, c > 0 independent of m, and N. Furthermore, from Lemma F.2, we have
Tr 2TQTQQ
@ @m]
QTQ Qm
Q L Q = O
Tr VTQTT V Q...
/m
As consequence, we have
MSBE ( MSBE 0 0.9 O.
D..
34

---

Published as a conference paper at ICLR 2024
Lemma F.2. Under Assumptions I and 2, let Qm E R be the resolvent defined in equation 13, let Qm E [nxx be the deterministic resolvent defined equation 15, and let M E Rax= be any matrix with bounded operator norm. Then,
Tr MQ,
MQ Tr V
QMM,, m
2 v Qm
m
for 1, 2/2 E kR defined in equation 19.
Proof. From Lemma F.6, we have
E = 2 MQm. m Q. - -7,,)= gg Qm
E (Q, -V,) V Tr (M.QT.QQ..) [Q_ 1-Q Q
+ +HH
Vm
Let
= U. XQ
With similar proof than for Lemma 1.1, show that there exists a real Ko such that, for all m, we have ||Qmll S KQ. We deduce thus that M' is matrix with bounded operator norm since |MMI + X From Lemma F.3, we have
[t MQ - -V J Q- MQ (U, - U [|]||==0
Therefore,
1 E TTTMQ MQ + I TV2 QTQ
1 vm
11111
Furthermore, from Lemma F.4, we have
QT 41Qm - (
1 Vm
and from Lemma F.5 we have
E TQQh v Qm]
@ v Qm m
Q v1 m + +01-1
Tr 2 1 1mQm)
(/m
N
We conclude thus
Tr y 2TQTT.
PIQT. QTh MQ m +
TTV fm + O11-1
1 N Tr QT 1
Vm
Lemma F.3, Under Assumptions and 2, let M E RR be any matrix with bounded operator norm, let Qm E Raxn be the resolvent defined equation 13, and let Q_ E Rnxa be the resolvent defined in equation 29, Then,
E
Proof. We observe that
| [B
QTT.M
-E -
| - - - QQ
= -E QQ M
35

---

Published as a conference paper at ICLR 2024
The objective is to show that both terms vanish. By exchangeability arguments, have
B
Q MQml
- E Q=_
N
E
MQ,,MMm, m
N
1
E
U U (U, (Un)
(Lemma L.2)
N
N
1+ 1 m U.Q (Ox))))
E
Q U o V.) MQm
N
m
DE
where D E RNNN is diagonal matrix for which, for all E [N], we have
1 -U. D. 1 m
From Lemma E.3, we know
Furthermore, from Lemma 1.4, we know there exists real K2 0 such that, for all m, have
N ZetnQ. $ K2
and
| | Qm ÜÜ - ~Va) mm
22Kg.
We deduce thus
| E mm]]
-
m
E
1
VV.
N
m
With similar reasoning, can show that
1
E [Q@MQ..) -
-E
and conclude thus
- m
E Q T MQm]
- E [Q_ MQ-1Q11 -11 o
Lemma F.4. Under Assumptions 1 and 2, let Qm E gu be the resolvent defined in equation 13, let Q_ E Raxx be the resolvent defined in equation 29, and let v nR be the matrix defined in equation 19. Then,
QTT 11Qm - Q
Proof. We observe that
Q v
-E Q-:2211111
QT R Qm - - - Qm
E Q
1 Qm
E
Q2
36

---

Published as a conference paper at ICLR 2024
The objective is to show that both terms vanish. By exchangeability arguments, have
|
Q
E [E mm
m
N
Qq Q-1]² v 9m
N
Q
UT. o.
(Lemma L.2)
N
m
E
Q
1+ -U, 2V,) 1m
N
E
of Ü
0
DE 1h
m
where
D DEP RNN is diagonal matrix for which, for all E [N], we have
D; = =+ _ oT ~,,'",
m
Let the matrices
1 B
Q DS DE V. Q
N
mi
and
CT
V
1
m
We decompose Z with its symmetric and its skew-symmetric parts as
BCT
C
BCT CB
z = E =E
+E
2
2
With the same reasoning on the symmetric part and the skew-symmetric part than for equation 41, get for the operator norm
2 <
E [BB
]] [[[[C]]]]
We want to show that both
E BB")
and [ |CC*]]
|| vanish. have
m²
E [BB"]] = E
DE
(Ü, vm) -V,)"" D
N2 m² vm
From Lemma E.3, we know
=|] 0(1).
Furthermore, from Lemma 1.4, we know there exists real K¹2 > 0 such that, for all m, have
- s 5
and
1 Vm
Qm
Ün
52Kg
We have therefore
1
E BBT T
0
Vm
For E |CCT]
we have
[CCT]
= E
QT T
mmmm
m
37

---

Published as a conference paper at ICLR 2024
Let N-+1 and N42
be independent vectors with the same law o have
N2
E
mym Q 1 1
= E
Uhe
UaU, 22
mym m² (1 8)2
Let
B' N 1
2 O
m m +
and
C IN U N N 2 m m
We decompose E |CC*] with its symmetric and its skew-symmetrie parts as
B'C
C
B'C C
E [Cc = E
+
and we get for the operator norm
E |Cc
S E B'B" T
|| [C
To prove
E
[cCT]] vanish, we prove both
| [B'B"] and || [C'CT]] vanish. Let K
(1+8)* N+1 we write E B' B as
N N
E
B
B"
E
1
N
Q NN U,Ü, IN N+ N
mmm m²
(1 + 8)2
N
E
Q N-
Ug
U.
mmm m²
(1 + 8)2
N+1
(
E
K
Σ
o
o
mym
m
m
N+1
Q
m/m
m
1=1
+ E
K 1
Σ
N+1
Q_,
1 [T(0,0TT33)
)
m/m
E=1
E
K (UÜÜ
mVm
22
1
E
K
TU,
Q
m
my m
=2=
where D' E NxN is diagonal matrices for which, for all i [M]. have
D' = -. 1 m
Tr (ū,ū
From Lemma E.3, from Lemma 1.4, and from equation 30, we have
1
Z O
From Lemma K.2, we have
E
0
Vm
and thus
1
ZZ = 0
38

---

Published as a conference paper at ICLR 2024
We conclude that
E
B'B"
=0
m
and
CC
mm
Therefore,
[CC"]]] 0
mm
and
E Q UT + S Qm
- E Q UT + Ü Q
||
=0
(v()
(mm
With similar reasoning, can show
Qml
Q
Vm
We conclude thus
1
1 L 11Qm] - [Q v 1 --11 =
Lemma F.5. Under Assumptions 1 and 2, let Qm E Ruxx be the resolvent defined in equation 13, let Qm E ignx be the deterministic resolvent defined in equation 15, let 1, U2 1uxn be the matrices defined in equation 19. Then,
1 vm
B B[QTH vm
Q f
=0
Tr QT
Proof.
From Lemma F.6, we know that
E E v1 [m = @Th v
Qm
+ E Q
VIVQQ (Ü, - VV,) V.
1
E
Q² L
Qm (Ün Vn) U. Q-
Tr (V2Q0 4 1
E [Q "Q-T P
N
11111
Exploiting Qm (Ü, - V,,"" v V&únn = XQn in the above equation, and from Lemma F.4, we
obtain the simplification
Tr (V2Q v Qm QT v Qm] +11-1 (
E F(QT V Qm
ºT V Q m
N
or equivalently
E m
v Qm]
1 (1- Tr 122 v Qm) E Q v Qml)
QTh v 1 01-11
m
B', XI for which Åm Ú, >V,)"" TT is the empirical transition model matrix (equation 14) and ZTT $ g is the Cholesky decompositon of $... We have from the cyclic properties of the trace
1 Let B', TT A. Z and Q' N 1+a
Tr N
QT m Q.Q..
1 N
(O((),-V,)T V.TTT - 3
m m (1+ +
1 N
Tr B Q' Q B.).
m m (1+
39

---

Published as a conference paper at ICLR 2024
From equation 48, we have
N 1
lim sup
Tr(B, Qm <
m m (1 + 5)2
Therefore,
E B v
Qm
=
2Th v Qm m +
Q v Qm +11-1
1 1 Tr 2 v 1
(/m)
Lemma F.6. Under Assumptions and 2, let Qm E ER be the resolvent defined in equation 13, let Q_ TRxx be the resolvent defined in equation 29, let Qm TRxx be the deterministic resolvent defined in equation 15, let Un Vn E Rmxx be the shift matrices defined equation 7, and let M be either any matrix with bounded operator norm M v Then,
- -QT MQm.
Q NMMQQT (U,, ~V,) u U
+ E Q- MQM - VU N
Tr ( E Q Q
=0 m
for 1, 222
E TRax defined in equation 19.
Proof. With the resolvent identity (Lemma L.2), we decompose E MQ
E E
MQ
M
MQQu
2m]
E [I
Qm,]]
(56)
O M
E
MQm
E
QT MC m
Ü -V.) (Ū, - - u Qm
Q M.
+E
TQ,. m ÜÜ, VVn) Tw TÜ
=21
E
Q MTMMQ -V. a U.Q
Z2
(57)
where ET Σm o is the same decompositon of ΣT than the one used in equation 32. From Theorem 5.1, we have
IE IE m
Qm = 0
Therefore, from above and from Lemma F.9 which upper bounds I.MQ.. ||. we deduce for Zi that
2 QT
MQ..Q,.
| QT MQ m
Q MQ...
| ml
m
[
mm
We want to find now a deterministic approximation for Z, in equation 57. From the Sherman identity (Lemma L..4 and with the resolvent Q defined equation 33 as
Q [ (Ü - -,)
1 1 a, AI m
40

---

Published as a conference paper at ICLR 2024
obtain the following relation
L Q -ho
Qm = Q-
1+ m (Un
By remarking that for all i [N], have
QT (Ü, - VW)'o
= MQ UU, -V,0)~~-VVao 0, 1+ UU
ΩTh MQ. m Ü, - Vnn Th u
1+0
8 m
U. a;
Z MQ m (Ü, V 0,0 Ú,
1+ 8
1 m
1 L0 Q (Un VV,
decompose Ze
(Ū, U.Qm L.
Z2
-E
E
(58)
E
QT m Ün, V.
(59)
22
N
(U, (U, ~Vn)""
Q U Q U
m
0
1+ 1. of (V)=,
=Z2
(60)
N
6 -0.
" Q,,MQ,i ~V,) o Ü.Q
m 1 +
m
=Z33
(61)
Σ E
Q
m 1 + =1
Lff -W00n Ü,, ~o) (o (0-
(1+ OFT ~V,)=o,
=2.1
(62)
Z21 Zz2 + Z23 ZZa-
(63)
From Lemma F.7, we have
1
Zza
0
mm
With similar proof than for Zze, we can show for Zza that
Zz4 || = 0
m
From Lemma F.8, we have
Zz3 = 0
mm
41

---

Published as a conference paper at ICLR 2024
As consequence, we conclude that
MQml QTh MQ m +E
1 (U,
ss.,aa Qm
E Q=MQm vV.)"
1 N
Tr (v220% MQm) B v
+ 1
(m
Lemma F.7. Under Assumptions 1 and 2, let Zn2 E BRux be the matrix defined in equation 60 as
Zr2
1
1
Σ
N
E
Q"
of (Un VV.00=, (U, ~VVn)
m
1 1+ U.! -V.
Then,
Zz
Tr
=
N
where Qm E RaxR is the deterministic resolvent defined in equation 1.5, Q Raxa is the resol- vent defined in equation 29, and 1, 22 E Raxn defined equation 19.
Proof. Let DE D be diagonal matrix for which, for all [N], we have
D. = - - -VV)"" To)
and D2 E NxN be another diagonal matrix for which, for all i E [N], we have
D2); 7 (Ü, - VV. (U, VV.)o
1
Tr (M
1+ 1
N
( R V.) (U, To
1+ Lo (Ü, V...TO
1 (Ü VV,) 2 2g (Un V Qm
m
1+8
ÜÜ, VV MQ (Ü, Vo.)TO
1+
- m o (U, VVa) o;
Tr (Un V. 2T MQ.. ÜUn - -- -V,)' TT
1+8
We have
Zz2
E "TQTVIQQ
Tr (T M.
1
1 | Ir (V
Zza
Σ
Q
m
N
Lf V. MQ (U, -U,--VVV)) V",)" oi
Q U
m ml+0 6
1+ 1+ U. -V,
1 MQ
N
E
U D'D,,
m
1 +
Zz21
42

---

Published as a conference paper at ICLR 2024
Let the matrices
B m 1
U D²
Vm
and
CT = m
D2
U,Q Qm-
vm
5
Using the matrices above, have
Zy21 = m 1 E E
1
E [C
BC + CCB
1+
1+0
2
since Z221 is symmetric. We use the relations (B (B-C) ž and (B (B+C) C)" 20 to deduce the following relation
-BB" CCC 3 BC + CB BB" CC
From this relation, we obtain
E [B || + II).
12221 5
2(1 + 5)
where
BB" = mym
Q..
and
CC
Q E D Un. Qm. m-
vm
To get the Lemma, we prove that both BB and E || ||| vanish. From Lemma I.4, know there exists real K²2 0 such that, for all m, have
ViL Lg SK's
and
1 Qm ÜÜ ~,))
S2K¹s
Vm
Furthermore, from Lemma E.3, know
E [ O())
We conclude that
B
E
BB
|]
0
m
For |||| we remark that
Ü - VV. (U, - oV
Pr( 2 Pr
1+ (U. 7V.)"
TT - VV Ü,, ~V,)??)
2 2
1 1+ U, (U -V, VT)
Tr $ g Ü V QT MQ m Ü -V))
+ Pr
1 m L U UÜ, V.)
1 TT( - 7 Vn QT MQ Ü, VV) 2/11 )
1 1
43

---

Published as a conference paper at ICLR 2024
Since
[MQml is bounded from Lemma F.9, with similar proof than for Lemma K.5, we
prove that
Pr o UU
m
1
>
Ce max(1.t3)
for some C, c independent N, m. Besides, from the proof of Theorem 5.1, we also have
1 Tr((U, -
- -V,)
(Ü, -- V =0
as both |U,l|| and V. are upper bounded by 1, Tr AB) < ||| Tr(B) for non-negative definite
matrix B, and from equation 30 that bounds 1 Tr($ g). From Lemma K.5, we have
m
Pr (r m
-V. -. a a>t) SC'e me'' max(t,
for some C², e' independent of N,m. m. From equation 49 in the proof of Theorem 5.1, we have
81
mm
Combining all results above, we deduce that
E (221) E
max
D2l
~C Pr
max
D
3 dt 0
1
ISiSN
m
and therefore
E B|||CC
mm
Lemma F.8. Under Assumptions and 2, let Z2a E TR RRu be the matrix defined in equation 61 as
1
8 1 of (U, - -00n-~V,, vV.)
Z23
E Q QT,QQm (Ü, 1 V.
171
1 QT (.n ov
Then,
Zzs || = =0 (11
(mm)
Proof. Let the matrices
B. m - QQ,M@Qmi,, 7
Vm
and
CT = 1 _
Vm
1 1+ LUT
We decompose Zzs with its symmetric and skew-symmetric parts
N
Z23
B
1 1+4
1=1
B.C.T + C.B.
1
N
B.C. C.B.
E
E
1
2
2
44

---

Published as a conference paper at ICLR 2024
With the same reasoning on the symmetric part and the skew-symmetric part than for equation 41, we get for the operator norm
1
Z2
E
B
E
Σ
C.C
1+0
+ 6
We want show that both
E
BBB,"
and
E
Σ i= C
vanish.
We write
E
N
C
(6 u. -U - = -. - Vv,) ''o1)²
E
C.
E
(1 m
N
8 oF - (V,)) 27
- m n2
Vm
m
E
where D3 NxN a diagonal matrix for which, for all i [N], we have
Dal = U - (V) a
m
With similar proof than for Lemma E.3, and from Lemma E.1 and Theorem 5.1, we find that
11
(II o m
From Lemma 1.4, we know there exists real K¹2 > 0 such that, for all m. we have
fm EzEn Qm
and
1
Qm Ün, - [.,'' "3
< $2K¹
Vm
We deduce thus
= =0
(1(2
E
Σ C.T.
vm
We write E
EN Di=1
B,
N
E
B
B
E
Q L.,.... (U, -V.)" a (Ū, -", MT
m m
R
Q_ (ú, - a VV) M Q
With similar proof than for Lemma I.1, show there exists real Ki such that, for all m, we have
|@.|l KQ.
Let Am = Ú,, be the empirical transition model matrix defined in equation 14, Under Assumption 2, Am is invertible. From Lemma I.3, we have
Qm (Un VV.) $
Qm (Ū, VV. U. VV.) A
N (1 + 8)( A - VV,)" A
8 (1+ KQ).
< Emia
45

---

Published as a conference paper at ICLR 2024
From above and from Lemma E.9 that upper bounds ||QQ
conclude that
N
E
Σ
B
0
Lemma E9.. Under Assumptions 1 and 2, let Qm E < be the deterministic resolvent defined in equation 15, and let M be either any matrix with bounded operator M =Ü, 1 UNn Then there exists a real K >> such that, for all m, we have
[MQ m S K.
Proof. With similar proof than for Lemma 1.1, we can show there exists a real KQ such that, for all m, we have
1Q s KQ.
In the case where M is matrix with bounded operator norm, i.c., || KM have
IMQ.. S K
Otherwise, when M 0. z
Ün. we consider Å. = Ün - V.) -V,) the empirical transition
model matrix defined in equation 14. Under Assumption 2, Am is invertible. From Lemma I.3, have
N
|
NmQmil ml|
U 4 S
m
N
- A Ü. - oV
m m114
( A- Ün In 1Qm]
(1 xkQ).
Smin
G PROOF OF THEOREM 5.3
To simplify the notations, denote the matrix Q.. as the resolvent Q (X) (defined in equation 13), and we set (S). We define the matrices V E Rmxm and V E RPxp as
N
N m
and V
4ss.
+
We also add the notation + OH
which means that |A B|| Vm
(im
Under Assumptions 1, and 3, this section is dedicated to find an asympiotic deterministic version of the true MSBE(²) defined in equation 2 with similar approach than the one used in Appendix F for MSBE(8) θ). In proofs both Theorem 5.1 and Theorem 5.2, we constantly use the fact that [|Qm || is uniformly bounded by constant Kº >> O. We can also easily bound the operator norm of m L Qm, since the empirical transition model matrix A,, Ü, ~V,)" (equation 14) invertible under Assumption 2. Indeed,
1 A Ü,, - -E)' = A [I, XQmIll
Σ DgDDUnn UnQ Qm
(1 + *Kg)
Smin
46

---

Published as a conference paper at ICLR 2024
However, do not have such simple control for L. -y since Un ~ is not invertible until all states visited. Furthermore, from Corollary K.1.1, only O(ym) upper bound can be derived for J.M Es or Jp Es| Nonetheless, with the additional Assumption 3, we can bound Dr (Ip -PP Qm stated by Lemma G.I. Fortunately for us, the proof of Theorem 5.3 indicates that controlling the operator norm of m Dn (I, , Qm is sufficient.
Lemma G.1. Under Assumptions 1, 2 and 3, there exists K > O such that, for all m, we have
D= -1E K.
m
Proof. The main idea of the proof is to use similar reasoning than for this end, we use the triangular inequality, the decomposition Drr(Ip - PP) = (U, V
1 Am E. E |. To
m
Dx - P)) UU, >V,)", and Assumption 3 as follows:
Dx (I, -P)EEE m
1
Un(Un ~Va) E'S ESun
m
1 [Dx [Ip 7PP) U,, VV.'' E.E,,..
+
m
Un
mm
+
Un -V,))'''''
Dn [1s)] - PP Σ
EsU Qm
Vm
mm
Vm
From Lemma L.1, know there exists Kę Therefore, for the left-hand part Z1, we have
0 such that, for all m, we have 1Q KQ.
1 = U, [. XQm] 1 AKQ.
From Assumption 3, for the right-hand part Zz, have
1
U, (Un -VV,
E/ Vm
Dr [[|)] - P Σラ
mm
1 Es
UU, VV.) Dz [[s] - - 7P]
mm
0 (1),
since |Es|| = (()) from Corollary K.1.1. Furthermore, from Lemma I.4, we know there exists real K22 0 such that, for all m, we have
1
ا 5KQ
Em
We have | (()) which concludes the proof.
Assumption 3 may hold for sufficiently large n since [U, (U, VV, + Dx [4, -P as + do (Tsitsiklis & Van Roy, 1996; Nedić & Bertsekas, 2003). Indeed, Tagorti & Scherrer (2015)
has established that we can control (U,, VV.) D [T PP] with a sufficiently large
With the additional Assumption 3, we can now present the following result on the asymptotic Mcan- Squared Bellman emror.
47

---

Published as a conference paper at ICLR 2024
Theorem G.2 (Asymptotic MSBE). Under Assumptions 1, 2, and 3, the determinsitic asymptotic MSBE
MSBE 0) + mm
vn SSUnQm()))r +A,
Dr
with second-order correction factor
vz)) 1lQm
A
N Tm (m
where
Ap s| - -
D (TST -PP]:
As N,m, + do with asymptotic constant ratio N N/m, MSBE( MSBE 0.
Proof. We decompose MSBE 0) as
MSBE(() | + y 1 D. = || + [yP Ip 1
(64)
Ip - -0 P Es Qm
(65)
mvn
DT
||
(66)
2
Dx [pp - PP UU
(67)
my
=22
+
[p
7P] Σ E U, Q
(68)
my
De
=Kg
We want to find an asymptotic equivalent for both Z2 and Zg. From Lemma G.3, we have
2 x. D [Tp
E ZZ
P r. 0
nn
mm
For Z3, we have
1
2
1
Z3
mvn [4, Es
mmn
D2
From Lemma G.4, we have
E /aa
T
Q
QT
v A 4 SUM
n
n
1 v Tr (Ap
Os v 0o
SU, - VV, + +Vs))
11Q m 112
n
Tr 2 v Qm
+
Vm
With similar proof than for Lemma K.6 deduce that
MSBE () MSBE 0
as
Lemma G.3. Under Assumptions 1, 2 and 3, let Ze E defined in equation 67 as
7n
myn E D [T
Then
Z2 - 1 P
Vn
for Qm the deterministic resolvent defined in equation 15, and Vs E TRPXP defined in equation 21.
48

---

Published as a conference paper at ICLR 2024
Proof. As in equation 32, decompose the matrix Σ
ΣS Σ o.
where o; = (S" wi) E R for which R denotes the i-th row of W defined in equation 5.
Let Q-; R be the following resolvent
Q- (U, ~V)">> _
_U,, (U, >V,' U, +M
independent of or and thus w, From the Sherman identity (Lemma L.4), we have
1
Z2
E
T Dx [Tp s
myn
n
N
E
T Dr Ip - 7 P
myn n
N
x" D I, - P
E
myn
o U.Q (Un
Li=1
Let D NNN be a diagonal matrix for which, for all i [N). we have
D: = 5 U ~V,)"= a;
We replace + 1 m o (U, VV, o, by as following
Z₂
E
Σ
D n [ U
my n
1 +88
Zzi
F
D I P
my 71
0
+
o UU
Zz
We have Zzz vanishing since E
DI]
0
and from Lemma G.I. From Theorem 5.1, we
vm
have thus
Ze
E
T D [,
U, Q-1
+
myn
+
vm
1 N
1
TT
D
Vn m 1
mm
=" D [I, - UUU U 0 Vn
mm
Lemma G.4. Under Assumptions 2 and 3, let Ap E RPXP be the matrix defined in equation 21, and let Zg R be defined in equation 68
Z
E
T
nm?
Then
Z3 TTT QQ U U S
n
Tr Ap 1 - 2Un(Un 7V,) us + Us)
Q r 41
=
TF Q² Q
N
49

---

Published as a conference paper at ICLR 2024
where Qm is the deterministic resolvent defined in equation 15, 1 D2 R defined in equation 19, s E RPxP and θ RPx=" are defined in equation 21.
Proof. As in equation 32, decompose the matrix
E Eg
N
DS Es Σ o.
where 0; (S" w;) E R for which R& denotes the i-th row of W defined in equation 5.
Let Q- Ru be the following resolvent
1 UU, "V,)" _U, (U, V + m
Q
independent of or and thus w, From the Sherman identity (Lemmaa L.4), we decompose Z3
Z3
E
(69)
nun2
I
Q U o A UnQ
(70)
nime
QL 0
, UnQ
E
Ap
nmm
U, Q (U,
1+ m
U (Un Vnn oo
A,
(71)
Q O
u,
Ap
nm?
1 U.Q UU, -VV,)T
1 UU
UU,
iti
=2n
QL o Un
nm2 n
(1 m
(V,)",
(72)
From Lemma G.5, we have
I, Q U AsSsPsUUUC
1
Z31
n
1 N
Tr Ap
Os V 20s - 7V,) vsl)
110 m
rl
V 1
+
For the second term Z32, we have from Lemma G.6,
1/ TT(Apsss)
11 10mrle, +0 1
Z32
N Tr 12QU v Q
We conclude that
Zg 732 + 732
1 U.
"
Tr (Ap (Ap -V, VS + +vss)
1 1
# Tr U., Q² v
1
mm
50

---

Published as a conference paper at ICLR 2024
Lemma G.5. Under Assumptions 1, 2 and let Zaı R defined in equation 72 as
1
r "QL U.Q
731
nmm2
(1+ U.U - [V, (1 U -v,)))))
i=1jfi
Then
Z31
1 1 Tr Ap Os v 2 sOs(Un ~V v.)
1Q 1Q
O
V2Q. vm))
where Qm the deterministic resolvent defined equation 15, 1, 22 E R are defined in
equation 19, s E RPxP and θ 12xx= are defined in equation 21.
Proof.
Using the Sherman identity (Lemma L.4), we decompose Z31 as
r
Z31
UUQ (U. (.)
(1
i=1
jæl
1
nm3
1 1 U Un
j
1
o. Apo
nm
U (
jzfi
Zan
N
U o (U, - -VU U.Q
E
nm
(1 UV
7.12
We want to find an asymptotic equivalent for both Za11 and Z312 For Za12, we have
N
Q U (U U
Z312
E
r
3
(1 U0
i=1
j
Q QUTTTOTTUUA (U. U Σ Apoo)
nm
(1 LOJU o',
where Σ/' oo E RRN- for which W-i E 1(N-))xd depicts the same matrix than the weight matrix W defined in equation 5 without the jth row. Let Da12 E N be diagonal matrix for which, for all j E [N]. we have
[Daig]
m of U., - UN
1 Tr -V,n=VV.00__pp 1'' 2S Apo m²
DS' ApDs).
From Lemma G. we know there exists a real K, > 0 such that, for all m, we have D Es Qn < K,. Therefore, we deduce that
L (U,, - VV.) U M ST Σ Ap = 0(1).
51

---

Published as a conference paper at ICLR 2024
D = 0 (v))) (m
From Lemma K.2, we deduce that E
Therefore, we get
T U U Un Tr((U, - -V U ES 2 Apys)
Z312
B
nm
(1 Q [Vn)
N
U D Dz12l (
E
U.U -U, (V,) a,)² ?2"
j=1
N
Q
U m (U, -V,)) U3 57
Eg Apts)
TUT
B
nm
Q
Un + Tr -
Σ5 5r Σ3 Ap
E
mm
+
Vm
(73)
where the last equality is obtained since IE real K22 > O such that, for all m, we have
[1] Da1el] = O ((²) and since we know there exists
N m
ESUnQm
S 5Ka
and
1
Qm UU, -2 22K¹
vm
from Lemma 1.4. We replace
+ L -U, - ~V,) o, by 1 + in Za12 as following
m
1
Z312
U U.Q.
ST Eg' Ap
nm3
(1+
j=1
1
U O,
ES' Ap
E
nm3
(1+5y
(1 1..
mm
N
r
nm3
(1 + 8)2
=Zarn
p T. E nm3 (1 + 8)2
-2
+0
mm
where D' E NxN is diagonal matrix for which, for all j [N], we have
(1+ 1 U.
D = (1+
m
52

---

Published as a conference paper at ICLR 2024
With similar proof than for equation 30, can show Tr m Tr (r()s) is uniformly bounded under Assumption Combining [Tr(AB) < || Tr B) for non-negative definite ma-
trix and Lemma G.I, we have m² Tr((U, >V, Q SETTE Σ "ES Ap O(1). From all
these upper bounds, and since can shown that E| D'Il - O we deduce the second term, Z3122, vanishes and thus
Z:12
1 1
E I
QQ
Q
UVV) - Apts)
nm 2
+
Let Q-ij IR" nxn be the resolvent defined
1 UU, VV,) 'sT Es U,, XIn
Q-u
(74)
m
where Σ5 = a S) E ( for which W E IR ( depicts the same matrix than the weight matrix W defined in equation without the 8th and 1uh row. Using the Sherman iden- tity (Lemma L.4), the term 1 Tr((U, VU. ES Eg As) in Za12 can be rewritten
m²
1 m²
Tr - ~V, ES Eg As)
Tr
Σ(,, - V= o Apds
m
(U VV 0 Apps
Tr
m
14 o. U (Un VV,
inf
1
Tr
(Un - VV U. A
m² 1+5
$$
1
1
(Un - V. o Apps (0 of Q - Un_)
(Un
Tr
m² 1+8
U. Q -Unn-VV,) Vo;
itj
N
1
Tr (Unn VV. U. h sAApps)
m²
1+5
1
Tr (Un=>VV.'",,,"
DES' Apts)
m
1+5
where D NxN is diagonal matrix for which, for all E [N], we have
8- 1-8-LoTUn vy - VV.
m
From the uniform boundness of 1 (s))
1 from Lemma G.I, we have
k-
TrU(U, " Ap 0(1). Since the operator norm of [ of order O Vml) we deduce the second term vanishes, and thus
Tr((U, - VV. " ApAp$s)
m
N 1
Tr (UU, -V..)___u fsA
_ +0
m 1+8
m
53

---

Published as a conference paper at ICLR 2024
Applying Lemma F.4 and Lemma F.5, deduce for Z312 that
331
L N Tr((U, W
11
+0
111 mm
1- x Tr Q v Qm)
1 Tr T VV.
N
11
+0
Tr 2 mm)
Vm
Now, we want to find an asymptotic equivalent for Za11. We replace 1 1 m VV,)" oy by 1 + in Z311 as following
U
2311
E
nm2
1+ UHOUU (U,
i=1
j
N
Q T
Eg E
A r
nm
1 U (U, UU
j=l
N
E
U Σs ES Un ;r
nm3
1+8
j=l
2am
1
E
pT
T ]
U Σラ ST
5
Σ A
nmm
148
1 U,
where D E RNNN is a diagonal matrix for which, for all j E [N], we have
D, = 8- 1 -U.
We observe that
Dg' E
TT
ESEs Q",
Q U 3o
-_
m
m
1Q m
ES
U² ES'S
Qr
Q² U
It m
Q UT EJEs
o Q UT o oo (U,, ( (1+ - (U, - )
UT ES
m
m
Q J
Q UT E
Q 0 (U, ~V
E
UT T,
UT
Q_,TTT
m
1
UT Q m (U, V.
m
m7
54

---

Published as a conference paper at ICLR 2024
From above, expand Z3112
73112
1
U
E A
E
mm
1+0 6
U - Vv.''
Q
U E Es m
nm2
1+
-21122
N
Q
U -V00--VV,.... (.
U. (U, (Vn) p
nm 8) (1 m
=211122
N Σ
E
r A
nm3 1
m
=2,1125
We have Z31121 = 0 (+m)) since E ||| = (vm)) and from Lemma G.I. Subsequently, we rewrite Z31122
Za1122 nim 1 [r" Q U V Dan
with D31122 E. NxN a diagonal matrix for which, for all j E [NV] we have
Da1122] DDoJJ (U, V. QT S
L m 0 U (V,)
It can be shown that E. [[]
|||
and we can deduce Z31122 O (v)Lm Similarly,
mm
have Z31123 0 mm
Z3112 vanishes, and thus
Zsn1 Z3n11 +
| /m
1
N
A +0 ()() vm
E
T
Q
nm?
2=1
It remains handle Z3111 for which we have from the Sherman identity (Lemmaa L.4),
Za111 nmd
E
Q²
Σ3' U
8
N
1
E
Q² U oo
Ap
nm?
N
Q U. A
2 1+5
Lo (V))'
f=1 i
-2s111
U
3
1+
UU
1=1 1
Z2nn2
55

---

Published as a conference paper at ICLR 2024
Again, replace +
+ in Zsin following
Q u
Z311111
E
TUT
6
U -onn---V,)
j=1
N
1
E
A 19 T
nm3
(1+ 8)2
j=1 زg
N
Ap 1 (U, UU
Q U
+ nm? (1 (1+6)²
j=1 iデj
1 1
E
1 Q" UTAAAPUUUQQ-..
n m²
(1 +-2
1
E
TQ TQ AP
nm? 2 (1+6)3
j=1 +
1
Q 0 A 2 SU (Un QUn ",, Dir
E
3
3 (1 8)2
0 1K
j=1 ifj
E
r
T
Q USAAPWU..Q-
N
1
E
T
U D iT A ,r
2m
(1 8)2
j=1
N
Q
U DE Daun EU
mm (1 + 8)2
j=1
where Daum E N is diagonal matrix for which, for all i [N], we have
1 of App Q Q-, - VV))
Dsunk =
1 o U,Q V.)o
and Q- is a resolvent with the same law than Q-ij. With similar arguments that before, we can show that T. DI] and E Damm are of order and therefore
vm
Zann11
L TQT
S. +0
1 vml
By extending Lemma F.2 to the matrix Ap U.AAAAAPP sU,, and from Lemma F.4 we obtain
Zau111 - 2 T
1 (A
11 11
n - 1 (1.Q%
0
mm
56

---

Published as a conference paper at ICLR 2024
Following the same reasoning for Z31112, and from Lemma K.2, have
1
N
Q
Ap
Z31112
TUT
(1
j=1
1
B
I Q 1
U AU
nm3
+
8)3
j=1 iイj
+
0
N
1
(f Apb:U -kh)))
B
r" Q Q o.
nm2
(1
8)3
ifj
1
Vm
N
E
r rT T U.
(Vn)"
nm
+
8)3
j=1 iデj
1
+0
Vm
1
E
T Q
n
where the last equality obtained with a similar reasoning than for equation 73. From Lemma F.4 and Lemma F.5, we have
N Sss - VV.) vs) 1QmTl +0
(0(1)))
1
Z3L112
1 N
Tr V.QTT
vm
We conclude for Z3n1 that
Zs11
-
TT U v S SUNQu.
1
Tr [Ap O 1 - Os(Un - ~V,)" vsl) Tv.
QQ., m r (
n
11 1 P, N
+ 0
mm
and for Z31 that
Z31
T QT U...
n +
(Ap Vs (U, - VV,) vs))
Tr (Ap
11 m r 1,
1/4 Tr 4
0
mm
Lemma G.6. Under Assumptions and let Zaz E R. defined in equation 72 as
N
QT UT A
Zyp
Σ
T
nm?
UU
57

---

Published as a conference paper at ICLR 2024
Then
1
N Tr
=0 (0(
Z3
Q
n N Tr 2 Q
where Qm is the deterministic resolent defined in equation 15, 1 V2 RR are defined in equation 19, and Vs E IRPXP is defined in equation 21.
Proof. We decompose Z32 as
N
Z33
Tum
N
U.U
E
(1+ L (U, (U,
QUO U UnQ- A - (T(
E
Tmm
(1 U (U, o.))
Tr (sAA
N
Q 0. U U
1
m
E
m7
U (Un - ~V,)' ?
r
N
+
E
Qth U U 0 U, Qm PPAp::TTrrap
m
Za2a
We want show Z322 vanishes and find asymptotic equivalent for Z321- Let D322 NNN be a diagonal matrix for which, for all i E [N], we have
1 of Apo; Tr(PsAp). m
[D22],
m
We rewrite Zy22 as
Qm 1 (o Apo, Tr(osAp))
Zy22
i=
= E
Qu U Σ
D EunQm
From Lemma 1.4, we know there exists real K¹2 > 0 such that, for all m. we have
| EsunQum $ R2
and
1 Qm (Un ~V,)'" S2K¹
Vm
Using Lemma K.2 we show that
E[I
D322
||]
0
1
and deduce that
vm
Z
O
We want to find an asymptotic equivalent for Z Let D E R N be a diagonal matrix for which, for all i [N], we have
[221,, = 51+ (1+
58

---

Published as a conference paper at ICLR 2024
We replace + o U,
ov by + 8 following
Z321
m
UUUU (V))o,
N
1
Q"
E
(1 + 8)2
m
N
(1+ (1+0)=-(1+ -0 (1--))-(11_ )9)
+
Q
U
o UnQ
(1+6)
m
m
m
N
4s Un Q-1 + (1 + 8)2
Qm U D2 sm
m (1 +
8822
1
1+8 v
1
1H1
7m
The last equality is obtained since we can show that E Lemma E.4
[[]
Da21ll 11
= O
vm
We have from
1
E [[ 1
-
E
Q Q 0
vm
and from Lemma E55
1
1
(2
Z321
E3 Q
L Qm]
Q L Qm
1111
(Vm)
1
1+
Tr
4 2 1 1
N
We conclude that
N Tr(Ap
1 vm
Z32 n N Tr 2 v Qm)
1Qmrlé + +0
Lemma G.7. When all states have been visited, the empirical transition model matrix An Ú, - Vv)) = Un VV)) defined in equation 14 is invertible.
Proof. Le N and d' S - N be defined such that, for all E c(S:) and (S,) represent the number of times S, occurs in X,, and X,, respectively. If all states have been visited (y = p). for all in [p], we have thus (S,)) 0. The structure of /nU,, R indicates each column of Un is a one-hot vector, where its j-th element is 1 if the i-th state 8; of X, is Sy. Conversely, each row of VnU, has a j-th element one if the j-th state 8, of X,, S,. similar correspondence holds for VnV, and X From interpretations of U, and Vn, we deduce nU,,U mm and nV,VV E mm are diagonal matrices where the i-th element of its diagonal are c(S,) and cS,)) respectively. In the same way, nU,, Rmxx is matrix for which [nU, Vi is c(S, - +S)) which represents the number of times the state S, follows S, in Dirain- We are going to prove Åm is invertible by using the Gershgorin circle theorem show Am is strictly diagonally dominant, i.c., [[Am]sil Eitp |mllyl From the interpretations of U, and U, V.T. we have
[m IU YUn V c(S,) rc(S, - St) 0,
and
Am = - - V. = -70(S; +,)) < 20, Vi V
n
To prove Am is invertible it remains to show E, Am = E, (U, ~V > 0 for all i E [m]. Let E [m]] we have
c(S.)
c(S: + +S,) = (1 - 7) Σ
c(S.)
-UU.(Un-VVin -
>
n
n
n
which concludes the proof.
59

---

Published as a conference paper at ICLR 2024
Lemma G.8. Let A be the second-order correction factor of MSBE(0) defined in equation 20. all states have been visited then
L Tr U ApA U 22
X N
A
I1Qm (A)rl
n
1 1 N
Tr 2 (A)T
where Am Ün - (Vn) Un -- Vn) is the empirical transition model matrix defined in equation 14.
Proof. When all states have been visited, we have U, = Ün V, = V. and Σs = Eg. Further- more, from Lemma G.7, Am = Ü,, - -V,) (U V is invertible. We write
s = U.UnQmll
- (VV) ,
= =A [T, XQ
Using the equality above and the cyclic properties of the trace we conclude that
Tr Ap Os 20s ~V, - vs]
=Tr Ap U. AQ 12 I, - 1Q T "U= A
- -2A Un - (U, (U, (Va)" 40 -Ws]
2 A V A A=1)) ( T A -VV,) Us)
-ATr(APVss(0 V= A + 22 (ATr(APA,Tl) AAAAAAAA Qm UU, VV,) v.s)
-2 A
H EXISTENCE OF THE RESOLVENT Qm
In this section, we show that Assumption guarantees the existence of the resolvent Qm (A) (Lemma H. but also that Assumption 2 may be true in practice under certain conditions (Lemma H.2).
Lemma H.1. Under Assumption 2, for any > 0, the resolvent Qm defined in equation 13 exists.
Proof. From Assumption 2, we know that Vini (A(m))) > Emin > 0, and thus H ET) is at least semi- comi--psstive-deiiiie From the Min-Max theorem, we deduce that the eigenval- ues of Am EJ have nonnegative real-parts. Consequently, the eigenvalues of 1ú, W EgUn have nonnegative real parts since both (Ū, ~>,,"" EgEU and EgA. E share the same nonzero eigenvalues from the Weinstein-Aronszajn identity (Lemma L.6).
Lemma H.2. Let S - N and S N be defined such that, for all [m], c(S.) and ((S)) represent the number of times S, occurs X, and X',, respectively. If for all [m], c(S.) 2 ($.) then the symmetric part of the empirical transition model matrix A. (defined in equation 14) is positive-defintt.
Proof. The structure of Vnū,, E Ruxn indicates each column úf is a one-hot vector, where its j-th element is if the i-th state s, of X,, is Š5. Conversely, each row i of vnū, has a j-th element equal one if the j-th state 8, of X,, is S, A similar correspondence holds for /n and X
60

---

Published as a conference paper at ICLR 2024
From interpretations of Un and Vn, deduce that nU, U, mm and nV, VT mmxm diagonal matrices where the i-th element of its diagonal is equal to of c(S.) and (S,)). respectively. In the same way, nU, V E Rm*m of times the state S, follows $, in Dirain We want to prove H(Am) = Am+ is positive-definite by using the Gershgorin circle theorem and by showing ((Am) is strictly diagonally dominant, i... [Ammll Σitz (Am))lls From interpretations of Ü,,ü and Ü, V,,, have for all i [n]
m is matrix for which [ntū, VTTle les is c(S; + S,), i... the number
2
[H(Am))s: = (Ü,Ü (Ü, |= c(S.) 7c(S: + S.) > 0,
and for all i #
H (H(m))ss -y(ú, VJ i - - V. -
-r(( + S3) - -r(S + S:) < 0.
2
2n
To prove that H (Am) is Dositive-definite it remains to show that
> H (Am)ls)
>
H [((Am)) (mm)ls + (Am)a
341
Ün -(=
Ún ~T())T
Σ
Σ
>0
2
18
for all E [m]. Let [m]. have
-1ū,(0n-7in) c(S))
c(S + Sj)
(1 7) c(S.)
and
c(S.)
c(S) St) c(S:) - -xd
Σ
n
n
since c(S:) 2 (c((S)) for all [m]. We deduce for all i i [m] that
Ü Ün -2,))
Ú S.Ú -v,)
[l((Am)ss
+ Σ
> 0,
2
2
and thus H(A (AA) ) is strictly diagonally dominant and positive-definite
Remark 19. Conditions of Lemma H.2 may hold in practice. If Drrain derived from a sample path of the MRP, where 4/4 s for all [n 111,,, and if St depicts the distinct visited state corresponding to the last next state visited 8', in Draiin then we have c(S.) = c'(S.) (()))for for all i + and c(Si) = (Si) - For sufficiently large n, we may have c(Si) T which satisfies conditions of Lemma H.2. Similarly, conditions of Lemma H.2 are satisfied for the pathwise LSTD algorithm, where Drrai is perturbed slightly by setting the feature of the next state of the last transition to zero (Lazaric et al., 2012) to get c(Si) 2 (S)))
I TECHNICAL DETAILS ON THE RESOLVENT Qm
The objective of this section to prove that the operator norm of Qm (X) is uniformly upper bounded under Assumption 2. Indeed, controlling the operator norm of Q.. (A) is crucial for prov- ing the theorems in Section 5. When 7 O, which corresponds the supervised learning case on the reward function, the result is straightforward with Lemma L.7 since ET Σx. is positive- definite (Louart et al., 2018; Liao et al., 2020). In the RL setting, the conclusion is less straightfor- ward as the resolvent is no longer that of symmetric positive-definite matrix. This issue is further exacerbated by the lack of results the literature concerning the upper bounds for operator norm of resolvents of non positive-definie matrices. Lemma I.1 aims to propose solution for the RL setting under Assumptions and Proof of the widely used Lemma I.4 is also presented at the end of this section.
61

---

Published as a conference paper at ICLR 2024
Lemma L1. Under Assumptions 1 and let X and let Qm E Rux" be the resolvent defined in equation 13 as
1 (U, - ~Va) و AI
Qm
Then there exists a real > such that, for all m, we have
1 S K.
Proof. Under Assumption 2, the empirical transition model matrix A. Ü, - VVn) (equa- tion 14) invertible since the symmetric part of Am is positive-definite Let
Emin
0 <<<< < Amin
Emax 4
for Smin Smax defined in Assumption 2. We rewrite equation 13 as
(m) = - (Ün - ~vn)
" DE Mn
(ūn~
m Eイ'E + clm Un *In c(ū, v
=B.
To apply the Woodbury identity (Lemma L.3) on Qm (A), we check that both
B, = =\n, - e(On - ?V.)
and
1 - Σ gg + elm
Mm
-Ü,B, (Ün - -T
1 DT Dg + clm
-1
[MI. - -AAm -1
Åm
m
DS + elm m
1
[AA cLm
are non-singular, since 1 E + eI is non-singular. Given that H (A.)) positive-definit, Am has eigenvalues with positive real parts. Consequently, by the Weinstein-Aronszajj identity (Lemma L.6), (U, -V, has non-zero eigenvalues with positive real parts. As Emex deduce that the matrix B, AI, <(ū, V., T has eigenvalues with positive real parts and is non-singular. In order to prove that the matrix Mm, is non-
m 2
Fraxx (H(())) Re(Vmax(AA
singular, we propose to show x" Mm for all non-zero æ m Since
m D
least positive-semmiddfniiii the statement x Mn for all non-zero x E R. may be restated as
for all non zero æ E RM
T
XA m
-1
elm
x > 0
for all non-zen x E Rm
AA m
cI
x >>0
for all non-zero zero x E Rm x
H(A )x
x >
Vmin (H
By construction of Ú, and V., we have both | < and V |l S
We deduce thus
| || [ 7 v.) 7 <.
62

---

Published as a conference paper at ICLR 2024
Since H(Am') [Am' Am''m we deduce from Ostrowski's Theorem (Lemma L.5) that
Mmin ( (H(Am)
Smin
Vmin (H(A))))
||
Since e < Amin we have x² M > for all non-zero æ E I and thus Mm. non-singular: As consequence, we apply the Woodbury identity (Lemma L.3) on the resolvent Qm (A) to get
= - (Un Vn, M B, Qm (Un ~v,)" (
D c
Ü, Bn
Multiplying the equation above by B,, XIn c(ū, V on both sides, and after manip- ulating terms to isolate Qn on the left-hand side gives
1 X2
(m
Bn (Ün -V,) M
+ de (U, V.) (m)))( - Un)
- "V) (2) ~v,)
1
Bn (Ün MM
X2
+ Se( - ~V,)²
Am ES Σ + AI
Ün
m
1
+dc(Un - VT,
Σ Eg Am AIm
Ün
m
- VT)TT
Am ESS + Alm
Un(Un-
Applying the operator nom on the equality above, we find
[A)ll X2
A 2c + 2|| M,
+ 2hc
Am E XI
2he
Σ Am
Amm
m
m
1
+ 4e2
Am E/ Alm
171
(75)
since
|B, = ||I - -((ūn-VV)) s 2e.
From Lemma 1.2, we have
1 Am E + Apm
1 4
S
m7
2
and
- A
1
+ Am
< 4
m
Smin
63

---

Published as a conference paper at ICLR 2024
To finish the proof, find upper bound for M m decomposition of the positie-semi-dcfinin matrix identity (Lemma L.3) to rewrite Mm as
||- By denoting by Z" Z the Cholesky
ΣТ g + elm m 5
we reuse the Woodbury
1 L + cIm
M m
|m clmb
m
m z² + [AA -1 - =mlm 1-1
-1 -mm]
[M mm] [^A m cm 1 2[1A -m ZT
+ Im
2 [
From Lemma L.7,
2 [AA cm ΣT + mm
-mm
11
since (Z cIm] z²) is positive-semi--deiniit. and from Lemma I.3 we have
A
Emin
Besides.
Z 2 = V'max
EJ + eIm
17) $
m
We deduce for the operator norm of M that
2
| 1 $
+
+c)
+
e
Emin
e
Emin
Setting
A
min
Smin
for
min
Emin
and putting upper bounds of
26
Emax
Emar
M
ll.
A
T
Eg
AIm
T Am + AIm
into equation 75 give
+ ) + dc
1
8
1 (A)ll -
A +
+ x
+
d
Emiu
Emia
Smin
cf
F2
Smin
c
2
1
4
1
+
) + e
++++
c
+
Emin
Emin
e
Smin
e2
c2
Smin
Remark 20. From the proof of Lemma I.1, eigenspectrum constraints on the empirical transition
model matrix An in Assumption 2 ensure the resolvent Qm (A) is uniformly bounded.
Lemma 12. Under Assumptions and 2, let X > 0 and let Q (A), Q% E Rm be the following resolvents
(A) = Am ES + XIm
and
1
(*)(A)
Ay + AI
m
where A. = Ú.Úū - E mm is the empirical transition model matrix (equation 14).
Then, for all m, have
1 4 and II"h (A) <
1
S
X Smin
c2 Smin
64

---

Published as a conference paper at ICLR 2024
Proof. Since the symmetric part of the empirical transition model matrix Am is positive-definit under Assumption 2, the matrix A. is non-singular. We write thus
1
(A)lI
Am E gg +
Amm
m
1 m
E S + AAm!
A A
1 ولا g + AA Aumin (H(A Aumin (H(A))) I
||
A
Vmin (H(Am²)
The last inequality is obtained with Lemma L.7 since H 1 E = AA (H(A,:)) Im {m
2
is positive-semi-defiitee By construction of both Ün and Vn. we have | and |V || 1. We deduce that
|| || |Íū,(Ü, -v,)" 2.
Since H(Am') | (A..) A we deduce from Ostrowski's theorem (Lemma L.5) that Viin (A()))))
P'min (H (Am))
Emin 4
Am 1
Furthermore, from Lemma I.3, we have | S
We conclude that
Emi
4
Q (A)ll X
Smin
With similar reasoning, we can find the same upper bound for 11Q% (A)II-
Lemma L.3. Let Am ÜŪ, VT) be the empirical transition model matrix defined in equation 14, Under Assumption 2, for all m, we have
A 1
Emin
Proof. We rewrite Am as
A = [A Vmii (A(m))) Im]] Pmin (HmA))
Since the matrix (IAm Umin (Hl (Am)) Lm) positive-semii-defiiie,, we apply Lemma L.7 on A-1 to get
|| Vnin (Am))
Emin
Lemma L4. Under Assumption and 2, let x > 0 and ler Qm Baxn be the resolvent defined in equation 13 as
1 (Ū, - m
(m)
AI
Then there exists real K 0 such that, for all m, have
Estr (2) K
Vm
and
1 | Qm (m)( Vn.'''"''
< 2K.
Vm
65

---

Published as a conference paper at ICLR 2024
Proof. From Lemma L.I, we know there exists real K > 0 such that, for all m, we have [Q (A)ll K. Since the symmetric part of the empirical transition model matrix Am (U, ~V,'"" (equation 14) is positive-definite under Assumption the matrix Å. is non- and both ||U,,|| and || |Va]| are singular. Furthermore, from Lemma I.3 we have || S Eman" upper bounded by 1. We deduce that
- Qm ( m
Vm U
Qm Qm
m
(m) Am U, In 1Qm (A]l(
K(1 + K)
Emia
Similarly, we have
1
Q m (1))
(A)(( ", -V."= - -m)))
[L XQm(A)) (Ün - v., Am (Ü, (2)7
K)I
2 2/
Emin
ABOUT THE EXISTENCE, POSITIVENESS, AND UNIQUENESS OF 5
This section is dedicated to prove that the fixed-point solution d of equation 17 is unique and positive under Assumptions 1 and 2. This result is proven in the following Lemma.
Lemma J.1. Under Assumptions I and 2, for all m, let 8 be the solution to the fixed-poin equa- tion 17 defined as
N 1 Ün m + + (Ün V.)" -Nhn )
8= 1 Tr (U.-
m
Then exists, is positive, and is unique.
Proof. For ease of notations, we define the matrix B, = (Ū, ~ ÜÜ The proof is based on the use of Lemma L.8 on the mapping f 8 + Tr (.)) To apply Lemma L.8, we need to show i. f is positive on [0, oo), ii. f is monotonically increasing, ini f is scalable, and iv. admits Zo E [0, oo) such that 2o 2 f(xo). Following this plan, we are going to show first i., ie.. f(6) 0 for all 8 > 0. By denoting uy (.. the j-th eigenvalues of the matrix B, (m
66

---

Published as a conference paper at ICLR 2024
have
B + AIn 11)
N
1
by (B, Qm
=
Bn
m +
1m1+0 Bn + N11 [')
N
= (Bn)
(from the Schur decomposition of B.))
m
(Bn)
m I+0 1/j (Bn)
1
N 1
2y (B,)p (xs))))) +
2
I48 V/ (Bx). + X
(76)
Let A,, = = ÜŪ, 'Vn)' be the transition model matrix defined in equation 14, and Z be the Cholesky decompositon of Dg.- From the Weinstein-Aronszaji identity (Lemma I.6),, the matrices B, (Ü, VV,) T.)To o Ü, and Zd Am. share the same non-zero eigenvalues. Under Assumption 2, the matrix H ( Am Z) is at least semi--ositive--eefniii, which implies that non- zero real parts of eigenvalues of 2" Am Z are positive. We deduce that (e(v)(B.)) 2 0, for all j E [m]. As a consequence,
1
((0)
Tr Bn Qm)))
8 P2) (B.))² + 2 ABy(
/=1
N
148 Uj (Bn) +
(77)
NN
1u (Bn)) + (RRe(s,(B.))
m
1 U (B,) +
m
Th
To prove ii., i.e., f monotonically increasing on [0, oo), show the derivative f" of f positive on [0, 00). Let > 0,
2 BB))
f(())
m
N
I48
(Bn) +
N 1
(1+6)2
N 1
1+6 2 (Bn) +
N
(1+672
N
(1 (B.) 2+ +Au
1
N 1
1+5 U/ (Bn) + A
N
(1+872
N22
1
| (B.)) + 2x N 1
22 m +
|2, (B.)) x xB,)
m² (1 (1+8) 8)2
m 148 V/ (Bn) + A
N
m (1+6yT
N
N22
1 B
21
N
11 B
Re(y,
m² (1 112
m 148 Uj (Bn) A
N
m
(1)
N
(1+8)²
Re(wr(Bi))
/=1
N
I+6
4/ (B₂)
(2)
67

---

Published as a conference paper at ICLR 2024
Since real parts of eigenvalues of B,, positive, (1) is clearly positive. Since Tr(B,)) (Lemma J.2) and thus (2) is positive, we can conclude it.. We can use a similar proof for the scalability in iid., i.., af( f(ad), Va > 1. Let and >> 0,
1 Tr(BnQQmaa)) m
a((66) f(a6) a m
Tr (0)) -
(78)
Ir (r mm) (6) Qm((d)])
(79)
m
N 1
1
2)
Tr
am
Bn
In
Q
m (a8)
m
m
1+ aó
a(l+8)
a
(80)
N
1
1
Tr Tr(B,,Qm. (6) Qm (ao)
m m
1+ ad
a(1 +
(1)
>0
(81)
1
+
Tr Bn 1m (m)@ (ad))
>0
To prove in.. we can show that both (1) and (2) in equation 81 are positive. We prove in öi that for any 8' 8. Since ad 8, we also deduce (1) is positive. For
Tr (r. (, (2), we can write
Tr (B, m (8) (m()))
1i (B, (m))
14 (Bn)
148 My (Br) A
m 1y +1)
((m²3
N22
(1+ (1 + a5) + +x² Re((s +
|u3 (B,)) 12
m 1+ 1 ab |u; (v;(B..)p)
N #/11 (
2 a
Cj
+
j=1
> 0,
where
9
148 "B, + N 14 (B.) + +^)
In order to apply Lemma L.8, still need to demonstrate év., i.e., f admits 20 [0, oc) such that
Fo 2 f(xo). To prove iv., is sufficient to notice that if f is bounded, i.e., V5, f(6) I C. Let
6 > 0, we have
1 (m)) f(ō) m
Tr(( (..
m 1
TT (1) -1000~--,a) vv,²²)
s m
Tr Q (6) v..''1
2 S Tr( ()) Qm. (6)
n
O(),,
where we used for the first inequality [r < || Tr(A) for non-negative definite matrix A. uniformly bounded under Assumptions and (see equation 30). Furthermore, both ||Ù, || and ||Vi|l are upper bounded by 1 and, with a similar proof than for Lemma I.I, we can show there exists a real Kク > such that, for all m and for all E [0, oo), we have @ (6)l S Kg. Since all hypotheses required on f to apply Lemma L.8 are satisfied, apply this Lemma which concludes the proof.
The last inequality is obtained since 1 -T($5))
68

---

Published as a conference paper at ICLR 2024
Lemma J.2. We have
Tr((U- - & &v.) > 0.
Proof. Let A Ün(Ü,, -V,))" We denote by S(A) A-A" the skew-symmetric part of A.
We have
Tr((U, VVn) T 5 +v
- + (0
- + Tr
+ 3 + TT(35((A) + ( { 0.
- -A) 11
Lemma J.3. Under Assumptions 1 and 2, let be the correction factor defined in equation 17. 6 is decreasing function with respect N.
Proof. For ease of notations, we define the matrix B, = (V, and we denote by Qm the resolvent Qm (A). The derivative of å as function of N is denoted as ((N) and defined as
1 Tr( T,, (.....
('(N)
(1+5)
N B., B.. (1+0)2
m
For all N, we have (N( < since Tr(B, Qm. B,, Q..)
N Q., B,, Q..) (1+6)²
and
using
(1+6)
m
similar reasoning than for equation 48.
Lemma J.4. Under Assumptions and let the correction factor defined equation 17. decreasing function with respect X.
Proof. For case of notations, we define the matrix B, = -Ü, - -V,)"= and we denote by Qm the resolvent (A). The derivative of as function of denoted as 8' (A)) and defined
8'(A)
For all X, we have 8'())= using similar reasoning than for iri. in Lemma J.1.
K CONCENTRATION RESULTS
The following section dedicated to a set of concentration results used for the proofs of Theo- rems. Preliminary results yield concentration of measure properties for the random feature matrix Eg E Nxm, which stem from the concentration inequality of Lemma L.1 for Lipschitz appli- cations of a Gaussian vector. Essentially, the guideline of the proofs involves the following steps; given W;; jj (Wi),, for which W.j A"(0, and yp Lipschitz function, the normal concentra- tion of W is transferred to W. This process induces a normal concentration of the random vector aw $), for w = ((w) and w ~ (0, Ia), and the matrix Eg. This implies that Lipschitz functionals of a Š) or Dg also concentrate. As highlighted earlier, these concentration results have multiple consequences on convergence of random variables, and are traditionally employed in Random Matrix theory and in Theorem 5.1. We start by revisiting Lemma K. and Lemma K.2, which are derived from Lemma L.1 and that were previously introduced in Louart et al. (2018). Sub- sequently, we provide intermediary Lemma K.3 and Lemma K.4 to reach the principal results of this section articulated by Lemma K.5 and Lemma K.6, which are employed in proof Theorems. In the remainder of this section, denote by ||-||r the Frobenius norm of matrix.
69

---

Published as a conference paper at ICLR 2024
Lemma K.1. Let o :. R be a K K--Lipcchitz continuous function, let X &R be matrix, and let w = ((ū)) be vector for which yp + R is a K - continuous function and w (0, Ia). Let
to = |o(0)) + Ko K x
Then, for all t 4to, we have
Pr (1 ( x) 21 S Ce
2xg 1X12
for some C, > are independent of all other parameters.
Proof. The proof of this Lemma can be found in the first half of proof of Louart et al. (2018, Lemma 2), and is based on Lemma L.I.
Corollary K.1.1. (Louart al., 2018, Remark 2) Let X E Rdxm and let Ex OW X) Nxm be its random features matrix defined as in equation 5. For all t 4to, have
1 Σx
cmm
Pr
2t
CNN
2
m
where to = |o(0)) + X
d
From the previous Lemma, deduce the following key concentration result.
Lemma K.2. (Louart et al., 2018, Lemma 2) Let o IR + be a Ko-Lipschitz continuous functon,,,,,nn
let X dxx be matrix, and let <p( (p(i) be vector for which y R - R is Lii-sshhh
continuous function and i ~ NO Ia). Let A E mm be a matrix independent of w such that
||| KA. Then, have
1
Pr
oww X)T Ao X) m
Tr (AE [o(w" X)o(w² x) >t)
m
min x T
$
Ce
for to = 10000]+++ V KoK |X|, and c, C Th. independent af all other parameters.
Lemma K.3. Let f R + R. W + S(W) be K --iiscchitz function with respect to the Frobenius norm for which W = (W) the matrix defined in equation 5. Then, we have
for some C, c > O. Pr( ((() -[[[W)]] >
>1) s Ce K
Proof. The vectorization of W, ())(W) [Wn.. Wnd R is a Gaussian vector. A K KL-Lischitzz function f W with respect the Frobenius norm is also a Ky-Lipschitz function of vec(W) with respect the Euclidean norm. Applying Lemma L.1 gives
Pr(1s(W) - - B[S(W)]] > = Pr ( ([(((()))))) ( =[((p(W)) >1)sCe
S
x337
for some C, c > 0.
Lemma K.4. Under Assumptions 1 and 2, let 0, W E Nxd and let the resolvent
Qm L(ú. (Ū,. V.) T W) E U AI
defined as in equation 13. Let or E R. independent of W such that v ||o||| S VK, Ko > O.
Then
Pr m
1 - (.) >1s5ce
com -emt
m
for some C, independent of and N.
70

---

Published as a conference paper at ICLR 2024
Proof. Let the function f W + LoT (m) - ~V,,'a. We want show f is Lipschitz in order to apply Lemma K.3. From Lemma L1, we know there exists a real K > 0 such that, for all m and for any W, we have
Qm (WIl S K.
Furthemore, both |[,]] and ||V.|| are upper bounded by 1. Let H E Nxd, we have
If(W + H f(W)
o' U Qm ( + H) - Qm -
2 UTT W + H) - "in)" (W + HW H
m²
-
U.Q W + H) VV,'" Σg W ( + H) [g)
m
W + H) [w) E3( U W.) Qw) ~i,) o
+
T U.Q W + H) -V.)" Eg + [ (W + H)
m
[ W ÜU, - vi)=
TUTQ W + H)ŪU, - vin) [ + H)
m
Eg(W)]
Eg Egg (W)UnQ (w) - 7
< K
I.s Qm W + H) -Vn) Es( + H)J
Eg(W (W + H) [w)
Vm
Vm W W + H) - [g]
Vm Eg (W)U (m)
1
+ K
From Lemma 1.4, we know there exists real K' > 0 such that, for all m, we have
(W), SK'
mm
and
1
H) $2K'.
Qm (W
vm
From those results, we conclude the Lipschitz continuity of since
If(W H) f(W) 8K.KK'
Vm Σ W + H) Es(W))
8K.KK
Eg(W + H) -5s(w))
mm
8K,KK'K
Vm HS
SK,KK'Ko Vm
Tr THHSSTTH' HT)
8K 8K,KK' Vm
|||| H
71

---

Published as a conference paper at ICLR 2024
The last inequality is obtained because [Tr(AB)
|B] Tr(A) for some semi weli--oosiiiefiiiieeee
matrix A. We prove that Lipschitz with parameter
8k. KK' Ka ||S||, and applying Lemma L..1
m
gives
1 Q Nh)" (. - ~Va) - (1
Pr
m
S Ce 2 "OX2x>XPK3RC k311s11
for some C, c > 0 independent of other parameters.
Lemma K.5. Under Assumptions I and 2, let Q E ER be the resolvent defined in equation 29, let wi NO, Ia) be a Gaussian vector independent of Q_, and let - R be real 1- Lipschitz,functi function. Then
Pr owo (00, - 0S wi)
1 Tr (Ü.E(Q-I(Ü,, vv,) Blo w:)o Si1) >1)
S Ce -mm max(t?.p) .t)
for some e independent of N, m.
Proof. We can observe that
Pr
σ (w) SUÜ,Q- 7(5") ws)
m
(Ü,EIQ ((0, ( wi)o S1]) >1)
m
1
Pr
r (w ( S) Q- (, o
m
<ww S) y V.) (w"" 5) >
m
+ Pr
ow
(U, - V., T
m
Bo w. ) (w) 5)])
> t
>
m
From Lemma I.1. there exists a real K such that, for all m, we have I| < K. S Š) -,, T
Besides, both |!Ox2 and | are upper bounded by 1. We thus bound the probability of the right- hand part with Lemma K.2
Pr
Loww"
m
[U, ~V,)) B(o w.) Si1) >t
(83)
m
min x
S Ce 2x 12
for to (o(0))
m K2 Ko |11, and C R independent of all other parameters. Let define the real K' > 0 and let Agr be the probability space defined as
Ak {w Rm | $\ll < K' Km).
72

---

Published as a conference paper at ICLR 2024
From Lemma K.I, we bound the second term Pr(Ak) as
Pr(Ake = Pr([[lo(w" $) K" (m)) S CCe
for some c', C" > 0 independent of other parameters, Conditioning the random variable of interest with respect to Ag and its complementary Axr gives with Lemma K.4
Pr ( lw S) - vV.) o (( olw" S),,,E(Q-I(U, - vVn) o 5) >t
m
Pr Pr()-a(w' 5) S vV) ow
1 oww U U.E (U, n v., ow $) >t tn Ax.) + Pr((Ak))
km
CCee CCe अह
(84)
where C² > O. Combing both equation 83 and equation 84 with equation 82 gives
Pr -oww Š) - -tx)
1 Tr ÜnE[Q - -Voo) Elo (w:)oww $i1) 21)
(85)
d'm² + +Ce 2x 222 min 2taig22iak) + C
d'mx
< Ce 2x2 11
Lemma K.6. Under Assumptions / and 2, let 0, W E Rxd, and let the resolvent
Qm(W) [1 (Ū, (W)) (W)U, AI
defined as equation 13. Let u E IR such that |||||| S Ku K 0. Then
X2 T (w) Qm (W)u X² [W)
(W) Q (W)Ju >1) < Ce Co
Pr for some C, c > O independent of m. and N.
Proof. Let the function f: W X2 u Qm "T"Q... (W)u. We want to show f is Lipschitz in order to apply Lemma K.3. From Lemma 1.1, we know there exists a real such that, for all and W, we have
1 WW] < K.
Furthermore, both ||Ù,,| and | are upper bounded by 1. Let H E Nxx we have
2
V[W H) S(W)
T [Q. W H (W H) Qm (W)² Qm (n))
n
Qm (W + H) Qm H) Qm (w) (w))
n
X2
Qm + H Qm (w)) Qm (W)u
+
73

---

Published as a conference paper at ICLR 2024
For (1), we have
x
T Q (W + H)" Qm + H) - Qm (W)) :z
n
x 1 u Qm W + HH (W - ( < + + H
[g(W) Eg (.
X² 1 u Qm (W + Q m (W H)(Ú (W) + [ + +H) [g(W)
[W H) - [g((W] (S(
X 1 u²
u''Qmi Qm W H Qm (W H) En) ( H) {
5 (W H
n
Eg(W)) (m
X2 u 2=Qm ( + H (W H) VV,) (W H))
n m
Es(W)] Σg (W)UnQQ(W))l
X2
1
K2KK 1
Vm Qm + HŪ - ~V,) Es H)²
Es(W (W + +H) Es Es(W)]
vm
2x
||| ا
1 vm
+
K²K2
Eg + H [w)
Eg Eg( (w)
n
Vm
From Lemma 1.4, we know there exists real K' such that, for all m, have
Σ W SK'
mm
and
Vm Q m W + H) - - + - s $2K'.
1
From those results, we conclude for (1) that
X² n Qm (W H)
Q W H) (w) TT
4X2K2K2K"
1
Es( (W H) [w)
n.
mm
4X² K'
1
WW H) Eg(W))
1
HSI
mi
K2K2K2K'K
Tr (HSST
Ra/m
KX
| H
T/m
The last inequality is obtained because [T(AB) < [B| Tr(A) for some semiipositivv--deiiiit matrix A. With a similar reasoning, we can prove for (2) that
X² u Q (W IW + H) Qm w)) Q W)
4X22233K'S ||S H|
nym
74

---

This Lemma is Published as a conference paper at ICLR 2024
We thus prove that f is Lipschitz with parameter gives
8A²K² K'K',, Ka
||]] and applying Lemma L..
nym
x² _n u Q (W)u
A u "'I (m))m()))))) (W))) =t)
Pr
S Ce R
for some C. c 0 independent of other parameters.
L INTERMEDIARY LEMMAS
Lemma L.1 (Normal Concentration). ((Ledoux, 2001, Corollary 2.6, Propositions 1.3, 1.8) or (Tao, 2012, Theorem 2.1.12)) For E N, consider y the canonical Gaussian probability on I defined through its density du(w) = (2T)- ------ =11w1? and f : R. + R LLi---ippcchitfffncttii Then
(f15-) fdu 2 2t)) =Ce -
(86)
where C, 0 are independent of dl and Tng- Lemma L.2 (Resolvent Identity). For invertible matrices A, E Raxx,
- B A A)B
Lemma L.3 (Sherman-Morrion-Woolldl
Matrix Identity). (Horn & Johnson, 2012, Theo- rem 0.7.4) Let A E |R be non-singular mutrix with a known inverse A-1; let M A+UCV, in which U E Rkxn,
V E Bank and Ck non-singular. If M and C-1 + VA- are non-
singular then
AA (A+UCV) = A-1 A A (C- VA- VA-!
(87)
In particular (A + AAUUV--U
A (L, + +VA- and V (A+UV)-
(I, + +VA- VA-!
Lemma L.4 inverse A A-1,
Formula). Let A E Rax be non-singular matrix with known ; let M = A uo,, in which u, v E RR. If M is non-singular and 1 + aT u u
then
A uuv A-1
(A + uuuu
A
(88)
1 + o. A A-1u"
In particular, (A wv= -1 I+o A-uu and v" (A + uv²)
-1
TTA ATA
u
140"
an extension of Lemma 1.3.
Lemma L.S (Ostrowski's Theorem). (Horn & Johnson, 2012, Theorem 4.5.9) Let A.S E Rax with Hermitian and nonsingular. Let the eigenvalues of A, SAST, and SST be arranged in nondecreasing order. Let σ1 2 On. >> 0 be the singular values of S. For each k E [n] there is a positive real number 0g E [o". such that
vs(SAST) (A)
Lemma L.6 (Weinstein Identity). For A E mmx B REER RaXM and À E R (0).
det(AB - Am m- det AIx). follows that the non-zero eigenvalues of AB and BA are the same.
Lemma L.7. Let A E RRxx and 0.
[IA + XI,) -11
if and only if AAT + +(A+ the Hermitian part (AA) A+ is semi pestiv-isit we have
)
)²"a is positive definite. In particular, for matrix A gaax whose
+ I AI,) 1
75

---

Published as a conference paper at ICLR 2024
Proof.
(I + AI,) 112 = Umaz
(A+) 11 (A+ (A+
([(A+ (A² + +*In)]
Vmax
(89)
(AA" + +1(++ A²) IZI,)) -1
Vmar
Min (AAA + + A + +
where maa () and Vmin denotes the maximum eigenvalue and minimum eigenvalues of
matrix B. Since A is positive-definite the matrix AA + A(A + A is semi-positive-define and
has positive nonzeros eigenvalues. Therefore, Vmin (AAT T + A(A + AT) + I2I)) X² and (IA + AI)) +
Lemma L.8. (Yates, 1995, Theorem If a mapping f : :00 o0) [0, 20)
is monotonically increasing, i.e x 2 x' f(x) 2 f(x'),
is scalable, i. Vo af(x) ((xx).
admits no E o0) such that zo 2 f(xo),
then f has unique fixed-point.
Lemma L.9. Let A Rmxx and B E Raxm If AB + XIm is invertible, then
AB A A N
Proof. We have
A A BA + AI = AB AI A
Since both AB and B A share the same non-zero eigenvalues from Lemma L.6, we deduce BA + AIn is also invertible. By multiplying the equation above with both the inverse of [BA + XIn] and
[AB + Am we get
AB + A 1- A = A[BA AL.
76


Reviews:
[{"review_id": "88Fq8l27gf", "reviewer": "Reviewer_xcHJ", "summary": "In this work the authors provide a theoretical analysis of regularized LSTD in a setting where the number of parameters of the value function approximation N and the number of distinct visited states m go to infinity with a fixed ratio N/m. The authors do so by relying on random matrix tools, in particular using features of the form sigma(WA) where W is a random feature matrix (Nxd) applied to any set of d-dimensional states A. The connection to neural networks is via this simplification via random matrices and can be likened to an N-dimensional single layer network, where the simplification is less objectionable due to the asymptotic regime.\n\nIn this setting, with some minor assumptions, the authors go on to show that the asymptotic empirical MSBE can be related to the two-norm of the resolvent applied to the reward vector, plus a second order correction term, and that the empirical MSBE approaches the asymptotic almost surely. The authors then show, including empirically for a small number of examples, that it is the second order term that contributes to double-descent behavior. A similar story can be shown for the true MSBE, albeit with a more complicated term and second-order factor.\n\nThe authors also show that the empirical variant reduces to a similar approach of Louart et al. for supervised learning when gamma, the discount factor, goes to zero. Additionally as the number of features, equivalent to the width of the network, or the regularization term increases the correction factor diminishes (thus leading to less prominence of the double-descent behavior).", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a clear, concise (as much as possible) presentation of their results. They relate the work to the literature well, particularly how this complements and extends work from the supervised learning literature. Similarly the effect of increasing the regularization strength or width of the \"network\" is beneficial. The empirical experiments are similarly good in explaining the effect of the theoretical work.", "weaknesses": "I don't think the paper has particular weaknesses, however I would ask what the practical implications of this work are? This is less a comment on this work and more a question directed towards the theoretical analsysis of double-descent in general, in that the random-feature assumption while seemingly valid asymptotically departs from how such work might be used in practice. Note that the authors do leave an extension to \"deep\" neural networks for later work. Similarly the authors discuss policy evaluation as a next step.\n\nOverall I would like to more discussion of how to place this within the \"standard/practical\" setting, although I do admit that actually attacking that problem is beyond the scope of this already long paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "0Krr5dZOCt", "reviewer": "Reviewer_7TMf", "summary": "The authors investigate a double-descent phenomenon in RL, where the mean-squared Bellman error (MSBE) initially decreases as the number of learnable parameters $N$ increases, then increases when $N$ equals the number of distinct visited states $m$, and finally decreases again in the overparameterized regime as $N \\to \\infty$. An analogous effect has been previously identified in supervised learning but not RL. The authors focus their analysis on least-squares temporal difference (LSTD) with random features to simulate a wide 1-layer network without needing to model the complexities of feature extraction. Analytical expressions for the MSBE as a function of the ratio $N / m$ and the $l^2$-regularization coefficient $\\lambda$ are derived, which indicate a spike in MSBE near $N / m = 1$ and $\\lambda \\approx 0$. This behavior is verified empirically by LSTD experiments in small environments, such as Taxi. Notably, it is experimentally shown that the peak at $N / m = 1$ disappears when either $m = |S|$ (the state space is covered) or $\\lambda$ is increased.", "questions": "1. Can the norm term in $\\bar{\\text{MSBE}}(\\hat{\\theta})$ (Theorem 5.3) be simplified to $\\|| \\bar{r} + (\\gamma P - I) \\frac{1}{\\sqrt{n}} \\frac{N}{m} \\frac{1}{1+\\delta} \\Phi_S U_n \\bar{Q}_m (\\lambda) r \\||^2_D$, i.e., factoring out $\\gamma P - I$? Or was it left expanded intentionally?\n1. Why was recursive LSTD used for the experiments? Since only the final weights are needed, would it be more efficient to just sample data from the behavior policy and then explicitly calculate the TD fixed point like $w = A^{-1} b$?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- I really like the idea of studying LSTD with random features to model neural networks. It is a useful abstraction to remove the noise of TD updates and other complexities of online learning like state visitations, changing features, and potential divergence with nonlinear FA.\n- The mathematical analysis is excellent and highly significant. The results are clear and the remarks after the theorems provide helpful interpretations for them. The math is correct to the best of my knowledge (although I only checked a small part of the appendix). It is apparent that a lot of thought and effort was put into this paper.\n- The experiments clearly demonstrate the hypothesized double-descent phenomenon, and also answer focused questions like to what extent regularization or changing the discount factor can change the double-descent peak. The analysis is good and connects the experimental observations back to the derived terms in the theorems.\n- The paper organization is great. The contributions, related work, and preliminaries/system model are explained well and help ease the reader into the main results.", "weaknesses": "- I wonder if the observed double-descent behavior may be specifically due to the analysis of MSBE rather than some other learning objective, like the mean-squared value error (MSVE), the error relative to $v_\\pi$. For example, it is known that TD methods that optimize MSPBE can converge to a solution far away from the minimum MSBE, which may explain the large peak around $N = m$. However, if we measure against MSVE instead, would we still see this? I imagine that if we have a set of features with some MSVE, and then add more features, we could just set those corresponding new weights to zero to preserve the MSVE. This seems to imply to me that the MSVE would be monotonically non-increasing as $N$ increases, although I am not sure if I am missing something. Perhaps the authors could better justify their choice of MSBE in this regard.\n- The paper says that only one random seed (42) was used to generate the training data, so I have to guess that only one seed was used to generate the random features as well. Since the MSBE is highly dependent on these “network” features, it is impossible to tell from just one trial that the double-descent observation is a common phenomenon over the distribution of possible feature initializations. It would be helpful to show the results averaged over a number of different networks, with confidence intervals shown.\n\n**Minor:**\n- On the start of page 4: “Deep RL can be cast as a special case of LFA, where the neural network learns both the feature vectors and the parameter vector.” While I see what you mean here, I personally found it confusing to describe deep RL as a special case of linear FA, since deep RL is nonlinear FA. I think this could be reworded for clarity.\n- Also page 4: “Linear TD methods are LFA methods that minimize the MSBE” but then later in the paragraph it is correctly noted that TD methods “minimize MSPBE rather than MSBE.” The first part should say something like TD methods *try to* minimize the MSBE, but actually minimize MSPBE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "BWvtx92Dmg", "reviewer": "Reviewer_a6mC", "summary": "This paper examines the behavior of the (regularized) LSTD estimator within the random feature model and the on-policy evaluation context. It investigates a doubly asymptotic regime in which both the number of parameters and the number of distinct visited states tend to infinity at the same rate. A double descent phenomenon is observed between the empirical mean squared Bellman error (MSBE) and the population MSBE. The authors derive analytical equations for both the asymptotic empirical MSBE and the asymptotic population MSBE. Based on these derivations, they demonstrate that the double-descent phenomenon diminishes as either the regularization increases or the number of distinct unvisited states decreases. Empirical experiments corroborate the theoretical findings.", "questions": "Questions:\n1. Why are the two asymptotic quantities the parameter number and the number of unvisited states as opposed to the parameter number and just the sample size?\n2. What are the technical difficulties when studying regularized LSTD for policy evaluation as opposed to regularized least squares for the regression case ($\\gamma = 0$). The text mentions that there is a lack of positive definiteness in the LSTD matrix -- is this the only difficulty? How is this difficulty overcome?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The setting provides a clean model to study TD methods in the over-parametrized regime, and the results are also fairly clean (at least conceptually, despite some of the linear algebra expressions being messy). The findings clearly demonstrate a theoretical over-parametrized double-descent regime for LSTD in this asymptotic setting, which to my knowledge, is a novel and interesting finding. I have not checked the proofs in great detail but from what I have seen they do check out. The experimental results, despite only looking at simple environments, appropriately confirm the theory.", "weaknesses": "One weakness is that the double descent behaviour is said to be related to the behaviour of the correction factor $\\delta$ but I do not think that this is demonstrated analytically. What is precisely happening to \\delta when N=m, or alternatively what is happening to the difference between the empirical MSBE and the true MSBE? This is one of the main selling points of the paper so it would be good to expand on this. \n\nOther than that, there are a few writing nitpicks, which I outline below. \n1. \"We use the regularized LSTD algorithm, [...] because it converges to the same solution as other TD algorithms.\" This is true without regularization, but is it true with regularization?\n2. \"Theoretical studies of TD algorithms often focus on asymptotic regimes, in either finite or infinite state space, where the number of samples n -> \\infty while keeping the number of model parameters N fixed\". The authors likely meant that it has not been studied what happens when parameters and samples both converge to infinity, but this sentence also implies that only asymptotic analyses of TD exist (as opposed to finite-sample), which is not correct. \n3. Section 3 \"Notations\" paragraph: what is the \"Euclidean norm\" of a matrix? Does the authors mean the spectral norm or the Frobenius norm?\n4. Items 4 and 5 in the \"Contributions\" paragraph both repeat that the correction terms vanish when the regularization increases and/or the number of unvisited states go to zero.\n5. The notation for feature matrix $\\Sigma_S$ is unfortunate since it clashes with typical notation for covariance matrices. Is there a reason not to use the more conventional $\\Phi$ notation for this matrix.\n6. Section 3 \"Linear Temporal-Difference Methods\" section: the Mean-Square Projected Bellman Error is undefined.\n7. Section 4.1. For the sampling paradigm I do not think the authors literally mean $(s,s') \\sim \\mu(s) P(s,s')$. This latter expression would be the marginal probability of observing s' only, and is just a number (not a distribution one can sample from).\n8. Section 4.1. \"We consider the on-policy setting, where $D_train$ is derived from a sample path of the MRP or its stationary distribution $\\pi$. These are very different (one is i.i.d.), are both truly considered?\n9. Some vector norms are indexed by $\\pi$, but many other norms are not indexed (e.g. Equation 8, 9,10). Is this a typo, or are all unindexed norms the Euclidean norm?\n10. Relatedly: the closed form for the LSTD estimator is defined without the usual diagonal D_\\pi, which implies that the algorithm performs regression on the Euclidean norm rather than $L_2(\\pi)$ (one can compare with the more classical weighted version e.g. in Amortila, Jiang, Szepesvári ICML 2023). In this case the LSTD estimator is different from the usual weighted one, can the authors discuss whether this is a meaningful difference and/or whether the results would hold for the weighted estimator?\n11. \"Under the assumption that all states are visited $\\hat{MSBE}(\\theta)$ converges to $MSBE(\\theta)$ with probability 1, as the number of collected transitions $n \\rightarrow \\infty$ (Bradtke & Barto, 1996).\" I do not think that this is shown in that paper, which instead deals with the projected bellman error.\n12. Typo in Assumption 3: should be O(1/\\sqrt{m})", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "Vmx1Kd9MCX", "reviewer": "Reviewer_jHhA", "summary": "This paper studies a theoretical model (based on random features) of temporal difference learning of the value function in a markov reward process using neural networks with one hidden layer. The key high-level parameters studied are the number of parameters $N$ in the hidden layer, the number of distinct states visited $m$, and the $\\ell_2$ regularization parameter $\\lambda$. The paper focuses on the regime where $N,m \\to \\infty$ but the ratio $N/m$ remains constant. Under suitable assumptions, the main results of the paper give numerically solvable equations for computing the asymptotic mean-squared Bellman error (both the true error, and the empirical error observed during training). These results then imply that the double-descent phenomenon occurs in this regime i.e. that the true mean-squared Bellman error decreases when the ratio $N/m < 1$ (the under-parameterized regime), has a large spike at $N/m =1$ (the interpolating regime), and then further decreases when $N/m > 1$ (the over-parameterized regime). Furthermore, the paper shows that increasing the regularization parameter $\\lambda$ mitigates this double-descent phenomenon, with sufficiently large values of $\\lambda$ eliminating the spike at $N/m =1$ altogether. Empirical results on simple reinforcement learning tasks are in very good agreement with the theoretical predictions.", "questions": "As discussed in the weaknesses above, is there something additional that can be said about how studying the double-asymptotic regime where $N/m$ is constant can give insights into the behavior of deep neural networks? In particular, the NTK and mean-field regimes may allow for theorems that apply to deep neural networks, but perhaps with somewhat unrealistic levels of over-parameterization. Is there any similar statement that can be made in this regime? Or is there some fundamental trade-off where the realistic parameter choices in the double-asymptotic regime preclude results applying beyond a single hidden layer.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper gives strong theoretical grounding for the occurrence of the double-descent phenomenon in temporal difference learning.\nFurthermore, the results demonstrate that double-descent can be mitigated by sufficient regularization, which could potentially have practical applications.\nFinally, the empirical results in the paper demonstrate that the theoretical predictions are sufficiently accurate (in terms of the rates at which the predicted quantities concentrate) that even in small examples there is good agreement between theory and the empirical measurements.", "weaknesses": "The paper gives strong results for the random features model, but it is somewhat unclear how practically relevant these are.\nWhile it is typical to study such models in order to prove high-level statistical properties that may be relevant to practical neural networks, it would be nice to have some discussion of when/whether these results might be relevant.\nFor example, when proving results in the NTK regime, it is actually true that even deep neural networks of sufficient width will behave as predicted given appropriate random initialization. Of course, the NTK regime requires a width that is unrealistic and thus does not necessarily capture the practical dynamics well. The mean-field regime is designed to (at least somewhat) mitigate this issue with the NTK regime.\nIt is unclear from the discussion in this paper precisely how the double-asymptotic regime fits-in to this picture with regards to modelling deep neural networks (as opposed to single-hidden layer networks).\nSuch discussion of the relevance of the double-asymptotic regime to deep-neural networks would also help to clarify the novelty of this work when compared with prior work on value learning in the NTK and mean-field regimes (e.g. the cited 2022 paper by Agazzi and Lu).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)