Backstepping Temporal Difference Learning
Authors: Han-Dong Lim
Donghwan Lee
Venue: ICLR 2023 poster (2023)
Keywords: reinforcement learning
temporal difference learning
policy evaluation

Abstract:  Off-policy learning ability is an important feature of reinforcement learning (RL) for practical applications. However, even one of the most elementary RL algorithms, temporal-difference (TD) learning, is known to suffer form divergence issue when the off-policy scheme is used together with linear function approximation. To overcome the divergent behavior, several off-policy TD learning algorithms have been developed until now. In this work, we provide a unified view of such algorithms from a purely control-theoretic perspective. Our method relies on the backstepping technique, which is widely used in nonlinear control theory.

Published as a conference paper at ICLR 2023
BACKSTEPPING TEMPORAL DIFFERENCE LEARNING
Han-Dong Lim
Donghwan Lee
Department of Electrical Engineering KAIST, Daejeon, 34141, South Korea Limaries30kaiis ac.
Department of Electrical Engineering KAIST, Daejeon, 34141, South Korea donghwankkaist kr
ABSTRACT
Off-policy learning ability is an important feature of reinforcement learning (RL) for practical applications. However, rithms, temporal-diffeet diffferenceeeee (TD) learning, is known to suffer form divergence issue when the off-polict scheme is used together with linear function approxi- mation. To overcome the divergent behavior, several off-policy TD-learning al- gorithms, including gradient-TD learning (GTD), and TD-leamnigg with correc- tion (TDC), have been developed until now. In this work, we provide a unified view of such algorithms from a purely control-theoretic perspective, and propose a new convergent algorithm. Our method relies on the backstepping technique, which is widely used in nonlinear control theory. Finally, convergence of the pro- posed algorithm is experimentally verified in environments where the standard TD-learning is known be unstable.
one of the most elementary RL algo-
INTRODUCTION
Since Mnih et al. 2013). which has demonstrated that deep reinforcement learning (RI.) outper- forms human in several video games (Atari 2600 games), significant advances has been made in
RL theory and algorithms. For instance, Van Hasselt et al. 2016); Lan et al. (220);; Chen et al. (2021) proposed some variants of the so-called deep Q-network (Mnih et 2015) that achieves higher scores in Atari games than the original deep Q-network. An improved deep RL was devel- oped in Badia al. (220)) that performs better than average human scores across 57 Atari games. Not only performing well in video games, but bctSithritwiieeer et al. (2020) also have shown that an RL agent can self-learn chess, Go, and Shogi. Furthermore, RL has shown great success in real world applications, c.g., robotics (Kober et al. 2013). healthcare (Gottesman al. 2019). and recommen- dation systems (Chen et al. 2019).
Despite the practical success of deep RL, there is still gap between theory and practice. One of the notorious phenomena is the deadly triad (Sutton Barto 2018), the diverging issue of the algorithm when function approximation, off off-policy learning, and bootstrapping
used together. (TD) learning (Sutton
One of the most fundamental algorithms, the so-called temporal-different 1988), is known diverge under the deadly triad, and several works have tried fix this issue for decades. In particular, the seminar works SStton et al. (2008) 2009) introduced the so-called GTD, gradient-TD2 (GTD2), and TDC, which are off-policy, and have been proved to be convergent with linear function approximation. More recently, Ghiassian et al. (202)) suggested regularized version of TDC called TD learning with regularized correction (TDRC), and showed its favorable features under off polico settings. Moreover, Lee et al. 2021) developed several variants of GTD based on primal dual formulation.
On the other hand, backstepping control Khalil 2015) is popular method in designing stable controllers for nonlinear systems with special structures. The design technique offers wide range of stable controllers, and is proved to be robust under various settings. It has been used in various fields including quadrotor helicopters (Madani & Benallegue/ 2006), mobile robots (Ficrro & Lewis, 1997). and ship control (Fossen & Strand] 1999). Using backstepping control technique, in this paper, we develop a new convergent policy TD-learning which a single time-scale algorithm.
In particular, the goal of this paper is to introduce new unifying framework to design off-policy TD- learning algorithms under linear function approximation. The main contributions are summarized as follows:

---

