Finite-Time Analysis of Adaptive Temporal Difference Learning with Deep Neural Networks
Authors: Tao Sun
Dongsheng Li
Bao Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Temporal Difference Learning
Adaptivity
DNN Approximation
MDP
Finite-Time Analysis

Abstract: Temporal difference (TD) learning with function approximations (linear functions or neural networks) has achieved remarkable empirical success, giving impetus to the development of finite-time analysis. As an accelerated version of TD, the adaptive TD has been proposed and proved to enjoy finite-time convergence under the linear function approximation. Existing numerical results have demonstrated the superiority of adaptive algorithms to vanilla ones. Nevertheless, the performance guarantee of adaptive TD with neural network approximation remains widely unknown. This paper establishes the finite-time analysis for the adaptive TD with multi-layer ReLU network approximation whose samples are generated from a Markov decision process. Our established theory shows that if the width of the deep neural network is large enough, the adaptive TD using neural network approximation can find the (optimal) value function with high probabilities under the same iteration complexity as TD in general cases. Furthermore, we show that the adaptive TD using neural network approximation, with the same width and searching area, can achieve theoretical acceleration when the stochastic semi-gradients decay fast.

Finite-Time Analysis of Adaptive Temporal Difference Learning with Deep Neural Networks"
Tao Sun
Dongsheng Li³
College of Computer
College of Computer National University of Defense Technology Changsha, Hunan 410073, China
National University of Defense Technology Changsha, Hunan 410073, China mudtsuntao0163. com
dsl i @uudet edu.. cn
Bao Wang
Scientific Computing & Imaging Institute University of Utah, USA
@atraaoj@@mai...comm com
Abstract
Temporal difference (TD) learning with function approximations (linear functions or neural networks) has achieved remarkable empirical success, giving impetus the development of finite-time time analysis. As an accelerated version of TD, the adaptive TD has been proposed and proved to enjoy finite-time convergence under the linear function approximation. Existing numerical results have demonstrated the superiority of adaptive algorithms to vanilla ones. Nevertheless, the performance guarantce of adaptive TD with neural network approximation remains widely unknown. This paper establishes the finite-time analysis for the adaptive TD with multi-layer ReLU networks approximation whose samples are generated from Markov decision process. Our established theory shows that if the width of the deep neural network is large enough, the adaptive TD using neural network approximation find the (optimal) value function with high probabilities under the same iteration complexity as TD in general cases. Furthermore, we show that the adaptive TD using neural network approximation, with the same width and searching area, can achieve theoretical acceleration when the stochastic semi- gradients decay fast.
Introduction
Temporal difference (TD) learning is a popular and successful iterative algorithm the area of rein- forcement learning (RL) evaluate given policy [47 [7]5 often employed for critic part evaluation various RL algorithms (28]
Classical TD algorithm adopts the tabular representation for value function, which stores value estimates a per-state basis. In large-scale scenarios, the tabular approach becomes intractable due to a large number of states. Thus, the function approximation techniques have been integrated with TD for better scalability and efficiency 4 50 36 57). The
function approximation techniques have achieved remarkable empirical success and are theoretically justifiable when the linear function approximation is used 23 As special function approximation approach, deep neural networks (DNNs) have also been integrated with TD
38 37 33
achieving
"This work is sponsored in part by National Key R&D Program of China (2021 YFB03011))) Hunan Provincial Natural Science Foundation of China (2022J110065), and the National Science Foundation China (62025508 and 61 6160000)).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

