Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the fixed point solution of standard model-free value-function optimization algorithms in RL (in particular TD, residual gradient, and Fitted Value Iteration) in the over-parameterized setting, meaning that the problem is underdetermined and can generally admit numerous optimal solutions. Importantly the paper shows that the different fixed points of TD and residual gradient in the limited-capacity case carries over to the over-parameterized setting as well.
main_review: In the reinforcement learning literature, numerous algorithms exist to learn the value function based on bootstrapping and in presence of function approximation. Chief among these algorithms are (linear) temporal difference learning and the residual gradient. These two differ slightly in terms of the objective functions (MSPBE vs MSBE), but it is known that this small difference can manifest itself significantly in practice. The commonly held intuition is that the TD algorithm has a superior fixed point, so eventhough Maei showed that TD is not following the gradient of any objective, it is preferred to residual gradient in practice. The soundness of residual gradient is also overshadowed by its need for double sampling to combat the bias that would otherwise be present.

One may intuit that the difference between the fixed point of the two approaches may not carry over to the setting with sufficiently rich feature space, which is the central question of this paper. The paper shows that indeed even in the overparameterized setting, the two approaches may result in different fixed-points. More specifically, each approach can have numerous fixed-points and convergence to a particular fixed point depends upon the initial weight vector, but that crucially these fixed points are different on a per-algorithm basis. This makes sense. After all, the parameter vector is trained to predict different things in each case: value function in TD, and temporal differences in residual gradient.

Overall, reading this paper really excited me, eventhough sometimes it felt like that the paper is purposefully making the math to look more difficult than it needs to be. It is certainly very interesting to study the fixed point of different approaches in settings that more closely resemble the common practice in which people use extremely powerful function approximators.

Getting to the core of the results, I have noticed a few issues worth mentioning:

- The fixed point in theorem 2 is in fact extremely similar to equation (2) from [1]. The newly introduced variables make it less obvious to see, but after plugging in the relevant quantities, one can see that things cancel out and lead to a solution very similar to what i noted, and the paper itself does note in equation (7). This result is still novel and does generalize to the underdetermined case, but I don't feel great about the paper not giving enough credit to [1] in the context of this result.

- The result branded as theorem 4 is really trivial. In particular, this is nothing but the least norm solution for underdetermined equations. See for example: https://see.stanford.edu/materials/lsoeldsee263/08-min-norm.pdf. Again, branding this as a theorem and not giving credit to people who first came up with this result is not a great practice.

- What's even more surprising, the Proof of theorem 4 in the appendix, which is just a copy of the existing result from the convex optimization literature, includes several mistakes. For example, as written $L(\theta, \alpha)$ is not a function of $\theta$ nor $\alpha$! It is in fact constant with respect to these variables. I think authors meant to compute $\inf_\theta \sup_\alpha L(\theta,\alpha)$ and refer to the objective as $L(\theta,\alpha)$. In any case, as written, this gives the wrong impression that this result is first derived in this work, but this is just a trivial result in convex optimization as I mentioned above.

- Less severe issue, but In equation 38 in the Appendix, it seems like that t+1 should actually be $\infty$?

- While I think the studied setting is very interesting, I don't quite see the connection with deep RL. In deep RL, it is not that the number of features are extremely large, therefore the last layer is solving an underdetermined problem. It is more that all but the last layer are jointly learning a basis function given which it is very easy to fit the value function using linear function approximation. For example, the last layer of DQN is comprised of 256 features, yet on a given game the support of the stationary distribution is vastly larger than 256 in light of the combinatorial nature of most games, how do you square your relating the setting to deep RL with my observation?

- I am also not sure I learned a lot from the experimental sections. Domains are pretty toyish and experiments are not well motivated. Also, the figures and their captions look pretty small. In light of the theory it is OK to not have a significant empirical contribution, but at this point, its debatable if the experiments are adding something or actually degrading the paper.



[1] Parr and friends, "An Analysis of Linear Models, Linear Value-Function Approximation, and Feature Selection for Reinforcement Learning"

summary_of_the_review: As mentioned above, I am excited about this paper in light of the importance of studying TD and related algorithms in settings other than standard under-parameterized settings. The demonstrated scholarship, or lack thereof, gives me doubts, but overall I like this paper and lean towards the acceptance side.
--
post rebuttal: I think this paper makes a respectable contribution to the theory of temporal difference learning. I believe authors will address my concerns, so I like to see this paper accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence properties of three classical value estimation algorithms (TD, FVI and RM) under over-parameterized linear case. The difference among convergence results are interpreted unifiedly through different constraints in an optimization problem. It also proposes an generalization bound for FVI. Furthermore, based on the results mentioned before, it proposes two regularizers to help convergence in deep reinforcement learning and experimentally evaluates their performance.
main_review: ### Strengths
Overall, this paper provides a novel perspective to reveal the implicit bias behind these classical value estimation algorithms, which is something that cannot be observed in under-parameterized case. The proposed regularizers are based on the weaknesses revealed by previous theoretical analysis and show good performance in experiments.

### Weaknesses
One of my major concerns is about the setting used in theoretical analysis. In particular, the analysis of this paper relies on an IID dataset $\left\lbrace (s_i, r_i, s_i')\right\rbrace_{i=1}^n$. However, in real offline policy evaluation problem, the dataset usually consists of sampled trajectories, in which the tuples $(s_i, r_i, s_i')$ are mutually dependent. It is not clear whether this dependency will break the results in this paper.

Another concern I have is about the experiments. Currently, the proposed regularizers are mainly tested in relatively simple environments. Is that possible to check whether these two regularizers are also effective in more complicated environments?

### Questions
- What if the dataset consists of many sampled trajectories instead of independent one-step transitions?
- What is the limit of generalization bound in Theorem 5 when $t\rightarrow\infty$ if the convergence criteria $||\mathbf{W}||\leq\frac{1}{\gamma}$ holds? How should we interpret this limit?

---

My concerns have been well-addressed and thus I increased my score. Meanwhile, I also decreased my confidence score because I realized that my expertise in this area might still need some improvement.
summary_of_the_review: This paper proposes a novel convergence analysis of three classical value estimation algorithms and reveals their implicit bias. However, the validity of its setting is questionable and the experiment results is not very persuasive.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: See main review.
main_review: Summary:
In this paper, the authors investigate the convergence results of three algorithms (RM, TD, and FVI) in OPE when the model is assumed to be over-parameterized linear function class. Besides, some empirical experiments are also conducted. But as I’m not a fully expert in empirical RL, I would not have any comments on the experiment part. To my opinion, the contribution of this work is not solid enough, even some results might be wrong. Please check the following parts.

Questions:
1.	This paper is claimed to understand over-parameterized model in OPE. However, after I read this paper, I’m still confused as there is no theoretical comparison between over- and under-parameterization cases. Besides, I also can’t learn from Thm 5 whether the size of model (d in this paper) has an effect on the learning process. Thus, I would be much appreciated if the authors could have a clear explanation of the motivation.

Errors:
1.	Equation (38), as t already goes infinity, RHS should be free of t.
2.	Equation (42), it should be $\theta_t$ at RHS. Thus, the recursive expression (43) is also wrong. (no effect on results I guess)
3.	At the bottom of page 15, it mentions that $M^\top D_k(M-\gamma N)$ can be eigen decomposed. Please explain why? To my knowledge, it’s not symmetric. And I think this would definitely have an impact on your results.
4.	In the proof of Corollary 2, Hoeffding’s inequality is applied to bound $\varepsilon$ and $\sigma$, and then taking an expectation over both sides in (97) without considering the high probability term $1-\delta$ when applying the Hoeffding’s inequality. I think this is definitely wrong.

Recommendation:
1.	To my opinion, the term ‘over-parameterization’ is confusing in this paper. To my best acknowledgement, the basic structure of an over-parameterized model is assumed a two-layer model, though a linear model is ok but not just enough. 
2.	Appendix A.7 presents two lemmas to control the expectation term in Corollary 2. Please give readers exact form in your case not just present its original form.
3.	I think an improvement on writing is necessary. There are a number of grammatical problems and the language is not precise enough. Please have proofread.

summary_of_the_review: See main review.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors consider the overparameterized linear representations of TD, FVI, and RM. A unified interpretation of these algorithms of minimizing the Euclidean norm of the weights subject to alternative constraints is proposed. The paper is also supported by the empirical results.
main_review: 1. This paper is concerned with the overparameterized linear representations of TD, FVI, and RM. The paper is easy to follow and digest. The overparameterized representation problem is a crucial problem. On the downside, the linear case is restricted, and technical analysis is not very novel. I have some high-level comments as follows.

2. The paper discusses the unified view of overparameterized linear representation. Does such view also hold for the underparameterized linear representation? If not, is there any intuition that why we would have such difference?

3. For the overparameterized problem, I think non-linear representation like deep neural network is more common and interesting. Although the linear representation result in this paper is new to me, it is too restricted. Usually we would not use linear function approximation with lots of parameters, therefore I feel the result in this paper has limited impact. Is it possible to extend to neural network with Relu activation?

4. Related to the prior point, I suggest the authors to add some discussions about the related work of overparameterized NN theory, e.g., NTK.

5. This paper defines the update equation for the underparameterized form (5,6) and says the equation for the overparameterized case (10,12) can be directly obtained. Can you provide some details of the derivation?

6. Is there any relationship between the solution of TD, FVI, and RM with overparameterized linear representation and the overparameterized linear regression?

7. What is the intuition to define D matrix in proposition 1?

8. Is there any interpretation of operator M, N, and R in the overparameterized regime? It seems that they can be obtained by pre-multiplying H matrix from the original operator for the underparameterized case? If so, why pre-multiplying H would be useful here?

9. For the overparameterized regime (theorem 4), it seems that the difference between TD/FVI and RM is that the convergence points of TD/FVI further constraints that \theta must lie in the row span of M. This is quite similar as the interpretation that TD/FVI is the solution of MSPBE while RM is the solution of MSBE (see ref) because the objective of MSPBE and MSBE are quite similar and they only differ by a projection operator. This projection operator is similar as the forcing \theta to lie in the row span of M. Is my understanding correct?

Ref: Policy Evaluation with Temporal Differences: A Survey and Comparison

10. In the theorem statement, it is mentioned that the algorithm will not converge if the norm is large. Could you provide more discussions about the implication?
 
11. The font size in the figure is too small.
summary_of_the_review: This is a theoretical paper about the overparameterized linear representations of TD, FVI, and RM. This is an interesting question. On the downside, the linear representation might be too restricted and the technical contribution is not significant.
review_title: null

Meta-review: This paper presents a study of the over parametrization of linear representations in the context of recursive value estimation.

The reviewers could not reach a consensus over the quality of the paper, with a fairly wide range of scores even after the rebuttal.

After considering the paper, the rebuttal, and the discussion, I lean towards accepting the paper. Despite the concerns voiced by some of the reviewers, the topic and analysis of the manuscript are novel and interesting, and it is my expectation that this manuscript will prove a valuable source of inspiration for future work.

I invite the authors to carefully consider the feedback received by all the reviewers (and in particular Reviewers xq3y and gT5o and) and to revisit the manuscript accordingly.
Decision: Accept (Poster)