Published as a conference paper at ICLR 2023
We propose systemic way to generate off- off-policy TD-leaning algorithms including GTD2 and TDC from control theoretic perspective.
Using our framework, we derive a new TD-learing algorithm, which we call backstepping TD (BTD).
We experimentally verify its convergence and performance under various settings including where ooolpy TD has known to be unstable.
In particular, most of the previous works on off-policy TD-learning algorithms (e.g., GTD2 and TDC) are derived based on optimization perspectives starting with an objective function. Then, the convergence is proved by proving stability of the corresponding O.D.E. models. In this paper, we follow reversed steps, and reveal that off-policy TD-learning algorithm (called backstepping TD) can be derived based on control theoretic motivations. In particular, we develop stable O.D.E. models first using the backstepping technique, and then recover back the corresponding off ooolcy TD-learning algorithms. The new amalysis reveals connections between off- off-policy TD-learning and notions in control theory, and provides additional insights off-policy TD-learning with simple concepts in control theory. This sound theoretical foundation established in this paper can potentially motivate further analysis and developments of new algorithms.
Finally, we briefly summarize TD learning algorithms that guarantee convergence under linear func- tion approximation. GTD (Sutton et 2008). GTD2 and TDC (Sutton al. 2009) have been de-
veloped to approximate gradient on mean squared projected Belllman error. Later, GTD and GTD2
has been discovered solve minimax optimization problem (Macua al. 2014 Liu et al.
2020
Such sadde-point view point of GTD has led to many interesting results inc melluing Du et al. 201
Dai et al.] (2018); Lee et al. 202T). TDRC (Ghiassian et al., (0200) adds an additional term similar to regularization term to one-side of parameter update, and tries to balance between the performance of TD and stability of TDC. TDC+ (Ghiassian et al. 2020) also adds an additional regularization term on both sides of the parameter update. Even though TDRC shows good performance, it uses additional parameter condition to ensure convergence, whereas TDC++ does not.
2
PRELIMINARIES
2.1 NONLINEAR SYSTEM THEORY
Nonlinear system theory will play an important role throughout this paper. Here, we briefly review basics of nonlinear systems. Let us consider the continuous time nonlinear system
i =x uz), 3o R"
(I)
where Tn E Rn is the initial state, 1. E IR, 2 0 is the time, It. E RR" is the state, ue E IR"" is the control input, and f : RR x Ra -> RR. nonlinear mapping. An important concept in dealing with nonlinear systems is the equilibrium point. Considering the state-feedback law
p(x,),, the system can be written as á; = f(x,, ux) = =f(x,, =(xx,,(xx))) =: f(x)), and a point x = x² in the state-space is said to be equilibrium point of of if it has the property that whenever the state of the system starts at x², it will remain at x (Khalil, 2015). For d = f(zz), the equilibrium
points are the real roots of the equation f() 0. The equilibrium point x² is said to be globally asymptotically stable if for any initial state zn E IR", 3e + x² as xc.
An important control design problem is construct state-feedback law u4 = p(xx)) such that the origin becomes the globally asymptotically stable equilibrium point of [T] To design a state- feedback law meet such goal, control Lyapunov function plays a central role, which is defined in the following definition.
Definition 2.1 (Control Lyapunov function (ontag 2013)). A positive definite function V R - R is called a control Lyapunov function (CLF) for all + O, there exists a corresponding control imput u E Rmhh that satisfies the inequality, V (xV()) f(z, u) < 0 foror all x + 0.
Once such a CLF is found, then it guarantees that there exists the control law that stabilizes the system. Moreover, the corresponding
feedback control law can be extracted from the CLF, e.g., ((x)) = arg min, V, [x) f u) provided that the minimum exists and unique. The concept of control I Lyapunov function will be used in the derivations of our main results. For the autonomous
2

---

Published as a conference paper at ICLR 2023
system, 21 f(x), and Lypaunov function V R. + R. Lie derivative is defined as CyV(x)
(2)
(V))))((()))))))) f(x) so that (zz) ()V(z)) along the solution.
2.2
STOCHASTIC APPROXIMATION
O.D.E. APPROACH
Including Q-learning (aakkins & Dayan 1992) and TD-learning (uttonn 1988). reinforcement
learning algorithms can be considered as stochastic approximation (Robbins & Monro I95T de- scribed by
(2) R" is nonlinear mapping, and E is an ii.d. noise. Borkar and Meyn the- orem (Borkar & Meyn 2000) well-known method to bridge the asymptotic convergence of stochastic approximation and the stability of its corresponding O.D.E. model, which can be ex- pressed as
Tk+1 = T% + az (f(x)) + (k),
where f 12 +
=, = f(x),
To R.,
where za RR is initial state, and t RR, t 2 0 the time.
Borkar and Meyn theorem (Borkar & Meyn 2000) states that under the conditions in Assumption 7.1 in the Appendix, global asymptotic stability of the O.D.E. [3) leads to asymptotic convergence of the stochastic approximation update ( which is formally stated in the following lemma.
Lemma 2.1 (Borkar and Meyn theorem (Borkar & Meyn 2000)). Suppose that Assumption 7 in
the Appendix holds, and consider the stochastic approximation in (2) Then, for any initial xn k
sup || < oo with probability one. In addition, 2g x as + 00 with probability one, where xº is the unique equilibrium point of the O.D.E. in
The main idea of Borkar and Meyn theorem is as follows: iterations of a stochastic recursive al- gorithm follow the solution of its corresponding O.D.E. in the limit when the step-size satisfies the so-called Robbins-Moo Monro condition (Robbins & Monro 195T) in (33) in the Appendix. Therefore, by proving asymptotic stability of the O.D.E., we can induce convergence of the original algorithm.
In this paper, we will use an O.D.E. model of TD-leaming, which is expressed as a linear time- invariant system.
2.3 BACKSTEPPING CONTROL
This section provides the concept of the backstepping control (Kokotovic 1992 Khalil 2015 which will be the main tool in this paper to derive TD-leamiing algorithms. The backstepping tech- nique is a popular tool for generating CLF (control Lyapunov function) for nonlinear systems with specific structures. In particular, let us start with the following general nonlinear system:
t f(y) + g(ye)x;
i;1
where Y/ E Thm Je E Rn are the states, Me E R..h is the input, and f R. - R. and g T TR. are continuous functions. The first system is a nonlinear system with a particular affine structure, and the second system is simply an integrator. It can be seen as a cascade interconnection of two systems, where the second system's 's state is injected to the input of the first system. The backstepping control technique gives provided that the first system admits a CLF independently. To this end, we suppose that the first system admits CLF. Through the backstepping approach, designing stable control law for the above system can be summarized in the following steps:
systematic way generate a CLF for such particular nonlinear systems
Step 1. Consider 2, in (4) as virtual input ((v)) (state-feedback controller), and consider the fol- lowing system: X = f(:) + o(v, ) (vr). Design ((v.) such that the above system admits a CLF V, i... it admits a positive definite and radially unbounded function V such that its time derivative is negative definite, i.e.,V Vvx.) < 0, Vy. + O.
Step 2. Denote the error between the virtual state- feebbfee controller ((ye) and state variable x Z1 -. Now, rewrite the original O.D.E. in (4) with the new variable (ye, =x):
[(ve) + g(v )=())) + g(y)
d' di
2t
ue 5(ye)
3

---

Published as a conference paper at ICLR 2023
Step 3. Design the control input u, such that the above system is stable. One popular choice is to consider the CLF Ve(Ye, 2) := V(3) + || //2 where V(y.) is defined in Step Then choose u such that the time derivative of Va 2x) be negative definite.
A simple example of designing stabilizing control law by backstepping technique is given in Ap- pendix Section
2.4 MARKOV DECISION PROCESS
In this paper, we consider a Markov decision process (MDP) characterized by the tuple (S, A. P,,,)), r), where S == {1. .........e |S]] stands for the set of finite state space, [S] denotes the size of S, A == (1,2....,1A4 [A] denotes the set of finite action space, |A| the size of A, E (0. 1) is the discount factor, P : S x A x S - [0, 1] denotes the Markov transition kernel, + R means the reward function. action A. then the current state transits to the next state s' E S with probability P(s, a, s'), and the agent receives reward r(s, a, s'). Each element of the state to state transition matrix under policy n, denoted by pT IR S1 (S is [P] = Σ ((aa))P(i, j),, 1 i,j < [S], where aEA
and r x A
particular, if an agent at state a E S, takes
[P"]i corresponds to i-th row and j-th column element of matrix P Moreover, the stationary state distribution induced by policy μs, is denoted as d : S + [0, i.e., du pu = d With the above setup, we define the following matrix notations:
Baws [r(8, as, a 1/
ddd (1)
E Ban r(s, a, s.)ss) s'){s
D" =
E R SIXIS
R
E ER|
d' ((S))
Be-x|r(s,a, 5)1s |l|]]
where DR is diagonal matrix of the state distribution induced by behavior policy le, each element of R the expected reward under policy at the corresponding state. The pol- S, (T)
icy evaluation problem aims to approximate the value function at state E EE== rr(k,. As, Sk+1) Su s. where the trajectory is generated under policy π : S A + [0, 1]. In this paper, we consider the linear function approximation to approximate the value function e" (s). In particular, we parameterize the value function (s) with o (s)G. where S:S + IR" is pre-selected feature vector with 6(s) ;= [ (*) ... [n])]]. ó1...., on :S + R are feature functions, and E Fn is the learning parameter. The goal of the policy evaluation problem is then to approximate the value function v (s) using this linear parameterization, i.e., (S)E oF (s). Moreover, using the matrix notation called the feature matrix, the linear parameterization can be written in the vector form &5. We also assume that is full column rank matrix throughout the paper, which is standard assumption (Sut-
((2). d(()) e R|(|xn
ton al. 2008 2009, Ghiassian et al. 2020 Lee et al. 2021)
2.5
TEMPORAL DIFFERENCE LEARNING
Suppose that we have access to stochastic samples of state s; from the state stationary distribution induced by the behav- ior policy μ., i.e., $І ~ d'(),, and action is chosen under behavior policy μ. i.e., ag ~ pu(-(sk). Then, we observe the next state sy following sy r(8R, ag, (.))))) *6)). Using the simplified notations for the feature vectors Φ2 == s(su), % ((s(). the TD-learning update at time step with linear function approximation can be expressed as Ex+1 = & (Ex))xx( where ag > 0 is the step-size, ōy(Ex) := rx +ook & of & is called the temporal difference or temporal difference error (TD-error), and Pk == p(ss, ax) = s(asles)
This section provides brief background on TD-learning (Sttonn 1988).
(((.aa, sg), and receive the reward To ==
plav]sa)
called the importance sampling ratio (Precup et al. 200T). The importance sampling ratio re- weights the TD-error to handle the mismatch between the behavior policy μ and target policy æ. is known that TD-learning with linear function approximation and off off-policy learning scheme does not guarantee convergence in general. The above stochastic approximation aims find fixed point of the following projected Bellman equation, which is, after some manipulations, expressed as:
Φ DM 7 DA DE" क6 D" R
(5)
4

---

Published as a conference paper at ICLR 2023
To simplify the expressions, let use introduce one more piece of notations:
A = B.w//attteeeee/rmrooooool000d0dd - 4 D - -
P R"x*,
b == Pe (s,, s'aaa,"))))) ())() $ D RT E ER
Even though can arbitrary distribution, for simplicity assume stationary distribution of μ.. Now, we can rewrite [5) compactly as
Ag" = b.
(6)
The corresponding O.D.E. for TD-learning can be written as & = A&, b, So E IR.. Using the coordinate transform Iy == EK 6" we get the O.D.E. a; Ar,, 3o E R", whose origin is globally asymptotically stable equilibrium point p(s.a) = x(مb
for all (s. E x A. Throughout the paper we will use the vector 2/s- == & - 5 to represent the coordinate transform of & the origin, and will use & and 22 to denote the corresponding continuous time counterparts of Ex and Fa, respectively.
m(als)
2.6 GRADIENT TEMPORAL DIFFERENCE LEARNING
To fix the instability issue of off-policy TD-learning under linear function approximation, |utton et al. (2008) and Sutton et al. (2099) introduced various stable off off-policy TD-leaming algorithms, called GTD (gradient TD-learning, GTD2, and TDC (temporal difference correction). The idea be- hind these algorithms is to minimize the mean-square error of projected Bellman equation (MSPBE) minęeR" 11 T D" (R +YP - D= where
|||||| == Vz Dx, and the global min- imizer of MSPBE corresponds to the solution of (6) The core idea of the algorithms is to introduce an additional variable λ& E I" to upproximate the stochastic gradient descent method for MSPBE
as an objective function. In particular, GTD2 update can be written as
A++1 A + (- A (Ex)))) Ek+1 Ex oul dEdE PKYYO x2
We denote X to denote continuous time part of λς. Since the fixed point for A is zero, it doesn't require coordinate transformation. It is a single time-scale algorithm because it uses a single step- size ag. The corresponding O.D.E. is expressed as Å₃ -CA, Ar,, &. A Xr, where C :=
E. Ex (=) (s)] = +" D Roxx, Similarly, TDC update can be written as
A = d + (- d (Ex)
Ex+1 = E + Bx P- d + (Ex)).))
(8)
where the step-sizes, 0g and 32, satisfy ag 8g + 0 k + oo and the Robbins and Monro step-size
condition (Robbins & Monro 1951 in (33) Appendix. It is two time-scale algorithm because uses two time-steps, (g) and 33g.
3 DESIGNING TD-LEARNING THROUGH BACKSTEPPING
We briefly explain the motivation for our algorithmic development. Borkar and Meyn the- orem (Borkar & Meyn 2000) in Lemma 2. a typical tool to prove convergence of Q- learning (Borkar & Meyn 2000 Lee & He 2019) and TD-learning (Sttonn et al., 2009) Lee et al.
2021) Most of the previous works on off-policy TD-learning algorithms (e.g.. GTD2 and TDC)
first start with an objective function, and then derive GTD algorithms based on optimization per- spectives. Then, the convergence is proved using the corresponding O.D.E. models and stability theory of linear time-invariant systems. A natural question arises is, can we derive off-police TD- learning algorithms following a reversed step? other words, can we develop a stable O.D.E. model first using tools in control theory, and then recover back the corresponding off-policy TD-learning algorithms? In this paper, we reveal that a class of off-policy TD-lcarning algorithms can be derived based purely control theoretic motivations following such reversed process. By doing so, this work provides additional insights on off- policy TD-learning algorithms and gives a sound theoretical foundation off-policy TD-leaming algorithms for further developments of new algorithms.
Designing stabilizing control laws for continuous time nonlinear system has been successful over the past decades (Khalil) 2015). One such technique, called backstepping, is popular controller
5

---

Published as a conference paper at ICLR 2023
With the help of the backstepping method (Khalil 2013), we design stabilizing control laws for continuous-time systems, and then the corresponding off-policy TD-learning algorithms are derived, and are shown to be convergent via Borkar and Meyn theorem (Borkar & Meyn, 2000) in Lemma 2.1 The brief procedure is explained in the following steps: Step 1) Choose appropriate continuous-time dynamic model such that (a) we can recover the TD-fixed point 5* in (6) via its equilibrium point; (b) the corresponding stochastic approximation algorithm can be implementable only through transitions of MDP and accessible data.; Step 2) Using the backstepping method, design control input to stabilize the dynamic model chosen in Step 1).
design method in non-linear control literature (Khalil 2015)
3.1 BACKSTEPPING TD
Now, we introduce a new off-policy TD-learning algorithm, which we call Backstepping TD (BTD). Firstly, we will develop a stabilizing control law for the following the continuous-tine time system:
A = (-C [-]+ - Axx
(10)
The idea stems from finding a control system for which we can easily apply the backstepping tech- inque. In details, the backstepping techinqiue can be applied to the two interconnected systems where one subsystem, namely [4) can be stabilized with 2e in (4) as a control input. Therefore, first aim is to find such a system. To this end, can try natural choice of O.D.E. to solve the TD problem, i.e., Å₂ Ad,, which is however unstable in the off off-policy case. Therefore, can develop modified O.D.E. X (-C nA)A, Ar2, where I2 is the control input, the neg- ative definite matrix CC is introduced to stabilize the system, and 1) > is introduced to provide additional degrees of freedom in design. Now, the constructed system can be stabilized through the state-feedback controller xe = 17,,, and admits the simple control Lypaunov function ((A) = |||l Moreover, A should be included in the right-hand side in order implement the corresponding algorithm without knowing the solution because 2i- = & - 5" and &* should be removed using Ag* b in the final step. Simply setting xt = 1/4e may cancel out in the right-hand side, the O.D.E. becomes Å = CA,, Therefore, as mentioned before, we can apply the backstepping tech- nique by adding an additional dynamic controller. As the next step, the backstepping technique is applied, and one needs to observe what would be the final form of the control system. In summary, if consist f(Ae) with the combination of A and -C (not necessarily -C, it may be -I) it can be a reasonable candidate to apply the backstepping technique. Cancelling A with virtual input only leaves -C, which guarantees stability from its negative definiteness. Therefore, (9] and (10) is a reasonable candidate for the dynamics where we can apply the backstepping technique. In particular, our aim is to design appropriate control input i, for the above system such that the origin is the unique asymptotically stable equilibrium point, i.c., (2), + 0 as + oc for any (Ao, 2o) E R R" The overall procedure is depicted in Figure [ in the Appendix, and we show how to choose the control input u, in the following lemma.
Lemma 3.1. Consider the O.D.E. in 19) (aaand(10) [10) we choose the control input u, := (AT +12A- xC) nA,, then the above O.D.E. has globally asymptotically stable origin, iee. (de, 21)
0) as oo for any (Au, Fu)) E RR" RR".
Proof sketch. The proof follows the steps given in the backstepping scheme in Section S First, substituting in with virtual controller (()x), we will design control law ((Ax) that stabilizes the following new virtual system:
-= AZ().).
(11)
One natural choice of the virtual controller is =(A:) = ride. Plugging it into (11) leads to A -CAs, and we can verify the global asymptotic stability of the above system with the following I Lyapunov function:
V(A.)
(12)
We now consider the original O.D.E. in (9) and [10] Applying simple algebraic manipulations yield
-Ch,
A(x:
rjλe), dt. uy. The emror between va and the virtual controller ((x)) can

---

Published as a conference paper at ICLR 2023
be expressed as new variable 24, which is 22 -i(A)) mdp. Rewriting the O.D.E. in 9) and (10) with (de, 2e) coordinates, we have
d = C².+ Azt 2 = Ue + nC'' + 1AA2,
(13)
To prove the global asymptotic stability of the above system, consider the function Vo(A,, 2r) v(A+)+ + 2 where (Aee) is defined in (12) By taking in as u, = A X ~ - -7,.,, we can
apply LaSall'es invariance principle in Lemma 7.1 The full proof is in Appendix Section 7.4. L
Using the relation == - - the control input in the original coordinate (Ac, zz) can be written
as Ue := A A T/C nA4z (A + " nAr, Plugging this input into the
original open-loop system in (9) and (10) the closed-loop system in the original coordinate (A,, xx) can written as
\ = (-C+ m4)4, - Ax,
(14)
= (A + - C) - AA
(15)
whose origin is also globally asymptotically stable according to Lemma 3.1 -A
Recovering back from
Ty to εr. we have d X
-C+
A
b
at
E2
= A A nC -n
Ee
+
[b
The corresponding stochastic
approximation of the O.D.E. in Theorem 3.1 becomes
A6+1 A + ax(((11+++++++)))0011 n) 1P=70K (T ) + 6 (Ex))
(16)
Ex+1 Ex + ax(((=>>++)))))))) ) -n² -2pP DaDE np (Ex)ou + (0x dROR PAYOR dkok)) (17)
The equilibrium point of the above O.D.E. is (0, Hence, we only need to transform the coordi-
nate of & to x, = & - - which results to the O.D.E. 14) and [1]] With the above result, we are now ready to prove convergence of Algorithm ! The proof simply follows from Borkar and Meyn
theorem in Lemma 2.1 of which the details can be found in Sutton et al. 2009))
Theorem 3.1. Under the step size condition
(33) with Algorithm in Appendix, & - 5"
> D0 with probability one, where 5" is the fixed point of 6
Proof. The proof is done by checking Assumption
Appendix.
Remark 3.1. Theorem 3.1 doesn't require any condition on n7. Therefore, we can set n which results to GTD2 developed in Sutton et al. 2009
3.2 RECOVERING SINGLE TIME-SCALE TDC
In this section, we derive a single-time scale version of TDC Sutton al. 2009p through the back- stepping design in the previous section. TDC (Sutton et al. 2009) was originally developed as two-time scale algorithm in Sutton al. (2099) Even though the two time-scale method provides theoretical guarantee for a larger class of algorithms, the single time-scale scheme provides more simplicity practice, and shows faster convergence empirically. Subsequently, Maei] (2011) pro-
vided a single-time scale version of TDC by multiplying large enough constant 1) >> 0 to the faster time scale part [7] which leads to
ARt1 Au Bun(- d + padx (Ex))øn
(18)
EK+1 = Ev + Ba(-PALOf &h
(19)
where
> max Ammin (C- (A+ AT)))
(20)
Here, we derive another version of single-time TDC by multiplying constant to the slower time- scale part in (8) which results in
Aet1 > + aal- d + Prox
(21)
Ex+1 E + a d puy deo' + (xbx(Ex)(k))
(22)
7

