Temporal Difference Learning: Why It Can Be Fast and How It Will Be Faster

Dear Reviewer,

Thank you for kind words and your questions. We will correct the mentioned typos.

To answer your question, with our choice of experiments, we picked these specific environments to have a close consistency check on our theoretical framework, which is the main contribution of work. Results on higher-dimensional nonlinear networks would not allow any conclusions to be drawn on the correctness of our theory regardless of the actual result. Nevertheless, it would be an interesting direction that we hope to pursue in the future.

It is important to mention again that we treat a topic with deep inconsistencies between theory and experiments: Theoretically TD can diverge, experimentally it still often finds better solutions than provably convergent methods. And despite a large body of empirical research, this behavior is still unexplained. From a statistical perspective, causal relations are established through a strong theoretical framework and controlled experimentation, and this is what we aim to provide. However, as an additional experiment, we will add Baird's original counterexample, where our method provides encouraging results.

When intending to apply our methods to established RL methods, one would have to identify the value estimation part in the algorithm. Such a component exists in most RL algorithms; this is why our work is of fundamental importance. One then would need to replace it by our update rule. As our theoretical description was focused on linear approximations, one should be aware that additional adjustments might be necessary for nonlinear function approximation. As said, we hope to address such questions as future work.

Regarding your reference [1], we will add this our related work as we aim to represent the diverse attempts to treat the divergence issue of TD and appreciate any hints on related work that might be relevant. They analyze a different approach that is based on introducing and updating a second set of parameters that then leads to updates on the actual network parameters. Their analysis appears not specific to particular ways of updating parameters, so the underlying updates can be GD, TD, or others. Therefore, we consider this work orthogonal to the methodological part of our work. We believe the most valuable part in our work is the theoretical framework of how convergence speed of TD methods can be investigated. Their paper and many others could use our work as a blueprint to provide theoretical arguments about whether their proposed methods will have improved convergence speed.

We appreciate your review and are more than happy to engage in further discussions should you have any follow-up questions.

Reviewer XMHR: if possible, can you reply to the rebuttal?

Dear Reviewer,

Thank you for reviewing our paper and sharing your thoughts. Below, you can find our answers to the questions you asked in the weaknesses (W) and questions (Q) sections. We will fix the typos you mentioned and omit them in the list below.

W1: Question on our choice of experiments: What of a setting where TD converges to the right solution? How does GDS-TDM compare there? Also, it is unclear why TD diverges in the grid-world example. The data is on-policy from the optimal policy, why then does TD diverge?

Thank you for raising this crucial point, which we will further clarify in our paper. Most importantly, TD does not provably converge, and hence test cases should distinguish "convergent TD" and "divergent TD" cases. Our paper argues theoretically that convergent TD offers a speed advantage and we present an idea of how to preserve the mechanism behind this speed advantage for divergent TD with a new method. Therefore, in a scenario where TD is already convergent, we would not expect our method to perform better as there is "nothing left to fix". Rather, our method was developed for cases where TD diverges, and hence we primarily choose to investigate its behavior for experiments that show diverging behavior. In the grid world example, we predict the values of the optimal policy. However, the state pairs are not samples from this policy, i.e. this is an off-policy case. Therefore, TD divergence is a real possibility and does not contradict the theory. In more detail, the state pairs in our setup are all equally likely whereas for an optimal policy, the state pairs closer to the terminal states are encountered more often. For brevity, we didn't mention the on- and off-policy topics until the related work section, but your question highlights the importance of this distinction, and we will clarify it in the upcoming revision. As your question Q8 also concerns the experiments, we will further comment on our choice of experiments there.

W2: In the sub-section Ill-Conditioning in Reinforcement Learning, the paper indicates why GD methods have a large condition number with delayed rewards. Though it only refers to a reference book and doesn't really explain the mechanism by which the condition number is so large. Could you provide a brief explanation as to why the condition numbers would be large with delayed rewards?

While not present in the mentioned subsection, we cite one work that explicitly studied connections between condition numbers and Reinforcement Learning (RL) parameters in the related work section. When we discuss the role of ill-conditioning in RL in our background section, we tried to provide some intuition on that issue while remaining concise. The linear system of the Markov reward process we defined in this subsection is one of the most studied linear problems, commonly known under the name Poisson problem. The reference only provides the scaling of the condition number of this particular linear system but adds nothing in terms of RL or delayed rewards. We will clarify this in our updated version of the paper.

One way to understand this behavior is that delayed rewards that connect states over many time steps lead to larger coupled linear systems and it is well-established in linear algebra that larger matrices typically have larger condition numbers. Another way would be to compare our Markov reward process against one where all n-state transition immediately connect to the terminal state. That would definitely be free of delayed rewards and the matrix in the Bellmann equation would be the identity matrix, i.e. perfectly conditioned. It is important to keep in mind that delayed rewards are only one way how condition numbers can increase.

Q5: Definition of $S$ in Theorem 3 confuses me a little bit. Does it imply $[-1, -1], [0, 0], [1, 1]$ are all valid values for $s$?

Yes, these are indeed valid values for $s$. The complete set is $S=\{(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1) \}$. We noticed we forgot to add $\forall i=1,2$ in the definition of $S$, which may have caused some confusion. Apart from that, the definition might seem a bit unusual at first, but the elements of $S$ simply serve to indicate the areas where the GD and TD update vectors don't change their sign.

Q6: Theorem 3 is for two-dimensional matrices and hence only two parameters. What would be needed for a more general proof?

Many of the complications arise from the non-differentiablity of the GDS-TDM vector field that is constructed from smooth GD and TD vector fields. Most convergence proofs in optimization rely on such properties; therefore, such proofs couldn't serve as blueprint or even inspiration. Our proof works roughly by subdividing the space into ever smaller regions, with the lowest layer having regions described by a linear map. There, a generalization of our characterization of the dynamics is straightforward. The challenging parts begin when be piece these smaller regions back together to characterize the global dynamics.

In two dimensions, we were able to eliminate certain kinds of divergent cyclic behavior between these regions by assigning them either clockwise or counter-clockwise movement, depending on how optimization trajectories look like within a region. In higher dimensions, another approach would be needed, potentially a proof by contradiction via some fixed point theorem to eliminate the possibility of such diverging cyclic trajectories.

Q7: How many times was the experiment repeated, what is the 95 percent confidence interval in Figures 4 (c) and 5 bottom?

The experiments were not repeated because both are convex optimization tasks. Hence, there are no local non-global minima or other complications that depend on initialization. The initial parameter values can change the initial loss values but asymptotic properties such as convergence and convergence rates are unaffected. Therefore, the shown results should not be considered lucky outliers, but are representative for the behavior of the different methods.

Q8: The proposed solution is really simple. Could you elaborate more on why these specific experiments were chosen? Perhaps experiments in more canonical RL tasks like mountain car or cart pole which have implementations online could be easily evaluated with the new technique? This would add a comparison in a control setting where TD does not diverge, where the discount factor is not 1, where the function approximation is established, and compare the empirical speed of learning and final solution reached for both TD, GD, and GDS-TDM.

Our experiments are motivated by the fact that the topic we treat has a considerable gap between theory and experiments. As outlined in our introduction, theoretically TD can diverge, experimentally it still often finds better solutions than provably convergent methods. And despite a large body of empirical research, this behavior is still unexplained. From a statistical perspective, causal relations are established through a strong theoretical framework and controlled experimentation, and this is what we provide. The 2-state experiment is a clear consistency check on the convergence proof of our method with all stochastic elements eliminated. The grid world example gives a glimpse on the question if such a proof could also be formulated in higher dimensions. Experiments on more complex environments are no doubt interesting, no less for us as authors, but regardless the result, they would not provide any insights about the correctness of our theoretical derivation, and we would again face the same gap between theory and experiments.

However, we followed the proposal of one of the other reviewers to include Baird's 7-star problem as an additional higher-dimensional experiment since it is probably the most studied example for the convergence properties of TD. It is promising to see GDS-TDM performing best in this test. Further experiments would also draw the focus further away from the first part of paper, our theoretical explanation of the speed advantage of TD. This is probably the most valuable part of our work as, to the best of our knowledge, nobody has previously provided an explanation for this advantage.

Thank you again for your many suggestions and questions. In case of follow-up questions, we'll happily discuss further.

W3: The thread leading to Equation 4 is abruptly cut off with no clear takeaway for a non-expert reader. What does the update shown in Equation 4 mean for the condition number, or for the optimization problem? Why does it fail?

Equation 4 is a gradient update. As such, its success or failure depends on the condition number, as we explained in the subsection 'Optimization theory'. The form of this update is a product of the TD error and the function approximation of values, as dictated by the chain rule of derivatives. Therefore, the overall conditioning can be expected to be ill since the TD error is already ill-conditioned, as we explained in the subsection 'Ill-Conditioning in RL'. On top, function approximation isn't usually well-conditioned either. We should mention that the condition number of a matrix product does generally not need to be higher than the matrix factors it is made of. E.g. the condition number is one when the two matrix factors are a matrix and its inverse, or unchanged if one of the two factors is an identity matrix. But in the practical relevant scenario of two matrix factors independent of each other, the overall conditioning will with high probability be worse. In our revision, we will add this additional explanation and make the relation to the previous subsections clearer.

W7: The related work has captured a lot of important references, particularly focusing on the unification of GD and TD, but has missed certain recent approaches that attempt to analyze or mitigate the instability of TD by empirically regularizing the gradient [2], or reframing the problem via an optimization lens [1].

We are eager to keep up with recent developments in RL and also offered some references of non-gradient updates beyond the RL field, as we think it is important to bridge different fields where the underlying mathematical problems are similar. [1] studies generalizations of linear TD's on policy convergence, such as for non-square losses or special cases of nonlinear function approximators. [2] doesn't study the divergence issue directly but rather the properties of solutions when TD succeeds and how to find better ones. Our work differs from these papers by providing a theoretical explanation for the faster convergence of TD training. Any suggestions for works whose relation to our work should be discussed are more than welcome and we are happy to add them in our updated draft.

