Weaknesses
1. It is not made very clear that the scheme proposed is actually different from the classical TD learning which was analyzed in [3] since the iterate $\theta_t$ of the target network is frozen. The paper considers a ‘target-based’ version of TD learning which was inspired by the DQN algorithm using target networks [1].
2. Since one of the motivations of the paper is to show that the optimization point of view allows to address more general settings than the linear function approximation setting with square loss, I would expect a more detailed discussion of these cases in Section 6 giving the definitions of the $H$ function in that case and verifying the uniform assumptions 1 and 2 of Section 6. The discussion in l. 277 to 280 is quite minimal. The generalization does still seem a bit restrictive and the analysis provides sufficient conditions that do not close the question of the understanding of the divergence behavior of TD learning. See also the Questions section.
3. Although the interpretation in terms of ‘target force’ and ‘optimization force’ has not been described as such in prior work to the best of my knowledge, arguments to show the results are quite classical and technical novelty is very limited in my opinion. The proofs of section 5 rely on the classical stability criteria in control for linear systems and was also used in other works ([16], see also discussions below about related works) even if the possibility of using other distributions instead of the stationary one was not described.The proofs for Section 6 follow standard analysis of gradient descent like algorithms for smooth and strongly convex objectives up to the drifting parameter $\theta_t$ which is periodically synchronized with the online iterate.
4. **Related work**: Closely related works are not discussed in detail, especially those analyzing the ‘target-based’ version of TD learning which is central in this work.
**(a)** While the present work indeed provides some new insights, the optimization perspective proposed in this work is not completely new and I believe some additional discussion regarding this would be welcome. As a matter of fact [16] is only briefly mentioned in l. 275 whereas the optimization point of view is alluded to in the remark in Section 2.4 of [16] (see also sections 3 and 5 therein) where the modified version of the Mean Square Bellman Operator with two variables (target and online) clearly appear. While the generalization beyond linear function approximation and the squared loss (under some Lipschitzness and strong-convexity assumptions) and the flexibility to consider a different distribution from the Markov chain’s stationary distribution are interesting insights, the results of Proposition 1 and Corollary 2 are not very novel. For instance, instead of periodically synchronizing the target network with the online one as in Algorithm 2, one could also consider the online moving average update rule proposed in the popular DDPG algorithm (Lillicrap et al. 2016) which was analyzed in the linear function approximation on-policy setting in [16, sections 2, 3, 5] and in Barakat et al. 2022 (see Sections 4.2, 5.1, 6.1). The aforementioned results also provide almost convergence results and sample complexity analysis accounting for noisy settings unlike the present work.
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning, ICLR 2016.
Barakat, A., Bianchi, P., Lehmann, J. Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation, AISTATS 2022.
**(b)** If one of the main motivations or consequences of this work is to show that the ‘optimization viewpoint’ can explain the possible convergent nature of TD learning in the presence of the deadly triad as mentioned in the conclusion (under some assumptions and some suitable choice of the sampling distribution in the off-policy case), then, the ability of the target-based updates (which is actually the ‘optimization point of view’) was also advocated for in Zhang et al. 21 [25] at least in the linear function approximation setting (see Section 4 for off-policy evaluation with Q functions which could be easily adapted to V functions).
**(c)** Further works such as Liu and Olshevsky 2021 could also be relevant to mention. This work points out that original TD learning (i.e. Eq. (2), as proposed in [6] and analyzed in [3]) can be seen as what they call a ‘gradient splitting’ (see Section 3 therein) even if it is known that the TD learning update rule does not correspond to any gradient descent over any function.
Liu, R., Olshevsky, A. Temporal Difference Learning as Gradient Splitting, ICML 2021.
**(d)** Several works have also considered the analysis of TD learning with nonlinear function approximation beyond the linear setting (see e.g., Brandfonbrener and Bruna 2020; Agazzi and Lu 2021 to name a few). A discussion about these works seems also relevant given the generalization motivation of the present work.
Brandfonbrener, D., Bruna, J. Geometric insights into the convergence of nonlinear TD learning, ICLR 2020.
Agazzi, A., Lu, J. Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes, MSML 2021.
**Minor typos:**
l. 104: ‘the root cause of TD’, of divergence?
l. 242: capital $H$ instead of $h$
l. 541-542: $\theta^{\star}$ instead of $\theta^{*}$
Questions
In the following, I list a few questions of which the first two are the main ones, focusing on the limit point definition and the strength of the assumptions.
1. All the theoretical results show convergence to the fixed-point $\theta^{\star}$. How is this point defined in those results? Eq. (5) mentions that if convergence happens then $\nabla_{w} H(\theta^{\star}, \theta^{\star}) = 0$. Such a characterization (which is also the fixed-point characterization of the TD solution) is used in all the proofs. Then l. 142-143 precise that ‘Whenever it exists, we refer to $\theta^{\star}$ as the fixed point of these iterative algorithms’. For the convergence results to be meaningful, the existence of the fixed point should be guaranteed. I guess you define $\theta^{\star}$ to be the fixed point of the projected Bellman operator which is indeed a contraction under some conditions but this is not very clear in the paper. However, as alluded to in the paper in l. 212-218, it is not clear whether the projected Bellman operator is still a contraction when one considers a distribution different from the stationary state distribution of the Markov Chain. What would then be the limit point(s) in the results in the case where existence is not guaranteed by the fixed point arguments relying on the operator viewpoint? Do you just suppose in that case that there exists a unique point such that $\nabla_{w} H(\theta^{\star}, \theta^{\star}) = 0$ (which is what is required and used to conduct the proofs)?
2. Concerning the assumptions and the examples provided in Section 6, input-convex neural networks [18] provide convex functions with respect to the inputs and not with respect to their weights (parameters). How these would help to guarantee that the strong convexity assumption 2 holds? Satisfying both assumptions does not seem straightforward. The constants $F_{\theta}$ and $F_{\omega}$ are uniform constants over $\theta$ and $w$ that are not easy to define and compute in practice which makes the core stability condition $F_{\theta} < F_{w}$ difficult to verify. I understand though that the focus of the paper is theoretical. Even in the linear setting and assuming that the feature matrix is given and known, can we for example suggest some distributions beyond the stationary state distribution for which the condition holds?
3. Regarding section 4, when you mention that the counter example was identified by [3], are you referring to Section IX in Tsitsiklis and Van Roy 97 (TAC) for this? Is it a simplified/modified example of that one?
4. Could you mention the stationary state distribution of the Markov chain for the counter example? This could be added if relevant to show that this stationary distribution is indeed valid and leads to a convergent behavior as expected.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.