Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: This paper is quite original. The quality is good. The paper is also well written.

Strengths:
1. Originality: This paper is original. The analysis is new and novel.

2. Quality: The contributions are very solid. Theory for both IID and Markov noise cases have been discussed. Numerical results are also provided.

3. Clarity: The paper is well written.

4. Significance: The contributions are significant. The analysis is very interesting. 

Weaknesses:
  The connections to the following relevant papers are missing, and some clarifications/discussions are needed. 
[Cai2019] Q. Cai, Z. Yang, J.D. Lee, Z. Wang. Neural temporal-difference learning converges to global optima. NeurIPS2019.

[Hu2019] B Hu, U Syed. Characterizing the exact behaviors of temporal difference learning algorithms using Markov jump linear system theory. NeurIPS 2019.

[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.

Specific suggestions are given as follows:

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. Hence it seems quite relevant to discuss the existing convergence theory for the neural network case. 

2. [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. 

3. [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]?













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]?

2. [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? 

3. [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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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).

strengths_and_weaknesses: Strength:
1. 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.
2. 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.

Weakness:
One 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.

Based on the results in ref[0], the projection step for the Markovian case for TD-learning may not be necessary.

ref:
[0] Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning, R. Srikant, Lei Ying. 
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
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strength:
The 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.

Weaknesses:
The setting is a little artificial. 
The experiments are not clear to be generalizable. 
The presentation is too compact and a little hard to follow, and is also unclear in some places. 
Importance 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. 
The 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. 
Finally, 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.
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. 

In the abstract, 'source condition' is unclear.
98: 'but ...' makes ambiguity. 
106: define a 'nonnegative' reward.
In (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.
Harris ergodicity, especially its regeneration set, need to be defined, and the discussion in these lines need more explanations.
132: it is unclear what is n, and how these computations relate to the setting.
Intuitions of Lemma 2 that the operator is like a contraction are required, as well as implications of such a fact.
The first paragraph of Section 3 is unclear. 
On proposition 1, I think we are interested in the solutions of (12), and not those of (13).
I am not convinced about necessity and/or usefulness of regularizing the TD.
limitations: Mentioned in Weaknesses.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.

Major Comments:

(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.

The 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.

(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?

(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?

(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.

Minor Comments:

(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.

(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.






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.
review_title: null

Meta-review: metareview: The paper studies the convergence of non-parametric temporal-difference learning in the non-asymptotic regime. All referees agree that the paper is technical sound and the result is important to further our theoretical understanding of reinforcement learning. The paper merits acceptance to the conference. 
confidence: Certain
Decision: Accept