Temporal Difference Learning: Why It Can Be Fast and How It Will Be Faster
Authors: Patrick Schnell
Luca Guastoni
Nils Thuerey
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning
Optimization
Primary area: reinforcement learning

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

Published as a conference paper at ICLR 2025
TEMPORAL DIFFERENCE LEARNING: WHY IT CAN BE FAST AND HOW IT WILL BE FASTER
Patrick Schnell, Luca Guastoni and Nils Thuerey
School Computation, Information and Technology Technical University of Munich
Bolzzmannstr. 3, 85748 Garching, Germany
(patrick.schre 11, luca. wucaaguuattnn... nils shuurrey@ttumcco
ABSTRACT
Temporal difference (TD) learning represents a fascinating paradox: is the prime example of 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 crucial speed advantage that makes these tasks solvable. However, it is limited to cases where the divergence issues are absent or negligible for un- known reasons. So far, the theoretical foundations behind the speed-up unclear. In our work, we address these shortcomings of TD by employing tech- niques for analyzing iterative schemes developed over the past century. Our anal- ysis reveals that TD possesses 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 particularly well-suited for RL tasks characterized by rapidly increasing condition numbers, e.g. through delayed rewards. Our novel theoretical under- standing 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 experiments problems where TD and GD falter, providing valuable insights into the future of optimization techniques in artificial intelligence.
also
INTRODUCTION
Temporal difference (TD) learning is a training technique for prediction models in multi-step tasks, mostly known for its application to value prediction in reinforcement learning (RL, [Sutton 1988
Kaelbling et al., 1996: AAulkumaran et al. 2017). By estimating expected future rewards, TD learn- ing helps agents make informed decisions based their interactions with the environment. This ap- proach has proven successful in various domains such as robotics (Littman et al. 1995 Rajeswaran al.) 2017). game playing (Mnih al., 2015 Lample Chaplot 2017). and autonomous driving (Shalev-Shwarrs et al.] 2016 Sallab et al. (0177). by addressing challenges like delayed rewards where the impact of actions is not immediately clear.
Behind these successes of TD hides profound contrast in how information is processed over time compared traditional time prediction methods, like autoregressive models. Such models are 1- step predictors and are often trained via unrolling (Goodfellow et al., (016), which is n-step update rule. This is suboptimal since predicting n steps with 1-step models leads to exponentially accumulating errors, and an n-step update rule requires storing n-step trajectories. By contrast, value functions combined with TD offer n-step predictors via a 1-step update rule, scoring in terms of both mathematical and computational scalability.
However, challenges arise during optimization: TD objectives are usually minimized with a non- gradient method, harboring the potential for divergence (Baird 1995). Nonetheless, it often succeeds in finding good solutions quickly. In contrast, provably convergent algorithms such as gradient descent (GD) and its variants impractically slow in RI,, despite being the leading optimization

---

Published as a conference paper at ICLR 2025
methods in deep learning. This difference in speed is well-documented empirically (Sutton & Barto 2018), but the theoretical reasons behind it are unclear. As a consequence, attempts of unifying GD and TD to arrive at convergent, fast optimization method often based intuition. The lack of theoretical understanding means there are no design principles to guide their development.
Our paper addresses this issue with the following contributions:
We provide a theoretical foundation to explain why TD can be fast starting from the long- established link between condition numbers and the speed of gradient methods. We gener- alize these ideas to non gradient methods, such as TD.
The insights into what makes TD fast uniquely position us identify the necessary modifi- cations. We demonstrate with simple method how unification of GD and TD preserving their positive attributes can look like.
BACKGROUND
The natural starting point for all optimization methods based derivatives quadratic objectives. They arise in linear systems as well as in nonlinear systems near the optima, where higher-order terms become negligible. Therefore, any method with issues quadratic ob- jectives will eventually fail. Typically, a quadratic loss of n variables is expressed as:
Optimization Theory
1 マ 1|
E @ERXX x E ER" || (l2-norm)
non-zero target y E R would not affect convergence properties of iterative solution methods, so neglect this possibility to maintain compact notation. Such methods take the following generic form in their (-th iteration.
1z+ = - P/Q) 1) E IR (learning rate), P E Ruxm
(2)
The most prominent examples are GD (P = Q²) and Newton's 's Method (P Q-1). Convergence occurs if the induced norm of the iteration operator || |- p/PQl is strictly smaller than 1. This value is also called the convergence rate because the induced norm, by definition, exactly describes the worst-case decrease of || relative to |æe||, and therefore, the optimization progress. For GD and optimal learning rate, the convergence rate equals x-1
where k is the condition number of the Hessian Q2 Q. Ill-conditioned problems (x 1) result in convergence rate only slightly below 1, rendering GD ineffective for solving them Garrigos & Gower, 2023).
K+T1
IllConditioning in Reinforcement Learning While one-step tasks can also suffer from ill- conditioning, RL tasks have their own unique mechanisms that elevate condition numbers, thereby complicating optimization, e.g. delayed rewards in multi-step problems require information flow through several time steps. Suppose we have an n-state Markov Reward Process with linear tran- terminal), where all rewards are 0 except for the final transition into the terminal state with reward of 1. This scenario exemplifies a quintessen- tial delayed reward problem, isolated from other complexities in RL such as stochasticity, changing environments, and continuous spaces. The correct values must fulfill the Bellman equation, consistency equation stating the value difference between consecutive states equals the intermediate reward. Any violation of this equation is called the temporal difference error dn
sition structure (n + n +
8n unn) v(n- 1) for and 81 v(1) 1-
(3)
This linear system is one of the most studied in linear algebra, often called Poisson problem. Its condition number scales as n² (Strang, 2006). Hence, even though the solution seems trivial all values are G-GD becomes increasingly impractical for solving this simple task increases.
Temporal Difference Objective with Function Approximation In most RL. tasks, the number of states is exponentially large and so is the number of values. Therefore, values es)) of states s have to be approximated by value functions v(s, 0) parametrized by 0. As loss function for training serves the TD objective I, that is, the squared TD error In the standard RL setting, there typically a reward r between states and s', and a discount rate 7, compared to our example in Equation 3
82 2
8 = u(s 0) - yu(s', -
(4)
2

---

Published as a conference paper at ICLR 2025
When these terms summed over all state transitions (s, s'). we obtain the full loss for the value function. For linear function approximation, i.c. v(s, 0) is linear the parameters 8, this loss is of the form in Equation [ The z in the notation for the iteration scheme corresponds then to the, possibly shifted, parameters 0, and Q is determined by the state transitions of specific RI. task.
Gradient Descent the Temporal Difference Objective One way to solve for the TD objective 4 is by applying Gradient Descent, in this context also known as Residual Gradient (Baird 1995):
UGD -0g1 - (āou(s, -000osss))000(( 700o(s'
However, GD is slow the TD objective is ill-conditioned. This is because top of the task of finding the correct values, which already has high condition number, comes the secondary task of learning this value through function approximation, making the overall condition number even worse. In Deep Learning, various methods have been proposed to reduce the condition number and so alleviate the slow convergence of GD (Goodfellow et al.) 2016). However, they only have limited effectiveness in Deep RL, where typically value functions are approximated: Normalizing data is impractical since the outputs are values and priori unknown. Also, the input distribution changes continually during the ongoing exploration of the state-action space. As consequence, initialization schemes, designed to transport normalization properties from one layer to the next, fail since input and output were never normalized. And while momentum can accelerate gradient optimization, is insufficient to reach an acceptable convergence rate by itself.
Minimizing the Temporal Difference Objective with Non-Gradient Updates An alternative method is the following, commonly referred to as "Temporal Difference Learning'. From now on, we will use TD to refer to this method. is important to note that this encompasses not only the temporal difference objective but also the specific form of parameter updates.
uTD 5 0ov(s, 0)
(6)
Compared to UGD in eq. [ the TD update urD lacks the derivative term of the subsequent value. Removing this term motivated by the idea that observations of new rewards should only adjust values of past states. However, the missing term renders the TD update non non-gradient update, therefore lacking any convergence guarantees. That TD updates can indeed lead to divergence has been shown (Baird 1995). Yet, empirical evidence suggests that this instability sometimes does not occur and that then TD finds solutions in reasonable time Sutton & Barto (0188). From a practical point of view, this ability deliver solutions in at least some cases makes it the preferred method over consistently slow GD. The logical conclusion is that completely resolving the divergence issue of TD without compromising its speed advantage would be even more beneficial. Achieving this requires a clear understanding of the reasons behind TD's speed advantage.
3 THE INCREASED SPEED OF TEMPORAL DIFFERENCE LEARNING
To answer why TD can provide faster convergence than GD, we analyze the iteration scheme intro- duced in Equation replacing PQ by H:
Tt+1 = (1 - nH)x,
We begin exactly where previous works stop: The update equation of TD (6) lacks a term present in GD ( making it non-gradient method. Basic calculus reveals that gradient field is associated with a corresponding scalar potential, the loss function, whose first derivative is the gradient field and whose second derivative, the Hessian HGD. is symmetric. Hence, -an-rrddien field like the one from TD need not, and generally will not, have a symmetric Jacobian, allowing for a skew- symmetric part in HTD- Gaining insight into how this part affects the eigenvalues is crucial for answering the question of TD's superior convergence speed.
3.1 CLOSED-FORR SOLUTION IN TWO DIMENSIONS
To explore the impacts of a non-symmetric HTD on optimization, we first focus on the special case of two-dimensions. This scenario can be solved exactly and will serve the guiding example
3

---

Published as a conference paper at ICLR 2025
Gradient Field
Small Rotation
Loss Curves
19"1
M
10-1
Loss
19rr
10-9
Gradienn Rield
10-9.
Sm all Rotation
Large Rotation
1014
100
200
300
400
Iterations
b)
Critical Rotation
d)
Large Rotation
f
Convergence Rate
1.4
Convergence
2.
Target
Trajectory
Start
Eigenvectors
0.2
Learning Rate
Figure I: a) d): Illustration of the four types of a HTD matrix with example of an optimization trajectory for random starting point. The background shows the underlying quadratic loss. e) Corresponding loss curves. f) Convergence rate function of the learning rate. The amount of rotation increases from blue (no rotation) to red (large rotation). The dot on each curves marks the best convergence rate under optimal learning rate.
for the mathematically precise but abstract argumentation for the generic case. Let us consider the following matrix, which we require to be positive-definite and not the identity for = O:
H = -1-,
b-r (rrr
b rr
(8)
This provides simple model for possible HGD (r = 0) matrix and HTD (r * 0) matrices with varying strength of the skew-symmetric part. The symmetric part of HTD equals HGD. a simplifying assumption for this model that will remove later. The eigenvalues \1/2 of H are key to understanding the dynamics of the corresponding iteration process.
11/2 = 1 (a =
with D = -) c)² + 452 4
(9)
For the discriminant D is positive, resulting in two distinct eigenvalues. As increases in magnitude, D decreases, causing the eigenvalues to converge. With more balanced eigenvalues, the iteration scheme progresses more uniformly both eigendirections, thereby increasing the conver- gence rate. We identify four qualitatively distinct cases, illustrated in Figure
a) 0, D 0: gradient case, distinct eigenvalues, orthogonal eigenvectors
b) r 0, D 0: small rotation, converging angemvalues,non-orthoee.. eigenvectors
c) r 0, D = 0: critical rotation, identical eigenvalues, only one eigenvector
d) rl > 0, D 0: large rotation, complex eigenvalues with identical real part, complex
eigenvectors
Figure Te depicts the loss curves for the shown optimization trajectories across the four regimes. The 0 curves differ from GD by their short burn-in phase that is followed by convergence at improved speed. In Figure TT. the convergence rate is plotted against the learning rate for different values of r. Overall, the results indicate that the observed speed-up for * 0 is consistent across a wide range r values, suggesting that this improvement is not a result of specific learning rate choices, but rather stems from the influence of the skew-symmetric part in HTD-
4

---

Published as a conference paper at ICLR 2025
3.2 GENERALIZING CONVERGENCE RATES
Next, we formalize the ideas above using more rigorous mathematical language. We first link the convergence rate to the minimal eigenvalue, and then show how rotation increases the minimal eigenvalue in arbitrary dimension. We observed that the loss curve may exhibit burn-in phase or oscillate during its descent, which motivates convergence rate c, defined as follows:
investigate TD's speed through an asymptotic
lim max ao EIR
(10)
For GD, the connection between and the condition number arises from the symmetry of HGD- For the non-symmetric TD ease, establishing a similar link from e the spectrum of HTD requires further work:
Theorem 1:
Let E R, n E N. 2o R", H Ruxn and N. Denote eigenvalues and their real and imaginary part as A Rr + ila k E (I...., and define:
R
Mmax 2 min
Ruin min Ri- k
(11)
R 12
Then, the iteration scheme 22 H) is convergent if R3 0 Ak {1,... n) and O < 17 < Amax- Furthermore, the convergence rate e is upper bounded by:
S v 1- 1-1 (I
(12)
Tmaz
Corollary 1: Let Rmin < 1, 2 max ( RR (x) and Copt be the convergence rate under optimal
learning rate. Then: Copt
Amix S 1 / (
Corollary 2: L) < 1. Then: e 1-1-10 R- O11²)
Theorem provides a formula for how convergence rate can estimated from spectrum in the case of non-symmetric HTD. Corollary and offer more interpretable expressions for two relevant situations in deep learning: ill-conditioned matrices (Rmin < 1) and small learning rates (1) < 1). Both expressions share the dependence the eigenvalue with the smallest real part Reuin highlighting how increasing this value benefits optimization.
3.3 EIGENSPECTRA OF SYMMETRIC, DESITIVE-DEFINIE MATRICES UNDER SKEW-SYMMETRIC PERTURBATIONS
We now generalize the ideas from Section 3.1 to arbitrary 2. Our analysis begins again with matrix = A + rB, where A is symmetric, positive-definite and skew-symmetric. As before, corresponds to GD and + TD cases. We find the following statements about the spectrum of H::
Let A Raxn be symmetric, positive-definite matrix and B Rax skew- symmetric. Additionally, let A and B have non-degenerate eigenvalues. Denote the i-th eigenvalue by x₂(-) ordered from smallest to largest eigenvalue, the i-th eigenvector of by us and of B by wy. Then:
Theorem 2:
i.) Amin (A) S
real (A + rB) W Areal (A AB+B) & (Aax(() V min
ii.) lim Ateal (A rr
(W;, Aw,)
(A + rB) 1= 0 and d min (A + r rB)
(v2 Bug
ii..) min
Az(A)
In Figure 2 we illustrate these statements for = 5 using random matrices A and B. The eigen- values (blue dotted lines) converge towards each other, earlier in the = 2 case. Especially the smallest eigenvalue, previously identified as crucial for the convergence rate, improves signif- icantly. The statements of Theorem 2, depicted in red, prove that this picture is representative of
5

---

Published as a conference paper at ICLR 2025
n=
n=100
10
10
Eigenvalues (Real Part)
10
Eigenvalues of Bounds and Asymptotic Limit
10
10
2nd-Order Expansion
Eigenvalues B
10
0.0
0.5
1.0
1.5
2.0
10
Rotation Parameter
Rotation Parameter r
Figure 2: Real-part cigenspectra of symmetric matrix A with different strengths r of a skew- symmetric perturbation B in a) and b) 100 dimensions.
any A and B matrices: Part secure that smallest and largest real part eigenvalue cannot separate any further by bounding the spectrum's 's real part from above and below. Part ii) fixes the right side through a formula for the large r asymptotic limit. Part iii) brings us the heart of why TD im- proves convergence speed. The formula quantifies the initial increase of the smallest eigenvector. With the second-smallest eigenvalue serving as the denominator, this term can become extremely large depending just how ill-conditioned A is. This counters ill-conditioning perfectly, making TD ideally suited for RL. To further illustrate this point, Figure P presents a more ill-conditioned example with 100, showcasing remarkable rise in the small eigenvalues.
Enhancing Theorem 2 by Probabilistic Arguments: Non-degeneracy of eigenvalues one of the requirements in Theorem 2: however, it is not essential for the statements to hold. Including it simplifies the mathematical proof and, more importantly, allows us to highlight different type of argument that will revisit later: In function approximation, the entries of the involved matrices originate from a random process, typically initiated by the random initialization of layers in a neu- ral network or feature matrices in linear function approximation. Among all possible cigenvalues of such a matrix, the occurrence of two identical eigenvalues is a rare edge case and practically irrelevant.
This can be mathematically formalized and proven using measure theory. One of its central theorems states the zero set of non-constant polynomial is a Lebesgue null set. Building on that, the set of matrices with degenerated eigenvalues is Lebesgue null since these matrices' characteristic polyno- mials have degenerated zeros and only if their discriminant, itself a polynomial, zero. Similarly, part ii) describes the eigenvalues' asymptotic limit which, in theory. could equal A's eigenvalues. But since cigenvectors are defined through polynomial equations, improvement of the spectrum is practically guaranteed. Moreover, by the law of large numbers, increases, the eigenvalues of H scatter around the mean of A's eigenvalues, a normal-sized number. In summary. the eigenspectra depicted in Figure are representative of all practically relevant scenarios and this conclusion stands firm under rigorous mathematical evaluation.
3.4 THE COMPLETE PICTURE
Finally, we are in position to present coherent argument for why TD leads to faster convergence than GD, provided that divergence does not occur.
1. The convergence behavior of iterative methods T++1 (1 nH)) jr is determined by the matrix H, known as the Hessian Hap for GD. For TD, HTD is distinguished by the presence of skew-symmetric part B. We decompose this as HTD A B.

