TD Convergence: An Optimization Perspective
Authors: Kavosh Asadi
Shoham Sabach
Yao Liu
Omer Gottesman
Rasool Fakoor
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Temporal Difference Learning
Value Function Optimization
Convergence

Abstract: We study the convergence behavior of the celebrated temporal-difference (TD) learning algorithm. By looking at the algorithm through the lens of optimization, we first argue that TD can be viewed as an iterative optimization algorithm where the function to be minimized changes per iteration. By carefully investigating the divergence displayed by TD on a classical counter example, we identify two forces that determine the convergent or divergent behavior of the algorithm. We next formalize our discovery in the linear TD setting with quadratic loss and prove that convergence of TD hinges on the interplay between these two forces. We extend this optimization perspective to prove convergence of TD in a much broader setting than just linear approximation and squared loss. Our results provide a theoretical explanation for the successful application of TD in reinforcement learning.

TD Convergence: An Optimization Perspective
Kavosh Asadi"
Shoham Sabach"
Amazon
Amazon & Technion
Yao Liu Amazon
Omer Gottesman Amazon
Rasool Fakoor
Amazon
Abstract
We study the convergence behavior of the celebrated temporal- -rrporal-diffreecee (TD) learning algorithm. By looking the algorithm through the lens of optimization. we first argue that TD can be viewed as an iterative optimization algorithm where the function to be minimized changes per iteration. By carefully investigating the divergence displayed by TD on classical counter example, we identify two forces that determine the convergent or divergent behavior the algorithm. We next formalize our discovery in the linear TD setting with quadratic loss and prove that convergence of TD hinges on the interplay between these two forces. We ex- tend this optimization perspective to prove convergence of TD in much broader setting than just linear approximation and squared loss. Our results provide a theo- retical explanation for the successful application of TD in reinforcement learning.
1 Introduction
Temporal-difference (TD) learning is arguably one of the most important algorithms in reinforce- ment learning (RL), and many RL algorithms are based on principles that TD embodies. TD is at the epicenter of some of the recent success examples of RL [1, 21, and has influenced many areas of remarkable success of TD in numer-
science such as AI, economics, and neuroscience. Despite settings, the algorithm is shown to display divergent behavior in contrived examples [3, 4, 5]. In practice, however, divergence rarely manifests itself even in situations where TD used con- junction with complicated function approximators. Thus, it is worthwhile to obtain a deeper under- standing TD, and to generalize existing convergence results to explain its practical success.
In this paper, our desire is to study TD through the lens of optimization. We argue that TD could best be thought of as an iterative optimization algorithm, which proceeds as follows:
g++1 Rs arg min H(0", "))
(1)
Here, the objective constructed by a) choosing a function approximator such as a neural network and b) defining discrepancy measure between successive predictions, such as the squared error. We will discuss more examples later.
This process involves two different parameters, namely the target parameter 0' that remains fixed at each iteration and the optimization parameter w that is adjusted during each iteration to minimize the corresponding loss function. Using the more familiar deep-RL terminology, Of corresponds to the parameters of the target network, whereas w corresponds to the parameters of the online network. Many RL algorithms can be described by this iterative process with the main difference being the approach taken to (approximately) perform the minimization. At one side of the spectrum lies the original TD algorithm [6], which proceeds by taking single gradient-descent step to adjust and immediately updating More generally, at each iteration we can update the w parameter K times
"Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

using gradient- descent while freezing 8, a common technique in deep RL [1]. Finally, Fitted Value Iteration [7] lies the other extreme and solves each iteration exactly when closed-form solutions exist. Therefore, a deeper understanding of the iterative optimization process (1) can facilitate a better understanding of TD and related RI. algorithms.
The iterative process (1) is well-studied in the setting where H is constructed using linear function approximation and squared error. In particular, with K 1, meaning TD without frozen target network, the most notable result is due to the seminal work of Tsitsiklis and Van Roy [3] that proved the convergence of the algorithm. More recently, Lee and He [8] focused on the more general case of K 2 1. While they took major step in understanding the role of a frozen aurge-nnetwork in deep RL, they leaned on the more standard optimization tools show that gradient-desceen K can be viewed as solving each iteration approximately. Therefore, in their analysis, each iteration results in some error. This error accumulated per iteration and needs to be accounted for in the final result. Therefore, Lee and He [8] fell short of showing convergence to the TD fixed-poing and managed to show that the final iterate will be in the vicinity of the fixed-point defined by the amount of error accumulated over the iterations.
with fixed
In this work, our primary contribution is generalize and improve existing results on TD conver- gence. In particular, in our theory, we can support the popular technique of employing frozen target networks with general K 2 1, and we also support the use of family of function approximators and error-measure pairs that includes linear function -pprroxmapooiiiiiiionn and squared error as a special case. To the best of our knowledge, this is the first contraction result that does not restrict to the case of K = 1, and can also generalize the well-explored linear case with quadratic error.
To build intuition, start by taking deeper dive into one of the classical examples where TD displays divergent behavior [3]. In doing so, we identify two key forces, namely a target force and an optimization force, whose interplay dictates whether TD is guaranteed to converge or that divergent behavior may manifest itself. If the optimization force can dominate the target force, the process is convergent even when we operate in the famous deadly triad [5], namely in the presence of bootstrapping. function approximation, and off offlicy updates. Overall, our results demonstrate that TD is a sound algorithm a much broader setting than understood in previous work.
2 Problem Setting
Reinforcement learning (RL) is the study of artificial agents that can learn through trial and error [5]. In this paper, we focus on the setting where the agent is interested in predicting the long-term good- ness or the value of its states. Referred to as the prediction setting, this problem is mathematically formulated by the Markov reward process (MRP) [9]. In this paper, we consider the discounted sefinite-horizon case of MRPs, which is specified by the tuple (S. R. P, 7). where S is the set of states. The function R. : S + E denotes the reward when transitioning out of a state. For any set, denote the space of probability distributions over it by A. The transition P S + A(S) defines the conditional probabilities over the next states given the current state, and is denoted by P(s' s)- Finally, the scalar y E (0, 1) geometrically discounts rewards that are received in the future steps.
The primary goal of this paper is to understand the behavior of RL algorithms that learn to approxi- mate the state value function defined as v(s) := E E rra so = s]. To this end, we define the Bellman operator T as follows:
[T)] = R(s) + Σxp(E P(s') s)u(s'),
S'ES
which we can write compactly as: To : R + yPu. In large-scale RL problems the number of states [S] is enormous, which makes it unfeasible use tabular approaches. We focus on the setting where we have a parameterized function approximator, and our desire is to find parameter 0 for which the learned value function vos;;) 0) results in a good approximation of the value function v(s))
A fundamental and quite popular approach to finding a good approximation of the value function is known temporal difference (TD) learning
[6]. Suppose that sample (s, (,rrs') s') is given where s' ~ P(-(s). In this case, TD learning algorithm updates the parameters of the approximate value function as follows:
(2) where of denotes the parameters of our function approximator at iteration Also, by Vou(s; 0*) we are denoting the partial gradient of v((; 0) with respect to the parameter O. Note that TD uses
0++1 - 0t + a(r + yu(s'; - v(s: 0') (eu(s;

---

the value estimate obtained by one-step lookahead (r + ro(s';0")) to update its approximate value function v(s; 0¹) in the previous step. This one-step look-ahead of TD could be thought of as sample of the right-hand-side of the Bellman equation. Our focus on TD is due the fact that many of the more modern RL algorithms are designed based on the principles that TD embodies. We explain this connection more comprehensively in section
To understand the existing results on TD convergence, we define the Markov chain's stationary state distribution d(.) as the unique distribution with the following property: s' Exes d(s)P(s' s) = d(s'). Then, Tsitsiklis and Van Roy show in [3] that, under linear func- tion approximation. TD will be convergent if the states s are sampled from the stationary-state distribution. We will discuss this result in more detail later on in section 5.
However, is arbitrary distribution rather than the stationary-state distribution of the Markov chain. A simple yet classical counter example of divergence of linear TD is shown in Figure I and investigated in section 4. First identified in [3], this example is very simple Markov chain with two non-terminal states and zero rewards. Moreover, little is known about convergence guarantees of TD under alternative function approximators, or even when the update rule of TD is modified slightly.
that linear TD can display divergent behavior if states sampled from an
In this paper, we focus on the Markov reward process (MRP) setting which could be thought of as Markov decision process (MDP) with a single action. TD can display divergence even in the MRP setting [3, 5]. which indicates that the presence of multiple actions is not the core reason behind TD misbehavior [5] Divergence can manifest itself even in the more specific case of single action. Our results naturally be extended to multiple actions with off-policy updates where in update (2) TD, actions are sampled according to a target policy but states are sampled according to a behavior policy. That said, akin to Tsitsiklis and Van Roy [3], as well chapter 11 in the book of Sutton and Barto [5], we focus on MRPs to study the root cause of TD in the most clear setting.
3 TD Learning as Iterative Optimization
In this section, we argue that common approaches to value function prediction can be viewed as iterative optimization algorithms where the function be minimized changes per iteration. To this end, we recall that for a given experience tuple (s, s')). TD performs the update presented in (2). A common augmentation of TD is to decouple the parameters to target (0) and optimization (w) parameters [1] and update 0 less frequently. In this case, at a given itcration t. the algorithm performs multiple (K) gradient steps as follows:
r + w + a(r + yu('';8)) v(s; w(t))) Voe
(3)
and then updates the target parameter G²+1 + w before moving to the next iteration t + 1. Here K is hyper-parameter, where K the dependence of v(s'; 0²) to our optimization parameter w is ignored in this update, despite the fact that implicit dependence is present due to the final step g++1 w This means that the objective function being optimized is made up of two separate input variables?. We now define:
takes us back to the original TD update (2). Observe that
1 Σ ((s) + ro(s':0) ro - v(s; u(); H(0, w) 2
where we allow d(-) to be an arbitrary distribution, not just the stationary-state distribution of the Markov chain. Observe that the partial gradient of H with respect to the optimization parameters w is equivalent to the expectation of the update in (3). Therefore, TD, DQN, and similar algo- rithms could best be thought of as learning algorithms that proceed by approximately solving for the following sequence of optimization problems:
g++1 ss arg min H ((' w),
using first-order optimization techniques. This optimization perspective is useful conceptually be- cause it accentuates the unusual property of this iterative process, namely that the first argument of the objective H hinges the output of the previous iteration. It also has important practical ramifications when designing RL optimizers [11]. Moreover, the general form of this optimization
'In fact, [10] shows that there cannot exist any objective function .(0) with a single input variable whose gradient would take the form of the TD update.
3

---

process allows for using alternative forms of loss functions such as the Huber loss [1], the logistic loss [12]. or the entropy [13], well as various forms of function approximation such linear functions or deep neural networks. Each combination of loss functions and function approximators
yields different H. but one that always comprised of function H with two inputs.
A closely related optimization process is one where each iteration is solved exactly:
@++1 f arg min H (0", w)
(4)
akin to Fitted Value Iteration [7. 14]. Exact optimization is doable in problems where the model of the environment is available and that the solution takes a closed form. pscudo-code of both algorithms is presented in Algorithms I and 2.
Algorithm Value Function Optimization with
Algorithm 2 Value Function Optimization with Gradient Updates
Exact Updates
Input: 00, T for t 0 to T do
Input: 80, T. K,
fort 0 1oo I
do
g++1 t arg min H (0', w)
w t 0r
end for Return HT
for k writl + wiik
to K do
a H(0
end for
0++1 w
end for Return 0r
In terms of the difference between the two algorithms, notice that in Algorithm 1 we assume that we have the luxury of somehow solving each iteration exactly. This stands in contrast Algorithm where we may not have this luxury, and resort to gradient updates to find a rough approximation of the actual solution. Thus, Algorithm 1 is more difficult apply but easier to understand, whereas Algorithm 2 is easier to apply but more involved in terms of obtaining a theoretical understanding.
Note that if convergence manifests itself in each of the two algorithms, the convergence point de- noted by l must have the following property: V (00
(5) This fixed-point characterization of TD has been explored in previous work [15, 16). Whenever it exists, refer to 8* the fixed-point of these iterative algorithms. However, convergence to the fixed-point is not always guaranteed [5] even when we have the luxury of performing exact minimization akin Algorithm 1. In this paper, we study both the exact and inexact version of the optimization process. In doing so, we identify two forces that primarily influence convergence. To begin our investigation, we study counter example to build intuition on why divergence can manifest itself. We present formal analysis of the convergence of the two algorithms in section 6.
4 Revisiting the Divergence Example of TD
In this section, we focus on a simple counter example where TD is known to exhibit divergence. First identified by [3], investigating this simple example enables to build some intuition about the root cause of divergence in the most clear setting.
Shown in Figure 1, this example is a Markov chain with two non-terminal states and zero rewards. A linear function approximation, v(s; 0) ((s)0, is employed with single feature where d(s1) and (x22) 2. The third state is a terminal one whose value is always zero. The true value function (0 in all states) is realizable with 0 = 0.
To build some intuition about the root cause of divergence, we discuss the convergence of exact TD with a few state distributions in this example. We desire update all but the terminal state with non-zero probability. However, to begin with, we focus on particular extreme case where we put all of our update probability behind the second state:
g++l +- arg min H w) arg min 1 ((1 (11 (1)20)))) -2w)²
2
We thus have V H w) 2(2 - (1 2))) and since V H,,, 10+1) 0. we can write:
gt-1 + 12 20 The process converges to the fixed-point 0 = 0 for all values of y

---

larger c). In this case, the update of 82 and é E [0, 1]. This is because the target force of 0s (namely ((1 ([1-c)p <)22) is always dominated by the optimization force of (namely 2). Note that updating this state thus not problematic at all, and that the update becomes even more conducive to convergence when is smaller and is larger.
We now juxtapose the first extreme case with the second one where we put all of our update probability behind the first state, in which case at given iteration t have:
1 - E
0++1 f- arg min H(' ,w) arg min 1 5(220' w)² 10
w
2w
We thus have V.. w) (w )20 and Bt+1 (1)-1>20', Unlike the first extreme case, convergence is no longer guaranteed. Concretely, ensure convergence, require that the target force of 0t (namely 72) be larger than the optimization force of w. (namely 1).
&
Figure 1: Divergence exam- ple of TD [3].
To better understand why divergence manifests itself, note that the two states $1 and $2 have very similar representations (in the form of a single feature). Note also that the value of the feature is larger for the target state than it is for the source state, (x2)) d(s1). This means that any change in the value of the source state 81, would have the external effect of changing the value of the target state $2. Further, the change is in the same direction (due to the positive sign of the feature in both states) and that it is exactly 27 larger for the target state relative to the source state. Therefore, when y 1/2, the function H will be more sensitive to the target parameter 0 relative the optimization parameter w. This is the root cause of divergence.
Moving to the where update both states with non-zero probability, first note that if the two updates were individually convergent, then the combination of the two updates would also have been convergent in probability-agnostic way. Stated differently, convergence would have been guaranteed regardless of the probability distribution d and for all off-policy updates. However, in light of the fact that the optimization force of 81 does not dominate its target force, need to choose d($;) small enough so as to contain the harmful effect of updating this state.
We compute the overall update (under the case where we update the two states with equal probabil- ity) by computing the sum the two gradients in the two extreme cases above:
(w - --0"2 + 2(2w - 72(1 c)0') = 0,
and G++1 + ( 4t) Note that even with uniform update distribution, the two states are contributing non-uniformly to the overall update, and the update the state 82 is more influential because of the higher magnitude of the feature in this state (ő(s2) = 2 against dds1) = 1).
5_ Notice, again, that we are combining the update in a problematic state with the update in the state that conducive for convergence. We can contain the negative effect of updating the first state by ensuring that our update in the second state even more conducive for convergence (corresponding can serve mitigating factor.
To ensure convergence, we need to have that y < G-
We can further characterize the update with general distribution. In this case, have:
d(si)((w - -20")) + (1 - d(s))) - 72(1 - -))0)) =0,
Both the denominator and the numerator are always positive, therefore regardless of the values of and 7, there always exists convergent off-policy update, but one that needs to assign less probability to the problematic state as we increase ? and decrease
which gives us convergent update if: d(s1) <
4-47(1-e) 3412ー1x1-0
This means that using some carefully chosen off-policy distributions not only safe, but that doing so can even speed up convergence. This will be the case if the chosen distribution makes the objec- tive function H more sensitive to changes in its first argument (target parameter 0) than its second argument (the optimization parameter w). We next formalize this intuition.
5

---

Convergence of Linear TD with Quadratic Loss
We now focus on the case of TTD with linear function approximation. In this case, the expected TD update (2) could be written the composition of two separate operators (with Ut 20,):
U++1 t Dp (T(v)),
where the projection operator DT and the Bellman operator T defined as follows:
1 4 -
and T(v) R+ R
Here, D is diagonal matrix with diagonal entries d(s1).... d(s,), where n is the number of states. The projection operator II is non-expansive under any distribution d. However, the Bellman op- erator is a y-contraction under a specific d, namely the stationary-state distribution of the Markov chain specified by the transition matrix as shown by Tsitsiklis and Van Roy [3]. Therefore, the composition of the two operators is a 7-contraction when the distribution d is the stationary-state distribution the Markov chain.
In light of this result, one may think that TD is convergent in a very narrow sense, specifically when the updates are performed using the stationary-staie distribution. But, as example, in general there may exist many other distributions d that are in fact very conducive for TD convergence. these cases, the proof technique above cannot provide tool to ensure convergence because of the reliance of the non-expansive and contraction properties of these operators. Is this a limitation of the TD algorithm itself, or limitation of this specific operator perspective TD? Further, if this operator perspective is limited, is there a different perspective that can give rise to more general understanding of TD convergence?
with the counter
Our goal for the rest of the paper is to develop an alternative optimization perspective that can be applied in broader setting relative to the operator perspective. To this end, first task show that the optimization perspective can give us new insights even in the linear case and with squared loss functions. We generalize our optimization view of TD in the counter example by defining the objective function H for this case:
1 (6, w) 1 7P00 10000-pw1133 Pwll
(6)
Vx Dx. Recall that in the exact case, the TD algorithm could succinetly be written as: g++1 + arg min H (0', w). Following the steps taken with the counter example, we first compute the gradient derive the target and optimization forces:
where ||ح||
V V 4 D(Ow R PPD0)
1 DJD4e 7 DP 200---11 DR.
(7)
M.
Here we have similar dynamics between and w except that this more general case, rather than scalar forces as in the counter example, we now have the two matrices M and Mg. Note that M positive definite matrix, Amin (M.)) min, x M ||>>|| > 0, if full rank. Below we can conveniently derive the update rule of linear TD by using these two matrices. All proofs are in the appendix.
Proposition 1. Let {0"TEe be a sequence of parameters generated by Algorithm 1. Then, for the fixed-point 0+* and any E N, we have
g++1 - =0= M2 (0' 8*)
This proposition characterizes the evolution of the difference between the parameter 6¹ and the fixed-point 0*. Similarly to our approach with the counter example, we desire to ensure that this difference converges to O. The following corollary gives us a condition for convergence [17].
Corollary 2. Let (0* JIEN be sequence of parameters generated by Algorithm Then, {0' O"hen converges to the fixed-point 0* if and only the spectral radius of M M, satisfies p(M M,) ) < 1.
We can employ this Corollary to characterize the convergence of TD in the counter example from the previous section. In this case, we have M., = 5 and M, = 766 -4), which give us (5) 4e) < 1. This is exactly the condition obtained in the previous section.

---

Notice that if d is the stationary-state distribution of the Markov chain then p(M,, in Mo) < 1 [3], and so the algorithm is convergent. However, as demonstrated in the counter example, the condition can also hold for many other distributions. The key insight is to ensure that the distribution puts more weight behind states where the optimization force of ae is dominating the target force due f.
Note that the operator view of TD becomes inapplicable as we make modifications to H, because it will be unclear how write the corresponding RL algorithm demonstrate that in these cases the optimizatin perspective is still well-equipped to provide us with new insights about TD convergence? We next answer this question affirmatively by showing that the optimization perspective of TD convergence naturally extends to a broader setting than considered here, and therefore, is a more powerful perspective than the classical operator perspective.
composition of operators. Can we
6 Convergence of TD with General H
Our desire now is to show convergence of TD without limiting the scope of our results to linear approximation and squared loss. We would like our theoretical results support alternative ways of constructing H than the one studied in existing work as well as our previous section. In doing so, again show that convergence of TT hinges on the interplay between the two identified forces.
Before presenting our main theorem, we discuss important concepts from optimization that will be used at the core of our proofs. We study convergence of Algorithms and 2 with a general function H R x R + R that satisfies the following two assumptions:
I. The partial gradient V.. H. is Fo-Lipschit:
v01, v02
IV. w) V. H(2,, will S Follo; 0211
II. The function H(0, w) is Fu -trnnnllyyy convex w:
Vui, Viz
(V n (0, w1) V H(, (w) - w2) 2 Fuollu1 - w2ll" 12
Note that, in the specific linear case and quadratic loss (our setting in the previous section) these assumptions are easily satisfied [8]. More specifically, in that case Fg = Amaz and Fur = (M.) But the assumptions also satisfied in much broader setting than before. We provide more examples in section 6.3. We are now ready to present the main result of our paper:
Theorem 3. Let heN be a sequence generated by either Algorithm I or 2. If Fg < Fu. then the sequence {0 HeN converges to the fixed-point 0*
In order to prove the result, we tackle the two cases of Algorithm and 2 separately. We first start by showing the result for Algorithm I where can solve each iteration exactly. This is easier case to tackle because we have the luxury of performing exact minimization, which is more stringent and difficult to implement but easier analyze and understand. This would be more pertinent to Fitted Value Iteration and similar algorithms. We then move to the case where we approximately solve each iteration (Algorithm 2) akin to TD and similar algorithms. The proof in this case is more involved, and partly relies on choosing small steps when performing gradient descent.
6.1 Exact Optimization (Algorithm 1)
In this case, convergence to the fixed-point 0** can be obtained as a corollary of the following result: Proposition 4. Let (Ø*) hee be sequence generated by Algorithm 1. Then, have:
||
8*1l || S F. Follo" 8*
From this result, we immediately obtain that the relative strength of the two forces, namely the con- ducive force Fi due to optimization and the detrimental target force Fe, determines the algorithm is well-behaved. The proof of Theorem 3 in this case follows immediately from Proposition 4.
6.2 Inexact Optimization (Algorithm 2)
So far we have shown that the optimization process is convergent in the presence of exact optimiza- tion. This result supports the soundness of algorithms such as Fitted Value Iteration, but not TD yet, because in the case of TD we only roughly approximate the minimization step. Can this desirable
7

---

convergence result be extended to the more general setting of TD-like algorithms where we inex- actly solve each iteration by a few gradient steps, or is exact optimization necessary for obtaining convergence? Answering this question is very important because in many settings it would be stringent requirement to have to solve the optimization problem exactly.
We now show that indeed convergence manifests itself in the inexact case as well. In the extreme case, we can show that all we need is merely one single gradient update at each iteration. This means that even the purely online TD algorithm, presented in update (2), is convergent with general H if the optimization force can dominate the target force.
However, it is important to note that because we are now using gradient information to crudely approximate each iteration, need to ensure that the step-size parameter is chosen reasonably. More concretely, in this setting we need an additional assumption, namely that there exists an > 0 such that:
FW1, Vw2
HO, w1) V w2)ll S L|lw -w2l
Notice that such an assumption is quite common in the optimization literature (see, for instance, [18]). Moreover, it is common choose a L/L, which we also employ in the context of Algo-
rithm 2. We formalize this in the proposition presented below:
Proposition 5. Let {0")ee be a sequence generated by Algorithm with the step-size a = 1/L. Then, have:
| -
8* *1 S σ ox -
where:
o = (1- (1- +1²
with K = F. and 17 = F. 1FF1P Fe.
Notice that K, which is sometimes referred to as the inverse condition number in the optimization literature, is always smaller than Therefore, we immediately conclude Theorem 3. Indeed, since the optimization force dominates the target force (meaning 1) < 1), Algorithm 2 is convergent. Notice that a surprisingly positive consequence of this theorem that we get convergent updates even if we only perform one gradient step per iteration (K 1). In deep-RL terminology, this corresponds to the case where we basically have no frozen target network, and that we immediately use the new target parameter 0 for the subsequent update.
To further situate this result, notice that as approaches oo then Øæ approaches 77, which is exactly the contraction factor from Proposition 4 where we assumed exact optimization. So this proposition should be thought of as a tight generalization of Proposition for the exact case. With a finite K we are paying price for the crudeness of our approximation.
Moreover, another interesting reduction of our result is to the case where the target force due to bootstrapping in RL is absent, meaning that Fg = O. In this case, the contraction factor o reduces to (1 - x) K/2, which is exactly the known convergence rate for the gradient-descent algorithm in the strongly convex setting [18].
6.3 Examples
We focus on two families of loss functions where our assumptions can hold easily. To explain the first family, recall that TD could be written as follows:
g++1 arg min ( w).
Now suppose we can write the function (0, w) the sum of two separate functions (0, w) G(O, w) + L(w), where the function L(w) is strongly convex with respect to w. This setting is akin to using ridge regularization [19], which is quite common in deep learning (for example, the very popular optimizer AdamW [20]). This allows us to now work with functions G that are only convex (in fact, weakly convex is enough) with respect to w. We provide two examples:
Suppose we would like to stick with linear function approximation. Then, the function G could be constructed using any convex loss where G(,, w) is Lipschitz-contimuous with respect to 0. Examples that satisfy this include the Huber loss [1] or the Logistic loss [12].
8

---

Suppose we want to use the more powerful convex neural networks [21]. We need the error to be convex and monotonically increasing so that G is still convex. This is due to the classical result on the composition of convex functions. One example is the quadratic error where we restrict the output of the function approximator to positive values. Such neural nets are also Lipschitz continuous given proper activation functions such as ReLU.
Beyond this family, we have identified second family, namely the control setting where a greedifi- cation operator is needed for bootstrapping. For example, with the quadratic error we could have:
H w) Σ d(s) Σ
x ((als) + max q(s a', 0)] q(s. a, w))?
where q is the state-action value function parameterized by either 9 or w.
We again need the two assumptions, namely strong-convent with respect to w and I Lipschitzness of V (0, w) with respect to 0 to hold, Actually, Lee and He [8] already showed the strong convexity with respect to w,, but we need to still show the Lipschitz property of V (0, w) with respect to 0. Note that they showed the Lipschitz property only with respect to w and not with respect to A. We are now able to show this result. Please see Proposition 8 and its proof in the appendix. Our proof also supports other greedification operators, such as softmax [22], so long as its non-expansive.
Related Work
In this paper, we studied convergence of TD through the lens of optimization. The underlying prin- ciples of TD are so central to RL that a large number of RL algorithms can be thought of as versions of TD, and the availability of convergence results varies between different types of algorithms. We chose a setting we believe is as elementary as possible to highlight key principles of TD conver- gence. Closest to work is the work of Tsitsiklis and Van Roy [3] who proved convergence of TD with linear function approximation, squared error, and the stationary-star distribution of the Markov chain. Later work, especially that of Bhandari et al. [23], further analyzed the case of TD with stochastic gradients and non-iid samples in the on-policy case. Extensions to the control setting also exist [24, 25].
In particular, Melo et al. [24] presented a condition in their equation (7) which may look similar to condition at first glance, but it is in fact quite different than the condition identified in our paper. In their equation (7), they require that the cigenvalues of Ma. the policy-conditioned covariance matrix & DΦ, dominate the eigenvalues of second matrix E (0). Here Σ (0) is similar covariance matrix for features, but one that is computed based on the action seiionngrediffiattion step.
We believe to be the first paper to show a exact contraction for TD with frozen target network and general K. To the best of our knowledge, existing results prior to Lee and He [8] mainly considered the case where we either never freeze the target network (corresponding to the value of K = 1), or the somewhat unrealistic case where we can exactly solve each iteration. Lee and He showed guarantecs pertaining to K > 1, but notice that, while their result is quite innovative, they leaned on the more standard optimization tools for ensuring that gradient descent with a fixed K can only solve each iteration approximately. Therefore, each iteration results in some error. In their theory, this error is accumulated per iteration and needs to be accounted for in the final result. Therefore, they fell short of showing 1) contraction and 2) exact convergence to the TD fixed-point and only show that the final iterate is in the vicinity of the fixed-point defined by the amount of error accumulated over the trajectory. With finite K, they need to account for errors in solving each iteration (denoted by ex in their proofs such as in Theorem 3), which prevent them from obtaining a clean convergence result. In contrast, we can show that even approximately solving each iteration (corresponding to finite K) is enough to obtain contraction (without any error), because we look at the net effect of K updates the online network and the single update the target network, and show that this effect is on that always take us closer to the fixed-point irregardless of the specific value of K.
Modifications of TD are presented in prior work that are more conducive to convergence analy- sis [26, 27, 28, 29, 30]. They have had varying degrees of success both in terms of empirical performance [31], and in terms of producing convergent algorithms [32]. TD is also studied un- der over-parannn pecerarrametiiiitioonn [33, 34], with learned representations [35], proximal updates [36], and auxiliary tasks [37]. Also, the quality of TD fixed-point has been studied in previous work [16].
large body of literature focuses on finding TD-like approaches that are in fact true gradient-descent approaches in that they follow the gradient of a stationary objective function [38, 15, 39, 40, 41, 42).

---

In these works, the optimization problem is formulated in such a way that the minimizer of the loss will be the fixed-point of the standard TD. Whereas TD has been extended large-scale settings, these algorithms have not been as successful as TD in terms of applications.
A closely related algorithm to TD is that of Baird, namely the residual gradient algorithm [4, 43]. This algorithm has a double-sampling issue that needs to be addressed either by assuming a model of the environment or by learning the variance of the value function [43, 44]. However, even with deterministic MDPs, in which the double sampling issue is not present [45], the algorithm often finds a fixed-point that has a lower quality than that of the TD algorithm [46]. This is attributed to the fact that the MDP might still look stochastic in light of the use of function approximation [38].
TD could be thought of as incremental approach to approximate dynamic programming and Fitted Value Iteration [7] for which various convergence results based on the operator view exits [14, 47, 48). Also, these algorithm are well-studied in terms of their error-propagation behavior [49, 50, 51].
Many asymptotic or finite-sample results on Q-learning (the control version of TD) with function approximation make additional assumptions on the problem structure, with a focus the explo- ration problems [52, 53, 54, 55, 56]. Like mentioned before, our focus was on the prediction setting where exploration is not relevant.
8 Open Questions
To foster further progress in this area we identify key questions that still remain open.
I. We showed that TD converges to the fixed-point 0 characterized by V "'" 0*) = 0 and the sequence VI )le converges to Can we further show that this sequence monotonically decreases with 6, namely that Vl ,(+1)] S H I1 for all t E N? Interestingly. a line of research focused on inventing new algorithms (often called gradient TD algorithms) that possess this property [57]. However, if true, this result would entail that when our assumptions hold the original TD algorithm gives us this desirable property for free.
II. Going back to the counter example, we can show convergent updates by constraining the representation as follows: ((s) I yo(s') whenever PPs' 8) > 0. This result can easily be extended to all MDPs with a single-dimensions feature vector. A natural question then is identify a multi-dimensional representation, given a fixed MDP and update distribution D, leads into convergent updates. Similarly, we can pose this question in terms of fixing the MDP and the representation matrix 4, and identifying a set of distributions that lead into convergent updates. Again, we saw from the counter example that putting more weight behind states whose target force is weak (such as states leading into the terminal state) conducive to convergence. How do we identify such distributions systematically?
III. We studied the setting of deterministic updates, To bridge the gap with RL practice, we need study TD under stochastic-gradier updates. The stochasticity could for instance be due to using a minibatch or using non-iid samples. Bhandari et al. [23] tackle this for the case of K- 1. Can we generalize our convergence result to this more realistic setting?
IV. We have characterized the optimization foree using the notion of strong convexity. It would be interesting to relax this assumption to handle neural networks and alternative loss func- tions. This can serve as a more grounded explanation for the empirical success of TD in the context of deep RL. Can we generalize our result to this more challenging setting?
9 Conclusion
In this paper, we argued that the optimization perspective of TD is more powerful than the well- explored operator perspective of TD. To demonstrate this, we generalized previous convergence results of TD beyond the linear setting and squared loss functions. We believe that further exploring this optimization perspective can be a promising direction to design convergent RL algorithms.
Our general result on the convergent nature of TD is consistent with the empirical success and the attention that this algorithm has deservedly received. The key factor that governs the convergence of TD is to ensure that the optimization force of the algorithm is well-equipped to dominate the more harmful target force. This analogy is one that can be employed explain the convergent nature of TD even in the presence of the three pillar of the deadly triad.
10

---

References
[1] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 2015.
[2] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanc- tot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 2016.
[3] John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffferen learning with function approximation. Advances neural information processing systems, 1996.
[4] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Muchine Learning. Elsevier, 1995.
[5] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[6] Richard Sutton. Learning to predict by the methods of temporal differences. Journal of Machine Learning Research, 1988.
[7] Geoffrey Gordon. Stable function approximation in dynamic programming. In Machine learning. Elsevier, 1995.
[8] Donghwan Lee and Niao He. Target-based temporal-differene learning. In International Conference on Machine Learning, 2019.
[9] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[10] Hamid Reza Maei. Gradient lemporal-difference learning algorithms. PhD thesis, University of Alberta, 2011.
[11] Kavosh Asadi, Rasool Fakoor, and Shoham Sabach. Resetting the optimizer in deep RL: An empirical study. Advances in Neural Information Processing Systems, 2023.
[12] Joan Bas-Serrano, Sebastian Curi, Andreas Krause, and Gergely Neu. Logistic Q-learning. In International Conference Artificial Intelligence and Statistics, 2021.
[13] Doina Precup and Richard S Sutton. Exponentiated gradient methods for reinforcement learn- ing. In International Conference on Machine Learning, 1997.
[14] Damien Ersst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 2005.
[15] Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard Sutton. Toward off- policy learning control with function approximation. International Conference on Machine Learning, 2010.
[16] J Kolter. The fixed points of off-policy td. Advances in Neural Information Processing Systems, 2011.
[17] Carl D Meyer. Matrix analysis and applied linear algebra. SIAM, 2000.
[18] Amir Beck. First-order methods in optimization. SIAM, 2017.
[19] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series (Methodological), 1996.
[20] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[21] Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Conference on Machine Learning, 2017.
[22] Kavosh Asadi and Michael I. Littman. An alternative softmax operator for reinforcement learning. In International Conference on Machine Learning, 2017.
11

---

[23] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, 2018.
[24] Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. Proceedings of the 25th international conference on Machine learning, 2008
[25] Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 2019.
[26] Richard S Sutton, A Rupam Mahmood, and Martha White. An emphatic approach to the problem off-policy temporal-difference learning. Journal of Machine Learning Research, 2016.
[27] Shangtong Zhang. Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with a target network. In International Conference on Machine Learning, 2021.
[28] Raghuram Bharadwaj Diddigi, Chandramouli Kamanchi, and Shalabh Bhatnagar. A conver- gent off off-policy temporal difference algorithm. arXiv, 2019.
[29]
Han-Dong Lim, Do Wan Kim, and Donghwan Lee. Regularized Q-learning. arXiv, 2022.
[30] Sina Ghiassian, Andrew Patterson, Shivam Garg, Dhawal Gupta, Adam White, and Martha White. Gradient lemporal-difference learning with regularized corrections. In International Conference on Machine Learning, 2020.
[31] Sina Ghiassian, Banafsheh Rafice, and Richard Sutton. A first empirical study of emphatic temporal difference learning. arXiv, 2017.
[32] Gaurav Manek and Zico Kolter. The pitfalls of regularization in off-policy TD learning. Advances in Neural Information Processing Systems, 2022.
[33] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning converges global optima. Advances Neural Information Processing Systems, 2019.
[34] Chenjun Xiao, Bo Dai, Jincheng Mei, Oscar A Ramirez, Ramki Gummadi, Chris Harris, and Dale Schuurmans. Understanding and leveraging overparameterrizaion in recursive value esti- mation. In International Conference on Learning Representations, 2021.
[35] Dibya Ghosh and Mare Bellemare. Representations for stable off-policy reinforcement learning. In International Conference Machine Learning, 2020.
[36] Kavosh Asadi, Rasool Fakoor, Omer Gottesman, Taesup Kim, Michael Littman, and Alexan- der Smola. Faster deep reinforcement learning with slower online network. Advances in Neural Informtion Processing Systems, 2022.
[37] Clare Lyle, Mark Rowland, Georg Ostrovski, and Will Dabney. On the effect of auxiliary tasks representation dynamics. In International Conference Artificial Intelligence and Statistics, 2021.
[38] Richard Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-differee learn- ing with linear function approximation. In International Conference on Machine Learning, 2009.
[39] Bo Liu, Sridhar Mahadevan, and Ji Liu. Regularized off-policy TD-leaningg Advances in Neural Information Processing Systems, 2012.
[40] Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Proximal gradient temporal difference learning algorithms. In International Joint Conferences Artifi- cial Intelligence, 2016.
[41] Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite- sample analysis of proximal gradient TD algorithms. arXiv, 2020.
[42] Yihao Feng, Lihong Li, and Qiang Liu. kernel loss for solving the Bellman equation. Ad- vances in Neural Information Processing Systems, 2019.
12

---

[43] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman--esiie residual minimization based fitted policy iteration and single sample path. Jour- nal of Machine Learning Research, 2008
[44] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song- Sbeed: Convergent reinforcement learning with nonlinear function approximation. In Interna- tional Conference on Machine Learning, 2018.
[45] Ehsan Saleh and Nan Jiang. Deterministic Bellman residual minimization. In Proceedings of Optimization Foundations for Reinforcement Learning Workshop at NeurIPS, 2019.
[46] Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of Machine Learning Research, 2003.
[47] Daniel Lizotte. Convergent fitted value iteration with linear function approximation. Advances in Neural Information Processing Systems, 2011.
[48] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep Q-learning. In Learning for Dynamics and Control, 2020.
[49] Rémi Munos. Performance bounds in I-pnoom for approximate value iteration. SIAM journal on control and optimization, 2007.
[50] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008
[51] Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for ap- proximate policy and value iteration. Advances in Neural Information Processing Systems, 2010.
[52] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, 2020.
[53] Simon S Du, Yuping Luo, Ruosong Wang, and Hanrui Zhang. Provably efficient Q-learning with function approximation via distribution shift error checking oracle. Advances in Neural Information Processing Systems, 2019.
[54] Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic Q-learning with function approximation deterministic systems: Near-optimal bounds on approximation error and sample complexity. Advances in Neural Information Processing Systems, 2020.
[55] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 2020.
[56] Shuhang Chen, Adithya M Devraj, Fan Lu, Ana Busic, and Sean Meyn. Zap q-learning with nonlinear function approximation. Advances in Neural Information Processing Systems, 2020.
[57] Richard S Sutton, Hamid Maei, and Csaba Szepesvári. A convergent o(n) semporal-different algorithm for off-policy learning with linear function approximation. Advances in neural in- formation processing systems, 2008
13

---

10 Appendix
Proposition Let {0' HeN be a sequence of parameters generated by Algorithm Then, for the fixed-point 0* and any E N. we have
g++1 - = M2
MM (0' - -8")
Proof. Since 0++1 arg min,, H w) we have w.. (0,, 0++1) = 0. Using (7) we have:
M,, Φ DR MaO' (M Ma)0 Ma0',
where the last equality follows from 0 being the fixed-point and therefore vm,h(0",00 = 0, which in light of (7) translates to क DR (M, Ma)0". Multiplying both sides by M_ we get:
0++1 = (T M,) + M M.'
Rearranging the equality leads into the desired result.
Proposition 4. Let (0' HeN be a sequence generated by Algorithm 1. Then, we have:
||gh+1 8*1| S F Fo 8*
Proof. First notice that 0++1 arg min,. H w), have V. (0', 0(+1) 0. Now, using the -stong convexity of w + H H w), we get that
F Fu - 11 s (0* - gh-1 V H(O' 0-) - "
(0' yf v v (0' (0')00)) (from V H(', 10000000000 00+11 0).
Now, since 8* a fixed-point, it follows that V (0" 0r) = 0. Therefore, we have:
F 10 0-1 < (0" 0++1 V (0', 0²) - V.. ",00,000 0*)) - || 00 V H (0" 0-) V (00
Fo 10 0* 110 0*1
where in the second line we used to Cauchy-Schwartz inequality, and the last inequality follows from the Fa-Lipschitz property of (., ),). Since this inequality holds true for any N, get that if = 0*, then we also have that 0++1 0* Thus, if 0² = 0* for some T E N, then H 8" for any t 2 and so the algorithm has converged. On the other hand, if 0 # 8* for all t N, the desired result follows after dividing both sides by ||@r+1 - 1*
14

---

To prove Proposition 5 we need to provide two new Propositions to later make use of. We present these two proofs next, and then restate and prove Proposition 5.
Proposition 6. Let {0 HENN be a sequence generated by Algorithm 2. Then, for all L E N and S k K we have
F2 2F
(1 a 2
L 2)
H(6 H(A', w S
100 8-12
Proof. Let & N. From the -trong convexity of w HO',, w), obtain that
Fw 1 - 11
H(0', w 10'0 0*) + (V (V wht -07)
2
which means that
F"
H1'', H0' w S
withh1)
| 00'1.
(8)
2
Moreover, in light of the fixed-point characterization of TD, namely that V. 0*) 0,
write
(V n H (0',0))00 - wrh+l) = (V H0' 0-) - V.' (0010000),,0 wiitt)
(V H ,8)) (,-H(0080) (0) whxtt1
V.. 00) HmH "00((000))1) 0²11 F'r | -0
0-1
2F
2
< 110t 8¹12 + Fw 2 - -
F
2
Here, the first inequality follows from the fact that a b (1/2d) ||l|| (d/2)llb|² for any d > O. In this case, we chose d = F... Also the last inequality follows from the Fp-Lippshhizz property of V., H, which is our assumption.
any two vectors a and we have
Now, by combining (8) with (9) we obtain that
F 0
F 2
Fu I /k 1-
H (10%,0)) H00 x <
11
||
-
111
2F
2
F2 112
||0'
(10)
2F
From the Lipschitz assumption write, due to the Descent Lemma [18] applied to the function w + HH'', w), that:
H(6 w w (0' whth S H(', wiik), wri wii + I. | 112
2
Now, notice that according to Algorithm 2 we have whh+1 with W (00, ww):)))), and so we can write:
(witi wiit1 whtt wii + Io llockktt w 22
H("", ww/tt) H(0 whh) <
a
1
L
1p
(1I)
2
Adding both sides of (10) with (11) yields:
H(O', 0*) - H(O', 2 <
F2 2F
10
0-1/2
(
--4 2
1/2
|| - wh
a
which proves the desired result.
15

---

Now, we can prove the following result.
Proposition Let (0" a sequence generated by Algorithm 2. Then, for and 0 O k K - we have
| 0¹11² $ (1 wn) 1 f 0-112+ + oFF
1 - 0- (2 (2-o || w
F..
In partieular, when 1/L,, we have
|| - - 1- (1111111
Fer I
FØ LF
ll - 1-11
+
110e 1-1
Proof. Let E N. From the definition of steps of Algorithm 2, that is, whht1 w HW w for any 0 S & < K- I, we obtain that
| - 1-1 l1 8²) a w H w²
lwok - 112 + 2a V W (0', w0(h) - + H( w
lwok 1-112 + 20 V H (0 wh ) ,
wiit + || w/ (12)
Using the Strong convexity + H(0', w) we have
Fwr
H (0', 8*) 2 H (0', whhh W (6', wtth), 0 wht Combining (12) and (13), get:
1 0-112. (13)
2
Fy w - 00113)
||w -0" < 1 k - 0¹112 + 2a 11 (0',0) - -1 (0', w(/,)
2
+ ||0 12
a l/u 1- 2a (H (0r, (0'
H (0t, .et.ki)) 1110 wt
Hence, from Proposition 6, we obtain
F
00 0¹1 (1) a 2 -)) |1o0 w
| 11112 < (1-af' aFF) |/ - 0-112+ 2a
2FF
+ ||00 12
aF
= =(1 a || 11 +
1
8¹112 - (2 aL) |10 w 11
F
which completes the first desired result.
Moreover, by specifically choosing the step-size a 1/L we obtain that:
Fu
F
1 - --112
|/ - -1
0
8¹11
110 w12
L
LF.
Fw
|1100 - 112 +
F
1
8^112
L
LF
This concludes the proof this proposition.
16

---

Using these two results, we are ready to present the proof of Proposition 5
Proposition Let {00) JTeN be a sequence generated by Algorithm with the step-size a = 1/L. Then, we have:
1 - 00 S xx - 00 -001
where:
o = (1 - (1=x)* (1 (1-17- 11-) +
with i. = F., and 1) F Fo.
Proof. Let 1 E N. From Proposition (recall that a = L)L) and the fact that 0++1 = wA,, we have
| - 0-11
|| 1-
S (1 x) ||l 0-11²+ =/>==00'' 0
S (1 x) [11 - K)) 1| 1- + n²²x100' - 0- [|=] + n/211110 0 1|
(1 xx)² / - 00112 + n/²x( (1 + - -x)) 1100 - 10
$ ...
K-1
$ (1 - 1:) ik | -0"112 + +12 K Σ
(1 - x)* 110- 11?
k=0
K-1
(1 - x) x 110 10
11 + 1/
(1 x)) k 110 1-,,
k=0
where the last inequality follows from the fact that w fr. Because is E [0, 1], the geometric series on the right hand side is convergent, and so we can write:
1 - (1 k) K xa-x)= +1²
(1 - K)
(1 - x) +n? (1-(1-
(1 -x))*))
(1 K)
which completes the desired result.
17

---

Now, following our discussion in Section 6.3 about examples of loss functions that satisfy our as- sumption, we recall that here we focus on the following loss
H (6, w) 1 Σ d(s)
Σ I(aas)) (Bs
[r
+ +y q (s', 0)] q (s, a, w) ?
As mentioned in Section 6.3 all is left is to show that Lipschitzness of V., H. (0,w) with respect to 0.
Proposition 8. Assume that for any (s,a), the function 0 q (s, 0) is (g -ipschhii Then,
there exists Fg > such that
v0,, v02
[V, w) H.. Foll: 8211.
Proof. First, we compute the gradient V H::
V V. H (0, = Σ d(s) Σ raass) (q (1(8, w) - E. r max a ((), Va as)
o
For the simplicity of the proof, we denote Q()).02) = max (s', - max q (8', a', 01). Hence
V w(), V H(0,, w)]l =7 w
Σ d(s) Σ π (als) (E. [Q 02))) Vy (3, a w)
5 Σ d(s) Σ t(als) [ [Q 62)] |V (s, a, w)
where we first cancelled the common parts in both gradient terms and the inequality follows imme- diately from the Cauchy-Schwartz inequality. Now, by using Jensen's inequality on the expectation, we obtain that
V H (O,, w) V (02, w)ll S Σ d(s) Σ [(als)EB [Q(0), (2) VV (s, will
Moreover, without the loss of generality we can assume that maxa y (5', a', 02). max q (8', a', 0,0), which means that we can remove the absolute value and obtain the following
VV w) V H(,, wIll S 7 Ed(s) d(s) Σ (alss) [Q(1, 02) VV (s, a, w)ll
Now, by using simple property of the maximum operation, we obviously have that max q (s', a', 02) max q (s', a', 01) I max (q (s', a', 02) q (s', a' 01)) Since the function - q (s', a', 0) is Lipschitz, we have that (s', a', 02) - q (s',a',0) S (s,, - 0211-
is also well-known that for such functions the gradient bounded and therefore (s,
Lg Lg a). Combining all these facts yield
||V n (01, w) - V I (0z, w|ll <
d(s) Σ [(
< Σ d(s)
(als)) max (q (8', a', 02) - a (8', a' 033 [sV
< Σ d(s)
(als)
max max (s ..660. a d')110: 021| (s(3)))
S 0/ 0g |E max Ly (5' a') Σ d(s) Σ T(lss)
> |0 1
max Lg (s', c')2]
where the last equality follows from the basic properties of the distribution matrix D. This proves the desired result.
18


Reviews:
[{"review_id": "SjaMjtm3ZK", "reviewer": "Reviewer_16Sb", "summary": "The paper studies the convergence conditions for Temporal Difference (TD) learning utilizing a target network, and further extends its findings to scenarios where TD minimizes alternative losses beyond mean square errors. The study is conducted by formulating TD updates as iterative optimizations, under the help of a target network. Notably, the paper provides an intuitive description of the coefficients before the student's TD network parameter and the target network parameter as \"optimization force\" and \"target force,\" respectively. The paper reaches the conclusion that when optimization force dominants, the algorithm converges.", "questions": "(1) Do Huber loss, logistic loss and entropy loss satisfy all three assumption stated in Section 6 for inexact approximation? ", "limitations": "The paper did not discuss the limitations. Some discussions on an extension to stochastic updates and non-linear settings would be fascinating.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "(1) The paper is of high quality and clarity. The authors have provided a clear setting, accompanied by well-presented proofs and well-defined assumptions. The demonstration of the counterexample is worth mentioning, as it effectively and intuitively introduces the main idea of the paper.\n\n(2) The paper extends current studies of TD to cases where alternative losses, such as Huber loss, are used, closing a gap between the theory and practical algorithms.", "weaknesses": "(1) The paper focuses on Markov Reward Process, which is not a common setting for TD convergence proof. Why authors did not focus on expected updates? Could authors provide more reasoning for their choice?\n\n(2) The paper re-forms TD updates as iteration optimizations with the help of a target network. Could authors add more comparisons to the convergence results of TD with a target network? For example, \nBreaking the Deadly Triad with a Target Network, Zhang et al. (2021)\nTarget-Based Temporal-Difference Learning, Lee and He (2019)\n\n(3) Some empirical results to show that the empirical contraction factor aligns with their theory findings would be great. \n\n(4) The paper proposes an interesting point: for some safe state distribution, TD converges in the off-policy case. Could authors provide the analytical form of safe distributions? Also, how should we compute these distributions in practice? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent carefully reviewing the paper and for appreciating our work. Please find below some clarification regarding your questions.\n\n- The paper focuses on Markov Reward Process, which is not a common setting for TD convergence proof. Why authors did not focus on expected updates? Could authors provide more reasoning for their choice?\n\nThank you for highlighting this question. In our case, we just followed the MRP setting studied in Chapter 11 of Sutton and Barto (specifically Example 11.1). Having examined our results based on your question, we found that from the optimization point of view, studying TD in this MRP setting is identical to the setting where we look at the expected TD update. Therefore, our results can be framed in the expected setting and we are happy to add this framing to the paper.\n\n- Could authors add more comparisons to the convergence results of TD with a target network? For example, Breaking the Deadly Triad with a Target Network, Zhang et al. (2021) Target-Based Temporal-Difference Learning, Lee and He (2019)\n\nSure. We start by better situating our paper with respect to Lee and He (2019). While previous work primarily focused on $K=1$ (the setting of changing the target network after each update to the online network) the work of Lee and He (2019) was, to the best of our knowledge, the first paper that tackled general $K$. One limitation of their result is that they could only show that TD will find a solution in a region around the fixed-point because with finite $K$ the analysis needs to account for errors that are accumulated in each iteration. Another way to think about their result is that they can only show contraction if one uses gradient descent with infinite $K$ (which corresponds to exactly solving each iteration). With finite $K$, they need to account for errors in solving each iteration (denoted by $\\epsilon_k$ in their proofs such as in Theorem 3), which prevented them from obtaining an exact convergence result.\n\nIn contrast, in light of the more practical literature on TD where a finite $K$ is used, we were interested to show that 1) we converge to the TD fixed-point exactly and 2) with any finite value of $K$, the TD algorithm would give us a contraction. We indeed show in our main result that TD is a contraction with any value of $K$, which we believe we are the first paper to show this kind of result in the RL literature. More concretely, we show that smaller values of $K$ can damage the contraction factor, but each iteration will nevertheless remain contractive irregardless of $K$.\n\nIn terms of comparison with Zhang et al. (2021), notice that due to the difficulties pertaining to proving convergence for vanilla TD, a line of existing research was to equip TD with modifications to make it more conducive to convergence. In this case, Zhang et al. (2021) introduced two projection steps that are crucial for obtaining convergence. However, we were able to obtain a general result showing that vanilla TD converges with any value of $K$, and it also supports TD convergence in a broader setting.\n\n- Some empirical results to show that the empirical contraction factor aligns with their theory findings would be great.\n\nIn deriving a generalized proof for TD, our motivation was to be able to explain the remarkable empirical success of TD with general $K$ and beyond linear function approximators. We liked our theory to complement the existing evidence on the solid empirical performance of TD in the literature, and to provide further theoretical evidence that TD is a sound algorithm in a broader setting than understood in previous work.\n\n- The paper proposes an interesting point: for some safe state distribution, TD converges in the off-policy case. Could authors provide the analytical form of safe distributions? Also, how should we compute these distributions in practice?\n\nThis is in fact a very important open question. We note that the fact that we are now interested in this open question is an insight that is driven from our optimization perspective. We believe that highlighting this open question, as noticed by the reviewer, is in fact a merit and not a weakness of our work. We believe that this question should be investigated deeply in future work, and that while quite important, remains outside of the scope of our paper.\n\n- Do Huber loss, logistic loss and entropy loss satisfy all three assumptions stated in Section 6 for inexact approximation?\n\nPlease see our detailed discussion in the general comment part.\n\n- Some discussions on an extension to stochastic updates and non-linear settings would be fascinating\n\nAgain, please see our detailed discussion in the general comment part about non-linear examples. Also, based on our preliminary investigation our theory can be extended to the case with stochastic gradients, and so publishing this paper will open the gate for a more thorough investigation of this case and beyond.\n\n"}, {"review_id": "4sQ1DoKdMu", "reviewer": "Reviewer_gJiK", "summary": "The paper studies TD-learning with target network update. The authors recast the TD-learning algorithm into a time-varying optimization problem. The authors proves convergence for a function class with strong convexity and smoothness. ", "questions": "1. How strict is the condition $F_{\\theta}<F_{w}$ in Theorem 3? Can we find any examples other than tabular or linear setting to show the convergence under general setting? \n\n2. Can we also find conditions for to ensure the convergence for the Baird example?", "limitations": "In summary, the impact of theoretical result is not sufficient for the following reasons:\n\n- Assumption on strong convexity is too strong.\n\n- There are no examples or experiments showing convergence of general function class other than tabular or linear setting.\n\n- There are no compariosn between the existing works Lee et al., and Chen et al..\n\nHence, I am leaning towards rejection as for now.\n\nLee, Donghwan, and Niao He. \"Target-based temporal-difference learning.\" International Conference on Machine Learning. PMLR, 2019.\n\nChen, Zaiwei, John Paul Clarke, and Siva Theja Maguluri. \"Target Network and Truncation Overcome The Deadly Triad in $ Q $-Learning.\" arXiv preprint arXiv:2203.02628 (2022).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The paper is easy to follow and the motivation of the work is well explained by a simple example form $\\theta\\to2\\theta$. Moreover, the viewpoint of target force and optimization force seems to novel viewpoint, and the theoretical result seems to be solid.", "weaknesses": "1. Assuming strong convexity and lipschitzness is too restrictive to argue for a general function class. Moreover, regarding the condition $F_{\\theta}<F_{w}$ in Theorem 3, I believe this is the key condition for the convergence but the discussion seems to be missing whether it is a common condition to be met or not. \n\n2. The analysis on iterative optimization objective for tabular and linear case has been studied in Lee et al. and Zhang et al.. The comparison with the existing work seems to be insufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review. In what follows, we address the particular weaknesses and questions raised.\n\n- A discussion seems to be missing whether it is a common condition to be met or not.\n\nPlease see our detailed discussion in the general comment part.\n\n- The analysis on iterative optimization objective for tabular and linear case has been studied in Lee et al. and Zhang et al.. The comparison with the existing work seems to be insufficient.\n\nWe answered this question in depth in our general comment, but we are happy to distill our point here so we better situate our result in comparison to these two papers mentioned by the reviewer. Starting by Lee and He (2019), note that while we were able to show TD convergence, Lee and He can only guarantee that TD will find a solution in a region around the fixed-point because with finite $K$ the analysis needs to account for errors that are accumulated in each iteration. Another way to think about their result is that they can only show contraction if one uses gradient descent with infinite $K$. With finite $K$, they need to account for errors in solving each iteration (this is denoted by $\\epsilon_k$ in their proofs such as in Theorem 3). To better make the point, suppose that we solve the first iteration with some error, meaning that we approximately solve:\n\n$\\theta^{1} \\approx \\arg\\min_{w} H(\\theta^0,w),$\n\nbut then after we solve each iteration perfectly, meaning for $i\\geq 1$:\n\n$\\theta^{i+1} =  \\arg\\min_{w} H(\\theta^i,w).$\n\nClearly, one can think of approximately solving the first iteration as initializing TD to a point different than $\\theta^0$ and then doing perfect optimization in all iterations. The fact that we then can solve each subsequent iteration perfectly should give us exactly a contraction to the TD fixed-point based on our analysis. However, in this case the result of Lee and He (2019) can still only support convergence to a neighborhood characterized by the approximation error $\\varepsilon$. In contrast, in this case we can guarantee convergence exactly to the TD fixed-point.\n\nMoreover, in light of the more practical literature on TD where a finite $K$ is used, we were interested to show that 1) we converge to the TD fixed-point exactly and 2) with any value of $K$ the TD algorithm would give us a contraction. We indeed show in our main result that TD is a contraction with any value of $K$ (which we believe we are the first paper to show). More concretely, we show that smaller values of $K$ can damage the contraction factor, but each iteration will nevertheless remain contractive irregardless of $K$.\n\nIn terms of comparison with Zhang et al. (2021) and Chen et al. (2022), notice that due to the difficulties pertaining to proving convergence for vanilla TD, a line of existing research was to equip TD with modifications to make it more conducive to convergence. In this case, Zhang et al. (2021) introduced two projection steps that are crucial for obtaining convergence, and similarly Chen et al. (2022) studies the case where a truncation step is added. These are very important techniques, and they indeed can make TD more convergent. However, our convergence result does not lean on these projection and truncation steps and is applicable to vanilla TD as well as TD with alternative loss functions and function approximators.\n\n- Can we find any examples other than tabular or linear setting to show the convergence under general setting?\n\nPlease see our detailed discussion in the general comment part for more examples.\n\n- Assumption on strong convexity is too strong.\n\nNotice that the existing literature, including all the three papers mentioned by the reviewer, revolve around the linear function approximation case with quadratic loss function. This is just a special case of having a strongly-convex function. So, to the best of our knowledge, we are showing TD convergence in a setting that is less stringent and more general than the previous work. We would like to highlight that one can only hope to understand the more difficult cases (such as convex, weakly convex, and non-convex) by first understanding the most natural extension of the quadratic loss, namely the strongly-convex case. This was absent in existing work and our goal was to fill this gap.\n\n- There are no examples or experiments showing convergence of general function class other than tabular or linear setting.\n\nAgain, please see our detailed discussion in the general comment part for more examples."}, {"review_id": "xxR4Q9A3c5", "reviewer": "Reviewer_fasm", "summary": "This paper studies convergence of the TD algorithm from the perspective of solving a shifting optimization problem. Through a classic failure case, the authors uncover two forces, whose interplay reveals TD's convergence properties. These two forces both depend on the state visitation distribution, the state features, and the transition kernel. The authors point out that while the stationary-state distribution ensures convergence, this does not mean no other state visitation distributions can and seek to establish sufficient properties. They generalize their analysis to TD error defined with more general functions and provide these sufficient conditions. Assuming the TD error $H$ has a value function gradient that is Lipschitz in the target function parameters and is also strongly convex in the value function parameters, a more general convergence criterion can be derived. The authors extend this result to the setting where the shifting optimization problem is only solved approximately at each step using $K$ gradient updates.", "questions": "- line 164: where does the $1/2$ come from in the equation? If that is there for convenience, can you add a $1/2$ to the def of $H$ under line 117?\n- line 237: $M_w$ is positive definite if $\\Phi$ is full rank **AND** $D$ is full-rank, i.e., every state has positive probability under $d(s)$, no?\n- line 320: $L$ here is typically known as the strong-smoothness parameter, no? In contrast to the strong-convexity parameter.\n- line 330: the condition number I'm familiar with (see [1]) is always greater than or equal to $1$ (max eig / min eig). In this case, I think you mean the \"inverse condition number\". Also, this technically means, $\\sigma_K^2 = 1$ when $\\kappa=1$, in which case, the analysis does not imply convergence. Can you please discuss this corner case?\n- line 370: \"exits\" --> \"exists\"\n\n[1] Guille-Escuret, Charles, et al. \"A study of condition numbers for first-order optimization.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\nhttp://proceedings.mlr.press/v130/guille-escuret21a/guille-escuret21a.pdf", "limitations": "I see no need for discussion of negative societal impact in this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I found this paper to be very clearly written. To my knowledge, the claim in Proposition 1 and subsequent results are novel and make significant progress towards understanding convergence of the TD algorithm.", "weaknesses": "The paper does a great job explaining and motivating the novel TD convergence analysis, and I believe it can stand on its own as a \"theory paper\". But I think experimental support for the approach in a complex (e.g., deep RL) setting could have made the paper much stronger.\n\nI am also not entirely clear which results are novel and can be attributed to the authors vs which were known beforehand. Equation (7) does not appear to be novel; some form exists in [35], sec 4. The paper could benefit from better signposting to explain where others got stuck and this paper advances.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's carefully reading our paper as well as the overall quite positive assessment. Thanks for pointing out that the paper is clearly written and also thanks for recognizing the novelty of our work in terms of extending TD convergence proof to general $K$, as well as extending the function class from quadratic to other alternatives.\n\n- The paper does a great job explaining and motivating the novel TD convergence analysis, and I believe it can stand on its own as a \"theory paper\". But I think experimental support for the approach in a complex (e.g., deep RL) setting could have made the paper much stronger.\n\nIn deriving a generalized proof for TD, our motivation was to be able to explain the remarkable empirical success of TD for general $K$ and beyond the linear function approximators and in settings such as deep RL. We liked our theory to complement the existing evidence on the solid empirical performance of TD in the literature, and to provide further theoretical evidence that TD is a sound algorithm in a broader setting than understood in previous work.\n\n- I am also not entirely clear which results are novel and can be attributed to the authors vs which were known beforehand\n\nThanks for highlighting this. We would like to summarize here the two main contributions of our paper, which we will better highlight in the main paper as well:\n\n1- To the best of our knowledge, we are the first paper to show the contraction result of TD with general value of $K$. We show contraction with convergence to exactly the TD fixed point. In this space, closest to our work is that of Lee and He (2019), which could only show that TD with general $K$ converges to a region around the fixed-point. The part where they got stuck is where they use the more classical analysis that gradient descent only approximately solves each iteration, and so they need to accumulate some error along the way. In contrast, we can show that even approximately solving each iteration (corresponding to finite $K$) is enough to obtain contraction (without any error term). Even though Lee and He are correct in saying that using a finite $K$ results in approximately solving each iteration, we can still show that each iteration remains a contraction by looking at the net effect of the  updates to the online network and the single update to the target network. We prove that the net effect of these updates is one that ensures that the iterate makes steady progress towards the unique fixed-point irregardless of $K$.\n\n2- To the best of our knowledge, we are also the first paper to show TD convergence in the most natural extension of quadratic functions, namely the strongly convex case. This allows us to argue that slight modifications of TD in terms of loss functions and function approximators are also sound so long as they satisfy our assumptions. We are unaware of any previous work that tackled this extension. \n\n- where does the $\\frac{1}{2}$ come from in the equation?\n\nYes, you are correct that this was added for convenience and we should also add it in line 117. Thanks for catching the missing $\\frac{1}{2}$.\n\n- $M_{w}$ is positive definite if $\\Phi$ is full rank AND $D$ is full-rank, i.e., every state has positive probability under, no?\n\nYou are correct, and we will clarify this in the paper. Thanks for your diligence.\n\n- $L$ here is typically known as the strong-smoothness parameter, no? In contrast to the strong-convexity parameter.\n\nWe think the reviewer means ``global'' Lipschitz continuous, so yes you are correct, and we will clarify this.\n\n- the condition number I'm familiar with (see [1]) is always greater than or equal to  (max eig / min eig). In this case, I think you mean the \"inverse condition number\". Also, this technically means, $\\sigma_K^2=1$, when , $\\kappa=1$ in which case, the analysis does not imply convergence. Can you please discuss this corner case?\n\nYou are right in saying that we mean the inverse condition number here. In terms of the corner case, notice that if $\\kappa=1$ (which means we have a quadratic dependence to the online parameter), then $\\sigma_k=\\eta$, which given the assumption is less than one. Therefore, this is a contraction and convergence will be guaranteed.\n\n- line 370: \"exits\" --> \"exists\"\n\nWe will fix it. Thanks!"}, {"review_id": "peqrmHKmm7", "reviewer": "Reviewer_5ZUZ", "summary": "This work studies the TD learning algorithm from an optimization point of view which differs from the more classical fixed point Bellman operator point of view. The goal of the paper is to argue that this other viewpoint permits a better understanding of TD learning and a generalization of its convergence results explaining its practical success. The investigation of the known counterexample of TD divergence allows to identify the interplay of two forces that determine the  convergence behavior of TD learning, namely a so called target force and an optimization force. It is shown that TD shows a convergent behavior when the optimization force dominates the target one. These insights are then instantiated for linear function approximation with square loss and beyond under strong convexity and smoothness assumptions, even under the celebrated deadly triad.  \n", "questions": "In the following, I list a few questions of which the first two are the main ones, focusing on the limit point definition and the strength of the assumptions. \n\n1. All the theoretical results show convergence to the fixed-point $\\theta^{\\star}$. How is this point defined in those results?  Eq. (5) mentions that if convergence happens then $\\nabla_{w} H(\\theta^{\\star}, \\theta^{\\star}) = 0$.  Such a characterization (which is also the fixed-point characterization of the TD solution) is used in all the proofs. Then l. 142-143 precise that ‘Whenever it exists, we refer to $\\theta^{\\star}$ as the fixed point of these iterative algorithms’. For the convergence results to be meaningful, the existence of the fixed point should be guaranteed. I guess you define $\\theta^{\\star}$ to be the fixed point of the projected Bellman operator which is indeed a contraction under some conditions but this is not very clear in the paper. However, as alluded to in the paper in l. 212-218, it is not clear whether the projected Bellman operator is still a contraction when one considers a distribution different from the stationary state distribution of the Markov Chain. What would then be the limit point(s) in the results in the case where existence is not guaranteed by the fixed point arguments relying on the operator viewpoint? Do you just suppose in that case that there exists a unique point such that $\\nabla_{w} H(\\theta^{\\star}, \\theta^{\\star}) = 0$ (which is what is required and used to conduct the proofs)? \n\n2. Concerning the assumptions and the examples provided in Section 6, input-convex neural networks [18] provide convex functions with respect to the inputs and not with respect to their weights (parameters). How these would help to guarantee that the strong convexity assumption 2 holds? Satisfying both assumptions does not seem straightforward. The constants $F_{\\theta}$ and $F_{\\omega}$ are uniform constants over $\\theta$ and $w$ that are not easy to define and compute in practice which makes the core stability condition $F_{\\theta} < F_{w}$ difficult to verify. I understand though that the focus of the paper is theoretical. Even in the linear setting and assuming that the feature matrix is given and known, can we for example suggest some distributions beyond the stationary state distribution for which the condition holds?  \n\n3. Regarding section 4, when you mention that the counter example was identified by [3], are you referring to Section IX in Tsitsiklis and Van Roy 97 (TAC) for this? Is it a simplified/modified example of that one? \n\n4. Could you mention the stationary state distribution of the Markov chain for the counter example? This could be added if relevant to show that this stationary distribution is indeed valid and leads to a convergent behavior as expected.  \n", "limitations": "Beyond the points raised above, one limitation that is not clearly mentioned is that the convergence results are limited to the deterministic setting. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- Understanding the behavior of the celebrated TD learning algorithm in the deadly triad setting and beyond the linear function approximation setting  is an important research goal given the popularity of the algorithm and its potential impact in RL. \n\n- Interesting insights starting from the simple counter example in Section 4 are provided and clearly explained. \n\n- The paper is very well-written, well-organized and overall easy to follow. To the best of my knowledge, proofs (including the appendix) are correct and cleanly presented. \n", "weaknesses": "1. It is not made very clear that the scheme proposed is actually different from the classical TD learning which was analyzed in [3] since the iterate $\\theta_t$ of the target network is frozen. The paper considers a ‘target-based’ version of TD learning which was inspired by the DQN algorithm using target networks [1].  \n\n2. Since one of the motivations of the paper is to show that the optimization point of view allows to address more general settings than the linear function approximation setting with square loss, I would expect a more detailed discussion of these cases in Section 6 giving the definitions of the $H$ function in that case and verifying the uniform assumptions 1 and 2 of Section 6. The discussion in l. 277 to 280 is quite minimal. The generalization does still seem a bit restrictive and the analysis provides sufficient conditions that do not close the question of the understanding of the divergence behavior of TD learning. See also the Questions section. \n\n3. Although the interpretation in terms of ‘target force’ and ‘optimization force’ has not been described as such in prior work to the best of my knowledge, arguments to show the results are quite classical and technical novelty is very limited in my opinion. The proofs of section 5 rely on the classical stability criteria in control for linear systems and was also used in other works ([16], see also discussions below about related works) even if the possibility of using other distributions instead of the stationary one was not described.The proofs for Section 6 follow standard analysis of gradient descent like algorithms for smooth and strongly convex objectives up to the drifting parameter $\\theta_t$ which is periodically synchronized with the online iterate. \n\n4. **Related work**: Closely related works are not discussed in detail, especially those analyzing the ‘target-based’ version of TD learning which is central in this work. \n\n**(a)** While the present work indeed provides some new insights, the optimization perspective proposed in this work is not completely new and I believe some additional discussion regarding this would be welcome. As a matter of fact [16] is only briefly mentioned in l. 275 whereas the optimization point of view is alluded to in the remark in Section 2.4  of [16] (see also sections 3 and 5 therein) where the modified version of the Mean Square Bellman Operator with two variables  (target and online) clearly appear. While the generalization beyond linear function approximation and the squared loss (under some Lipschitzness and strong-convexity assumptions) and the flexibility to consider a different distribution from the Markov chain’s stationary distribution are interesting  insights, the results of Proposition 1 and Corollary 2 are not very novel. For instance, instead of periodically synchronizing the target network with the online one as in Algorithm 2, one could also consider the online moving average update rule proposed in the popular DDPG algorithm (Lillicrap et al. 2016) which was analyzed in the linear function approximation on-policy setting in [16, sections 2, 3, 5] and in Barakat et al. 2022 (see Sections 4.2, 5.1, 6.1).  The aforementioned results also provide almost convergence results and sample complexity analysis accounting for noisy settings unlike the present work. \n\nLillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning, ICLR 2016.\n\nBarakat, A., Bianchi, P., Lehmann, J. Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation, AISTATS 2022.\n\n**(b)** If one of the main motivations or consequences of this work is to show that the ‘optimization viewpoint’ can explain the possible convergent nature of TD learning in the presence of the deadly triad as mentioned in the conclusion (under some assumptions and some suitable choice of the sampling distribution in the off-policy case), then, the ability of the target-based updates (which is actually the ‘optimization point of view’) was also advocated for in Zhang et al. 21 [25] at least in the linear function approximation setting (see Section 4 for off-policy evaluation with Q functions which could be easily adapted to V functions). \n\n**(c)** Further works such as Liu and Olshevsky 2021 could also be relevant to mention. This work points out that original TD learning (i.e. Eq. (2), as proposed in [6] and analyzed in [3]) can be seen as what they call a ‘gradient splitting’ (see Section 3 therein) even if it is known that the TD learning update rule does not correspond to any gradient descent over any function.   \n\nLiu, R., Olshevsky, A. Temporal Difference Learning as Gradient Splitting, ICML 2021.\n\n**(d)** Several works have also considered the analysis of TD learning with nonlinear function approximation beyond the linear setting (see e.g., Brandfonbrener and Bruna 2020; Agazzi and Lu 2021 to name a few). A discussion about these works seems also relevant given the generalization motivation of the present work.  \n\nBrandfonbrener, D., Bruna, J. Geometric insights into the convergence of nonlinear TD learning, ICLR 2020.  \n\nAgazzi, A., Lu, J. Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes, MSML 2021.\n\n**Minor typos:** \nl. 104: ‘the root cause of TD’, of divergence?  \nl. 242: capital $H$ instead of $h$\nl. 541-542: $\\theta^{\\star}$ instead of  $\\theta^{*}$\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing that we have tackled an important research goal, for stating that our paper is insightful, clearly-written and well-organized, and also for your diligence in checking our proofs.\n\nIn terms of weakness 1, we will emphasize better that one of the major contributions of our paper is to show convergence of TD under a frozen target network ($K>1$). In fact, our results include the special case (with $K=1$), but also bridges the gap with practice where usually a much larger value of $K$ is used. We will put more effort to emphasize this.\n\nIn terms of discussing examples that satisfy our assumptions, Please see our detailed discussion in the general rebuttal. We will add this to the paper.\n\nIn terms of weakness 3, the novelty of our results, we respectfully disagree that the proof techniques are standard. In fact, by following the standard proof techniques of gradient descent (which Lee and He 2019 leveraged) they end up with an error term that accumulates over iterations, and so exact convergence to TD fixed-point cannot be shown with a finite $K$. Using proof techniques that are new to the RL literature, we showed for the first time that irregardless of the value of $K$, and under the natural extension of quadratic loss, contraction can be shown, and convergence to exactly the TD fixed-point can be concluded. To the best of our knowledge, this is a quite novel and significant.\n\nAs for Section 5 about linear approximatiors and squared loss, our intention was not to say that we are very novel in exploring this setting (we provided credit to van Roy Tsitsiklis and other influential papers). Our intention was merely to formalize our intuitions from the counter example, before moving to the general setting in Section 6 and present our main novel result. We are happy to clarify this in the paper.\n\nIn terms of related work, we agree that more discussion will strengthen the paper. We extensively discussed relationship to two of your suggested papers in our general rebuttal and in response to reviewer 16Sb. Here, we discuss a third paper you mentioned and defer further discussion to the paper due to space limits. In the case of gradient splitting work of Liu and Olshevsky. Their contribution is to introduce the notion that the update of the TD algorithm with $K=1$ could be thought as gradient splitting. Leveraging this insight, and by adding a projection step to TD, they improved the sample complexity bound of Bhandari et al (which we have cited in the submission). The key difference with our case is that we are interested in vanilla TD convergence under general $K$ and also that we have extended the quadratic loss to the somewhat more general case of strongly-convex functions. Nevertheless, we found this work quite interesting and will add this to the paper. Thanks.\n\nPlease rest assured that based on our investigation the other papers you mentioned, while quite innovative, do not undermine the novelty of our work. We will cite and discuss them, and we hope the reviewer considers increasing their score in light of our better situating our paper. \n\nRegarding the existence of a fixed point, we want to make a distinction between existence of a fixed-point and the fact that a certain operator is a contraction. For example, in the counter example a fixed-point always exists (namely $\\theta^{\\star}=0$), for which $\\nabla_{w} H(\\theta^{\\star},\\theta^{\\star})={\\bf 0}$. This is despite the fact that for some distributions TD might be divergent. So, the existence of a fixed-point is a property of the problem, not the algorithm that attempts to find the solution to that problem.\n\nMore generally, in the linear case with quadratic loss we can show that a fixed-point always exists under very mild assumptions. In particular, from $\\nabla_{w} H(\\theta^{\\star},\\theta^{\\star})=0$ we get:\n\n$\\Phi^{\\top} D(R+\\gamma P\\Phi\\theta^{\\star} - \\Phi\\theta^{\\star})=0,$\n\nmeaning:\n\n$\\theta^{\\star} = \\big(\\Phi^{\\top}(I - \\gamma P)\\Phi\\big)^{-1}\\Phi^{\\top} D R.$\n\n$P$ is a stochastic matrix, so $(I-\\gamma P)\\succ 0$, therefore the inverse always exists and the problem always has a unique fixed-point. Some algorithms might diverge in their attempt to find the fixed point, but that does not change the fact that it exists.\n\nMore generally it is an open question whether there exists a fixed-point with alternative $H$. We generally need additional information to answer this question. In the optimization literature determining if a problem has a solution is a vibrant research area. However, this is beyond the scope of this paper, and we would love to explore this direction once this paper gets accepted.\n\nTo clarify our pointer to input-convex neural nets, the reviewer is correct in saying that the original paper focused on the convexity of the net with respect to the input given fixed weights. That said, the same network architecture the paper proposed is also convex with respect to the weights given a fixed input. To see this, consider the class of functions $f(x,\\theta)=ReLU(x^{\\top}\\theta)$. Notice that this function is both a) convex with respect to $x$ given fixed $\\theta$, and b) convex with respect to $\\theta$ given fixed $x$. Thank you for your astute question, and we will clarify this in the paper.\n\nRegarding the counter example, we took it from the standard textbook of Sutton and Barto. In their Example 11.1, Sutton and Barto credit it to van Roy and Tsitsiklis and we followed the standard they set.\n\nRegarding the stationary-state of the example, the distribution depends on the parameter $\\varepsilon$ used to define the transition model. In particular, it assigns $\\frac{\\varepsilon}{1+\\varepsilon}$ to the first state, and $\\frac{1}{1+\\varepsilon}$ to the second state. We add this to the paper.\n\nYou are right about the deterministic limitation. To clarify, we support stochastic transition matrices, but that the gradient computation needs to be exact (deterministic). We will add this limitation."}]

Author rebuttal:
We appreciate the thoughtful feedback provided to us by our reviewers. All reviewers agreed that our results are clearly articulated. Notably, Reviewer 16Sb believes that the paper is of high quality and is accompanied by well-presented proofs. Also, Reviewer fasm confirms that our results are novel and make significant progress towards a better understanding of TD convergence.

In light of the reviews, we realized that we could have done a better job in articulating the major contributions of our work. We reiterate here that our paper has made two significant advancements in terms of generalizing existing results on TD convergence:

1- We believe to be the first paper to show a contraction for TD with frozen target network and general $K$. To elaborate further, to the best of our knowledge, existing results prior to Lee and He (2019) mainly considered the case where we either never freeze the target network (corresponding to the value of $K=1$), or the somewhat unrealistic case where we can exactly solve each iteration. Lee and He (2019) showed guarantees pertaining to the more general case of finite $K>1$, but notice that, while their result is quite innovative, they leaned on the more standard optimization tools for ensuring that gradient descent with a fixed $K$ can only solve each iteration approximately. Therefore, each iteration results in some error. In their theory this error is accumulated per iteration and needs to be accounted for in the final result. Therefore, they fell short of showing 1) contraction and 2) exact convergence to the TD fixed-point, and only show that the final iterate is in the vicinity of the fixed-point defined by the amount of error accumulated over the trajectory. 

In contrast, we actually proved exact convergence to the TD fixed-point by showing that each iteration is indeed a contraction irregardless of the value of $K$. Even though Lee and He are correct in saying that using a finite $K$ results in approximately solving each iteration, we can still show that each iteration remains a contraction by looking at the net effect of the $K$ updates to the online network and the single update to the target network. We prove that the net effect of these updates is one that ensures that the iterate makes steady progress towards the unique fixed-point irregardless of $K$. To the best of our knowledge, this result is completely novel, and takes a major step in supporting the soundness of TD as well as the successor algorithms (such as DQN) that use a frozen target network.

2- We believe to be the first paper to show convergence of TD in the most natural extension of the quadratic objective. To ensure that this extension is possible, we made two additional assumptions, namely the Lipschitz continuity of the objective with respect to the target network, and the strong convexity of the objective with respect to the online network. While these assumptions hold in the linear case with quadratic loss, some of the reviewers asked us to elaborate further in terms of the validity of these assumptions for mainstream loss functions and function approximators.

To this end, we present two families of loss functions where our assumptions can hold easily. In particular, to explain the first family, recall that TD could be thought of as solving for a sequence of optimization problems as follows:

$\theta^{t+1} \leftarrow \arg\min_{w} H(\theta^{t},w).$

Now suppose we can write the function $H(\theta,w)$ as the sum of two separate functions $H(\theta,w) = G(\theta, w ) + L(w)$, where the function $L(w)$ is strongly convex with respect to $w$. This setting is akin to using ridge regularization which is quite common in deep learning (for example AdamW). This allows us to now work with functions $G$ that are only convex (in fact they technically can be weakly convex) with respect to $w$. We provide two examples:

1- Suppose we would like to stick with the linear function approximation architecture. Then, the function $G$ could be constructed using any convex loss where $\nabla_w G(\theta,w)$ is Lipschitz-continuous with respect to $\theta$. Examples that satisfy this include the Logistic loss or the Huber loss.

2- Suppose we want to use the more powerful convex neural networks. We need the loss function to be convex and  monotonically increasing so that the resultant function $G$ is still convex. This is due to the classical result on the composition of convex operators. One example is the quadratic loss where we restrict the output of the function approximator to positive values. Such neural nets are also Lipschitz continuous given proper activation functions such as ReLU.

Beyond this family, since the submission we have identified a second family, namely the control setting (beyond prediction) where a greedification operator is needed for bootstrapping. For example, with the quadratic loss we could have:

$H(\theta,w)=\frac{1}{2}\sum_sd(s)\sum_a\pi(a|s)(E_{s'}[r+ \gamma\max_{a'}q(s',a',\theta)]-q(s,a,w))^2.$

We again need the two assumptions, namely strong-convexity with respect to $w$ and Lipschitzness of $\nabla_w H(\theta,w)$ with respect to $\theta$ to hold. Actually, Lee and He (2020) already showed the strong convexity of the objective with respect to $w$, but we need to still show the Lipschitz property of $\nabla_w H(\theta,w)$ with respect to $\theta$. Note that Lee and He (2020) showed the Lipschitz property only with respect to $w$ and not with respect to $\theta$. We are now able to show this result. Please see the proof in the pdf attached to this rebuttal. Our proof also supports other greedification operators, such as softmax, so long as these operators are non-expansive. We will add this result to the paper. So, together, this would be another example of the kind of loss functions of the form $H(\theta,w)$ that satisfy our assumptions.

Lee and He ``Target-based Q-learning", 2020.

Meta-review: This paper studies the convergence of TD algorithms by viewing TD as iterative optimization procedures. The authors identified "optimization force" and "target force" as determining factors for convergence or divergence, and the conclusion is that TD converges when the optimization forces overcomes the target force.

The viewpoint of optimization and target forces seems novel to most reviewers and the AC, and it makes good progresses toward better understanding convergence of TD methods. Reviewers found that the paper is well-written and easy to follow.

There were several questions regarding comparing to existing results and weakening the strong convexity assumptions from the reviews that the authors provided responses during rebuttal. Please include these clarifications and discussions in revisions to strengthen the current exposition.
Decision: Accept (poster)