On the Performance of Temporal Difference Learning With Neural Networks
Authors: HAOXING TIAN
Ioannis Paschalidis
Alex Olshevsky
Venue: ICLR 2023 poster (2023)

Abstract: Neural Temporal Difference (TD) Learning is an approximate temporal difference method for policy evaluation that uses a neural network for function approximation. Analysis of Neural TD Learning has proven to be challenging. In this paper we provide a convergence analysis of Neural TD Learning with a projection onto $B(\theta_0, \omega)$, a ball of fixed radius $\omega$ around the initial point $\theta_0$. We show an approximation bound of $O(\epsilon + 1/\sqrt{m})$ where $\epsilon$ is the approximation quality of the best neural network in $B(\theta_0, \omega)$ and $m$ is the width of all hidden layers in the network. 

Published as a conference paper at ICLR 2023
ON THE PERFORMANCE OF TEMPORAL DIFFERENCE LEARNING WITH NEURAL NETWORKS
Haoxing Tian, loannis Ch. Paschalidis, Alex Olshevsky Department of Electrical and Computer Engineering
Boston University Boston, MA 02215, USA (tianhx, yannisp, alexols]ebu.e
ABSTRACT
Neural Temporal Difference (TD) Learning is approximate temporal difference method for policy evaluation that uses a neural network for function approxima- tion. Analysis of Neural TD Learning has proven to be challenging. In this paper we provide a convergence analysis of Neural TD Learning with a projection onto (00, w), a ball of fixed radius around the initial point Og- We show approx- imation bound of (E + 1/ //mm) where is the approximation quality of the best neural network in B B(6o: w) and the width of all hidden layers in the network.
INTRODUCTION
Temporal difference (TD) learning is considered to be a major milestone of reinforcement learning (RL). Proposed by |Sutton (1988.. TD Learning uses the Bellman error, which is a difference between an agent's predictions in Markov Decision Process (MDP) and what it actually observes, drive the process of learning an estimate of the value of every state.
To deal with large state-spaces, TD learning with linear function approximation was introduced in Tesauro (195).. A mathematical analysis was given in Tsitsiklis & Van Roy (996), which shows the process converges under appropriate assumptions on step-size and sampling procedure. However, with nonlinear function approximation, TD Learning is not guaranteed to converge, as observed in Tsitsiklis & Van Roy (1996) (see also Achiam et al. (2019) for more recent treatment).
Nevertheless, TD with neural network approximation, referred to as Neural TD, is used in practice To our knowledge, rigorous analysis was only addressed in the three papers Cai et al. (2019): Xu & Gu (2020): Cayci et al. (2021).
despite the lack of strong theoretical guarantees.
In Cai al. 2211). single hidden layer neural architecture was considered along with projection on a ball around the initial condition; approximate convergence was proved to be an approximate sta- tionary point of a certain function related to the linearization around the initial point. This result was generalized to multiple hidden layers in Xu & Gu (2020), but this generalization required projection on a ball of radius of w ~ m -1/2 around the initial point, where is the width of the hidden layers. Because the radius of this projection goes to zero with m. this effectively fixes the neural network to small distance from its initial condition. Both Cai et al. (2019); Xu & Gu 2020) additionally gave a convergence
required certain regularity conditions on the policy. Finally, Cayci et al. (2021)
result for single hidden layer, also with projection onto a radius of m 1/2 around the initial
point, but with the final objective being the representation error of neural approximation without any kind of linearization. This result also required a condition on the representability of the value function of the policy in terms of features from random initialization.
In this paper, we analyze Neural TD with a projection onto B(0,, ball of fixed radius w around the initial point 0g. We show an approximation bound of 0(E+1/vm where is the approximation quality of the best neural network in B (60g. w). Our result improves on previous work because it does not require taking the radius to decay with m, does not make any regularity or representability assumptions on the policy, applies to any number of hidden layers, and bounds the error associated with the neural approximation without any kind of linearization around the initial condition.

---

Published as a conference paper at ICLR 2023
The main technical difference between paper and previous works is the choice of norm for analysis. We will describe this at a more technical level the main body of the paper, but we norm introduced by Ollivier (2018), which is convex combination of the usual 12-norm weighted by the stationary distribution of the policy with the so-called Dirichlet semi-norm. The later has previously been used in the convergence analysis of Markov chains (Diaconis & Salofi- Coste (196)); Levin & Peres (2017)). It was shown in Ollivier (2018) that Neural TD is exactly gradient descent on this convex combination of norms if the underlying policy is reversible.
In the case where the policy is not reversible, these results were partially generalized in Liu & Olshevsky (20T)) where was shown that TD Learning with linear function approximation can be viewed as a so-called gradient splitring, a process which is analogous to gradient descent. We build heavily on that interpretation here. Our main technical argument is that Neural TD approximates the gradient splitring process at each step so that despite the nonlinearity of the approximation, an improvement in approximation quality can be guaranteed unless the system is already close to the best possible approximation over the projection radius. Notably, our arguments do not imply that the neural network stays close to its initialization and our empirical simulations show a significant benefit from taking the projection radius w not to decay with the width m.
2 PRELIMINARIES
2.1 MARKOV DECISION PROCESSES
In this section, we present key concepts from MDPs, mostly to introduce our notation.
A finite discounted-reward MDP can be described by a tuple (S, A, Pene; T; 7), where S {81, (2..,....... 8n} is a finite state-space whose elements are vectors; A a finite action space; Pe Peny (Penv (s') a) e is the transition probability matrix, where Penv (s'|s, a) is the probability of transitioning from to after taking action a; r S x A + R is the reward function; and y E (0, is the discount factor. A policy æ in MDP is mapping S A [0, 1] such that E.eA (TS, a) = 1 for all & E S, where π (s, a) is the probability that the agent takes action a in state s. We will use n for the number of states, i.c., |S| = n.
Given policy define the corresponding transition probability matrix P (P(s'(s))
P(sl(s) Σ T(. Pewv (s' (s|ssa)..
aAA
We also define the state reward function as
r(s) = Σ (ss,a)r(ssa).
Although P and r(s) depend on the policy स, throughout this paper the policy will be fixed and hence we will suppress this dependence in the notation.
The stationary distribution μ corresponding to the policy æ is defined to be a nonnegative vector with coordinates summing to one and satisfying n² 1²² P. The Perron-Frobenius theorem guar- antees that such a f exists and is unique subject to some conditions on P, e.g., aperiodicity and irreducibility (Gantmacher 1964)). We use uss) to denote each entry of μ.
The value function of the policy я is defined as:
V V*(s) Eg
Σ t=0
Ex'r(st))
where Eg stands for the expectation when the starting state and actions are taken according to policy π, and s is the f'th state encountered. Note that this quantity depends on but once again we suppress this dependence because the policy will be fixed throughout this paper. Moreover, note that, despite the star superscript, V is not the optimal value function but rather the true value function corresponding to policy ा.
It is well known that this value function satisfies the Bellman equation,
V R + PV*
2

---

Published as a conference paper at ICLR 2023
where V is vector whose i'th element is (s:) and R is vector whose i'th element is r(s:). We will further assume that rewards are bounded [-Tmax, mmax as the following assumption. Assumption 2.1. For any s, S x A. we have (r(s,a)] Tmax-
This immediately implies that
V*
mmax as S.
(2)
2.2 MARKOV CHAIN NOISE MODEL
There are two standard sampling models where policy evaluation methods are usually considered. The simplest model involves i.idd. sampling of at each step from stationary distribution μ.
Alternatively, in the Markov model the states 8, are collected from a single path of Markov chain transitioning according to P. It is still assumed in this case that the initial distribution is μ,, so that the distribution of each 8, is still μ4, with the difference that the successive states are now not independent. This always be approximately satisfied by generating sufficiently long path from P and ignoring the initial states.
Assuming that the underlying Markov chain mixes with geometric rate is common in many anal- yses, like [handari et al. (2018); Liu & Olshevsky (2021). We will also make this assumption. Formally, let p denote the matrix raised the i' ''th power, PA, be the row of ps corresponding state 8, and || l/ the total variation distance.
Assumption 2.2. There exists constant C > and 3 E (0, 1) such that
max || P -MllTV S CB
This assumption guarantees "mixing": matter the initial distribution, the state will get closer and closer to the stationary distribution z as t increases. As pointed out in Levin & Peres (2017), this assumption always holds when the Markov chain is irreducible and aperiodic. Another useful quantity is the mixing time, Tiiix (fixx) defined as the smallest integer such that
max P u||TV Emix.
Note that Assumption 2.2 implies
Emix
Tiix (emix)
logg
C
For simplicity, we will use Tmix without specifying its dependence on emix throughout the paper.
2.3 D-NORM AND DIRICHLET NORM MDPS
We now introduce the so-called D D-norm || ||D and the Dirichlet semi-norm IDr associated with a policy. While the former has long been used for the analysis of temporal difference learning dating back to Tsitsiklis & Van Roy (996),, the latter has, to knowledge, been introduced in the context of RL relatively recently in Ollivier (2018).
Let D diag(u(s)) be the diagonal matrix whose elements given by the entries of the stationary distribution jr. Given a function f S + R, its D-norm is defined as
|1 = f Df = Σ (s))
(4)
.ES
The D-norm is similar to the Euclidean norm except each entry is weighted proportionally to the stationary distribution. We also define the Dirichlet semi-norm of f:
I1
Σ ((s)(((((s)((())) f(s)²
(S)
S.''
A semi-norm satisfies the triangle inequality and absolute homogeneity, any norm, but it is not norm as may be equal to zero at non-zero vector. Note that || Dir depends on the policy both through the stationary distribution (ss)) as well as through the transition matrix P.
3

---

Published as a conference paper at ICLR 2023
Finally, following Ollivier 2018). the weighted combination of the D-norm and the Dirichlet semi- norm is denoted as N (f) and defined as
N() (1- +
Note that (f((f is valid norm: since (ff is quadratic, can write N(f) f for some symmetric matrix N; examining the first term in the definition of N() we see that N =
(1 (1))dii((11...... nn) ) 0 by irreducibility and aperiodicity.
2.4 NEURAL NETWORK BASED APPROXIMATION
In this section we closely follow the notation from the previous works in Cai et (2019): Allen-Zhu al. (2019); Liu et ) Ollivier (2018) neural approximations. We define multi-layer fully connected neural network by the following recursion:
(010), for & E [l,...,,Ky K}, Vm
where or is an activation function and the input is state of the MDP: (0) E S. Next, we define
V(s, 0)
8² (K))
m
to the output with no activation function on the output. We assume that each entry of g( are initialized from N (0, 1) and each entry of the vector b satisfies |b, 1, Vr. We further assume that all the hidden layers have the same width which denote by m, i.e., all the matrices g(k) have first dimension of m. Note that the total number of layers in the neural network is denoted by K.
We will stack up the weights of different layers into column vector 0 consisting of the entries of the matrices ((1) ....., ((K), with norm defined by
K Σ k=1
||0||2
[ 1.
where ||. ||ee is the Frobenius norm. During the training process, only the weights 0 will be updated while the weights b will be left to their initial value.
This particular definition many papers on both TD Learning (i.e., Xu & Gu (2020) and Deep Neural Network (i.c., Liu et al. (2200) analysis. Although there is not an explicit bias term above, this definition does allow each layer to have different bias. This can be reached by setting the last entry of !0) be 1 and last row of each ((k) to be (O...., 0,
neural network, as well the decision to leave b fixed, is used by
We can view this ncural network as mapping the parameters 9 to a vector with as many entries as the number of states. Specifically,
define the vector V(O) whose i'th entry is
[V()]: (s,,, 0), 1, 1,2,...,
Note that n in the above equation denotes the number of states in the MDP, i.e., (S). We remark that this vector will never be actually used in the execution of any algorithms discuss due to its large size, but its use is still useful conceptually. The Jacobian of V ((0) is then the matrix
Vo (S1, 0)
VoV(0)
VoV
where, abusing standard notation, VoV(s, 8) are defined to be row vectors.
A standard assumption made to simplify the analysis is the following.
Assumption 2.3. Suppose for any {1, 2, ... .......,, n). || where || stands for the I-norm.

---

Published as a conference paper at ICLR 2023
Assumption 2.3 can always be satisfied by scaling, typically have control of how choose to represent the states of the MDP. is also a common assumption that appears in many previous works (c.g.. Cai et al. 2019); Allen-Zhu et al. (2019)).
function f is called L-Lipschitz
(z) f(v)l - L|z - ul. Vx,y. And differentiable function RR + R is fo-smooth if
(x) (y) S co/a- y/. Vz. y,
where f' stands for the derivative of f. We find it helpful to make the following assumption: Assumption 2.4. The activation function a is I-Lipschitz and co-smooth.
The smoothness condition implies that our results below are not directly applicable to popular func- tions like ReLU. However, many activation functions are twice differentiable (e.g., sigmoid, tanh, arctan, softplus) and one could always use smooth approximation to a ReLU activation (e.g.. GeLU or ELUU). We do need the smoothness of the input-to-output map as we will use the result from Liu et al. 2020), which claims the neural network is O L O smmoohheess with respect to its parameters. The following assumption is also required implement their result:
Assumption 2.5. For any E 21,2...., KK, given i {1.2...., m.) there exists some constant
((k) O, such that | |= Ō(1) at initialization. Here, t. means the i'th entry of (k))
2.5 NEURAL TD
In this section, we introduce (projected) neural TD learning. At each time step t, this algorithm samples state from the stationary distribution from either of two sampling models discussed earlier, generates the next state the MDP, and computes the temporal difference error, defined as
6, r(s) + (s', 0,) (s,0t).
Defining s(O,)
((0,) = V8, 0,)
projected neural TD updates the weights as
0.41/2 = 0g + a.g(ft).
0.+1 Proj(0++1/2)
where the projection is onto a ball of radius w around the initial condition:
Proj(0) arg
min
|| 0||-
2:11=-0ol155
Projection a common tool in neural TD and neural Q-learning to try to stabilize the iterates, since divergence can occur (Achiam et al. (2019) Van Hasselt et al. (2018)). Most analyses of TD learning proceed by comparing the evolution of TD to mean-path update, defined as
0.+1/2 = 02 + a,,(
0.+1 Proj(O.+1/2)
where
((0,) E(g(0.)1(.)
= Σ [) (VV V
(()))).
It is convenient to rewrite g(O)) in terms of the difference between (0.) and V*, which can be done
by subtracting Eq. with the result being
( V.V (O.) P -
For simplicity, for the rest of paper we will define to be the set onto which we are projecting:
θ B(6, w) {0 ||0 Poll & w].
Finally, we will say that V is an e-approximatton to the true value function V* if
max
max v' - V*()| s E.
(8)
#ES
We will denote ú to be the point where the function V(Ô-) e is the e-approximation of V*.
5

---

Published as a conference paper at ICLR 2023
3 OUR MAIN RESULT
We can now state the main contribution of this paper, which is performance result for Neural TD. We will require assumption to the effect that the initialization is not too large.
Assumption 3.1. For all E {1,2..... K), | I O
This is common assumption: theoretical justification can be found in Liu et al. (2020) In particular, this assumption holds with high probability for a random Gaussian initialization if, for example, K (the depth) grows slower than exponentially in (the width).
Now we are ready to state our result.
hold, 0, is generated by projected Neural TD with the constant step-size ot = and C. 3 come from the Assumption 2.2
Theorem 3.1. Suppose Assumption 2.7 2.2
2.3
2.4
2.5 3.1
(a) Under ii.d. sampling, we have
T-1
- Σ (V:) 1100 0_11
+((
1 vm
+0
+ +0 (at?)
(1 -1- -1- (a))
20T
1=
In particular, if = T-112 TT-1/1 and S 1, we have
100 0.11
(ct
1
(
EIN((((,) v(0.))l
+0
0
T
2
mm)
(1-
(b) Under Markov sampling, we have
110
0.11
+0(ct
1 1)
(UN(V(())-V(CC)
+0 c+
+0 (ac²)
+
(1 7) O(a)
2aT
Vm
log
C
log C B
+0
a
x2
+
a
(1 7)2
In particular, if = 1/2 and S 1, we have
110 0.11
(e -
(++)
( s
+0
0
2
vm)
(-
vT
1
1 log(CVT)
(1 7)2
1 5 VT
In all O(-) notations above, we treat factors that do not depend on T, e, m, or, B, Og as constants.
As mentioned earlier, the key distinguishing feature of this theorem is the choice of norm. The left-hand side of all the equations measures the differ- ence between V(O.) and the best possible V(O.) within B(fo, w) by taking the ((-)) norm.
17
((())
We note that since, trivially, II < ((f)/(1 7). where ? the dis- count factor, one can simply replace the left-hand sides of all the equations by !!Í to obtain results that look more similar to the previous literature on TD, which usually proceeds based on analysis in the D-norm (e.g.. Tsitsiklis & Van Roy| (1996)).
Figure 1: Key
property of gradient splitting: h(0) has the same inner product with as (1/2)V5(0).
As is common in analyses of SGD, the performance measure is the average of performance measures from 1 to T. a particular 6₂ is sought that satis- fies the bounds obtained, standard trick is choose t' to be uniform from In that case, the expectation (V ((O.), is exactly the
T. ,,...,T. left-hand side of all the bounds in the theorem.

---

Published as a conference paper at ICLR 2023
Looking the right- hand sides of all the equations, the theorem guarantees final eπror of O( + 1/ 1/ym), with a convergence rate that scales as O(1/VT). The difference between the two cases is that that the Markov sampling case contains an additional term containing
the mixing time. As result of this extra term, the convergence time in the Markov case is worse by factor of Ollo VT).
We now revisit the discussion of the novelty of this paper. First, in contrast to previous work, we do not assume the projec- tion radius w has to decay with m, nor do we restrict analysis to a single hidden layer case. In proof, the projection ra- dius appears constant in the (-)) notation, which is why we need assume is a constant. Second, the left-hand side of the equations is a measure the error (0,) V(O.). which can be thought of the dif- ference between the error of the neural network and the best possible error in B30,, w) Moreover, as already discussed, the left-hand side of the equations above is greater than the quantity
lal
coder
da Lieen
(a) Mountainear,
(b) Mountaincar,
(c) Mountaincar,
(d) Caripole, 3
(c) Cartpole, 5
(l) Cartpole, 7
Britmon
(g) Acrobot, 3
(h) Acrobot,
ii) Acrobol,
Figure 2: Averaged Bellman error.
(1 (1-)))]V(0)) - v(0.) = (1- - 7) Σ (()(((() (s)
which is a natural measure of the average error. The point is that the network is not being linearized around the initial condition in any sense. Finally, no additional assumptions the policy are being made here; in particular, no assumptions that the policy is regular or that is representable are neces- sary. As outlined in the Introduction, (small projection radius, linearization around the initial condition, assumptions on policy, restriction single layer case) all previous papers suffered from least three.
of the four potentially undesirable elements discussed here
DISTINGUISHING FEATURE OF OUR ANALYSIS
The main technical difference between our work and the previous papers is the use of the function (((-) to measure the approximation error. Here, follow Ollivier (2018): Liu & Olshevsky (2021) which explained why this function is the "right" function to analyze policy evaluation.
In Ollivier 2018) it shown that if the matrix P corresponds VoN(() for some f. This makes neural TD very easy to analyze, as it can be viewed gradient descent. Unfortunately, in practice policies are almost never reversible.
reversible Markov chain, then
E g (.)
In Liu & Olshevsky (2021). it was shown how to further use the function NV(-) to analyze TD with linear approximation when the policy is necessarily reversible. The key idea the notion of
7

---

Published as a conference paper at ICLR 2023
gradient splitting: a linear function h(0) is said to be gradient splitting of convex quadratic f(0) minimized at f = a
2 V -)) - -0000
In other words, h()) has exactly the same inner product with the "direction to the optimal solution" as the true gradient of f(0) (up to the factor of 1/2). The significance of this that it allows many analyses of gradient descent to be modified to analyze TD with linear approxima- tion, since the key step in analyses of gradient descent usually to argue that the left-hand side of Eq. 99) is negative, signifying gradient descent "makes progress"
le 21100 Wilecia UP
(a) Mountaincar,
(b) Mountaincar,
(c) Mountaincar, 7
couraat odlon
(d) Cartpole, 3
(e) Cartpole, 5
(f) Cartpole, 7
that
towards the optimal solution. In Liu &
(g) Acrobot, 3
(h) Acrobot,
Acrobot,
Olshevsky (2021)
it was shown that for TD with linear approximation, 5(0)
Figure 3: Distance to initialization divided by the projection radius.
exactly the gradient splitting of (f)). We build on that idea in this paper as follows. We use recent NTK-style bounds from Liu al. (2020) to argue that with increasing width, the neural approximation gets more linear. For finite m, we can then modify existing techniques for analyzing gradient descent with errors in the gradient evaluations to analyze the neural TD update, which view as gradient splitting with error in the evaluations.
It should be stressed that the most interesting "regime" which expect these results to be ap- plicable is when m is only moderately large. Intuitively, when m is too large, the network will be very close to linear, and the benefit over taking random linear features will be small. In terms of our bounds, in this case we would expect the term in Theorem 3. be large. On the other hand, when m is too small, the error bound scaling with width of m -112 will not be very attractive. On the other hand, our results can be applied the "middle range" say m 100 where, depend- ing the context of the problem, network will be sufficiently linear to converge well, but not so linear to lose approximation quality. Our simulations confirm this, verify good approximations for networks of approximately this width on several open Al benchmarks.
m m/112 error is acceptable. Informally, in this regime the
5 SIMULATIONS
might be objected that many analysis of neural network training in the large-width regime proceed by arguing that the neural network stays around its initial point (e.g., Chizat al. (2019); Telgarsky (2200). If so, then the part of our results dealing with avoiding a projection radius that goes to zero with m would not make much difference practice. Here, we show empirically that, setting the projection radius to be constant rather than m- 1/2 does make substantial difference.
8

---

Published as a conference paper at ICLR 2023
We produce simulations Open Al Gym tasks: Mountainear, Cartpole and Acrobot. In each task, a trained policy is used to sample data to train fully connected neural network for policy evaluation using Projected Neural TD learning. The policy in Mountaincar and Cartpole is trained by Proximal Policy Optimization (PPO) (Schulman et al. (2017) while in Acrobot is trained by Deep Q-Learning (DQN) (Mnih al. (2055). Both algorithms implemented through the Stable Baselines package Raffin et al. (2021).
We run total
of 2000 (5000 in Acrobot task)
steps on each task, computing the y value during the training process every 20 (50 in Acrobot task) step. Different widths m are chosen for each task. In each figure, the x-axis plots time steps while the y-axis plots the averaged Bellman error, the distance initial- ization (given by [o:= ), and the difference between gradients (given by [VV fr)
(a) Mountaincar,
(b) Mountaincar,
(c) Mountaincar,
(d) Cartpole,
(e) Cartpole, 5
(I) Cartpole,
condan
(oV lo)l
respectively. Each subtitle of each fig- suggests which task is performed on and how many hidden layers are used. It is clear from the figures that the networks we use are nonlinear. It is also clear that networks with decaying projection radius are significantly outperformed by networks with a constant projection radius.
(g) Acrobot, 3
(b) Acrobot, 5
Acrobot, 7
Figure 4: Gradient differences V (c) VoV 0o) as a measure of nonlinearity of the neural network.
6 CONCLUSIONS
We have provided an analysis of Projected Neural TD for policy evaluation. We have shown that the projection set is ball of constant radius B(f,, w) around the initial point dg. the final approx- imation eπror is O(e + 1/ 1/vm). where e is the approximation quality of the best neural network in B(0, and m the width of all hidden layers in the network. Our result improves on previous works because it does not require taking the radius w to decay with m. does not make any regularity or representability assumptions on the policy, applies to any number of hidden layers, and bounds the error associated with the neural approximation without any kind of linearization around the ini- tial condition. We conjecture that unprojected neural TD converges to the optimal solution with high probability provided it begins within radius of O ((vm) away from a point which exactly describes the true value function. This conjecture is proved for single hidden layer networks. Finally, we have demonstrated empirically that these changes make substantial difference in performance.

---

Published as a conference paper at ICLR 2023
REFERENCES
Joshua Achiam, Ethan Knight, and Picter Abbeel. Towards characterizing divergence in deep Q- learning. arXiv preprint 1:Xxiv:/03..0600 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp- 242-252. PMLR, 2019.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692.
PMLR, 2018.
Qi Cai, Zhuoran Yang, Jason Lee, and Zhaoran Wang. Neural lemporal-difference learning con- verges to global optima. 2019.
Semih Cayci, Siddhartha Satpathi, Niao He, and R Srikant. Sample complexity and overparam- eterization bounds for temporal difference learning with neural network approximation. arXiv preprint arXiv:2103.01391, 2021.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Persi Diaconis and Laurent Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. The Annals of Applied Probability, 6(3):695-750, 1996.
FR Gantmacher. The theory of matrices. New York, 1964.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107, American Mathe- matical Soc., 2017.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 33: 15954-15964, 2020.
Rui Liu and Alex Olshevsky. Temporal difference learning gradient splitting. In International Conference on Machine Learning, pp. 5905-6913, PMLR, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-53, 2015.
Yann Ollivier. Approximate temporal difference learning is gradient descent for reversible policies. arXiv preprint arXiv: 1805.0000000000 1805.00869, 2018
Antonin Rafin,, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. basble-baselines:: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268): 2021. URL http://mmm...rrgp/ppppps/ss/
20 1364. html
Walter Rudin. Principles of mathematical analysis, volume 3. McGraw-Hill New York, 1976.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. Advances in neural information processing systems, 31, 2018.
Richard Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9 44, 1988.
Matus Telgarsky. Deep learning theory (Lecture Notes), 2020.
Gerald Tesauro. Temporal difference learning and DD-Gammon. Communications of the ACM, 38 (3):58-68) 1995.
10

---

Published as a conference paper at ICLR 2023
John Tsitsiklis and Benjamin Van Roy. Analysis of cemporal-diffteree learning with function approximation. Advances in neural information processing systems, 9, 1996.
Hado Van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Mo-
dayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv:18/2.02664 2018.
David Williams. Probability with martingales. Cambridge university press, 1991.
Pan Xu and Quanquan Gu. A finite-time analysis of Q-learning with neural network function ap- proximation. In International Conference Machine Learning, pp. 10555-10565. PMLR, 2020.

---

Published as a conference paper at ICLR 2023
A PROOF FOR THE MAIN RESULT
A. 1 USEFUL LEMMAS
Before we go into details, we first introduce the following lemmas.
Recall we have defined N() as
(1-)i1l-)
The first lemma implies important property of N(().
Lemma A.1. For any function f defined on the state space S, the following equation holds:
-N(f) D
Proof. We can perform the following sequence of manipulations:
Il
Σ
2 8,8'
2 Σ (+)
Σ
IMOP((11))
E(ss)((d1))))))) 8,8
3,0"
2 Eu(s)s(()
- - -MOPP(N))OO =m
Σ ((S
where the first equation uses Eq. and the forth equation uses Eq. Thus,
D - I)f = ff Df + D(P
-11111BB + Σ (s))((s) E P(5(s)5(())
-11->))lf13 -
=-N(f).
The following lemmas are some variations of the mean-value theorem. In this lemma and below, we adopt the notation that gradients are row vectors.
Lemma A.2. (a). Let IR - be any differentiable function. For any x, y E RR there exists
À E (0,1) and z Ar + (1 X)y such that
h(y) h(z) (2)(() z).
(b). Let E : RR. - TR be any differentiable function. For any x, y E R", there exists À E (0,1) and Ax + A)y such that
E(v) E(x) = ['(()(v z))
(c). Let f R2 + & be any differentiable function and e R be any vector For any F. y E Ra, there exists E0, 1) and z = Ax + (1 A)y such that
eT((() - f(x)) = (=) x),
where f2(2) is the Jacobian at z.
Proof.
(a). This a direct result of the well-known mean value theorem (Theorem 5.10 in Rudin 1976)).
12

---

Published as a conference paper at ICLR 2023
(b). Define h : IR- R such that h(w) 5(x + w(y z)). u, U E R, there exists À E (0, such that
Using the above fact, for any
h(v) - h(u) = h'(Au + (1 A) u).
By letting and 0,
( E(x) EAor Aa + (1 (y - =x).
(c). Define ç I2
such that e² f. Using the above fact, for any vectors 2, y Ie ,there exists x E (0, 1) and & = x + (1 X)y such that
{(y) {(x) = (1 -2)
Notice that in this case, E(v) {(x) = e (f(y) - f(x)) and C'(z) f()). So for any vectors z, y, there exists
Ax + (1 A)y such that
e" f(v) e² f(x) = e" (y
which is exactly what needs to be proved.
Lemma A.3. Let f Raa - RRb be any differentiable function. For any n. y RRa there exists À E 1) and λx (1 Ayy such that
(1 [(=)1 < (1)l lly 2/|-
Proof. Let take - [(y) - (1x in Lemma A.2 We thus have
(f))) f(x)) (f(v) (())) x)-
We now apply Cauchy-Schwarzz incquality on the right hand side to obtain,
(I - f=)]l s (1)(v) ((=)1 =)11. and finally using the definition of matrix norm,
llf( f())ll (z) =)1l = [f) -1l -
The next lemma shows how the mean-value theorem can help to analyze Neural TD Learning. Lemma A.4. The Projected Neural TD Learning with a mean-path update can be rewritten as
oz+1 = Proj(O, oulgg (0.) + 92(0.) + (o)))
with 9. (0.). T2 (0t). ÿz (6:) defined as follows:
(1,) V.V (Omil)T DGP v(_)),
(10)
(2(0,) (VoV(8)) )
-V())),
(11)
==(0.)= =
(12)
where À E [0, is a sealar and Grid = 10; + (1 2)0_ a vector such that
(0, o,
(13)
Proof. By Eq.
g(0.) D(V V*)
(14)
-VV( D(pP 1)(V -
-V).
13

---

Published as a conference paper at ICLR 2023
Now let
- V(l.)) be the vector in Lemma A.2 There exists scalar À (0,1)
and vector 0pmid 10; + (1 2)0, such that
(0.- D - -
This gives the reason divide Eq.(T4 into two parts as follows:
- v(Q.))
- -v())
V.. (()(P-)(V(())))) v(O.))
The following lemma builds the relationship between x² Dy and expectation.
Lemma A.5. Let a. y be two vectors and x(i), y(i) denote their 'tth entries, respectively. Let T. y be two scalars such that [x(i)] < E and (y(i) S y hold for all i. The following results hold:
Dy = y Dx $ 2y. x
x² DPy S sy,
DPx sy.
Proof. We expand xT Dy, x. DPy and y" DPx as follows:
D' = x² Dr = Σ ((ss))(())(())) & ((ss)) S szg
DPy- = [((s))r(i) Σ P(sglssiv S zÿ Σ u(si) Σ P(sy(si) 20g
y DPx D P(sslss))()) S zy IE((s:)PL say.
The following lemmas implies two important properties of neural network approximation: Lips- chitzness and smoothness.
Lemma A.6. For all E
||0(0] < 0(vm).
Proof.
||0(k)|| S <10(())
0(x) + [10(0) ||
+101
s 50(mm),
where the second inequality is by projection and the last inequality uses Assumption 3. and the fact constant to m.
Lemma A.7. For all (1.2...,,K),
||o( O(vm).
14

---

Published as a conference paper at ICLR 2023
Proof. From Assumption 2.3
|2:00|| I 1. By Lemma A.6
|12 =
1
(0(1) 20(0)
vm
12 12110010
(0)
1 (0)
m
- (m))
By induction, suppose ||=(6a112 Σ ((m). By Lemma A.6
(1 ||3
(((0))))(()))111))))
mm
12 111100+2)11211000000) lo(0))
(mm).
Lemma A.8. For all le E (1. K).
|| -) (k) 11 01))
Proof.
o'' Σ C0 (10000)0)000-1110)) (1.)
Vith 1)
vm"
which implies
m
V (100
sup Σ
214 2) (i.))00
||||==1
sup
||||=
- |1000)1111
m
01).
where E' is a diagonal matrix with E'( = o' 'E, (1. ())()))())))) The last inequality holds
because of Lemma A.6
Lemma A.9. For all E (1, K}.
V 20 (8) < O())
Here, (0)) is defined to be matrix whose (i, (j 1)m + h) 'th entry ( (1.j, h) given
by
0z (i)
( (i,j,h) 201k) h)
Proof.
V
_ lfi = jto'
1
(i) 200-2007
vm"
We can write this as
V (1) (i.j.'') = (0())"))))))))))
1 11==
vm
15

---

Published as a conference paper at ICLR 2023
which implies
V (10))
sup Σ
V (()) (k) (i.j.5")Vss'
|| i=l
3.
2
Σ1 1(i = j}E00) (D
sup
m7
i=1
j.
2
Σ 1 = (101)
sup
i=1
E(i) [V
sup
m | [==1
(
sup
||V||==
K 1 |E|| 1)
K O().
The last inequality holds because of Lemma A.7
Lemma A.10. For all S and 0,
[o. > O
with respect to m.
Proof. Since each entry satisfies 6,| & 1, it easy to see that
||V (K) (s, 0)
||b|| s 1.
By Lemma A.8 Lemma
A.9 and the chain rule,
Voc (s,, 0) = | 00) Vss, V) Vack-ia (K)
aann (k++)) Vouy 11 (1 O0)).
follows:
K [oV(s, = sup Σ
V 000 V(s s01).
[IV||==1
Lemma A.11. The Hessian matrix, which is V 0), has a norm of 0(m-0.0)) -.3). In other words,
IVV 0)1 < O(m 0.55).
This is direct result of Theorem 3.2 in Liu et al. (2020). Notice that since assume Assump- tion 3.1 2.5 (which correspond to Lemma G.I and Lemma G.4 in Liu et al. (202)) holds with probability Lemma A. also holds with probability 1.
The following lemma implies that the update during each step will not be too large.
Lemma A.12. We have the following bound for [lg(0.)]l:
11.(0.)112 < 0(2)) + (I (1- 0(1). 0(1.
16

---

Published as a conference paper at ICLR 2023
Proof. Recall that Eq. ① tell us the property V satisfies, and it can be rewritten
(*()) r((s + + Σ ((""
Moreover, recall that g(6)) is defined to be
g( (sV + 7V'''', - (ss, 0,]]
This immediately implies that g(t)) is actually a random variable and implicitly relies on the state
s. This allows g(()) to be rewritten as
g(0.)= -V 01) (r(() + +V((', - V(s,0.)
=VoV(s, 8.)
(-(s) - (,,, + IR(ST)SVViE,))
-VoV(s, 01)
(V(s, (V(s, ((+, + (V'(s)-V(s,0))
+ Σ P()"|s) (V(s, 01) - v(s',0) + -(66
VoV 01) ((s) (v'()-- - v(s,
+ (1
where, for simplicity, denote f(s) 0.) - V(s,, B1). Now, 1(((0)]112 can be bounded as
(le(0.)11 (000)//=SEIV/VV000001))01 ( (((((111))))) + (v(7))-
+ 1 (1) + ( }
There are five different terms, and now we will bound them respectively. By Lemma A. which says f(s) Lipssiips and the fact that 1|0: 0.11 S w.
f(6) < 001).
Using the above fact,
b ? Σ -1P
Using Eq. we can derive
[v'ss) 20()).
Using the above fact,
1 =7 - - SP((E))
( Σ P(S -(V0)
Using Eq. and Jensen's 's inequality,
(2rmaxx) 2 72
1 1-7) )² =
7 Σ (6) 5n² Σ ps)
(1 (1- 011.
17

---

Published as a conference paper at ICLR 2023
Combine the above five facts, and we have the bound for (1((3:)11
(I(((((O))(o)) (
|T.(0,))) silVoo f(s)2+ +
)
+ (> P(s")))((() + < -v-)))))
<5]lVo 0111 (011) (01)+
72 (1 (1-10011)) 011)
0(1) 72 011)
5(1+2)) + +e)
(1 (1-7)3
(15)
where the last inequality uses Lemma A.10 Since 0 y $ 1, we can simplify the bound
llg(0.)11 = (1 (1- O(1)
A.2 PROOF FOR THE MAIN RESULT
Proof. Consider Projected Neural TD Learning, it is easy to see
||0++1 - 0- |Proj + ong(O:)) 0.112
S ||0: - 0. + a,)()))1
||0: 0.112 + 2ar - -0. g(.)) + a0,1)(0.)11
1|0, - 0.112 + 20, - -0.) g(0.) + (g()) 20, - - -(O)). (16)
First, consider (0, 0_)² (((())- Lemma
A.4 allows to divide it into several parts and
bound them respectively as follows:
(0, 0.) g(.) 2a, 0.) +22)) (a))).
To bound (0, (.))..
(0t - 0_) ((.)))
=(0: 0 (VV(onidd] D(y-P- ()(((()) v(ê))
=(V(0.) V(O)))" D(pP ().( -V(-))))((.)))
= =OV(VV(0.) v(())),
where the first equality is by T0). the second equality is by Eq. 13 and the third equality is by setting f = (0,) (θ.) in Lemma A.I
To bound (0: (0.-0.)T (0.). first notice that Lemma A.11 means V(s, is 00000mmmmm00000---mm with respect to 0. Hence,
V 0.) VsV
Om
(05). 0.5). |00, gyid
O(m -0.5).
where the inequality is by Lemma A.11 and the equality is because both 0 and @mid are in B(O,, w). Similarly, Lemma A. tells us that [s, 6) (1))-iipschiz. This means
(s, 0,) (s, 0.)1l < 0(1) 1 - 0_1l = =01)=
where the inequality is by Lemma A. 10 and the equality is because both O, and Ô lie in B(0g.w). These facts imply that each entry of VV.(().) V.V ((ooid))) - Ō.) is upper-bounded by
18

---

Published as a conference paper at ICLR 2023
(m5) and each entry of V(O)) V(ê.) is upper-bounded by O(1). With this fact,
(0: 0.) (0:)
=0A - 8.) (VoV(()) - VoV(OT"))"" II(())-))((()))) - v(,.))
<(1 + 700
<m 0.5).
where the equality by Eq. 11 and the first inequality is by setting x to be (VeV(o,)
VaV (oV())))) - 0.), to be ((,)) - V(.) in Lemma A.5
To bound (0, - 0.)"
(0: 0.)² (B.)
(0, 0.) VoV D(pP D(P-
5(1 (eee))
20(c),
where the equality is by Eq.
12) and the first inequality is by setting x to be (0) - 0.), y to
be V+ in Lemma A.5 as each entry of (oV(0.) - 0.) is bounded by O(1) using Lemma
and each entry of V is bounded by e using Assumption
Combining the above facts,
2a, - (())) S -V0)) O(ammm 0.5
1..5.0 +c)),
which is the bound of the first part in Eq. 16..
Second, we consider af (0))) By Lemma A.12
1 7)2 Oaa)).
a < O(afee) +
The above facts are all we need to establish the result when each 8, is sampled i.idd. from In summary,
(0, - 0.)² + + a -V v(.))
1 0(a)),
+ +0 + e)) + O(afe?) + (1 フ)² O(a
which just simply combines the bound for 20, - -0.) and at lg) we obtained earlier.
Given 8r, taking expectation both sides of 16)
0 0.
< 10 0.112 + 20, - ((o (0, -0)))l(0()))))) - -((0))
=|10: 0.112 20r 0.)g(0.) + (00)11
0.5 + e)) + +(a36)) < 00 0.112 2o. - ((.)) + (m.(m 0.5
+ (1 (1-7)² Oaa)):
1
where the equality uses the condition that given s are sampled i.i.d. from μ4, which will lead to E[g(6,) g (6.) = 0. From now on we fix a, = and this leads to
E | 0.1131 B 0.1 <
1 O(a).
(m
2a
2a
(1-
Telescoping from 1 to T and dividing both sides by T. establish the result in i.idd case.
To continue with the non i.i.d. case, need to consider 2a(0, (g)T(g(()) g(f))) in 1 which is no longer We will use Tmixe the mixing time defined in Eq.(3). to split it into two terms and bound them separately. This idea is from Sun al. (0018)
19

---

Published as a conference paper at ICLR 2023
Our first step is to divide it into two terms:
(0, - (g(()) 0(0))) = 2a(0; 6 m (g(6,) - -((()) + -2( rmix (o))))))) -0(6)),
(17)
To bound 2x(00, - -w
-wix (.,),) ((0r)), notice that Lemma A.12 implies ||g(0:)11 < O(e) +
1-7 ((1). As consequence Eq. we have
|10, - 0 0 || S 1 0, m + ag(O:-1)]
1--2 m (9(0)-1) + g(0c-2)]
0 Taii
Oe Tmix + (0(( + g(0(_2) +... + 0(01-7mm)
Tani
((c) + 1-7 0(1) OfF
1
Further, the same upper bound that ((0)) has holds for g(0+) since g(o:) = E[]((.)]. These obser- vations imply that
20( - 01 (g(0)) - g(0,)) S raix (o(2)+ + (1 (1-1)-0))) om)
To bound
(g(()) -((,)) observe that, conditioned on - the quantity ) 0 (mmiix can be bounded by
O, 0miix 0, is deterministic, and (0)) g(O,)
E[g(O,) - -(0)))0 Tanx
O(c) + 1-y O(1) max ||
AIITV
O(e) + 1 (1)
Cmix-
The first inequality follows because, conditional 8 -mmi the random variable s; has the distribu- tion of one row of prmix Thus, the second term in Eq, (1) can bounded as
[f2ax(0: (g(()) g(0))) E[E[2o (1tmmi (g)((())) g(O.))
(((c) 1-7 0(1)
acmix
Thus, coming back to Eq. 17). we obtain that
E[2a((0. ([2a((0.-0.))) -.))( g(0))) a² Tmix [o(2) +
1
0(1) 2(1) + 1o-ooo+1--0 1-7 0(1)
1 0(1) acmix-
(1 (1-2 7)² (1-
log
Now let emix = a, by the definition of Tmixx Tmix we derive
Using the fact that log x S x- 1, Vx > O.
Tog p
log
log
log C
log 3
3
where the first incquality is because log 3 1 3 - 1 < 0 and log oh < 0. The bound can be rewritten as
log C
1 O + (1- o + [ole) + 1-7 o a².
1
E|2a, - (a)) - (00(())))g(()))) s a²
I
Now are ready to consider Eq. 16. Taking expectation on both sides,
E[2a(00, g())) a a (1)))11)
1
S - 2-2aN(V(8))
- v(.)) ((a(m u.5 + +c))+0(aa²)) + (1 - 7)2 0(a²)
log C (((2+ (1- 7)2 om) + [o(o+ 1
a 1- 8
1-9 0(1)
a²
1
= --2) v(O.)) + (a(m 0.5 +e)) + +aa2²²))
+
(1 (1- O(a?)
log C
1
log C
+(aa 2 1-
2) +
O
(1 )
1- 3
20

---

Published as a conference paper at ICLR 2023
Rewrite this inequality
E 0141 0.1
E[] 0 0_
2x
2a
-VV(V( v((=)) O(m 00.5 c) + 0(ac)) (1 71- ((a)
+ 0(a log 2 + (1 (1-7) 0 log
3
B
Telescoping sum from 1 to T and dividing both sides by T, we establish the result in non the i.d.
case.
21

---

Published as a conference paper at ICLR 2023
B ANALYSIS OF UNPROJECTED TD LEARNING - PROOF OF OUR CONJECTURE FOR THE SINGLE HIDDEN LAYER CASE
B.1 RESULT WITHOUT PROJECTION
Here we prove that when the distance from the optimal solution is O(ym), unprojected TD learning converges with high probability. We begin by standardizing notation.
Recall g(,)) is defined by
g(O+) VoV
where
8, r(s) + V (s'' (,) V(s, 0t). Without projection, there is only one step in the algorithm, which is
0.+1 02 (g.)
We call this algorithm Non Projected Neural TD Learning. Similarly to the way we proceeded earlier in this paper, Non Projected Neural TD Learning with mean-path update is given by
0.+1 = 0g + aig(f)).
We will need to make the following assumption on exact approximation, which is stronger than what we assumed in the projected case.
Assumption B.1. There exists some 0, such that V(0O) V*.
Now, for simplicity of notations, we also introduce the following notation. Remember the smallest eigenvalue Amin of some matrix A is defined
||Ax||
Amin (A) = arg min
||]|||
A similar way can be applied to define the smallest 2, D eigenvalue o 2.D of matrix A:
||Ax||o
o min (A) = arg min
|
For simplicity, we will use min to denote the 2, D eigenvalue of VgV(
We will always suppose each s; is sampled i.idd from p. We now introduce the following result. Theorem B.1. In the Non Projected Neural TD learning using one hidden layer neural network, smooth and Lipschitz activation function, suppose each 8t are sampled i.i.d from J4, and stepsize chosen to be 0g X(1-13. Further, let A be the event
2(1 (o - + 72)
A
sup X.
m
0.5
4(1 + 7)col
and assume
22 - (0 2,D 334 72)) )
E [1000 - 1
m8 2.
64(1 + 72
Then, A happens with probability at least 1 8 and the sequence { [110 -0. 0= converges
B.2 USEFUL LEMMAS
Lemma B.I. (0, 0-) g(O)) can be rewritten
(0. 0.)² g(.)) ği (0.) (2().) (z()),,
where (0)) (..)).z(()))
(0)). (Ot) are defined as follows:
91 (0.) (0. 0-) VoV - 0.).
(18)
22

---

Published as a conference paper at ICLR 2023
02(0,) = (V.V0) - - - V(0.)),
-V())))
(19)
]2(O,) = (O. D(
VoV 0.).
(20)
Here, 22 [0, is scalar and 0g X20 + (1 12)00 is vector such that (0, 0.) = -0--0-1 -((.))
(0.-0.)
Proof. First, we divide (0: 0.)" g(o)) into two parts.
(0, - 0.) g(O,) = v. D(TP ()(()))) - V(O.))
(0: (Q.- D(>P -V((0)))V(()))
= (0,- (0.- VoV(O.))
().) + (00=-0))(TT00))-<_000))))2)2)"2) (()))))((())))-- -))( v(0.))
(0(V()))((()))))))) +2
where the first equality is by the definition of ((.)) in 7.. Now let (0,
I) be the vector in Lemma A.2 There exists a scalar 22 [0. 1] and a vector Ornid A20: + (1- A2) such that
= -0-- Using this fact, - (0--000"TT((0000-----00000000000 ((.)) can be divided by
(0,-0.)² (0--,//(kk000))0p---VVV000-0-0
+ (0: - -.2" VoV -00 0.)
+..00.))9a(00)
Lemma B.2. If the activation function is 1-Lipschitzz and cg-smooth, for any 8, O1 and Oz the in- equalities
[[VaV(s, -oV 02)1 S com V 01)1 <
-0.5 -0.$110 0211.
hold where C1 is a scalar that is independent of m and
Proof. Using the definition of neural network in Section 2.4, one hidden layer neural network would be simplified as
1
V(s,0) = vm
b, 0 s).
is easy to see that
VoV(s, - 1b o' 0010 s)s
b (0 s)s
Suppose the activation function is -mooohh.. That is, for any a and
[1o'(x) - d'('lll S collx y|l.
This means
1 - ||b (o' (0) 5) 0' (0) 8)) .... ,m. (o'(0m:T s) o' (((or"Ts))s sT)
||VoV VoV(s,02)1
||s|| s) - o' 10 s))2
||s|| 2 r5 s)
m
||0||$2|11 2010 0/
2
10 0211
23

---

Published as a conference paper at ICLR 2023
which proves the first part of the lemma. Now let us move on to the second part of the lemma. By Lipschitzness,
VV 01)11
|| 1 (0) s)s" :.. "...,bm (' s)s"11"
[s s))2
m
1
12
Now finish the second part of the lemma.
Lemma B.3. The following inequality holds:
N(VoV(O.)) -0.)
2 (0 2..D)
10 0.
Proof. To begin with, the definition of / is
N(VoV(O.) 0.)) = (1 - V VoV 0.)1 VVVoo -.)1lBir
2 (1 - 7) VoV 0.)I
Using the definition of min.
N(VoV(O.) 0.))
VoV(8.) 0-)1B
2 (1 - 7)
- 10-22
110 - 0.
2 (1 (02.)
which establishes the result.
Lemma B.4. If a non negative sequence {X+} satisfies
X S (1
]x,
1+1
(1 + 1)2
for some b, c >>>> 0, then the sequence {X.} converges
Proof. Recursively applying the relation between X and Xt, we can derive the following:
X,
b
II (1
II 9Xx.
(21)
The first term in Eq. 21 definitely goes to 0 as goes to infinity. Now let us consider the term I1 9). A logarithm usually helps to convert it into sum, so we perform the following
manipulations:
Σ In(1 In(1 - 9-- Σ c
c(In(i + 1) - In(1 + 1)),
j
#=
#=1+1
where the first incquality uses the fact In(1 x) I x and the second inequality uses Ej=it In(t + 1) In(i + 1). So,
II (1 9)= - j=i+1
Eham (n In(1-)) s cln #t
(i + 1)
(1 + 11c
24

---

Published as a conference paper at ICLR 2023
By setting i = 0, this means the third term in Eq.
21) goes to 0 as goes to infinity. Now consider
Σ [1 f). obtain
II
(1-
(i+
1)
(++ 1)
j2
j=+1
4b
t-1
11+
(t + 1)
==1
4b
4b
J (i+
(t 1)
(++1))
(++1)²
where the second inequality uses the fact
2 Σ 4 for all positive integer i, and the third inequality
combine the two facts E1 + 1jo-2 v 5/ + 1) [/ + 1) given e 2 and
(i - f (i 1)0-2-2 v
2 given e < 2. If c # 1, then
(1 (1-}) 9) 1)
46
46
+
1)
j=i+1
If c = 1, then
1-1 Σ3
b (1 In(t + 1) 1ln
11
1=+t1
Under both cases, we can easily argue that the second term in Eq. 21 goes to 0.
Now, we have proved that all three terms in the right hand side of Eq. 21 go to 0 as goes to infinity. This directly implies {X,} converges O.
Lemma B.S. (Optional Stopping Theorem) Suppose {Xt) is super martingale and T is stop-
ping time. If there exists a constant e such that X S e holds for all T, then we have
E[X,] < E[X.].
This is also called Doob's Optional Stopping Theorem. See Theorem 10.10 of Williams 1991]
B.3 PROOF OF LEMMA B.1
Consider Non Projected Neural TD Learning,
||0+11 0- ||0: 0, + ())())))
= ||0: - 0. 2 + 2a, 0.) g(0.) + a
Given 0,, the only randomness is from st. Taking expectation on both side and using the fact that Elg(O.)] = ((0z) (since we assume 8, are sampled i.i.d. from μ1), we obtain
E [1| 0- 10 = 110 0. + (0, - 0.) g(())) + af [1la(0))
(22)
First, we consider 20x, 0,, (.)TT((,) Lemma B.1 allows us to divide it into several parts and thus we can bound them respectively:
+ 20x - 0.)TT (0.) = 20, (0.( (2.) + (O.)).
To bound Ti (0.).
ō1 (8.) =(9, (0- ". -8.)
= - 8.))
5- -1 (
where the first equality is because the definition of 9 (0,) in Eq.
18), the second equality is by setting Vo (0.)( 0.) in Lemma and the inequality is by Lemma B.3
25

---

Published as a conference paper at ICLR 2023
To bound (2(()),
92 = - - v(O.))
5/100: - -0.)--V0VV - DPV()))
+ (0)
- [
71c0lmm
0.11,,
where the equality is because the definition of (2)) in Eq. 19 the first inequality is by triangle
inequality which says I yl S | + yl. and the second inequality is by setting z to be (B)
(o. (0, - ).), y to be (().) - (Ō.) in Lemma A.5 with each entry of æ, y bounded by
com 0.5 |0 - 0-112, 0l00: 0.1l respectively using Lemma B.2
To bound ãa (O+).
(0,) (0, 0.)
( VoV(O))) - 0.)
s (/0 0.) ".)" (oV - 0.)
( ",0,
voV(6.)) 0.)
(1++7))mmmm-m0)1 03
where the equality is because of the definition of ga (0,) in 20), the first inequality is because of the triangle inequality, and the second inequality is by setting x to be (VoV(egii) (0. [)
0.), y to be (0.) 9.) in Lemma A.5 with each entry of x, y bounded by cym 063 f. 11?
2116- - 0_11 respectively using Lemma B.2
Combine the above facts and we now have the bound for the second term in the right hand side of Eq. (2).
20.(0, - (a.(0....)" ((.)) S -2as - (o - 0. 1|2 4cx (1 + 7)col -055 - 0.11².
Second, we consider E[a""] (0.) in Eq. 22 22)
For simplicity, define f(s) = (8,,0.)VV(6 0z).
Since are using one hidden layer neural network to approximate V(s, 0).
| = (v 0.) Vs))
(0((5)))) o (((rs))
m
(1)) s01
P110 01
Σ 11107 8:11
= e 10, - 1.
Recall that 0s) satisfies Eq. which is
V(s, 0.) = r(s) + Σ P(s" 0.),
and (0,) is defined to be g(O,) = (s, 0.) (rss +>V 0,) V(s, 0t)]. This latter immedi- ately implies that g(0,) is actually a random variable and implicitly relies on the state 8. Using these facts, we obtain
g(0)) VoV (ra) +~V((+ (s.
[()) ())
Σ P(<')s))((')) + EP66100166
26

---

Published as a conference paper at ICLR 2023
By 2) we obtain the following quick result:
(V) - v(s" 2r max
1-7
And this leads to the following:
Vo (oV(s, 0.) f(s) -7 7 P(s"(s))f()) +2 [((s")s)(V(''))) v(s" v(s",
<3 (oV
[f($) + P(( + (VV)) v 0.))
V3
[f(()] + Σ (()(s)) P(s" -()
<3(1 +3(1+73)011 -0.112+ + 71-
(23)
where the first inequality uses the fact that (a + b + c)² S 3(a² + 62 + c²), the second inequality by Jensen's inequality, and the third inequality simply uses Lemma B.2 to bound || (o Further,
122 [11(0)0)) (l 0.112
(1 - 7)
Now let us go back to Eq.22) (2 where the second and third terms on the right hand side can be bounded by
20, (()(0--.)- ((,)) + af (1lg [119(0.)11
5 - 20,0 - (o
2.D 2 0.112 + 41, + 7)olm -0.5 - 01
+ +30 + 11 - + 222
(1 (1-7)²
( (-2 - (0) + 30 + +72)74) 110: - 1_11
=
+ 40r + 7)colm 0.0 0.113 + 72 maax
(1-7)²
This means
E [1 - 0.11310.]
< (1 20 - 2iDo2 + +1
+g2)11) (110))=)1100---111 (007)110--011 1
(24)
+ (1+ + 7)cmlm 0.5 0,113 ?2a,???? max
(1 (1-
27

---

Published as a conference paper at ICLR 2023
For simplicity, we define the following notations:
X, =110, - 0-11,
C 12 2 max
(2 - 7)
00 A(t + 1)²
0. 20x (1 (7) 22:)) -30 (1 + 72)1.
b. 41, + 7yym -0.5
12a max
C
C2 (1- 71
(t 1)
de C
(while do is defined be do 2).
We can rewrite Eq. 24
EP X X1]
X + ct: (2 (o 2. 11+
$ (1
while the condition E [1100 13]
md 2 is just
04(1+77)-ff-5*
0g - dg.
E x S
4b/
Under such notations, an important fact is that
C S dg - dz+1-
This can be showed casily since (1+1)=
S 1 1+I
1
If we define the stopping time T inf 2
eo
and the sequence (Y,} to be
2n,
(x + de
i
Yi
Yr-1
ift
Now we first claim that the sequence {Yi} is super martingale. We show this as follows:
Suppose T O, and we find that Y; Yo, Vt. this trivial case, obviously, (Yi is super martingale. Now we assume T > O.
When we have
X| S (1
2 2an)xz co X + + Xx + di.
which means Y| < Yo.
For S T, by the definition of T we know that X,
S do which implies that X. S dr 2h
(this
26,
because by the definition of a and be, h((t) = an is increasing with t). Hence, 2h,
X,] S (1 2 xx) + x2+a S X2 d. d+11-
which means B M Y.
For > T. by the definition of {Yi} we know that Y, = Yy.
Hence, combine all the above facts and conclude the sequence (Y,) is super martingale.
Next, we claim that X, <
an 2bp
holds with probability at least 1 8. This can be shown as follows:
Let A be the event sup, X, < 2bp
No
X1
20g }.
To compute P(A), notice
that
Xo < ag
X1 < ag
20 :....
P
Yo
<
4
+ do Y1 <
2
+ d1, ....)
20p
4b2
462
28

---

Published as a conference paper at ICLR 2023
We can easily check that T is also stopping time for {Yi). In order use Lemma B.5 need to check the conditions that |Yr| S c for some constant c. We split it into two cases.
First, 7 T, then AAT |r Because of the definition of I'' we know that
dg +
d 4
|+ I
+ 2,
40g
where we use the fact that {de} is a decreasing sequence and do = 2. Second, if r 2 T, then [Y^r Yrl. Recall that update of the algorithm is
Oc+1 02 + arg((.).
which implies
|10++1 - 0 1 110 0 || + az ((())
Now we let = T and use X, notations. The above fact can rewritten as
|X S |Xr-1l + a ar-1ll9(0r-)))
Because of the definition T, we know that |Xy-1| S
22. 2ho
Moreover, Eq. give us a bound for
(0) which is (19(Or-1)ll < /3(1 + -2)
12
(1->)- Finally, ar-1 is set to be
X(++J so is obviously bounded. All these facts lead to the result that |Yr] is bounded.
Combining the above two cases, we are now eligible to use Lemma B.5 Hence, we obtain
E[Y,AT] S [[)...
On the other hand, B[Y FATT can be expanded
< + r|P(T Ely = P(T S EY
Combining these two facts,
E|Yo 2 E[TT) T)
a
2
+
dr
P(T $ T)
4bg
2
where the second inequality using the fact that Yz >
dr. Hence,
4bg
P(T 5T) Y
E[XØ]
+ do
E + do
< 8.
ag
+
dr
+ dr
46
45g
48
where the equality is because [(YY = F[ +o. the second inequality is because d, is nonnegtive, aa
and the third inequality is because of the condition [[X3]
<
8 - do. Next, is easy to see
46g
of do, Y1
af
of dr
P
Yo
+ d1,
Y,
P(T 7) = = - P(T T) 2 5.
4b²
4bg
4b²
This result holds for all r, so we can let 7 and obtain
P(A) 8-8.
Actually, using A(() is monotonically increase with again, event A implies X, With this fact,
8r VL.
2b,
2b.
x E
A < (1- at + x,xx) + s (1 -2)))))))) ax)x + +a, Vt.
29

---

Published as a conference paper at ICLR 2023
Plugging in oz = 20x(11 - (omin)) - 300(1 + 722)1, c2 derive
1 mma and ar X(++1)* we can (1 (1-2)²
(1 () 2
3(1 + 7²
X² + 12 max
E
X1, A S
A(t
2t + 1)²
(1 +
(1-7)m² (o
Given that X₂
da 2bg
Hence, we conclude
2(147)ool
(1 (2?
3(1 + 2,D 2,D) min
) m
12 max (1 (12 + 1)2
X2 |1
X2 Al $
x²+
A(t 1)
Take expectation both sides and we derive
(1 (o X(t 1)
B| 3(1 7 min
12 max (1 (1-7)8A2(1 + 1)2²
E
[1144 S
7) 1)²
By Lemma B.4 we conclude that the sequence (E [XX[A]} converges to
30


Reviews:
[{"review_id": "mkVq_6dYy17", "reviewer": "Reviewer_oRiv", "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 provides a convergence analysis of projected Neural TD - Temporal Difference learning using a neural network for function approximation, and a projection step onto a norm ball of fixed radius around the initial iterate. The authors show sublinear convergence with an approximation error of $\\mathcal{O}(\\epsilon + \\frac{1}{\\sqrt{m}})$, where $m$ is the width of all hidden layers of the network. The paper mainly builds on the idea of ``gradient splitting'' which was previously used to analyze TD learning with linear function approximation [Liu and Olshevsky, 2021].  ", "summary_of_the_review": "I am inclined to recommend accepting this work conditional on the authors putting their results in better perspective as compared to prior work as well as improving proofs in the Appendix.", "strength_and_weaknesses": "I find the analysis and results of the paper interesting - quantifying the first order progress term using arguments from gradient splitting is a good idea. However, I feel the extension from linear -> neural network function approximation is fairly straightforward from a technical point of view. Straightforward extensions can make for good papers - my main complaint is that the authors need to do a much better job of putting their contributions in perspective of prior results. Some comments:\n\n1) The three relevant papers are Cai et. al. (2019), Xu and Gu (2020) and Cayci et. al. (2021). The authors reference problems in that analysis - that the projection radius needs to shrink at a rate of $\\mathcal{O}(m^{-1/2})$ -- but don't specifically compare the results in these papers to their results presented in Theorem 1. \n\nMy understanding is that most of these papers also characterize the quality of solutions that Neural TD converges to - for example, see section 4 in Cai et. al. (2019) - the approximation error here may be non-vanishing but there is a characterization of the limit point in terms of the solutions of the projected Bellman equation. The results in Cayci et. al. (2021) seems stronger. In addition to provide a projection free analysis, they also give guidance about scaling the network width for a given value of target error. It seems that in their results, $\\epsilon$ can be arbitrary large and there is now guidance on how to select $\\omega$. \n\nI request the authors to provide a more detailed, clear and transparent comparison to past work - highlighting the strengths and weaknesses of their approach as well as results vis-a-vis past work. That would be immensely useful. Maybe an empirical comparison to projection free and max-norm scaling methods of Cayci et. al. (2021) is also useful. \n\n2) While the main paper is well written, I think the Appendix requires some work in clear writing. Instead of saying 'By Lemma A.5 and eq(13)' can you kindly write out each expression and bound term by term? Can the equations be properly numbered to show how '$g(\\theta_t)$ can be rewritten as' .. Similar comments go for the proof of non i.i.d case. I assume most inequalities to be correct (since the resulting bounds make sense), I don't think these have been properly justified. I think it is really bad to put the onus on reviewers to parse badly written proofs - the burden must be on the authors to write in a clear and easy to follow manner.\n\n\n ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "kvR4vtKhgl", "reviewer": "Reviewer_SRvC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 provides a convergence analysis of Neural TD Learning with a projection onto a ball of fixed radius around the initial point. ", "summary_of_the_review": "The paper seems to contain interesting results. \nHowever, some assumptions are strong to be practical, and some convergence results need to be clarified more as indicated in my previous comments. ", "strength_and_weaknesses": "The paper provides some new results on the convergence of TD learnign with neural network. \nThe results seem interesting. \nWeaknesses of the paper are summarized as follows:\n1) The definition of semi-norm in eq (5) is not defined. \nMoreover, the definition caligraphic N would not be a norm. It is a semi-norm.\nSome discusssions would be needed. \n2) In the definition of fully connected neural network, is there a bias term? Usually, NN has bias parameter in each layer. \nIt should be clarified.\n3) It is not discussed why the final weight b is fixed. \n4) Assumption 2.4. requires that activation function is l-Lipschitz. However, to my knowledge, most popular activation functions are not globally Lipschitz. \nSome discusssions would be needed. \n5) In the result of Theorem 3.1, caligraphic N is not a norm. Therefore, we may not have any useful convergence result using the semi-norm because semi-norm may be zero for nonzero input. \n6) Moreover, in the left-hand side, the average cannot go inside the V since it is nonlinear. Then how can we derive a conclusion for theta_t?\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "djbLOn0XlmS", "reviewer": "Reviewer_ZfL8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "Authors derived a new bound for Neural TD projecting for a fixed policy using arbitrary set of layers within the ball with radius \\omega around a starting parameter \\theta_0. They showed that the approximation error is bounded by O(\\epsilon + 1 / \\sqrt(m)) where m is the width of the neural network and \\epsilon is the approximation quality of the best neural network within that ball. The main advantage of the new theorem is that it relaxed four conditions of the previous proofs: 1) small projection radius, 2) linearization around the initial condition, 3) restriction on policies, and 4) limited to a single layer network. Authors provided insight on the effect of m by running experiments for policy evaluation across three toy domains with both a random and well-trained policies.", "summary_of_the_review": "Overall a great and well-written paper with a major theoretical step.", "strength_and_weaknesses": "Strengths:\n+ Given the wide usage of neural TD this paper provides a great contribution for the community\n+ The paper is well-written overall while being a theoretical paper\n\nWeaknesses\n- More tips around the applicability of the theorems to practitioners would have been great. For example ReLU, a widely used function, does not satisfy the assumption of the theorem.\n- I could not find the constant value of the omega for the results shown.\n\n\nMinor errors:\nPage 2: pi(s,a) -> \\pi (s,a)\nPage 4: \\sigma is and activation -> \\sigma is an activation", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Wfhz4LtzbgC", "reviewer": "Reviewer_bfdn", "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 studies the convergence of the temporal-difference (TD) algorithm with overparametrized neural networks. Compared with previous works, it weakens the projection step radius to a constant level by using a different analyzing techniques. The paper also provides simulation results to support the theories.", "summary_of_the_review": "The paper uses novel techniques to modify the previous analysis of the global convergence of neural TD. The reviewer believes that the result, although not quite strong, is helpful to the understanding of such a problem. ", "strength_and_weaknesses": "Strength: the paper uses new techniques to analyze the convergence of neural TD. In particular, it utilize a combination of D-norm and Dirichlet norm to characterize the distance to the true value function. The reviewer believes that the analysis brings insight to the reinforcement learning community.\n\nWeakness: The theoretical result seems a weak increment. It is not clear why changing the projection radius to constant can help the TD learning in practice. In fact, since the essential models considered are still linear models implied by the neural tangent kernel (NTK), the generalization error will be the same as the settings of previous neural TD works. From the computation cost perspective, it will be more interesting if the authors can show that the projection step can be totally discarded (just as most NTK works on supervised works do).", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster