Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: What is the specific question/problem tackled by the paper?

The paper studies convergence & non-divergence of TD(0) with value function estimates from the class of ReLU deep neural nets (optionally with residual connections). 

Is the approach well motivated, including being well-placed in the literature?

Yes.


Does the paper support the claims? This includes determining if results, whether theoretical or empirical, are correct and if they are scientifically rigorous.

The support is adequate.


Summarize what the paper claims to do/contribute. Be positive and generous.

The 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.


Clearly state your decision (accept or reject) with one or two key reasons for this choice.

I vote for accepting the paper.


Provide supporting arguments for the reasons for the decision.

The 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.

The paper also makes an adequate choice of function space to restrict the guarantees to.


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.

It 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.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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.

TD learning follows a biased estimate of the gradient of the squared expected Bellman error, which
is minimized by the true value function. The bias is intrinsic to the fact that one cannot obtain more
than one independent sample from the environment at any given time. As it turns out, this bias
can be seen geometrically as “bending” the gradient flow dynamics and potentially eliminates the
convergence guarantees of gradient descent when combined with nonlinear function approximation.
》》 I don’t know what this means. TD diverges with nonlinear FA just because the contraction mapping does not hold any more. 

such as two timescale algorithms, but these algorithms are not widely used
>>this argument is a bit weak. 

We prove global convergence to the true value function when the environment is “more
reversible” than the function approximator is “poorly conditioned”.
>>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. 

Section 2:

Equation 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. 

Convergence to V* immediately follows. – What convergence? I thought you were talking about stability of the ODE. 

the “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. 

V(\theta)_s: this notation is odd. 

it 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.  


The first is when V is linear and the second when the MRP is reversible so that A is symmetric.
>>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. 

Section 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. 

Definition 1: “homogeneous”. This is not the usual definition of homogeneous in mathematics. Square function is.  Relu: gradient at 0 exist?

 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.  

I 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? 







 
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: The paper analyses the convergence of TD-learning in a simplified setup (on-policy, infinitesimally small steps leading to an ODE).

Several new results are proposed:
- convergence of TD-learning for a new class of approximators (the h-homogenous functions)
- convergence of TD-learning for residual-homegenous functions and a bound on the distance form optimum
- 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.

While the theory applies to the ideal case, t provides some practical conclusions:
- TD learning with k-step returns  converges better because the resulting Markov chain is more reversible
- convergence can be attained by overparmeterized function approximators, which can still generalize better than tabular value functions.

The experiments corroborate the link between reversibility factor and TD convergence on an artificial example.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: 
####
A. Summarize what the paper claims to do/contribute. Be positive and generous.
####

The 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.

This 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:

1. 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.

2. 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.

3. 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. 

4. 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.

5. 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). 

####
B. Clearly state your decision (accept or reject) with one or two key reasons for this choice.
####

This 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).

The paper is interesting and easy to read (even for someone without background in proving the convergence of RL algorithms).

####
C. Provide supporting arguments for the reasons for the decision.
####

Whether 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.

Good intuitions given for the mathematical results in addition to proofs (e.g. why homogeneity prevents divergence).

This 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).

####
D. 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.
####

D0. 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?
D1. 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. 
D2. Is it an issue for homogeneity if there is a point where the derivative does not exist (e.g. at x=0 for ReLU).
D3. 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?
D4. 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?.
review_title: Official Blind Review #3

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)