Gradient descent temporal difference-difference learning
Authors: Rong Zhu
James Murray
Venue:  (2021)
Keywords: temporal difference learning
gradient-descent based temporal difference
Off-policy
regularization

Abstract: Off-policy algorithms, in which a behavior policy differs from the target policy and is used to gain experience for learning, have proven to be of great practical value in reinforcement learning. However, even for simple convex problems such as linear value function approximation, these algorithms are not guaranteed to be stable. To address this, alternative algorithms that are provably convergent in such cases have been introduced, the most well known being gradient descent temporal difference (GTD) learning. This algorithm and others like it, however, tend to converge much more slowly than conventional temporal difference learning.
In this paper we propose gradient descent temporal difference-difference (Gradient-DD) learning in order to accelerate GTD learning by introducing second-order differences in successive parameter updates.
We investigate this algorithm in the framework of linear value function approximation and analytically showing its improvement over GTD learning. Studying the model empirically on the random walk and Boyan-chain prediction tasks, we find substantial improvement over GTD learning and, in several cases, better performance even than conventional TD learning.


Under review as a conference paper at ICLR 2021
GRADIENT DESCENT TEMPORAL CEFFERENCE-DIFFEENNE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Off-policy algorithms, in which behavior policy differs from the target policy and is used to gain experience for learning, have proven to be of great practical value in reinforcement learning. However, even for simple convex problems such as linear value function approximation, these algorithms are not guaranteed to be stable. To address this, alternative algorithms that are provably convergent in such cases have been introduced, the most well known being gradient descent tempo- ral difference (GTD) learning. This al algorithm and others like it, however, tend to converge much more slowly than conventional temporal difference learning. this paper propose gradient descent temporal difference-difereen DD) learning in order to improve GTD learning by introducing second-order dif- ferences in successive parameter updates. We investigate this algorithm in the framework of linear value function approximation, analytically showing its im- provement over GTD learning. Studying the model empirically on the random walk and Boyan-chain prediction tasks, we find substantial improvement over GTD learning and, in several cases, better performance even than conventional TD learning.
(Gradient-
INTRODUCTION
Off-policy algorithms for value function learning enable an agent to use behavior policy that dif- fers from the target policy in order to gain experience for learning. However, because off off-policy methods learn a value function for target policy given data due to a different behavior policy, they often exhibit greater variance in parameter updates. When applied to problems involving function approximation, off-policy methods are slower to converge than on-policy methods and may even diverge (Baird, 1995; Sutton & Barto, 2018).
Two general approaches have been investigated to address the challenge of developing stable and effective off-policy temporal-diiference algorithms. One approach is to use importance sampling methods to warp the update distribution back to the on-policy distribution (Precup al.. 2000; Mahmood et al., 2014). This approach is useful for decreasing the variance of parameter updates, but does not address stability issues. The second main approach addressing the challenge of off-po off-policy learning is to develop true gradient descent-based methods that are guaranteed to be stable regardless of the update distribution. Sutton et al. (2009a;b) proposed the first off-policy gradient- descent-basee temporal difference (GTD and GTD2, respectively) algorithms. These algorithms are guaranteed be stable, with computational complexity scaling linearly with the size of the function approximator. Empirically, however, their convergence is much slower than conventional temporal difference (TD) learning, limiting their practical utility (Ghiassian et al., 2020; White & White, 2016). Building on this work, extensions to the GTD family of algorithms (see Ghiassian et al. (2018) for review) have allowed for incorporating eligibility traces (Maei & Sutton, 2010; Geist & Scherrer, 2014), non-linear function approximation such with neural network (Maci, 201 I), and reformulation of the optimization as saddle point problem (Liu et al., 2015; Du et al., 2017). However, due to their slow convergence, none of these stable off- offlppoliy methods are commonly used in practice.
In this work, we introduce new gradient descent algorithm for temporal difference learning with linear value function approximation. This algorithm, which we call gradient descent temporal difference-differen (Gradient-DDD learning, acceleration technique that employs second-

---

Under review as a conference paper at ICLR 2021
order differences in successive parameter updates. The basic idea of Gradient-DD is to modify the error objective function by additionally considering the prediction error obtained in last time step, then to derive a gradient-descent algorithm based this modified objective function. In ad- dition to exploiting the Bellman equation to get the solution, this modified error objective function avoids drastic changes in the value function estimate by encouraging local search around the current estimate. Algorithmically, the Gradient-DD approach only adds an additional term to the update rule of the GTD2 method, and the extra computational cost is negligible. We show mathematically that applying this method significantly improves the convergence rate relative to the GTD2 method for linear function approximation. This result is supported by numerical experiments, which also show that Gradient-DD obtains better convergence in many cases than conventional TD learning.
1.1 RELATED WORK
In related approaches to ours, some previous studies have attempted to improve Gradient-TD al- gorithms by adding regularization terms to the objective function. Liu et al. (2012) have used I regularization on weights to learn sparse representations of value functions, and Ghiassian et al. (2020) has used l2 regularization on weights. Unlike these references, our approach modifies the error objective function by regularizing the evaluation error obtained in the most recent time step. With this modification, our method provides a learning rule that contains second-order differences in successive parameter updates.
Our approach is similar to trust region policy optimization (Peters & Schaal, 2008; Schulman et al., 2015) relative entropy policy search (Peters al., 2010), which penalize large changes being learned in policy learning. In these methods, constrained optimization is used to update the policy by considering the constraint on some measure between the new policy and the old policy. Here, however, our aim here is to look for the optimal value function, and the regularization term uses the previous value function estimate to avoid drastic changes in the updating process.
GRADIENT DESCENT METHOD FOR OFF-POLICY TEMPORAL DIFFERENCE LEARNING
2.1 PROBLEM DEFINITION AND BACKGROUND
In this section, we formalize the problem of learning the value function for a given policy under the Markov Decision Process (MDP) framework. In this framework, the agent interacts with the environment over a sequence of discrete time steps. t = 2, At each time step the agent observes partial summary of the state S, E S and selects an action a A. In response, the environment emits a reward rt E IR and transitions the agent to its next state 8t41 E S. The state and action sets are finite. State transitions are stochastic and dependent preceding state and action. Rewards are stochastic and dependent on the preceding state and action, as well on the next state. The process generating the agent's actions is termed the behavior policy. In off- off-policy learning, this behavior policy is in general different from the target policy π S + A. The objective is learn an approximation the state-value function under the target policy in particular environment:
the immediately
V(s) = E
relsi
(1)
where 7 E [0, 1) the discount rate.
In problems for which the state space is large, it is practical to approximate the value function. In this paper consider linear function approximation, where states mapped to feature vectors with fewer components than the number of states. Specifically, for each state E S there is corresponding feature vector x(s) RP, with p < [S], such that the approximate value function is given by
(s) w T x(s).
The goal is then to learn the parameters such that V (s) V(s).
2

---

Under review as a conference paper at ICLR 2021
2.2 GRADIENT TEMPORAL DIFFERENCE LEARNING
A major breakthrough for the study of the convergence properties of MDP systems came with the introduction of the GTD and GTD2 learning algorithms (Sutton al., 2009a:b). We begin by briefly recapiulating the GTD algorithms, which we will then extend in the following sections. To begin, we introduce the Bellman operator B such that the true value function V E R satisfies the Bell- man equation:
V - R -= BV,
where the reward vector with components 8 = s), and P is matrix of state transition probabilities. In temporal difference methods, an appropriate objective function should minimize the difference between the approximate value function and the solution to the Bellman equation.
Having defined the Bellman operator, we next introduce the projection operator II, which takes any value function V and projects it to the nearest value function within the space of approximate value functions of the form (2). Letting X be the matrix whose rows are x(s), the approximate value function can expressed as V w Xw. We will also assume that there exists a limiting probability distribution such that d, lim p(,,, =) (or, in the episodic case, d, is the proportion of time steps spent state 8). The projection operator is then given by
I= X ''
where the matrix is diagonal, with diagonal elements da.
The natural measure of how closely the approximation Vw satisfies the Bellman equation is the mean-squared Bellman error:
MSBE(w) I|V BV w I
(3)
where the norm weighted by D, such that | VVDV. However, because the Bellman operator follows the underlying state dynamics of the Markov chain, irrespective of the structure of the linear function approximator, BVw will typically not be representable as Vw for any w. An alternative objective function, therefore, is the mean squared projected Bellman error (MSPBE), which we define as
J (ww = IV - IIVV
(4)
Following (Sutton al., 2009b), our objective is minimize this error measure. As usual in stochas- tic gradient descent, the weights at each time step are then updated by Aw -a V w [w), where 0, and
2 ww)) (-)===((?>x+++ x, x [[((x,,, "1 '((8xxn)
2 - --E[(( - X |
(5)
For notational simplicity, have denoted the feature vector associated with sn x, x(s)).
We have also introduced the temporal difference error 5n = ra + (7x,+1 - x,) w,, as well as 77 a linear predictor approximate [E(x,,,,, - -( Because the factors in Eqn. (5) can be directly sampled, the resulting updates in each step are
5n =Yn + (7Xx+1 1 - xxn) Wn
7x+1 nn + (a - x nn )xx
Wa+1 =W, an (7x,+1 - xx 7m))
(6)
These updates define the GTD2 learning algorithm, which we will build upon in the following section.
3 GRADIENT DESCENT TEMPORAL DIFFERENCE-DIFFERREE LEARNING
In order to improve the GTD2 algorithm described above, in this section we modify the objective function via additionally considering the approximation error V. V w.,, given the previous time step 1. Specifically, we modify Eqn. (4) as follows:
JanD(w/w.-11) (ww + </|V V Ww.-1 11.
3

---

Under review as a conference paper at ICLR 2021
Figure 1: Schematic diagram of Gradient-DD learning with w E R2 Rather than updating directly along the gradient of the MSPBE (arrow), the update rule selects wn. that min- imizes the MSPBE while satisfying the con- straint |V V W.. 1 S (shaded ellipse).
Wn
W
where x 2 0 is a parameter of the regularization.
Minimizing Eqn. (7) is equivalent to the following optimization
arg min (w) s.t. V VV,.. 1l S
(8)
where l is a parameter which becomes large when is small, that the MSPBE objective is recovered as μ + co, equivalent to k + O in Eqn. (7). We show in the Appendix that for any >> 0, there exist
such that the solution of Eqn. (7) and that of Eqn. (8) are the same.
Eqns. (7) and (8) represent tradeoff between minimizing the MSPBE eπror and preventing the estimated value function from changing too drastically. Rather than simply minimizing the optimal prediction from the projected Bellman equation, the agent makes use of the most recent update to look for the solution. Figure/ gives schematic view of the effect of the regularization. Rather than directly following the direction of the MSPBE gradient, the update chooses the MSPBE while following the constraint that the estimated value function should not change too greatly. In effect, the regularization term encourages searching around the estimate at previous time step, especially when the state space is large.
that minimizes
With these considerations in mind, the negative gradient of JGDD w/wn-11 is
V BwJJDD(w/w....
2
E[(7xn+1 X. xx, [E x, DI (.,x)) xE(((x, Wn XxI wn-1)xx) E[(7xx+1 - Xn )x, nm <x[(x,, Wa xJ_ Wn- .)x].
Because the terms in Eqn. (9) can be directly sampled, the stochastic gradient descent updates are given by
6n =r, + (78x+1 Xn) wn
7n+1 -n + (n x, nn )Xn
W Wn+1 =W, (x,, Wn x,, wn- (7x,111111111 - (x, n.
(10)
These update equations define the Gradient-DD method, in which the GTD2 update equations (6) are generalized by including second-order update term in the third update equation, where this term originates from the squared bias term in the objective (7). In the following sections, we shall analytically and numerically investigate the convergence and performance of Gradient-De learning.
4 IMPROVED CONVERGENCE RATE
In this section we analyze the convergence rate of Gradient-DD learning. Note that the second-order update in the last line in Eqn. (10) can be rewritten system of first-order difference equations:
(I + X,, (Wx+1 w.) X,,,,, (12+1 u,) as (xXXn=111 - (x, nn);
u,41 =W,+ W..
(11)
4

---

Under review as a conference paper at ICLR 2021
Let 3n [a < > 0. We consider constant step sizes in the updates, i.., Kn and On a. De-
Vxx,,,
X,, (X,, +X++1)
note H =
X, and G2 -xx, *X,+1)x;
We rewrite
the update rules of two iterations in Eqn. (11) as single iteration in combined parameter vector with 2n components, P.. / w. and new reward-related vector with 2n components, ga+1 (r,x, 0 as follows:
Pa+1 P,, - (H - Pn-1) + (<a(G..,, - gn+1),
(12)
Denoting #n+1 = a (pn+1 - Pn)) Eqn. (12) rewritten as
Pn+1 Pn
I + kHn
-kaH,
[[[
-v[(Gn,, -8--1)
gn-1)
2 nn+1 - 4nn
=0
I
-aI
VvG VÇa Gn
-KH,, -a -a kH
][
Pn
V5g++1
=0
2
+
V
Bn+1
(13)
I kH, I
KkaHn
I a -a- kH,))
RHH
where the second step from
De-
aal
HHH, note Jn = -V -a xH,,) Eqn. (13) tells us that J, is the update matrix of
the Gradient-DD DD algorithm. (Note that G. is the update matrix of the GTD2 algorithm.) Therefore,
assuming the stochastic approximation in Eqn. (13) goes to the solution of an associated ordinary differential equation (ODE) under some regularity conditions (a convergence property is provided in the appendix by following Borkar & Meyn (2000)), we can analyze the improved convergence rate of Gradient-Do DDD learning by comparing the eigenvalues of the matrices E(G,, denoted by G, and
VCG
-xH
E(J,) denoted by J (Atkinson et al., 2008). Obviously. J -V[a-a -a - kH)
where H = B(H,). To simplify, we consider the case that the matrix B(x,x,)) =
Let AG be real eigenvalue of the matrix v(G. (Note that is defined here with opposite sign relative to G in Maei (2011).) From Maei (2011), the eigenvalues of the matrix -G are strictly
negative. In other words, AG > Let À be an eigenvalue of the matrix J. i.c a solution to the equation
[XI J| =(A+ Aa)(A+a ka-aa-a -a= X² Ja 11--aa-1111 (1+*)) + AclA +a - =0 (14)
The smaller eigenvalues Am of the pair solutions to Eqn. (14) are
Aoo
where details of the above derivations are given in the appendix. This explains the enhanced speed of convergence in Gradient-DD learning. We shall illustrate this enhanced speed of convergence in numerical experiments in Section 5.
Additionally, also show convergence property of Gradient-DD under constant step sizes by applying the ordinary differential equation method of stochastic approximation (Borkar & Meyn, 2000). Let the TD fixed point be w", such that Vw- IIBV wt. Under some conditions, prove that, for any e > 0, there exists by < oo such that lim P[[[w, - w*ll > <) < bi
Details provided in the appendix. For tapered step sizes, which would be necessary to obtain an even stronger convergence proof, the analysis framework in Borkar & Meyn (2000) does not apply into the Gradient-DD algorithm. Although theoretical investigation of the convergence under tapered step sizes is question to be studied, we find empirically in numerical experiments that the algorithm does in fact converge with tapered step sizes and even obtains much better performance in this case than with fixed step sizes.
5 EMPIRICAL STUDY
In this section, we assess the practical utility of the Gradient-DD method in numerical experiments. To validate performance of Gradient-DDD learning, we compare Gradient-DD learning with GTD2
5

---

Under review as a conference paper at ICLR 2021
learning, TDC learning (TD with gradient correction (Sutton et al., 2009b)), TD learning, and Em- phatic TD learning (Sutton Mahmood, 2016) in tabular representation using a random-walk task and in linear representation using the Boyan-chain task. For each method and each task, per- formed a scan over the step sizes on and the parameter & so that the comprehensive performance of the different algorithms be compared. We considered two choices of step size sequence (an):
(Case 1) On is constant, i.e., On cx.
(Case 2) The learning rate On is tapered according to the schedule On = oo + 1)/(10 + n).
We set the cog where 1,2,4, 4. Additionally, also allow dependent and consider Case 3: On is tapered as in Case 2, but Kn, ca,. In order to simplify presentation, the results of Case reported in the Appendix. To begin, we set 3,, On, then later allow for 3n (a,, under Ç E {1/4, 1/2, 1 / in order to investigate the effect of the two-timescale approach of the Gradient-based TD algorithms on Gradient-DD. all cases, we set =1
5.1 RANDOM WALK TASK
As first test of Gradient-DD learning, conducted simple random walk task (Sutton & Barto, 2018) with tabular representation of the value function. The random walk task has a linear arrange- ment of states plus absorbing terminal state each end. Thus there are m-+ sequential states, So. "I, -.. Sm-1, where m = 20, 50, or 100. Every walk begins the center state. At each step, the walk moves to neighboring state, either to the right or to the left with equal probability. If either edge state (So or Sm+1) is entered, the walk terminates. A walk's outcome is defined to be 0 at So and r 1 at Sm+1- Our aim is learn the value of each state V(s), where the true values are (1, ... mm)
1). In all cases the approximate value function is initialized to the intermediate value (s(+) = 0.5. In order to investigate
effect of the initialization Vo(s), we also initialize Vs(s) 0, and report the results in Figure 7 of the Appendix, where its performance is very similar as the initialization Vo(s) 0.5.
We first compare the methods by plotting the empirical RMS error from the final episode during training as function of step size a in Figure 2, where 5000 episodes are used. From the figure, we make several observations. (1) Emphatic TD works well but is sensitive to It prefers very small a even in the tapering case, and this preference becomes strong as the state space becomes large in size. (2) Tradient-DD works well and is robust a, is conventional TD learning. (3) TDC performs similarly to the GTD2 method, but requires slightly larger a than GTD2. (4) Gradient-DD performs similarly conventional TD learning and better than the GTD2 method. This advantage is consistent in different settings. (5) The range of a leading to effective learning for Gradient-DD DD
roughly similar that for GTD2.
Empirical RMS eiror
Empirical RMS emrrr
06
Empirical RMS error
Empirical RMS emror
86
04
04
02
TD:
59
1e-05
1e-03
1e-01
1e-05
1e-03
1e-01
1e-05
1e-03
1e-03
1e-05
1e-03
16-01
0
CX
(a) Constant step size.
Tapering step size.
Figure 2: Performance in the random walk task depends on step size. (a), Constant step size Os, Ogg. (b), Tapering step size an = a00 + 1)/(10 + n). In (a) and (b), state space size (left) or 20 (right). GDD(c) denotes the Gradient-DD with The curves averaged over 20 runs, with eπror bars denoting standard deviations across runs.
Next we look closely at the performance during training. which we show Figure 3, where each method and parameter setting to facilitate comparison of these methods, we set ag = 0.1 for 10 spaces, an = 0.2 for 20 spaces, and og 0.5 for 50 spaces. Because Emphatic TD requires the step size be especially small
for 5000 episodes. From the observations in Figure 2, in order

---

Under review as a conference paper at ICLR 2021
shown in Figure 2, the plotted values of on for Emphatie TD tuned relative to the values used the algorithm defined in Sutton & Mahmood (2016), where the step sizes of Emphatic TD d are chosen from (0.5%, 0.1%, 0.05%, 0.01%) } by the smallest area under the performance curve. Additionally we also tune ogp for TDC because TDC requires On, larger a little than GTD2 as shown in Figure 2. The step sizes for TDC are set as Ot by the smallest area under the performance curve.
(ETD)
(TDC) a0n, where is chosen from (1, 1,5,,,2) 2,3)
From the results shown in Figure 3a, we draw several observations. (1) For all conditions tested, Gradient-DD converges much more rapidly than GTD2 and TDC. The results indicate that Gradient- DD even converges faster than TD learning in some cases, though it is not fast in the beginning episodes. (2) The advantage of Gradient-DD learning over other methods grows as the state space increases in size. (3) Gradient-DD learning is robust to the choice of c, which controls the size of the second-order update, as long as с is not too large. (Empirically c = 2 is a good choice.) (4) Gradient-DD has consistent and good performance under both the constant step size setting and under the tapered step size setting. In summary, compared with GTD2 learning and other methods, Gradient-DD learning in this task leads to improved learning with good convergence.
TD
Empirical RMS eror
ETD
Empinical RRMiiccalMMMSS RMS error
Empirical RMS crror
0.4
GTD2
0.4
RMS
TDC
GDD(1)
GDD(2)
0.2
GDD(4)
0.2
1000
3000
5000
1000
3000
5000
0
1000
3000
5000
episode
episode
episode
(a) Constant step size On. = ov.
Empinical RLMS enror
Empirical HMSS error
Empirical RMS errar
0.4
0.4
0.4
0.2
0.0
0
1000
3000
5000
0
1000
3000
5000
0
1000
3000
5000
episode
episode
episode
(b) Tapering step size an ou o0(10 (10 + 1)/(102 + n2).
Figure 3: Performance of Gradient-DD in the random walk task. From left to right in each subfigure: the size of state space is 10 (og = 0.1), 20 (og = 0.2), 50 (og = 0.5). The curves are averaged over 20 runs, with error bars denoting standard deviations across runs.
In addition to investigating the effects of the learning rate, size of the state space, and magnitude of the regularization parameter, we also investigated the effect of using distinct values for the two learning rates, On and 3,. To do this, we set B, = Ça,, with < (1/4, 1/2, 1,2] and report results Figure 8 of the appendix. The results show that comparably good performance of Gradient- DD is obtained under these various 3, settings.
5.2 BOYAN-CHAIN TASK
We next investigate Gradient-DDi learning on the Boyan-chain problem, which is a standard task for testing linear falue-function approximation (Boyan, 2002). In this task allow for 4p - 3 states, with p = 20, each of which is represented by p-dimensional feature vector. The p-dimensional representation for every fourth state from the start is [1,0,.-. ..................... 0] for state 81, [0, 1, ... .0] for 85.
7

---

forward steps Under review as a conference paper at ICLR 2021
and [0, ..... 0 for the terminal state $4p-3. The representations for the remaining states obtained by linearly interpolating between these. The optimal coefficients of the feature vector are (-4(p- 1), 4p .). .0/5.. Simulations with p 50 and 100 give similar results to those from the random walk task, and hence are not shown here. In each state, except for the last one step
before the end, there two possible actions: move forward with equal probability 0.5. Both actions lead to reward -0.3. The last state before the end just has one action of moving forward the terminal with reward -0.2. As in the random-walk task, ag used in Emphatic TD is tuned from {0.5%, 0.2%, 0.1%, 0.05%).
We report the results in Figure 4, which leads to conclusions similar those already drawn from Figure 3. (1) Gradient-DD has much faster convergence than GTD2 and TDC, and generally con- verges to better values despite being somewhat slower than TD learning at the beginning episodes. (2) Gradient-DD is competitive with Emphatic TD. The improvement over other methods grows as the state space becomes larger. (3) As i: increases, the performance of Gradient-DDD improves. Ad- ditionally, the performance of Gradient-DD is robust to changes in long is not very large. Empirically a good choice is to set K = a or 2a. (4) Comparing the performance with constant step size versus that with tapered step size, the Gradient-DD method performs better with tapered step size than does with constant step size.
Empirical RMS error
0.6 0.8 1.0
Empirical RMS error
00 0.2 0.4 0.6 0.8 1.0
Empirical RMS emrr
TD
ETD
0.6 0.8
GTD2
TDC
GDD(I)
0.4
GDDI2)
0.4
GDD14)
0.0 0.2
20000
60000
5000
15000
5000
15000
episode
episode
episode
(a) Constant step size Oa
Olo, where on 0.05, 0.1, 0.2 from left to right.
Empirical RMS error
1.0
Empirical RMS error
1.0
Empirical RMS erro
1.0
0.8
0.8
08
0.6
0.6
06
0.
0.0 0.2 0.4
04
0.2
00 022
0.0
0
20000 60000
5000
15000
5000
15000
episode
episode
episode
(b) Tapering step size a. a00 1)/(10 n). where ao 0.3, 0.5, from to right.
Figure 4: Performance of Gradient-DD in the Boyan Chain task with 20 features. Note that the case Gradient-DD(4)) i.c. = not shown when does not converge.
5.3 BAIRD'S COUNTEREXAMPLE
We also verify the performance of Gradient-DDD on Baird's off-policy counterexample (Baird, 1995), for which TD learning famously diverges. We consider three cases: 7-state, 100-state and 500-state. We set a = 0.02 (but for GDD2 and ą 0.8 for GDD3. For the initial parameter values (I, ... 1, 10, 1) We measure the performance by the empirical RMS errors function of sweep, and report the results in Figure
10-6 for ETD), 3 and = 0.99. We set 0.2 for GDD1, к = 0.4
The figure demonstrates that Gradient-DD works as well on this well-known counterexample GTD2 does, and works better than GTD2 for the 100-state case. We also observe that the performance improvement Gradient- DD increases as the state spaces increases. We also note that, because the linear approximation leaves residual error in the value estimation due the projection
8

---

Under review as a conference paper at ICLR 2021
Empirical RMS error
20
Empirical RMS error
20
Empirical RMS error
20
TD
ETD
19
GTD2
12
-7
TDC
GDD
GDD
GDD(40)
6
5
0
100
300
500
100
300
500
100
300
500
weep
S weep
weep
Figure 5: Bairds off-policy counterexample. From left to right: 7-state, 100-state, and 500-state. TDC is not reported here due its similarity to GTD2. We set a = 0.02 (but 10-5 for ETD), a, and 0.02c. GDD(c) denotes the Gradient-DD with c.
error, the RMS errors in this task do not go to zero. Interestingly, Gradient-DD reduces this residual error as the size of the state space increases.
CONCLUSION AND DISCUSSION
In this work, have proposed Gradient-DD learning, gradient descent-based TD learning algorithm. The algorithm is based on a modification of the projected Bellman error objective func- tion for value function approximation by introducing second-order difference term. The algorithm significantly improves upon existing methods for gradient-based TD learning, obtaining better con- vergence performance than conventional linear TD learning.
Since GTD learning was originally proposed, the Gradient-TD family of algorithms has been ex- tended for incorporating eligibility traces and learning optimal policies (Maei & Sutton, 2010; Geist & Scherrer, 2014), as well as for application to neural networks (Maei, 201 1). Additionally, many variants of the vanilla Gradient-TD TD methods have been proposed, including HTD (Hackman, 2012) and Proximal Gradient- TD (Liu et al., 2016). Because Gradient-Do DD just modifies the objective er- ror of GTD2 by considering an additional squared-biaa bias term, it may be extended and combined with these other methods, potentially broadening its utility for more complicated tasks.
In this work we have focused on value function prediction in the two simple cases of tabular rep- resentations and linear approximation. An especially interesting direction for future study will be the application of Gradient-DD learning to tasks requiring more complex representations, including neural network implementations. Such approaches are large, and indeed we have found in our results that Gradient-DD DD seems to confer the greatest advantage other methods in such cases. Intuitively, we expect that this is because the differ- ence between the optimal update direction and that chosen by gradient descent becomes greater in higher-dimensional spaces (cf. Fig. 1). This performance benefit in large state spaces suggests that Gradient-DD may be of practical use for these more challenging cases.
especially useful in cases where state spaces
REFERENCES
K. Atkinson, W. Han, and D. Stewart. Numerical Solution of Ordinary Differential Equations. JOHN WILEY & SONS, 2008
L. C. Baird, Residual algorithms: Reinforcement learning with function approximation. In Pro- ceedings of the 12 th International Conference on Machine Learning, pp. 30-37, 1995.
V.S. Borkar and S.P. Meyn. The ODE method for convergence stochastic approximation and reinforcement learning. SIAM Journal Control and Optimization, 38(2)4447466,, 2000.
Justin A. Boyan. Technical update: least-squares temporal difference learning. Machine Learning, 49:233-246, 2002.
S. Du, J. Chen. L. Li, L. Xiao, and D. Zhou. Stochastic variance reduction methods for policy evaluation. In Proceedings the 34 th International Conference Machine Learning, 2017.

---

Under review as a conference paper at ICLR 2021
M. Geist and B. Scherrer. Off-policy learning with eligibility traces: A survey. Journal of Machine Learning Research, 15:289-3323 13889933,,00 2014.
S. Ghiassian, A. Patterson, M. White, R.S. Sutton, and A. White. Online off off-policy prediction. arXiv:1811.02597 2018.
S. Ghiassian, A. Patterson, S. Garg, D. Gupta, A. White, and M. White. Gradient temporal- difference learning with regularized corrections. In International Conference Machine Learn- ing, 2020.
L. Hackman. Faster gradient-TD) algorithms. Master's thesis, University of Alberta, Edmonton, 2012.
B. Liu, S. Mahadevan, and J. Liu. Regularized off-policy TD-learning In Advances in Neural Information Processing Systems, 2012.
B. Liu, J. Liu, M. Ghavamzadeh, S. Mahadevan, and M. Petrik. Finite-sample analysis of proximal gradient TD algorithms. In Proceedings the 31st International Conference on Uncertainty in Artificial Intelligence, pp. 504-513, 2015.
B. Liu, J. Liu, M. Ghavamzadeh, S. Mahadevan, and M. Petrik. Proximal gradient temporal differ- ence learning algorithms. In The 25th International Conference on Arti cial Intelligence (IJCAI- 16)., 2016.
H.R. Maei. Gradient temporal-differecce learning algorithms. PhDD thesis, University of Alberta, Edmonton, 2011.
H.R. Maei and R.S. Sutton. GQ(A): A general gradient algorithm for temporal-differene predic- tion learning with eligibility traces. In Proceedings of the 3rd Conference on Artificial General Intelligence, pp. 91-96, 2010.
A. R. Mahmood, H. van Hasselt, and R. S. Sutton. Weighted importance sampling for off off-policy learning with linear function approximation. In Advances in Neural Information Processing Sys- tems 27, 2014.
Peters, K. Mülling, and Y. Altin. Relative entropy policy search. An Conference on Artificial Intelligence, 2010.
Jan Peters and Stefan Schaal. Natural actor-critie. Neurocomputiing (1(7):1180-118) 2008
D. Precup, R. S. Sutton, and S. Singh. Eligibility traces for off off-policy policy evaluation. In Proceed- ings of the 17 th International Conference on Machine Learning, 2000.
John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region policy optimization. In Proceedings of the 32nd International Conference Machine Learning, 2015.
R. S. Sutton, Cs. Szepesvári, and H. R. Maei. A convergent O(n) algorithm for off-policy tempo- ral difference learning with linear function approximation. In Advances in Neural Information Processing Systems 21, 2009a.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition edition, 2018
R.S. Sutton and M. Mahmood, A.R. amd White. An emphatic approach to the problem of off off-policy temporal difference learning. Journal of Machine Learning Research, 17(73): 2016.
R.S. Sutton, H.R. Maei, D. Precup, S. Bhatnagar, D. Silver, Cs. Szepesvári, and E. Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the 26th International Conference on Machine Learning, 2009b.
A. White and M. White. Investigating practical linear temporal difference learning. In International Conference on Autonomous Agents and Ageni Systems, 2016.
10

---

Under review as a conference paper at ICLR 2021
APPENDIX
6.1 ON THE EQUIVALENCE OF HQNS. (7) (8)
The Karush-Kuu Kuhn- Kuhn-Tucker conditions of Eqn. (8) are the following system of equations
2w
d J(w
+
dw
d
( w
V Vw,-ill Il 11) = 0;
x(|] V
V w.-1
I μ4) = 0;
w
IV w
1l S μc:
K #26 O.
These equations are equivalent to
J(w)
d IV w dw
V -w lB = 0 and K. > 0,
dw
if [ V w. l = μ
dw J(w) = 0 and x = 0, if V w Vw--1 lB < μ.
Thus, for any O, there exists such that
Tw
d [(w
+ M dw
d
V
V Wn 11 0.
6.2 EIGENVALUES OF J
Let be an eigenvalue of the matrix J. We have that
+ VCG
xH
|AI - J
VÇa 'G
a
A VCG
<H
-a- I
AI aI+a-1
A VGG
kH a I ka X V(G) "H
0
HH
+ (AI + a "1)
ka- A
From the assumption x and the definition H, some eigenvalues the matrix J, X
are solutions to
XI J =(A + AG) + a 0:
and other eigenvalues of the matrix J, x, are solutions to
|AI J| =(A Ac)
ka a
=> + (1 n) + >aa> - \c =0
Note AG > 0. the pair solutions to the equation above are
A =
la - + Ac]
2 (1-((1
+ Ag - 4a AG
1a (1 + >c|
0 (1-1( AaI + 4a AGK.
2
Thus, the smaller eigenvalues of the pairs
Am
2 la (1
[1
Aal
a 1(1 + k) Ao) 4a Aox
1 aa
- k) Aa] v la 1(1 R) da13
2
where the inequality is from A 0. When -1 + k) - -c 0, then
Am 7 (1+ k) + >el 1
(a - + x) Ac)
2
= - a (1+
Ao,
When a - Ao < 0, then
Am 1/a -1 k)) k)+ da|+ la -1 x) Xa)
Ao,
11

---

Under review as a conference paper at ICLR 2021
CONVERGENCE WITH CONSTANT STEP SIZES
At last we apply the ODE method of stochastic approximation to obtain the convergence perfor- mance.
Theorem Consider the update rules (10) with constant step size sequences K. and B satisfying 5 Ça. Ç O, E (0,1) and 5 Let the TD fixed point be w', such that V w IIBV w.. Suppose that (AI) (Xn; nn.. x1+) is an i.d. sequence with uniformly bounded second Xn are non-singular, Then for any > 0, there
moments, and (A2) E[(x,, - -xx++xx+xxx, and ([Xx,,, exists bj 00 such that
limsup P(| - w > -) bja.
Proof From the constant step sizes in the conditions, denote fin and On Thus, Eqn. (12) equals
(I + (Hu) Pn) kH,, -HH, (Pnt1 2p + P
= - --Vaa(GnP, gn+1).
(A.1)
Denoting 2n+1 = a (Pn+1 - Pn): Eqn. (A.1) is rewritten as
Pat1 -
Ønl1= n
I kHn
HK -al
-V[(G - -g++1)
I
///2
VCGn
-xHH
][
Pr
VSa-G
(I xHH))
2b
V[gn+1 Vςa gn+1
+
(A.2)
where the second step is from
I KH, KKaH,
I
-HH <H
aa
a aa'
-a -
Denoting G = ). g B(g.) and H = E(H,). then the TD fixed point of Eqn. (A.1) is given by
-Gp + g
(A.3)
We apply the ordinary differential equation approach of the stochastic approximation in Theorem (Theorem 2.3 of (Borkar & Meyn, 2000)) into Eqn. (A.2). Note that (Sutton et al., 2009a) and (Sutton et al., 2009b) also applied Theorem 2.3 of (Borkar & Meyn, 2000) using the gradient- descent method for temporal-diiference learning to obtain their convergence results. For simplifying notation, denote
G...
HHH, -a -a -I kH
J,
Va G.
/C
-xH
J
-a -a xH)
Vgg+1
vīg V(a -g-
yn.
Pn 2
hn =
and h
Eqn. (A.2) is rewritten as
Bu+1
yut1 = =v, + aaf((y))) + h Mn+1), where f(yn)= Jy, and M,+1 = (J,, J)y, h, h.
(A.4)
Now we verify the conditions (c1-c4) of Lemma Firstly. Condition (c1) is satisfied under the assumption of constant step sizes. Secondly, f(y) is Lipschitz and (y) Gy. Following Sutton et al. (2009a), the Assumption A2 implies the real parts of all the eigenvalues of G are positive. Therefore, Condition (c2) satisfied.
12

---

Under review as a conference paper at ICLR 2021
Because E(M,+1
(F.,) and M Fr) I co(1+|lymn11 where F,, M0,,,,,,i n),
a martingale difference sequence, we have that
MM 112 s 2[[],, |ly, ||h, - hll
(A.5)
From the assumption A1, Eqn. (A.5) follows that there are constants çj and en such that
J - Fl) S sgj
E ha+1 - hll²) Σ ch.
Thus, Condition (c3) is satisfied.
Finally, Condition (c4) is satisfied by noting that y" G- g is the unique globally asymptotically stable equilibrium.
Theorem I bounds the estimation error of w in probability. Note that the convergence of Gradient- DD learning provided in Theorem 1 somewhat weaker result than the statement that w,, + w with probability as + oo. The technical reason for this is the condition on step sizes. In Theorem 1, we consider the case of constant step sizes, with Ox = a and Ki = K. This restriction system of first-order difference equations, which
imposed so that Eqn. (12) can be written cannot be done rigorously when step sizes are tapered as in (Sutton et al., 2009b). As shown below, however, find empirically in numerical experiments that the algorithm does in fact converge with tapered step sizes and even obtains much better performance this case than with fixed step sizes.
AN ODE RESULT ON STOCHASTIC APPROXIMATION
We introduce an ODE result on stochastic approximation in the following lemma, then prove Theo- rem 1 by applying this result.
Lemma (Theorem 2.3 of Borkar & Meyn (2000)) Consider the stochastic approximation algo- rithm described by the d-dimensional recursion
Yn+1 Yn (y))( + Mn+1).
Suppose the following conditions hold: (cl) The sequence {orn} satisfies for some constant 0 < < < On < ō; (c2) The function f is Lipschitz, and there exists a function for such that lim fr(y)= fooly), (y), where the scaled function fr Bd - Rd is given by fr(y) = frry)/r. Furthermore, the ODE y fso(y) has the origin as a globally asymptotically stable equilibrium; (c3) The sequence F with Fr o(yi, M, S n), is martingale difference sequence. Moreover, for some Co < oo and any initial condition yo. M[[[M S co(1 -ly,all). The ODE
(ll) (c4)
y(t) = f(y(t)
has unique globally asymptotically stable equilibrium y". Then for any c > O, there exists by < 00 such that lim sup P P(lly y"1l <) b,a.
6.3 ADDITIONAL EMPIRICAL RESULTS
13

---

Under review as a conference paper at ICLR 2021
Empinical RMS error
Empirical RMS error
0,4
0.4
0.4
Empiniaal RMS
0
0.
0.2
0.0
0
1000
3000
5000
1000
3000
5000
1000
3000
5000
episode
episode
episode
Figure 6: Performance Gradient-DD in the random walk task under Case 3. Tapering step size On (10 + 1)/ n) and is allowed to be dependent on n. fin = COn. From left to right each subfigure: the size of state space is 10 (ao 0.1), 20 (co = 0.2), 50 (ag = 0.5). Results are averaged over 20 runs, with error bars denoting standard deviations across runs.
Empincaal RMS eiror
0.4
0.2
00
0
1000
3000
5000
episode
Figure 7: Performance of Gradient-DD in the random walk task when the initial values set O. The size of state space 20, with tapering step size a₂ = 0.2(103 + 1)/(103 + n). Results are averaged over 20 runs, with error bars denoting standard deviations across runs.
GTD2
TOC
Imreaceal RMS ertrr
Empercel RMS error
GDD(1)
0.2 0.4
GDD12)
G00(4)
Empiicaill
Empircall
0.7
0.0
1000
opbcde
epicdd
spiodd
epiodd
Figure 8: Performance under various 8n the random walk task with 20 states. On = ag (10 + 1)0 + n) with ogg 0.2. From left to right in each subfigure: the size of state space is 8, an/4, B. an/2 2, 3n = a., and 3n = 20, Results are averaged over 20 runs, with error bars denoting standard deviations across runs.
14

---

Under review as a conference paper at ICLR 2021
Empirical RMS error
1.0
Empirical RMS erro
1.0
Empirical RMS error
0.8 10
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.0 0.2
0.0 0.2
0.0
0
20000
60000
5000
15000
5000
15000
episode
episode
episode
Figure 9: Performance of Gradient-DD in the Boyan Chain task with 20-features under Case 3. Tapering step size a, = ag c103 +1)/(102=-))) (10*+n), where ag 0.3, 0.5, 0.8,, where ag = 0.3, 0.5, 0.8 from left to right, and k is allowed to be dependent Kr co2, Note that the case GDD(4), i.c. c 4, is not shown when it does not converge.
15


Reviews:
[{"review_id": "vT77JFVg6iw", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a variant of the GTD2 algorithm by adding an additional regularization term to the objective function, and the new algorithm is named as Gradient-DD (GDD). The regularization ensures that the value function does not change drastically between consecutive iterations. The authors show that the update rule of GDD can be written as a difference equation and aim to further show the convergence via Lyapunov based analysis. An simulation study is provided to compare the proposed GDD algorithm with TD, ETD, and GTD. \n\nThe paper is well written in general. The idea of extra regularization on the distance between two value functions sounds reasonable to me since it resembles the constraint in trust region optimization for policy gradient methods. However, the claimed improved convergence over GTD is not rigorously proved and thus not convincing. \n\nIn Section 4, the convergence analysis is not derived in a rigorous way. It would help the readers to understand the improved convergence if the authors could complete the analysis and show the convergence rate. \n\nWhy can the eigenvalues of matrix J_n be written as the block matrix before eq (14)? It seems to me that G and H are diagonal matrices with the diagonal elements being the eigenvalues of G_n and H_n. Ideally the eigenvalues of J_n, which is denoted as J in this paper, should also be a diagonal matrix. Furthermore, since G_n is not symmetric, G may have some complex values as its eigenvalues. This is ignored from the current analysis without any explanation. \n\nIn the experiment part, Figure 3 shows that the RMS error of the GDD algorithm will blow up when step size is large. It seems that the proposed algorithm may not be as robust as the conventional TD algorithm?\n\n#########Edits after the rebuttal#########\nThank you for the responses. After reading them and the discussion with other reviewers, I still think the current contribution of this paper is marginal and I keep my score as 5.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lv6Rx7TUwy-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "EDIT: After reading the other reviews, the author's responses, and thinking more about the concerns raised, I have increased my score. However, I still recommend rejection because of questions around the hyperparameters used in the experiments.\n\n---\n\n### Summary:\nThe paper introduces a regularized mean squared projected Bellman error objective function where the regularizer penalizes large changes to the estimated value function. This regularized objective function is used to derive a GTD2-like algorithm where updates to the value function weights are penalized. The paper claims an improved rate of convergence, and empirically investigates the proposed algorithm on tabular random walks, the Boyan Chain environment, and Baird’s counterexample.\n\n### Pros:\n+ paper proposes interesting new method\n+ paper includes theoretical argument for proposed method\n+ paper empirically investigates proposed method\n\n### Cons:\n- concerns about soundness of method\n- concerns about originality, clarity, and quality\n\n### Decision:\nAt the present time I recommend rejecting the paper until the following concerns can be addressed.\n\n### Soundness:\nDoes the proposed modification to the MSPBE change the underlying problem being solved? Is the solution to the regularized MSPBE the same as the solution to the original MSPBE, even with function approximation? The fact that Gradient-DD(4) did not converge on the Boyan chain is very concerning. The motivation for GTD2 is to converge when used off-policy with function approximation. If the proposed modifications lose the convergence guarantee then why not just use conventional TD off-policy?\n\n### Originality:\n- There are no references to prior work on convergence rates of GTD2 in section 4. The analysis seems like it was based on an existing analysis, but nothing is cited.\n- There is no explicit related work section, which would help clarify the novelty of contributions and would help position the paper within the existing literature.\n\n### Clarity:\n- Section 4 (improved convergence rate) is poorly explained, and very difficult to follow.\n- Section 5 doesn't mention beta—the step size for the auxiliary weights. Earlier in the paper kappa is referred to as a regularization parameter, but in section 5 it's called a step size parameter and annealed?\n- There are several statements that don’t make sense to me:\n\n    - “the regularization term uses the previous value function estimate to avoid large biases in the updating process.”\nThe use of the word “biases” here is confusing and conflicts with the statistical notion of bias. Updates to weights would generally not be considered “biases” in the statistical sense. However, the regularization term can be thought of as biasing the optimization towards solutions with certain qualities.\n\n    - \"[importance sampling] is useful for decreasing the variance of parameter updates\"\nUsing importance sampling to correct the difference between the target and behaviour policies usually increases the variance of parameter updates. IS shrinks updates that occur more often than they would when following the target policy, and enlarges updates that occur less often than they would when following the target policy. The average distance from the mean update can be larger than without importance sampling.\n\n    - \"In effect, the regularization term encourages re-experience around the estimate at previous time step, especially when the state space is large.\"\nWhat does “re-experience” mean?\n\n    - “accelerate the GTD2 algorithm” The word “accelerate” is used several times in the paper to describe the Gradient-DD update, but the idea of penalizing large updates to the value function weights conflicts with the conventional meaning of acceleration in optimization (using past information to make larger changes to weights as is done with Nesterov acceleration, momentum, ADAM, etc.), which is confusing. Penalizing updates to the value function weights would actually slow the changing of the value function weights, not accelerate it. This might allow the second set of weights to learn better estimates of the expected TD error (because the expected TD error is changing as the value function weights change), which could account for the performance increase over GTD2.\n\n### Quality:\n- Best performance in the final episode is not an appropriate way to determine the \"best-performing\" parameter settings when the paper makes claims about the speed of learning of various methods. The parameter settings that result in the lowest error at the end of training will not in general be the parameter settings that result in the fastest learning (i.e., smallest area under the curve). If the paper is going to make claims about learning speed, then the parameter settings should be selected based on the smallest area under the curve. This might be why TDC performs so poorly in these experiments when it out-performs GTD2 in other papers (see Ghiassian et al. 2018; TDC is called GTD in that paper) and intuitively should perform similarly to conventional TD in early learning when the correction weights are near 0. This seems like a serious issue to me; the experiments may need to be re-run with different parameter settings that better match the claims the paper is making about learning speed.\n\n### Suggestions for improvement:\n- In addition to addressing the concerns mentioned above, consider adding a related work section that explicitly compares and contrasts the most relevant related methods.\n- Consider motivating Gradient-DD more along the lines of TRPO, REPS, and other algorithms that penalize large changes to the weights being learned instead of motivating it as accelerating GTD2.\n- Actually, it would be better to do some simple experiments to test why the regularization improves performance over GTD2. Does it result in the second set of weights learning the expected TD error with greater accuracy? Can the same effect be achieved by a two timescale approach where the value function weights are updated with a smaller step size than the second set of weights? If not, it would provide more support for the proposed method.\n- Despite the concerns listed in this review, I actually think this paper has a very interesting premise and deserves further study and investigation.\n\n### Misc. details:\n- A sentence trails off in the first paragraph of the introduction.\n- ”where this term originates from the squared bias term in the objective (6)” Equation 6 seems to be the GTD2 update rules, not the objective function.\n\n### References:\nGhiassian, S., Patterson, A., White, M., Sutton, R. S., & White, A. (2018). Online off-policy prediction. arXiv preprint arXiv:1811.02597.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CmnOLsrs213", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary of Contributions\n\nThe paper proposes the gradient descent TD difference learning (GDD) algorithm which adds a term to the MSPBE objective to constrain how quickly a value function can change. They argue that their approach has a quicker convergence rate, and empirically demonstrate in several examples with linear function approximation that it substantially improves over existing gradient-based TD methods.\n\n### Review\n\nI like the simplicity of the proposed method, and its intuitive interpretation as a value-based trust region. However, I have the following questions and concerns:\n\n1) There doesn't seem to be any information regarding how many independent runs were performed in the empirical evaluation, and there was no no reported statistical significance testing. Can the authors clarify this information, and comment on the significance of the results?\n\n2) While it led to improvements over GTD2, it largely didn't improve over regular (semi-gradient) TD apart from Baird's counterexample, which was designed to make TD fail. As such, I don't think the addition of a new parameter was convincingly justified. Some of the results seemed to suggest that the improvement grew as the state space/complexity increased, that it may be the case that the evaluation falls a bit short on exploring more complex environments. While the breadth of the ablation studies is really nice, we observe similar trends in many neighbouring figures that the space in the main text from showcasing the many different configurations could be summarized with representative examples, and the additional space could have been used to provide some additional experiments/insights (like those suggested in the discussion).\n\n3) From how modular the addition of the term is to the objective, have the authors tried incorporating the regularization to semi-gradient TD? Is there anything about the semi-gradient update that bars its use? TD generally performed really well in the paper's evaluation (outside of Baird's counterexample) that it would make a stronger case if the extension was demonstrated to be more generally applicable, and that it consistently improved over the methods it was applied to. This sort of ties into what was described in 2), where what was presented seems to fall a bit short, and how the space could have showcased a bit more.\n\n4) While the paper's focus was on the case of linear function approximation, can the authors comment on how readily the approach can be extended to the non-linear case? GTD methods have not seen as much adoption as their approximate dynamic programming counterparts when combining TD methods with non-linear function approximation, that it can raise questions as to how the methods scale to more complicated settings.\n\nGiven the above, I am erring toward rejection at this time. I think 1) is a rather significant issue that needs to be addressed, and I'm willing to raise my score if that, and my other concerns, can be sufficiently addressed.\n\n----- Post Discussion -----\n\nTaking the other reviews and the authors' response into account, I still maintain my score. While I agree that it's good to be thorough in something clear and simple, it can still be done to a point of redundancy, and consequently seem less thorough in the overall picture and claims made. I'm still largely unsure on the choice to only apply the supposedly modular extension to GTD2, and not try it with TD which seemed like a clearer winner (apart from Baird's counterexample). As others suggested, there are additional methods which might be good to compare to, and other evaluation metrics might make more sense for the claims being made. Many of my concerns were largely brushed off as future work, that little got addressed- without having to carry out the experiments, high level comments/current thoughts could be provided regarding how readily the approach can extend to the scenarios suggested, or if there are nuances that need to be worked out, etc.", "extra_scores": {}, "extra_text": {}}, {"review_id": "23cMPTzhR6f", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary of paper\nThis paper introduces a novel regularized mean-squared projected bellman objective and corresponding GTD2-like algorithm which minimizes the objective. The paper analytically investigates the convergence rate of the proposed algorithm, then empirically investigates the performance of the algorithm across several problems with linear function approximation.\n\n## Summary of review\nThis paper is a clear reject for me. There appear to be significant issues in both the analytical section and the empirical section; which in total bring into question the utility of the proposed algorithm. The literature review also appears to be lacking and there appear to be several minor incorrect statements throughout the paper. I feel quite confident in my evaluation of the empirical section and literature review. I feel confident that there is a bug/typo/incorrect result in the analytical section. I did not attempt to debug the proof to determine which of the three (bug, typo, or incorrect result) was true. Details follow roughly in order of greatest concern -> least concern.\n\n### Proof of convergence rate\nI follow the proof up to equation (12). This is a standard result from (e.g) Maei's 2011 thesis. After equation (12) I follow the transformation that solved for $\\rho_{n+1} - \\rho_n$ resulting in a matrix inverse. However, after distributing the matrix inverse, I remain confused why $\\sqrt{\\xi} g_{n+1}$ is not multiplied by the inverted matrix? This, however, may not change the resulting eigenvalues so I do not believe it will change the result. Continuing on to equation (14), I did not check for correctness solving the polynomial for the eigenvalues, so I will rely on the given result in the paper. The conclusion of which states: $\\lambda = - \\frac{1}{2} (\\alpha^{-1} + \\lambda_G) \\pm \\frac{1}{2} \\sqrt{\\text{thing}} < -\\lambda_G$. Ignoring a few details in the middle, the result ultimately states $\\lambda < -\\lambda_G$. Here lies the fundamental problem. Because GTD2 is known to be a convergent linear system, then we know $\\lambda_G$ are all strictly negative (proof of this in Maei's thesis) under some assumptions (notably the invertibility of $X X^\\top$). For such a linear system to be convergent, we **must** have the real part of the eigenvalues be strictly negative. The proof under equation (14) states $\\lambda < -\\lambda_G$, which because $\\lambda_G$ is strictly negative, means that $\\lambda < \\text{some positive number}$. This (a) tells us nothing of the comparative convergence rates since $\\lambda$ could be larger than $\\lambda_G$, and (b) also suggests that there could be cases where the proposed algorithm does not even converge in the first place because $\\lambda$ could be greater than or equal to 0. This could be a typo and the negative sign on the right shouldn't exist, but because there are few details from equation (14) to the end, I was unable to debug and decide if this is typo/bug/incorrect conclusion.\n\nThere a few other issues with the proof that concern me.\n* Do we know that the upper-bound on $\\kappa$ is reasonable? The quantity $\\alpha (\\lambda_G - \\alpha^{-1})^2 / 4$ is difficult to interpret, but the reliance on $\\alpha^{-1}$ seems to imply a preference toward much smaller stepsizes; which seems counter-intuitive towards the goal of improving convergence rates.\n* Likewise, the first part of the solution for $\\lambda$ we have $-\\frac{1}{2} (\\alpha^{-1} - \\lambda_G)$ which likewise implies that smaller stepsizes significantly improve convergence rate (small $\\alpha$ implies highly negative $\\lambda$). Considering the remainder of the solution for $\\lambda$ is under a square-root, this first factor appears to be dominant (though I could be wrong on this, more insight would be appreciated!). A stepsize approaching 0 would yield the fastest convergence rate (apparently) by having the smallest eigenvalue approach negative infinity. This simply does not pass the \"smell test\".\n* Further building on my previous point, for large enough values of $\\alpha$ we will be in a situation where $\\alpha^{-1} < |\\lambda_G|$ meaning that the first term will become positive. Considering that the second term is a plus-or-minus, then we could be adding a positive term to a positive term yielding a positive eigenvalue. This means that for large enough $\\alpha$ we don't have convergence any longer. I wonder how feasible the upper-bound on $\\alpha$ is to guarantee convergence. I would also like to see these assumptions explicitly stated in the proof.\n* A lot of little details were left out of the proof. Where are the assumptions on boundedness of the features and the rewards? Can one show that the noise sequence of the modified algorithm is actually a Martingale Difference Sequence and thus the result from Borkar and Meyn 2000 holds? Need there be an assumption of independent samples or are these samples coming from Markovian sampling?\n\n### Empirical section\n* The choice to set the initial value function $V(S) = 0.5 \\forall S$ for the random walk was odd. I suppose that because the left reward = 0 and the right reward = 1, and the policy is 50% chance to go left or right, and $\\gamma=1$, then the optimal value function $v_\\pi$ linearly interpolates from (0, 1) with the center-most state having value $V(n // 2) = 0.5$. This choice seems likely to disproportionately favor the proposed GDD algorithm; which encourages the value function estimate to change slowly. Because the initial estimates are so close to correct, only small changes will be necessary and the regularizer term will remain small. What happens if the value function is initialized to 0 everywhere, or even to -1 everywhere?\n* The exclusion of TDC from the stepsize sensitivity investigation makes little sense to me. The first experiment chose an aggressively large stepsize $\\alpha = 0.5$ for which TDC performed poorly. Then did not investigate the sensitivity of TDC to stepsize in later plots because of this choice. If you check [Giassian et al. 2020], they report that TDC in fact out-performs GTD2 on all of the same domains tested here for appropriately chosen $\\alpha$ and $\\beta$.\n* The choice of $\\beta$ is never discussed. How did you set $\\beta$?\n* How many runs? What is the variance? Are any results statistically significant?\n* The primary motivation of the paper was around off-policy learning, yet only one of the tested domains was off-policy (Baird's Counterexample star MDP). It would have been nice to see the random walks made into off-policy domains.\n\n### Literature review\n* This paper modifies the MSPBE by adding a regularizer term. There are a few other papers in the literature that do this and derive the corresponding GTD2/TDC algorithms. Liu et al. 2012 and Ghiassian et al. 2020 immediately come to mind. These should both be cited and discussed.\n* Are there any papers that add such a constraint as $\\| w_n - w_{n - 1} \\|^2$ to any known objective function? This seems like an odd choice of regularizer (penalizes making changes to the weights), so any prior literature from any field (supervised learning, online learning, optimization, etc.) would go a long way in convincing the reader that this is a good idea.\n* The paper mentions several times that GTD methods converge more slowly than TD. I know of a single proof that shows this in Maei's thesis for the GTD algorithm. I do not know of any such proof for TDC or GTD2. There exists empirical evidence of this in Ghiassian et al. 2020 or White and White 2016, but neither of these papers are cited.\n* GTD methods and importance sampling are not mutually exclusive methods for off-policy learning. In fact, GTD methods canonically use IS for their off-policy variants. Further importance sampling definitely does not decrease the variance of parameter updates (mentioned in the second paragraph of Section 1).\n* Sutton et al. 2009 is not really a breakthrough in the study of convergence properties of MDP systems. In fact, the proofs of Sutton et al. 2009 do not even assume samples are drawn from a distribution induced by an MDP. Perhaps Borkar and Meyn 2000 is a better reference as it fundamentally builds the proof structure used by Sutton et al. 2009?\n\n### Other minutiae\n* Eye-balling the modified objective function leads me to believe the objective shares the same fixed-point as the MSPBE (thus the new GTD2 algorithm converges to the same fixed-point as TD), but it would be nice to show this formally in the analytical section.\n* Is it possible to extend this objective to the non-linear setting?\n* The paper mentions that the proposed regularizer avoids large biases in the updating process. Does it not *add* bias to the updating process? Perhaps it was meant that the regularizer avoids high variance? Either way, a careful analytical discussion of the bias-variance properties would go a long way towards improving this paper.\n* In section 5.3 what is $\\eta$? I believe this is supposed to be $\\beta$ (i.e. the stepsize for the secondary weights) since $\\eta$ is your secondary weight vector?\n* Would it make more sense to consider $\\kappa$ to be a regularizer parameter instead of a stepsize and having it absorb $\\alpha$? It seems in the experiment section you split these anyways, so perhaps it makes the analytical section much more clear if the algorithm was instead $\\alpha\\kappa (x^\\top w_n - x^\\top w_{n-1})$. \n* The paper repeatedly defines off-policy learning as learning the optimal policy using an exploratory policy. This is a bit of a restrictive setting and is certainly not the setting that Sutton et al. 2009 considered (the work that this paper builds upon).\n* Why assume that the target policy is deterministic (mentioned in Section 2.1)? This is a strange choice that is not used in either the empirical or analytical section as far as I can tell.\n* It is mentioned that TD methods should seek to minimize the MSPBE (or perhaps the MSBE it isn't clear which is meant), but shouldn't instead the goal be to minimize the MSVE (e.g. $\\| \\hat{V}_w - v_\\pi \\|^2$)?\n\n### Papers mentioned in this review\nMaei, Hamid Reza. “Gradient Temporal-Difference Learning Algorithms.” University of Alberta, 2011.\n\nSina Ghiassian, Andrew Patterson, Shivam Garg, Dhawal Gupta, Adam White, and Martha White. “Gradient Temporal-Difference Learning with Regularized Corrections.” International Conference on Machine Learning, 2020. http://arxiv.org/abs/2007.00611.\n\nAdam White, and Martha White. “Investigating Practical Linear Temporal Difference Learning.” International Conference on Autonomous Agents and Multi-Agent Systems, 2016. http://arxiv.org/abs/1602.08771.\n\nBorkar, V. S., & Meyn, S. P. (2000). The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning. SIAM Journal on Control and Optimization, 38(2), 447–469. https://doi.org/10.1137/S0363012997331639\n\nSutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., & Wiewiora, E. (2009). Fast gradient-descent methods for temporal-difference learning with linear function approximation. Proceedings of the 26th Annual International Conference on Machine Learning - ICML ’09, 1–8. https://doi.org/10.1145/1553374.1553501\n\nLiu, B., Mahadevan, S., & Liu, J. (2012). Regularized Off-Policy TD-Learning. Advances in Neural Information Processing Systems, 9.\n\n# After discussion and edits\n\nI acknowledge that I have read the other reviews and resulting discussions and I have read the relevant changes in the edited text. I have raised my score from 2->3 to reflect that several concerns were alleviated through the edits, but several new concerns (and old concerns) remain. I will summarize below.\n\nAfter the author edits, the issue with convergence and convergence rates appear to have been resolved. I additionally appreciate the much greater clarity in the analytical section. However, I still find the contribution to be borderline at best in terms of novelty of approach and I find that the evidence of applicability is still considerably lacking. The introduction of a regularizer to accelerate GTD methods is itself not novel. The form of the proposed regularizer is novel, however, I find its form to be unintuitive as it punishes making changes to the weights. There are some prior works that motivate this well (i.e. TRPO and other trust-region optimization techniques), but this paper does not appeal to prior works to motivate their regularizer. Instead, I must rely on the empirical study which does not investigate the learning speed of the proposed algorithm compared to baselines. In many cases, the proposed algorithm does not clearly outperform baselines.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces an simple but potentially effective off-policy TD algorithm. 

Overall, the reviewers felt the work was incomplete and not yet ready for publication. The all recognized the authors made significant updates to the paper, but serious issues remain with the empirical work: studying the impact of the proposed extension on other algorithms, missing baselines (e.g., TDRC), scope of environments limited similar chain-like domains, significant questions about how best parameter settings where chosen for comparison, etc.

This is clearly an interesting direction. If the authors can improve the experiments and better situate their method if the literature (connecting to the lit in off-policy RL about accelerating and improving off-policy TD methods this will become a solid contribution.
Decision: Reject