Temporal-difference learning for nonlinear value function approximation in the lazy training regime
Authors: Andrea Agazzi
Jianfeng Lu
Venue:  (2020)
Keywords: deep reinforcement learning
function approximation
temporal-difference
lazy training

Abstract: We discuss the approximation of the value function for infinite-horizon discounted Markov Reward Processes (MRP) with nonlinear functions trained with the Temporal-Difference (TD) learning algorithm. We consider this problem under a certain scaling of the approximating function, leading to a regime called lazy training. In this regime the parameters of the model vary only slightly during the learning process, a feature that has recently been observed in the training of neural networks, where the scaling we study arises naturally, implicit in the initialization of their parameters.  Both in the under- and over-parametrized frameworks, we prove exponential convergence to local, respectively global minimizers of the above algorithm in the lazy training regime. We then give examples of such convergence results in the case of models that diverge if trained with non-lazy TD learning, and in the case of neural networks.

Under review as a conference paper at ICLR 2020
TEMPORAL-DIFEERENCE LEARNING FOR NONLINEAR VALUE FUNCTION APPROXIMATION IN THE LAZY TRAINING REGIME
Anonymous authors Paper under double-blind review
ABSTRACT
We discuss the approximation of the value function for infinite-horizon dis- counted Markov Reward Processes (MRP) with nonlinear functions trained with the Temporal-De Cemporal-Difference Difference (TD) learning algorithm. We consider this problem under a certain scaling of the approximating function, leading to a regime called lazy training. In this regime the parameters of the model vary only slightly during the learning process, a feature that has recently been observed in the training of neural networks, where the scaling study arises naturally, implicit in the initialization of their parameters. Both in the under- and over- wver-parametrized frameworks, we prove exponential convergence to local, respectively global minimizers of the above algorithm in the lazy training regime. We then give examples of such convergence results in the case of models that diverge if trained with non-lazy TD learning, and in the case of neural networks.
INTRODUCTION
In recent years, deep reinforcement learning has pushed the boundaries of Artificial Intelligence an unprecedented level, achieving what was expected to be possible only in a decade and outperforming human intelligence in a number of highly complex tasks. Paramount examples of this potential have appeared over the past few years, with such algorithms mastering games and tasks of increasing complexity, from playing Atari to learning of Go (Haarnoja et al., 2018; Mnih et al.; 2013; Silver et al., 2016; 2017; 2018). Such impressive success would be impossible without using neural networks to approximate value functions and or policy functions in reinforcement learning algorithms. While neural networks, in particular deep neural networks, provide a powerful and versatile tool to approximate high dimensional functions (Barron, 1993: Cybenko, 1989; Horiik, 1991), their intrinsic nonlinearity might also lead to trouble in training. in particular in the context of reinforcement learning. For example, it is well known that nonlinear approximation of the value function might cause divergence in classical leiforel-difference learning due to instability (Tsitsiklis & Van Roy, 1997). Several algorithms have been proposed in the literature to address the issue of non-convergence (Bhatnagar al., 2009; Maei & Sutton, 2010; Riedmiller, 2005; Sutton et al., 2009a;b; Szepesvári, 2010), while practical deep reinforcement learning often employs and prefers basic algorithms such as temporal-diffee -ifffrrene (Sutton, 1988) and Q-learnig (Watkins, 1989) due to their simplicity. It is thus crucial to understand the convergence of such algorithms and bridge the gap between theory and practice.
walk and beating world grandmasters at the game
The theoretical understanding of deep reinforcement learning is of course rather challenging, as even for supervised learning, which can be viewed as special case of reinforcement learning, deep neural networks are still far from being understood despite the huge amount of research focus in recent years. On the other hand, recent progress has led to an emerging theory for neural network learning least in the regime of over-parametrization, including recent works on mean-field point of view of training dynamics (Chizat & Bach, 2018a; Mei et al.. 2018; Rotskoff al., 2019; Rotskoff & Vanden-Eijnden 2018; Wei et al., 2018) and also the linearized training dynamics in the over weerparametrized regime (Allen-Zhu et al., 20 8a;b;; Chizat & Bach, 2018h, Du al., 201 8a:b; Ghorbani al., 201 9a; Jacot et al., 2018; Lee et al., 2019; Oymak & Soltanolkotabi, 2019; Zou et al., 2018).
The main goal of this work is to analyze the dynamics of prototypical reinforcement learning algorithm temporal/difference (TD) learning based on the recent progress in deep supervised learning. In particular, we will focus the lazy training regime, inspired by the recent work Chizat

---

Under review as a conference paper at ICLR 2020
& Bach (2018b), and analyze TD learning in both over-parametrizedd and under- ander-parametrizee regimes with scaled value function approximations.
Related Works. This work closely related to the recent paper Chizat & Bach (2018b), addressing the problem of lazy training in the supervised learning framework when models are trained through (stochastic) gradient descent. In particular, that paper introduced the scaling that we consider in this work explanation, e.g., of the small relative displacement of the weights of over- and neural networks for supervised learning. That work, however, leverages the gradient structure of the underlying vector field, which we lack in the present framework when the underlying policy is not reversible (Ollivier, 2018). The linear stability analysis is also considered in the recent work Achiam al. (2019) based on the neural tangent kernel (Jacot et al., 2018) for off-policy deep Q-learning.
under-parametrre
The groundbreaking paper Tsitsiklis & Van Roy (1997) proves convergence of TD learning for linear value function approximation, unifying the manifold interpretations of this convergence phenomenon that preceded it by highlighting that convergence of the algorithm is to be understood in the norm induced by the invariant measure of the underlying Markov process. Furthermore, the paper gives an illuminating counterexample for the extension of the linear result to the general, nonlinear setting. Our result shows that divergence does not occur in the lazy training regime.
Concurrent work (Brandfonbrener & Bruna, 2019) has shown convergence and non-divergence of TD learning in the over parameterizedd respectively the under-paraun parrmmtrrrdee regime, provided that the environment is sufficiently reversible. We note that working in the lazy training regime allows to ensure convergence independently on the reversibility of the environment and quantify the error of the fitted model in the pedde--prametrrized regime. Finally, another concurrent work (Cai et al., 2019) analyzes global convergence of a modified TD algorithm for two-layer neural networks with ReLu nonlinearity when the width of the hidden layer diverges. In contrast, in the present paper focus on the original TD(A) learning algorithm for general approximators.
This paper proves that on-policy TD learning for policy evaluation con-policy policy- evaluation for short), widely used algorithm for value function approximation in reinforcement learning, is convergent (asymptotically with probability one), in the lazy training regime, when the model is nonlinear function of its parameters. More specifically, we prove convergence of this algorithm in both the under- and over- wver-paramerriee regime to local and global minima, respectively, of natural, weighted error function (the projected TD error), and illustrate such convergence properties through numerical examples.
Contributions.
To obtain the result summarized above, we adapt the contraction conditions developed in the frame- work of linear function approximations to a nonlinear, differential geometric setting. Furthermore, we extend some existing results on the convergence in the lazy training regime of nonlinear models trained by gradient descent in the supervised learning framework to the world of reinforcement learning. This requires generalization of the techniques developed in the gradient flow setting to non non-gradient (i.e., rotational) vector fields such as the ones encountered in the TD learning framework.
MARKOV DECISION PROCESSES
We denote a Markov Reward Process (MRP) by the 4-tuple P,r,,). where S is the state space, P= s')a.'e a transition kernel, r(s,s') s')..'' is the real-valued, bounded immediate reward function and 7 (0. 1) is discount factor. In this context, the value function V : S - R. maps each state to the infinie-hhorizon expected discounted reward obtained by following the Markoy process defined by P. We assume that this Markov process satisfies the following assumption:
Assumption 1. The Markov process with transition kernel P is ergodic and its stationary measure has full support in S. Furthermore we assume that is compact.
In this note we are interested in learning the value (or cost-to-go) function V*(z) of a given MRP (S, P.r, 7), which is given by
D0 Cr'r(5()441) s6t1)
V (*(s) == E.
(I)
where E, |-] denotes the expectation of the stochastic process s; starting at 8g More specifically we would like to estimate this function through a set of predictors Vs, in a Hilbert space F parametrized by vector W = RRP We make the following assumption such predictors:
2

---

Under review as a conference paper at ICLR 2020
Assumption 2. The parametric model V E. + F mapping i V.).) is differentiable with Lipschitz continuous derivative DV w + DV (where DV is a linear Lipschitz constant LDv defined WRT the operator norm.
 map from Ip - with
A popular algorithm to solve this problem is given by value function approximation with TD(A)
updates (Sutton& & Barto, 2018). Starting from an initial condition w(O) E W. for any À E [0, 1). this
learning algorithm updates the parameters of the predictor by the following rule:
w(t + 1) == w(t) + (t)(t)xx(t),
(2)
for fixed sequence of time steps { to be specified later, where the temporal-differnne error 8(t) and eligibility vector (t) are given by
8(t) == r(8t, 8141) + (ee()( (x 21(1) = Σ (GA V Vi(o
(3)
This work focuses on the asymptotic regime of small constant step-sizes Br + 0. In this adiabatic limit, the stochastic component of the dynamics is averaged out before the parameters of the model can undergo significant change. This allows to consider the TD update as a deterministic dynamical system emerging from the averaging of the underlying stochastic algorithm. We focus on analysis of this deterministic system to highlight the aspect of nonlinear function approximation. The averaged, deterministic dynamics is given by the set of ODES
d (t) = Eu (rr(,, + +VVnto)(s') -
(4)
df
where E,, denotes the expectation with respect the invariant measure of the underlying dynamics. In the case of finite state space ((S = d) we can represent V as vector in Rd, while in general is a function S + IR, which we will restrict to the space L² μ), namely square integrable function with respect to the measure p.
To streamline our analysis of the TD algorithm, we define the TD operator T> L)) + LL(
(= := 1 A)
Σ A
Ar(s S241) + (
Note that when À the above operator acquires the simple form T == F + PV for F(s) = E, [r(s, s')]. Then, denoting throughout by DV= the Fréchet derivative of V at w, it can be shown (Tsitsiklis & Van Roy, 1997, Lemma 8) (and is immediately verified in the special case A = 0) that the continuous dynamics (4) for general x < can be written as
d w(t) = (T (n) Vu((e) DV DVn(t)
(5)
dt
where we define throughout the inner product induced by the invariant measure (acting component- wise in expressions such as the one above)
(a, (a.b),. : (())((s))((ds)
(6)
and denote by || || the corresponding norm. Note that in the case |S] d, denoting by I the d-dimensional diagonal matrix whose entries are the (positive) values of the invariant measure ja()), one has (a, b),
rb. The extension of convergence results for the limiting, average dynamies we consider in this paper convergence with probability one of the underlying, stochastic algorithm can be obtained through standard stochastic approximation arguments (Borkar & Meyn, 2000; Borkar, 2009). More details on this straightforward extension are given in Remark 3.4 in Section 3 and in the appendix.
In this work, we are interested in a certain scaling of the TD learning algorithm with function approximation. More specifically, we consider the rescaled update
d
dt w(t) =
- aV (t)) DV DV
for large values of the scaling parameter a > 1. One of the reasons why this scaling of the model is of practical interest is because it arises naturally when training neural networks, implicit in some widely applied choices of initial conditions, as we explain in Section 4.2. Furthermore, as we shall see below, under some mild assumptions for large values of a the parameters w of the model vary only slightly during training, inducing what is called the "lazy training" regime. A visual representation of the geometric effect of this scaling in the case where p < d < 0o is given in Fig. 1.
3

---

Under review as a conference paper at ICLR 2020
W
F
Tr(w
V(w(O))
(0)
aV(W)
Figure 1: Schematic representation of the effect of the linear scaling of the approximating function (e.g., in (11)) in the under-paramedd paddee-prrmeerizzed setting. The space of parameters (left) is mapped to the space of predictors (right) by the parametric model V. The scaling V + a changes the manifold For that the parameter space is mapped to (different surfaces on the right). In particular, this scaling "widens" the reach in the space of functions of the predictors within a ball of small radius in W, but at the same time it "flattens" that space (locally in W) bringing it closer to the tangential plane to the initial model (o) Choosing V Vu<(o as in the picture above leaves the initial point of the dynamics (in predictor space) invariant under such transformation.
MAIN RESULTS
3.1
OVER-PARAMETRIZED REGIME
In the over-parametrized setting we assume that (V is surjective, i.e., its singular values are uniformly bounded away from O. This is only possible in the finite state space setting and is automatically the case if the number of parameters p is larger than the size of the state space S. Admittedly, in applications such as AlphaGo (Silver et al., 2016; 2017), it is unrealistic to over- parametrize, but we start with this regime as it parallels the study of over- wver-parametrized supervised learning for global convergence of the training loss. Analysis of the under-parametrized regime will be discussed in the next subsection. In order to state our first result, we introduce the scalar product in F defined by (a.b), it induces. Note that 9.. is the metric tensor associated to the pushforward metric induced by the parametric model V RR + F. We note that if DV has singular values that uniformly bounded away from 0, the norms & Il < lll < ollffloo for all f F.
(a. 9)) where In (DV.* DV
and denote by || llo the norm
|| ll llo are equivalent, i.e., there exists K > 0 such that
case). Assume that amin > O, where amin is the small- est singular value of DV Assume further that w(O) is such that VV lo < M == (1 -1-77 70- /1122/19912200000 DV (o)( II), thenfor 0o == ||V*|ooMM we have for all 2 0 that
Theorem 3.1 (Over-parametrizee
-|V aVai, lla S -1I=" (V llãe 1.3+
Recall that V* is the exact value function given by (1). Moreover, if I[ (o, S C1 for constant C> 0, then supr>a [|w(t) (0)] = 1)
Similarly to the proof in Chizat & Bach (2018b), we first show that DV,, and Vio do not change much assuming that w stays in a small ball of radius g. Then, combining this result with the Lipschitz continuous character of DV in one shows that w does indeed stay in the desired ball of radius g. A similar computation can be done our case, To bypass the absence of a strongly convex cost functional in our framework, which was crucial in the analysis of Chizat & Bach (2018b), we adopt strategy based on the use of a local Lyapunov function
Uff) = If V
where V* is the sought for value function (1). The theorem is based on some preparatory lemmas, proofs of which can be found in appendix. The first one states that for large values of the scaling parameter a the pushforward metric Iw varies in a negligible way during training. Throughout, we denote by 1 the identity map in the corresponding space and by By (v)), (1) and (y(v) the balls with radius around in I| || Ilo and || l|2 respectively.
Lemma 3.2 (Perturbation of the metric). Let Go be a compact subset of linear space G. For v(0) Go. let ge be a continuous, self-adjoint linear operator that is positive definite in neighborhood of v0) when restricted on G. Then all > 0 there exists > such that, for all E Bs(v(0)) S Go
Pe(0) (1 + go)
(10)
4

---

Under review as a conference paper at ICLR 2020
for a linear operator gu with |g < E. More specifically, let min be the smallest singular value of (V Then if e S (1 miin (4SLDV) (10) holds with llāv(w)) We also recall from Tsitsiklis & Van Roy (1997) the following contraction property of the TD operator in the || l| norm. For the convenience of readers, we recall the proof in the appendix.
< 1 for all (B)(w
Lemma 3.3. (Tsitsiklis & Van Roy, 1997, Lemmas
7) Under Assumption for any V, E F we have that |[TAV - -T*VII 1l S >x/lV Vll for 7 = 7 S < 1. In particular there exists a unique fixed point T V E F given by (1).
The proof of Theorem 3.1 relies the above lemma to establish decay of the local Lyapunov function U as long as w stays within a ball. The nonlinear effects become negligible when a is sufficiently large. The control of U in turn gives the bound of the change of w, which closes the argument. The details are given in the supplementary materials.
Remark 3.4. Our results can be extended to show stability and convergence in the stochastic approximation setting, similarly to Bhatnagar et al. (2009); Tsitsiklis & Van Roy (1997), under the additional assumption that the step size {3c} satisfies the Robbins-Monro condition (Robbins & Monro, 1951). For example, one can apply (Borkar & Meyn, 2000, Thms. 2.2, 2.4) guaranteeing almost sure convergence and exponential contraction of the expected error with probability one over the initial condition provided that the limiting vector field (in our case (7)) has unique fixed point and is Lipschitz contimuous. Lipschitz continuity is an immediate consequence of the linearity of T and the boundedness of closed balls in F logether with the Lipschitz continuity of the models Assumption 2. The existence of a fixed point (1) in F of the limiting vector field is trivial while its uniqueness is shown in the proof of Theorem 3.1 in the appendix.
3.2 UNDER-PARAMETROS PARAMETRIZED REGIME
We now proceed to state and prove a convergence theorem in the under- muder-parametrizee case. The underlying assumption in this section is that the size of state space is larger than the number of parameters, which in turn bounds the rank r of (V from above: r < p < d (where possibly d = 00). In this regime, in general, there is no hope that TD will converge to the true value function V*. In fact, the image of the operator T might not even lie in the space Fr of approximating functions. However, the derivative DVT in the TD update acts as a projection (WRT the product ((()) ())) onto the tangent space of F... at Vun(t) (more specifically, DV wi(t) projects the image of T onto W, which is then mapped back to (wett) Fa by DV We denote throughout by II and Ho the projection operator under (6) onto T (()) and Tv(w(o))FF respectively. What one can hope for is that the TD algorithm converges to a locally "optimal" approximation V of V on the manifold Fu. which is close to the best approximator IlgV* of V* on the linear tangent space (w) Fw..
Theorem 3.5 (Under-parametrizedd case). Assume that r := rank( DVw) is constant a neighbor- hood of (0) and Vor(o) = O. Then there exists og >> O such that any a > ag the dynamics (7) (and the corresponding approximation Va) converge exponentially fast to a locally (in W) attractive fixed V*Il
point V*, for which |[[TA>> - V*)
and I -----VVlle <
1->0 1- [ (iIV*-V'"I V*I + O(aa ").
Note that for random initialization the constant rank assumption is generically satisfied. Indeed, the maximal rank property holds generically in W and thus wp1 at w(0) when the model parameters are initialized randomly. Furthermore, by the lower semicontinuity of the rank function the Jacobian DV will have maximal rank in an open subset of W. The main difference of the proof of the above result WRT the one in the ever-parametrzer This implies on one hand that the norms || ر| and || llo are not equivalent in F, even though we still have || Ilo S x|| |I, for a K > O, provided that Assumption holds. On the other hand, as mentioned above, this implies that the model V., evolves on submanifold F., of F, and that T does not, in general. map onto the tangential plane Fw) of Fw at V.. The action of T is then projected back onto Fw by the operator DVu(e). The nonlinear structure of the space F... slightly complicates the proof WRT the over-paramettoo geometric tools to map the problem back to a linear space.
regime is that DV DV does not have full rank anymore.
case, and we apply standard differential V Fo
Wo
Proof. We apply the rank theorem (Boutaib, 2015; Lee, 2003) ((Abraham et al., 2012) for the co-dimensional setting) to show that there exist sets Wo. Wo RP, Fo C F and diffcomorphic maps & : Wo + Wo. & F, - FF,
à
Wo
Fo
where voo Vog-1 mr. ((w(0)) 0, vb( (V))))) = 0 and, for an appropriate choice of bases, n. maps
5

---

Under review as a conference paper at ICLR 2020
the coordinates of Wu to the first coordinates of Fu, i.e. (T1,...,, zp) (æ1,..... 2r, 0, 0.0.... .......).
where r is the rank of the operator (o) We denote by II, the hyperplane in F ssannndd by the first r vectors of the basis. We recall that by Abraham et al. (2012); Boutaib (2015); Lee (2003) the maps, tt, Ø, My are continuous with Lipschitz derivatives DØ, DΦ, DT, respectively.
We consider the trajectory of V Vi(t) == n, o(w((t) = <((w(t)): Denoting by D- the Fréchet derivative at the corresponding point of the dynamics and noting that DV = Dip De we have
d V dt (1(1) = DVDVDV ,T aab (V m(t)) - an (V (Vw(1))>
1
a 1 DT, (Dn, Dx, (D (Dib-1) T aV onb (V w())))
(11)
so V remains in II,.. As consequence of the above we can naturally define metric (the pushforward metric) on F by the tensor 9s = (D DoD Dx," In fact, by choosing the metric tensor to be constant on Fo. i.e., equal to Do for all v E Fo. we equip the linear space Fo with a scalar product (...)u
")u This, in turn, directly induces norm || llo on the same space. We now proceed to use such simple metric structure to establish the existence and uniqueness of a fixed point of (11) in Fo for large enough.
The result of our theorem follows from (Simpson-Ponl Porco & Bullo, 2014, Proposition 4.1), which of a dynamical system evolving
establishes uniqueness and exponential contraction at rate under the flow of vector field X given by the RHS of (11) in forward invariant set Fo provided that for every geodesic (s) ) in Fo (12) holds. Therefore, the proof of convergence is concluded by applying Lemma 3.6 and Lemma 3.7, whose proof' can be found in supplementary materials. The
proof of the optimality of the fixed point is postponed as Lemma A. in the appendíx.
Lemma 3.6. There exists ó > and on > such that the ball B (0) S Fo is forward invariant and forward complete with respect to the dynamics of (7) for all a > 0xp-
Lemma 3.7. There exists i >> 0, 5 > O and on > 0 such that for all a > an and all geodesics ri(s) contained in the ball (0) C Fo, the function
((7())) es(n'
(12)
strictly decreasing in s.
Remark 3.8. The proof of Theorem 3.5 can be straightforwardly generalized the case where the initial condition Vo is not identically O but within B Belaa (0) for e(a) going to 0 with - 6c. This generalization, however, requires the map V to be uniformly Lipschitz smooth for E Wo. Among other things, this extension allows to explicitly cover the training of randomly initialized, single layer neural networks.
4 NUMERICAL EXAMPLES
4.1 A DIVERGENT NONLINEAR APPROXIMATOR
We illustrate the convergence properties of TD learning in the lazy training regime in the under- parametrized case by applying to the classical framework of (Tsitsiklis & Van Roy, 1997, Section X). This reference gives example of family of nonlinear function approximators that diverge when trained with the TD method. The intuition behind this counterexample is that one can construct a manifold of approximating functions F., in the form of spiral, with the same orientation as the rotation of the vector field induced by the TD update in the space of functions. By choosing the windings of the spiral to be dense enough, the projection of the TD vector field follows the spiral in the outward direction, leading to a divergence of the algorithm, as displayed schematically in Fig. 2a. More specifically, consistently with Tsitsiklis & Van Roy (1997), we parametrize the manifold F.. (10, -7, -7),
(2.3094, -9.815, 7.5056), = 0.01, = 0.866. We choose the discount 7 = 0.9 and a step-size of 3. = x 10-3, while the underlying Markov chain is defined by the transition matrix Pt. (6, mood(i.)))+ + /22. where 8i,; is the Kronecker delta function and equals if = j and 0 else. We note that the step-size does not affect the convergence properties of the algorithm, the immediate reward was set to = (0, 0, 0). Note that, as realizing the conditions of Theorem 3.5 would start the simulation the solution V (0, O, 0), shift both the solution and the manifold
Vg e0 (a (X0) bsin(}0))
V for
argued in Tsitsiklis & Van Roy (1997), where

---

Under review as a conference paper at ICLR 2020
(a) =1
(b) 10a
Figure 2: Schematic representation of the manifold F., for the example in Section 4.1 before (a) and after (b) scaling a. The underlying vector field represents the TD error d(V) from (3), whose projection on F.F gives the dynamics of the TD update in F... In (a) this projection points "outwards" along the spiral, while (b) has fixed point close to O. The scaling yields an effective "linearization" of the manifold around O. The red point marks the global fixed point of the vector field.
of approximating functions by the same vector in the embedding space, leaving the new solution V = Vo = -a at the center of the spiral, i.e., realized at 0 = -o0. This corresponds to choosing an average reward change in F results in a global shift of the TD vector field in F and does not affect the update of d. In particular, this means that the TD update remains divergent for every initial condition different than the solution V*
( (-6.85 6.85, 8.35, 1..).. We note that by the affine nature the TD update, this
We the TD update in the off-centered situation both for values of a (the classical, divergent regime) and a = 100. As explained in the previous sections, this scaling of the approximating function makes the TD update convergent, as displayed in Fig. 3a. Indeed, under this scaling the solution converges to a local minimum of the dynamics. The intuition behind the convergence of the algorithm is outlined Fig. 2: when a is large we are in an almost linear regime where the TD update converges.
4.2 SINGLE LAYER NEURAL NETWORKS
We show that the regime of study arises naturally in one hidden layer neural networks for a certain family of initialization. We consider the example ReLu activation, i.e., when the model is given by
(s) a, max(0, b, ca).
(13)
for E R and N distinct (m + --diinnniio vectors w, (a., (b:) (bi) CE) Typical initialization of the weights of the above model is of the form 04 itd N(00 1/ /VN), (b.); ind
(0 1//m) for all j and e, idd (0, 1). However, by the linearity of (13) in a; by the rescaling property normal distribution this is equivalent to writing
(V = a Σ a; max(0,b, b, -c;),
(14)
for an N-dependent a(N) /N (diverging in N), aj Rdd N(O, (be), std N(O,, 1/Vo) and
G sid (0, 1)¹, Therefore, this common choice of initial conditions implicitly starts the training of the above model in the lazy regime (Ghorbani et al., 2019b). We train the model (14) by TD learning regime. To so, we
(7) with fixed step-size B2 10-3 both in the over- and under-parametriaa
draw an objective function V randomly with distribution (*(s)
itd NN(0,) 1) for all E S grid
A heuristic justification that the scaling the parameters of the neural network by a(N) to lazy training while the scaling - is natural for the model Ve and does not lead to the lazy regime can be found in Chizat & Bach (2018h). This natural scaling is studied in depth in Chizat & Bach (2018a): Mei et al. (2018); Rotskoff Vanden-Fijnden (2018)
1/v leads
7

---

Under review as a conference paper at ICLR 2020
Orepannetiizdd
100
4.0
10
Unleppmantiied diffeee inttial cocal.
Berations
(a) Example from Tsitsiklis & Van Roy (1997)
(b) Neural networks simulation
Figure 3: Results of the training of nonlinear value function approximation with TD learning for the examples described in Section 4.1 (a) and Section 4.2 (b). In (a). we plot the μ-norm of the projected TD error I V-). This quantity measures the increments of the model parameters during training and vanishes at a local minimum of the TD dynamics. We see that the algorithm diverges for a = 1 (blue curve), but converges to local minimum for 100. In (b, above) we plot the MSE of single layer neural network during training in the over-parametrized regime (N 100, d = 30, a = 500) ) for different choices of y (0.8, 0.83, 0.85, 0.87, 0.9), showing exponential convergence (at different rates) to the global minimum claimed in Theorem 3.1. In (b, below) we again plot the norm of the the projected TD error for a neural network in the under- padder-pramettrzeed regime (N 10, 50, a 100) for different initial conditions, showing that the dynamics converge to a local fixed point.
of dl equally spaced points the interval [-1, 1]. We then compute the corresponding average reward by solving the TD equation: F = (1 >P and train the model (7) for À = 0, 0.9 (when not specified otherwise) with transition matrix Ps3 = (8) (0).mod(i.d)++ + 5z,)/2. To respect the conditions of Theorem 3.5, we initialize half of the parameters of the neural network as explained above, while the other half obtained by replicating the values of b;, G, and inverting the one of a; > a; This "doubling trick" introduced in Chizat & Bach (2018h (b) produces neural network with V (a)(o) = 0 and randomly initialized weights with the desired distribution. We consider situations where N 10, d 50 (under- uunder-parametio parametrized, taking 100) and N 100, d 30 (over- aever-parametrized, with a = 500), and plot the convergence to local, respectively global minima in Fig. 3b.
DISCUSSION AND CONCLUSION
In this work we have proven the convergence properties of the TD learning algorithm with nonlinear value function approximation in the lazy training regime. In this regime, the algorithm behaves essentially like linear approximator spanning the tangential space of the approximating manifold (in function space) at initialization. As such, the training converges exponentially fast with probability one to the global minimum or local fixed point depending on the codimension of the approximating manifold in the search space. This guarantees convergence with little parametric displacement. This phenomenon can be intuitively understood as an effect of the linearized regime in which the neural networks are trained which reduces them, in the limit, to a randomized kernel method (more precisely a Neural Tangent Kernel (Jacot et al., 2018)). In this sense, convergence of lazy models may come at the expense of their expressivity. Recent works (Chizat & Bach, 2018b; Ghorbani al., 2019b) discuss the approximating power of lazy neural networks in the supervised setting, highlighting their limits WRT their non-lazy counterparts and naturally comparing them with random feature models (Yehudai & Shamir, 2019), but an exhaustive study of the expressivity of these models, in particular in the context of reinforcement learning still lacking. Nonetheless, the results proven in this work emphasize the interest of this regime in the framework of deep reinforcement learning, where models often suffer from divergent behavior especially during early stages of training.
Future directions of research include the extension of these results to more complex, nonlinear rein- forcement learning algorithms such as Q-learning, and the development of more refined, nonasymp- totic versions of the above theorems. Furthermore, a more thorough exploration of the relationship between the limiting results in Chizat & Bach (2018a) 8a) and the ones presented here and in Chizat & Bach (2018b) while transposing those to the framework of reinforcement learning would be important for the understanding of the limiting dynamics of neural networks in this domain.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ralph Abraham, Jerrold E. Marsden, and Tudor Ratiu. Manifolds, tensor analysis, and applications, volume 75. Springer Science & Business Media, 2012.
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards Characterizing Divergence in Deep Q-Learnnn, 2019. preprint, arXiv:190s 19903088944
Z. Allen-Zhu, Y. Li, and Y. Liang. Learning and generalization in overparametrized neural newtorks, going beyond two layers, 2018a. preprint,
Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-paramettriiztion 2018b. preprint, 1 181..0996..
A. R. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information Theory, 39(3):930-9453 1993.
Shalabh Bhatnagar, Doina Precup, David Silver, Richard S Sutton, Hamid R. Maei, and Csaba Szepesvári. Convergent cemporal-difference learning with arbitrary smooth function approximation. In Advances in Neural Information Processing Systems 22, pp. 1204-1212 2009.
V. Borkar and S. Meyn. The O.D.E. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2))4477469 2000. doi: 10.1 10.1137/50033311997333333
Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009.
Youness Boutaib. On Lipschitz maps and their flows, 2015, preprint, arXiv:1510.07614.
D. Brandfonbrener and Bruna. On the expected dynamics of nonlinear TD learning, 2019, preprint, arXiv:1905. 12185.
Qi Cai, Zhuoran Yang, Jason D. Lee, and Zhaoran Wang. Neural lemporal-difffrence learning converges to global optima, 2019. preprint, arXiv:1905.
Lénaïic Chizat and Francis Bach. On the global convergence of gradient descent for ovrr-parrmeterizee models using optimal transport. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 3040-3050, 2018a.
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. 2018b. preprint, arXiv:1812.0799
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, Dec 1989.
S. Du, J. D. Lee, H. Li, I.. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks, 2018a. preprint, MTt::1811.038000
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks, 2018b. preprint, 1r0.v:1810.02054.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension, 2019a. arXiv preprint 1904
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural networks, 2019b. preprint, urXiv:1906.08899
Haarnoja, S. Ha, A. Zhou, J. Tan, G. Tucker, and S. Levine. Learning to walk via deep reinforcement learning, 2018. preprint, a 1812. 1103..
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2): 251 257, 1991. ISSN 0893-6080.

---

Under review as a conference paper at ICLR 2020
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in neural information processing systems, pp- 8571-8580, 2018.
Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve Linear Models Under Gradient Descent, 2019. preprint, arXiv:1902.06720
J.M. Lee. Introduction to Smooth Manifolds. Graduate Texts in Mathematics. Springer, 2003. ISBN 9780387954486.
Hamid Reza Maei and Richard S. Sutton. GQ(lambda): general gradient algorithm for temporal- difference prediction learning with eligibility traces. In 3d Conference on Artificial General Intelligence (AGI-2010). Atlantis Press, 2010. ISBN 978-90-78677736--.
Song Mei, Andrea Montanari, and Phan-Ming Nguyen. mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33))87665-77777,, 2018. doi: 10. 10.3/ss/ 806579115.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, (7540):529-53)) 02.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. In NIPS Deep Learning Workshop. 2013.
Yann Ollivier. Approximate temporal difference learning is gradient descent for reversible policies, 2018. preprint, arXiv:1805.00869.
S. Oymak and M. Soltanolkotabi. Towards moderate overparametrization: global convergence guarantees for training shallow neural networks, 2019. preprint, 192iv:1902.04674.
Martin Riedmiller. Neural fitted Q iteration first experiences with data efficient neural rein- forcement learning method. In João Gama, Rui Camacho, Pavel B. Brazdil, Alípio Mário Jorge, and Luís Torgo (eds.), Machine Learning: ECML 2005, pp. 317-328, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
H. Robbins and S. Monro. A stochastic approximation method. Ann. Math. Statist., 22:400-407, 1951.
G. Rotskoff, S. Jelassi. Bruna, and E. Ganden-Eijndee Global convergence neuron birth-death dynamics, 2019. preprint,
Grant Rotskoff and Eric Vanden-Bijnden. Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biana BiancBBaachh,... and R. Garnett (cds.), Advances in Neural Information Processing Systems 3/, pp. 7146-7155. Curran Associates, Inc., 2018
David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schritwwesser, loannis Antonogiou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen. Timothy Lillicrap. Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of Go without human knowledge. Nature, 550:354, October 2017.
10

---

Under review as a conference paper at ICLR 2020
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419): 14004 140-1144, 2018.
John W Simpson-Porco and Francesco Bullo. Contraction theory on Riemannian manifolds. Systems & Control Letters, 65:74-80, 2014.
R. Sutton and Barto. Reinforcement Learning: Introduction. MIT Press, Cambridge,
MA, second edition, 2018.
Richard S. Sutton. Learning predict by the methods of temporal differences. Machine Learning, (1):9 44, Aug 1988.
Richard S Sutton, Hamid R Maci, and Csaba Szepesvári. A convergent o(n) temporal-difference algorithm for off-policy learning with linear function approximation. In Advances neural information processing systems, pp. 1609-1616, 2009a.
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 993-1000. ACM, 2009b.
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis Lectures on Artificial Intelligence and Machine Learming, 4(1):1-103, 2010.
John Tsitsiklis and Benjamin Van Roy. Analysis of lemporal-difffreene learning with function approximation. In Advances in neural information processing systems, pp. 1075-1081, 1997.
C. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, Oxford, 1989.
C. Wei, J. D. Lee, Q. Liu, and T. Ma. On the margin theory of feedforward neural networks, 2018 8. preprint, arXiv:1810.05520
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks, 2019. preprint, AiXi:1904.00087..
D. Zou, Y. Cao, Zhou, and Q Gu. Stochastic gradient descent optimizes over-parameteerrizee deep ReLU networks, 2018. preprint, arXiv: 1 110008888.

---

Under review as a conference paper at ICLR 2020
A SUPPLEMENTARY PROOFS
To simplify the notation in the forthcoming analysis, we slightly abuse the notation used when the state space is finite-dimensional extending it, when necessary, to the infiniteddimensional setting. This naturally generalizes matrix multiplication to the action linear operators. In particular the action of I, which we recall in the fiite-dimennionnl setting is a diagonal matrix with entries y((s), is to be intended as
// a: (s(s), (s) p(ds).
(a Tb)is
Furthermore, we introduce the following decomposition of the TD operator:
TV 7PVV,
where
(s) = =1
7'n(s),
(0 Σ (A (V(m++1)]
172 m
1=0
m=0
or, in vector notation
X)
p
P= (1- Σ (7)) mm)
m==
1=0
m==
In the proofs below, we will use the above, simplified notation to obtain contraction estimates on the dynamical system (4). These estimates will leverage the fact that Pd is nonexpansive and y 1, and from this notation contraction rates in terms of will arise naturally. However, by Lemma 3.3, we know that the contraction rate of T yx. Rewriting the proofs with y - 7A will show the stronger contraction.
A.1
REGIME
Lemma 3.2 (Perturbation of the metric). Let Go be compact subset of linear space G. For u(0) Go. let ge be a continuous, self-adjoint linear operator that is positive definite a neighborhood of v0) when restricted on G. Then for all > O there exists >> O such that, for all E BB(((0)) C Go
Pv(0) = (1+ g.)ge.
for a linear operator Go F - F with |1ā=1|, < &. More specifically, let m be the smallest singular value of DVw Then if S (1 ()- minn / (48L (10) holds with llāv < L for all w E (w))).)
w(()) DV, We carry out the proof for the case amin < 1 (else the result holds with min in 2), in which case we have for all w E (,(w(O) that
Proof of Lemma 3.2. Let B (V) DVT
|| s 2LDv w|ll (LDv ([ wol)² s 3L (0()) will
Then we can write
(w) = (DV ) ) = (DV,, DV + Bw))
( Iv Bw))) -1 (1 Iw Bw)) - gro
00
Σ (1- (gw 3" Iw = Iw + Σ
(g
n=1
Furthermore, by the assumptions on the regularity V and on the initial condition w0) we have
that 9u < of min 11, provided that w E (w)( for e as in Lemma 3.2. Therefore, the perturbation Tw = En=1( (-1)" B.,"" satisfies
2
CC Σ
3LDV (lo(0) wll < 1 1-7
|| = Σ (1
By
Σ
min ///44/1/
The proof applies in the general case with different, implicit constants.
12

---

Under review as a conference paper at ICLR 2020
Lemma 3.3. (Tsitsiklis & Van Roy, 1997, Lemmas 1, 7) Under Assumption for any V.V F we have that
1-1
IT - - <xllV VIla for 72:=1 1- S <1.
(A.1)
In particular there exists a unique fixed point of V* F given by (1).
Proof of Lemma 3.3. We first prove that ||PVII I [V This follows by Jensen inequality and by the invariance of j.:.
|PV| V PTPPV S ((doa) ((s,dd')V(d'))
5 5=
p(ds) P(dd))(( ( =
usds)
(A.2)
Js
Then, writing
TV((s) = (1 (1-
ATE,
(r(s), s(+1) + + (8m+1))
m==
= -1 (1- -) A) Σ nm
EE [F(s)) + M [V (Sm+1))
0
= (1
(P)) (yp))++
1=
where 8, is the process on S induced by P with initial condition so, we have contraction of the operator T in (, (b) by
[T - 1)
A)
Σ x (yP) (V(s) (7(5)-Vi) (v())-v(s))
m m=
< - A) Σ m+ ((())
( - -(0)-
7(1 A) V(s)- -(>)l,
1 1-
where in the inequality above we have used (A.2). This proves that 7 is contraction in F, and as such it must have a unique fixed point. That this fixed point corresponds to (1) is immediately checked by direct computation.
O
Theorem 3.1 est singular value of DV Assume further that w(O) is such that VV lo M (1-7)00 / (112n=2 Lpv DV (o Il), then for
case). Assume that Jmin > O. where Omin is the small-
a ag = ||V we have for all 2 0 that
| VV 113 S I[V (o l1ee 1
(A.3)
Recall that V* is the exact value function given by (1). Moreover VVo S -1 for a constant C> 0, then sup:sa []w(t) - w())l = O()
Proof of Theorem 3.1. By setting == (1 7 min/ (48L.v and by the assumed Lipschitz smooth- ness of V. DV, DV o /4 long as w E B (w()).. We would like to check a local exponential contraction condition, i.e., that for all w(t) E (,((()) we have
पे U(aVo()) < 2-- U(VVato),
for t > 0.
(A.4)
2x
To obtain the above result apply the chain rule:
dt U(aVa()) = (a,U(aVm()) dt
a avmc)l
13

---

Under review as a conference paper at ICLR 2020
a(aVi())) V DV d = (aVi(1) - VV, DV T aV - aV wVa(t)))
at w((t))
(A.5)
Throughout, we define Tę == in < w(t) & ()(w(())), Iw == (DVw ) (recalling that the DV DV has full rank in B3 (w((())) and write 9o = (1 + Iw)ew, where gw is defined in Lemma 3.2. Then, long & < To have, for every b F
D (a, DVwc)) w(() rb), = (a, (1 + (o))) S (a, b) + l b
By the above result we can bound from above the of (A.5) by
di ((Vu(()) S (aVoio - V*, +
(A.6)
Recalling that by Lemma 3.3 have
ar (()) a V II = ( V* llaVa())) V* s 2 Vl (A.7)
and applying Lemma 3.2, we can bound the second term (A.6) from above as
1owollllaV V V' (o llx S 1-7 |a ((()) V| On the other hand, for the first term we have by
(A.8)
inequality and (A.1) that
(aVw(r) V*, T - aVw(e)
= (aVieo) - V", (T*)V - V*) (a wo() V*)) p
S w Vl aV VlI|, ||(V/ V || < ( - 1)llaV 11
(A.9)
where y is the contraction rate of the TD difference in F, see (A.1). Finally, combining (A.8) and (A.9) we obtain
dt U(aV - ? 2 |a laV 11
7-1 2x
l|a w(t) V*lla
(A.10)
and the last inequality results from the equivalence norms llo and ||, (both have full support on a finite set). The desired result (A.3) follows directly from the above by Grönwall's inequality for all < Tg-
now only remains to show that under the given choice of a, we have Te = co. By the contraction
of A Lemma 3.3 and our choice of < (2L we write
d
dt (t)
<
DV (o) aT aV - DV V*
Integrating the above and combining with the result from (A.10) in the previous paragraph have
(ol - V* f exp
[| - (0))l2 < a
ds
2x²
<
DV DV a - V lo
(A.11)
a (1
Given that [|aV (w) Vo < 2aM, the above quantity is bounded by and therefore Te = 00, as desired.
Finally, from (A.11) we see that if || V I Ca -1 then ||w(()) w(0)ll2 - a(1 Moo) (1a-1) for all
4x2 DV |V
0.
A.2 UNDER-PARAMETRIZEI REGIME
Lemma 3.6. There exists 8 > and on > such that the ball B5((), C F is forward invariant and forward complete with respect the dynamics of (7) for all > 0g-
14

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 3.6. We define the Lyapunov function U(f : 2 If whose sublevel sets (0). We prove forward invariance of such sets by showing that, their boundary (i.e., on the sphere S C Fu of radius 6), (f) decreases along trajectories of (7) for large enough.
Noting that 5% C Fo upon taking å small enough, we differentiate (V w(t)) WRT time for w(()
obeying (7) points V = V w(t) S
d
1 (V, (w(() Du I(T an (v)
di (V)
(V, (D T an) (V) - onb - (V))) + (V)
(D pa + aa(7 - 1 (V)) + RV(V)
s (D V p (V)) - Drj Dr V1I, || (V)). (A.12)
(V) where we have defined (V) == (V. (w (D
a (V)) for gu from Lemma 3.2. We now proceed to bound the last two terms on the RHs from above. The second term is of order a and therefore goes to 0 for a + oo while for the last one we have that, by the equivalence of the norms
ar
1lu and
1/2.
(V) <
[F + (TPA - 1)an (V) ll2
< Vllll I + || [VVlaal(aaccllll(0)) -10p-~ (VV]l2
1)b
Sa + C
(A.13)
for a constant C' bounded by the norm of all operators and, by Lemma 3.2 a positive function ( with l = O. By the bounds established above and the fact that | V E S 1 C Fo it is sufficient to show that the first term in (A.12) satisfies
2 x 18 for
(Di''V (7PA) - 1) -))) < -
(A.14)
for å small enough and constant & >> 0 independent of 5. We Taylor-expand b- around the origin, denoting the second order remainder of that expansion by R2( and since & (Vo) = we have,
(D 1)0 1V)) (D0F'V, "..'V.(7Pp..) 17PM-11)Pp 1)D
(D V (7 (V. (A.15)
where we have introduced the short hand notation Dep1 = D By the Lipschitz smoothness of d/- (-) (Lee, 2003) we can bound the norm of the second term from above
(De.'V. (nPA* (V, V) = 2 RI V)
2 D V
(A.16)
For the first term in (A.15) we can also expand DWE'' = D#5'1 + Re )), and by applying a similar bound as (A. we obtain that
(Dit V, Py Do VV),, S (Dvo VV p- 11)
- 2I V
(A.17)
The second term of the above equation being O V['), we now consider the first one. By the nonexpansion of P in || lla proven in Lemma 3.3 we have
(Dv5 'V P2 1)D 'V,, S Tl| D V PA Drh VIl,.
D '
< (7 1)11 D4
V 2 #
Di (7 1)(a
min
1 (A.18)
De-1 where o min
denotes the smallest singular value of D in By (0). Combining (A. (A.17) and (A.18) we finally obtain
(D VV 1) -V))),()), < [ () min
1
C' (IVlo))V
(A.19)
15

---

Under review as a conference paper at ICLR 2020
7 |]) and recalling that a. is the equivalence constant between the norms || 1I and || llo in Fo. Therefore, choosing ó small enough we obtain (A.14) and conclude the proof of forward invariance.
for C' 2 (
|
By boundedness of 88 (0) in Fo. forward completeness follows directly from forward invariance. D
Lemma 3.7. There exists > 0, 8 > 0 and on > 0 such that for all a > og and all geodesics 7())
contained in the ball (0) C Fo. the function
(s(ss) (
strictly decreasing in s.
Proof of Lemma 3.7. To simplify the notation and the forthcoming computation, we prove the differ- ential version of the desired result, i.e., we show that there exists & > such that
d ds
((((s)) (s( (0,, <.
(A.20)
The above expression exists almost everywhers by Lipschitz continuity of the terms to be differenti- ated. When this is not the case, we must interpret this derivative in the sense of distributions. We will highlight the steps where this could be necessary In our case, X is the RHS of (11) mapped through &p onto Fo, i.e.,
go along the proof.
1 X(>(s)) = - (DV) TI(T
(T((s) (>((s)) arb (
We going consider the "flattened" manifold obtained by the maps and equipped with the metric Ju- In this space, geodesics have the form 7(s) = 01 + sÂe where Av == 022 01 for U1 D2 E Fo and their derivative is (s(s) = Av. Consequently (A.20) reads
d (Au, (((s)))) < All ds
(A.21)
where defining (-(0) 900 1 in Lemma 3.2 we have
ds ds go (Do (
d X(((s)) =
""000"100000000"00000>0">""0"1"0 (1())))) (aa
d
8(7(s))) + (~(3) ds
(7(s)) (X))))) (A.22)
ds
for
X(>(s) = (D ((5)
T (oab (aa) (?(s)) ari acp)
We proceed by analyzing the first term in the above equation and leave the task of bounding the last two for later. Using ()as5 = aD 70) (s) = aD Au we have that
x(((s)) (D ( ( oy (T on (T())), ds
(A.23)
a
+ (D T Au D Do7 Au
where ( denotes the inversion of the last two indices of the Hessian. We now proceed consider the two terms in the sum above separately (multiplied by the scalar product of (A.21)),
defining throughout (TD), == r(T> ( oz6- (r(s)). For the first term we have:
1 (Av. 22 a T()) (TD,,A)), = || D' (()) (a 11p2 + (ypx 1)0 (y()) || E'
(A.24)
We recall that by construction of mappsings vi d, n. and by our assumption in Theorem 3.5 the metric tensor 9, has full rank on Ju and being the latter set compact its eigenvalues are uniformly bounded from below. At the same time, we can equip Fo with the metric induced by I' by restricting it to its first elements, which are uniformly bounded from below. Hence, the two metrics are equivalent on this space for some equivalence constant
16

---

Under review as a conference paper at ICLR 2020
for any E' > by using the linearity of the Hessian and bounding its operator norm of x on a compact space in Fo while choosing a large enough and small enough, since ((s) E (0). Note that if D is not differentiable, the above computation is to be understood in the sense of distributions.
We now focus on the second term of (A.23). In this case we incorporate the operator I in the inner product and write this term as
(De 7(3) Au, DT DVS -IDe 7(a)
Aul
Now, by the contraction property of T onto the tangential space T F in the norm || Il we can write
V7(0) *(()
(D) Av, DT DV Di Ao), = Aollal| Aollull
((a Aelly S DD Aull
so that
(Du 7(8) Au, DT D (0) Au), - S (1-1))1Do77
(A.25)
Denoting by max De- De- in 8 (0) (which are bounded away from upon possibly making this set smaller), by nondegeneracy of De and by the equivalence of the 1| and
min the largest and smallest, respectively, singular values of the map D'b
|| llo norms on Fo we have that
k t
De-1 min
|Awllo & | 7 De
< | (())
Arlla S Aulllo Du- I <niAAullooma De
Thus we have
I ((o) Aul 2 K (o ( ||uu1/
Dv
(A.26)
Getting back to the last two terms in (A.12), we immediately see from Lemma 3.2 that F-(s) is small, Lipschitz continuous perturbation. Hence, the product
(T))).(()
can be hounded from above similarly to (A.13), while the second order derivative in the third term of (A.22) can be dealt with analogously to what is done in (A.24), giving terms e Aull and e(3) Av respectively, both going to 0 as 8 > 0. Therefore, combining the above with (A.24), (A.25) and (A.26) we have
(Av,
d ((((s))) dt
7 7-1 x²
+
Σ
< 7- 1
(
2
/|Allla.
2x²
This directly gives (A.21) by choosing large enough.
The next lemma estimates the distance between the fixed point V of the dynamics (7) and V given by (1), showing that it is close, for large values of to the best linear model in the tangent space of Fur at Vu given by Io We recall that the projection operator Tl onto the linear space spanned by the columns of DV is given by (Tsitsiklis & Van Roy, 1997, Eq. (1))
I.W:
arg min (DV Au AWER")
( Aw W DVmnto) (DV-T ( (DVi DV -'VVTT,, TW,
-'DVT
for all W F where, if necessary, we interpret (DVT (O) (V)
pseudo-inverse.
Lemma A.1. Let V* be the fixed point of (7) and V* be the global fixed point of the TD operator, given by (1). Then under the assumptions of Theorem 3.5 there exists constants > 0 and C* > 0 (independent of ag), such that
| - V
<
1 -
(A.27)
1-7
where Th is the projection operator onto Fw(
17

---

Under review as a conference paper at ICLR 2020
To prove the above result compare the dynamics (7) to the dynamics of the model V when linearized at w(O). In this case, the dynamics of the parameters is given by
d (tt)
T VaT") Va(r)),
(A.28)
dt
where V E is the linear, tangent model of V at (0) defined as
Vi Vit + (V (w w())
(A.29)
We also write the dynamics of the linear model
dt Va())= = (V)))) DV I - Va(e))
(A.30)
Scaling the model as V aV and a a-'t 't obtain the analogue of (7):
1
(tt) == DV (0() I(T"aaa - aV(o(t)).
(A.31)
dt
which in F reads
d
a aVa = (V DV w() T ((T - aVaat))
di
Proof of Lemma A. Recall from (Tsitsiklis Van Roy, 1997, Lemma 6) that for the linear value function approximation one has
1- 1 - -V 1-7
I - V <
(A.32)
where Ho is the projection on (o) and V is the unique fixed point of the dynamics (A.30) on that space. In light of this result, our task reduces to bounding the distance between the trajectories of the original (i.e., dynamics (7)) and the linearized model (i.e., dynamics (A.31)) by Ca- -1 for C large enough. We do so in 3 main steps. First of all, we bound the maximal excursion of the models V and V. Mapping both dynamics onto common coordinate space, we then bound from above the distance between the two trajectories in this space by O(a Finally, we map the dynamics back to the embedding space and show that the correction again of the same order O(ar
Bounding the maximal excursion. To compare the dynamics of (V and aVaatt)) we map them to common space. Recalling the definition of the maps d hr, 3 from the proof of Theorem 3.5 we note that the first order expansion of vt, maps [v( to Fo- Explicitly, for V E Fo and for AV E (o)) Fw with |/ol small enough we have
(V + AV) == AV
and
Vin( Doto V E Tw) (A.33)
Now, we proceed to show that the dynamics of (7) and (A.31), mapped Fo. do not exit ball (0). when choosing 5 = C/a for C' large enough. We show this with the same strategy used for the proof of Lemma 3.6, i.e., we show that U(}) : 1/ 1 decreases on S 57-)(0) along the trajectories of interest (note that 5 is now much smaller than that used in Lemma 3.6). We will start with the curved dynamics (7) and will then show that the same result follows, in a simpler setting, for (A.31). For (0) we start by bounding, in 12), the derivative
V ((()) E S
1 a
((V) S (DOE'V, (rP* 1)th -V)) dt
(V))
(A.34)
Before bounding the above terms we recall that by Lipschitz smoothness of we have that
| (V)]l < [|Vaço)l| + -'D'V''' + LDD-:
(A.35)
Then, since Vu<o) = 0, similarly to (A.12) we have for the last term in (A.34) that, for a large enough,
(V, < gg ||| 12 | (I (D
- 1)1((
LDv [V
18

---

Under review as a conference paper at ICLR 2020
By the equivalence of the norms ||
222 and ||
II, and since 5 C/a we have that
Ry
V
V 1 1) O(a
(A.36)
upon increasing if necessary and defining K ~3 (Dee))
1 for Rg the
equivalence constant between 2/2 and || llo on II,.. The second term (A.34) can be bounded similarly to the above by the equivalence of norms:
DV |1
1 LIDE S IV
(A.37)
C
The first term in (A.34) can be treated identically to the proof Lemma 3.6 to obtain (A.19) Changing the norm in (A.19) and combining it with (A.36) and (A.37) gives
1s2 D
||| I + 11
((V) S V
7-1
De (amin
(K + +1) ( +
O)a
dt
2n.
C
Since 7 -
< <
can choose C large enough make the second term brackets smaller than
(7 - 1)/ (D
min )z. The same holds for the third term in brackets by (10), and for the higher order term by taking a large enough, showing that
dt (V)
7-1
(o
De min
V < 0,
4x²
desired. We note that the reasoning with LDV 0 and Duj,"' Dry yields an identical conclusion for the dynamics of ball of radius = C/ for C, o large enough. Also, we note that combining the above computation with (A.16) yields
one ( (V))I < |
'I + aT D [V133
$ ( 1) 1
||
O(a
Co.
(A.38)
for Co large enough, where Dus T is considered as operator mapping Fo + Fo-
Bounding the distance of trajectories. The distance between two trajectories with the same initial condition can be bounded by O(a using similar argument as in (Chizat & Bach, 2018 8b, Lemma B2) for the present framework. We include the proof of this lemma here as the assumptions are not identical and to make the paper self-contained, while we do not claim any improvement on that result.
De- denotes the smallest singular eigenvalue of D in To enounce this result, we recall that min
ball g for g (0) for small enough.
(0). which is bounded away from for small enough. Similarly, we recall that G. > o
Lemma A.2. Let V., V, Fo be solutions of
d
dt V. o. (D TTTT acb
V, = 0o (Dio 11 a (V.)
dt
Then defining K sup ( Do 1) ) onl- (V.)) and
x (o Dv )a we have that
1 2K
sup V Vello < 1>0
Proof of Lemma A.2. We define the function h(()) = 1 ( - Vellg. take its time derivative
M((1) = (V, - V V, V.).,
and defining
(TD), = on (V..) ar - -VV)).
19

---

Under review as a conference paper at ICLR 2020
(TD); = T - (Vee)
we evaluate (for simplicity of notation, we introduce the short hand Dir= = De for the rest of the proof)
(Di) ")TTTD)) - 96 (DV)
91
0
a
< 90
- "
(A.39)
-
(Dv;
(De, "
(A.40)
We look at the two terms on the RUS separately and obtain, for (A.39)
Co (Dei JI(TD), - 5o (Dv,')) V. -Vi)o
(A.41)
! -DD " (DV, V. V.-VI V.--V V.)
((TD), (T (V. (V. (V:-V))),
(A.42)
1 (DD)) - T V. V.).
(A.43)
We immediately that by Lipschitz smoothness of -- and the equivalence of || ||2 and llo norms on IT, and (A.38), for (A.43) we have
Ci 22h(t),
- (((D)) V. V.) < Lo ( -
a²
(A.44)
by choosing C1 large enough. For (A.42) by the definition of 1p have
(TD), -0):-(77) (TD): = ob (V.)
(V.)
=a(p* (1 (V,, -v))))))
and hence, by (A.35) we have
(TD))- - (TD),, Duj LV. V.)),, s ((P) (V.) - Dv -V)),
DWo
((PA-1)DD 10D05' - D.),
(V, 'V, (V)),,)))
+ .IV. 'II[V, - Della-
Defining B = 1-7 (DDD') ) the first term from above can be bounded as in (A. to obtain
(o
x²
min
((P* 1) ' (V. V.), Dv DV, Ve)), S -Bh(tt,
(A.45)
while for the second by our choice of 5 = C/ we have
C²
D [V II| Vell < kLn Dov |1 /2((t).
(A.46)
a
Finally, combining (A.44), (A.45) and (A.46) we have
(A.41) - -3h(t) + C2
22((t),
(A.47)
a²
where C2 = C1 CR
1|( '1
We now consider (A.40). Here by the definition of K we have
K VV Vello = K V2h(t).
( _o -o D T(TD),, V. V.l -
a
Combining the above with (A.47) we finally obtain
1t(t) < -Bh(t) + K
22h(t) + C2 a² (2h(t) S -Bh(t)+ + 2K
Vh(t),
a
20

---

Under review as a conference paper at ICLR 2020
for large enough. The above expression is negative soon h(t) 4K2 /a:B)) Therefore, because h(0) = O, we must have that h(t) _ 4K (aB)) for all > 0, i.e.
1 2K IV. Vello a B
for all > 0,
as claimed.
To achieve the claimed O(a bound, we observe that K in the above Lemma can be chosen (aa-1) by the Lipschitz continuity of gt Indeed, since we chose || have that
C/a, by (A.38) we
C 8 K"
K sup |I(TD)) a Vilo Coo max L 90 a
t>o
2
for K' large enough, and therefore
K' a²
V Vello
for all >> 0.
(A.48)
Mapping to the embedding space. where we have
We conclude the proof by mapping back to the original space,
sup IIV t>0
Volla = sup ||0 110 (V,) - (V.Ile
S sup (1 (V. Vell. 1ppw-I/Vell
x|| 14 sup IV. Vello + x² T.D t <a
V =l1
Then, letting V" be the fixed point of (A.30) (unique and attracting by Tsitsiklis & Van Roy (1997)), by our choice of i = C/a, (A.32) and (A.48) we have that
V* 1l - |
V
1
+ sup ||V
Vella
t>
1 (x] + C²
x
11
- -
1
claimed.
21


Reviews:
[{"review_id": "SyltdOWAYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers TD learning with function approximation, and establishes convergence results for over- and under-parameterized models in the lazy regime, and illustrates the theory on simple numerical examples.\n\nAlthough the obtained results are interesting and the paper is well written, the contribution is quite incremental, in that it simply combines prior work on TD learning with linear function approximation with lazy training in order to show that models with a certain scaling can lead to convergence. This scaling makes the models essentially linear in the parameters (with a non-linear feature map given by initialization), so that it is not surprising that convergence can be reached, given the prior work on linear function approximation. I encourage the authors to further explain their motivation in studying such a setting.\n\nIt is claimed that the over-parameterized regime is only useful for finite state spaces, which seems quite limiting, since one cannot obtain global convergence in the under-parameterized case. When considering neural networks at infinite width, would the results be applicable if one assumes that V* belongs to the RKHS of the corresponding neural tangent kernel?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HkgtJlIJ5B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyses the convergence of on-policy TD-learning for policy evaluation with non-linear function approximation (deep nets) in the lazy regime. Similar to deep learning theory, the key idea is that in the lazy regime, for an overparameterized network, if initialized in a certain manner, weights do not change significantly during training. The paper heavily draws upon techniques from n Chizat & Bach (2018) and adapts them to the setting with value functions, and policy evaluation. In order to get a strongly convex objective in function space, they consider a strongly convex Lyapunov function for the analysis. In the under-parameterized regime, the paper shows convergence to local optimum, by showing that convergence is exponentially fast to a local minimum where the key insight is that standard differential geometry can be applied to analyze the behavior of the projection on top of TD-lambda operator using past existing analyses. Finally, Section 4 shows numerical examples -- a divergent function approximator and some empirical results on a single-layer neural net.\n\nOverall, I lean in favor of rejection for this paper. I am mainly concerned with the significance of the content in the paper and positioning with respect to past theoretical/empirical work. My specific concerns are:\n\n1. Assumption 1 is strong, it assumes full support over the state-space, however, in any situation of practical relevance, this is not the case. There are many papers at this point (for example, [1], [2]) which show empirically that even with Q-learning (Fitted Q), divergence is not common if the function approximator is large/wide enough, and the support of the state space is full, however, these methods can diverge if the support is not full/ skewed. I am not sure if this assumption is very realistic then.  (The results are for specific function approximation in this paper, and hence it is unclear if that is the case we use in practice)\n\n2. I am not sure if the techniques used in the paper are relatively novel (from a theoretical point of view), and I would appreciate if the authors can elaborate a bit on this. It seems like most of the proof is drawn from past work (although past work has theoretical results in a different problem setting -- supervised learning). While the setting of policy evaluation is novel, I am concerned about how many new techniques are to be gained from a theoretical point of view here.\n\n3. What assumptions are needed for Theorem 3.1 and Theorem 3.2, from a deep-learning standpoint? What recommendations does the theory give to practitioners? I find a discussion on both of these points missing from the paper. It would be appreciated if the authors can elaborate on these points.\n\nReferences:\n[1] Deep Reinforcement Learning and the Deadly Triad, van Hasselt et.al.\n[2] Diagnosing Bottlenecks in Deep Q-learning Algorithms, Fu et.al.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gBBwcGKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discussed the nonlinear value function approximation for temporal different learning on on-policy policy evaluation tasks in the lazy training regime. The authors proved that for the both over-parameterized case (state number is fixed finite number) and the under-parameterized case (state number is sufficiently large or infinite), the value function can converge to some stationary point with exponential convergence rate. Moreover, the authors also characterized the error when the value function is under-parameterized.\n\nOverall, this is a good paper. But the paper organization is awful. There are many places that are ambiguous or with notations that not formally defined. It may not due to the page limit as the authors currently use only 8 pages. I think the authors should polish the whole paper and make it more readable. Below are some main clarity issues I find, but the authors should not only solve the issues I mentioned.\n\n1. For better presentation, I suggest the authors include a notation paragraph in the main text, which will be very helpful for the readers.\n2. I think it would be better to mention (7) returns w that V_w = V^* / \\alpha in Sec. 2 for better reading.\n3. In Theorem 3.5, it is unclear that the estimation \\tilde{V}^* is from \\alpha V_{w}.\n4. The WP1 in the paragraph after Theorem 3.5 means with probability 1?\n5. In Equation (11), what is the definition of the measure \\pi? If I understand correctly it is still \\mu as the invariant measure should be fixed for a given policy?\n6. The last paragraph in the proof of Theorem 3.5 is hard to follow. It can be better to introduce the result from the textbook and list the condition that need to verify, then give the lemmas show that the conditions can be verified.\nWhat is the functional X in (12)? Should mention it in the main text, not in the appendix.\n7. Figure 2 is somehow hard to understand. Maybe better show how the projection of TD error vector field outwards along the spiral in (a) and inwards in (b) in the figure.\n\nFrom my point of view, the proof is almost correct and most of the lemmas are standard. This result is meaningful as it shows how and when the nonlinear function approximation will converge in temporal-difference learning (under the context of lazy training, and I think it is also correct under the context of NTK). The perspective on viewing the TD learning as linear dynamic system on functional space can inspire several new research in this field. My main concern is about the paper organization. I feel it can be hard for the potential readers to go through the whole paper. If the authors improve the quality of writing during the rebuttal period, I will consider improve my score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygGVkvh3B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper discusses the policy evaluation problem using temporal-difference (TD) learning with nonlinear function approximation. The authors show that in the “lazy training” regime both over- and under-parametrized approximators converge exponentially fast, the former to the global minimum of the projected TD error and the latter to a local minimizer of the same error surface. Simply put, the lazy regime refers to the approximator behaving as if it had been linearized around its initialization point. This can happen if the approximation is rescaled, but can also occur as a side-effect of its initialization. The authors present simple numerical examples illustrating their claims.\n\nAlthough I did not carefully check the math, this seems like a solid contribution on the technical side. My main concern about the paper is that it falls short in providing intuition and contextualizing its technical content. Regarding the presentation, I believe it is possible to have a less dry prose without sacrificing mathematical rigor. If some of the technical material is moved to the appendix --like auxiliary results, discussion on proof techniques, etc--, the additional space could be used to discuss the implications of the theoretical results in more accessible terms.\n\nFor example, a subject that ought to be discussed more clearly is the nature of the approximation induced by the lazy training regime. As far as I understand, this regime can be thought of as a sort of regularization that severely limits the capacity of the approximator.  Although the authors mention in the conclusion that “...convergence of lazy models may come at the expense of their expressivity”, after reading the paper I do not have a clear sense of how expressive such models actually are. In their experiments, Chizat et al. (2018) observed that the performance of commonly used neural networks degrades when trained in the lazy regime --to a point that they consider it unlikely that the successes of deep learning can be credited to this regime of training. It seems to me that this subject should be more explicitly discussed in a paper that sets out to provide theoretical support for deep reinforcement learning.\n\nStill regarding the behavior of lazy approximators, my intuitive understanding is that they work as a linear model using random features. If this interpretation is correct, this makes the theoretical results a bit less surprising. They are still interesting, though, for they can be seen as relying on a “smoother” version of the linearity assumption often made in the related literature. Maybe this is also something worth discussing? Still on this subject, it seems to me that one potential disadvantage of lazy models with respect to their linear counterparts is that it is less clear how to enforce the lazy regime in practice. In Section 4.2 the authors discuss how this can naturally happen as a side-effect of the initialization, but it is unclear how applicable the particular strategy used to illustrate this phenomenon, with the “doubling trick”, is in practice. This is another example of a less technical discussion that would make the paper a stronger contribution.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides convergence results for Non-linear TD under lazy training.

This paper tackles the important and challenging task of improving our theoretical understanding of deep RL. We have lots of empirical evidence Q-learning and TD can work with NNs, and even empirical work that attempts to characterize when we should expect it to fail. Such empirical work is always limited and we need theory to supplement our empirical knowledge. This paper attempts to extend recent theoretical work on the convergence of supervised training of NN to the policy evaluation setting with TD.

The main issue revolves around the presentation of the work. The reviewers found the paper difficult to read (ok for theory work). But, the paper did not clearly discuss and characterize the significance of the work: how limited is the lazy training regime, when would it be useful? Now that we have this result, do we have any more insights for algorithm design (improving nonlinear TD), or comments about when we expect NN policy evaluation to work? 

This all reads like: the paper needs a better intro and discussion of the implications and limitations of the results, and indeed this is what the reviewers were looking for. Unfortunately the author response and paper submitted were lacking in this respect. Even the strongest advocates of the work found it severely lacking explanation and discussion.  They felt that the paper could be accepted, but only after extensive revision.

The direction of the work is important. The work is novel, and not a small undertaking. However, to be published the authors should spend more time explaining the framework, the results, and the limitations to the reader.


Decision: Reject