phenomenal performance in several applications. However, from the theoretical perspective, estab- lishing theoretical convergence guarantees for training DNNs is much more complicated than that for the linear approximation algorithms, which is still widely open. Some convergence results of TD with DNN approximations have been proved by the authors of 21 53], under some extra assumptions and restrictions. The adaptive methods for DQN have been proposed in [37 22], inspired by the adaptive stochastic algorithms to accelerate TD. The numerical results show that the adaptive versions of TD can outperform the vanilla ones in many tasks.
Mathematically, the (projected) TD (with function approximation) can be described as
g++1 Projv
7g
(1)
where V is the constrained set, and Projy denotes the projection onto V. 0 is the iterate, and g is the stochastic semi mani-gradient" ? gradient descent (SGD), it is much more complicated due to the Markov noise, even in the linear function approximation case. Motivated by the adaptive SGD [20 27 the adaptive TD with linear function approximation is proposed in [52 46). The main difference between the adaptive TD and the standard TD lies in the use of adaptive stepsize and momentum. This paper considers the neural adaptive TD. In the ktth iteration of neural adaptive TD, performs
Although the update scheme of TD looks similar to the stochastic
m fmm h- + (1 3)g*
y = k-1 + |g
@++1 = Projv (0t -mm²/(=*)8)
where 3 >> 0 is the momentum parameter, and 1) > The points m² and e* contain past information. The numerical results have demonstrated the advantage of adaptive TD over vanilla TD. The adaptive TD is proved to be convergent with linear function approximation, but the convergence remains unclear when the neural network approximation is used.
This paper proves that the adaptive TD with neural network approximation converges when the width of ReLU network is sufficiently large. Moreover, we prove that adaptive TD is faster than TD with the ReLU DNN approximation.
1.1 Related Works
Analysis and the recent development of TD. Leveraging the stochastic approximation techniques, the authors in (25) establish the first convergence results for TD. The limiting convergence of TD with linear function approximation is proved in (50) with the perspective of the dynamics. Since the seminal work of (50), many works have been using the ODE-based method study the asymptotic convergence of TD since TD update does not follow the (stochastic) gradient direction of any objective function 66, [9]. Some variants of TD have been proposed in [14] with asymptotic convergence guarantees. The first asympooti analysis for the gradient TD, a variant of the TD, has been studied in (34). Finite-time analysis of TD with independent and identically distributed (i.i.d.)
observation assumption has been presented in [3]. The Markov sampling convergence analysis is proved in subsequent paper S In concurrent line of research, TD has been studied from the perspective of stochastic linear systems [29] The tnite-time analysis for Markov sampling stochastic linear system has been developed by the authors of [43 24). The finite-time analysis of multi-agent
TD is proved in (15. A unified analysis for a class of TD learning algorithms with Markov jump is established 224 Based on Nesterov's acceleration method, class accelerated TD is developed and analyzed in [66. From the algorithmic viewpoint, the adaptive TD has been recently proposed in [46]] 52 to accelerate TD, inspired by the adaptive SGD. In [44), the authors present the finite-time convergence results of decentralized TD with linear approximations.
TD with deep learning. In contrast the tremendous empirical success of the deep Q-networks (DQNs), the theory is still relatively weak; until recently, only a handful of papers have studied the theoretical results of TD using neural network approximation. In [2]], the authors prove the conver- gence rates of fitting Q-iteration with sparse multi-layer ReLU network under i.i.d. observations.
We call it as semi coni-gradient because its stationary expectation is not the gradient of any fixed objective function.

---

The convergence of TD with two-layer neural network approximation is provided by [7 with i.i.d assumption on the samples. The TD-based algorithm with mullti-layer ReLU networks under Markov samples is studied in [3.. The theory of the TD with multi-layer ReLU U network relies heavily on
the existing results about overparameterized deep networks 266 12 19
3
1.2 Difference Between our Work and Existing Works, and Technical Challenges
Existing related works contain two categories: adaptive TD with linear approximations and neural TD. However, our work significantly different from these related works. 1) In contrast to adaptive consider the neural network approximation, in which case
TD with linear approximations, do not have nice properties that linear approximation enjoys, and we have to consider the neural tangent kernel (NTK) regime and develop new analysis leveraging the semi-Lipschin continuity property. 2) Compared to neural TD, we use the adaptive stepsize and momentum, which has never been considered in neural TD.
1.3 Our Contributions
In this paper, we consider the adaptive TD with a multi-layer ReL.U network approximation under the Markov observations. In contrast to the existing works [21 7 53], we study the adaptive variant of TD. The scheme of the algorithm is much more complicated, raising tremendous challenges in theoretical analysis. Our main theoretical contributions are summarized below:
We extend the analysis of adaptive TD with linear function approximation 46 52 to multi-layer neural network approximation under Markovian samplings. The theoretical results show that adaptive TD still works for the neural network approximation, even with deep neural networks.
We establish the finite-time analyses of adaptive TD with multi-layer ReLU network approxima- tion under Markov observations. In particular, we show that the adaptive algorithms guarantee convergence when the neural network is sufficiently wide, and adaptive TD with neural network approximation converges to projected optimal action-value function. The technique required to connect Adam-type algorithms and neural TD is non-trivial since they belong to two very different research areas. To this end, we develop a new technique that uses expectation with a fixed delay, which is different from the coupling technique used by the authors of [ 53).
We prove that the speed of the adaptive TD can be faster than the vanilla ones with multi-layer ReLU network approximation. Specifically, we show that the adaptive ones use fewer iterations to reach the same desired error with the same network widths and searching areas. Our theoretical results first explained why Adam-type algorithms perform better than TD in DQN, which has been observed in practice.
2 Preliminaries
We introduce the notation, some basic concepts, and properties of TD in this section.
Notation: We use E[-] denote the expectation with respect the underlying probability space without stochasticity of the initial point, and we use || || to denote the Frobenius norm, a(-) denotes the ReLU activation function. We use Φ x A > Rd to denote the feature map. Given a closed set V. Projv(xx (x) represents the projection of the vector x onto V. The initial point is defined as @init B(0, w) denotes the ball centred at with radius w. We use d₂ = Ö(bz) to hide the logarithmic factor of by still with the same order. We write aę O(b)) if ag O(b)) and by O(ax), ). and we use a @(bb) hide the logarithmic factor. We denote x" as the sub-algebra that generated by 8 0¹ ....., 0h, where 8 is the value in the keth iteration.
2.1 Markoy Decision Process
For the sake of presentation, we consider the finite state space Consider a Markov decision process (MDP) described as a tuple (S, P. P,R, R),,, where S denotes the state space, A denotes the action
Our results can be extended to infinite state cases, and consider the finite state for simplicity.

