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 submission is a theoretical paper which investigates a common belief in the community around the problem of the deadly triad: regularization would prevent instability and divergence of TD methods with function approximation in an off-policy setting. This paper provides four counter-examples showing that this is not the case and that l2 regularization can lead to instability and divergence in the context of function approximation and even with neural networks. The paper also shows that emphatic methods can also suffer from these divergence issues. This paper is an invitation to reconsider the use of regularization in off-policy TD learning.

strengths_and_weaknesses: **Contribution**
The paper provides interesting new counter-examples showing some issues of TD methods under regularization. I also appreciated the explanatory figures 2, 3, 4 , 5 illustrating the counter examples from the text. 
As mentioned by the submission, the fact that off-policy TD learning can be unstable or have unbounded error when it converges is already know in the literature but the authors provide a simpler example. The other insights and examples from sections 3.2, 3.3 and 3.4 are new as far as I am aware.

It would be interesting to understand whether these counter examples could have an impact on current RL algorithms that have been used on common benchmarks, ie are these counter examples extreme situations or can they explain empirical results from past papers?

In particular, the analysis from section 3.4 is limited to two-layer neural networks and it could be interesting to see if the insights would hold for overparametrized architectures too. This shouldn't prevent acceptance of the paper though. 
One weakness I see is that given the dynamics of sgd with off-policy TD are unknown it is hard to conclude that the issues highlighted by the paper are a practical issue for current deep rl algorithms. This aspect is briefly mentioned by the authors line 246.

**Organization and Clarity**
The paper is overall well-written and well-organized.
L70 "error of the zero model": at this point in the text it is not clear what this means.
L 122 inconsistencies \Pi_\mu vs \Pi_D: does the representation error depend on the distribution \mu ? if so, this is the error in the learnt value function and what is the distribution under which the representation error is bounded?

**Related work**
The related work seems overall well covered.

**Typos**:
L 48: as it differently than in supervised settings,
L107-109: inconsistencies for real numbers \mathcal{R} , \mathbb{R}
L109 : [0..1]
L253: some training methods / a training method
L376: to fails
questions: What are promising solutions to address the issues highlighted in the paper? While regularization can be harmful as the paper shows, itsnt there a tradeoff given it can help in other examples under the same off-policy setting?
limitations: There is no dedicated section to limitations. I would say this work highlights issues in the off-policy setting but is limited in terms of practical solutions.


Post-rebuttal update:

I want to thank the authors for engaging into this discussion. After carefully reading other reviews, I will update my score to 7 and recommend acceptance.
review_title: null

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: It is well-known that TD methods diverge when used in
conjunction with value function approximation and off-policy learning.
Several recent works have proposed the use of additional regularization to
prevent divergence in this setting. This paper provides several counterexamples
demonstrating that adding regularization to linear TD methods can lead to
vacuous value estimates, and that regularization can in fact cause divergence
in certain settings. Counterexamples are also given for a popular emphatic TD algorithm,
and for non-linear TD. Taken together, the results suggest that the role of regularization
being proposed by recent works needs reconsideration.

strengths_and_weaknesses: Overall, I thought the paper was excellent --- easily the best I reviewed this round of reviews --- and recommend acceptance.
The results are novel, thorough, and clearly relevant to
on-going discourse in the community; the
paper is well-written and the explanations were clear.
I really only have minor comments and questions, which I provide below.

### Minor Comments
- Line 266: "A separate primal-dual saddle point method has also been adapted to $\ell_2$ regularization,
  but error bounds at convergence are not yet known"
  - I think this may no longer be true; the results in Du et al. (2022) capture
    the regularized MSPBE as a special case. This paper was posted after the NeurIPS deadline I believe,
    but I think it is worth revising this sentence. I don't think the existence of such bounds for
    the $\ell_2$ regularized MSPBE takes anything away from the results presented here anyways
- Line 158, typo: $\xi\in[0..1]$ should read $\xi\in[0,1]$

questions: - Emphatic approaches:
  - The conclusions in section 3.3 hold only for a specific
    algorithm, COF-PAC, which simultaneously learns both a
    value model and emphasis model, but not necessarily to
    emphatic methods in general; am I understanding this correctly?
  - Do you expect similar conclusions could hold under more general assumptions
    on the emphasis model? or is the core problem specifically the *learning* of the emphasis model
    in parallel with the value model?

limitations: yes
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 proposes and analyzes a set of simple counter examples to show that l2 regularization can not mitigate the problems faced value estimation in the deadly triad setting consisting of off-policy learning under function approximation with bootstrap. The authors also analyze emphatic TD approaches and show that l2 regularization on the weight norm is insufficient.


strengths_and_weaknesses: Strengths:

* This is a well written paper with simple but non-trivial examples that demonstrate concretely that l2 regularization can not solve the convergence issues highlighted in the "deadly triad" problem in off-policy learning under function approximation.

* The analysis over a range of regularization strengths and comparison against "vacuous bounds" helps understand when prior bounds like Eq (9) are not informative.

* The analysis showing how the off-policy distributions can influence the optimum regularization, specifically causing different non-overlapping ranges of $\eta$ to be necessary for non-vacuous performance seems like a helpful qualitative insight even though it arises out of very specific counter examples. 

Weaknesses:

* I'm not sure that there was a widespread belief that regularization necessarily solves the deadly triad, so in that sense the demonstrated phenomenon is not necessarily surprising even if valuable

* The paper is presented as a general study of regularization though the results are specific to l2 weight regularization. 
questions: * What is the precise definition of a "vacuous model"? Anything that achieves an error worse than the trivial zero-prediction solution? An alternate threshold for vacuity could be the variance of the value function as opposed to the l2 norm. Can the authors make this a bit more clear as this term is repeatedly used through the paper across multiple sections? 

* The takeaways from Section 3.4 are a bit unclear. It appears to mainly imply that there are situations where the resulting solution from TD is not useful. What could be more interesting is some evidence that these phenomena can occur with neural nets occur outside of the specific counter examples considered. 

* What is the distribution parameter p in Fig 5(a)?  

* Nit: small-eta in L230.
limitations: Adequate
review_title: null

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: Off-policy RL can be divergent when function approximation and bootstrapping are utilized, and it is commonly believed that $l^2$ regularization prevents divergence in this case. The authors show that there are problems where linear models with any amount of $l^2$ regularization produce worse error than the trivial zero solution does. An analytical and geometric argument is presented, and experiments on linear and nonlinear models demonstrate specific examples in which $l^2$ regularization can increase value-estimation error or lead to divergence.
strengths_and_weaknesses: **Strengths**
- The paper addresses a fundamental issue in off-policy RL with function approximation, with the potential for significant practical implications. I expect these findings will be of interest to a wide audience of RL researchers.
- The paper is very well written. There are lots of motivating examples presented in a logical, cohesive flow---almost like reading a chapter of a textbook.
- The geometric interpretation in Figure 2a was helpful for developing an intuition for the problem addressed by the authors.

**Weaknesses**
- Overall, I finished reading the paper feeling a lack of clear instruction about “the pitfalls of regularization.” The authors’ general takeaway seems to be that regularization is bad and should be avoided. In reality, the issue seems to be far more nuanced than that. The paper would benefit from further discussion about when regularization is good, too, and what the practical trade-offs may be. For instance, it was not clear to me how pertinent the specific counterexamples in the paper are to off-policy RL in general.
- I am not totally convinced by the neural network (NN) experiment in Example 4, Figure 5b. The authors claim that their divergence results in the linear approximation case carry over to nonlinear approximation as well, since there are some $\eta$-values that increase the error of the learned NN value function. In reality, I think this conclusion is based somewhat on the misleading x-axis log scale, and the fact that the y-axis does not start at the origin. To me, it looks like, below $\eta=10^{-3}$, there is effectively no regularization, and the error is a plateau. If the x-axis were linear, then this region would be essentially negligible. Then, at $\eta=10^{-3}$, after a short uptick in error, the error starts to decrease rapidly for about two orders of magnitude, before the regularization becomes too strong and starts to worsen again. The takeaway I ultimately got from this graph is that a moderate amount of regularization is actually quite helpful!

**Minor Edits**
- Line 48: The grammar in this sentence sounds incorrect to me.
- Line 96: Typo in “regularization.”
- Line 129: Don’t end a paper section with a colon.
- Lines 145, 149: I would change the notation “trajectory (1),” since it looks like you are referencing an equation there.
- Line 195: I think it should be “reweighting,” not “reweighing.”

questions: 1. In Example 1, how can you guarantee that $\hat{w}^Tw^*(\eta) \leq 0$, $\forall~\eta$? Do you have any theoretical results for when a distribution $\mu$ that causes this either exists or does not exist?
1. The geometric interpretation of a vacuous model (a trajectory within the halfplane tangent to the $l^2$ ball) makes sense for linear models, but I don’t see why it would necessarily extend to nonlinear (NN) models. Could you elaborate on why you think these results are transferrable?
1. In Figure 5b, what would happen if you used a NN with more than just 3 neurons in each layer? Would you still expect to see an increase in error for some $\eta$-values?

limitations: N/A
review_title: null

Meta-review: metareview: This paper presents a counterexample-driven analysis of regularization in TD learning with function approximation.

Despite the paper's simplicity, the reviewers unanimously though there was a good contribution being made here, and I agree. Highlights include a clarity of presentation and new insights into what is known as the deadly triad. The reviewers generally agreed that these results are relevant to deep RL today, but would have appreciated more forward guidance. 
confidence: Certain
Decision: Accept