A Non-asymptotic Analysis of Non-parametric Temporal-Difference Learning
Authors: Eloïse Berthier
Ziad Kobeissi
Francis Bach
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
temporal-difference learning
non-parametric
kernel methods
convergence
policy evaluation

Abstract: Temporal-difference learning is a popular algorithm for policy evaluation. In this paper, we study the convergence of the regularized non-parametric TD(0) algorithm, in both the independent and Markovian observation settings. In particular, when TD is performed in a universal reproducing kernel Hilbert space (RKHS), we prove convergence of the averaged iterates to the optimal value function, even when it does not belong to the RKHS. We provide explicit convergence rates that depend on a source condition relating the regularity of the optimal value function to the RKHS. We illustrate this convergence numerically on a simple continuous-state Markov reward process.

A Non-asymptotic Analysis of Non-parametric Temporal-Difference Learning
Eloïse Berthier
Ziad Kobeissi Institut Louis Bachelier
Inria & Ecole Normale Supérieure
PSL Research University, Paris, France
Inria Paris
ziad. www.kebeseiiiii. @inria. fr
Francis Bach
Inria Ecole Normale Supérieure PSL Research University, Paris, France francis bach@inria.fr
Abstract
Temporal-difference learning is popular algorithm for policy evaluation. In this paper, we study the convergence the regularized non-parametric TD(0) algorithm, in both the independent and Markovian observation settings. In particular, when TD is performed in universal reproducing kernel Hilbert space (RKHS), we prove convergence of the averaged iterates to the optimal value function, even when it does not belong the RKHS. We provide explicit convergence rates that depend a source condition relating the regularity of the optimal value function to the RKHS. We illustrate this convergence numerically on a simple continuous- state Markov reward process.
Introduction
One of the main ingredients of reinforcement learning (RI) is the ability to estimate the long-term effect on future rewards of employing given policy. This building block, known policy evaluation. already contains crucial features of more complex RL algorithms, such as SARSA or Q-learning [64]. Temporal-difference learning (TD), proposed by [62], is among the simplest algorithms for policy evaluation. The estimation of the performance of the policy is made through a value function. is updated online, after each new observation of couple composed of state transition and reward.
Although the formulation of TD is quite natural, its theoretical analysis has proved more challenging, it combines two difficulties. The first one is that TD bootstraps, in the sense that uses its previous possibly inaccurate predictions to correct its next predictions, because it does not produced
have access fixed ground truth. The second difficulty is that the observations along trajectory following a fixed policy (on-policy), hence they are correlated, which calls for more involved stochastic approximation tools compared to independent identically distributed (i.i.d)) samples. Moreover, using off-policy samples, produced by different policy than the one being evaluated, can make the algorithm diverge [16]. Off-policy sampling out of scope in this paper.
third element which is not inherent to TD further complicates the plot: function approximation. While TD was originally proposed in tabular setting, its large-scale applicability has been greatly extended by its combination with parametric function approximation [17]. This enables the use of any linear or non-linear function approximation method to model the value function, including neural networks. However, one can exhibit unstable diverging behaviors of TD even with simple non-linear approximation schemes [66]. This combination of difficulties (even with linear function approxima-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

tion) has been coined the "deadly triad" by [63]. We argue that convergence can be obtained even with non-linean function approximation. by making use of the non- non-parametric formalism of reproducing kernel Hilbert spaces (RKHS), involving linear approximation in infinite-dmmnnsinn. Studying this case could bring us closer to understanding what happens with other universal approximators used in practice, like neural networks.
1.1 Contributions
We study the policy evaluation algorithm TD(0) in the non-parametric case, first when the observations sampled i..dd from the invariant distribution of the Markov chain resulting from the evaluated policy, and then when they are collected from a trajectory of the Markov chain with geometric mixing. In that sense we follow similar outline as the analysis of [10] which is dedicated to the linear case.
The non parametric formulation of TD closes the gap between the original tabular formulation and the parametric formulation which involves semi-gradients. It allows the use of classical tools and theory from kernel methods [22]. In particular, we highlight the central role of covariance operators [5, 2] which already appear in the analysis of other non- con-paameetri algorithms, like least-squares regression. We study a regularized variant of TD, a widely used way of dealing with misspecification in regression. Importantly, when the regularized TD approximation is run on an infiniteddimensionall RKHS which is dense in the space of square-integrable functions, then there is no approximation error and the algorithm converges the true value function. More precisely, we provide proof of convergence in expectation of TD without approximation error, even when the true value function does not belong to the RKHS, under a weaker source condition. Furthermore, we give non-asymptotic convergence rates related to this source condition, which measures the regularity of the true value function relative to the RKHS, e.g., its smoothness if the RKHS is a Sobolev space [51].
Note that using universal kernel [48] to obtain convergence of TD to the true value function is also interesting from a theoretical point of view. Indeed it exempts us from a possibly tedious study of the approximation (or projection) error on a given basis, and simply removes an error term which in general scales linearly with the horizon of the Markov reward process [49, 70].
In the rest of this section, we review the related literature. In Sec. 2, we present the algorithm, along with generic results and notations. In Sec. 3, we analyze simplified version of the algorithm, namely population TD in continuous time. This allows to catch the main features of the analysis, while postponing the technicalities related to stochastic approximation. Sec. 4 dedicated to the analysis of non-parametric TD with i.i.d. observations, while Sec. 5 consists in similar analysis for correlated observations sampled from a geometrically mixing Markov chain. Finally, in Sec. 6, we present simple numerical simulations illustrating the convergence results and the role the main parameters.
1.2 Related literature
Temporal-difference learning. The TD algorithm was introduced in its tabular version by [62], with first convergence result for lincarly independent features, later extended to dependent features by [27]. Further stochastic approximation results were proposed by [41] for the tabular case, and by [58] for the linear approximation case. An exact analysis of the behavior of tabular TD was recently carried out by [40], using the framework of Markov jump linear systems. [66] provided a thorough asymptotic analysis of TD with linear function approximation, while failure cases were already known [4]. A non-asymptotic analysis was later proposed by [45] in the i.i.d. sampling case with constant step size, concurrently to another approach extending to Markov sampling by [10]. Other problem-dependent bounds for linear TD were derived around the same period [26, 60], along with an analysis of variance-reduced TD [44, 69]. All of the analyses mentioned above focus either on the tabular or on the linear parametric TD algorithm. A recent work by [33] deals with the batch counterpart of non-parametrie TD, namely the least-squares TD algorithm (LSTD), but they rather focus on the analysis of the statistical estimation error. Importantly, LSTD only requires offline computations and is not related to stochastic approximation. Most closely related to our work is the non-pan non-paramttric regularized TD setting studied by [43]. However, their analysis is limited to the case where the optimal value function belongs to the RKHS. This is not sufficient to get rid of the approximation error term. Also, we will show later that regularization is not necessary in this case. Furthermore, their analysis is restricted to the i.i.d. setting, for which we will require fewer regularity assumptions. Finally, let us mention the recent work by [18] concerning TD with function