---

Published as a conference paper at ICLR 2023
where B satisfies
Amin Amia(C)
0 << 3
if (A) <
clse
B>
0.
(23)
Amin (A)
We derive the above algorithm following similar steps as in Section 3.1 Let us first consider the following dynamic model:
7, -C AAx
(24)
át Wt
(25)
Using the backstepping technique, we can prove that the above system admits the origin as global asymptotically stable equilibrium point with the control input un B ((A" C)) AL.). which is shown in the following lemma:
Lemma 3.2. Consider the O.D.E. in (24) and [25] Suppose that we choose the control input
uy == 3 ((A C)}x - AC,)), and B3 satisfies condition
(23) Then, the above O.D.E. has globally
asymptotically stable origin, i.e., (Ne) + (0,0) as oc.
The proof of Lemma is given in Appendix Section
By Borkar and Meyn theorem in Lemma 2.1 we can readily prove the convergence of Algorithm 2 in Appendix, which uses
7.42
stochastic recursive update (2T) and
(2)
Theorem 3.2. Consider Algorithm in Appendix. Under the step size condition
33 satisfies (23 Ex + E" as k > oo with probability one, where 5" is the fixed point of (6)
and
We will call the Algorithm as TDC-slow, and single-time version of TDC suggested by Maci 2011) TDC-fast. Other than the multiplication of constant reflecting two-time scale property, we can make TDC into a single-time algorithm, which we call a single time-scale TDC2, while the original version in Maei (20T) will be called the single time-scale TDC. The derivation is given in Appendix Section 7.5 The performance of such versions of TDC are evaluated in Appendix Sec-
tion 7.9.1 Even though not one of the algorithms outperforms each other, TDC-slow and TDC2
shows better performance in general.
3.3 GENERALIZING TDC+
This section provides versions of TDC+ (Ghiassian et al., 2020). which is variant of TDC. With an additional regularization term & on both updates of TDC in and (8) the update is written as follows:
Ac+1 X + awn(-00 d + p Bbx)
(26)
{x+1 Ex + ( da 3dx + 8 (Ex)ØR),
(27)
where 17 > satisfies (00 and B > is new parameter. Note that TDC+ can be simply viewed as variant of TDC by adding the term BA in the update, which can be seen regularization term. Therefore, letting 3 = 0 yields the original TDC. this paper, we prove that our controller design
leads to the following update:
AR+1 Av + cwn(- 1b dE + (b)x(E))) - 3dx))
(28)
Ex+1 = Eu + aul- da + (1 k ARdiE KBTAA. + Pa (E)))EEEE)))
(29)
where and 3 are new parameters and when = 1/n it becomes TDC++. The difference with the original TDC+ can be seen in their corresponding O.D.E. forms. The corresponding O.D.E.
for (26) and (27) (original TDC++) can be expressed as: d X
- (1) ー
X
A 31
-A
Ft
X
Meanwhile, the O.D.E. corresponding to (28) and (29) (new TDC++) becomes
Tr.
(C AT - (C + 3T) -KMA
-11
A
We experiment under different of and 7 to examine the behavior of new TDC++. The result shows that in general, smaller x leads to better performance.
xt
The results given in Appendix Section 7.9
8

---

Published as a conference paper at ICLR 2023
Lemma 3.3. Consider the following O.D.E.:
A -n|c + BT)x, -1
(30)
31 ut.
(31)
Suppose that we choose the control impul (AT ky|C + B1)) Am. Assume dl >
and 3 and K satisfies the following condition: 8 KAmiu (A) Amin (C)). Then, the above O.D.E.
has globally asymptotically stable origin, L... (Ac, 24) (0, 0)
The proof is given in Appendix Section
With Lemma 2.1 can prove the convergence of stochastic update with (28) and (29) whose pseudo code is given in Algorithm 5 in Appendix.
Theorem 3.3. Consider Algorithm in Appendix. Under the step-size condition [33] and if satisfies 220] then & 5 as k + do with probability one, where & is the TD fixed point in [
Remark 3.2. We can replace the regularization term with nonlinear terms satisfying certain condi- tions. The details are given Appendix Section 7.6
EXPERIMENTS
We verify the performance and convergence of the proposed BTD under standard benchmarks to evaluate off-po TD-Jearnin algorithms, including Baird environment (Baird 1995). Ran- domWalk (Sutton al. 2009) with different features, and Boyan chain (Boyan 2002 The details about the environments are given in Appendix Section 7.7 From the experiments, we see how BTD behaves under different coefficients E {-0.5, 0. 25, O, 0.25, We measure the Root Mean-Squared Projected Bellman Error (RMSPBE) as the performance metric, and every results are averaged over 100 runs. From Table D the result with 7 0.5 shows the best performance except at Baird, where = O, corresponding to GTD2 performs best. There exist two aspects on the role of 17. First of all, can be thought of parameter that can mitigate the effect of instability coming from matrix A in [9] For example, smaller 1) can stabilize the system. However, trade off, 1) is too small, then the update rate might be too small as well. As a result, the overall convergence can be slower. Furthermore, 1) also controls the effect of - in (13) in the BTD update rules, where -C corresponds to (-17 + 77))z Ag Φ in (17) Note that the role of r7 in the final BTD update rule in [1) shows different perspectives compared to that in (9) In particular, "7 1/2 maximizes the effect of -C in (17) From Table L leads to reasonably good performances in most domains. Another natural choice is multiply v - -C instead of A. However, in such cases, need to introduce another constrain 7) > O, whereas in the current BTD, convergence is guaranteed for all 1 R. Finally, we note that simply multiplying -C by large positive constant does not lead to good results in general. This is because in this case, it may increase variance, and destabilize the algorithm. Overall results are given in Appendix Section 7.8
Table 1: Backstepping TD, step-size = 0.01
1)
-0.5
-0.25
0.25
0.5
Env
Boyan
1.51 + 0.66
1.481 +: 0.656
1.452 + 0.647
1.428 +:2 0.64
1.408 1 0.635
Dependent
0.11 + 0.19
0.097 + 0.163
0.086 = 0.142
0.079 + 0.128
0.076 0.122
Inverted
0.21 + 0.25
0.173 + 0.218
0.151 + 0.193
0.139 + 0.177
0.136 + 0.172
Tabular
0.17 0.28
0.147 0.238
0.133
0.208
0.124
0.191
0.122 + 0.188
Baird
0.1 + 0.64
0.09 + 0.629
0.085 + 0.625
0.087 + 0.628
0.092 0.637
CONCLUSION
In this work, have proposed framework to design off-policy TD-leaming algorithms from control- -entrol-theoretic view. Future research directions would be extending the framework to non-linear function approximation setting.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work was supported by the National Research Foundation under Grant NRF- 202IRIFIA1061 Institute of Information communications Technology Planning Evaluation (IITP) grant funded by the Korea government (MSITY(N0.2022-000044 and the BK21 FOUR from the Ministry Education (Republic of Korea). (Corresponding author: Donghwan Lee.)
REFERENCES
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International Conference on Machine Learning, pp. 507-517. PMLR, 2020.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, (8(2):447-46%5 2000.
Justin A Boyan. Technical update: Least-squares temporal difference learning, 2002.
Xinshi Chen, Shuang Li, Hui Li, Shaohua Jiang, Yuan Qi, and Le Song. Generative adversarial user model for reinforcement learning based recommendation system. In International Conference on Machine Learning. pp. 1052-1061. PMLR, 2019.
Xinyue Chen, Che Wang, Zijian Zhou, and Keith Ross. Randomized ensembled double q-learning: Learning fast without a model. arXiv preprint arXiv:2101.05982 2021.
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 International Con- ference Machine Leurning, pp. 1125-1 134. PMLR, 2018.
Simon Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pp. 1058. PMLR, 2017.
Rafael Fierro and Frank L Lewis. Control of a nonholomic mobile robot: Backstepping kinematics into dynamics. Journal of robotic systems, 14(3):149-113 163, 1997.
Thor Fossen and Jan P Strand. Tutorial on nonlinear backstepping: Applications to ship control. 1999.
Sina Ghiassian, Andrew Patterson, Shivam Garg, Dhawal Gupta, Adam White, and Martha White. Gradient temporal-diffee -ifference learning with regularized corrections. International Conference on Machine Learning. pp. 3524-3534. PMLR, 2020.
Omer Gottesman, Fredrik Johansson, Matthieu Komorowski, Aldo Faisal, David Sontag, Finale Doshi- and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1):16-18) 2019.
Hassan K Khalil. Nonlinear control, volume 406. Pearson New York, 2015.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal Robotics Research, 32(11):1238-177) 2013.
Petar V Kokotovic. The joy of feedback: nonlinear and adaptive. IEEE Control Systems Magazine, 72(3):7-17, 1992.
Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White. Maxmin q-learning: Controlling the estimation bias of q-laarning arXiv preprint arXiv:2002.064877 2020.
Donghwan Lee and Niao He. A unified switching system perspective and ode analysis of q-learning algorithms. arXiv preprint arXiv: 1rXiv:1912.02270) 2019.
10

