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

Authors: Patrick Schnell, Luca Guastoni, Nils Thuerey
Primary area: reinforcement learning
Keywords: Reinforcement Learning, Optimization

Abstract:
Temporal difference (TD) learning represents a fascinating paradox: It is the prime example of a divergent algorithm that has not vanished after its instability was proven. On the contrary, TD continues to thrive in reinforcement learning (RL), suggesting that it provides significant compensatory benefits. Empirical evidence supports this, as many RL tasks require substantial computational resources, and TD delivers a crucial speed advantage that makes these tasks solvable. However, it is limited to cases where the divergence issues are absent or negligible for unknown reasons. So far, the theoretical foundations behind the speed-up are also unclear. In our work, we address these shortcomings of TD by employing techniques for analyzing iterative schemes developed over the past century. Our analysis reveals that TD possesses a mechanism that enables efficient mapping into the smallest eigenspace—an operation previously thought to necessitate costly matrix inversion. Notably, this effect is independent of the conditioning of the problem, making it particularly well-suited for RL tasks characterized by rapidly increasing condition numbers, e.g. through delayed rewards. Our novel theoretical understanding allows us to develop a scalable algorithm that integrates TD’s speed with the reliable convergence of gradient descent (GD). We additionally validate these improvements through a rigorous mathematical proof in two dimensions, as well as experiments on problems where TD and GD falter, providing valuable insights into the future of optimization techniques in artificial intelligence

Decision: accept (poster)
Reviewer scores: 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730068284544

thread_type:
official_review

<thread_object>
creator: reviewer_xmhr

<content>
summary:
The paper deals with convergence problems in reinforcement learning. The convergence problems of temporal difference (TD) learning and the sometimes very slow learning behavior of gradient descent (GD) are considered. The paper introduces a new way of looking at the problems, which is based on the consideration of the size of eigenvalues. An explanation is provided and a simple modification is presented which is a synthesis of TD and GD. For this purpose, the sign of the GD update vector and the magnitude of the TD update vector are used. The considerations are supported by proofs and illustrated application to small but pathological examples.

strengths:
* The paper is excellently written. A real pleasure to read.
* If everything the authors present is correct, then this is a groundbreaking work that solves a problem that has been unsolved since Baird's time.

weaknesses:
I cannot identify any weaknesses.

I must say, however, that I am not capable of reliably verifying that all the claims are correct.

Minor suggestions:
* “where where typically” -> “where typically”
* “equation (2)” -> “Equation (2)”
* “section 3.1” -> “Section 3.1”
* Would not be “representation of Baird’s counterexample” more natural, than “representation of the Baird’s counterexample”?

questions:
* Why is the advantage of GDS-TDM not demonstrated using difficult, high-dimensional benchmarks?
* What should be considered when using GDS-TDM together with neural networks as Q-function in difficult, high-dimensional environments?
* Are the ideas from [1] relevant for the present work?
* Should [1] be cited and discussed?

[1] Wang & Ueda, Convergent and Efficient Deep Q Network Algorithm, 2022
</content>
</thread_object>

</thread>
<thread>
creation date:
1730185803011

thread_type:
official_review

<thread_object>
creator: reviewer_m5ys

<content>
summary:
This paper does a comparative analysis of the parameter updates when using gradient descent (GD) and temporal difference (TD) approaches. They focus on the one-step Bellman equation as the optimization target in both cases. In this analysis, the paper posits that GD methods have a high condition number, leading to slow convergence. It then focuses on TD updates when the Hessian matrix involved in the update is a combination of symmetric and skew-symmetric matrices.

Here the paper shows that as the skew-symmetric component of the Hessian grows, the eigenvalues start converging. With the eigenvalues closer together, the paper shows that the iteration scheme will progress more uniformly and lead to faster convergence. But this speed-up is capped by the largest learning rate that can be used.

The above analysis leads to a new method that uses the sign of GD and the magnitude of TD, called GDS-TDM in this paper. Theoretical analysis here shows that there exists a maximal learning rate under which convergence in guaranteed, and also specified the rate of convergence.

Finally, empirical evaluation on a simplified version of Baird's counter-example and a 10x10 grid world show stable learning, faster convergence, and lower error when using GDS-TDM compared to GD or TD

strengths:
* The paper states that they have two contributions: theoretical analysis validating why TD can converge fast, and a unification of GD and TD that seeks to combine the positive attributes of both. From my perspective, both of these contributions are partially justified. I go into more detail on the positives below and where I might need more convincing in the following sections.
* This paper presents an interesting analysis of the GD and TD updates based on their condition number and convergence rates. The breakdown of the TD Hessian into symmetric and skew-symmetric matrices seems to be novel and leads to the subsequent analysis in the paper.
* Figure 1 is well done and gets the idea across well.
* Section 3, which focuses on the first contribution, does a good job in analyzing a simpler problem and then generalizing the result in Theorem 1. The analysis of the eigenvalues as the Hessian is skewed more in Theorem 2 is interesting and communicated well via Figure 2.
* I have checked the proofs of Theorems 1 and 2 and I did not catch any major issues (minor quibbles in the Questions section).
* The proposed modification in Section 4 seems to be simple, and the experiments bear out some of the qualities that the paper advertises, namely, faster convergence than GD and more stable learning than TD.
* The proposed modification is extremely simple.

weaknesses:
Overall I really like the idea behind the paper, but I feel like there are bits and pieces that left me feeling confused. Below I try to write down these bits:
* As mentioned briefly above, I am not completely convinced that the contributions have been sufficiently justified. I appreciate that while this is a theoretical paper, the authors have attempted to empirically validate their technique. But the experiments both seem to show situations where TD is unstable, and GD is slow, and how GDS-TDM converges more stably compared to TD, and faster than GD. 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 while performing policy evaluation), with what seems like not undue state aliasing. Why then does TD diverge?
* 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? It would help a reader to better grasp the problem.
* 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?
* I wasn't able to follow some of the notation in Section 4. I have added particular confusions in the Questions section.
* There are some other notation typos and confusions. Clarifying in the Questions section.
* End of section 1, Typo: `demonstrate with a simple method *what* a unification of GD and TD preserving their positive attributes can look like`.
* 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]. These references might be useful to look at. I am not suggesting they be added to the related work, since it is clearly organized in a way that does not seek to exhaustively reference all previous attempts to improve the TD update.
[1] Asadi, K., Sabach, S., Liu, Y., Gottesman, O. and Fakoor, R., 2024. Td convergence: An optimization perspective. Advances in Neural Information Processing Systems, 36.
[2] Kumar, A., Agarwal, R., Ma, T., Courville, A., Tucker, G. and Levine, S., DR3: Value-Based Deep Reinforcement Learning Requires Explicit Regularization. In International Conference on Learning Representations.

questions:
* 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? Perhaps a quick clarification here might be helpful.
* 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?
* Equation 9 seems to have a misplaced $k$. Is it supposed to be $t$?
* Does $I_k$ in theorem 1 indicate an identity matrix?
* 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?
* This theorem is for 2 dimensional matrices and hence only two parameters. What would be needed for a more general proof?
* How many times was the experiment repeated, what is the 95% confidence interval in Figures 4 (c) and 5 bottom?
* 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730574896891

thread_type:
official_review

<thread_object>
creator: reviewer_1w4z

<content>
summary:
The paper proposes a theoretical analysis to understand the speed benefits of TD and the convergent properties of GD. It proposes a method that combines the benefits of each to have a faster and convergent algorithm. It presents a theoretical analysis and empirical results on toy domains.

strengths:
- The proposed method of combining TD and GD is simple and reasonable.
- The paper includes nice visualizations to understand the intuition behind the trajectories of the algorithms.
- The toy domains illustrate the idea reasonably well. It is nice to include results on Figure 4.

weaknesses:
- While not an empirical paper, I think some comparison to methods like GTD (gradient TD) would be useful to get a sense of the rate of convergence of other similar algorithms. I think just evaluating TD and GD in Section 5 is limited.
- Perhaps it would be useful to also evaluate the proposed methods on other toy domains known to exhibit convergence like the full Baird counter example like Figure 11.1 from Sutton and Barto [1] and Figure 1a from [2].
- I think the paper can do better at improving intuition in terms of language. The attempt of 3.4 is nice of giving the complete picture, but I think the broader implications are still missing and the details are still too narrowly focused on technical details. It would be nice to include some broader implication on future design of such algorithms based on the theoretical results.

[1] http://incompleteideas.net/book/RLbook2020.pdf
[2] A Kernel Loss for Solving the Bellman Equation. Feng et al. 2020.

questions:
- While there are some details in the related works, I am having a tough time placing this work in the context of others. Currently, the paper is written as though no one else has worked on this problem since Baird’s 1999 papers. Is this actually true? While the proposed method may be new, Theorem 1 and 2 seem quite fundamental and it's interesting that other works have not explicitly tried to address this. This question may be due to just my unfamiliarity with the literature, and so I would defer to other reviewers on the value of the proposed insights. 
- The paper cites Gallici et al. 2024 for their use of layer norm to address TD divergence. I am curious whether the authors think this itself is sufficient for getting both a convergent and fast algorithm? If layernorm enables TD to converge, we don’t necessarily need to rely on GD’s convergence benefits right?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732211868508

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to All Reviewers

comment:
Dear Reviewers,

Thank you for taking the time to review our paper and sharing your thoughts. We are glad to know that all of you were able to follow our arguments. In the individual responses, you will find our answers to your questions and concerns. We also plan to upload an updated draft as soon as we incorporated your feedback. Any further discussion is welcome and we would be happy to address any additional points.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732364451274

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Paper Update

comment:
Dear Reviewers,

We have uploaded the updated version of our paper. To address your comments, we have revised several formulations for improved clarity and added additional explanations. Furthermore, we have included Baird’s counterexample in the appendix as a further experiment. All changes have been marked in blue for your convenience.

Thank you once again for your feedback on our work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper looks into two algorithms for learning value functions: temporal difference learning (TD) and gradient descent (GD). The authors analyse both, arguing that TD if faster while GD has better convergence properties. They propose GDS-TDM, a method that takes the sign from the gradient descent update and the magnitude from the td update, combining the benefits of both approaches.

This is a strong and novel submission that proposes a simple-to-implement algorithm for a relevant problem. It also includes good visualisations on toy domains and a novel theoretical analysis.

Because of the strengths of the submission, I recommend acceptance, while strongly encouraging the authors to improve the presentation for the camera-ready version. Specifically:
- The paper implicitly realises that TD learning doesn't minimise any function, but does not emphasise this enough. Since recognising this fact is a fundamental feature of any analysis of TD learning, it has to be much more prominent.
- On a related note, when comparing with gradient descent, it has to be made much more clearly what objective (loss function) the gradient descent is using.