Geometric Insights into the Convergence of Nonlinear TD Learning
Authors: David Brandfonbrener
Joan Bruna
Venue:  (2020)
Keywords: TD
nonlinear
convergence
value estimation
reinforcement learning

Abstract: While there are convergence guarantees for temporal difference (TD) learning when using linear function approximators, the situation for nonlinear models is far less understood, and divergent examples are known. Here we take a first step towards extending theoretical convergence guarantees to TD learning with nonlinear function approximation. More precisely, we consider the expected learning dynamics of the TD(0) algorithm for value estimation. As the step-size converges to zero, these dynamics are defined by a nonlinear ODE which depends on the geometry of the space of function approximators, the structure of the underlying Markov chain, and their interaction. We find a set of function approximators that includes ReLU networks and has geometry amenable to TD learning regardless of environment, so that the solution performs about as well as linear TD in the worst case. Then, we show how environments that are more reversible induce dynamics that are better for TD learning and prove global convergence to the true value function for well-conditioned function approximators. Finally, we generalize a divergent counterexample to a family of divergent problems to demonstrate how the interaction between approximator and environment can go wrong and to motivate the assumptions needed to prove convergence. 

Published as a conference paper at ICLR 2020
GEOMETRIC INSIGHTS INTO THE CONVERGENCE OF NONLINEAR TD LEARNING
David Brandfonbrener
Joan Bruna
Courant Institute of Mathematical Sciences New York University
Courant Institute of Mathematical Sciences
Center for Data Science
New York University
bruna cims. nyu, edu
ABSTRACT
While there convergence guarantees for temporal difference (TD) learning when using linear function approximators, the situation for nonlinear models is far less understood, and divergent examples are known. Here take first step towards extending theoretical convergence guarantees to TD learning with non- linear function approximation. More precisely, we consider the expected learning dynamics of the TD(0) algorithm for value estimation. As the step-size converges zero, these dynamics are defined by a nonlinear ODE which depends on the geometry of the space of function approximators, the structure of the underlying Markov chain, and their interaction. We find set of function approximators that includes ReLU networks and has geometry amenable to TD learning regardless of environment, so that the solution performs about as well as linear TD in the worst case. Then, show how environments that more reversible induce dynam- ics that are better for TD learning and prove global convergence to the true value function for well-conditioned function approximators. Finally, generalize di- vergent counterexample to family divergent problems to demonstrate how the interaction between approximator and environment can go wrong and motivate the assumptions needed to prove convergence.
INTRODUCTION
The instability of reinforcement learning (RL) algorithms is well known, but not well characterized theoretically. Notably, there is no guarantee that value estimation by temporal difference (TD) learn- ing converges when using nonlinear function approximators, even in the on-policy case. The use of a function approximator introduces a projection of the tabular TD update into the class of repre- sentable functions. Since the dynamics of TD do not follow the gradient of any objective function, the interaction of the geometry of the function class with that of the TD algorithm in the space of all functions potentially eliminates any convergence guarantees.
This lack of convergence has motivated many authors to seek variants of TD learning that re- establish convergence guarantees, such as two timescale algorithms. In contrast, in this work focus on TD learning directly and examine its behavior under generic function approximation. We consider the simplest case: on-policy discounted value estimation. To further simplify the analy- sis, we only consider the expected learning dynamics in continuous time as opposed to the online algorithm with sampling. This means that we are eschewing discussions of off-policy data, explo- ration, sampling variance, and step size. In this continuous limit, the dynamics of TD learning are modeled as (nonlinear) ODE. Stability of this ODE is pre-requisite for convergence of the algo- rithm. However, for general approximators and MDPs it can diverge as demonstrated by liitsiikis & Van Roy (1997). Today, the convergence of this ODE is known two regimes: under linear function approximation for general environments (Tsitsiklis & Van Roy 1997) and under reversible environments for general function approximation (Ollivier 2018). We significantly close this gap through the following contributions:
We prove that the set smooth homogeneous functions, including ReLU networks, is amenable the expected dynamics of TD. In this case, the ODE is attracted to compact

---

Published as a conference paper at ICLR 2020
set containing the true value function. Moreover, when parametrization inspired by ResNets, nonlinear TD will have error comparable to linear TD in the worst case.
2. We prove global convergence to the true value function when the environment is "more reversible" than the function approximator is "poorly conditioned".
3. We generalize divergent TD example to broad class of non-reversible environments.
These results begin to explain how the geometry of nonlinear function approximators and the struc- ture of the environment interact with TD learning.
2 SETUP
2.1 DERIVING THE DYNAMICS ODE
We consider the problem of on-policy value estimation. Define a Markov reward process (MRP)
M = (S, 7) where is the state space with |S] = finite, P(s'(s) is the transition matrix, r(s, s') is the finite reward function, and 7 E [0, 1) is the discount factor. This is equivalent to Markov decision process with a fixed policy. Throughout we assume that P defines an irreducible, aperiodic Markov chain with stationary distribution μ.. We want to find the true value function: V*(s) == E 7 rrs, $141)(sp = s). where the expectation is taken over transitions from P The true value function satisfies the Bellman equation:
(*()) Es'=p( ,)[r(s, (s) - >V
(1)
It will be useful think of the value function Pes- (r(s)ss)) s') so that the Bellman equation becomes V = R + PPV*
vector in R" and to define R(s)
The most prominent algorithm for estimating V is temporal difference (TD) learning, form of dy- namic programming (Sutton & Barto 2018). In the tabular setting (with no function approximation) the TD(0) variant of the algorithm with learning rates an makes the following update iteration k ++1: 1:
(s) = (a(s + ap(r(s, s') + +VV(s'') Vi((s)).
(2)
Under appropriate conditions on the learning rates and noise we have that V₂ V as k + co (Robbins & Monro 1951; Sutton 1988). Moreover, under these conditions the algorithm is a dis- cretized and sampled version of the expected continuous dynamics of the following ODE.
(s) μ (R(() + >lE===()> (V'))] V(s)).
(3)
Letting D,, be the matrix with μ along the diagonal and applying the Bellman equation we get
À = DR. pV V) Dv - PV + +VV V) Dr - 7V
We now define
A
(5)
While A is not necessarily symmetric, it is positive definite in the sense that x Ax > 0 for nonzero since 1 (A + AT) is positive definite (Sutton 1988). This can be seen by showing that is non-singular M-matrix (Horn & Johnson 1994p. This then implies convergence of the ODE defined in V regardless of initial conditions.
In practice, the state space may be too large to use a tabular approach or we may have feature representation of the states that we think we can use to efficiently generalize. So, we can parametrize a value function Vg by 0 E Rd. Then, the "semi semi-ggaadent" TD(0) algorithm is
0 O₂ Org VV, (s)(r(s, 8') + VVo, (s') Vo, (s)).
Now by abuse of notation, define V Rdd + R² to be the function that maps parameters 0 to value functions V(0) so that V(0), = (*(). Now, the associated ODE which we will study becomes:
(7) The method is called "semi-grasd sumiiggradent" because it is meant to approximate gradient descent on the squared expected Bellman error, which is not feasible since it would require two independent sam- ples of the next state to make each update (Sutton & Barto 2018). This approximation is what results in the lack of convergence guarantees, as elaborated below.
0 = (V DD, (T)
V²) = - VV ((V V*).
In RL the true value function is often denoted V for policy Our MRP can be thought of as an MDP with fixed policy, is part of the environment and we use V" to emphasize that the objective is to find V*
2

---

Published as a conference paper at ICLR 2020
2.2 CONVERGENCE FOR LINEAR FUNCTIONS AND REVERSIBLE ENVIRONMENTS
There are two main regimes where the above dynamics are known to converge. The first is when (()) is linear and the second when the MRP is reversible so that A is symmetric.
is a classic result of T'stsiikis & Van Roy (997)) that under linear function approximation, where (0) 40 for some full rank feature matrix Φ, TD(O) converges to unique fixed point (the result
also applies to the more general TD(A)) The proof uses the fact that in the linear case, letting become:
0- (0) 2 AV"""', the dynamics
7
T" A -0)) 0*).
The positive definiteness of A gives global convergence to 0".
Recent work has extended this result to give finite sample bounds for linear TD (Bhandari et al.) 2018). Making such an extension in the nonlinear case is beyond the scope of this paper since even the simpler-to-analyye expected continuous dynamics are not understood for the nonlinear case.
Some concurrent work has also extended linear convergence to particular kinds of neural networks in the lazy training regime where the networks behave like linear models (Agazzi & Lu 2019 Cai
al. 2019). The relationship to our work will be discussed in Section
The other main regime where the dynamics converge is when defines a reversible Markov chain which makes TD(0) gradient descent (Ollivier 2018). In that case, A is symmetric so (7) becomes:
V (0)- V
where A must be symmetric to define an inner product. Then for any function approximator this gradient flow will approach some local minima. Note that without this symmetry the TD dynamics in are provably not gradient descent of any objective since differentiating the dynamics get non-symmetric matrix which cannot be the Hessian of any objective function (Maei) 2011).
2.3
AN EXAMPLE OF DIVERGENCE
To better understand the challenge of proving convergence, Tsitsiklis & Van Roy (1997 provide an example of an MRP with zero reward everywhere and a nonlinear function approximator where both the parameters and estimated value function diverge under the expected TD(0) dynamics. We provide description of this idea in Figure 1.
MRP
Tabular
Divergent Example
Reversible
0.5
0.5
0.5
3
0.5
0.5
Figure 1: Each dimension of the vector field diagrams corresponds to the value function evaluated at a state. Here we see only two-dimensional slice of the 3-dimensional function space corresponding to the 3-state MRP. There is no reward so V = 0. The blue vector field represents the dynamics defined by the linear system V -A(V V*). The red spiral represents the one parameter family of functions defined for the divergent counterexample. Using an approximator constrains the dynamics to the red curve by projecting the ambient dynamics (blue arrows) onto the tangent space of the curve (note this projection is not explicitly illustrated in the diagrams). The yellow dots indicate stable fixed points and pink dots unstable fixed points. For the tabular approximator, global convergence to V* is guaranteed since the dynamics are unconstrained. For the divergent example, projecting the vector field onto the tangent space of the curve causes the dynamics to spiral outwards regardless of initial conditions. However, if we use the same function approximator but make the environment reversible, the dynamics on the curve will converge local optimum.
3

---

Published as a conference paper at ICLR 2020
3 TD WITH HOMOGENEOUS APPROXIMATORS INCLUDING NEURAL NETWORKS
Our first result is that the expected dynamics of TD(0) are attracted to neighborhood of the true value function in any irreducible, aperiodic environment when we use a smooth and homogeneous function approximator.
R** Rmm is h-hhmogeneous for h E R if f(x) = (V)())) Note that by Euler's homogeneous function theorem, this equivalent to f((or) = a f(x) for all positive
Definition 1 (Homogeneous). f
Remark 1. The ReLU activation as well as the square and several others are homogeneous. More- over, neural networks of any depth with such activations remain homogeneous. This can be found in Lemma 2.1 of (Liang al. 2017) and we include a proof in Appendix E completeness.
Note that linear functions are also homogeneous and we will show that much like linear functions, the set of homogeneous functions works well with TD learning. At high level, the intuition that the image of a homogeneous mapping from parameters to functions is a set in function space who's h geometry prevents the sort of divergence seen in the spiral example. When V homogeneous, then the point V (0) in the space of functions must lie in the span of the columns of VV (0) which define the tangent space to the manifold of functions. This prevents examples like the spiral where the tangent space is nearly orthogonal to (Ø) for all V(#) in the manifold of functions. However, since homogeneous functions are much more general class than linear functions, the following result is
not quite as strong as the global convergence in the linear setting.
Theorem 1. Let V IRd + Rn be an h--homogenoos function such that (V S C/1111 Let [1V |R T-
B
[1(
Then, for any initial conditions Og if follows the dynamics defined by
1-7
we have
inf [|V S B.
(10)
1-xx0
The full proof is found in Appendix A.1 The main technique is to use homogeneity to see that
dl001 = -V==-0"VV(0)) ((V(()(((( -V) -->= - - ((V()A(((O)) V*). (11)
dt
This allows relate the of the value function the dynamics in parameter space. We can also extend this result to prove that the limsup of the dynamics attains the same bound if we add a stronger assumption that the approximator is bi-Holder continuous. This result in Appendix A.2
One way to think about the theorem is to say that using a homogeneous approximator does at least as well as a baseline given by the zero function. This because B is a potentially tight bound on ||V* - Oll,. but cannot be known a priori since we do not know the expected rewards in advance. Using this intuition, we can change the parametrization of the function to include stronger baseline. We can use linear baseline since we understand how TD behaves with linear approximators. This gives a parametrization that resembles residual neural networks (He et al. 2016) and which we will call residual- homooeeeo-mmooemuuu when the network is also homogencous.
Definition (Residual-homogeneen))
A function f Ra x R2 - R. residual-homogeneon
if (f1( x22) Φz1 + ( where + Rm and g is h--homogeneous.
For this function class, we prove the following theorem, which extend the ideas from Theorem Theorem 2. Let V Idd x dg + I be residual-home homogeneoms function where & is a fill rank feature matrix and [[[()] S Cl]@||e_ Let II be the projection onto the span of &b and let (V- -I, -Ia Il,, Then for any initial conditions Og, 0 follows the dynamics defined
B3
by we have
In [V(()) V' S Bg. 1+000
(12)
The proof is in Appendix A.3 This allows us to bound the quality of the value function found by TD learning compared the linear baseline, but may want to also bound the actual distance to the true value function. Using the above bound relative to the baseline in conjunction with the quality of the baseline,
derive the following corollary, with proof in Appendix A.3
4

---

Published as a conference paper at ICLR 2020
Corollary 1. Under the same assumptions as Theorem 2 we have
1 I|V - -I
lif [IV 1- S (1
(13)
Remark 2. For linear TD, we gel that lim ||
1l S IVV' at the fixed point O* 1-7
[Tsitsikiis & Van Roy 19977. So, our result shows that in terms of the worst case bound, residual- homogeneous approximators perform similarly to linear functions, especially for large %
These are the first results that characterize the behavior of for a broad class of nonlinear functions including neural networks regardless of initialization under the same assumptions on the environ- ment as used in the analysis of linear TD. Our current results resemble those established in the context of non-convex optimisation using residual networks (Shamir) 2018), also obtained under weak assumptions. One direction for future work would be to extend the results from the liminf to limsup to show that the limit exists. Another direction for future work is try to strengthen the assumptions and leverage structure V itself to reduce the space of possible solutions and be able to make stronger conclusions.
4 THE INTERACTION BETWEEN APPROXIMATOR AND ENVIRONMENT
In the previous section we considered a class of approximators for which we can provide guarantees in all irreducible, aperiodic environments. Now we consider how the function approximator inter- acts with the environment during TD learning. Recall that prior work has shown that in reversible environments, TD learning is performing gradient descent (Ollivier 2018). Our insight is that strict reversibility is not necessary to make similar guarantees if also have more information about the function approximator. As seen in the spiral example, the geometric problem with TD arises from the combination of "spinning" linear dynamics from asymmetric Á matrix (i.e. non-reversible environment) with a poorly conditioned function approximator that "kills" some directions of the update towards the true value function in function space. In this section we will formalize this no- tion by showing how we can trade off environment reversibility and approximator conditioning and still guarantee convergence. First we need a way to quantify how reversible an environment is and offer the following definition.
Definition 3 (Reversibility coefficient). Let SA == 1/2(A+ + A and RA == 1/2(A AT) be the symmetric and anti-symmetric parts of A, as defined in equation 5 coefficient p(M) is
Then the reversibility
||AV/ + ||AII
p(M)=
min VER
(14)
RAAV
Note that when the environment is reversible this coefficient infinite since in that case A is sym- metric and R. is zero. The antisymmetric part RA captures the spinning behavior of the linear dynamical system function space (as the spiral example). At high level, more spinning means less reversible environment and larger R. which lowers the reversibility coefficient.
Now we need a compatible way to quantify the effect of the function approximator. To do this, have to examine the matrix VV(0) (O))"" This matrix shapes the dynamics of TD and in the case of neural networks under particular assumptions it is known as the neural tangent kernel (Jacot et al. 2018). The condition number of this matrix gives us one way quantify how much the approximator prefers updates along the directions in function space corresponding to maximal eigenvalues over those corresponding to minimal eigenvalues. This gives us a way to quantify how well-behaved the function approximator is and allows us to prove the following theorem.
Theorem 3. Let x(M) be the condition number of matrix M. Assume that for all 0,
K (VV p(M).
(15)
Then if evolves according to we have that for all 0
( V SA
(16)
where SA 1/2 + AT). Thus, V(0) v regardless of initial conditions.
5

---

Published as a conference paper at ICLR 2020
The proof is relatively simple and proceeds by using the chain rule write out the time derivative of the Lyapunov function and applying the Courant-Fischan Weyl min-max theorem along with the assumption to get the result. The full details can be found in Appendix B
This result provides strong global convergence guarantees, albeit under fairly strong assumptions. It nevertheless provides intuition about how the environment interacts with the function approxi- mation. We show that we can use a nonlinear approximator that generalizes across states by using gradient information long as the condition number of the tangent kernel of the approximator bounded by the reversibility coefficient. Note that for the condition number of the kernel to be finite, the Jacobian must be full rank which means that the function approximator has more parameters than the number of states. Such an approximator has more parameters than a tabular approximator, but can be nonlinear and generalize across states using the structure of the input representation. This opens few directions for future work to formalize the relationship between the environment and approximator in the regime when there are less parameters than states or when the state space is infi- nite. It may be fruitful to connect this to the literature from supervised learning neural networks (see for example example(Oymak Oymak Soltanolkotabi (2019) and references therein), especially in the case of value estimation from a finite dataset (i.e. a replay buffer). Another direction would be to leverage structure in V and the input representation so that the approximator is effectively over-parametrized and similar arguments can be made, but it is not clear how formalize such assumptions.
rer-paaametrized
4.1 EXTENSION TO K-STEP RETURNS
We now consider how the analysis strategy presented above applies to a classical variation on the TD learning algorithm. We find that k-step returns have better convergence guarantees by increasing the reversibility of the effective environment. This not completely surprising since in the limit k: - co we recover gradient descent in the μ-norm with the Monte Carlo algorithm for value estimation. However, we show that our sufficient condition to guarantee convergence in the well-conditioned regime weakens exponentially with k. In Appendix[C we show that with k step returns the dynamics of the algorithm become
i -= -1- -
(17)
We can define notion of effective reversibility that scales exponentially with k such that we recover the same type of convergence as Theorem 3
whenever
": <VVV())VV())))) Pmiin (1 **) (T)2(P)))
(18)
Pmaz
where (P) is the second largest eigenvalue of P. which is strictly less than I under our irreducible and aperiodic assumption. This result shows how using k-step returns to increase the effective
reversibility of the environment can lead to better convergence properties. See Appendix C for more precise statement of the result and its proof.
4.2 NUMERICAL EXPERIMENT ON THE DIVERGENT EXAMPLE
We perform small set of experiments on the divergent spiral example from Section 2.3 which support our conclusions about reversibility and k-step returns. We integrate the expected dynamics ODEs in two settings, one where we introduce reversibility into the environment and the other where we increase the value of & in the algorithm. The function approximator is always the spiral approximator from the example. We can introduce reversibility by adding reverse connections the environment with probability 5 E (0, 0.1, 0.2, 0.23) as shown in Figure This effectively reduces the spinning the linear dynamical system in function space defined by the Bellman operator. We find that increasing reversibility eventually leads to convergence. We also validate the result that increasing will lead to convergence by increasing the effective reversibility without changing the MRP. Note that the spiral example is outside the assumptions of the theory in this section since the function is not well-conditioned. but we wanted to show that the connection between reversibility and convergence may extend beyond the well-conditioned setting.

---

Published as a conference paper at ICLR 2020
0.5
Varying delta
Varying
Reversibiiity
120
22:97
120
0.5- 6
0.5 8
Datance
198. 74
1236 85
Distancc to
1.0
80
60
2
40
40
0.5 5
0.5
0.5
Time
Time
Figure 2: Left: the Markov chain used for the experiments labeled with the transition probabilities. Center: the spiral divergence example in progressively more reversible environments. stronger re- verse connection makes the environment more reversible and eventually causes convergence. Right: The impact of using stepp returns. We use for all values of k and get convergence for k = 3.
5 A GENERALIZED DIVERGENT EXAMPLE
To motivate the necessity of assumptions similar to the ones that we have made we can look again to the spiral example of (Tsitsiklis & Van Roy 1997). Here we generalize this example to arbitrary number of states for most non-reversible MRPs. Our construction allows for approximators with arbitrary number of parameters, but restricts them to have rank deficient tangent kernels to mimic
the spiral in 2-D subspace of function space. The construction can be found in Appendix D and the result can be described formally as follows.
If the MRP is not reversible such that = Da(1 -PP) has at least one non-real eigenvalue, then there exists a function approximator V such that TD learning will diverge. That is, for any initial parameters Gg rank up to n - 1, where n is the number of states, for all 6.
Proposition 1.
we have (0V V*I - Moreover, (0) can have
The construction of the approximator in the counterexample is somewhat pathological, but any con- vergence proofs have to make assumptions to rule out these divergent examples. In this work we avoid these by using either smooth homogeneous functions by using well-conditioned functions in nearly-reeersible environments. While there may be other assumptions that yield convergence, they must also account for this class of divergent examples.
RELATED WORK
6.1 CONNECTIONS TO WORK IN THE LAZY TRAINING REGIME
Concurrent work (Agazzi & Lu 2019) has proven convergence of expected TD in the nonlinear, non-reversible setting the so-called "lazy training" regime, in which nonlinear models (including neural networks) with particular parametrization and scaling behave as linear models, with a kernel given by the linear approximation of the function initialization. Whereas this kernel captures some structure from the function approximation, the lazy training regime does not account for feature selection, since parameters are confined in a small neighborhood around their initialization (Chizat & Bach 2018). Another result in similar direction is from concurrent work (Cai et al. 2019) which considers two-layer networks (one hidden layer) the large width regime where only the first layer is trained. They show that this particular type of function with fixed output layer is nearly linear and derive global convergence in the limit large width with an additional assumption on the regularity of the stationary distribution. In contrast with these works, our results account for feature selection with more general nonlinear functions. Our homogeneous results hold for broad class of approximators much closer to those used in practice and our well-conditioned results hold for general nonlinear parametrization and provide useful intuition about the relationship between approximator and environment.
7

---

Published as a conference paper at ICLR 2020
6.2 CONNECTIONS TO WORK ON FITTED VALUE ITERATION
Another line of work provides convergence rates for fitted value iteration or fitted Q iteration under the assumption of small optimization error at each iteration (Munos) 2007 Munos & Szepesvári 2008 Yang et a (019b). These papers give bounds that depend on the maximum difference be- tween the function returned by the Bellman operator applied the current iterate and its projection into the space of representable functions (which they call the inherent Bellman residual). This as- sumption means that priori the function class has geometry amenable to the MDP being evaluated. Here we do not rely on any assumptions about successful optimization or an assumption that the projection of the tabular TD update into the space representable functions uniformly small. Instead we find scenarios where we can guarantee that the difference between the tabular update and projection cannot be too far so that the optimization procedure succeeds.
6.3 ALTERNATIVE VALUE ESTIMATION ALGORITHMS
There are several papers that introduce new algorithms inspired by TD learning but modified so as to have provable convergence with nonlinear approximators. To our knowledge, all of them use either timescale argument where the optimization procedure at the faster timescale views the slower timescale as fixed (Borkar 1997| 2008 or they attempt to optimize a different objective function (Baird 1995). Most of the algorithms have not seen widespread use, potentially because these modifications make optimization more difficult or decrease the quality of solutions. More specifically, |Baird (1995) present residual algorithms, which attempt optimize different objective which avoids double sampling, but has incorrect value functions as solutions (Sutton & Barto 2018).
Bhatnagar et al. (2009) present GTD2/TDC which uses two timescales to perform gradient descent on the norm of the TD(0) dynamics projected onto the image of the nonlinear approximator in (2018) and
function space and thus has the same fixed points as TD(0). More recently, |Da et al., Chung et al. (2019) present two timescale algorithms which are provably convergent. Yang et al. (2019a) characterize target networks, which have seen widespread use (Mnih et al. 2015). as a two timescale algorithm. Finally, while they do not provide guaranteed convergence with nonlinear functions, Achiam et al. (2019) present an algorithm that uses a similar observation to ours about the connection between TD- with nonlinear functions and the neural tangent kernel. Their algorithm then estimates a preconditioning matrix that serves a similar function as the two-timescale argument. In contrast to this line of work algorithmic modifications, our work is first step towards characterizing the behavior of nonlinear TD without two timescales or a modified objective.
6.4 EMPIRICAL WORK
Recent empirical work by Fu al. 2019) empirically investigates the interaction between nonlinear function approximators (neural networks) with Q-learning, which is a semi-gradient algorithm that similar to TD. They find that divergence is rare and that more expressive approximators reduce approximation етror and reduce the chances of divergence. Since these more expressive approxima- tors are more likely be well-conditioned, this gives reason believe may be possible to extend our convergence results from the well-conditioned setting for very expressive approximators to more realistic approximators.
7 DISCUSSION
We have considered the expected continuous dynamics of the TD algorithm for on policy value es- timation from the perspective of the interaction of the geometry of the function approximator and environment. Using this perspective we derived two positive results and one negative result. First, we showed attraction to compact set when homogeneous approximators like ReLU networks. The worst case solution in this set is comparable to the worst case linear TD solution for particular parametrization inspired by ResNets. Second, we showed global convergence when the environ- ment is more reversible than the approximator is condly-condiiioned. Finally, we provided gener- alized counterexample to motivate the assumptions necessary to rule out bad interactions between approximator and environment.
There are several possible directions for future work. First, while our results extend both the linear and reversible convergence regimes, they do not close the gap between the two. One direction for
8

---

Published as a conference paper at ICLR 2020
future work is thus to provide unifying analysis that would neatly connect all of the convergent regimes. Next, it may be possible to find more precise notion of the well condiitoii necessary to get local convergence rather than global convergence which would allow extension to more realistic settings. It may be possible to leverage assumptions about regularity of the true value function so that the function class is effectively well-conditioned. Another direction is that, while it was beyond the scope of this paper, it would be instructive to extend the results to finite sample results as has recently been done for linear TD. would also be interesting extend the results off-policy and Q-learning settings, but likely would require stronger assumptions. Finally, we would like to motivate future work by noting that the ultimate goal of this line of work is put TD on the same solid footing as optimization in supervised learning where we can characterize easy problems (by convexity), can guarantee convergence even in hard problems (to local minima), and have some notions of how to make optimization easier (like over ver-paraametrizttion) Here we have taken step towards this kind of analysis, but the precise characterization of what makes a problem easy and whether and where TD converges on hard problems remain incomplete.
ACKNOWLEDGMENTS
We would like to thank Yann Ollivier for helping to inspire this project and for sharing some his notes with us. We also thank the lab mates, especially Will Whitney, Aaron Zweig, and Min Jae Song, who provided useful discussions and feedback.
This work was partially supported by the Alfred P. Sloan Foundation, NSF RI-1816755 NSF CA- REER CIF 1845360, and Samsung Electronics.
REFERENCES
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards Characterizing Divergence in Deep Q-Leaming, arXiv e-prints, art. 19X3vv1903.08800 Mar 2019.
Andrea Agazzi and Jianfeng Lu. Temporal-diifereence learning for nonlinear value function approxi- mation in the lazy training regime. CoRR, abs/1995.10017 2019. URL. http:/ttp////xi.rrrr///
1os/1905.2o 10917
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. finite time analysis of temporal difference learning with linear function approximation. arXiv preprint arXiv:1806.00 000100240000 2018.
Shalabh Bhatnagar, Doina Precup, David Silver, Richard S Sutton, Hamid R. Maei, and Csaba Szepesvári. Convergent temporal-difference learning with arbitrary smooth function approxima- tion. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems 22, pp. 1204 1212. Curran Associates, Inc., 2009.
Vivek S. Borkar. Stochastic approximation with two time scales. Syst. Control Lett., 29(5):211- 294, February 1997. ISSN 0167-6911. doi: 00.1006/90166--6611199999011 00:000166666900 6911 (97) 90015-3
URL http:
/ //dx. doi. www.oo..................o....... /00.
V.S. Borkar. Stochastic Approximation: Dynamical Systems Viewpoint. Cambridge University Press, 2008. ISBN 9780521515924. URL Inttps://boot
QLXIvgAACAAJ
Qi Cai, Zhuoran Yang, Jason D. Lee, and Zhaoran Wang. Neural temporal-difference learnn converges to global optima. CoRR, abs/1905. 10027, 2019. URL http::://axx...oo////aa///
1905. 10027
Lénaïc Chizat and Francis Bach. A Note Lazy Training in Supervised Differentiable Pro- gramming. working paper or preprint, December 2018. URL https: inw.aainiiii....................
ha 00- 01945778

---

Published as a conference paper at ICLR 2020
Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White. Two-timescale networks for nonlinear value function approximation. ICLR, 2019.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED: Convergent reinforcement learning with nonlinear function approximation. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1 1125-11344 Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http::htt///p/oeeeee ngs. press// 38C/da118c.ho html
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing Bottlenecks in Deep Q- learning Algorithms, arXiv e-prints, art. 190.:1992..105000 Feb 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Roger A. Horn and Charles R. Johnson. Topics in matrix analysis. Cambridge University Press, Cambridge, 1994. ISBN 0-521-46713-6. Corrected reprint of the 1991 original.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Tengyuan Liang, Tomaso A. Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geometry, and complexity of neural networks. CoRR, abs/1711.01530, 2017. URL http:// wwt.://orrabbb//111s. 01530
Hamid R. Maei. Gradient lemporal-differene learning algorithms. University of Alberta, 2011.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep rein- forcement learning. Nature, 518(7540):529-333 February 2015. ISSN 00280836. URL http://dx. doi. org. 10. 1038 http/nuuuuueeeeee
Rémi Munos. Performance bounds in In-norm for approximate value iteration. SIAM J. Control and Optimization, 46(2):541-5611 2007.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Much. Learn.
Res., 9:815-857, June 2008. ISSN 1532-4435. URL
cfm?1d=13906B1 1390700
Yann Ollivier. Approximate temporal difference learning gradient gescent for reversible policies. CoRR, 0ttss/885.00080 2018. URL
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparametterization:: global conver- gence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.04677 2019.
H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407 1951.
Ohad Shamir. Are resnets provably better than linear predictors? In Advances in neural information processing systems, pp. 507-516, 2018.
Richard S. Sutton. Learning predict by the methods of temporal differences. Mach. Learn.,
(1):9 44, August 1988, ISSN 0885-6 688856615.... doi: 00.1023/A:10022333334499 URLhttp://dxx. doi www.rrg/11 /0. 1123//...222333111777777
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, USA, 2nd edition, 2018.
10

---

Published as a conference paper at ICLR 2020
John N. Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffference learning with fune- tion approximation. In M. C. Mozer, M. I. Jordan, and T. Petsche (eds.), Advances in Neural Information Processing Systems 9. pp. 1075-1081. MIT Press, 1997.
Zhuoran Yang, Zuyue Fu, Kaiqing Zhang, and Zhaoran Wang. Convergent reinforcement learn- ing with function approximation: A bilevel optimization perspective, 2019a. URL https:
Zhuoran Yang. Yuchen Xie, and Zhaoran Wang. A theoretical analysis of deep q-learning. CoRR, abs/1901.00137, 2019b.
http://awwv..oogaa//////000 00137

---

Published as a conference paper at ICLR 2020
A TD WITH HOMOGENEOUS APPROXIMATORS
A.1 PROOF OF THEOREM 1
Theorem 1. Let V Rd _ be an fi-homogeneous function such that IV S C/1001.. Let [1 (PV-PP |RR. 1-y I-y" B
Then, for any initial conditions 0,, if f follows the dynamics defined by
we have
lim inf (|V S B.
(10)
1-000
Proof. Applying the chain rule, 7 and the homogeneity assumption we get that:
d| QT 8 VV(O)) A(V(0) VV) = =- A V*).
For any c O, whenever B c [(-НP) In +c<||V(()])) have that
1-7
IV(0)* A 7PM
< <11-))]V((01; c(1 -))
$ [ - -
(B
I (1)0)",,(0)-~~V00"),,,
for c = (11-7)) (B + +)
The last inequality follows from an application Lemma of
Tsitsiklis & Van Roy 1997) that
|| I ,|V||, along with Sauchy-Schwarz show that:
(0) DV D( D (V) S [V(())..)PP())) s (I)
D,,
Putting this all together we get that whenever B + [()]|, we have that
a!llll dt S h (V AV - (V) AV
C <. h
Put another way, we can define (0: dil0 - and W (V ||]] S B Bee.. By the
above, we have that (U)) C W where V(U) is the image of U under V, i.e. (V :3:300 U s.t. V==
de
V(0)). Now define O (0 C/ < B -B+ c} which contains an open ball around the origin. By our Holder continuity assumption, we know that (OO C W.
Putting all together, if 0 & U at time f, the dynamics |0]|² are contracting faster than e/h so that there exists finite T >> such that at time T' the parameters ((T)) will either be in O or U, either way implying ((0) will be in W. Since the above reasoning held for any e > 0, taking the liminf can take - 0 which yields the result.
A.2 BI-HOLDER HOMOGENEOUS STABILITY
Proposition 2. Let V= : Rd + RR be h--homogenooss Moreover, assume that c|10|| < [V(0)) < ||]]].
C'101]" for some c, s, C Let [(I-9))V'1,
1-7 Then, for any initial conditions fo.
1-7
0 follows the dynamics defined by 7 we have
lim sup [|]()) S C(B/O//4 b0x
(19)
Proof. Using the same reasoning as above without the additional get that whenever B (1-PPV" lns [[V()) we have
IVO)T AV V(O)T AV(0)-
So, whenever B [V(())) have that d|l0
0.
12

---

Published as a conference paper at ICLR 2020
Define O- (0 c||0|| < B). Thus, by the lower Holder bound, < have that as / -> oc, 0 E O. And, by the upper Holder bound, if 0 E df
< for all 0 & O. So, we
then
[|V(O) I max C/10'II" & C(B/c)
d'EO
Since, 8 E O in the limit, we get the desired result.
A.3 PROOF OF THEOREM 2 AND COROLLARY
Theorem 2. Let V Rd. Rd + IRt be priidual-omogeneonee function where Tp is a full rank feature matrix and [0) S C' Let 1l,, be the projection onto the span of & and let Bg [V-)P)(V" - Vil,,, Then for any initial conditions On. 0 follows the dynamics defined
by we have
lim inf [V(00) IT, Vl S Bo. 1+000
(12)
Proof. Let f be homogeneous and
( = V(0,, = + f(02)
Let 0- I1 V be the best linear predictor. In fact, the proof would go through for any 0% only the bound gets worse for worse choice of 0g.
Note that
d|@
- -07, (V A(V(0)) V*)
dt
= ( 01) + S -0)=00)) A(V(0) V*) 0))
= -V((0)) -60)) A(V(0) - -607) -V((0) - +00)) A(00T - V*).
The residual parametrization is necessary here to have the linear part of DV independent from 0 so that we can turn the difference 0, 0j into a difference between functions.
As in the proof of Theorem for any > 0 we get that whenever Bx + < IIV(0) - D01
(V) T A(
V - [V((0) - 467 |IT P) - V*)
- (1->))[V(()) 201 <(1 V V -00 l|
< [[V(0) - -407 12 - vl) - 20 1: - -6(1 - () + E)
< [[V 400 1 >(V(0) +01) D2 P(V - +00)
(V(0) - -D0)) ((( 207) c.
As consequence we can conclude that whenever Bs + < (V &01
d (01.0)12
dt < cchh
To conclude the proof, we can define U = {0 dl1e-(0,0)
2 - c//h} and W = (V V 10 B + +). Then we have that VLU) C W. Now define O ((0,0) + 0: C|I@I < B B
which contains an open ball around (07.0) 0). By our Holder continuity assumption and the residual
parametrization of V, we know that V(O) C W.
Putting it all together, if & U at time f, the dynamics of |0|| are contracting faster than c/ h so that there exists finite T such that at time T the parameters ((T) will either be in O U, either way implying (0) will be in W. Since the above reasoning held for any e > 0, taking the liminf can take which yields the result.
Corollary 1. Under the same assumptions as Theorem
2 we have
1 1
lim inf (V - V* s (1 t+x
||
V'
(13)
13

---

Published as a conference paper at ICLR 2020
Proof. Applying the triangle inequality and the result of the Theorem, get that
lim inf (IV Vl
lim (I) II Vl 1| | V V*(
1-000
2-300
lim inf [V 11.. V*I,
Il + 11 V*
20000
S B + [1
[[ V
V*I
Then, we note that || pPl S + since P is a stochastic matrix which lets us bound Bg by
[1 V* V Putting this together with the above yields the result.
B CONVERGENCE IN THE WELL-CONDITIONED SETTING
B. PROOF OF THE THEBOREM
Theorem 3. Let r(M) be the condition number of matrix M. Assume that for all 6
<(VV(()VVV()))) < p(M).
(15)
Then i evolves according to we have that for all 0
dll V 11
(16)
where SA = 1/2AA AT). Thus, V(0) V regardless of initial conditions.
Proof. To simplify notation, use S for SA and R for RA. We define L : 12d - R which will be the Lyapunov function for the dynamical system as
L( = [V(0) v
By applying the chain rule and the polarization identity to we have
(0) -V,
-\))
-IV((O) ((V V*) (V(()= V\), A(()) -(V)))
= [IVV(O))A(((() - V*)12
-1 1 (VV - ())((())))))))))-))))))))))))))) V\)1
= -
where R = 1-2(AA ) So using the assumption and then the min-max theorem,
K< (VV())VV((0))>>> < ((M)
AmaX VV(()VV())>)) V²) < Amn (VV (1A(V()) V+ -V))))
(VV -V* < V (VV(') V*)]|
where Amax Amin are the maximal and minimal eigenvalues. Combining, we conclude that i.(0) O and the result follows.
B.2 CALCULATING THE REVERSIBILITY COFFFICIENT
The reversibility coefficient can be seen as the minimizer of generalized Rayleigh quoticnt (Hom
& Johnson 1994). Such quotient for Hermitian matrices B, C is defined as Rn,c(u)
x² Rv.
And when C' is full rank, we know that this is maximized by the maximal eigenvalue of C-1.. In our case, this gives us a way to calculate the reversibility coefficient as
Ammax (IST + A
RTRA) (20)
P(M)
max (EE=\(()
S 2
2
14

---

Published as a conference paper at ICLR 2020
C K-STEP RETURNS IN THE WELL-CONDITIONED SETTING
C.1 EXPECTED DYNAMICS DERIVATION
The k-step return variant of TD learning replaces r(s, s') + <Ve('') in the original algorithm O by
Σk-1 I'r(st, 81+1) + 7t (V((())) To get the continuous matrix version of the dynamics we replace R witt V pPV* in the following expression get a telescoping series that
k- V
Σ DDPYR+ = - V --)- t
-V).
Thus, we can define the TD(k) dynamics by
i = DV-
(21)
C.2
EFFECTIVE REVERSIBILITY
To draw the comparison to the TD(0) algorithm analyzed in the paper, we define the matrix
Ax == D, ()
Now we take symmetric and asymmetric parts S - (AA + A and Rs = ]{A,= - AL). Then we can define reversibility in this effective environment. Definition 4 (Effectivv reversibility coefficient).
SS ||AV||
Pi (R(M)= = min VER"M(0
(22)
R
C.3 CONVERGENCE PROPOSITION
Proposition Let (P) be the modulus of the second largest eigenvalue of P, which strictly less than by our irreducible, aperiodic assumption. Then
Pmin (1 - -/) (772(P))) S PM(M)
(23)
Mmaz
V
And if follows the ODE defined by
21 then
whenever
d8
Mmin (1 *t) (T)2(P)))*
(VVV
(24)
Mmax
As a consequence, as long NN (VVV is finite there exists k sufficientll large guarantee convergence to V* regardless of initial conditions.
Proof. To extend Theorem this result, we will show that
Pmin (1 - )*)
||&AV|| (O) [ S (M)
(x22
min
Pmax
First, since R4 PT - (p(PP))) we have R&1 0 since D,, is the stationary distribu- tion that (12) DD,1 Ph p.. So only need to consider V 1. Now, have
RRVI 2 (
"mmaa (>e()))
where A is the eigenvalue with second largest magnitude (since is the largest eigenvalue, but it has eigenvector 1 for P and μ for PT)) And we have
S&VI| 2 Amin )m > (Nmin - Mmnin)]
by the Gershgorin circle theorem since pk defines distribution with stationary distribution D,, so that subtracting the off diagonal from the diagonal of A we get Amiin (As) 2 bz EE 7 DD, Pb
15

---

Published as a conference paper at ICLR 2020
[4; 14--"1u for all i. Since an analogous argument applies to the columns of Ag, get the above bound on the eigenvalues of Sk. Dividing the bounds we get the first result.
Then by Theorem 3 we get the second result that - Moreover, the global convergence follows for some sufficiently large & since the effective reversibil- ity coefficient is increasing exponentially with k.
< O when the condition holds.
df
D GENERALIZED DIVERGENCE CONSTRUCTION
If the MRP is not reversible such that A DI(I-~93 has at least one non-real eigenvalue, then there exists a function approximator V such that TD learning will diverge. That is, for any initial parameters Oo, as - oo we have [IV - V*Il - Co. Moreover, VV (0) can have rank up to 1, where n is the number of states, for all 6.
Proposition
Proof. Since A is real, having one non-real eigenvalue implies that A has pair of complex eigen- values a + bi, a - corresponding to eigenvectors V1, V2. We know that > 0 since A a non-singular M-matrix and that U = (U) U2). Note that U1, U2 are linearly independent since V1, V22 are so that U is full rank and
by assumption. Define U1 Re(Vi) and U2 Im((V) and
b) that AU = (-b o)
To construct a divergent approximator, define
Q := = -==U(U² (=8 b -.) (U UU
so that Q is matrix of rank with range equal E span (an U2}.
For any V E E so that V = U
we have || < C(x² + y²) with C > 0. Then
VTQTAV AV = (x VUTTUTT
(=o
b
(UT
b)
-a
- a
a +
|V
-x (x y)
< (a² + +
a² + b²
C
Thus, Q² A is matrix of rank 2 with eigenvectors Vi, 1/2 and eigenvalues (a² + b2) (a² + 12)i. Choosing Vo in the span of V1, V22 we define for E R:
V el E span [V, VV, 1/2)
Then for V = O, we aply the above to 7 to get
(O) AV (0) (O0 + (T)AV(0) > 0
as long as E < (a2 + b3)CC and (()) + 0. This gives us divergence since as + oo we have [[V(0) co.
Now we just need to show that we can make (V(0) rank n - To do this we will note that define any function V()) from Rdd - E- for any number of parameters and still get divergence if we use the function approximator V'(e, 0) = (Ø)). This is because @v' (C++Q)V(L) (0) L (V so that Ó remains strictly above 0 as before. implying divergence. With this construction, we can build a divergent approximator V" on n states with VV' 0) of rank -
de
everywhere. For example, set d n 2 and let (()) be the identity function.
E NEURAL NETWORKS ARE HOMOGENEOUS
Lemma 1. (Liang al. network f R. 12t by
2017 Let IR R. be h-homogeneous. Then define homogeneous
f(01,... ,0)) af ( ..0)))
(25)
16

---

Published as a conference paper at ICLR 2020
where 0g is a dj-1 d1+1 matrix and & is the x p matrix of data points and is applied compo- nentwise. Then for all i
f(0) = hー- 1-1 (f(
L
vec(O,)
and
=(0) - -00=V1((0)))
Σ W4-it/IL
(26)
Övec(B.)
where vec maps the matrices to vectors while 0 R is already vector.
Proof. We will consider = and note that the result applies for arbitrary by applying the result each component function f.
Define g' (:) = ((... ( )02)).))::))............... ...0. 0..0-1)6, which we will denote simply g' so that we have f = (gg). Note that g¹ is dx+1 dimensional vector and d+t1 (o.,..... ........;..))) (a.
Defnn
(000 (+0)))))) ... 1)- and denote it I so that f o(g'). Let fo be @. Now we proceed by induction on the gap j i for j 2 from to 1.
As the base case, consider i = Then we have that
0fú @vec(0,)
Ofa 0g' 0gi @vec
0fg dgi
vec(0:)
(0000)=)
(0t)ac
0ge (00)brr
b.c
ff
dgi
Og' a(0;)bn ba
(0e)ve = - Σ
(0,)ba
Ig'. a(0;)
b.c
= o''(ii (1ia) Σ 1b (0:)oa =o' o'(su)9
1
h J.
1
h
Make the inductive assumption that for j - -i = k 2 O we have for S di+1
ff vec(0.) h fd Ovec(O;)
1
Now consider j - i= + 1. We have
ffg
0f2 afi-1
1
0f -1
vec(0,) = 0fj-1 @vec(0,)
vec(O.)
8/-1
(ve)
= hk+l
hk+t ΣΣ 012 Ogk
1/- 11
h++1 Σ o'
0g 0f
1
ht4 o' (o)) = h²t2 fd
Taking j = L gives us the first result that f(0) = h h-i++ a/10)
vec(f.). Summing over the L
Ovec(e,)
choices of i gives /(0) = v El_ h /b--+1//T.
17


Reviews:
[{"review_id": "rJl4tiBa9S", "reviewer": "AnonReviewer4", "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 establishes a theoretical insight into Temporal Difference (TD) learning for policy evaluation, on the convergence issue with nonlinear function approximation. It proposes that for a so-defined class of “homogeneous” function approximators, the TD learning will be attracted to a “neighborhood” of the optimal solution. While this seems an important work, I am uncomfortable to give an accept decision because the statements of the results can be found inaccurate from place to place. I actually found it is a bit confusing to use this wording (from the paper). For example, with neural networks, there is still approximation error and local minima issue, how could you say that the update is absorbed into a neighborhood of the true solution? And this is claimed in the beginning of Section 3.\n\nTD learning follows a biased estimate of the gradient of the squared expected Bellman error, which\nis minimized by the true value function. The bias is intrinsic to the fact that one cannot obtain more\nthan one independent sample from the environment at any given time. As it turns out, this bias\ncan be seen geometrically as “bending” the gradient flow dynamics and potentially eliminates the\nconvergence guarantees of gradient descent when combined with nonlinear function approximation.\n》》 I don’t know what this means. TD diverges with nonlinear FA just because the contraction mapping does not hold any more. \n\nsuch as two timescale algorithms, but these algorithms are not widely used\n>>this argument is a bit weak. \n\nWe prove global convergence to the true value function when the environment is “more\nreversible” than the function approximator is “poorly conditioned”.\n>>not clear what this means until here. What is “reversible environment”, what does it mean FA is “poorly conditioned”? Later in Section 2, it was mentioned “MRP” is reversible so that some matrix is symmetric. \n\nSection 2:\n\nEquation 1 uses V^* is a bit inconsistent ( P is used). Why not use V? V^* usually means the optimal value function. I saw your footnote, but remember value function is “associated” with P. \n\nConvergence to V* immediately follows. – What convergence? I thought you were talking about stability of the ODE. \n\nthe “semi-gradient” TD(0): do you mean tabular TD(0) is not semi-gradient? Do you think it is gradient? Even in tabular, it is not gradient descent. \n\nV(\\theta)_s: this notation is odd. \n\nit is meant to approximate gradient descent on the squared expected Bellman error:  This is arguable. Actually it is not precise. One can say it is true and others may say it’s not. This is never an established result or acknowledge showing that TD is an approximation to the gradient descent on the mean squared Bellman error.  \n\n\nThe first is when V is linear and the second when the MRP is reversible so that A is symmetric.\n>>this is ambiguous. Do you mean the second case is when V is nonlinear and the MRP is reversible? I am guessing this is what you mean. And it’s true. \n\nSection 2.3: doesn’t carry much value. The example is from the paper cited (Tsitsiklis and Vanroy 1997). Adding the symmetric case for P doesn’t give much value because that’s easily seen to be true. \n\nDefinition 1: “homogeneous”. This is not the usual definition of homogeneous in mathematics. Square function is.  Relu: gradient at 0 exist?\n\n Section 4.2: experiments about modifying the spiral example into symmetric MRP is not very interesting, because symmetry brings obvious convergence guarantee. However, it is good to see the experiment with a variable delta that controls the level of symmetry.  \n\nI think a missing experiment is the showcase for the divergence examples the case of “homogeneous” function, such as the square function and the neural networks (as claimed in the paper, these are “homogenous” functions). How does the behavior that the TD update is absorbed into the “neighborhood” of the true value function? \n\n\n\n\n\n\n\n ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HygHpb4qcr", "reviewer": "AnonReviewer2", "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 analyses the convergence of TD-learning in a simplified setup (on-policy, infinitesimally small steps leading to an ODE).\n\nSeveral new results are proposed:\n- convergence of TD-learning for a new class of approximators (the h-homogenous functions)\n- convergence of TD-learning for residual-homegenous functions and a bound on the distance form optimum\n- a relaxation of the Markov chain reversibility to a reversibility coefficient and convergence proof that relates the reversibility coefficient to the conditioning number of grad_V grad_V^T.\n\nWhile the theory applies to the ideal case, t provides some practical conclusions:\n- TD learning with k-step returns  converges better because the resulting Markov chain is more reversible\n- convergence can be attained by overparmeterized function approximators, which can still generalize better than tabular value functions.\n\nThe experiments corroborate the link between reversibility factor and TD convergence on an artificial example.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HkxUUm6Tcr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "What is the specific question/problem tackled by the paper?\n\nThe paper studies convergence & non-divergence of TD(0) with value function estimates from the class of ReLU deep neural nets (optionally with residual connections). \n\nIs the approach well motivated, including being well-placed in the literature?\n\nYes.\n\n\nDoes the paper support the claims? This includes determining if results, whether theoretical or empirical, are correct and if they are scientifically rigorous.\n\nThe support is adequate.\n\n\nSummarize what the paper claims to do/contribute. Be positive and generous.\n\nThe paper takes a first step in bridging the gap between existing analyses of TD(0): convergence with linear function approximators, and convergence in reversible MRPs. The first contribution is a non-divergence result for the method with ReLU deep neural networks with and without residual connection. The second result connects a notion of reversibility of an MRP and the condition number of the neural tangent kernel, saying that better conditioning can make up for the lack of reversibility.\n\n\nClearly state your decision (accept or reject) with one or two key reasons for this choice.\n\nI vote for accepting the paper.\n\n\nProvide supporting arguments for the reasons for the decision.\n\nThe paper is well written, with a clear story and accessible explanations. The paper provides novel results and an interesting line of work that allows us to tradeoff good behavior of the function space and of the MRP in order to have TD converge, in the sense that as the MDP becomes less and less reversible we can make up for it by having properly conditioned matrices.\n\nThe paper also makes an adequate choice of function space to restrict the guarantees to.\n\n\nProvide additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\nIt seems that Theorem 3 cannot recover the linear case results for properly conditioned Phi matrices and irreversible MRPs. It would be good if the result could really interpolate between the two previously studied cases (linear irreversible and nonlinear reversible). Alternatively, a comment about this limitation of the result would improve the paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1eT1g545S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\n####\nA. Summarize what the paper claims to do/contribute. Be positive and generous.\n####\n\nThe paper characterises the convergence of Temporal Difference learning for on-policy value estimation with nonlinear function approximators. It looks at a few classes of functions which include Deep ReLU networks, with and without residual connections. It looks at how a few aspects of function approximators affect their convergence properties, and how these are intertwined with a property of the environment.\n\nThis topic is important for improving the theoretical understanding of Deep RL. The paper provides a series of mathematical results which will be interesting for the community as they are well-motivated, intuitively explained, and of clear practical relevance.  The paper works within a simplified setup that is however NOT toy. It makes reasonable simplifying assumptions to avoid confounding issues with exploration, off-policyness of data, and stochastic optimization. Within a continuous-time MRP framework they show that:\n\n1. When a particular class of function approximators known as homogenous functions (e.g. Deep ReLU networks) is used, the error on the state value function can be bounded. Tweaking the class of function approximators by making them like residual networks (residual-homogenous) obtains a bound similar to known bounds for linear function approximators.\n\n2. It is known that TD(0) converges with linear function approximators and arbitrary environments. It is also known that TD(0) converges with arbitrary function approximators when the environment is fully reversible. This paper shows that there is in fact a tradeoff between how well the function approximator is conditioned and how reversible the environment is (for particular definitions of well-conditionedness and the \"extent\" to which an environment is reversible). This nicely links up known theory and is especially relevant for practitioners who would like to apply neural net function approximators in arbitrary environments.\n\n3. They show that using n-step returns instead of TD(0) returns can have a similar effect to the environment being reversible. That's a nice insight. \n\n4. There is a classic counterexample for TD(0) with a nonlinear function approximator diverging. The paper makes this example more general which more clearly demonstrates how/why convergence fails beyond the single pathological example whose relevance to real neural nets was hard to determine. It makes it clear that a necessary condition for convergent TD learning with function approximators is dodging this more general class of divergent example.\n\n5. The theory is supported by (toy) experiments, whose empirical results suggest the theory can be made more general (e.g. to include more classes of function approximators). \n\n####\nB. Clearly state your decision (accept or reject) with one or two key reasons for this choice.\n####\n\nThis paper should be accepted because the results are interesting, relevant, novel (as far as the reviewer understands), well-explained, and as far as the reviewer can tell correct (though I have not scrutinized the proofs in the appendix).\n\nThe paper is interesting and easy to read (even for someone without background in proving the convergence of RL algorithms).\n\n####\nC. Provide supporting arguments for the reasons for the decision.\n####\n\nWhether or not (and under what conditions) TD(0) converges is an important object of study for the Deep RL community, which is well-represented at ICLR. The results shown here should be more widely known.\n\nGood intuitions given for the mathematical results in addition to proofs (e.g. why homogeneity prevents divergence).\n\nThis work contributes to the understanding of Deep RL and could eventually lead to actionable theory which lets us design more robust RL systems (with insights about the coupling between learning algorithm, function approximator, and environment).\n\n####\nD. Provide additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n####\n\nD0. My main critique is that the results are somewhat disparate. How does homogeneity or residual homogeneity relate to the conditioning number of the neural tangent kernel? Can these all be connected up better?\nD1. Be more clear in Remark 1 on page 4 that the homogenous property applies to *deep* ReLU networks. Otherwise the reader may assume the proof only applies to single-layer neural networks until they read the more detailed exposition in the appendix. \nD2. Is it an issue for homogeneity if there is a point where the derivative does not exist (e.g. at x=0 for ReLU).\nD3. Can the paper make it more clear to a Deep RL audience in the intro or discussion what the holy grail of this research direction would be?\nD4. As tanh or multiplicative activations (e.g. those found in LSTM/attention networks) are not homogenous, can the authors speculate about whether or not they would have similar convergence properties to homogeneous activations? What are the obstacles to a similar proof for this class of networks?.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "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": {}}]

Author rebuttal:

Meta-review: This paper takes steps towards a theory of convergence for TD(0) with non-linear function approximation.  The paper provides two theoretical results.  One result bounds the error when training the sum of linear and homogenous parameterized functions.  The second result shows global convergence when the environment dynamics are sufficiently reversible  and the differentiable function approximation is sufficiently well-conditioned.  The paper provides additional insight using a family of environments with partially reversible dynamics.

The reviewers commented on several aspects of this work.  The reviewers wrote that the presentation was clear and that the topic was relevant.  The reviewers were satisfied with the correctness of the results.  The reviewers liked the result that state value function estimation error is bounded when using homogeneous functions. They also noted that the deep networks in common use are not homogeneous so this result does not apply directly. The result showing global convergence of TD(0) with partial reversibility was also appreciated. Finally, the reviewers liked the family of examples.

This paper is acceptable for publication as the presentation was clear, the results are solid, and the research direction could lead to additional insights.
Decision: Accept (Poster)