---

Published as a conference paper at ICLR 2023
Donghwan Lee, Han-Dong Lim, Jihoon Park, and Okyong Choi. Versions of gradient temporal difference learning. arXiv preprint arXiv:2109.0403.. 2021.
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. arXiv preprint arXiv:2006. 14364, 2020.
Sergio Valcarcel Macua, Jianshu Chen, Santiago Zazo, and Ali H Sayed. Distributed policy evalu- ation under multiple behavior strategies. IEEE Transactions on Automatic Control, 60(5): 12600- 1274, 2014.
Tarek Madani and Abdelaziz Benallegue. Backstepping control for a quadrotor helicopter. In 2006 TEEE/RSJ International Conference Intelligent Robots and Systems, pp. 3255-3260. IEEE, 2006.
Hamid Reza Maei. Gradient temporal-differen learning algorithms. 2011.
A Rupam Mahmood, Huizhen Yu, Martha White, and Richard S Sutton. Emphatic temporal- difference learning. arXiv preprint arXiv: 1r07.01507.00 5..00011566. 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 518(7550):529-33 2015.
Doina Precup, Richard S Sutton, and Sanjoy Dasgupta. Off-policy temporal-differenn learning with function approximation. In ICML, pp. 417-424, 2001.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Julian Schritwieser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go. chess and shogi by planning with learned model. Nature, 588(7839):604-663 2020.
Eduardo D Sontag. Mathematical control theory: deterministic finile dimensional systems, vol- ume 6. Springer Science & Business Media, 2013.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent o (n) algorithm for off-policy temporal-difference learning with linear function approximation. Advances in neural information processing systems, 21(21):1609-166 2008.
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods semporal-difference learning with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 993-1000, 2009.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI conference artificial intelligence, volume 30, 2016.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):799-22,, 1992.
11