---

approximation using one-hidden layer neural network with finite-width, called 'neural TD". Since finite-width neural networks are not universal approximators, there an approximation error. which vanishes in the infinite-width limit if the value function belongs to a particular function space.
Kernel methods in RL. To tackle large-dimensional problems, kernel methods have been combined with various RL algorithms, including approximate dynamic programming [53, 11, 6, 38], policy evaluation [25]. policy iteration [36]. LSTD [33], the linear programming formulation of RL [29], upper confidence bound [32], fitted Q-iteration [47]. Such kernel methods often come along with practical ways to reduce the computational complexity that grows with the number of observed transitions and rewards [7, 43].
Stochastic approximation. The analysis of TD requires tools from stochastic approximation [8], among which the ODE method [13]. Such tools are primarily designed for finite-dimensional problems. Stochastic gradient descent (SGD) [15] is specific instance of stochastic approximation that has received extensive attention for supervised learning. particular, the role of regularization of SGD for least-squares regression has been studied [19, 24], as well as the effect of of sampling data from a Markov chain [50]. Finally, we use formalism which close to the analyses [31, 54, 9] of non- non-parametric SGD for least squares regression.
2
Problem formulation and generic results
2.1 The non-parametric TD()) algorithm
We consider a Markov reward process (MRP), i.e. Markov chain with reward associated to each state. This is what results from keeping the policy fixed in Markov decision process (MDP) for policy evaluation. We consider MRPs in discrete-time, not necessarily with a countable state space X. Specifically, we use the formalism of Markov chains on measurable state space, also called Harris chains, which unifies discrete- and continuous-state Markov chains. Formally, let X c. IR measurable set associated with the olalgebra A of Lebesgue measurable sets, Let (In)221 a time- hime-homogeneous Markov chain with Markov kernel τ. A Markov kernel [56, 42] is mapping X x A + [0, 1] that has the following two properties:
1. for every x E X, k(xx-) is probability measure on A, and
2. for every A E A, A(-:A) is A A-maasurable.
If X is a countable set, is represented by a transition matrix Q such that Qu, PP((i) x(1, (i), for any i X.
We define reward function X IR uniformly bounded by R oc, and discount fac- tor E [0, 1). The aim of policy evaluation is to compute the value function of the MRP:
+oc
Va E Ex V'(x) =
Σ 0
(((
20 x
(1)
where the (Ix)x21 are drawn from the Markov chain. A probability distribution p : A - IR is a stationary distribution for x if for all A E p(A) fxx <(x, A)p(dz). The existence and uniqueness of a stationary distribution P. along with the convergence of the Markov chain to p in total variation, is ensured by ergodicity conditions. A sufficient condition is that the Markov chain is Harris ergodic, i.e., it has a regeneration set, and is aperiodic and positively recurrent (see [1] and [35] for a complete exposition of Harris chains). For discrete-state Markov chains, ergodicity conditions somewhat more simply, and any aperiodic and positive recurrent Markov chain has unique invariant distribution. Throughout this paper, assume that p is the unique invariant distribution of the Markov chain, and that it has full support on X. Only in Sec. 5, we will in addition assume that the Markov chain is geometrically mixing.
be expressed
We define (p),,, the set of squared integrable functions f : X + R with respect to p. with the norm || ! = fx f p(d))) +oo. We also consider reproducing kernel Hilbert space Hi of A-measurable functions, associated to a pesitive-definite kernel K X - R. For all x E X, we use the notation ((x)= == K(x,)) -) for the mapping of in HC, and (:, +)c for the inner product in H
3

---

(we sometimes drop the index). We assume that Mx := suprer xx, is finite, which implies that DC c (p). More preciscly, the Io-norm controls the in H thus converges in (p). Indeed, f E JC:
any sequence converging
() / f(x)) = 1 (f.
& 11flB /10(=))B(dp())) S Mo I. (2)
We also assume that r E (p). The non parammeertii TD(O) algorithm in the RKHS H is defined follows [53, 43]. Draw sequence (In) according to the Markov chain with initial distribu- tion p. and collect the corresponding rewards (r(z)))n2 Define sequence of non-negative step sizes (Pa)n21- We build recursively a sequence of approximate value functions (V,)220 in (p))
Throughout the paper, we take Vo O for simplicity, but note that all the results can be adapted to the case Vo E H. For 2 1:
Vy E X,
Vv((y) v + pm [r(aw) +Vnn1(a4)) -vo- K K v).
(3)
where o/ == In+1- The term in brackets is called temporal-difference. Equivalently, in the RKHS:
V2 = Vn- + Pm [r(o.) + (Vn-1 - (Vn=(( (((n)
(4)
This update has a running time complexity of (n which can be improved to (n)) e.g. using Nyström approximation in App. B.2. This non- parpaaamettic formulation a natural extension of the tabular TD algorithm. Indeed, if X is countable set and K (a, y) 1m=y is a Dirac kernel a valid positive-defintte kernel - then we exactly recover tabular TD: the update rule (3) becomes, after observing a transition (i, r2) = (In, 2/y (x)))):
random features [39]. More details the implementation are given
= Vv- + Pm
po rr - - (i). and Vj i, V.(i) = vz) (5)
This also covers the semi remi-gradien formulation of TD for linear function approximation [64]. Sup- pose HC has finite dimension d, then V,, can be identified to & Rdd and we are searching for an approximation of the form V, (x) E.T (z). Then (4) becomes:
E. En-1 + Pn. (((x))) + ( ( VeVi Ve-
Since Vo E H. all the iterates Vn are in the RKHS, in particular V, E span (((x))(((s)sssss) Conse- quently, if the sequence (V,) converges in the topology induced by the L [p) it converges in H. the closure of H. with respect the (p))norm) In particular, for dense RKHS and because p has full support on X, H (p), but in general it only holds that H C (p).
To understand the behavior of the algorithm, we will first consider the population version (also called mean-path in [10]) of the algorithm: set Vo = 0 and for 2 1:
Vn Vn-1 + Pr y (1(x)) + (V')( Vn- (x))
where the expectation is taken with respect to ddr dz') == p(dr)((z, dz'). Since V E H, the reproducing property holds: (x) = (V ((x))a( Hence the update is affine and reads: V, Vn + (m.(A, + b), with A == E, (z) @ ((x')- (x)) @ ((x) and b= E, (z)))
where @ denotes the outer product in H defined by g 8 f (f, h)og..
2.2 Covariance operators
Assume that the expectations Σ = (x) @ P(x)] and Σ, := (<(((< @ D(x') are dellede E and Σn are the uncentered auto-covariance operators of order 0 and 1 of the Markov process (In)n21, under the invariant distribution p. They are operators from H to H, such that, for all
J.g E H. using the reproducing property:
(x](()))())] = [S, (z)))r(( ((x))a) = (f, E,la, (z)))c Eg) (z)((()((z)) = E, (()))r(() ((x))) (f. E, (F))) = Eig
(8)

---

In particular, for all X and f E H., (Ef)()) (i(v), Efix = Ex)x(xx) y)] and similarly, (E) [ (=')= (x (z..)) y)]. Following [31], Σ and Σn can therefore be extended to operators > and 2i from L3 (p) (p) defined by:
3: :H [ f(z) (z))((2) such that Vy X, (E (,I
(9)
E S + J1z ((2)) dr'), such that Vy E X, (Ei))v) (2,
These two operators are the building blocks of the TD iteration (7). In particular, A= Σ and b = r, the latter being valid for r E (p). With a slight abuse of notation, we denote simply as X, Σj the extended operators. Furthermore [31], Im( C H and 1 is an isometry from L (p) to H:
Ef
[
|/
(10)
The fact that p is stationary distribution for implies particular constraint linking 2 and E;: Lemma 1. There exists a unique bounded linear operator Σn : HC -> such that Σ₁ E1/2,, 11/ on H, and | llop S (ll llop the H-operator norm).
This results from an application of [5, Thm. 1], valid on H and extended by continuity to H. See also [37] for an exposition of cross-covariance operators specifically an RKHS. finite dimension, this is retrieved with generic results on positive semi-definite (PSD) matrices. Specifically, if C R the uncentered covariance matrix of the random variable (#(x), (xx)), when (x, x') ~ is:
Σ Σ
Σ
Using a classical condition on block matrices [12, Prop. 1.3.21, this matrix is PSD if and only if there exists a matrix ES such that |كك Ilop and Σ; / E1/2 (II |lop is also the spectral norm in this case). This corresponds to the fact that the Schur complement of a PSD block matrix is also PSD.
Assumptions on Σ and V*. We assume that x + K(x,, 2:) is uniformly bounded by Mac. There- fore, the eigenvalues Σ are upper-bounded. However, unlike [66] and [10], we do not assume them to be lower-bounded, i.e., Σ > 0 is not invertible in general. We will formulate our convergence results for two sets of assumptions. The first one recovers known results from [10] for linear function approximation. The second one assumes that V* verifies a source condition [30, Chap. 1]:
(A1) V* E E.,, H is finite-dimensional and Σ has full-rank; (A2) V* E /)/2((() for some 0 E (-1, 1] (and consequently, ||3 1/200/2>*ll> < +00), and H (p) (i.e., K is universal kernel).
In (A1), HC is mnite-dimensional because Σ cannot be simultancously compact (x + K(x,x) being uniformly bounded) and invertible in infinite-dimension [21]. Recalling the isometry prop- crty (10), the case 0 = -1 always holds in (A2) because V E L²(p) (which we prove in the next subsectioo)...........s The case 0 = 0 is equivalent to V E H. For 0 > O, it must be interpreted as: s.t.
+o: if V* & /2/2()(). Using universal approximation removes the need for projection operator on H, typically used for dimenioaimnsionnl function approximation, and hence there will be no projection error [66].
||>0///** 1B := [ s.t. V /// with |/-0//2"*|
2.3 Non-expansiveness of the Bellman operator
is known that the value function V* of the MRP a fixed point of the Bellman operator T., We define two operators P and T: (p) + (p) by, for V [2))), PV(x)) (x',)( V(x') and (v r(x) + PV)).. (x). Both operators can be expressed in terms of Σ and E, For V E T2)
ΣPV = E. (PP) = -, E.(+(=)V(('))=>>>> E,V {
(11)
ETV Ex E.V.
Lemma 2. For any V E Lp):): | (26) S Vile
5

---

This is direct reformulation of [66, Lemma 1], the proof of which is given in App. A.I. As stressed by [66], this strongly relies on the fact that p a stationary distribution of the Markov chain. implies that T is 7-contraction mapping on (p) and has as unique fixed point V*. One can check that if Σ is non-singular, Lemma 2 is exactly equivalent to ||-|//Σ,_~1/3] op I 1, that is, Lemma 1, Moreover, using Lemma 2, we obtain [[V)) S ||r| (a() /1 7) and V E (p))..
3 Analysis of a continuous-tine version of the population TD algorithm
Before considering regularized TD with stochastic samples, we look at simplified versions of the algorithm that momentarily remove the difficulties related to stochastic approximation. Specifically, we consider the population version of TD to capture a "mean" behavior, and a continuous-time algorithm to avoid choosing step sizes. Instead, we focus the role of the regularization parameter.
3.1 Existence of a fixed-point for regularized TD
For X 2 0, let us consider the regularized population recursion:
Vn V + Pa (yΣ) E XT)
(12)
If the TD iterations converge, their limit will be a solution of the regularized fixed-point equation:
Σr (yΣ1 ~
(13)
Proposition 1. 1f 751 E AI is non-singular on H and equation (13) admits unique solution VX in L (p),,, defined by VX (7211 -1r Funthemorr, VX E H and:
|Er|| VMollllla
|VA S
(14)
X
The proof is in App. A.2. Hence, for À > 0, the FC-norm of VX is always bounded, unlike ||V*|
3.2 Convergence of the regularized fixed point to the optimal value function
Recalling that V* E (p()), satisfies the relation TV* = V*, implying that ETV* ΣV* i.e., Σr + (7 - ΣトV* = 0. This unregularized fixed point equation possibly has other solutions, but K is universal kernel, as assumed by (A2), then Σ is injective [61] and V is the unique solution. Let us recall that (A2) does not imply that V has bounded H-norm. However, we can control the L (2())-non (p)-m of V V when À is small using the source condition (A2).
Proposition 2. Assume that X and assumption (A2). Then:
20+1
I|V
V (2200 S (1 7) E 0/21*11 1.
(15)
The proof in App. A.2 is inspired by similar results [19, 24] in the context of ridge regression (recovered for y = 0). Note that only [[V V (p) is controlled, not V* Consequently, we obtain the convergence of V V ('' when À O: the higher 0 is, the faster the rate of convergence. For universal Mercer kernels [23], if we drop the source condition (A2), using only the fact that V* (p) corresponding to 0 -1 in (A2) we can still prove that VX converges to 4 in 1.2 (p)-orm when À 0, but without explicit rate (see App. A.2, Cor. 1).
V*
3.3 Convergence of continuous-time population TD
Following the ordinary differential equation (ODE) method [13]. we study the continuous-time counterpart of the population iteration (12). At least formally, this consists in defining V.=V,(() for t and n(tt) satisfying t = Σnet) Pi. and letting p; tend to 0 for any i 2 1, where Va(e) is defined by recursion using (12). With a slight abuse of notation, we use the notation V; instead of V.. We then obtain the following ODE in H: Vo = 0 and for 2 0:
dVv
(A XI)V, + +b.
(16)

---

We can exhibit Lyapunov function for this dynamical system, see [59]. This implies that Vi converges to V when tends infinity, where V is defined in Prop. More precisely, for {-1,0), we define W the Lyapunov function, by (t) == 1 VX (please note that ( role W an index, not a power). (*(1) strictly decreases with as follows:
Lemma (Descent Lemma). For À > for all t O, the following holds:
(t S --- (t).
(17)
The proof (see App. A.2) mainly relies on the contraction property of the Bellman operator as expressed in Lemma 2. We can then deduce the convergence of the ODE (16) to VX-
Proposition Under assumption (A1), the solution V₂ of the ODE (16) with À = 0 is such that:
For T> 0, I - V' S
(18)
2(1 -7 T
where V the Polyak-Rupper average [55] of Vo, defined by V = + So Vidl.
Under assumption (A2), the solution Ve of the ODE (16) with X > O is such that:
For T 2 0,
V| 11 S V 1 2AT
(19)
Under (A1), we recover the same O1//T) convergence rate as [10]. We focus on (A2), where we get a fast convergence to V in H-norm (stronger than (p)). However, we are rather interested in convergence to V*, Prop. 2 quantifies how far V is from V Indeed, the error decomposes as:
||T V V" 2M V 1b:c 2 - V V*
(20)
Combining Propositions 1, 2, shows a trade-off on A: || - 111 = O (e-2NT) /X² + x0+1). Taking (3 + log balances the terms up to logarithmic factors: 1|V V 21
Ô (T-1-0) (where (gg()) (g((n) log(n))), for some l E IR). In particular, for 0 ie., V* E HC we recover a convergence rate Ô (1/T): up to logarithmic factors, is the same as the unregularized case with averaging, assuming (A1). In this case, regularization brings no benefits.
4 Stochastic TD with i..dd sampling
We now consider stochastic TD iterations (4), where the couples (In, 2221 sampled i.i.d. from the distribution qdlx, dæ') = pl dz) (x dx'). Such i.i.d. samples can be obtained by running the Markov chain until it has mixed that 2,, ~ p. collecting couple (2n,2,), and restarting. With A, == (Ix)) & ((*,) - (xx,) 8 ((I,) and bn == r(E,, (I,), we study the recursion:
Vn Vn- + Pn((A, -
(21)
and A, and b, are independent of the past (V=)xen- For 8 E {0, 13, let W = | 12- V. Adapting the proof of Lemma 3, we exhibit similar decreasing behavior of W:O in expectation, hence showing that V, Vl + 0 for well-chosen step sizes Pr. Finally, À is chosen to balance [I[|V, V ( and ||V - V*Il?
In particular, F. [An] A, [,
We define Viee
and ( a as the exponentially-weighhe and the tail- -veraeedd n-th iterates respectively:
Vie) Eh (1 p\)n~*Vp-> Eh (1-A)-t
and y
1
Σ
V4-1-
(22)
n2 1n/2|
k=|n/2]
Theorem 1. Let 2 9. Under assumption (A2) with -1 < 0 < 1, there exist a positive real number Dg independent of n such that, for No 2 Ag.
(a) Using A= = don 358 and a constant step size p
log n An
then:
V V* 12 (1)
O(llog n)n 340
140
7

---

(b) Using À = Anni z=0 and a constant step size p
-nn" then:
log
An
(00 O(1og n)n 240
Lie
(c) Using À = Aon 240 and constant step size p= 2 lug then decreasing step size Ps=
for the first Ln/2] 1 iterates and An
XE> then:
E
V (1)))))))) O(log =
similar exponentially-weighedd averaging scheme as in (b) has been used study constant step size SGD in [28]. When 0, the rates can be compared to existing results for SGD. For example, for A [0, 1), [65] proves almost sure convergence for regularized least-mean-squares without 1+0
averaging at rate On 240) The dependence in 0 is similar to what we obtain. Moreover, under assumption (A1), we recover the same O(1/vn) convergence rate as [10] (see Prop. stated in App. A.3), Finally, our bounds have a polynomial dependence in the horizon 1/(1 - 7) of the MRP.
Remark. Because the Bellman operator also a contraction mapping in -orm this analysis in 7.2-norm might be adapted to the -orm, using modified Lyapunov function to study the ODE, e.g., following [14]. The stochastic case could be handled using the smoothing technique recently developed by [20].
Stochastic TD with Markovian sampling
We now consider the truly online TD algorithm, where the samples are produced by Markov chain. In particular, there is now a correlation between the current samples (mn, zn,) and the previous iterate - To control it, assume that the Markov chain mixes at uniform geometric rate: (A3)
3m > 0, E 10, s.t. sup drv (P(a E -.00 = x). S my"" =EX
(23)
where drv denotes the total variation distance. This is always verified for irreducible, aperiodic finite Markov chains [46]. Note that the uniform mixing assumption might be relaxed by weaker drift condition using the technique developed by [34] for linear TD, although its extension to the infinite-dimensional setting is not straightforward, and out of our scope. We give example of continuous-state Markov chain with geometric mixing in Sec. 6. Furthermore, following [10], in our analysis need to control the magnitude of the iterates almost surely. To do so, add projection step at each TD iteration:
Vn II (00----p(((A,, XIVV + bn)),
(24)
where IT is the projection on the H. ball of radius B > O. If [V < B, the convergence of the method is preserved. the following theorem, we consider two regimes with different rates of convergence. In the first one, we assume like [10] that we are given oracle B upper-boundin ||V sc. with B independent of X. In the second one, we use the bound of Prop. 1, but this will affect the convergence rate since in this case B = O(LA))
Theorem 2. Assuming (A2) and that the samples are produced by a Markov chain with uniform geometric mixing (A3), the projected TD iterations (24) are such that:
(i) Using X = n 2To a constant step size p log and using projection radius B 2xn
independent of X provided by an oracle and such that IIV
1lx & B, then:
[
v* ([ s o( [logn)²n 249
149
E
(25)
log(1/1)
(ii) Using = n ,tअ, p
logn Zxn
and the projection radius = V [Mcllrllee ( /X, then:
[iv!! - v01 (11122())] s so( (log )
11
E
(26)
log 1//4)
with V((0)
ER=n (
ΣØ= (1 2p
8

---

When an oracle is given for B (i.e., setting (i)). we recover the same rate as i..dd sampling, up to a multiplicative factor log(n)/ log(1/p) which represents the mixing time of the Markov chain. If no oracle is provided (i.e., setting (ii)), the convergence will be slower because the bound B is of order X. Note that the slight changes in the definitions of p. X, V(s), and the absence of constraint on X, as compared to Thm. I, are implied by the boundedness of the iterates. Following a similar study for SGD [50], we might compare these rates to those of a naive algorithm which we call "T-Skip-TD" TD", for some 2 I, where only one every T samples from the Markov chain is used to make TD updates:
V - -I + Pn((Arr XI) + bnr)
(27)
For large enough, of the order the mixing time of the Markov chain, the new sample (Iwr, )nr)) is almost independent from the past ones (Ierr = )a-nn Of course, since we need to generate times more samples to make a step, we must look at the distance convergence rates for 7-Skip-TD are derived in App. A.4, Cor. 2. In setting (i), they are similar to Theorem 2 up to a log(n) factor. This suggests that making updates at each sample of the Markov chain is not more efficient than T-Skip-TD for large T, least in theoretical analysis. In practice, using all samples seems slightly better, especially for a slowly mixing Markov chain (see App.B.3). In setting (ii) we obtain rate for Skip-TD whose leading term does not depend on log(1 (1/p)) which only appears in higher order terms suggesting that the rate and parameters of Thm. 2, setting (ii) might be suboptimal.
///r to the optimum. Such
Remark, The analysis of TT with linear function approximation by [60] does not require projec- tion step. Hence the necessity of the projection step might only be artifact of our proof technique inspired by [10]. In the above experiments, we simply omit the projection step.
6 Experiment on artificial data
Building a value function. We build a toy model for which the main parameters can be computed in closed form. We consider the dynamics on the circle X = [0, 1] defined by: with probability e, Ta+1 L[(0, 1]). and with probability - E, Fn+1 = Fn. Because the Markov kernel is symmetric, u([0, 11). In particular, the mixing parameter can be bounded explicitly with m and μ = 1 E (see App. B.1). Also, simple computations show that V is
the invariant distribution is
an affine transform of r: V*(x) ar(x) + b, with a = (1 - 7(1 - -)) and = -a fo' r(u)du. Hence build V with given regularity by choosing appropriate reward with the same regularity. We consider two rewards: (z) == 2/x 1/2] and reos( == (1 + c0s
Kernels on the torus. We consider the RKHS of splines on the circle [67] of regularity E N*, denoted by He
per It is a Sobolev space equipped with the following norm:
11 ( ((a)dz)
(2m)22 L. (1
(28)
Its corresponding reproducing kernel K2 is translation-invariint kernel defined by:
(2m)²*
K, 1+ (-1)²-1 (2x)! B2 -w}),
(29)
where {x) : x [a]] and B, is the j-th Bernoulli polynomial [52]. Let us recall that the Fourier series expansion on the torus of a 1-periodic function f E (2(p)) is: f(x) = Ewez eiiwn fur the space of
with fu == So f(r)e 2i dx, for w E Z. The kernel K, has an embedding Fourier coefficients ((x) (V mez with eu := [w| -2s if w o 0 and cp := 1. Using Parseval's is theorem in Eqn. (28), one can compute the norm of f from its Fourier coefficients Il = Ewez 1 /c/ The operators Σ and Σ, can be represented as countably infinite-
dimensional matrices Σ diag(c) and Σ1 (1 - E)Σ + (V)( Hence the source condition states that 1.60 = [=]==(1++0 [fa co. In particular, it holds if f e H for any s' 2 s(1+0). In our example, we consider two Sobolev spaces H and Ha and our two example functions have Fourier coefficients (Fats)s --1= for w o O, and (Fen)) = 0 for [w| > such that the source condition holds are indicated in the first row of Tab. 1.
The largest 0 E [0, 1]

---

Results. We run TD on functions Tabs and rees. with kernels K1 and Kg. We use parameters À and and exponential averaging as prescribed in Thm. 1 (b). Each experiment repeated 10 times and we record the mean + one standard deviation. The implementation is based on finite dimensional representation the iterates (V&)&-sn in IR² (see further details in App. B.2). This implies computing the kernel matrix in O(n²) operations. To accelerate this computation when the eigenvalues decrease fast, we approximate it with the incomplete Cholesky decomposition [3]. In Tab. 1, we set E = 0.8, 0.5 and report the observed convergence rates the ones expected by Thm. 2, which are fairly consistent. In Fig. 1, we show the respective effects of varying & and 7. Larger values of e or y make the problem more difficult and slow down convergence, presumably in the constants without affecting the rates, as predicted by Thm. 2. Additional experiments are provided App. B.3.
Table Predicted and observed convergence rates with different reward functions and kernels.
Sobolev kernel
Sobolev kernel 2
r Tabs
T' Teos
Tabs
T Teos
Maximal 0 Predicted rate
1/2
-1/4
-0.6
0.67
-0.43
00.67
Observed rate
0.72
0.64
-0.58
00.64
Fabs, K
Cabs. K= K2
c=11
0.8
10
109-
[|V] 1/ 112-
10-3
10-1_
[|V
10-2
10-2
y=0
0.7
10-3
10-3
10a
Figure Respective effects of varying (for ς = 0.5 fixed) and (for 0.8 fixed).
7 Conclusion
We have provided convergence rates for the regularized non-parametric TD algorithm the i.idd and Markovian sampling settings. The rates depend on source condition that quantifies the relative regularity of the optimal value function to the RKHS. They are compatible with our empirical observations one-dimensional MRP, but we have not proved optimality of such rates. Interesting directions include the extension to the TD(A) algorithm, which we believe can achieved with similar tools, as well as more challenging extensions control counterparts of TD (Q-learning, SARSA...) for which the policy is optimized.
Acknowledgements
The authors thank the anonymous reviewers and Pierre Marion for suggesting additional references. This work was supported by the Direction Générale de I' ArAmmment, and by the French government under management of Agence Nationale de la Recherche as part of the "Investissements l'avenir" program, reference ANR-19. 19--331--0001 (PRAIRIE 31A Institute). We also acknowledge support from the European Research Council (grant SEQUOIA 724063).
10

---

References
[1] S. Asmussen. Applied Probability and Queues, volume 2. Springer, 2003.
[2] Bach. Information theory with kemel methods. arXiv preprint arXiv:2202.08543 2022.
[3] Bach and M. L. Jordan. Kernel independent component analysis. Journal of Machine Learning Research, 3(Jul):1 2002.
[4] L. Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the International Conference on Machine Learning, pages 30-37, 1995.
[5] C. R. Baker. Joint measures and cross-covariance operators. Transactions of the American Mathematical Society, 186:273-289, 1973.
[6] A. Barreto, D. Precup, and Pineau. Reinforcement learning using kernel-based stochastic factorization. Advances in Neural Information Processing Systems, 24, 2011.
[7] A. M. Barreto, D. Precup, and J. Pineau. Practical kernel-based reinforcement learning, Journal of Machine Learning Research, 17(1):2372-2411 2016.
[8] A. Benveniste, M. Métivier, and P. Priouret. Adaptive Algorithms and Stochastic Approxiaais volume 22. Springer Science & Business Media, 1990.
[9] R. Berthier, F. Bach, and P. Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances Neural Information Processing Systems, 33:2576-222 2586, 2020.
[10] J. Bhandari, D. Russo, and R. Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, pages 1691-1692, 2018.
[11] N. Bhat, Farias, and C. C. Moallemi. Non-parametric approximate dynamic programming via the kernel method. Advances in Neural Information Processing Systems, 25, 2012.
[12] R. Bhatia. Matrix Analysis, volume 169. Springer Science & Business Media, 2013.
[13] V. S. Borkar and S. P. Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000.
[14] V. S. Borkar and K. Soumyanatha. An analog scheme for fixed point computation. IEEE Transactions Circuits and Systems I: Fundamental Theory and Applications, 44(4):351-355, 1997.
[15] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
[16] Boyan and A. Moore. Generalization in reinforcement learning: Safely approximating the value function. Advances in Neural Information Processing Systems, 7, 1994.
[17] J. Bradtke and A. G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1):33-57, 1996.
[18] Q. Cai, Z. Yang. J. D. Lee, and Z. Wang. Neural lemporal-diffcrence learning converges to global optima. Advances in Neural Information Processing Systems, 32, 2019.
[19] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-366 2007.
[20] Z. Chen, S. T. Maguluri, Shakkottai, and K. Shanmugam. Finite-samia samile analysis of contractive stochastic approximation using smooth convex envelopes. Advances in Neural Information Processing Systems, 33:8223-8234 2020.
[21] E. W. Cheney. Analysis for Applied Mathematics, volume 1. Springer, 2001.
[22] N. Cristianini and Shawe-Taylor, Kernel Methods for Pattern Analysis, volume 173. Cam- bridge University Press, 2004.

---

[23] F. Cucker and S. Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 39(1):1-49, 2002.
[24] Cucker and D. X. Zhou. Learning Theory: an Approximation Theory Viewpoint, volume 24. Cambridge University Press, 2007.
[25] B. Dai, N. He, Y. Pan, B. Boots, and L. Song. Learning from conditional distributions via dual embeddings. In Artificial Intelligence and Statisties, pages 1458 1488-1467,222 2017.
[26] G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor. Finite sample analyses for TD(0) with 18/AAAI (S/AAA'//EAAAI/AA 2018.
function approximation. Proceedings of AAAI'18/AA/
[27] P. Dayan. The convergence of TD(A) for general X. Machine Learning, 8(3):341-362, 1992.
[28] A. Défossez and F. Bach. Adabatch: Efficient gradient aggregation rules for sequential and parallel stochastic gradient methods. arXiv preprint arXiv:/711.01761, 2017.
[29] T. Dietterich and X. Wang. Batch value function approximation via support vectors. Advances in Neural Information Processing Systems, 14, 2001.
[30] A. Dieuleveut, Stochastic Approximation in Hilbert Spaces. PhD thesis, Paris Sciences et Lettres (ComUE), 2017.
[31] A. Dieuleveut and Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, (A44):363--1999 2016.
[32] O. D. Domingues, P. Ménard, M. Pirotta, E. Kaufmann, and M. Valko. Kernel-based reinforce- ment learning: A finite-time analysis. In International Conference on Machine Learning, pages 2783-2792, 2021.
[33] Y. Duan, M. Wang, and M. J. Wainwright. Optimal policy evaluation using kernel-based temporal difference methods. arXiv preprint 1at.:2009912000, 2021.
[34] A. Durmus, E. Moulines, A. Naumov, S. Samsonov, and H.-T. Wai. On the stability of random matrix product with Markovian noise: Application to linear stochastic approximation and TD learning. In Conference Learning Theory, pages 1711-1752, 2021.
[35] R. Durrett, Probability: Theory and Examplex, volume 49. Cambridge University Press, 2019.
[36] A.-M. Farahmand, M. Ghavamzadeh, Szepesvári, and S. Mannor. Regularized policy iteration with nonparametric function spaces. Journal of Machine Learning Research, 17(1):48094474 2016.
[37] K. Fukumizu, F. R. Bach, and M. I. Jordan. Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces. Journal of Machine Learning Research, 5(Jan):73-99, 2004.
[38] S. Grünewälder, G. Lever, L. Baldassarre, M. Pontil, and A. Gretton. Modelling transition dynamics MDPs with RKHS embeddings. In International Conference on Machine Learning, 2012.
[39] N. Halko, P.-G. Martinsson, J.d A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217-288, 2011.
[40] B. Hu and U. Syed. Characterizing the exact behaviors of temporal difference learning algo- rithms using Markov jump linear system theory. Advances in Neural Information Processing Systems, 32, 2019.
[41] T. Jaakkola, M. Jordan, and S. Singh. Convergence of stochastic iterative dynamic programming algorithms. Advances Neural Information Processing Systems, 6, 1993.
[42] A. Klenke. Probability Theory: Comprehensive Course. Springer Science & Business Media, 2013.
12

---

[43] A. Koppel, G. Warnell, E. Stump, P. Stone, and A. Ribeiro. Policy evaluation in continuous MDPs with efficient kernelized gradient temporal difference. IEEE Transactions on Automatic Control, (144))1856-863) 2020.
[44] N. Korda and P. La. On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence. In International Conference on Machine Learning, pages 626-634, 2015.
[45] C. Lakshminarayanan and C. Szepesvari. Linear stochastic approximation: How far does con- stant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pages 1347-1355, 2018.
[46] D. A. Levin and Y. Peres. Markov Chains and Mixing Times, volume 107. American Mathemat- ical Society, 2017.
[47] J. Long, J. Han, and W. E. An L analysis of reinforcement learning in high dimensions with kernel and neural network approximation. arXiv preprint arXiv:2104.077 0779449 2021.
[48] C. A. Micchelli, Y. Xu, and H. Zhang. Universal kernels. Journal of Machine Learning Research, 7(12), 2006.
[49] W. Mou, A. Pananjady, and M. J. Wainwright. Optimal oracle inequalities for solving projected fixed-point equations. arXiv preprint arXiv:2012.05299, 2020.
[50] D. Nagaraj. X. Wu, G. Bresler, P. Jain, and P. Netrapalli. Least squares regression with Marko- vian data: Fundamental limits and algorithms. Advances in Neural Information Processing Systems, 2020.
[51] E. Novak, M. Ullrich, H. Wožniakowski, and S. Zhang. Reproducing kernels of Sobolev spaces on Rd and applications embedding constants and tractability. Analysis and Applications, 16(05):693-715, 2018.
[52] F. W. J. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark. NIST Handbook of Mathematical Functions. Cambridge University Press, 2010.
[53] D. Ormoneit and S. Sen. Kernel-based reinforcement learning. Machine Learning, 49(2):161- 178, 2002.
[54] L. Pillaud- Vivien, A. Rudi, and F. Bach. Exponential convergence of testing error for stochastic gradient methods. In Conference on Learning Theory, pages 250-296, 2018.
[55] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838-855 855,, 1992.
[56] R.-D. Reiss. A Course on Point Processes. Springer Science Business Media, 2012.
[57] W. Rudin. Real and Complex Analysis, 3rd Ed. McGraw-Hill, Inc., USA, 1987.
[58] R. E. Schapire and M. K. Warmuth. On the worst-case analysis of temporal-different learning algorithms. Machine Learning, 22(1):95-1211 121, 1996.
[59] J.-J. E. Slotine and W. Li. Applied Nonlinear Control, volume 199. Prentice Hall Englewood Cliffs, NJ, 1991.
[60] R. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Conference Learning Theory, pages 2803-2830, 2019.
[61] I. Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research, 2(Nov):67-93, 2001.
[62] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning. ((1):9 44, 1988.
[63] R. Sutton. Introduction to reinforcement learning with function approximation, In Tutorial at the Conference Neural Information Processing Systems, page 33, 2015.
13

---

[64] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
[65] P. Tarres and Y. Yao. Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEE Transactions on Information Theory, 60(9):5716 5735, 2014.
[66] J. IN. Tsitsiklis and B. Van Roy. An analysis temporal-diiference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674-690, 1997.
[67] G. Wahba. Spline Models for Observational Data. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 1990.
[68] Weidmann. Linear Operators Hilbert Spaces, volume 68. Springer Science Business Media, 2012.
[69] T. Xu, Z. Wang, Y. Zhou, and Y. Liang. Reanalysis of variance reduced temporal difference learning. arXiv preprini arXiv:2001.00 0.8998 2020.
[70] H. Yu and D. P. Bertsekas. Error bounds for approximations from projected linear equations. Mathematics of Operations Research, 35(2):306-32,, 2010.
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] Sec. and the conclusion,
where we mention that the obtained rates might be suboptimal.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We cannot foresee any negative societal impacts of this mostly theoretical work.
(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]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are included in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] The code and the instructions to run minimal experiment are provided in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix. B.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(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)? [Yes] See Appendix. B.
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]
(e) 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, if applicable? [N/A]
14

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "k7gKyLg1dfc", "reviewer": "Reviewer_KMJg", "summary": "This paper analyzes the kernel based (on-policy) TD learning. Specially, they consider the case where TD learning is performed with the value function in a reproducing kernel Hilbert space (RKHS) (eq 3, 4). They provide convergence guarantees when the true value function V* does not belong to the RKHS under a so-called source condition (A2). They also provided non-asymptotic convergence rate for the algorithm under i.i.d setting and the Markovian setting (where the state action sequence is sampled from a fixed policy).\n", "questions": "The paper analyzed the so-called regularized TD learning (eq 12). My understanding is that this $\\lambda$ is for the use of the representer theorem. But this parameter needs to be tuned in practices. In the main theorem (theorem 1), the analysis needs $\\lambda > \\lambda_{\\theta}$. Is there any insight on the parameter $\\lambda_{\\theta}$ here, does it depend on $\\gamma - 1$?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper is well written and structured. The authors gradually build the machinery from dynamic programming, RHKS, stochastic approximations (and etc) so as to introduce their main results and analysis.\n2. As far as I know, the main technical contributions of the paper is the analysis of kernel based on-policy TD learning setting in the framework of RKHS. The general framework of analysis is similar from the analysis of TD-learning with linear function approximation, the results in terms of RKHS is technical.  To my knowledge, theoretical guarantees of TD-learning with general nonlinear function approximation is still lacking. Kernel based TD learning could be a step forward from existing TD-learning with linear function approximation.  And such results can provide more insight and support into those kernel based methods.\n\nWeakness:\nOne potential drawback could be that the main framework of analysis bears some resemblance to the analysis of TD learning with linear function approximation. But again, performing such analysis using tools from RHKS is still technical.\n\nBased on the results in ref[0], the projection step for the Markovian case for TD-learning may not be necessary.\n\nref:\n[0] Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning, R. Srikant, Lei Ying. ", "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": "dFwiUsE6doS", "reviewer": "Reviewer_XY19", "summary": "This paper focuses on solving the policy evaluation problem in reinforcement learning using non-parametric TD-learning. By introducing a regularization parameter $\\lambda$, the authors derive (1) the convergence rate of the associated ODE, and (2) the convergence rate of non-parametric TD-learning under either i.i.d. or Markovian sampling. Numerical experiments agree with the theoretical findings.", "questions": "My main concerns are the need for the regularizer and the technical novelty compared to existing literature studying kernel-based RL.", "limitations": "This paper does not have any potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well organized and well written. The authors start with the ODE associated with the deterministic variant of TD-learning, and use the Lyapunov function there to study the non-parametric stochastic TD-learning algorithm. While this is a highly technical paper, the structure makes the paper easy to follow.\n\nMajor Comments:\n\n(1) What is the motivation of introducing the regularizer $\\lambda$? Is it because $\\Sigma$ is not necessarily invertible but $\\Sigma+\\lambda I$ is guaranteed to be invertible? The Bellman operator is also a contraction with respect to the $\\ell_\\infty$-norm, regardless of whether the Markov chain has a unique stationary distribution or not. Introducing the regularization parameter is to some extend equivalent to solving a different MDP with a smaller discount factor, and I feel it should be avoided if possible.\n\nThe TD-learning algorithm with the regularizer $\\lambda$ is different than the original one. What is the updated algorithm? I do not think it is simply subtracting another $\\lambda V_{n-1} (x_n)$ in the temporal difference.\n\n(2) Regarding the convergence rate of the ODE. Suppose we exploit the $\\ell_\\infty$-norm contraction instead of the weighted $L_2$-norm contraction. Do we always get geometric convergence?\n\n(3) The need for projection in TD-learning with Markovian sampling is somewhat problematic. First of all, assuming there is an oracle that gives the right projection set is not realistic. Second, the estimate of the size of the projection set depends on unknown parameters of the MDP. In [55], the authors provide a way of analyzing TD-learning with linear function approximation without a projection. Is it possible to remove the projection using similar techniques?\n\n(4) The authors listed existing literature studying non-parametric RL, but did not compare the results and the techniques with them. I briefly checked [30], which is not for fitted Q-iteration (as claimed in this paper), but studies kernel based non-parametric LSTD and seems to be closely related to this work. The technical novelty is not entirely clear in the current manuscript.\n\nMinor Comments:\n\n(1) \"Deadly Triad\" refers to bootstrapping, off-policy, and function approximation (which does not have to be nonlinear). This should be made clear in the paper.\n\n(2) TD-learning with either tabular representation or linear function approximation has been studied extensively in the literature, and the convergence rate there is $1/\\sqrt{n}$. Some discussion seems needed to clarify why non-parametric TD has a slower convergence rate.\n\n\n\n\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": {}}, {"review_id": "LDmqG6fJ_A", "reviewer": "Reviewer_15bu", "summary": "This paper studies the convergence of the regularized non-parametric TD(0) algorithm with RKHS approximation. For both the IID and Markovian noise settings, convergence rate bounds have been obtained.  Numerical results have been given to support the theory.", "questions": "1. [Cai2019] has discussed some results for neural network approximation case. In the introduction, the authors mentioned that studying the RKHS case could bring us closer to understanding what happens with other universal approximators used in practice, like neural networks. Can the authors comment on the connections between their paper and [Cai2019]?\n\n2. [Hu2019] has given some exact analytical formulas for the TD error for linear approximation on countable state space. Is it possible to obtain similar exact formulas for the RKHS approximation on general state case? \n\n3. [Durmus2021] has addressed the TD error for linear approximation on general state space. It will be interesting to compare the assumptions in [Durmus2021] with the Harris ergodic assumption in this paper. In the linear approximation case, can the analysis method in this paper be used to get some improvements over [Durmus2021]?", "limitations": "Yes, the authors have discussed the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is quite original. The quality is good. The paper is also well written.\n\nStrengths:\n1. Originality: This paper is original. The analysis is new and novel.\n\n2. Quality: The contributions are very solid. Theory for both IID and Markov noise cases have been discussed. Numerical results are also provided.\n\n3. Clarity: The paper is well written.\n\n4. Significance: The contributions are significant. The analysis is very interesting. \n\nWeaknesses:\n  The connections to the following relevant papers are missing, and some clarifications/discussions are needed. \n[Cai2019] Q. Cai, Z. Yang, J.D. Lee, Z. Wang. Neural temporal-difference learning converges to global optima. NeurIPS2019.\n\n[Hu2019] B Hu, U Syed. Characterizing the exact behaviors of temporal difference learning algorithms using Markov jump linear system theory. NeurIPS 2019.\n\n[Durmus2021] A Durmus, E Moulines, A Naumov, S Samsonov, H Wai. On the stability of random matrix product with Markovian noise: Application to linear stochastic approximation and TD learning. COLT 2021.\n\nSpecific suggestions are given as follows:\n\n1. [Cai2019] has discussed some results for neural network approximation case. In the introduction, the authors mentioned that studying the RKHS case could bring us closer to understanding what happens with other universal approximators used in practice, like neural networks. Hence it seems quite relevant to discuss the existing convergence theory for the neural network case. \n\n2. [Hu2019] has given some exact analytical formulas for the TD error for linear approximation on countable state space (under both IID/Markov assumptions). Is it possible to obtain similar exact formulas for the RKHS approximation on general state case? Some discussion will be helpful. \n\n3. [Durmus2021] has addressed the TD error for linear approximation on general state space. It will be interesting to compare the assumptions in [Durmus2021] with the Harris ergodic assumption in this paper. In the linear approximation case, can the analysis method in this paper be used to get some improvements over [Durmus2021]?\n\n\n\n\n\n\n\n\n\n\n\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": {}}, {"review_id": "3uOZl6pYbBU", "reviewer": "Reviewer_3hWK", "summary": "The paper studies the temporal difference algorithm for estimating the value function of a Markov decision process, assuming that the control policy is already applied and the resulting Markov chain is homogenous and stationary. Under certain assumptions, the rates of convergence of the weighted averages of the value functions provided by a regularized temporal difference algorithm are shown, averaging over the stochasticity, as well as the state space.", "questions": "I would like the authors to address the points discussed under Weaknesses, and also explain how they can improve the presentation. The latter seems necessary as there are unclarity and lack of enough explanation in some places. \n\nIn the abstract, 'source condition' is unclear.\n98: 'but ...' makes ambiguity. \n106: define a 'nonnegative' reward.\nIn (1), it is unclear what is known and what is not. The main interest is in the case that the Markov transitions are unknown, but from the rest of the presentation, it does not seem to be the case as some of the quantities need the transition to be computed. Note that as the processes is assumed to be stationary and/or mixed, the authors need to argue why the known distribution does not provide the transition.\nHarris ergodicity, especially its regeneration set, need to be defined, and the discussion in these lines need more explanations.\n132: it is unclear what is n, and how these computations relate to the setting.\nIntuitions of Lemma 2 that the operator is like a contraction are required, as well as implications of such a fact.\nThe first paragraph of Section 3 is unclear. \nOn proposition 1, I think we are interested in the solutions of (12), and not those of (13).\nI am not convinced about necessity and/or usefulness of regularizing the TD.", "limitations": "Mentioned in Weaknesses. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThe framework seems technically solid. The presented results are explained rigorously, and the setting is abstract enough to include non-tabular Markov decision processes, as long as the feature space is an RKHS.\n\nWeaknesses:\nThe setting is a little artificial. \nThe experiments are not clear to be generalizable. \nThe presentation is too compact and a little hard to follow, and is also unclear in some places. \nImportance of the problem is not sufficiently motivated as the policy is already applied, the transitions are mixed and have reached to the stationarity, and now the goal is to find the value function. This, as well as the next, restrict the applicability of the proposed approach for being used as the evaluation step of a reinforcement learning policy. \nThe results are in the form of average-case analysis. Intuitively, that means that if we repeat the setting many times, we can learn the value function nicely. However, the more interesting analysis is one that can establish accuracy of the learned value function based on a single trajectory. So, in some sense, the policy evaluation is analyzed in an offline fashion, while for offline reinforcement learning policies, evaluations are not the main obstacle. \nFinally, I do not think that Section 4 fits well in the framework as restarting for many times, together with the fact that the expected learning error is studied, defeat the purpose and limit the practicality of the approach.", "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