---

Published as a conference paper at ICLR 2025
2. As established in Theorem 1, convergence requires that the real parts of the eigenvalues of HyD are positive. This directly translates to A being positive-defimg
3. With that, we are in the scope of Theorem 2. The real parts of eigenvalues of HTD con- verge towards each other. Especially the smallest eigenvalue increases quickly, driven by the ill-conditioning of A. While we previously thought of as Han, this assumption is not necessary anymore since Theorem 2 yields better HTD for any symmetric positive- definite A.
4. According to Corollary increasing the smallest eigenvalue improves the convergence rate. However, the speed-up is capped by the maximal learning rate. This limitation be- comes critical in the large-rotation regime, where the growing imaginary parts of the spec- trum limit the achievable benefits.
5. More importantl, Corollary 2 provides a similar link for small learning rates. This is particularly relevant in nonlinear function approximation, where learning rates must be kept small to ensure the accuracy of linear approximations. In this regime, this explanation for the speed-up up from TD is valid without restriction.
This inherent speed advantage of TD has motivated research aimed at addressing its divergence is- sue. Shortly after Baird introduced GD to RL, he presented interpolation between GD and divergent TD, marking the first attempt fuse these two methods. Our analysis sheds new light on why this idea does not work: In Theorem 2, we interpolated with a skew-symmetric B, whereas in Baird's framework, this matrix would possess an indefinite symmetric part. Perturbation analysis reveals that in this case cigenvalues shift in both directions. Thus, for an ill-conditioned A characterized by small positive eigenvalues, even minimal negative shift creates negative eigenvalues, making this interpolation method instantaneously divergent. Nevertheless, unifying GD and TD is desirable and we demonstrate now with a simple construction how this can be achieved.
A PRINCIPLE- LUIDDED METHOD TO UNIFY GRADIENT DESCENT AND TEMPORAL DIFFERENCE LEARNING
Inspired by our new understanding, we combine the two update vectors of GD uep and TD unD by using GD's sign and TD's magnitude. Therefore, we denote this new method by GDS-TDM:
tees TDM sign(ues) ||urol
(13)
The particular form of this update rule is motivated as follows: tween GD and GDS-TDM can be most z/ n/2, enforcing movement in similar directions as conver- gent GD and thereby preventing divergence. Where the signs of GD and TD are constant, the update rule is described by linear map. Its matrix will have skew-symmetric part as it is build from the TD update. As we learnt, this is the key property that causes a drastic speed up in ill-conditioned problems. We now present a mathematical proof to show that this theoretical argumentation also holds under mathematical scrutiny:
Through the sign term, the angle be-
Theorem 3 (Enhanced Version): Let D E R22x2 be symmetric and positive-definite E R222 with eigenvalues unequal 0, H IR2 + R², + -sign (x:)- RR,, $ {s E R2|s; E
{-1, 0, 1} Vi {1,2)), and for E S, let Ag {x E R sign( sign (Rx), s Vi {1,2)}. Then:
i.) For all 8 E S, Ag, H is described by a linear map R, E 2x22 such that Vo E A, H(x) R,,.
ii.) There exists a maximal learning rate Muaa > 0 such that for < Mmxx the iteration scheme 3; = 11++HH110 (11)(===-) converges to O.
i If convergence occurs within one A., the convergence rate i given by e 1-1/>s. where A, is the smallest eigenvalue of - -R..
iv.) If convergence occurs across two Ag. the convergence rate is given by c 1-n K, c), where f is the direction of the smallest eigenvector of D, K the condition number of D.
and e the angle between d and Rd, where d is the boundary vector between the two A.. G is monotonically increasing function in K.

---

Published as a conference paper at ICLR 2025
GD
b)
TD
GDS-TDM
Sign Swep Sipn Seap
Howe Sate: Z.gaas Conie
Illustration of our proposed GDS-TDM update: The GD and TD vector fields (left and middle) result in the GDS- EDS-TDM field on the right. Convergence either occurs within single region (orange), or zigzagging (cyan).
Figure 3:
As before, we separated the technical requirements that are automatically fulfilled the involved matrices stem from a continuous sampling process. The full list of these Lebesgue null assumptions can found in the appendix. Figure gives an illustration of the theorem. Part a) and b) show examples of D and R vector fields, corresponding to GD and TD. Part c) shows the boundaries of the different regions, the dashed lines, along which the sign flips happen. They decompose the domain into the regions Ag, each with its own linear map. The orange trajectory shows example of convergence within one A., and the cyan trajectory of zigzag convergence between two A..
To understand why this method can have better convergence speed, consider first the zigzag case (part iv) and the function G. For GD, the term after the learning rate decreases with the smallest eigenvalue, explaining its slowness for ill-conditioned D. In contrast, here G shows the opposite behavior, increasing convergence speed with the condition number of D. As one can also guess from Figure 3 the dependence depends more on geometric quantities of R, not D, such as the angle at which the flow lines of R intersect the boundary line. For the inner convergence case (part iii), the convergence rate depends on the smallest eigenvalue. The linear maps R. are non-symmetric, and as we have shown before, this substantially increases the smallest eigenvalue, improving convergence.
Besides this mathematical characterization, practical advantages of the update rule are that it is easy to implement and causes minimal computational overhead. Since GD and TD are two backprop- agation techniques based on the same forward pass, they can be computed in parallel with little additional memory. The runtime increase due to component-wiss sign comparison is likewise minimal.
EXPERIMENTS
While our central contribution is theoretical foundation for understanding TD and for deriving algorithms with well-understood properties, we provide first set of empirical results for how GDS- TDM compares against GD and TD. In our experiments, we target value estimation, which is a fundamental part of most practical reinforcement learning algorithms. The choice and setup of these experiments are described below and motivated by our intention to provide a clear consistency check of our theoretical derivation. Two additional experiments can be found in Appendices B and
Two-State Example for TD's Divergence We consider a variant of Tsitsiklis & Van Roy (1996b)'s 's canonical value prediction task with a second parameter, as shown Figure 44. There are two transitions (state 0 + 0 and - 0). The self-transition is convergent while the other one leads divergence. Training off-policy using a state distribution with too much weight on the divergent transition will therefore make TD divergent on this task. This alternating between convergent and divergent updates can be nicely seen in TD trajectory in Figure H.. GD and GDS-TDM both con- verge. However, as can be seen in Figure Te. the convergence rate of GDS-TDN is substantially better, agreeing with our theoretical treatment.
10x10 Grid World This is classic RL environment, for which value functions are easy to visu- alize, allowing for easier assessment of iterative solution methods. We consider a two-dimensional non-periodic grid with terminal states located in the top-left and bottom-right corners. The agent
8

---

Published as a conference paper at ICLR 2025
a)
GDS-TDM
Weight
W1 + W/2
Start
-2
Goal
0123 45 6789
0123 43
6789
012345 6789
-2
Weight
10"
W0 + 2w
Loss
Loss
10-2
109
TD
GDS-TDM
GD
10-4
TD GDS-TDM
10-1
5000
10000 Iterations
15000
20000
50 Iterations
100
Figure 5: (Top) Visualization of the learnt value function in a 10 x 10 grid world for the different methods: gradient descent (GD, left), temporal difference (TD, center) and GDS-TDM (right). (Bottom) Comparison of the learning curves of the three methods.
Figure 4: a) Schematic representation of Tsitsik- lis and Van Roy's counterexample. b) Learning trajectories of the different algorithms in the pa- rameter space, c) Training loss as a function of the learning iterations.
can move up, down, left and right (unless on the boundary), and penalized with reward of 1 for every move that does not lead to the terminal state. Given the optimal policy, we estimate its values using a 100-parameter linear function approximator based on polynomial features, which we train on full batches to avoid stochastic effects of mini-batch training. The state pairs for the updates are sampled with equal probability, i.c. this is an off off-policy case. In the optimal policy distribution, state pairs closer the terminal states would occur more frequently than those further away. The exact solution has a value in the terminal corners and is minimal along the diagonal. An illustration is given in Figure 5 where GD and GDS-TDM correctly approach this solution. In contrast, TD suffers from divergence and is unable to find a good answer. Comparing the loss curves, we observe that GD and GDS-TDM behave similarly, both steadily decreasing the loss and eventually reaching a similar accuracy. This 100-parameter example gives us an outlook beyond the strict mathematical argumentation of our 2D proof. The absence of substantial speed-up of GDS- CDM over GD could point to limitation of our method in higher dimensions, suggesting that additional modifications might be necessary. It is also possible that Grid World, with its immediate rewards, does not generate the high condition numbers where TD methods thrive and GD fails. The fact that the value function estimated by GD already closely resembles the exact solution supports this. Regarding divergence, the picture is clearer: GDS-TDM does not encounter the divergence issues exhibited by TD.
6 RELATED WORK
A number of successful applications of TD exists in literature (Tesaro TD learning was originally introduced in contrast to Monte-Carlo methods, which rely on complete episodes, along with further TD variants that vary the number of steps over which errors are evalu- ated (Sutton 1988). Notably, our analysis applies all variants of TD, as we did not use any specific form of updates but only their non- coongrrdient nature. The fact that TD is not a gradient method and divergent was discovered by [aird (1995), and another example of divergence of TD was given by (Tsttsikis & Van Roy| (1996b). While the precise circumstances under which TD diverges re- main mostly unclear, it has been shown that TD converges for linear function approximation with on-policy training Tsitsiklis & Van Roy (199a)). In that case, the convergent transitions outweigh the divergent ones. Generalizations of linear TD's on-policy convergence were found by Asadi et al.) every transition could speed-up optimization.
1995 Mnih et al. 2015),
2003). Even in this setting, method convergent Emphatic- TD methods (Sutton et al. (016) reweight the state distribution to update less frequently on divergent state transitions. While this can suppress divergence, it inherently impairs the ability

---

Published as a conference paper at ICLR 2025
to learn the divergent part of the state space. The factors contributing to divergence in RL were later summarized under the term 'deadly triad', including TD training, function approximation and off- off-policy training. Given the importance of these elements in modern RL, a number of different research works have tried to address the shortcomings of TD divergence. For instance, van Hasselt et al. (2018) try build intuition for the TD algorithm behaviour and design number of mitigation strategies that they test empirically. Furthermore, least-squares TD (LSTD), in its recursive (Bradtke) & Barto 1996) or incremental (Geramifard et al. 2006) implementation, provide convergence guar- antees at the cost of a higher computational complexity. More recently, diverse attempts are made to address TD's divergence through normalization techniques (Gallici et al., 2024), or by introducing and updating second set of parameters that then leads to updates on the actual network parameters
[Wang& & Ueda 2022). Beyond the divergence issue, Kumar et al. 2021 studies how regularization can improve the quality of TD solutions.
The introduction of GD to RL, under the name residual gradient (Baird 1999), has been proposed as solution to the divergence of TD. This was quickly followed by interpolation techniques between TD and GD to address the apparent slowness of GD (Baird 1999), marking the first attempt to combine the positive elements of both methods into that slows down GD, was also investigated in an RL context, confirming that condition numbers can indeed be high in RL tasks (Sharifnassab & Sutton 2023). Further attempts unify TD and GD have been made under the name gradient TD (GTD) methods (Sutton et al.] 2008 2009). They address another phenomenon how TD and GD can differ: On stochastic tasks, GD can converge to a different solution than TD. While GTD methods converge and approach the original TD solution, they do not address the slowness of GD. This is apparent when considering that the slowness issue already exists in deterministic tasks, where GTD simplifies to GD. Further improvements to the GTD algorithms were proposed by Yao (2023) and Qian & Zhang (2023), reducing the number of hyper-parameter to tune in the algorithm.
method. Ill-conditioning, the property
is noteworthy that positive observations of learning with non-gradient methods reach beyond RL (Schnell & Thuerey 2024). Examples include time series prediction with unrolled computa- tion graphs (Stachenfeld et al. (2022) often in combination with differentiable simulators (Um et al.) 2020). as well as in the context of bilevel optimization (Bolte et al. 2024 Domke 2012)) such as hyperparameter optimization (Lorraine et al. 2020), deep equilibrium models (Geng et al. 2021 Fung et al. 2022) and meta-learning (Andrychowicz
al., 2016). Typically, the backpropagation pass is either shortened or modified in another way, which consequently destroys the gradient prop- erty of the outcome, thus falling within the scope of our argument. Similar to TD, the evidence is primarily empirical and these research fields could benefit also from the discovery of the underlying reasons behind the observed improvements.
7 CONCLUSION
Our work presented a theoretical framework that explains the widespread and puzzling observa- tions that TD can deliver crucial speed-up for making RL tasks solvable. We identified the skew-symmetric part of the iteration operator, which distinguishes non-gradient from gradient-based methods, as the key quantity driving this acceleration. An interesting future direction will be to de- sign model architectures that effectively control this quantity to enable a consistent performance boost. This shares similarities with initialization schemes that are tailored to influence the condition number to enhance gradient descent.
we proposed a method that combines the convergence properties of GD with the speed- up mechanisms of TD. We supported this with mathematical proof for the two-dimensional case, providing a detailed understanding of how these properties integrate. With our focus primarily on the theoretical aspects, natural next step is further empirical investigations. These could include exploring nonlinear function approximation, testing compatibility with momentum and other opti- mization techniques, and extending to advanced control algorithms in RL.
Furthermore,
In an empirically-drive. field, is crucial to remember the significance of theoretical results. Unify- ing GD and TD has been a longstanding goal in RL, and despite extensive empirical research, it has not been satisfactorily resolved, even in two dimensions. In that spirit, we believe our theoretical framework serve stepping stone for developing more reliable and faster RL algorithms.
10

---

Published as a conference paper at ICLR 2025
ACKOWLEDGEMENTS
This work was supported by the ERC Consolidator Grant SpaTe (CoG-2019-863850) We would also like to express our gratitude to the reviewers and the area chair for their helpful feedback.
REFERENCES
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. Advances in neural information processing systems, volume 29, 2016.
Kai Arulkumaran, Marc Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep rein- forcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38, 2017.
Kavosh Asadi, Shoham Sabach, Yao Liu, Omer Gottesman, and Rasool Fakoor. TD convergence: An optimization perspective. In Advances Neural Information Processing Systems, volume 36, pp. 49169-49186, 2023.
Leemon C. Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37, 1995.
Leemon C. Baird. Reinforcement learning through gradient descent. PhD Thesis, 1999.
Jérôme Bolte, Edouard Pauwels, and Samuel Vaiter. One-step differentiation of iterative algorithms. In Advances Neural Information Processing Systems, volume 36, 2024.
Steven J. Bradtke and Andrew G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1):33-57, 1996.
Justin Domke. Generic methods for optimization-base modeling. In Artificial Intelligence and Statistics, pp. 318-326. PMLR, 2012.
Samy Wu Fung, Howard Heaton, Qiuwei Li, Daniel McKenzie, Stanley Osher, and Wotao Yin. Jfb: Jacobian-free backpropagation for implicit networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 6648-6656, 2022.
Matteo Gallici, Mattie Fellows, Benjamin Ellis, Bartomeu Pou, Ivan Masmitja, Jakob Nicolaus Foerster, and Mario Martin. Simplifying deep temporal difference learning. arXiv preprint arXiv:2407.048/1 2024.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprinl arXiv:230..11235, 2023.
Zhengyang Geng, Xin-Yu Yu Zhang, Shaojie Bai, Yisen Wang, and Zhouchen Lin. On training implicit models. Advances in Neural Information Processing Systems, 34:24247-24260, 2021.
Alborz Geramifard, Michael Bowling, Martin Zinkevich, and Richard Sutton. iLSTD: Eligibility traces and convergence analysis. In Advances in Neural Information Processing Systems, vol- ume 19. MIT Press, 2006.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:
// //www. www.weeepeeee... ea wnw.orooo...oooo..o org
Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996.
Aviral Kumar, Rishabh Agarwal, Tengyu Ma, Aaron Courville, George Tucker, and Sergey Levine. DR3: Value-based deep reinforcement learning requires explicit regularization. In Deep RL Work- shop NeurlPS 2021, 2021.
Guillaume Lample and Devendra Singh Chaplot. Playing fps games with deep reinforcement learn ing. In Proceedings of the AAAI conference artificial intelligence, volume 31, 2017.
11

---

Published as a conference paper at ICLR 2025
Peter D. Lax. Functional Analysis. Pure and Applied Mathematics: A Wiley Series of Texts, Mono- graphs and Tracts. Wiley, 2002. ISBN 9780471556046. URL https://bookk: google. de/ htt.bokk/1.-111@ppAAAE..
Peter D. Lax. Linear Algebra and Its Applications. Pure and Applied Mathematics: A Wiley
Series of Texts, Monographs and Tracts. Wiley, 2013. ISBN 9781118626924. URL https:
//books.goog / SMTgC
Michael I. Littman, Anthony R Cassandra, and Leslie Pack Kaelbling. Learning policies for partially observable environments: Scaling up. Machine Learning Proceedings 1995, pp- 362-370. Elsevier, 1995.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International conference artificial intelligence and statistics, pp- 1540-1552. PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 2015.
Xiaochi Qian and Shangtong Zhang. Direct gradient temporal difference learning. arXiv preprint arXiv:2308.00 01 170, 2023.
Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. Proceedings of Roboties: Science and System, 2017.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 29(19):70-70, 2017.
Patrick Schnell and Nils Thuerey. Stabilizing backpropagation through time to learn complex physics. In The Twelfth International Conference on Learning Representations, 2024.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.032955 2016.
Arsalan Sharifnassab and Richard Sutton. Toward efficient gradient- based value estimation. In International Conference Machine Learning, pp. 30827-30849, PMLR, 2023.
Kimberly Stachenfeld, Drummond B Fielding, Dmitrii Kochkov, Miles Cranmer, Tobias Pfaff, Jonathan Godwin, Can Cui, Shirley Ho, Peter Battaglia, and Alvaro Sanchez-Gonzaler Learned coarse models for efficient turbulence simulation. In International Conference on Learning Rep- resentations, 2022.
Gilbert Strang. Linear Algebra and Its Applications. Thomson, Brooks/Cole, 2006. 9780534422004, URL
ISBN
Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3(1):9-44, 1988.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL
2nd.
html
Richard S Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent O(n) algorithm for off-policy temporal-different learning with linear function approximation. Advances in neural information processing systems, (((1):1609-16111 2008.
Richard S. Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast drasient methods for temporal- differeece learning with linear function approximation. In Proceedings of the 26th Annual International Conference Machine Learning, pp. 993-1000, 2009.
12

---

Published as a conference paper at ICLR 2025
Richard S. Sutton, A. Rupam Mahmood, and Martha White. An emphatic approach to the problem of polliy temporal-differeen learning. Journal of Machine Learning Research, 17(73):1-29, 2016.
Gerald Tesauro. Temporal difference learning and TD-Gammon. Communications of the ACM, 38 (3):58668, 1995.
John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffference learning with function approximation. Advances in neural information processing systems, 9, 1996a.
John Tsitsiklis and Benjamin Van Roy. Feature-based methods for large scale dynamic program- ming. Machine Learning, 22(1):59- 94, 1996b.
Kiwon Um, Robert Brand, Yun Fei, Philipp Holl, and Nils Thuerey. Solver-in-the-lopp: Learning from differentiable physics to interact with iterative pde-solvers. In Advances in Neural Informa- tion Processing Systems 33, 2020.
Hado van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Mo- dayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv: (oXXxv:8//2.024444 2018.
Zhikang T. Wang and Masahito Ueda. Convergent and efficient deep q learning algorithm. In International Conference on Learning Representations, 2022.
Hengshuai Yao. A new gradient TD algorithm with only one step-size: Convergence rate analysis using 1-À smoothness. arXiv preprint arXiv:2307.15822 2023.
13

---

Published as a conference paper at ICLR 2025
A MATHEMATICAL PROOFS
A.1 THEOREM AND ITS COROLLARIES
Theorem 1: Let 7) E R. N, zo R", H E Rux" and t E N. Denote cigenvalues of H and their real and imaginary part as Ay= = R& + ilk k E {I,,, nj and define:
R
1max 2 min
Rain min Ra &
(14)
R + h
Then, the iteration scheme 2, (1 7H JI is convergent Rş
Ak {l,... n} and
O < 1j < Imaax. Furthermore, the convergence rate c is upper bounded by:
c S v B7
!f Tmma
(15)
Proof:
We start with:
|
c= lim max
V |
1- 20ER"
lim
V VI[(1-17 7
(16)
KE (E(......))
The first equality the definition of the convergence rate; the following inequality rewrites the expression using operator norms; the last equality applies Gelfand's formula (Lax 2002). For the inputs max-operator, have:
V1 21/22 2 + 12)
(17)
Hence, in order have < 1, require R₃ > 0 for all le {1, n]. The radicand is parabola with a value of for 17 = Hence, it is also 1 for 17 = 27/ where v/f is the minimum.
d (1 2n + mr ( 12) 0
(18)
dnj
We find:
R R + 12
(19)
Hence, e < for < c 7max = 2 ming ni..
For the inequality on the convergence rate, we use again properties of parabolas: parabolas determined by three conditions. A parabola P(n) lying above the & other parabolas between 0 and Tmax is fixed by:
P(0)
P(Imax) = 1
dn P(0) 2Rnin
This leads to:
2R 172
P(n)
2R +
(20)
Tmmax
Corollaries and 2:
Both follow from Taylor expansion and determining the extrema of Equation 20
14

---

Published as a conference paper at ICLR 2025
A.2 THEOREM
Theorem 2: Let A E I be symmetric, positive-definite matrix and B E R skew- symmetric.. Additionally, let and B have non-degenerate eigenvalues. Denote the i-th eigenvalue by >x(-) ordered from smallest to largest eigenvalue, the i-th eigenvector of A by and of B by wy Then:
i.) Amin (A) min (A BB) S X max (A +B) S (A) V
ii.) lim yrall (A + rB) (w: Aw;)
ii..) dr min
real (A + r IB) 1= = and
neal (A + -BB) 2
Bon)
2r
(2(
Proof:
Part i)
We compute the numerical range of A+r B. which is defined as the range of the Rayleigh coefficient: Let E C" and normalized. Denote the vectors of the cigenbasis of A by vj and the corresponding cigenvalues by Aj.
(a, (A+ (A+rB)z) = E Ay1o,/ Bsna,ao
, >5 +r. By x + afx+) + in
(21)
Bzu xf=
J.k
3.k
Since B skew-symmetric, the second term adds zero Therefore, an expression for the real part of the Rayleigh quotient contains only the first term. Using || = 1, we find bound for the numerical range:
min (A) & Re((z, (A+rB)a)) I (A)
(22)
As the numerical range of matrix contains its spectrum, the claim follows.
Part ii) and iii):
(2013) compute the derivatives: Consider differen- tiable mruuare-matrix-vluuee function F(t) of a real variable t. Let be non-degenerate eigenvalue of F(O). Then for sufficiently small f, A(t) has an eigenvalue p(t) and corresponding eigenvector h(tt) that both depend differentiably on t. The derivatives with respect to & at 0 are denoted by dots and given as follows with h = f100) and / the left eigenvector of F(0) corresponding to μc:
We follow the procedure outlined by Lax
# (1, (h)
(23)
(1)
(F(() - whh =-fF- -i))
(24)
(1, 2(1, Fh) 2p(1,h)
(25)
(1,
Application iii):
A+rB is differentiable square-matrix qqure-matrix-vvauue of r equalling A for = 0. A is symmetric, implying left and right eigenvectors are identical. Using Ad, = Ayuj to denote eigenvalues and normalized eigenvectors, we find:
2, (uy, Buy)
(26)
15

---

Published as a conference paper at ICLR 2025
The last equality follows from the antisymmetry of B.
(d-Ay)úū = -
(27)
This singular system is solved by the following expression for any a E R. Note that the inverse here the pseudoinverse.
83 -A- XU)uz t
(28)
The second derivatives are given as follows:
X 2(ug. Boy)
2(Brj, (A - A1) Buj + ouz)
2BBrj, (A - b5)-1BBu)
(29)
(Uk, Bu,}²
2
dE Xg
kgj
For the largest eigenvalue, denominators are negative and therefore the largest eigenvalue does not grow for sufficiently small r. For the smallest eigenvalue, the situation is reversed.
Àmax 50 0
(30)
Xmin 2 0
Application to ii):
In the same spirit, apply the formulas for the derivatives again. B is skew-symmetric, therefore diagonalizable. We have:
d Ae B) e(w,, Awa)
(31)
de
Since eigenvalues of skew-symmetric matrices lie on the imaginary axis, we find:
Ae + B) = Aw,, + O(E2)
(32)
Hence, we can verify the claim:
lim A((A + rB) lim 1-00
Xe + B) (wi, Aw;) c00
(33)
A.3 THEOREM'S
Theorem 3: Let D E R2x2 be symmetric and positive-definite, R2x2 H. I 12 x +
-sigu -sigu(Dx) |Rx] S = {s R2 (-1,0,
}}}, 0]]] and for E let A, (ar E I sigu Dx):
sign (Rx); = vi {1,2)} Then:
i.) For all E S, A., H is described by linear map R2 Rx2 such that Vo E A H(r) R.T.
Assume further that D has different eigenvalues, has eigenvalues unequal 0, and that all the R. diagonalizable. Let 11, be the maximal eigenvector to R2 (eigenvector to the eigenvalue with largest real part). We assume U1 and Dvy,, have no zero components for all s. Denote by d, a vector for which the i-th component of Dd; is O. Then assume Rd, has no zero component.
16

---

Published as a conference paper at ICLR 2025
ii.) There exists maximal learning rate Mmaa such that for 17 mmax the iteration scheme
Ze = (1+ ( converges to O. iii.) If convergence occurs within one Ag. the convergence rate c given by 1-17ss where A is the smallest eigenvalue of - R...
iv.) If convergence occurs across two Ag. the convergence rate is given by c c K, c), where / is the direction of the smallest eigenvector of D, K the condition number of D. and e the angle between and Rd,, where d is the boundary vector between the two Ag. G is a monotonically increasing function in K.
Proof:
Description by Linear Map For all E S. the matrix elements of Rg are given by (Ra) -s; Rij. Then, for all & E (1,
(R
Rajatj = -8 (Rx))
(34)
Furthermore, for all Ag:
Rook
H(x)& sign (Dz) |Rx| -8h
8k: (Rx)s
(35)
sign( Rex)
Therefore, for all x E A,, (x)) = R.T.
Further Subdividing R For each x E IR, there exists an 8 such that x As. We will classify the dynamics within each region Ag by using the eigendecooppsition of its linear map Rg:
Rg Uk = 24
(36)
We choose the numbering according to the size of the real part of eigenvalues:
R(^1) 2 (222)
(37)
The division A, of R² consists of straight lines (when component of is zero) and double cones (for the remaining s). A cone C generated by vectors 9i is defined as:
C = far E R Σ Osfi where all a; > 0}
(38)
A double cone is the unification of the two cones generated by gi and -9:- The problem with this division is that the behavior within one specific cone can vary. For instance, an A, with only negative cigenvalues and the eigenvectors inside of Ag, there will have some x for which converges and other æ for which it leaves A,. This is why we further subdivide the A, into subregions B that behave consistently for all points inside. This works as follows:
1. First we split all double cones into the cones they are made of.
2. For each cone C, check if eigenvector of the corresponding R. is in the interior of C. If not, we leave C as it is. If so, we divide C, generated by {91. 92) into new cones always replacing one of the generators by {v.92} and g. In between these new smaller cones, we will also have 1-dimensional cones, generated by fewer than n vectors.
3. If there still are eigenvectors in the two smaller cones, we repeat this procedure until there are none inside anymore.
This will leave us with a subdivision of R. into subregions B with no eigenvectors in their interiors.
Restriction to Neighbor Transitions For our convergence proof to work, we restrict our iteration scheme to avoid jumping between subregions but only transition to adjacent subregions. Adjacent subregions B, and B, means 0B, n nåB2 + {0}. For a subregion B, we achieve this by allowing only learning rates smaller than maximal learning rate ng. Let B be generated by 9i and C be B unified with all its adjacent subregions. Then we define D3 as the cone spanned by the generators gi 8 82 and g2 8 91. These obviously cones containing B C D3 for all 5 > 0.
17

---

Published as a conference paper at ICLR 2025
Now, there exists y > 0 s.t. D,, C. For each of the 9t. determine 7) such that f(n)
(1 - nR 99 E Dy. This 77, is greater than 0 since f is continuous, f(0) = 9s and 9i is an interior point of Dy. Set f/8 min; Tj. Then for any Z E B, a191 + a292, the result of an iteration
step y is:
-1 BB =
a1(1 1/B RB),
(39)
Since a; > O due x B, y is in the open cone spanned by (1 [1-7) R RB ).. These generators are in D,, by construction. Hence, y E D.y and y E C. This means hat for all learning rates below f/8, the iteration scheme maps only to B or its adjacent subregions. If the subregion was a lower-dimensional cone, we can apply this argument to an adjacent -ulldimensiionl cone. Choosing the minimum T/B over all subregions, receive maximal learning rate Thmax, AT that guarantees adjacent transitions globally.
Classification of the Dynamics within Subregions We classify subregion B according to the position of the largest eigenvector by of their corresponding linear map Rg.
Case 1: in 0B, convergence
(U1 lies on the boundary of B)
An immediate consequence is that the eigenvalue A1 01 has to be negative (A1 0 is not possible by our theorem assumptions). To prove this, let { be sequence of vectors converging to ii li Tt. with xp B Vk E N. Then by how our method constructed:
sign(Dxt) =
VI N
(40)
By continuity, we have lim;-+oc Rgæt = Røv1 aa and lime Dr, Dos. Since by assumption of the theorem bi and Dv have no zero components, and the sign function is
continuous outside of O, we also have lim sign( (g sign(Rge1) sign(A1e1) and lim Sign( = sign(De,) Putting that together, we find:
sign(Dv1)
sign(Rge1)
sign(A1) sign(V1)
(41)
By assumption of our theorem, positive definite, implying the angle between in and De has to be smaller than r and eliminating the possibility of positive A in the last equation. Therefore, A is negative.
Next, we show that our method converges to 0 from within this region: For all x E B, we can write x = Ei= agg., This is again the standard parametrization of cones with a' positive and g the generators of the cone. Note that t1 is such a generator; we set 91 U1. Furthermore, this parametrization also includes lower-dimensional cones, where the gi could be linear dependent. Let now be To B. We obtain the next iteration vector 21 by applying the iteration scheme with the linear operator of B:
21 (1 (#))
= (1 + +R x0
= (1 + +
0g
= (1 +
(1 (2n 32
(42)
(1 + ()i)
+ (1 + 022
(1 + [h)
nu 2 3191)
(1 + (A))))o) + (1 + n12202221
a: + (1 + 122202222
(1 + n222)
(1+m)i)) a1 -
(1 n وزحي
91 + (1 (1+10 122))
In the fourth step, we switched from conic coordinates a; to the eigencoordinates 3, the description in the eigenbasis of Rn. The last line shows the conic coordinates of the new iterate 21. We choose
18

---

Published as a conference paper at ICLR 2025
learning rate 77 < -1/22. Then the second coordinate is positive. The first coordinate is also positive since + (1+) < (1+m))) and 31 > 0 because 6, the coordinates of 92 in the eigenbasis, are themselves conic coordinates of a cone spanned by the cigenvectors that 92 is part of. Altogether, we conclude that the sequence xy stays within B. Therefore, the dynamics of the iteration scheme entirely described by the linear map RB- We estimate for starting point 20 within B:
|elll [oll|
c=
lim (100
lim VII - R max 11 + m/A: = 1 ++ nA 1-00
(43)
1m1
Hence, for 17 < -1/A2 as chosen above, we have c < and the sequence converges to inside of B. Repeating this for any B yields maximal learning rate II for inner convergence within all subregions where this is possible.
Case 2: 11 0B, transition to an adjacent subregion or convergence
While we could repeat a similar calculation in conic coordinates as before, we present an alternative briefer argument here: In case the eigenvalues and are real, consider f(t) (1 RR for t E TR This is a continuous map with f(0) = To and, by power iteration, lim,, oz (tt approaches the direction of the largest eigenvector, which is V1. Therefore, by the intermediate value theorem, there exists a minimal i such that g(t)) lies on the boundary of the cone and g(t) inside of B for all t < f1. Choose = [t,] (smallest integer larger than or equal to t1). Then 22 is outside of B but, by our choice of learning rate, inside an adjacent subregion.
In case the eigenvalues and 01 have an imaginary part, we can switch the basis defined by the real and imaginary part of U1. There RB takes the form:
R((A) ((1))
-1 =
( RODAL
3(11)/AA1) R(x))/Ai
(44)
The last matrix is rotation matrix. So applying this linear map netimee to vector means rescaling by a factor [^ı] and then rotating by the angle n arccos(9R(M)) (/Ar///il Therefore, it is clear that any for any zo in the cone B, the cone will be left in finite number of steps.
For completeness, there is also the possibility that zo is proportional to the second eigenvector v2. By the same argument as above in Case 1, the second eigenvalue would then be negative and we would observe convergence within the learning rate bound and rate as determined in Case 1. Nevertheless, this is an edge case and does not compromise the conclusion that for any subregion observe either convergence or transition to an adjacent subregion.
Dynamies between Subregions With the dynamics of single subregions classified, we can begin to glue them back together. Let di be vector for the first component of Dd, is zero, and dg be vector for the second component of Dd2 is zero. Then the cones spanned by d2]. f- -1. dz). [d2. {-d1, d2) along with the lower-dimensional cones in between decompose R². We will denote these cones as C-cones. All of the cones of subregions B are exactly part of one C and several B-cones may form one C-cone. The statement is now within one C cone the iteration scheme will either converge to 0 or leave C' in a finite number of steps. This is basically the same sort of statement we received for the B regions. This implies that the iteration scheme cannot diverge within C' by jumping back and forth between subregions B.
To prove this, assume we have a sequence { from our iteration scheme inside a C-cone that does neither leave C' nor converges to O. Since {x²} } does not converge within a subregion, it will leave any subregions ever visits. Since the number of subregions B is finite, {æ,} must therefore revisit at least one subregion it has already been in. In two dimensions, this implies there are two adjacent subregions B, and B2, and a, b E N with a < b such that x; E B, for a and I = and x; E B2 for a < t < b + 1. By construction and by assumption of no convergence, neither B1 nor B2 have an eigenvector inside or on their boundary.
The important observation is that inside D region there are no sign flips of Dz. That means even though H may be described by different linear functions in the different subregions, they are glued together in a way that H is continuous on D. The updates moving out of B, into BN is Hr, and the one moving from Bg back into B, is HIs, Working in polar coordinates and recalling that the subregions adjacent cones, this means that the angular coordinates of these two updates
19

---

Published as a conference paper at ICLR 2025
must have different signs. By continuity of H and the intermediate value theorem, this implies that there is an x in between Za and Zb. in one of the subregions or their boundary, where the angular coordinate of Hæ is O. Therefore, Hæ has only radial component, implying is an eigenvector of the corresponding linear map and the sequence {are} } will converge in contradiction to the assumption that {xz) does not converge. As consequence, the iteration scheme does either converge inside D regions or leaves them in a finite number of steps.
A further consequence of this argument here the transition from one subregion the next happens in one direction only, clockwise or counter-clockwise. This can be seen by repeating the above argument, where we had two different linear maps when we assumed the existence of two points with different update direction. The two linear map were continuously connected. In contrast, here we would have only one linear map for the two points, and this map is trivially continuous everywhere between, allowing us to repeat argument.
Dynamics between D-Cones To understand the dynamics between the D-cones, we first char- acterize them geometrically. Let Si be the largest eigenvector of D. Then we choose the vectors di and d2, which were defined by the i-th component of Did; being 0 in the last subsection, to have (fi.d)) d.) > 0. This can be achieved by simply replacing d, by -d,- Then all d1 and d2 lic within the same quadrant and fi lies inside the cone generated by the d, This is a direct conse- quence from the fact that positive definite matrices define ellipses. As our D by assumption has an off-diagonal part unequal 0, the de will not be the coordinate axes. A further consequence is that (ign(d,) sign(dz) = sign(f).
Next, we conclude that (x) for all r in D-cone spanned by d, and d2 points to 0 in terms of their sign:
(x) = - sign( Dx) = - sign( (f/) = sign(S) (1) = sign(a)
(45)
Similarly, we have for in the D-cone spanned by -d1 and -d2:
sign H (x)) = sign( Dz) = sign( Df1) = sign(f)) = sign(x)
(46)
For the remaining cones, the last equality does not hold. Let f2 be the other eigenvector of D and be oriented such that it is part of the 1) cone spanned by d1, d22. Then for all x in that cone:
sign(H (z))
sign(Dx)
f2)
sign(f2)
(47)
For all x in the remaining cone spanned by -d1, d2:
sign(H = - siggn(Dr)) sign( = sf)
(48)
We already showed that the transitions from one subregion to the next go only in one direction. With these geometric thoughts, we can eliminate the possibility of our iteration scheme cireling around forever between the D-cones. What is possible is going back and forth between two subregions
that meet at the di or the d2 line. This can be shown by the existence of two subregion where the transitions happen only clockwise in one and counterclockwise in the other.
To show this assume without loss of generality that d2 lies before d2 when moving clockwise and that both lie in the first quadrant, i.e. sig = (+1, +1) Then the first subregion is given by the subregion B1 whose boundary is d1 and not in the cone spanned by dj and dg. For x B, and in the first quadrant, we are in the cone spanned by d1, d2, therefore the sign of the update direction is (-1,+1) +1) - Hence the iteration scheme will cross dj clockwise. Repeating the argument for the subregion B3 whose boundary is d2 and not in the cone spanned by dj and d2. we find that there the iteration scheme will cross d2 in counter-clockwise direction. This proofs the existence of two subregions adjacent to one the d-lines between which the iteration scheme moves back and forth.
To describe this dynamics near the d-line, where the iteration scheme moves back and forth between two subregions B1 and Bg, we work in the basis d, e with being orthogonal to d. We denote the corresponding coordinates by Ya, Ye, and without loss of generality assume that for Ye > we move into B, First we analyze this zigzag behavior for simplified map H* defined by Hx)))
By
(ye, x) > O and H' (x) = B2 if (Ye, x)) < 0. A drawing of this situation can be found in A.3 for the case where one of the sides moves actually away from O. It is part of the argumentation that in this case the movement toward 0 on the other side outweighs the divergent part. Denoting
ri = [[d] and r2 = ||B2d]], one iteration step in B₁ changes the coordinates as follows:
Ara- -T)r Nit (0)(
(49)
A7
= 7 sin (:)
20

---

Published as a conference paper at ICLR 2025
B
0
Figure 6: Geometric model for zigzag convergence. Blue lines show where the sign of the gradient field switches. The green crosses with the red-colored quadrant indicate the allowed signs of the update vector in the three regions defined by the blue lines. The red line corresponds to the flow line of the non-gradient field.
Similarly, one iteration step in B2 changes the coordinates as follows:
Ana -Va227aa cos(
(50)
Are "/"2"dd sin
For the iteration scheme to move between B1 and Bg endlessly, we require Ae, the number of B steps has to be λ the number of B, steps, where и can be computed from:
(
kyp (in ypr (a)
(51)
(a)
Here, set r Ti 72 since along the boundary, the vector only flips sign in one component and therefore, the lengths are the same. Consequently, the average A'ya progress per step is:
kr Ara = - K1
cos(a)
+ K ++1
cos(3)) = -nF Byaa
(52)
As long as + 3 convergence. the angle between the H* (xr) updates and the coordinate axis along which the sign flips. fulfills::
the expression in the brackets F gives a positive number, leading to
a + B 2c
(53)
By assumption of the theorem, they are not parallel, giving e > and a a 3 n. We also introduce the angle ø between d and the first coordinate axis.
0 + a n/2
(54)
To apply these ideas now to the actual vector field H, we note that the maximal step away from the boundary be more than wh (1 R/ and wa + R) To receive worst-case
21

---

Published as a conference paper at ICLR 2025
estimate for the convergence rate, we assume the updates always happen with the worst possible angle am and Sm. which would lead to more movement along é and less along As by continuity for 17 0, they approach and 8. choose a learning rate smaller than 7maxx 22 that is chosen such that the angle between the worst case value of o' and / on both sides of d with the coordinate axis of the sign flip is still c/2. Then Equations 53 and 54 change to:
a'+
(55)
0 0+a's + +c/2= n/2
As still a' + 3 < и, our iteration scheme is still convergent through 52 The a' and 3 can be written as a function of & and
a' d/22/22-/2-0
(56)
8' -/2 - e/2 0
With that we can give an upper bound on the convergence rate, using that is bounded by Ta-
xell x
lim 1-000
- - =1 -
(57)
By again using the geometry of ellipses, eigenvector fi of D and the coordinate axis. As the ellipse defined by D) becomes more elongated by increasing the condition number K of D, 0 increases with K. Using this information together with the functional form of F, we can then give the following formula for c, where G > 0 through K and > 0, and G fulfills G(fi, K1, E) G(fi, K2, if K1 >> K2 this leads better 0.
further estimate 0: As mentioned d lies between the
$ 1 111-
(58)
Final Estimates Putting it all together, we choose Tmax as the minimum of 7max, AT. 7mmax. Amax.22 22. Then for < 17 < 7max the construction in our proof is valid and after a finite num- ber of steps, we either reach one of the two asymptotic situations of convergence. The convergence rate is bounded by the maximum of S G/i, K, for zigzag convergence and e + n/ for convergence within one subregion.
22

---

Published as a conference paper at ICLR 2025
b)
a)
10a
2
2ura
2err
2mná +oora
2
2n00
10
GD
Loss
10
GDS-TDM
10
10
2w5
50
100
150
200
250
Iteration
Figure 7: a) Schematic representation of Baird's counterexample with states. b) Loss function of iterations.
B BAIRD'S S COUNTEREXAMPLE
As another case, present the version of Baird's counterexample provided by (Stttnn & Barto (218)), which is likely the most famous example associated with TD's divergence. Figure 7a shows schematic drawing of this Markov reward process along with the structure of the used function approximation. The transition probabilities of the policy to be estimated are on the solid arrows and 0 elsewhere. The transition probabilities of the behavior policy used for off-policy training 1/7 on the solid arrows, 6/7 on the dashed arrows, and O elsewhere. We use discount factor of 0.99 and train on full batches to avoid stochastic effects of mini-batch training.
Figure/h shows the loss (Bellmann error) over training iterations for GD, TD and GDS-TDM, At the beginning. GI) performs decently before then stagnating around 10-6 This is due ill-conditioning as explicit calculation of the condition number of the Hessian reveals; its value is 1.3 10a. TD diverges, which is due to the off-policy training procedure. GDS-TDM behaves similarly to GD in the beginning, decreasing the loss. When GD reaches is plateau, GDS-TDM continuous to decrease the loss. Later GDS-TDM stagmates as well but at a much better value roughly 10-10, It is worth mentioning that at some point expect the loss not to decrease any further due to floating point precision and the presence of non non-zero solutions. The latter exists in any underdetermined linear system; here, use 8 variables to learn 7 values.
23

---

Published as a conference paper at ICLR 2025
102
GD
TD
10
GDS-TDM
10
10
Loss
10-6
10-8
10 10
10-12
10
25
50
75
100
Iterations
Figure Loss over iterations for 3x3 Gridworld.
C 3x3 GRID WORLD
We present an additional variation of our Grid World experiment where we reduce the size from 10x10 to 3x3. For that case, TD converges and we have reference of what the convergence speed TD actually is. Consequentially, we can test whether our method GDS-TDM can indeed reach the same speed as TD in higher dimensions well. The results are shown in Figure 8 We observe GD slower than TD, as expected; however, GD is not impractically slow since the condition number for this www-dimensional Grid World is still small. GDS-TDM lies between GD and TD. After the burn-in phase, GDS-TDM achieves similar asymptotic speed as TD. This is an encouraging result the theoretical analysis in work also focused the asymptotic convergence rate.
24


Reviews:
[{"review_id": "sqZpB4oeHB", "reviewer": "Reviewer_1w4Z", "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.", "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. \n- 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?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method of combining TD and GD is simple and reasonable.\n- The paper includes nice visualizations to understand the intuition behind the trajectories of the algorithms.\n- 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.\n- 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].\n- 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.\n\n[1] http://incompleteideas.net/book/RLbook2020.pdf\n[2] A Kernel Loss for Solving the Bellman Equation. Feng et al. 2020.", "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": "", "extra_scores": {}}, {"review_id": "NkHo3QrUYt", "reviewer": "Reviewer_m5YS", "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.\n\nHere 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.\n\nThe 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.\n\nFinally, 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", "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.\n* 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?\n* Equation 9 seems to have a misplaced $k$. Is it supposed to be $t$?\n* Does $I_k$ in theorem 1 indicate an identity matrix?\n* 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?\n* This theorem is for 2 dimensional matrices and hence only two parameters. What would be needed for a more general proof?\n* How many times was the experiment repeated, what is the 95% confidence interval in Figures 4 (c) and 5 bottom?\n* 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n* 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.\n* Figure 1 is well done and gets the idea across well.\n* 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.\n* I have checked the proofs of Theorems 1 and 2 and I did not catch any major issues (minor quibbles in the Questions section).\n* 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.\n* 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:\n* 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?\n* 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.\n* 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?\n* I wasn't able to follow some of the notation in Section 4. I have added particular confusions in the Questions section.\n* There are some other notation typos and confusions. Clarifying in the Questions section.\n* End of section 1, Typo: `demonstrate with a simple method *what* a unification of GD and TD preserving their positive attributes can look like`.\n* 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.\n[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.\n[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.", "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": "", "extra_scores": {}}, {"review_id": "o1sNaqLfpj", "reviewer": "Reviewer_XMHR", "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.", "questions": "* Why is the advantage of GDS-TDM not demonstrated using difficult, high-dimensional benchmarks?\n* What should be considered when using GDS-TDM together with neural networks as Q-function in difficult, high-dimensional environments?\n* Are the ideas from [1] relevant for the present work?\n* Should [1] be cited and discussed?\n\n[1] Wang & Ueda, Convergent and Efficient Deep Q Network Algorithm, 2022", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper is excellently written. A real pleasure to read.\n* 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.\n\nI must say, however, that I am not capable of reliably verifying that all the claims are correct.\n\nMinor suggestions:\n* “where where typically” -> “where typically”\n* “equation (2)” -> “Equation (2)”\n* “section 3.1” -> “Section 3.1”\n* Would not be “representation of Baird’s counterexample” more natural, than “representation of the Baird’s counterexample”?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)