---

space, Pa represents the transition matrix associated with action a, and 0 < < is the discount factor. In this case, let (s denote the transition probability from state to state under the action a. The corresponding transition reward is r(s, a). We consider the stochastic policy : + (AA that specifies probability density all actions given the current state s. T a) denotes the probability to choose action when the current state is s, and Lae x(s, 1. We consider the on policy setting, where both target and behavior policies are т. The corresponding action-value function Qa (s, a) S x A + R is defined
Qu (s. E Σ
0.00 = =00
and the associated value function V S + IR is defined as
V+(s) = Ex Σ t=0
(rr(se =s Σ I a(s,a)
It is evident that the restriction on discount 0 < << < can guarantee the boundedness of Qx a).
The Markovian property of MDP yields the following celebrated Bellman equation
T=Q = QT:
(3)
where the Bellman operator Tx on a value function Q can be represented as
(T=Q=)(s,a) =() +
Σ Pa(ss(s)V=()))
''ES
= a( + Σ Pa(s'(s) Σ T(s', ((((5))
''ES
where E S,aa a A. Directly solving needs [[55) computational cost, which is very expensive since |A||A| usually very large. Thus, people turn to use a linear or non-linear approxi- mation as Q₂ R (0) : RD + SIIAA,, where 0 E R and D < [S][A]. this way, the dimension be significantly reduced, and can get approximate solution very efficiently.
We collect necessary assumptions for MDP below.
The transition rewards are uniformly bounded by 1, that is, |r(s, 1,8 E.SEE. E S, E A. For any E A. it holds u(s) lim,, P(st s|30 s', A0 a') 0. There exist constants 0 S < 1 and R > 0 such that
Assumption
I(ss s|50 s a') mss) s kp'.
SES
The boundedness of (r(s, (r(s,,'))e.e s'))...es comes from the finiteness of S. In Assumption I the uniform boundedness assumption can replaced by non-uniform boundedness the finite state case. this paper, it is used for simplicity. The rest part of Assumption i standard for the Markovian property. well-known that irreducible and aperiodic Markov chains can always follow Assumption 30]. For Assumption I the time that (st, 02)22 needed for its current state distribution to match the stationary one with error in total variation distance is O(log / /log f)) Thus, the constant represents the speed of the process accessing the stationary distribution. In finite-time cases, is easy to prove that is the second largest eigenvalue P. We can see that the smaller is, the faster the process will converge to the stationary states.
2.2 Neural Temporal Difference Learning
Although we can get Q by solving the Bellman equation induced by the given policy æ, in practice S may contain very large number of different states and actions, and it is hard to solve the Bellman equation directly. Thus, alternative methods have been proposed, including leveraging the linear [48] or non-linear approximations (e.g., kernel methods and neural networks (38). This paper is devoted to the study of the approximation using L-hidden-layed ReLU neural network defined as
f(0:x) ( L------oW--p

---

where x E R is the imput data, W1 E R WL Rixm and W. E Rmxm for I = 2...., and 0 [W.... W....,, Wr] denotes all the weights. In neural TD, use the following approximation
Qr f(0; ((s www
LowWLolW WWWWooWWo.. L-1 (Wio(s, a))...).
where 0 E (R( +mmmmm +md+m the parameter vector, and m usually set such that (I. 2)m2 md + is smaller than |||| to reduce the difficulties caused by the high dimensionality. It is worth mentioning that factor / /m is multiplied to guarantee the output to be meaningful: [Lemma 4.4, [. is proved that [(;;30 x) = (1) as m is large and randomly initialized. we remove mm, the function value is then the order Õ(1/ /m), which tends to as m is large. We stress that such is standard in ReLU network theory.
Assumption For any state-action pair (s,a) E S A. we assume the feature vector is uniformly bounded such that [ a)ll
simple normalization can make Assumption 2hold. This assumption is used to simplify coefficients in the subsequent proofs.
Next, present the scheme of neural temporal difference learning. With (sk, ag)xz0 be- ing a trajectory sampled from π and a hyper-parameter v > 0, the neural TD updates with g + g(0"; 8k: ake Sk+1, ax+1) in (T) where the stochastic semi-gradient is defined as
g(O; Sk: Ok, Sk+1, a++1) Vef(0; ((sk; a+)
(4)
x [s(0; ((8k, Qx)) - r(sk; ax) - 75(0; ((=0::((+++1 (x+1))]
The projection in scheme 2 is used to ensure the boundedness of g and simplify the convergence analysis. In the deep neural network approximation, the searching area V chosen as a ball around the initialization ginit = [Winil Willl] for the ease of analysis. The detailed expression of the set V is given as follows:
0 WI,.. W Wini S w]
(5)
where 1 < L. It is assumed that ginit is chosen randomly from the Gaussian distribution, i.e., Winit is drawn from (00 1/m) with I...., m.
The collection of all local linearization of f(0; ((s, a)) the initial point iimit is defined
Fv.m := (f( (( a)) + (Vof(0 (ss. a)), l : V}.
the function ff is linear, i.c.,
f(0: ((s, a)) (0, o(s a)),
(6)
we can see that Fv.m = 100 (s a)) Vj. The approximate stationary point of neural TD associated with Fy.m defined as follows.
Definition ((7) point is said to be the approximate stationary point if
(h(0"), 0 0-) 2 0, 40 EV,
where
h(0) = A (
and the temporal difference error Å is defined as
i A(s, d':0) f(0: 6(s a)) - r(s, 7f(0:
(8)
and (() Jv.m.
The convergence of neural TD is dependent on 0* and so is our result. In [7], it has been proved that such definition well-defined; the approximate stationary point exists, minimizing the mean squared projected Bellman error (MSPBE). Such fact is more straightforward if the function is linear: the approximate stationary point of TD is identical to the unique solution to the projected Bellman equation [50].
5

---

Algorithm Neural Adaptive Temporal Difference
Require:
Parameters: % 33, L, m,
Initialization: g" = 0, m = 0, v = O. With (V,0, with / 1,..., L, V is set as For k 1,2....
1 I.samlle the trajectory 80, 40, 81, A1,... from π
c.alcullaee g = g(0"; 8k, Ok: 8k+1, 0k+1) as
3. .pddate the parameter 0* as
End for
2.3 Neural Adaptive Temporal Difference Learning
This paper considers the neural adaptive TD. In the kth iteration of neural adaptive TD, we sample g g(0"; Sk; Ok: $k+1; a*+1) in (2 with stochastic semi-gradient The set V is chosen as (5)
with @mm also being sampled from the Gaussian distribution.
2.4 Some Useful Properties
For neural adaptive TD, several bounds and properties are presented in the following lemma (c.f.
Lemma 6.1, [53]; Lemma 4.4, 8
Lemma Assume that (0*) ISSSS E B(0", w), given any < < 1 and K E zt, m. w and L satisfying
m 2 max log m
4 log
m wo Lam3/4 S S [loggm))
C
C2
then it holds
(10)
and
|5(0"; C. CLy/oo
(11)
Denote that h² = ((00)) (8 is given by 8 it follows
lgg - C3(2 2/3 vm log m log K/5) C/ log m + Czw L.m,
h01l
(12)
where gh is the stochastic semi-gradient neural adaptive TD, and
lg - (2 + mm
(13)
holds with probability at least 1 - 25 31 2xp(-Comu2233 2/3T.) over the randomness of the initial point, where {C₁ > O) and C > are universal constants.
Lemma Thas been proved by [Lemma 6.1, [53] and [Lemmna 4.4, [8]]. The bounds 10 and
are only dependent on the structure of the neural networks. Our theory is built on Lemmal I Without the ReLU activation, Lemma T cannot be guaranteed to hold, and thus we only consider deep ReLU networks in this paper. Indeed, due to the property deep ReLU networks, there has been line of theoretical research deep ReLU networks, high probabilities, * < (2 2C log( K/5)k when Ie < K. But this is the worst-case bound and mog(
e.g. [54. 18 40 9
55 133. From Lemma I with
may not always be achievable. From 44, we can see that g keeps the sparsity of V (ef(0"; 0($k, ax) because
[f(o;; ((3,, ax)) - r(Su, an) - -0 0(S1+1, 4x+1)) E IR.
Thus, the stochastic semi-gradien g can be very sparse, based on which the following bound is proposed.
Condition 1 In neural adaptive temporal difference learning, the following bound holds
J < Colmlog((//8)))) 0<a51, 15k K.
(14)

---

finite-time convergence
lower bound of Σ B((m², " 0" 0*)) (
upper bound of Σx= 1= E[[[m" 113//11// /12//**)
Lemma 5
Lemma 6
Lemma 3
Figure 1: The roadmap of the proof.
We can see that directly holds for (14) due the bound (3): while < a 1 indicates the stochastic semi-ge comi-gradients decay fast. In applications, the sparse gradients can always obey such condition. We stress that such assumption is standard in the analysis the Adam-type algorithms; see, e.g., references
32
20 39
35 45
the neural approximation case. As mentioned above, the convergence analysis the approximate stationary point 0" One core part of our proofs is investigating h versus the iteration. Due to the Markovian observation, 8k: (gg. 5k+1, aK+1 may miss visiting several states in a single sampling, i... choosing some states and actions with probability O. That indicates 15]h"] may be biased expectation of h. To get controlled difference bound, we consider E(h(O" -" ix) and h(O h(@*-T), where
Now,
h T)= = Á(Sk, ak 5k+1, 0++1: 0 Vof : a)))).)))).
Although with biased samples, the Markov property means (( = s|sk-T = $ ax-T = a') is sufficiently close to pls) when T is large. Such technique then yields following lemma.
Lemma Assume (0* Joskek is generated by neural adaptive TD, and condition 9 holds. Given an integer 1 < T < K, as K T, we have
|B(h( T) 1x*) - h(0t-=)) s $2 m log J D
with probability at least 1 28- 3L e1feexpp(CCii (ppp-Comw22/31 over the randonness of the initial point.
The factor p² in the upper bound Lemma 2 comes from the Markovian noise. The lemma tells that when 7 is large enough, the difference between Eh (h and h(@*-T) will be very small.
The lower bound directly holds based on the definitions above.
Lemma For VO E V, it follows that
(h(0), 0 2 20) -)2
(15)
3
Main Results
This section contains the finite-time analysis of adaptive TD using deep neural network approxi- mations. The descriptions of convergence results are dependent on the notion of the approximate stationary point 0*
3.1 Roadmap
first provide a high level explanation of the proofs and how the technical lemmas work in the proofs. Our proofs begin with traditional idea of algorithmic convergence analysis, i.e., bounding the gap (1 0* 0f1l2))20 versus the iteration. It is easy to have the following estimate
(m 0" -00)/(0²} < 1
0²1 - 1 - 1²+1112 + 17 m k /2//0
7

---

Summing this inequality from & = 1 to K and taking expectation, we are led to
2n B( ; - -0)//(²)))) B 0'112 Σ RC [
(16)
Notice that (66 is very similar to the recursion of the well-known SGD. Recalling the finite-imme convergence analysis of SGD, we then get the big picture for the proof of our algorithms, which contains two major steps and can be presented by Figure
Step 1. The first step is quite straightforward, i.e., bounding the summation Σ k== E[I[m 1 with high probability. This step is proved by Lemma
K
4 in the supplementary materials.
However, it is much more complicated than the first step. To this end, we need to exploit the relation between E(m", 0- 000000~((00000000 /0*/((")))))) & and ((h(6") -0= //(//(())) (proved by Lemma 6 the supplementary materials). Nevertheless, cannot directly get Lemma that connects E5 0" (100)))/v with E 0 // (proved by Lemma 5 in the supplementary materials). Further with the connection between E(h(O"), 0 00)) and B(f(0": 8, a) f(0"; a))))² (Lemma 3 we then prove the lower bound.
Step 2. The second step is to establish lower bound of Σ 2k=1 [[(m"*, 0" -0%) (((mm",0'00*)((())))))))) /(=*))).
have to develop technical lemma
3.2 Finite-Time Time Analysis of Neural Adaptive TD
Now, prepared to present the convergence of neural adaptive TD.
Theorem Suppose (0²) is generated by neural adaptive TD under the Markovian observation, and condition ( holds, and Assumptions
and condition 14) hold. Given the integer E Z+,
> 0, vo
w 0,0 < 1, for K 2 2 2 T, we have
:( a)))² (m a. ISkSK
min
K1-a/2
K1-a/2
(17)
ca a, K)p=K² K + ca(m, w, K)
with probability at least - 28 2I expl-CCop m/3 over the randomness of the initial point, where
a.m.n.a.. T) = 0(mm + m log K),
c2(m, 11 0, T. K) (wm ميد log m 1t WT WW/m//(K T)),
(18)
cs(m,w, K) ([um -0 log K),
calm,w, K) = ([w Vm 3 Vm + w w'm] log K),
and their details are given by 29 in supplementary materials.
If we set the radius
Omm 1/2) and T In(mK)
and 17
1/2 with 18 the right-hand
In
side of (1 is in the order of
1/(KL-o/2 1/ 1/K11-00/2
1 1 m
Thus, with high probability to achieve the e-accuracy for minlsesk E, (f(0" 8, (,0)) we need that
m = 6(1/c), 1/(K1-a/2 Ō(c).
Thus, we get the worst-case iteration complexity of K as follows
1
(19)
In I- 1))
'Such choice of the radius in neural TD is also used in (53

---

The worse case is a 1. in which case we get the complexity as ((1/22). Note that even for SGD without strong convexity, the optimal complexity ((1/e²) [Theorem [T]]]. Thus, our result is nearly optimal (just with an additional logarithmic factor that barely hurting the rate). We can see that when 0 v a < 1, the worst iteration complexity of K is smaller than (n
when
< 1//[ll( ),), which indicates a faster speed than the neural TD. Due to that is the desired error and thus can be very small, the acceleration always happens for a small Note that 1 directly holds with any extra assumption. In this case, the iteration complexity of the adaptive neural TD matches existing neural TD [53] in the case of DNN approximation.
worth mentioning that compared with the convergence rate of neural TD with ReLU deep networks, we used the same searching radius and network width as presented by the authors of [53]. In applications. the sparse stochastic semi-gradiene always yield the fast decaying condition. In other words, with sparse stochastic semi-gradient, the neural adaptive TD also accelerates the vanilla TD even in the ReLU network approximation case. Such a phenomenon resonates with the existing acceleration results of adaptive methods for stochastic optimization: "for sparse data, the adaptive methods are likely to perform better than non-adaptive methods" [20].
The scheme of neural TD uses a projection to the set V such that all iterates are constrained in small neighborhood around the initialization (also called NTK regime). Such a procedure is to use the property of deep ReLU networks 7 [3). Thus, the searching radius is small, which is reasonable because in DNN training, the parameters usually only change in a very small range in the overparameterized regime.
Proposition! 1 Assume that conditions of Theorem 7 hold, and Condition 7 holds with O S a < 1, 1 (mm m $ m 6(1/c"), < 1/[m(( the neural adaptive TD enjoys a faster finite-time convergence rate than the neural TD in the ReLU DNN approximation of function values with probability at least 1 28- 3L exp(-Comw"1)) over the randomness of the initial point.
In the following, we present proposition that characterizes the difference between our established results and the optimal vetiun-value function.
Proposition 2 Assume conditions of Proposition 7 hold, with probability at least 25 3L2² Sap(-Cemw213 over the randomness of the initial point, we have
min ISKS
E(F(0" 8, a) -3a))QQ(3. as,
= σ [II m (Q" - QQ*,sa))
1-7
where II (Q, is projection of (s, to the linear function family Fy. that is, 11 (Q, = f(Oini Φ(s a)) + (Vef(Omit Ø(s, a)), 01 -ginity with 0¹ E
arg argminoev {|| f11m ((s. a)) (pss))((ssss))))
Φ(s, 0 - ginit) Q* a |
Proposition 2 indicates that the algorithm can find the optimal action-value function Q' (s, a) provided that the function family Fy.m contains Q* (2ss a).
4 Conclusions
This paper studies the finite-time convergence analyses of temporal difference learning with adaptive learning rates and momentum approximated by deep ReLU neural networks using the Markovian samplings. Our established theoretical results show that the neural adaptive temporal difference learning is convergent when the neural network is sufficiently wide. Our work shows convergence results and establishes the theoretical advantages of the adaptive algorithms for neural network approximation cases, i.e., adaptive schemes achieve better rates than neural temporal difference learning when the stochastic remi-gradients decay fast. There are numerous avenues for future works, including 1) Can we extend the multiple ReLU active functions to others, e.g., sigmoid or more general functions? 2) Can we establish the finite-time convergence of adaptive temporal difference

---

learning with other kinds of neural network approximation, e.g.. recurrent neural networks and graph neural networks? 3) Can we get a relaxed bound for the radius of the searching area?
References
[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. In Advances in neural information processing systems, pages 6155-6166, 2019.
[2] Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-paramettrriztionn /CML, 2019.
[3] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. ICML, 2019.
[4] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning, pages 30-37. 1995.
[5] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Operations Research, 69(3):950-973, 2021.
[6] Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000.
[7] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning converges to global optima. In Advances in Neural Information Processing Systems, pages 11312-11322, 2019.
[8] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pages 18835-10845, 2019.
[9] Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning over-parameterized deep relu networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3349-3356, 2020.
[10] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. ICLR, 2018.
[11] Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianhao Yang. Universal stagewise learning for non-convex problems with convergence on averaged solutions. In International Conference on Learning Representations, 2018.
[12] Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in neural information processing systems, pages 1036-3046, 2018.
[13] Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for TD(0) with function approximation. In Thirty-Secont AAAI Conference on Artificial Intelligence, 2018.
[14] Adithya Devraj and Sean Meyn. Zap Q-leariing In Advances in Neural Information Processing Systems, pages 2235-2244, Long Beach, CA, Dec. 2017.
[15] Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Convergence rates of distributed TD(0) with linear function approximation for multi-agent reinforcement learning, arXiv preprint 10Xiv:190..07393 2019.
[16] Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Convergence rates of accelerated markov gradient descent with applications in reinforcement learning. arXiv preprint arXiv:200.00887, 2020.
10

---

[17] Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pages 2658-2660 PMLR, 2020.
[18] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.
[19] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. ICML, 2018.
[20] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Reseurch, 12(Jul):221-21133 201
[21] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pages 186-489. PMLR, 2020.
[22] William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In International Conference Machine Learning, pages 3061-3071. PMLR, 2020.
[23] Lei Ying Harsh Gupta, R. Srikant. Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning. In Advances in Neural Information Processing Systems, pages 4715, Vancouver, Canada, November 2019.
[24] Bin Hu and Usman Syed. Characterizing the exact behaviors of temporal difference learning algorithms using markov jump linear system theory. In Advances in Neural Information Processing Systems, pages 8477-8488, 2019.
[25] Tommi Jaakkola, Michael Jordan, and Satinder P Singh. Convergence of stochastic iterative dynamic programming algorithms. In Advances in neural information processing systems, pages 703-710, 1994.
[26] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 1571- 2018.
[27] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2014.
[28] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, pages 1008-1014, 2000.
[29] Chandrashekar Lakshminnraaanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pages 1347-1355, 2018.
[30] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[31] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. AISTATS, 2018.
[32] Luofeng Liao, Li Shen, Jia Duan, Mladen Kolar, and Dacheng Tao. Local adagrad-type algorithm for stochastic convex-concave minimax problems. arXiv preprint arXiv: 106. 10022, 2021.
[33] Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver. and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 1509.02971, 1, 2015.
[34] Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. In Proc. Conf. Uncertainty in Artificial Intelligence, pages 504-513, Amsterdam, Netherlands, 2015.

---

[35] Mingrui Liu, Youssef Mrouch, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. In International Conference on Learning Representations, 2019.
[36] Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning, pages 664-671, 2008.
[37] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukeuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928-1937, 2016.
[38] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-333, 2015.
[39] Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. ICLR, 2019.
[40] Johannes Schmidt-Hieber. Nonparametrie regression using deep neural networks with relu activation function. The Annaly of Statistics, 48(4):1875-1897, 2020.
[41] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pages 1889-1897, 2015.
[42] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 3xXiv:707.00644/ 2017.
[43] Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. COLT, 2019.
[44] Jun Sun, Gang Wang. Georgios B Giannakis, Qinmin Yang. and Zaiyue Yang. Finite-time analysis of decentralized temporal-different learning with linear function approximation. In International Conference Artificial Intelligence and Statistics, pages 4485 4495. PMLR, 2020.
[45] Tao Sun, Linbo Qiao, Qing Liao, and Dongsheng Li. Novel convergence results of adaptive stochastic gradient descents. IEEE Transactions on Image Processing, 30: 1044-1065,, 2021.
[46] Tao Sun, Han Shen, Tianyi Chen, and Dongsheng Li. Adaptive temporal difference learning with linear function approximation. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 2021.
[47] Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3(1):9-44, 1988.
[48] Richard S Sutton, Andrew G Barto, al. Introduction to reinforcement learning, volume 2. MIT press Cambridge, 1998.
[49] Richard S Sutton, Hamid R Maei, and Csaba Szepesvári. A convergent o(n) temporal-difference algorithm for off-policy learning with linear function approximation. In Advances in Neural Information Processing Systems, pages 1609-1616, Vancouver, Canada, Dec. 2009.
[50] JN Tsitsiklis and B Van Roy. An analysis of cemporal-differcee learning with function approximation. IEEE Transactions on Automatic Control, 1997.
[51] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292 1992.
[52] Huaqing Xiong, Tengyu Xu, Yingbin Liang, and Wei Zhang. Non-asymptotic convergence of adam-type reinforcement learning algorithms under markovian sampling. arXiv preprint arXiv:2002.06286, 2020.
12

---

[53] Pan Xu and Quanquan Gu. A finite-tima analysis of q-learning with neural network function approximation. In International Conference on Machine Learning, pages 10555-10565. PMLR, 2020.
[54] Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference on learning theory, pages 639-649. PMLR, 2018.
[55] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109(3):467-492, 2020.
[56] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterizeed deep neural networks. Advances in Neural Information Processing Systems, pages 2053-2005 2019.
[57] Shaofeng Zou, Tengyu Xu, and Yingbin Liang. sinite-sample analysis for sarsa with linear function approximation. In Advances in Neural Information Processing Systems, pages 8665- 8675, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See future directions presented in Section 4.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary Materials
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "gevetM6LZLI", "reviewer": "Reviewer_MzJb", "summary": "Disclaimer: I do not have enough background to check the technical details and hence basically make a guess. There may be another reviewer (sorry for my late notice) for this paper. I will go through other reviews carefully and adjust my score accordingly.\n\nThe paper is purely theoretical. It provides the finite-time analysis for the adaptive TD with multi-layer ReLU networks. \n", "questions": "NA. ", "limitations": "NA", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\nThis should be the first work in analyzing the convergence of adaptive TD with multi-layer ReLu NNs.\n\nWeaknesses: \n\nMy main concern is the work is likely to be incremental, in the sense that the proof framework and the method of proving technical assumptions, and lemmas are quite similar to those existing papers as cited by the authors, especially [7,18,48]. I expect an explicit discussion about the differences in the techniques used for proofs.  \n\nThe main theoretical result is not informative; it is known that usually adaptive learning rate strategies can improve the convergence rate by choosing appropriate hyper-parameters (as the non-adaptive/plain version is simply a special case). But the result does not provide any additional insight into what designs/hyper-parameter choices in the adaptive method can help improve convergence.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "c75PLnSOj-s", "reviewer": "Reviewer_QeLT", "summary": "This paper establishes the finite-time analysis for the adaptive TD with\n9 multi-layer ReLU networks approximation whose samples are generated from\n10 a Markov decision process. Overall, the paper includes interesting results. However, it needs modifications to improve its quality.\n", "questions": "1) \\phi is not defined in the definition of the neural approximated Q in line 124. How can we understand the  feature vector in the nueral approximation? Please clarify it in the paper.\n2) Why do you use boldface for value function while the normal font for Q-function?\n3) Why do we have sqaure root of m in the definition of f? Please clarify it in the paper.\n4) The norm || ||_F in eq (5) is not defined. \n5) The set B in Lemma 1 is not defined. \n6) It is in general hard to understand the intuitive meaning of Theorem 1. For example, what is the meaning of the objective function being small? How can we interprete the solution theta^*? Moreover, it is not easy to conclude that the bound is small in practice. More dicussions are needed to clarify the above points.  \n7) Overall the overall presentation is sloppy. There are many math expressens whose definitions are lacking. \n8) There is notational explosion. It is recommended to simplify the notations.", "limitations": "It seems that it is hard to conclude meaningful results in practice from the analysis in this paper. ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: New analysis of TD learning with neural network. The established theory shows that if the width of\nthe deep neural network is large enough, the adaptive TD using neural network 12 approximation can find the (optimal) value function with high probabilities under he same iteration complexity as TD in general cases. \n\nWeaknesses: \nIt includes the projection step, which is in general hard to perform. \nThe overall presentation is sloppy.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PNOdrntt5xJ", "reviewer": "Reviewer_Npn2", "summary": "This paper studies the adaptive TD method in the nonlinear function approximator setting, specifically MLPs with ReLU activations. It essentially bridges two prior works, one of which establishes the convergence of TD under MSPBE to the global optimum, while the other proves accelerates rates of convergence for adaptive TD in the linear setting. The current submission combines these the two and proves accelerated rates of convergence to the minimizer of MSPBE for adaptive TD in the nonlinear setting.", "questions": "- The bounds obtain depends quadratically (in fact, cubically) on the diameter of the set V. The authors avoid this issue by carefully setting a whole host of magic constants to have them magically vanish, yielding the final bound. However, it is unlikely that any practical application can actually make these choices. Do the authors see an avenue forward for this line of research that avoids such strong depends on the diameter of the projection set?\n\n- The authors mention a novel proof technique, do you believe this technique can be useful in other cases as well? \n\n- Do the authors have an intuition of how hard it would be to extend these result to also include policy improvement iteration?", "limitations": "See above. Overall, the authors are very clear about assumptions under which their results hold.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a natural next step for a recent body of work that have analyzed finite-time convergence rate for (projected) TD methods in the non-linear setting. In terms of originality and significance, the main result itself, if somewhat incremental, is novel and useful. Beyond the result itself, the authors introduce a new proof technique that may prove useful beyond the scope of this paper. The paper is technically polished with a clear exposition of the results and its derivations (I did look at the proofs, but not in great detail). Overall, the paper is well written with a clear motivation and contribution.  \n\nMy main issue with this paper is that it does not delineate the difference between MSBE (which is not analyzed) and MSPBE (for which the results hold). This is extremely important because the proof technique that this paper uses (introduced in prior work) relies on an implicit linearization. The approximation error induced by linearization grows with diameter of the projection set. This is the main limitation of this type of analysis, because tight convergence rates requires the projection set to be small, and hence the minimiser to which it converges is often very different from the minimizer of MSBE. Consequently, these result are really only relevant for MSPBE. While understanding MSPBE is in itself useful, it important to delineate the contribution made to not con that the paper fails to make. With that said, this can be resolved by adding a paragraph or two. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4-wA-BkHQXk", "reviewer": "Reviewer_tHmB", "summary": "This paper proves that the adaptive temporal-difference (TD) learning with ReLU neural network approximation converges when the width of the network is sufficiently large. Moreover, this paper proves that adaptive TD is faster than TD with the ReLU neural network approximation.", "questions": "- Might the authors briefly explain why the analysis is limited to ReLU networks?\n\n- Might the authors briefly explain the tightness of the bound in Theorem 1?\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of this paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- To the best of my knowledge, Theorem 1, the main result of this paper, is significant and highly non-trivial. In particular, this paper has extended the analysis of adaptive TD with linear function approximation to multiple layers neural network approximation.\n\nWeakness:\n\n- The analysis is limited to ReLU networks.\n\n- It is not clear if the bound in Theorem 1 is tight. The authors might consider running some experiments to illustrate this.\n\n- The writing of this paper can be further improved. In particular, the current version of Section 2.4 is a little bit hard to follow. This paper also has a complicated notation system; however, some notations are used without first defining them. Examples include $\\hat{f}$ in Definition 1 and $\\mathbf{B}$ in Lemma 1.\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept