A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning

Thank you very much for your thoughtful feedback.

Regarding the comment on weaknesses

We understand your concern about the density of the paper and agree that the depth of the content may be better suited for a journal format.

Due to space constraints, we placed several definitions and discussions in the appendix, which may have affected the reading flow. We appreciate you highlighting this and will revise the paper to bring the most essential notations and explanations into the main text to improve clarity and accessibility.

Regarding the comment on writing precision:

Thank you for pointing this out. You mentioned that the statement on line 147—"Its solution is the same as the original linear system"—may depend on the choice of $M$. We appreciate the opportunity to clarify this.

In this case, as stated just prior to that sentence, the preconditioner matrix $M$ is assumed to be a nonsingular matrix. Under this assumption, the preconditioned linear system $MAx = Mb$ indeed has the same solution set as the original system $Ax = b$. Therefore, in this case the choice of $M$ does not affect the solution set. We carefully chose the language to reflect this exact condition, and we believe the statement is precise in this context.

That said, we truly appreciate your close reading and will consider clarifying this further to avoid any possible ambiguity for readers.

To answer your question

You asked about how likely such cases are in practice, and how these examples came to light. It's difficult to say how much a real world problem has in common with a 3-state, 2-feature MDP, but we can say that we emphasized linearly independent features because it is widely perceived to be a benign case where things are often well behaved. A practitioner aiming for a good set of features for linear approximation will often aim for linear independence as a starting point. So, we believe this is a reasonable assumption. From that starting point, it's simply a matter of finding two pairs of features that satisfy the convergence conditions of one algorithm, but not the other. Since that was not difficult do intentionally, we don't expect it would be very hard to do accidentally in practice.

Thank you once again for your insightful review and for helping us strengthen the paper.

Thank you very much for your thoughtful question.

First, we would be happy to clarify that Appendix Section I is intended to highlight and correct certain inaccuracies in the existing literature. For example, Proposition 3.1 in [17] is presented as offering necessary and sufficient conditions for TD convergence under the assumption of linearly independent features. However, as we carefully demonstrate in our paper, this result in fact provides only a sufficient condition. We present the correct necessary and sufficient conditions for this setting.

More broadly, one of the central novel contributions of our work is to establish necessary and sufficient conditions for the convergence of TD, FQI, and PFQI without making any assumptions about the features used (e.g., linear independence) under linear function approximation. We further show how such commonly assumed feature conditions influence convergence behavior in each case.

Response regarding the linear independence assumption and rank invariance

We truly appreciate your interest in this point. The assumption of linearly independent features is indeed a widely adopted simplification in the analysis of reinforcement learning algorithms such as TD, FQI, and PFQI under linear function approximation. For example, many of the earlier works discussed in Appendix I rely on this assumption to facilitate convergence analysis. We would also like to emphasize that rank invariance is, to the best of our knowledge, a completely new and previously unrecognized condition in the literature.

In prior works—such as Section 2.2 of [17]—it has been commonly stated that the uniqueness of the TD fixed point in the off-policy setting can be guaranteed solely by assuming linear independence of the features. However, through our analysis in this paper, we identify rank invariance as a distinct and essential condition, separate from linear independence.

Most importantly, we rigorously prove in Proposition 4.5 that the fixed point of TD is unique if and only if both linear independence and rank invariance hold. This result corrects a commonly accepted assumption and provides a stronger, more precise characterization of the uniqueness condition.

We are confident that rank invariance has not appeared in prior literature and constitutes a genuinely novel contribution. Moreover, as we discuss in Appendix C.2, it is a mild condition that widely holds in practice. Our results show that it plays a surprisingly central role in:

• Ensuring the existence of fixed points (Proposition 4.2), and
• Influencing the convergence behavior of TD, PFQI, and FQI, as elaborated in the respective sections of the paper.

In addition to the strengths you kindly pointed out, we would like to take this opportunity to clearly itemize several key contributions of our paper. We hope this provides a more accessible overview—especially in light of Reviewer 991y’s comment that the content may feel too dense for a conference paper.

• Unifying Perspective on TD, PFQI, and FQI:

  • Shows that TD, Partial Fitted Q-Iteration (PFQI), and Fitted Q-Iteration (FQI) are a single iterative methods solving the same linear system (the LSTD system), differing only in their choice of preconditioners and matrix splittings.

• Matrix Preconditioning Interpretation:

  • Interprets TD as using a constant preconditioner, FQI as using a data-feature adaptive preconditioner (inverse feature covariance), and PFQI as interpolating between them.
  • Demonstrates that increasing the number of updates under a fixed target value function corresponds to transitioning from a constant to an adaptive preconditioner.

• Clarification of Convergence Conditions:

  • Provides necessary and sufficient convergence conditions for TD, PFQI, and FQI under linear function approximation, without making any assumptions about the chosen features
  • Identifies limitations of commonly used assumptions in prior literature.

• Introduction of the Rank Invariance Condition:

  • Proposes a new condition---rank invariance---that is necessary and sufficient for universal consistency of the target linear system (i.e., solvability for any reward function). It is also necessary and sufficient to ensure that every solution of the target linear system is a desired solution if it exists.
  • Highlights the distinction between rank invariance and linear independence.
  • Shows that when rank invariance holds, FQI is an iterative algorithm that uses the proper splitting scheme to formulate its iterative components and preconditioner.
  • Demonstrates that rank invariance widely exists in practice and is guaranteed to hold in the on-policy setting.

• Conditions for Uniqueness of Solutions:

  • Proves that the target linear system has a unique solution if and only if both rank invariance and linear independence hold.

• Encoder-Decoder View of TD:

  • Introduces an encoder-decoder interpretation of TD's convergence condition, clarifying why TD may diverge even under overparameterization.

• Analysis of On-Policy and Off-Policy Settings:

  • Shows that rank invariance always holds in the on-policy setting, guaranteeing the existence of a fixed point.
  • Extends on-policy TD convergence guarantees to cases without linearly independent features, showing that this common assumption can be dropped.

• New Insights into Learning Rates:

  • Demonstrates that when a learning rate ensures TD convergence, then all smaller learning rates will also ensure convergence.
  • Provides guidance where to choose learning rate to make batch TD converge when it can converge

• Convergence Relationships Among TD, PFQI, and FQI:

  • Provides formal implications (and counterexamples) regarding convergence dependencies between TD, PFQI, and FQI.
  • For example, if TD converges, PFQI with a small learning rate also converges. Moreover, despite the common perception that FQI is more stable than TD, TD convergence does not guarantee FQI convergence—our analysis explains why.

• Relevance to Deep RL and Nonlinear Function Approximation:

  • Extends insights to neural networks by noting that final linear layers justify applying results beyond the assumption of feature linear independence.

Response to the comment on the Weaknesses

We agree that it would be nice to extend insights from the current work to policy control settings (nonlinear problems). As noted by the Reviewer 991y, the paper is already quite dense and rich with results, many of which appear in the appendix because of space limitations. We hope the reviewer would agree that extensions to policy control settings are best deferred for future studies.

With respect to the reviewer’s comment on the absence of empirical experiments to support our claims, We agree that experiments can play an important role in papers, especially when there are gaps between theory and practice. In such cases, experiments can reassure that theory still informs practice, and/or suggest new directions for inquiry. However, not all theoretical contributions require experiments. Some of our theoretical work, for example, is motivated by known empirical results. Other results provide reassurance about the conditions under which algorithms are guaranteed to perform well (necessary and sufficient conditions). This is an important thing to know, yet it is impossible to verify experimentally since these are statements about all possible sets of models and features. Still other results show that the good behavior of one algorithm does not necessarily imply the good behavior of others. This is validated in Appendix G.3, where we provide a specific MDP and set of features.

Thank you again for your thoughtful and constructive feedback—it has been invaluable in improving our work

We thank the author for the response and have no further questions. We maintain the original score.

Dear referee,

Could you please take a look at the author's rebuttal and update your review/score if and as needed?

Thank you!

Thank you so much for taking the time to thoroughly review our paper and for recognizing its contributions—we truly appreciate your thoughtful feedback.

In response to your minor concerns:

Regarding the typos:
Thank you for pointing this out. We will carefully review the manuscript and make sure to correct any such issues.

Regarding clarity:
The terminology and notation are indeed defined in the paper; however, due to space constraints, we placed all definitions related to linear algebra in Appendix A.1, as noted in Section 2 (Preliminaries) of the main text. That said, we very much appreciate this comment. It’s a valuable suggestion, and we agree that moving some of the most frequently used or important definitions into the main body could improve accessibility and clarity for readers.

Regarding the missing discussion of related work you kindly pointed out:
Thank you very much for bringing these papers to our attention.
Perdomo et al. (reference [30] in our paper) indeed provides a valuable finite-sample analysis. However, in their Section 3 on FQI preliminaries, they state that

converges to the true value function parameter $\theta_\gamma^{\star}$ only if $\rho(\gamma \Sigma_{\mathrm{cov}}^{-1} \Sigma_{\mathrm{cr}}) < 1$, which suggests that this condition is necessary. We would like to gently point out that this is not strictly correct.

As shown in our Theorem 5.1 and Proposition D.3, the power series can still converge when $\gamma \Sigma_{\mathrm{cov}}^{-1} \Sigma_{\mathrm{cr}}$ is semiconvergent (definition provided in line 544), which includes cases where $\rho(\gamma \Sigma_{\mathrm{cov}}^{-1} \Sigma_{\mathrm{cr}}) = 1$.

We also note that in the broader literature, it is a common misunderstanding to treat $\rho(A) < 1$ as a necessary and sufficient condition for the convergence of power series of the form

derived from the iterative update equation $X_{t+1} = A X_t + B$. As we discuss in Appendix I, many prior works have made this same assumption. One of the contributions of our paper is to help clarify and correct such misconceptions in the literature.

Regarding your mention of three papers stating that $A_{\text{LSTD}}$ being nonsingular is necessary and sufficient for OPE:
We greatly appreciate your comment, though we were unable to locate this specific claim in the referenced works. Moreover, this statement does not generally hold. For instance, as we show in Appendix G.3, there are concrete examples where $A_{\text{LSTD}}$ is nonsingular, yet both TD and FQI fail to converge.

If you wouldn’t mind pointing us to the specific statements or sections where this claim appears—or sharing a bit more about what you had in mind regarding $A_{\text{LSTD}}$ being a necessary and sufficient condition for OPE—we would be sincerely grateful. We would be more than happy to revisit those works with your guidance.

To answer your question:
Thank you for the thoughtful and insightful question! We address this point thoroughly in our paper. The two solution sets you mentioned are formally defined as $\Theta_{\text{FQI}}$ (line 160) and $\Theta_{\text{LSTD}}$ (line 174), with the desired solution set denoted as $\Theta_\pi$ (line 215).

In Proposition 3.1, we prove that $\Theta_{\text{LSTD}} \supseteq \Theta_{\text{FQI}}$ always holds, and we provide the necessary and sufficient condition under which $\Theta_{\text{LSTD}} = \Theta_{\text{FQI}}$. Later, in Proposition 4.8, we show that $\Theta_{\text{LSTD}} \supseteq \Theta_\pi$ always holds, and we also give necessary and sufficient conditions under which every solution of the target linear system is indeed a desired solution—that is, when $\Theta_{\text{LSTD}} = \Theta_\pi$.

We hope this fully addresses your question, and we’d be happy to clarify further if needed!

We are grateful for your insights and thank you again for your valuable comments.

Thank you so much for clarification. We definitely want to cite previous work appropriately.

We'd like to bring to your attention that theorem 3 from Perdomo et al. does not strictly prove all "linear estimators" will fail when $A_{LSTD}$ is singular. The informal version of theorem 3 at Page 5 differs from what the formal version on page 15 says. In the formal version and proof, it only proves the necessity of $A_{LSTD}$ being nonsingular under the linearly independent features assumption (covariance matrix is invertible). Please note that this is assumed in the second bullet in the statement of the theorem on page 15. However, in our proposition 4.8 we prove the TRUE necessary and sufficient conditions without the linearly independent features assumption. Their result is implied by ours, but our result is not implied by theirs because it is more general.

Additionally, the related results e.g. Theorem 4.2. and 4.3 of the Amortila, Jiang, and Szepesvari paper are also under assumption of linearly independent features (invertible covariance matrix) which is their Assumption 2.3, which we believe applies to all results in the paper. Nevertheless, even if they did not intend for this assumption to apply to their theorem 4.2, it is implied by their assumption on $\sigma_{min}$ in the statement of theorems 4.2 and 4.3.

Regarding the Amortila, Jiang, and Xie paper: We still need a little help understanding the connection. It seems that their work is concerned with questions of statistical efficiency under the assumption of linearly independent features (implied by part 2 of their coverage assumption, which requires a lower bound on the eigenvalues). Our work does not address statistical efficiency and also does not make a linear independence assumption. So, while that work seems quite interesting an important in terms of understanding the statistical efficiency challenges in applying our results in the batch setting, we do not see how it contradicts or subsumes our results. Please help us understand if we have overlooked something.

In any case, we will endeavor to cite these papers properly and correctly acknowledge their true contribution in any final version.

We say how our work differs from previous work throughout the paper. If there are places where we have failed, we are happy to make changes. Previous work gave important insights into some questions we address, especially sufficient convergence conditions. Focusing on linear case, we provide a fuller characterization - both necessary and sufficient conditions. Such a characterization for what is essentially the entire suite of core RL algorithms has never been provided before, even in the linear case.

Our results do not apply only in the expected TD setting. Our TD results extend to stochastic and batch settings (line 129 and appendix E.14). Results about PFQI and FQI are easily adapted to the batch setting (line 1802, line 1815). The expected matrix form is simply for cleaner exposition.

[1] explores the connection between TD and PFQI, and between PFQI and FQI, to understand better why target networks stabilize PFQI convergence for a general class of approximators. Our paper shares some similar goals, but is very different. We provide stronger, more varied, and more general results in the area of linear approximation. We also provide many additional results beyond those considered in [1] - see our response to reviewer KHfd.

The class of nonlinear approximators considered in [1] doesn't include all linear approximators - not even the case of linearly dependent features, which is thoroughly studied in our paper. This case is important: It captures what is happening in the final layer of most deep nets, where feature vectors often aren't linearly independent. Linear versions of assumptions in [1] are quite restrictive - much milder sufficient conditions were discovered years ago - explained later.

[1] only provides SUFFICIENT condition for TD, PFQI and FQI under some assumptions, and establishes convergence connections between TD and PFQI, and between PFQI and FQI, based on these conditions. We provide NECESSARY and SUFFICIENT conditions for convergence for each algorithm. We remove all standard assumptions under linear function approximation, such as the commonly assumed linear independence of features, and provide NECESSARY and SUFFICIENT conditions for TD, FQI and PFQI without this. We reveal the convergence connection between TD and PFQI, between PFQI and FQI, AND BETWEEN TD and FQI (there is no convergence connection analysis between TD and FQI in [1]). It is only with necessary and sufficient conditions that you can rigorously say one algorithm's convergence implies the other (e.g. thm. 8.1.), and fully characterize when and why it doesn't (e.g. line 369).

Response to RE-FORMULATIONS OF KNOWN RESULTS Contrary to the review, we never claim contribution for discovering or characterizing the TD fixed point equation nor the PFQI update equation. We cite the relevant sources.

Response to Analysis of FQI Thm. 1 from [1] implies a connection between conditions for convergence in the linear case and $\left(H_{\mathrm{FQI}}\right)^l$. Even in the linear case, that theorem would not fully characterize convergence of FQI as we did, since it would only provide a sufficient condition. Second, from the necessary and sufficient conditions we provide in our thm. 5.1, we see that the condition of thm. 1 from [1] is not entirely sufficient as it omits the required consistency condition.

You mention slight generalization for using pseudo inverse, but this ignores why it's there. It is because we studied the case where the covariance matrix is not invertible or features are not linearly independent, leading to new insights, e.g. Prop. 3, App. B2, and it is a key component in understanding the influence of that setting on convergence of FQI (sec 5.1).

Response to Analysis of TD

[2] is noted for its on-policy TD result. Our paper is in the off-policy setting, a much more general case. In the on-policy setting our paper is the first show (line 299) that the common assumption of linearly independent features from [2] can be dropped.

[1] only provides a sufficient condition for TD convergence for a class a nonlinear approximator. Its contribution is mostly for the nonlinear part, not the sharpness of the condition. In the linear case, it's just a sufficient condition already covered in [34]. [34] proves that eigenvalues having negative real parts is sufficient, but [1] is stricter: strictly negative eigenvalues. Both are covered by cor. 6.2. which provides NECESSARY and sufficient conditions for TD, and cor. 6.3 identifies all possible learning rates that make TD converge.

Your comment about our use of the spectral norm is puzzling because we never use any spectral norm.

Response to Analysis of PFQI Eq. 7 in [1] uses Jacobian analysis to explore connections between TD and PFQI, and between FQI and PFQI. Converting to the linear case, it's not equal to preconditioner analysis. The Jacobian matrices of TD and FQI in eq. 7 are completely different from the preconditioner of TD and FQI. In Eq. 7, TD's Jacobian matrix $\bar{J}_{T D}^{\star}$ is

$I-\alpha\left(\Sigma_{c o v}-\gamma \Sigma_{c r}\right)$ . Our preconditioner is just $\alpha$. Also, thm. 3 in [1] only shows that assumptions 1, 2, and conditions on $C(\alpha, k)$ are sufficient for convergence of PFQI. We show the preconditioner of TD, FQI and PFQI largely determine the convergence properties of each algorithm, providing necessary and sufficient conditions for convergence of each.

As you say, $C(\alpha, k)<1$ is a stricter condition than $H_{PFQI}$ being semiconvergent, and even $H_{PFQI}$ being semiconvergent alone is not enough as necessary and sufficient condition for PFQI; it also needs a consistency condition for a complete necessary and sufficient condition for FQI. Also, there is a gap between sufficient condition and a necessary and sufficient condition; the latter is mandatory to establish the complete convergence connections between different algorithms.

Difference between Thm. 8.1 and thm. 2 in [1]: thm. 2 provides SUFFICIENT conditions (assumptions 1-4) for convergence with diminishing step sizes for PFQI, and these SUFFICIENT conditions also include SUFFICIENT conditions for TD to converge. Therefore, this established a connection between sufficient convergence conditions of TD and PFQI, but it does not imply PFQI always converges if TD converges. On the other hand, our thm. 8.1 shows that there exist constant step sizes for which TD convergence NECESSARILY implies PFQI convergence. That's a much stronger result because it covers every possible case where TD converges, where thm. 2 only holds when specific TD sufficient condition holds. One of these conditions (assumption 4) is a strong condition for linear approximation - less strict conditions were provided in [34] from 2002.

For your comment on Thm. 8.3, the learning rates conditions are not the same. Our $\frac{2}{\lambda_{\max }\left(\Sigma_{\operatorname{cov}}\right)}$ is only dependent on covariance matrix, however, $\frac{2}{\lambda_H^{\star}}$ where

from [1] are obviously also dependent on learning rate $\alpha_l$.

Thm. 4 of [1] doesn't cover the result that convergence of FQI implies convergence of PFQI for large enough $t$, as [1] only provides sufficient conditions for FQI and PFQI convergence, then establishes connection between two sufficient conditions. That's not enough to say, in general, that convergence of FQI necessarily implies convergence of PFQI for large enough $t$.

We never claim that convergence of PFQI implies convergence of FQI, even when TD does not converge as novel conclusion in this paper. In fact, "convergence of PFQI implies convergence of FQI" is not necessarily true, specifically when features are not linearly independent, as shown in Sec 3 and App B.2 that PFQI and FQI are not solving the same linear system, therefore, the convergence of PFQI for large enough $t$ can not even guarantee the existence of fixed point for FQI, nor convergence. As mentioned before [1] only establishes connection between sufficient conditions for PFQI and FQI. Therefore, it is not a consequence of [1] either.

Response on concern about line 32 "strawmanning": We do not refer to [1] here. Nevertheless, we believe we do correctly represent an intuition that is widely held in the community.

Response on NOT A SIGNIFICANT ENOUGH CONTRIBUTION We hope we have clarified many ways our paper is different from [1], going well beyond what can be inferred by specializing the results from [1] to the linear case, and answering many open questions not addressed by [1] or any previous authors. We also hope we have clarified that our results do not apply only to expected TD, and explained that such a complete characterization of core algorithms has never before been provided for any function approximation class.

Response on LITTLE PRACTICAL BENEFIT As our paper is the only paper to provide a complete characterization of the convergence behavior of linear function approximation for all major algorithms in the expected, batch, and stochastic cases, it should be the definitive resource for anybody using linear value function approximation. The idea that the possibility of regularization makes understanding the behavior of unregularized systems of little practical benefit seems dismissive. At minimum, it's helpful to know when and why regularization may be needed. We demonstrate a huge gap between what can be said about the linear case and what is known about the non-linear case, where few results on necessary conditions exist. As is often the case, we expect that resolving fundamental, unresolved questions in the linear case will eventually help answer similar questions in the non-linear case, perhaps starting with the final, linear layer in many deep networks.

Thank you for the review. Would the referee please take a look at the rebuttal to assess the merits of the authors' arguments? Notably on the value of necessary and sufficient versus only sufficient conditions, and the fact that the class of approximators considered is not a special case of those in [1], and in addition has value when the features are not linearly independent; but also their other arguments on the preconditioner etc.