Q1: Beginning of Section 3, The Hessian for TD is correctly identified as not being symmetric. Why is the conclusion that the subsequent matrix has a skew-symmetric component, and not any other type of asymmetry?

Any matrix $A$ can be written as sum of its symmetric part $(A+A^T)/2$ and skew-symmetric part $(A-A^T)/2$. Hence a non-symmetric matrix has a non-zero skew-symmetric component in such a decomposition. When we decompose $H_{TD}$ in that way, it is actually less a conclusion than it is a preparation for our mathematical treatment of TD's convergence speed. To avoid any confusion, we should clarify that this is not a Hessian in the strict mathematical sense as there is generally no associated scalar potential for TD updates.

Q2: In equation $8$, where does the $\eta$ come from? Is it the learning rate? I thought we were looking for the eigenvalues of $H$, and not $1-\eta H$. Which brings me to the possible incorrectness in the value of $\lambda_{1/2}$. Where does the $1$ come from?

$\eta$ is indeed the learning rate and the eigenvalues in Equation $8$ are the eigenvalues of the iteration operator $1-\eta H$ from Equation $6$, as you correctly suspected. Since we illustrated the optimization trajectories in Figure $1$, it was also our intention to show the eigenvalues of $1-\eta H$. The observations mentioned in this section, that the eigenvalues converge and become complex at some point, hold equally for $H$ and $1-\eta H$. Nevertheless, we see that we didn't phrase this well in the paragraph before Equation $8$ and will change our manuscript accordingly. Thank you for pointing this out. We also double-checked our theorems to make sure it is clarified if we consider eigenvalues of $H$ or $1-\eta H$.

Q3: Equation 9 seems to have a misplaced $k$. Is it supposed to be $t$?

Yes, thanks.

Q4: Does $I_k$ in theorem 1 indicate an identity matrix?

No, $I_k$ is the imaginary part of the $k$th eigenvalue of $H$. This is stated in line $1$-$2$ of Theorem 1.

Reviewer m5YS: if possible, can you reply to the rebuttal?

Dear Reviewer,

Thank you for your interest and giving feedback on our work.

Your first suggestion was to include GTD as a further comparison method in our experiments. Here it is important to point out that our experiments are on deterministic environments, for which GTD simplifies to plain Gradient Descent (GD), as the next state sampling process inherent in GTD methods always leads to the same outcome. GTD are specifically designed for another difference between GD and Temporal Difference (TD) methods, namely that they can have different fixed points on stochastic environments. We focus on the convergence speed difference between GD and TD, and so deliberately chose deterministic systems to offer a clear ground without other complications. Along the same lines, we think the experiment from your reference [2] would unfortunately not be helpful due to its stochastic rewards and transitions. In contrast, we followed your advice to include Baird's counterexample. It doesn't have the issue with different fixed points and is probably the most famous example for TD's divergence. It is encouraging to see that GDS-TDM performs best on this experiment and will include the details in our upcoming revision.

Another suggestion was to focus more on the broader implications of our work and less on the technical details. It is important to highlight that there is a considerable gap between theory and experiments around TD. As outlined in our introduction, theoretically TD can diverge, experimentally it still often finds better solutions than provably convergent methods, and this has been unexplained for a long time despite lots of empirical research. We think the best approach to address this gap is by presenting a theoretical description that holds under mathematical scrutiny and we would argue that the technical details are valuable in achieving this. Our goal with the simple method in Section 4 (GDS-TDM) was to show that this understanding can indeed already benefit future design of algorithms. This method is built on our understanding of TD's speed from Section 3. We will try to clarify this further in our manuscript and also mention again that value estimation through TD is part of many practical RL algorithms. We think the fundamental character of our work is interesting enough to warrant further research that can ultimately benefit practical RL algorithms.

Questions section:

Q1: How to place this work in the context of others? Are there other works on this topic since Baird's 1999 papers? Are Theorems 1 and 2 unique, or have they been addressed by other works?

We believe we are indeed the first to describe the speed advantage of TD theoretically. While there are other works addressing TD's divergence, which we discuss in our related work section, they focus on different aspects. For instance, as we explained above, GTD addresses another issue. We agree that Theorems 1 and 2 are indeed quite fundamental, but we could not identify any other works, even in different fields, performing a similar analysis with non-symmetric matrices.

Q2: Citation of Gallici et al. 2024 for their use of layer norm to address TD divergence. Is this enough for a convergent and fast algorithm? If yes, would we need to rely on GD's convergence benefits anymore?

We cited this work to show TD's divergence issue is an active area of research with diverse attempts to solve it. Regarding the convergence speed, we think it will be hard to argue for any method to have TD's convergence speed, as to the best of our knowledge, our framework is the first to show how such an theoretical argument on the convergence speed can be made. Regarding convergence, in our opinion, it makes sense to be open to the various approaches people take to tackle this issue and we will see what future research reveals. We have no specific argument if or if not layer normalization can enforce TD's convergence. But we agree with the implication that in the presence of further convergent methods, we wouldn't need to rely as much on GD.

Thank you again for your review and we are happy to discuss further questions you may have.