Reviews:
[{"review_id": "of9O6T81FQ4", "reviewer": "Reviewer_8KPk", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper presents a brand new approach for developing gradient TD methods from canonical control theories. The approach starts with finding an ODE of interest and then uses back-stepping to stabilizing the ODE. The approach succeeded in both recovering existing GTD methods and developing some variants.", "summary_of_the_review": "See above", "strength_and_weaknesses": "Strength: \nThis paper is well written and easy to follow. Using back-stepping to develop stable off-policy RL algorithms appears novel to me and can probably open up a new direction in RL. The authors did a good job in connecting their methods with existing ones. Though I didn't check the proof line by line, I feel confident that the proof should hold.\n\nWeaknesses: \nMy major concern is that the proposed approach feels so hand-crafted. \nThe development of the new algorithm starts from the ODEs in (9) and (10). I absolutely have no idea where the two ODEs come from. It seems that the ODE in (9) comes from the ODE just above (7), which is the ODE from GTD2 updates. But how do the author motivate the introduction of \\eta in (9). Even we can accept that the authors somehow magically introduced this \\eta, motivating (9) with the ODE from GTD still does not make sense to me. **If we do not know GTD beforehand, is there still a reasonable way to write down the ODEs in (9) and (10)?** If the authors cannot provide an affirmative and convincing answer, I do not think the proposed framework of using backing stepping is significant -- it can only start from existing solutions and cannot start from the problem", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XY2DdVA01Gy", "reviewer": "Reviewer_kJdF", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper provides some temporal-difference (TD) learning algorithms based on the celebrated backstepping technique from control theory for addressing a family of nonlinear systems. The proposed TD algorithms are claimed to be stable and convergent in contrast with the divergent behavior of standard TD algorithms. Several existing TD generalizations have been shown as special cases of the proposed backstepping TD algorithm.    ", "summary_of_the_review": "Some detailed comments are listed as follows.\n1. In the Abstract, please include theoretical and numerical convergence comparison with existing TD algorithms.\n2. How Eq. (5) is obtained?\n3. The paper focuses only on second-order linear systems. When the order of the system increases, the backstepping technique will have a complexity explosion problem pertaining to computing the derivatives of the virtual control. So would this have an impact on the computational complexity of the proposed algorithm?\n4. The paper contains quite some grammar issues. ", "strength_and_weaknesses": "The paper draws ideas from control theory and presents stable and convergent backstepping TD algorithm for off-policy learning. The idea is interesting and seems effective. \n\nStrengths:\n+ Interesting combinations of backstepping control with model-free TD learning\n+ Well-established analysis and stability results\n+ General enough to accommodate existing TD modifications\n\nWeaknesses:\n- Backstepping design and theory is suited for nonlinear control systems, but only linear BTD algorithms are discussed here\n- Theoretic analysis (e.g., asymptotic/non-asymptotic convergence) of BTD is lacking\n- Numerical convergence comparison against existing TD variants not provided\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2ekKZXuohu", "reviewer": "Reviewer_t2qM", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper studies TD-learning for a non-linear control theory perspective. Motivated by the idea of designing stabilizing control policies for non-linear ODE systems based on the control Lyapunov function method, the paper studies TD-learning as a special case. The paper designs a novel TD-learning algorithm that is stable under linear function approximation in the off-policy learning setting, and provides extensions to GTD2 and TDC. The paper is mostly theoretical and uses a few experiments to illustrate properties of the new algorithm.", "summary_of_the_review": "A few questions and comments.\n\n=== **Notation** ===\n\nIn Eqn 4, I suggest the author used notation other than $\\lambda_t$ for the state variable. Maybe $\\lambda_t$ is a standard notation in the control literature, since much of the audience has RL background, it might be better to use something like $y_t$ as the state variable, which also distinguishes from the controllable state $x_t$.\n\nThe notation $x_s(\\lambda_t)$ is confusing. From what I understand, $x_s(\\cdot)$ is itself a function and the index $s$ does not stand for anything. Maybe it is better to replace $x_s$ by something like $\\tilde{x}$ altogether because it can be easy for certain readers to relate $s$ with the time index $t$, leading to confusions.\n\n=== **TD-learning** ===\n\nI think a factor of $\\phi_k$ is missing from the TD-learning update in Sec 2.5, TD-learning should update as \n$$e_{k+1}=e_k+\\alpha_k\\rho_k\\delta_k\\phi_k$$\nwhere $\\phi_k$ is necessary to match the dimension against $e_k\\in\\mathbb{R}^n$.\n\nIn Eqn 5, $X$ should be $\\Phi$.\n\n=== **Motivation for Sec 2.6** ===\n\nPresentation-wise, as an example, I think it would be good for the paper to provide more motivations for the behavior of GTD, GTD2 and TDC. These algorithms have been designed to improve stability of vanilla TD-learning -- can we spot from the vanilla TD-learning's update rule that it is unstable, can we say something about the non-PD of the $A$ matrix defined in Eqn 6, can we show some plots displaying the instability? This provides motivations for the class of stable TD-learning algorithms that provide motivation for this work.\n\nI also hope the authors can provide more elaborations on the background in Sec 2.6, where they say \"the idea behind these algos is to minimize the mean-square error of MSPBE\". I don't immediate see how the idea of minimizing mean-square error of MSPBE is reflected in Eqn 7-8 or equations right above them. Maybe it is good to give a quick explanation here. It is also good to explain why minimizing MSPBE helps improve stability, which is not immediately clear.\n\n=== **Sec 3.1** ===\n\nIt is a bit confusing where Eqn 9-10 come from, somehow I feel they are related to the ODE systems on page 9 right above Eqn 7, but no clear explanation is given. Eqn 9-10 defer from the ODE system right above Eqn 7 by a factor of $-\\eta A\\lambda_t$, whose motivation is not clear to me. The authors should provide a more clear motivation as to how one arrives at such an ODE system to start with and why adding the extra term $-\\eta A\\lambda_t$.\n\n=== **BTD** ===\n\nBTD in Eqn 14-15 are the main contributions of the paper. Though it is good that the authors have arrived at a novel TD-learning update rule that is stable in the off-policy case, overall it feels like it is not completely clear how one arrives at the new update rule in an \"easy-to-understand\" way. This can be better strengthened and clarified by providing more motivations for each step of the derivation, such as the origin of the ODEs in Eqn 9-10.\n\nMeanwhile, given Eqn 16-17, it is better if the authors can provide further motivations and intuitions for the updates. Decomposing the terms in the ODE updates, can we deliver interpretation intuitions for each term, do they correspond to certain types of modified TD errors? Since the algorithm is single time-scale, it will be interesting to understand exactly what mechanism leads to the stability of the new update rule, beyond the set of math that arrives at the conclusion that the update is stable.\n\n=== **$\\eta$** ===\n\nThus far to me, the role of $\\eta$ is mysterious and not well justified in the paper. In Eqn 9-10, the extra factor introduced $\\eta$ into the ODE system. Throughout, it is not clear what role $\\eta$ plays in stabilizing the ODE system. It seems that $\\eta=0$ recovers GTD2, but what is the intuitive explanation for having $\\eta>0$? Is it just a numerical trick, does it correspond to certain interpretable regularization? \n\n=== **Experiments** ===\n\nExperiment results are probably too simplistic in the main paper. I'd appreciate a table or plots of comparison of BTD vs. GTD2, TDC and vanilla linear TD, emphatic TD on tabular domains listed in Table 1.\n\nSince the role of $\\eta$ is not clear in the BTD update and is poorly motivated, it is not clear what it means when $\\eta>0$ works more poorly than $\\eta=0$ (GTD2) on the Baird example. Can we characterize when to use $\\eta>0$ and when to set $\\eta=0$ in practice, does the theory provide any useful indications on that?\n\n=== **Minor comments** ===\n\nThe first sentence below Sec 3.3 does not read well.", "strength_and_weaknesses": "=== Strength ===\n\nThe paper seems to provide a novel and unifying perspective on viewing various TD-learning algorithms under linear function approximations in the off-policy learning setting. Prior work such as GTD and TDC, which have been motivated to bypass the instability of vanilla TD-learning, can be understood as special instances under the new framework proposed in this paper. The paper also suggests a new stable TD-learning algorithm, which is quite interesting in its own right.\n\n=== Weakness ===\n\nOverall, the intuition of the new algorithm is not very clear, despite the fact that it has been derived based on control Lyapunov function and leads to stable learning, and the fact that it can be implemented as a single time scale algorithm. The paper can be greatly improved if further intuitions and explanations of the new algorithm can be provided, beyond control-theoretic mathematical aspect of the algorithm. The experiment section of the paper is also quite simple, making it more difficult to assess the advantage of the new algorithm.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster