A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning
Authors: Zechen Wu
Amy Greenwald
Ronald Parr
Venue: NeurIPS 2025 spotlight ()
Keywords: Policy Evaluation
Temporal Difference Learning
Fitted Q-iteration
Target Network
Offline RL
Linear Function Approximation
Matrix Splitting
Primary area: reinforcement_learning

Abstract: In off-policy policy evaluation (OPE) tasks within reinforcement learning, Temporal Difference Learning(TD) and Fitted Q-Iteration (FQI) have traditionally been viewed as differing in the number of updates toward the target value function: TD makes one update, FQI makes an infinite number, and Partial Fitted Q-Iteration (PFQI) performs a finite number. We show that this view is not accurate, and provide a new mathematical perspective under linear value function approximation that unifies these methods as a single iterative method solving same linear system, but using different matrix splitting schemes and preconditioners. We show that increasing the number of updates under the same target value function, i.e., the target network technique, is a transition from using a constant preconditioner to using a data-feature adaptive preconditioner. This elucidates, for the first time, why TD convergence does not necessarily imply FQI convergence, and establishes tight convergence connections among TD, PFQI, and FQI. Our framework enables sharper theoretical results than previous work and characterization of the convergence conditions for each algorithm, without relying on assumptions about the features (e.g., linear independence). We also provide an encoder-decoder perspective to better understand TD’s convergence conditions, and prove, for the first time, that when a large learning rate doesn’t work, trying a smaller one may help(for batch TD). Our framework also leads to the discovery of new crucial conditions on features for convergence, and shows how common assumptions about features influence convergence, e.g., the assumption of linearly independent features can be dropped without compromising the convergence guarantees of stochastic TD in the on-policy setting. This paper is also the first to introduce matrix splitting into the convergence analysis of these algorithms.

A Unifying View of Linear Function Approximation in Off-Policy Reinforcement Learning through Matrix Splitting and Preconditioning
Zechen Wu
Amy Greenwald Department of Computer Science
Department of Computer Science Duke University zechen. wu@duke. edu
Brown University
amy amy-greenvalldbboom.. edu
Ronald Parr
Department of Computer Science
Duke University parrêcs duke. edu
Abstract
In off-policy policy evaluation (OPE) tasks within reinforcement learning, Tempo- ral Difference Learning(TD) and Fitted Q-Iteration (FQI) have traditionally been viewed as differing the number of updates toward the target value function: TD makes one update, FQI makes an infinite number, and Partial Fitted Q-Iteration (PFQI) performs a finite number. We show that this view is not accurate, and provide a new mathematical perspective under linear value function approximation that unifies these methods as single iterative method solving the same linear system, but using different matrix splitting schemes and preconditioners. We show that increasing the number of updates under the same target value function, i.e., the target network technique, is transition from using constant preconditioner using a data-feature adaptive preconditioner. This elucidates, for the first time, why TD convergence does not necessarily imply FQI convergence, and establishes tight convergence connections among TD, PFQL, and FQI. Our framework en- ables sharper theoretical results than previous work and characterization of the convergence conditions for each algorithm, without relying on assumptions about the features (e.g., linear independence). We also provide encoder-decoder per- spective to better understand the convergence conditions of TD, and prove, for the first time, that when a large learning rate doesn't ' work, trying smaller may help. Our framework also leads to the discovery of new crucial conditions features for convergence, and shows how common assumptions about features influence convergence, e.g., the assumption of linearly independent features can be dropped without compromising the convergence guarantees stochastic TD in the on-policy setting. This paper is also the first to introduce matrix splitting into the convergence analysis of these algorithms.
Introduction
In off-policy policy evaluation (OPE) tasks within reinforcement learning, the Temporal Difference (TD) algorithm [6 38 can be prone to divergence (2) while Fitted Q-lteration (FQI) [5] 31 24
reputed be more stable (3). Traditionally, TD and FQI are viewed as differing the number of updates toward target value function: TD makes one update, FQI makes an infinite number,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

and Partial Fitted Q- Q-Iteration (PFQI) performs a finite number, similar to target networks in Deep Q-Networks (DQN) [27]. Fellows al. [T6] showed that under certain conditions that make FQI converge, PFQI can be stabilized by increasing the number of updates towards the target. The traditional perspective fails to fully capture the convergence connections between these algorithms and may lead to incorrect conclusions. For example, one might erroneously conclude that TD convergence necessarily implies FQI convergence.
This paper focuses on policy evaluation, rather than control, while using linear value function approximation without assuming on- on-policy sampling. We provide a unifying perspective on linear function approximation, revealing the fundamental convergence conditions of TD, FQI and PFQI, and comprehensively addressing the relationships between them. Our main technical contribution begins in Section []] where we describe these algorithms as the same iterative method for solving the same target linear system, LSTD 10 28 The key difference between these methods their preconditioners, with PFQI using a preconditioner that transitions between that of TD and FQI. However, we also show in Section &
that the convergence of one method does not necessarily imply convergence of the other. Additionally, we show that the convergence of these algorithms depends solely on two factors: the consistency of the target linear system and how the target linear system is split to formulate the preconditioner and the iterative components.
In Section 4 we analyze the target linear system itself. We examine consistency (existence of solution) and nonsingularity (uniqueness of solution), providing necessary and sufficient conditions for both. We introduce a new condition, rank invariance, which necessary and sufficient to guarantee consistency of the target linear system regardless of the reward function. We demonstrate that this condition is quite mild and is naturally satisfied in most cases. Rank invariance, together with linearly independent features, form the necessary and sufficient conditions for the target linear system to have a unique solution. We also demonstrate that when the true Q-functions can be represented by the linear function approximator, any solution of the target linear system corresponds to parameters that realize the Q-function and only if rank invariance holds.
Sections 5 to 7 study the convergence of FQI, TD, and PFQI, providing necessary and sufficient conditions for convergence of each, with interpretations of these conditions and the components of the fixed points to which they converge. We also consider the impact of various common assumptions about the feature space on convergence. For FQI, when rank invariance holds, the splitting of the target linear system into its iterative components and a preconditioner is a proper splitting 14. This yields relaxed convergence conditions and guarantees a unique fixed point, providing a theoretical explanation for why FQI exhibits greater robustness in convergence in practice. While it is known that on-policy stochastic TD converges assuming a decaying learning rate and linearly independent features [0), we prove that the assumption of linearly independent features can be dropped. For PFQI, we prove that when the features are not linearly independent, increasing the number of updates toward the same target without reducing to smaller learning rate cause divergence. In methods that infrequently update the target value function (c.g.. DQN), increasing the number of updates toward each target value function can be destabilizing, particularly when the feature representation is poor.
Section 8 uses our results for the convergence of PFQI, TD, and FQI, along with the close connection between their preconditioners, to reveal PFQI's convergence relationship with TD and FQI, elucidating why the convergence of TD and FQI do not necessarily imply convergence of each other.
Related work Bertsekas and Tsitsiklis (6] provided early results on convergence and instability of TD. For linearly independent features, Schoknecht [4] provides sufficient conditions for TD convergence. Fellows et al. [16] propose a sufficient condition for TD convergence with general function approximation. Lee and Kim (25] studies sinite-sample behavior of TD from a stochastic linear systems perspective, while more recent convergence results in OPE scenarios are documented by Dann et al. [13]. Tsitsiklis and Van Roy [40], and Borkar and Meyn [8] present an ODE-based view connecting expected TD and stochastic TD, allowing application of results from Harold et al. [19] Borkar and Borkar 77. Benveniste et al. [3) These results establish almost sure convergence of stochastic TD to a fixed-point set, aligning with previous expected TD results B
Voloshin et al. 43 empirically evaluates performance of FQI on various OPE tasks, and Perdomo et al. 30 provides finite-sample analyses of FQI and LSTD with linear approximation under linear realizability assumptions. PFQI can be interpreted as adapting the target network structure from

---

Mnih et al. (27 to the OPE setting. Fellows et al. []6] and Zhang et al. [45] show that under certain conditions ensuring FQI convergence, increasing the number of updates toward the same target value function can also stabilize PFQI. Che et al. [[]] shows that under linear function approximation, and numerous assumptions on features, transition dynamics, and sample distributions, increasing updates toward the same target value stabilizes PFQI providing high-prou high-probability bounds on estimation error.
The unifying view provided in this paper provides a simpler and clearer path definitively answering many longstanding questions, while also allowing us to clarify and refine some observations made in previous work. Corrections to previous results in the literature are discussed in detail in Appendix
2 Preliminaries
The Appendix A.I provides review of all linear algebra concepts and notation used herein.
An MDP a tuple. (S, (, where S is finite state space, A is a finite action space, P S x A + (SS) is a Markovian transition model, R : S x A + R is a reward function, and 0 < 7 S is discount factor. We focus on the common 0 < 7 < 1 case. A Q-function, Qx : x A + R, for policy, :: - ((A). represents the expected, discounted cumulative rewards starting from (s, a). In vector
where P E R form, Q- E Rhh h =| S x A I. with: Q+ R + >P (I- P(s' s, a.))((aa s'), is the row-stochastic transition matrix induced by x, (() and R E R is vector form reward function. Policy evaluation finds Q., a) for each as. In on- on-policy evaluation, data are sampled following x. In off policy policy evaluation, they are sampled with distribution pls. a), which can be uniform, user-provided, or implicit in sampling distribution. In the on-policy setting, any state-actions visited with nonzero probability can be removed from the problem, as it would be impossible to estimate their values under since they We assume ju(s, a) > 0 for every state-action pair that would be visited under т, i.e., the assumption of coverage [39]. We represent ju as a vector, μ E Ra, and = diag (μ)) In an on-policy setting, l the stationary distribution: μPx J..
be never visited.
In contrast with the tabular setting [14 21), large state and action spaces require function approxi- mation to represent the Q-function. The linear case is extensively studied because it is amenable to analysis, computationally tractable, and step towards understanding more complex methods such as neural networks, which typically have linear final layers. aatte-action pairs are featurized with d features Φ1 ... Φa. and corresponding d-dimensional feature vector, a(s, a) - RRd. In matrix form, Dbi,j] (;, a):), for (s, a); El S x A The goal of linear function approximation is to find 0 such that @0 = Qo R Q. We focus on a family of common algorithms interpreted as solving for 0 which satisfies linear fixed point equation known LSTD [10] 9 28 These algorithms share vector
state-action covariance (Ecov) and cross-covariance (Eer) matrices, and mean
Eoor == DD2, Eer == 2 TD,, 4, 0sr == DDR
(I)
2.1 Introduction to algorithms
The algorithms described below are presented in their expected form, in which the true transition matrices and complete feature vectors are employed. Appendix K provides additional details on the batch setting, in which these quantities are estimated from batches of data.
FQI The Fitted Q-iteration 31 24 (FQI) update takes the following form under linear function approximation (detailed introduction in Appendix A.3.Ip:
D = > Oz + Dt Prr
Stochastic TD and batch TD Stochastic Temporal Difference Learning (TD) 36 38 is an
iterative stochastic approximation method that does one update per (s,a, r, sample. With linear function approximation and learning rate R+ the update equation is Equation 33. Batch TD
(update below) uses the entire dataset instead of samples to update (detailed in Appendix K A full mathematical derivation of both forms is provided in Appendix A.3.2
0x+1 = 0 - a [Ø(s, a) (ø(s, a) T 0g ro(s', aa)T 0g - r(s, a))]
(3)
For more detailed definition of notation in Section 2 please Appendix A.2
3

---

This paper largely focuses on expected TD, which can be understood as modeling the expected behavior of a TD-style update applied to the entire state space simultaneously. This abstracts away sample complexity considerations, and focuses attention on mathematical and algorithmic properties rather than statistical ones, but the results in this paper can be easily adapted for stochastic TD and Batch TD (explained in the Appendix E.14). The expected TD update equation with linear function approximation Equation (4) (a detailed derivation provided in Appendix (.3.2):
Expected TD
1++1= = (I aoo + a(>Ecr + 0g.r)
Partially fitted Q-iteration (PFQI) PFQI differs from FQI and TD by employing two sets of parameters: target parameters 0g and learning parameters 0g., [T6]. The target parameters 0g parameterize the TD target [rQ0 (s', , a') r(s, a)], while the learning parameters OR,, parameterize the learning Q-function Qon.- While Oz., is updated at every timestep, 0g. is updated only every I timesteps. In this context, Qo in the TD target is referred to as the larget value function, and its value Qo (s, a) is called the target value. After t timesteps, we update the target parameters: 8g- Ok.c. DQN (27] popularized this approach, using neural networks function approximators, The net for the TD target is known as the Target Network. When using linear function approximator, the update equation at each timestep becomes: 0x,1+1 (1 a2ieor + a()),,0 + 0g.r). Modeling the update to 0x+1 as a function of 02 (a complete mathematical derivation is provided in Appendix A.3.3):
0k+1
Σ - Ferr (I aooo))
O2 + a
Σ
aCoo)) -0,r-
3 Unified view: preconditioned iterative method for solving linear system
The typical, vanilla, iterative method for solving a linear system Az b, where A E Rax and b E R"," is:
Fk+1 = (1 - A) Fk +
(5)
Convergence depends on consistency of the linear system and the properties I- Preconditioning via matrix M can improve convergence [33. MA Mb is called a preconditioned linear system, where nonsingular matrix M is called a preconditioner. Its solution is the same as the original linear system. The iterative method to solve this preconditioned system is:
1k+1
MA) vx + Mb
(6)
Now, convergence depends on the properties of H. The choice of preconditioner adjusts the conver- gence properties of the iterative method without changing the solution.
Unified view The three algorithms-TDe FQL, and Partial FQI are the same iterative method for solving the same linear system fixed point equation (Equation 7 but using different preconditioner M. We refer to this linear system the target linear system:
Enon
Eerr
TD uses positive constant preconditioner: MTD aT. FQI the inverse of the feature covariance as a precondi- tioner Equation (8) provides an example of such a formulation for TD. For detailed calculations and expressions for each algorithm, please refer to Appendix [.I When the target linear system is consis- tent, the matrix inversion method used to solve is exactly LSTD 9 28). Therefore, we denote the A matrix and vector b of the target linear system as ALSTD = (Ecov >err and BLSTD = 6s. and
matrix? 2 .MQqi Mipl as a preconditioner. PFQI uses MpFqi = a 2/= (1 - aLicov)'
"Here, we assume the invertibilityy of Eoon; later, we provide an analysis of FQI without this assumption. 'Here, we assume that (Ei=)(T (.Ean)))) is nonsingular for clarity of presentation. However, this assumption does not affect generality. Because Σ.m. is symmetric positive semidefinite and always easily find scalar such that (a....) has no eigenvalues equal guarantees that (2 (1 aLCcoo))) nonsingular for any eligible t.
under these conditions, Lemma B.2

---

LSTD as set of solutions of the target linear system, LLSID = {0 E The H matrix, defined .A,, for TD, FQI and PFQI HTD. Hrqi and Hrrqr, respectively.
Rd
(Ecor ~xEer) ) 0 = prr
0K+1 #2+1
I al (2co 22
+
al
0 o.r
(8)
Preconditioner transformation From above, we can see that TD, FQI, and PFQI differ only in their choice of preconditioners, while other components in their update equations remain the same-they all use ALSID as their matrix and ILSID as their matrix. Looking at the preconditioner matrix (M) of each algorithm, it is evident that these preconditioners in Equation (9). When = 1, the preconditioner of TTD equals that of PFQI. However, as t increases, the preconditioner of PFQI converges to the preconditioner of FQI. We can clearly see that increasing the number of updates toward the target value function (denoted by l)-a technique known as target network [27] essentially transforms the algorithm from using constant preconditioner using the inverse of the covariance matrix as preconditioner, in the context of linear function approximation.
strongly interconnected, demonstrated
aT TD
71000
co0
1=0
FQI
PFQT
FQI without assuming invertible covariance matrix Our unified view of FQI uses Mror = Eove as the preconditioner to solve the target linear system, but this requires full column rank Φ. When & not full column rank, we revert to the original form of FQI in (2). which we refer to as the FQI linear system (Equation (10), with solution set OrQI
7E Der)
Σt D0.
(10)
AFQI
brg
This also implies HFQI I AFQI- See Appendix B.2 2 for details, where also prove
Proposition [3.1] showing the relationship between the FQI system and the target linear system.
Proposition 3.1. (1) OLSTD 2 F (2) OLSTD Foo if and only if Rank (Eeov >Eer)
Rank (1 - 72ooo (3) If 4 is full column rank, OLTTD OfgI-
4 Singularity and consistency of the target linear system (LSTD system)
Consistency of the target linear system linear system Az = b has solution if and only b E (A), so the target linear system is consistent if and only if ÉLSTD E Col (ALSTD). Proposi- tion 4.2 provides the necessary and sufficient conditions on consistency for any R, i.c., universal consistency. We call this "Rank Invariance" (Condition 4.1 It can be easily achieved and should widely exist, as by Lemma C.2 it holds if and only if Et
can Eer has no eigenvalue equal to (detailed explanation in Appendix C.2) There are many other conditions equivalent to rank invariance as well (see Lemma C.I Rank invariance and linearly independent features (Condition 4.3) are distinct conditions: One does not necessarily imply the other (explanation in Appendix C.I)). Therefore, the existence of a solution to the target linear system cannot be guaranteed solely from the assumption of linearly independent features.
Condition 4.1 (Rank Invariance). Rank (Ø) Rank (Φ D(I ())))
Proposition 4.2 (Universal Consistency). The target linear system: T DD DR consistent for any RR'h if and only if rank invariance holds.
Nonsingularity of the target linear system Below, we identify rank invariance and linearly independent features (Condition 4.3) as necessary and sufficient conditions for nonsingularity of the target linear system. While rank invariance is not difficult to satisfy if linearly independent features (Condition (43) holds, it is nevertheless necessary condition that was overlooked by previous papers, e.g.. Ghosh and Bellemare [17. which mistakenly claimed that linearly independent features (Condition 4.3) alone sufficient to ensure the uniqueness of the TD fixed point the off-policy setting, assuming the fixed point exists.
5

---

Condition 4.3 (Linearly Independent Features). + is full column rank (linearly independent columns). Condition 4.4 (Nonsingularity Condition), ALSID = (+ D - (P))) is nonsingular.
Proposition 4.5. (Eeor - ) is nonsingular matrix (i.e., Condition 4.4 holds) if and only if db is full column rank (i.e., Condition 4.3 holds) and rank invariance (Condition holds.
Nonsingularity of the FQI linear system Unlike the target linear system, which requires both
linearly independent features (Condition 4.3 and rank invariance (Condition 4.1p to ensure the uniqueness of its solution, Proposition 4.6, we prove that the FQI linear system requires only rank invariance-bolte
necessary and sufficient conditions. This highlights the fundamental role of rank invariance and, more importantly, shows that the FQI linear system forms a more robust linear system whose nonsingularity is not restricted by independence assumptions but rather relies broadly satisfied condition.
Proposition 4.6. AFQr is nonsingular if and only if rank invariance (Condition 4.7 holds.
The consistency and nonsingularity of the target linear system in the over-parameterized setting are analyzed in detail, with results provided in Appendix J.1
Over-parametterizatonn
4.1 On-policy setting
Proposition 4.7 shows that in the on-policy setting, rank invariance holds, implying that the target linear system is universally consistent, and thus fixed points for TD, FQI, and PFQI necessarily exist. Moreover, when linearly independent features (Condition 4.3) also holds, Proposition 4.5 imppiess that the target linear system is nonsingular, aligning with Tsitsiklis and Van Roy [40], which proved that in the on on-policy setting with linearly independent features, TD has exactly one fixed point.
Proposition 4.7. In the on-policy setting, rank invariance (Condition 4.1 holds.
4.2 Fixed point and linear realizability
Assumption 4.8 (Linear Realizability). Q is linearly realizable in a known feature map Φ SSx Rd if there exists vector 8 E Rd such that for all (s, a) E S A, (x, o(s,a) a fT. iee. Qr = Φ6"
Proposition demonstttrsss three points: 1) the target linear system may remain consistent even when the true Q- Q-function is not realizable (O, = 0); 2) if the true Q-function is realizable, the target linear system is necessarily consistent, and every perfect parameter (any vector O,)) is guaranteed to be included in the solution set of target linear system; 3) when linear realizability holds, rank invariance is both necessary and sufficient to ensure that every solution target linear system is perfect parameter, further implying that rank invariance is necessary and sufficient condition to ensure that any fixed points of the iterative algorithm solving target linear system are perfect parameters.
Proposition 4.9. When linear realizability holds (Assumption 4.8) OLSTD 2 O, always holds, and OLSTD θ holds and only if rank invariance (Condition 4.1 holds.
The convergence of FQI
Theorem 5.1 establishes necessary and sufficient conditions for FQI convergence: 1) the linear system must be consistent; 2) HFQr must be semiconvergent. The fixed point it converges to
consists of two components: (1 (I- Aroi (Avai)") Gu. a vector from Ker (Aroi) associated with
initial point, and (Arqi) brot, the Drazin (group) inverse solution of FQI linear system A detailed interpretation of the convergence conditions and fixed points is in Appendix [DT Theorem [.1 establishes necessary and sufficient conditions for FQI convergence: 1) the linear system must be consistent; 2) HFQI must be semiconvergent. The fixed point it converges to consists of two
components: (T (T-Arqu Aroi (Aroi)P) 6n. a vector from Ker (Aroi) associated with initial point, and
'The Drazin inverse solution (Arqi)" brqi equals the group inverse solution (Arot)* # broi (Appendix D.I.

---

(Apoi) bFot, the Drazin (group) inverse solution of FQI linear system 8 the convergence conditions and fixed points in Appendix [.I]
A detailed interpretation of (Hror = - Argi) is semiconvergent. It converges 10
Theorem 5.1. FQI converges for any initial point Og if and only if (broi) E Col (Arqi) and
[Arei) brer + (I Aver (Arei))) Bo] OLSTD.
5.1 Rank invariance
When rank invariance holds, FQI is an iterative method that employs a proper splitting scheme [4 construct its iterative components and preconditioner for solving the target linear system (Lemma 5.2). which yields significant advantages. For example, the FQI linear system (Aroi) becomes nonsingular (Proposition 4.6, ensuring existence and uniqueness of the solution. This also ensures that not an eigenvalue of y y Eer, common cause of FQI divergence.
Proper splitting
Lemma 5.2. If rank invariance (Condition 4.1 holds, Lcor and Eer are a proper splitting of (Neov -er))
Corollary 5.3] addresses the impact of rank invariance on FQI convergence. The nonsingularity of FQI linear system is guaranteed, the of fixed points is just single point, and the requirement MFor(= 720 being semiconvergent is relaxed to (722 Ber < 1. Thus, rank invariance can help the convergence of FQL. Although doesn't 't transform the FQI linear system exactly the target linear system, the solution of the FQI linear system is also solution of the target linear system.
Corollary 5.3. If rank invariance (Condition 4.1 holds, FQI converges for any initial point Bu if and only if p (t Eer) < 1. It converges to
Ett En Eer Bo.n OLSTD-
Linearly independent features and nonsingular FQI linear system When + is full column rank, the FQI linear system becomes exactly equivalent to the target linear system (Section 3). Thus, the consistency condition changes to bLSTD Col (ALSTD), and Ecov becomes invertible. FQI is then an iterative method using Diou as a preconditioner to solve the target linear system, with MrQr = Emi and Hroi
MrQr Beyond this, the convergence conditions for FQI remain largely unchanged compared to Theorem which lacks the linearly independent features assumption. We conclude that the linearly independent features assumption does not play a crucial role in FQI's convergence but instead determines the specific linear system that FQI is iteratively solving The nonsingularity AFQI is an ideal setting for FQI, guaranteeing the existence and uniqueness of its fixed point, and reducing its necessary and sufficient conditions for convergence to p (HFQi) < 1 (Corollary (.3). The nonsingularity does not depend on linearly independent features but only on rank invariance (Proposition (.6),, which commonly holds in practice, making FQI inherently more robust in convergence. This observation partially explains why FQI is often empirically found to be more stable than TD, whose uniqueness of the fixed point relies linearly independent features (Condition 4.3).
Previously, Asadi et al. 11. Xiao et al. provided necessary and sufficient conditions for FQI convergence under the linearly independent features assumption and over- wer-parameterized setting, respectively, however, as we detail in Appendix they only sufficient conditions.
The over-parameterized setting is discussed in Appendix J.2 Also, the results in this section can be easily adapted to the batch setting, as explained in Appendix
The convergence of TD
Theorem 6.1
establishes necessary and sufficient conditions for TD convergence: 1) the linear system must be consistent; 2) HTD must be semiconvergent. The fixed point it converges to is composed of (I (ALSI)) lu. a vector from Ker (ALSid) associated with initial point,
'The Drazin inverse solution (Arqi)" begi equals the group inverse solution (Aro))* # bro (Appendix D.I. 6 "Do and D.. form proper splitting of (Ze.e - >>ir)
For a detailed conclusion and calculation refer to Appendix D.3
7

---

and (ALSTD) BLSID, the Drazin (group) inverse solution of the target linear system. For a detailed interpretation of the convergence conditions and fixed point, see Appendix E.T
Theorem 6.1. TD converges for any initial point Oo if and only if DISTD E Col (AISTD), and HyD is
semiconvergent. It converges to (ALSTD) BLSTD + (T (ALSTT)(ALSTT))) 80 E LLTTD
The convergence condition involves the learning rate a. We define TD as stable when there exists a learning rate that makes TD converge from any initial point lg For the formal definition, refer to Definition F. Corollary 6.2 provides necessary and sufficient conditions for the existence of a learning rate that ensures TD convergence. When such a rate exists, Corollary 6..3 identifies all possible values, showing that they form an interval (0, E), rather than isolated points, aligning with widely held intuitions: When a large learning rate doesn't I work, a smaller one may help. It presents so far the sharpest characterization
convergence of TD. The condition "ULSTD Col (ALSTD) is strictly positive stable" was previously shown to guarantee TD convergence under the assumption of [34]
Condition 4.3
Corollary 6.2. TD is stable if and only if the following 3 conditions hold: (1) Consistency condition:
BISTD Col (ALSTD) ) (2) Positive semi-stability condition: ALSTD is positive semi-stable (3)Index condition: Index (ALSTD) S 1. Additionally, if ALSTD is an M-matrix, the positive semi-stable condition can be relaxed to: ALSID is nonnegative stable.
Corollary 6.3. When TD is stable, TD converges if and only if learning rate a E (0,c), where
2 R(A)
min AEo(EEcv (00)
This highlights fundamental contrast between TD and FQI. Since TD's preconditioner is only constant, its convergence depends on ALSTD = D > an intrinsic property of the target linear system. In contrast, FQI employs convergence characteristics. Moreover, in Appendix F..5. we describe the target linear system as an encoder-decoder process, showing that TD convergence requires preservation of the positive semi-stability of the system's 's dynamics: D(T )P,), which is an M-matrix (Proposition (..). This explains why TD can diverge (2), even when each state-action pair represented by linearly independent feature vectors lover-parameterization and proves that TD convergence is guaranteed when these feature vectors are orthogona 2 (Proposition E.p.
fata-feature adaptive preconditioner that alters its
Linarly independent features, rank invariance, and nonsingularity There may be an expectation that TD is more stable if & is full column rank, but this does not guarantee any of the conditions of Corollary 6.2 Ghosh and Bellemare [1] claimed that under the assumption of Condition 4.3 the necessary and sufficient condition for TD convergence is ALSTD being positive stable, but detail Appendix[[ [ it is only a sufficient condition. Rank invariance ensures only the consistency of the target linear system but does not relax other stability conditions. When the target linear system is nonsingular, the solution of the target linear system (the fixed point of TD) must exist and be unique. The necessary and sufficient condition for TD be stable reduces to the condition that ALSTD is positive stable. More details about these results are presented in Appendix E.8
Over-parae parameterization We also provide convergence results (e.g, necessary and sufficient condi- tions) in the over- parammttrreee setting in Appendix [E.6] and also correct the over-parameterized TD convergence conditions provided in previous literature 44
On-policy TD without linearly independent features In the on-policy setting, it is well-known that if & has full column rank, then ( D(I - P is positive definite. This property serves as
the central piece supporting the proof of TD's convergence (40] aligns with and is well-reflected
in our off-policy findings in Corollary 6.2 as further explained in Appendix 1.. However, becomes positive semidefinite (39). property that longer guarantees TD stability. We demonstrate that even without assuming & is full rank, ② T D(I - PPa) ) is an RPN matrix (Proposition E.21 and prove that TD is stable without requiring & to have full column rank (Theorem 6.4), relaxing previous the full column rank requirements 40).
when does not have full column rank, + D DDT--P,
'(ALSTD) BLSTD = (ALSTD) # HLSD. which proved in Appendix F.1
Here, "orthogonal" does not imply "orthonormal." which imposes additional norm constraint.
8

---

Theorem 6.4. In the on-policy setting (μP, n = (4), when & is not full column rank, TD is stable.
Stochastic TD and Batch TD It is known that if expected TD converges to a fixed point, then stochastic TD, with decaying step sizes (as per the Robbins- Monooo condition 32 40) stricter step size conditions), will also converge to a bounded region within the solution set of the fixed point I 13 40]. Therefore, the necessary and sufficient conditions for the convergence of expected TD can be easily extended to stochastic TD, forming necessary and sufficient condition for convergence of stochastic TD to a bounded region of the fixed point's 's solution set. For example, stochastic TD with decaying step sizes, under the same on-policy setting but without assuming linearly independent features, converges
bounded region of the fixed point's solution set, relaxation of conditions in Tsitsiklis and Van Roy [40] that, to our knowledge, has not been previously established. Additionally, for batch TD, By replacing expected symbol with their empirical counterpart (e.g, Ecov + Ecov We can convert the convergence results of expected TD Batch TD.
The convergence of PFQI
In Theorem 7.1 the necessary and sufficient condition for PFQI convergence is established, compris- ing two primary conditions: 1) consistency of the target linear system and 2) the semiconvergence of HPFQI / - MPFQiALSTT The fixed point is sum of two components: (MPPOIAA.TTD) MPFQrIL.TTD. and (I - (MPrqiA ALSTD) (MprQr A D) Oo. a vector from Ker ( (ALSTD) associating with the initial point. For a detailed interpretation of the convergence conditions and fixed point, see Appendix F..T Also, the results in this section can be easily adapted to the batch setting, explained in Appendix K.3
Theorem 7.1. PFQI converges for any initial point Oa if and only if biSTD Col (ALSTD) and HrFo semiconvergent. It converges to the following point in OLSTD:
(MPFOIAISTD)) P MPFQIbISTD - (I - (A-(AFFAASSST)) (MPFgiALSTT) 0o-
(11)
Linearly independent features As we show Proposition F.2 linearly independent features (Con- dition 4.3) does not directly relax the convergence conditions above" However, linearly independent features can be indirectly helpful through PFQI's preconditioner, MpFQI a > Without it, !/FFQ = MrFQI ALSTI may diverge (explanation in Appendix F.3 except in some specific cases, like over- over-parameter parameterized representation, which we show in Appendix [T.3] where the divergent components can be canceled out. Thus, when the features are not linearly independent, taking a large increasing number of updates under each target value function will most likely not only fail to stabilize the convergence of PFQI. but can make it more divergent. This provides a more nuanced understanding of the impact of slowly updated target networks, commonly used in deep RI. While typically viewed as stabilizing the learning process, they can have the opposite effect the provided or learned feature representation is not good.
Rank invariance and nonsingularity Under rank invariance (Condition the consistency condition for the convergence of PFQI can be completely dropped. However, unlike FQI, the other conditions cannot be relaxed. Moreover, for the convergence of PFQI under nonsingularity (Condition 4.4). the fixed point is unique. In this case, Hrro must be strictly convergent (p (Proi) < 1) rather than merely semiconvergent. More detailed results are included in Appendix F.4
The necessary and sufficient conditions for the convergence of PFQI in the over- perr-aramtterieed setting are provided in Appendix J.3 and the influence of t on its convergence in this setting is also discussed.
Over- parameterization
8 PFQI as transition between TD and FQI
PFQI is often intuitively understood as a step from TD towards FQI, an intuition which suggests that stability might increase as the number of steps for which the target is held constant increases from I
Detailed definition on each symhol's empirical version, please see Appendix K
See Appendix F.3 for more details convergence conditions of FQI with linearly independent features.

---

(TD) towards infinity (FQI). This intuition is partly supported by Chen et al. [12, which shows stabilizing effect for target networks under some strong assumptions. This section provides the first general results on the convergence relationships between PFQI and its limiting cases of TTD and FQI the linear value function approximation setting. These results show that the intuitive understanding of these algorithms is mostly correct, but more subtle than it might initially seem, ultimately leading to surprising cases where TD converges but FQI does not, and vice versa.
We begin by considering what TD implies about PFQI. Our result shows relationship beween a and t rather than an unconditional implication:
Theorem 8.1. (when TD stability -> PFQI convergence) If is stable, then for any finite E N there exists E R that for any a E (0, ct), PFQI converges.
This relationship only holds when is finite. If + co, - is possible. Next, we consider what PFQI tells us about FQL. As with TD and FQL, the implication is not unconditional:
Proposition 8.2. (when PFQI convergence FQI convergence) For full column rank matrix & (satisfying Condition 4.3) and any learning rate E (0:
2 (Fane)))))) if there exists an integer
T E z+ such that PFQI converges for all 2 T from any initial point Og, then FQI converges from any initial point to-
One might wonder whether the convergence of FQI implies the convergence of PFQI when the features are linearly independent. This is not sufficient, but under the stronger assumption a nonsingular target system the relationship does indeed become bidirectional.
Theorem 8.3. (nonsingular target system: PFQI convergence <> FQI convergence) When the target linear system is nonsingular, the following statements are equivalent 1) FQI converges from any initial point 9g. 2) For any learning rate (0, Xmaz (Ecor) such for all L 2 T, PFQI converges from any initial point On
2
there exists an integer T Z
Surprising counterexamples Does TD stability imply FQI stability with linearly independent
features? Proposition 8.2 and Theorem 8.3 reveal that the convergence of PFQI for any sufficiently large implies convergence of FQI, which necessarily includes the case as f - co. However, the stability of TD does not necessarily guarantee the convergence of PFQI when - oo. As becomes larger, usually becomes smaller, shrinking the interval (0, ex),, from which is safely chosen. As t + 00, e could approach zero, causing this interval to vanish. Appendix G.3 presents examples with linearly independent features where TD is stable while FQI does not converge, and vice versa. We further analyze and establish conditions under which the convergence of TD and FQI imply each other in Appendix H
Discussion
We presented a novel perspective that unifies TD, FQI, and PFQI via matrix splitting and precondi- tioning, in the context of linear function approximation for OPE. This approach offers key benefits: simplifying convergence analysis, enabling sharper theoretical results, and uncovering crucial condi- tions and fundamental connections governing each algorithm's ''s convergence. This framework could also give insight into policy optimization. This perspective could be expanded to include other TD variants [36] 39 37 (88, and possibly nonlinear function approximation. Our results could also potentially inform design of new algorithms with improved convergence properties.
Acknowledgment
Zechen Wu and Ronald Parr were partially supported by ARO Grant #N911222210251.
References
[1] K. Asadi, S. Sabach, Y. Liu, O. Gottesman, and R. Fakoor. TD convergence: An optimization perspective, 2023. URL https::t////rae org/ abs/2306
10

---

[2] L. Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine learning proceedings 1995, pages 30-37. Elsevier, 1995.
[3] A. Benveniste, M. Métivier, and P. Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[4] A. Berman and R. J. Plemmons. Cones and iterative methods for best least squares solutions of linear systems, SIAM Journal on Numerical Analysis, 11(1):145-144, 1974.
[5] A. Berman and J. Plemmons, Nonnegative matrices in the mathematical sciences. SIAM, 1994.
[6] D. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
[7] V. Borkar and S. Borkar. Stochastic approximation: &dynaiccal systems viewpoint, volume 9. Springer, 2008
[8] V. S. Borkar and S. Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000.
[9] J. A. Boyan. Least-squares temporal difference learning. In International Conference Machine Learning, pages 49-56, 1999.
[10] S. J. Bradtke and A. G. Barto. Linear least-squares algorithms for temporal difference learning. Machine learning. 22(1):33 57, 1996.
[11] Che, C. Xiao, J. Mei, B. Dai, R. Gummadi, O. A. Ramirez, C. K. Harris, A. R. Mahmood, and D. Schuurmans. Target networks and over-parameetrrizaion stabilize off-policy bootstrapping with function approximation, 2024. URL httpp://arxii.... abcp//0b/240 21043
[12] Z. Chen, J.-P. Clarke, and S. T. Maguluri. Target network and truncation overcome the deadly triad in-learning. SIAM Journal on Mathematics of Data Science, 5(4):1078-1101, 2023.
[13] C. Dann, G. Neumann, and J. Peters. Policy evaluation with temporal differences: A survey and comparison. The Journal of Machine Learning Research, 15(1):809 8833099888880 2014.
[14] Dayan. The convergence of TD (A) for general X. Machine learning, 8:341-362. 1992.
[15] D. Ernst, P. Geurts, and I.. Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
[16] M. Fellows, J. Smith, and S. Whiteson. Why target networks stabilise temporal difference methods. International Conference on Machine Learning, pages 9886-9909. PMLR, 2023.
[17] D. Ghosh and M. G. Bellemare. Representations for stable off- off-policy reinforcement learning, 2020. URL https:ttttxxxi.....p org/ wttp://..rrggb/////0000 05520
[18] T. Greville. Note on the generalized inverse of matrix product. Siam Review, 8(4): 518-521, 1966.
[19] Harold, G. Kushner, and G. Yin. Stochastic approximation and recursive algorithm and applications. Application of Mathematics, 35(10), 1997.
[20] K. Hensel. Über potenzreihen von matrizen. 1926.
[21] S. Jaakkola, M. Jordan, and S. P. Singh. On the convergence of stochastic iterative dynamic programming algorithms, Neural Comput. 666): 1994. doi: 10.1.62/E00 6.1 185. httts:///// org/10..o/.o 11t/ 1991. 1185
[22] T. Kato. Perturbation theory for linear operators, volume 132. Springer Science & Business Media, 2013.
[23] M. G. Lagoudakis and R. Parr. Least-squares policy iteration. The Journal of Machine Learning Research, 4:1107-1149, 2003.

---

[24] H. Le, C. Voloshin, and Y. Yue. Batch policy learning under constraints. In International Conference on Machine Learning, pages 3703-3712. PMLR, 2019.
[25] D. Lee and D. W. Kim. Finite-time analysis of temporal difference learning: Discrete-time linear system perspective, 2023. URL wttpthttt////iiiii wwwp://wwwwrrrba////////a ab2/2244 10479
[26] C. D. Meyer. Matrix analysis and applied linear algebra. SIAM, 2023.
[27] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 518(7540):22-533,, 2015.
[28] A. Nedić and D. Bertsekas. Least squares policy evaluation algorithms with linear function approximation. Discrete Event Dynamic Systems, 13(1):79-110, 10, 2003.
[29] M. Ortega and Rheinboldt. Monotone iterations for nonlinear equations with application to gauss-seidel methods. SIAM Journal on Numerical Analysis, 4(2):171-190, 1967.
[30] J. C. Perdomo, A. Krishnamurthy, P. Bartlett, and S. Kakade. A complete ciaricccitionn of linear estimators for offline policy evaluation, 2022. URL http::///axxivv.or//aaaa 04236
[31] M. Riedmiller. Neural fitted iteration first experiences with data efficient neural reinforce- ment learning method. In European conference on machine learning, pages 317-328. Springer, 2005.
[32] H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[33] Y. Saad. Iterative methods for sparse linear systems. SIAM, 2003.
[34] R. Schoknecht. Optimality reinforcement learning algorithms with linear function approxi- mation. Advances in neural information processing systems, 15, 2002.
[35] Schröder. Lineare operatoren mit positiver inversen. Archive for Rational Mechanics and 1961.
Analysis,
[36] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3: 9-44, 1988.
[37] R. S. Sutton, C. Szepesvári, and H. R. Maei. A convergent O(n) algorithm for off-policy remporal-different learning with linear function approximation. Advances in neural informa- tion processing systems, ((21)):669-1611) 2008.
[38] R. Sutton, H. R. Maei, Precup, Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora. Fast gradient-descent methods for temporal-differenc learning with linear function approxima- tion. In Proceedings of the 26th annual international conference on machine learning, pages 993-1000, 2009.
[39] R. S. Sutton, A. R. Mahmood, and M. White. An emphatic approach to the problem of off-policy cemporal-differenn learning. Journal of Machine Learning Research, 17(73):1-29, 2016.
[40] J. Tsitsiklis and B. Van Roy. Analysis of temporal-diffferent learning with function approxi- mation. Advances in neural information processing systems, 9, 1996.
[41] R. S. Varga. Factorization and normalized iterative methods. Technical report, Westinghouse Electric Corp. Bettis Plant, Pittsburgh. 1959.
[42] R. S. Varga. Iterative analysis. New Jersey, 322, 1962.
[43] C. Voloshin, H. Le, Jiang, and Y. Yue. Empirical study of off-policy policy evaluation for reinforcement learning, arXiv preprint arXiv:1911.0685. 2019.
12

---

[44] C. Xiao, B. Dai, J. Mei, O. A. Ramirez, R. Gummadi, C. Harris, and D. Schuurmans. Under- standing and leveraging overparamelerization in recursive value estimation. In Interaational Conference on Learning Representations, 2022. URL httppst://pperreiiieeee wttptrreeiieeeee//rrrrr.. id=shbAgEsk3qM
[45] S. Zhang, H. Yao, and S. Whiteson. Breaking the deadly triad with target network. In International Conference Machine Learning, pages 12621-12631. PMLR, 2021.
13

---

A Preliminaries
A.1 Linear and matrix algebra
Given an n x m real matrix A, let Col and Row (A) denote its column and row spaces, respec- tively. The null space of A, denoted Ker (A), is defined as {i C Ar = 0}. The complementary subspace to Ker (A)),, denoted Ker (A), includes all vectors in R" that are not in Ker (A), formally expressed as Ker (A) = {u E R v & Ker (A)). Any vector two subspaces: either Ker (A) Ker (A), but not both. A 2 0 and A > 0 means matrix A is glement-wise nonnegative and positive, respectively. A is monotone when Ar 2 0 implies x 2 0, for all x E R". A and el are the conjugate transpose of matrix A and vector v, respectively. Given A E R=*m, .A is the Drazin inverse of matrix A, A is the group inverse of matrix A, and At is the
R" must lie in one of these
pseudoinverse of matrix A. If Col (A) Col (A then A = A².
Given an n X n square matrix A with eigenvalue A, vy is an eigenvector of A whose related eigenvalue is X; or (A) is the spectrum of matrix A (the set of its eigenvalues); pl () is the spectral radius of A (the largest absolute value of the eigenvalues); and R()A) represents the real part of complex number X. We call matrix A positive stable (resp. non-negative stable) if the real part of each eigenvalue of is positive (resp. non noggaeeatie)). and we call it positive semi-stable the real part of each nonzero eigenvalue is positive. A is inverse-positive when A exists and A 2 O. we define as the identity matrix, Index (A) denotes the index of A, which is the smallest positive integer s.t. Raxa = Col (A*) + Ker (A*) (or, equivalently, Col (A*) n Ker (A*) = 0) holds, where the symbol @ represents the direct sum of two subspaces. The index of nonsingular matrix is always O. When Index (A) = 1, AD = A# The index of an eigenvalue E a (A) for a matrix A is defined to be the index of the matrix (A Xí): index (A) Index (A 11--111 XI).
The dimension dim (V) of vector space V is detined be the number of vectors in any basis for V. Given a vector E V. ||e||| denotes the 4--norm for e and ||=|| denotes the p-weighted norm for v. alg mult (A) and geo mull (A) are the algebraic and geometric multiplicities, respec- tively, of eigenvalue X E a (A). If alg mull (A) = 1, we say that eigenvalue À is simple, and say that eigenvalue À is semisimple.
alg mult (A) geo mult (A), C=xn, the spectrum a (I A) of the matrix (I (I-A) A) is given by {1-A| AA E a [A)]. and AA E a (A), alg mult (A) = alg mult A (1-1)) X) and geo mult A (A) geo mullm A (1 X).
Lemma A.1. Given a matrix
This lemma is proved in Appendix A.I.I Every theorem, lemma, proposition, and corollary in this paper is accompanied by complete mathematical proof in the appendix, regardless of whether provide an intuitive explanation for its validity in the main body of the paper.
Linear systems: Given matrix A E: _ax and a vector 6 E RR", if there exists x E R" such that Ax = b, the linear system Ax is called consistent. Given vector b E R and matrix B E R if the linear system Az = Bb is consistent for any h E R.a we call this linear system universally consistent. If A can be split into two matrices M and N, such that A M N. M 2 0, and N 2 O. the splitting is called regular splitting [5] Chapter 5, Note 8.5] [1 35). 1- and M-1N 2 0, it is referred to as a weak regular splitting 442 Page 95, Definition 3.28] [29]. Lastly, if A can be split into matrices M and N such that A = M N, and additionally
Col (A) = Col (M) and Ker (A) = Ker (M), the splitting is called a proper splitting 4
Positive definite matrices:
The definition of a positive definite matrix varies slightly throughout the literature. The following definition is consistent with all the papers cited herein:
Definition A.2. The matrix A E C is called positive definite if R (a Ar) > 0, for all x E C")(O).
Lemma A.3. For a A E BR R (aHAA) O. for all E CTM, is equivalent x T > for all x E Re*
T Ax > 0, for all From Lemma A.3 we know that a matrix A E gaxx is also positive definite if x
E Rd (00). Property A.4. For any positive definite matrix A E Cuxn, every eigenvalue of has positive real part, i..., VA E a (A), R(A)= 0.
14

---

Sometimes the definition of positive definite matrix includes symmetry, leading to the statement that a positive definite matrix has only real positive eigenvalues and is necessarily diagonalizable. However, in this paper, the definition of a positive definite matrix does not require symmetry. Consequently, positive definite matrix may not have only real positive eigenvalues (as shown Appendix (A.1.2) or be necessarily diagonalizable (as demonstrated in Appendix A.1.3
Range Perpendicular to Nullspace (RPN) Matrices RPN matrix is a class of square matrices whose column space is perpendicular to its nullspace: {A E C Col (A) 1 Ker (A)} where Row (4), and EP Matrices. As shown in Property A.S) any RPN matrix necessarily has index less than or equal to 1. The following Lemma A.6 shows the fight connection between RPN matrices and positive definite matrices.
1. denotes perpendicularity. this is also equivalent to Col (A) = Col (AT)
Ker (A) Ker (A) [26] Page 408], sometimes it also called
Property A.5. If A E Ca is singular RPN matrix, then Index (A) 1.
Lemma A.6. For any positive definite matrix gax= and any matrix X e R X AX is an RPN matrix.
Semiconvergent matrices Definition A.7 provides the definition of semiconvergent matrix, while Proposition A.8 characterriss the conditions under which matrix qualifies semiconvergent matrix terms of its spectral radius and eigenvalues.
x is said be semiconvergent Definition A.7. [3] Chapter Definition 4.8] A matrix A E Rax= whenever limy A exists.
Proposition A.8. (26 Page 630] A matrix A is semiconvergent if and only if p(A) < or where x= = 1 is the only eigenvalue on the unit circle, and X is semisimple.
Z-matrix, M-matrix, and nonnegative matrices Definition A.9 provides the definition of Z- matrix, while an M-matrix is a specific type of Z-matrix, with its dehnition given in Definition A. Notably, the inverse of a nonsingular M-matrix is known to be a nonnegative matrix [5].
Definition A.9 (Z-marrix [5)) The class of Z-matrices are those matrices whose off-diagonal entries are less than or equal zero, i.e., matrices of the form: Z (2iz). where 2:y S 0, for all + j. Definition A.10 (M-matria (5). Let be can be expressed in the form = sl B, where B = (bxz). with bij 2 0, for all 1 S ú, S n, and 2 p (B).
real Z-matrix. Matrix A is also M-matrix if it
A.1.1 Proof of Lemma A.1
Proof. Given matrix A E C"x", denote its Jordan form as J, so there is nonsingular matrix P that:
= P-
Therefore,
-- T-A-1-P--p-P----P---
Since diagonal entries of matrix J are the eigenvalues of matrix A, and from above we can see that (I JJ) and (I A) are similar to each other. the two matrices share the same Jordan form. Moreover, because the Jordan form of I - J is itself, (I - J) is the Jordan form of (I A), then we know that diagonal entries of matrix (I - J) are the eigenvalues of matrix (7 - A), so a (1 A) J) is the same as of J, we have VA E a (A) alg mult, A (A) alg multi-A (1 A), geo geo mult (A) = geo mult, (1 A).
(1 V-AX E (A)). and since the size of every Jordan block of (I J)
A.1.2 Counterexample for real positive definite matrix having only real positive eigenvalue
Consider the matrix A 22 -1
2
1. Quadratic Form: Checking the quadratic form xf Ax:
x
32
T1
-
Ax = (x1
r2)
(
2 -1
2
x2
x1
15

---

= 2xf 2 - -122 2122 + 2r² 2x + 2r² > 0 for all x + 0.
The quadratic form is positive for all non-zero æ. Eigenvalues: To find the eigenvalues of A, solve the characteristic equation dct(A XT) =
det 2
-1 2 2 (2 X)(2 - >) (-1)(1) X² 4A + 5=0.
The solutions to the characteristic equation are:
A 4 /16 - 20 4 4 2
2
The eigenvalues are + and i, which are complex.
Thus, A is an example of a non-symmetric matrix with positive quadratic form but having complex cigenvalues.
A.1.3 Counterexample of a real positive definite matrix as necessarily diagonalizable
An example of a positive definite but non-symmetric matrix that is not diagonalizable is:
1 1)
A
This matrix is positive definite because:
x T Ax 21
32 ) 1
11
of (x) 1001++000 x2) x2 27 x1 + x
T2
for all xı * and * O. However, A is not diagonalizable because it has single eigenvalue, 1, with algebraic multiplicity 2 but geometrie multiplicity 1. Thus, it does have full set of linearly independent eigenvectors.
Therefore, while A being positive definite implies certain spectral properties, it does not guarantee that A is diagonalizable if A is not symmetric.
A.1.4 Proof of Lemma A.3
Lemma A.11 (Restatement of Lemma A.3 R" (0).
For A Rux", R (x*Ax) > 0fror all a E C0)
equivalent to (x" Ax) for all
Proof. Assume (x Ar)) 0 for all RR (0), then know (T (TTAr) 0 for
all E IR" (00), so we have (x (A + A A)))) > 0 for all x E I (0). It is clear that (A A is
a symmetric, real matrix, and by Lemma A.12 we know that this implies (= + A )æ) > 0 for
all x E (C). Then by Lemma A.13 and the fact that is real matrix, we obtain R (a Ar) > 0 for all x E (0).
Conversely, assume R (2.HAA) 0 for all (C). Since (xTAx) is real number for all R [0). it follows that (z Ar) > 0
Hence, the proof is complete.
Lemma A.12. Given a symmetric matrix Roxn, T Ax 0 for all x E (*). then # Ar > for all x e (0).
Proof. Given that A is symmetric real matrix and T Ax > 0 for all x E R²), we need to show that H Ax for all (*).
Let C be an arbitrary nonzero complex vector. We can write x as z u + iv, where u and real vectors in R
The quadratic form in the complex case is " Ar:
z Ax (u - - +vv)
16

---

bi, and we know Expanding the expression, we get:
Ti x Ar u Au iv Au + iu Av + AvvAv Av.
Since A is symmetric, v Au (u T A v) (u Av) =u Av. Therefore:
x H Ar u Au + v Av.
Since u and v are real vectors, and is positive definite, we have:
Au 0 for + 0
T Av for v +
For x + 0, either u + or + (or both). Therefore:
u T Au v Av > 0.
Thus, A Au Av for all Cm
Lemma A.13. Given matrix A Cuxa and for all x E (*), (A"(A+ A4)a) is real number, and (A + yz) has the same sign as (x Ax).
Proof. Define the quadratic form of A as H Ax = a + bi where a and are the real part and imaginary part of the complex number, then we have x. A (x Ax) H that
n! (A+ (A+A")== x= = x." Ar H A
bi + bi 20,
so quadratic form H (A+ A x is always real for any x E C", and it shares the same sign with Rxx Az) = a.
Lemma A.14. Ifa matrix A E C is Hermitian, then it is positive definite if and only if x Ar for all x E (0).
Proof. Define quadratic form of A as H Ar + where a and b are the real part and imaginary part of the complex number, then we have " " = (xx AAx) H = a bi. Because A is Hermitian, + bi bi, which implies b= = 0, so H A a, meaning the quadratic form is always a real number. If H A _ > we have:
1 A
x
Ax
x .
+
A
A
2 AA" x
2
x
H
(A+
-A") x
(12)
= x
(A+
x
_
H (A (A-A#) 4
2
Because A is Hermitian,
H (A- (A- 1 A
H 0
Therefore, obtain
H Ax
xx x
(A+ (A+
x= (a bi + bi) =a,
2
so H Ar is real number for all E Ca, equivalent to AA > 0 for all x E C" (0)..
Subsequently, Re Ax) for all E C*)(0) is
17

---

A.1.5 Proof of Lemma A.6
Lemma A.15 (Restatement of Lemma A.6 For any positive definite matrix A E RRxx and any matrix X " X AX is an RPN matrix.
Proof. Given positive definite matrix A E Rax" and a matrix X E R"xm then by the definition of RPN matrix, we know that X AX is RPN matrix if and only if
Ker (XTAX)
AX) = Ker
First, by Lemma A.16 we know that
Ker (X AAX = Ker (X).
Second, by Lemma A.17 it is clear that XT also a positive definite matrix, then the following holds:
Ker (XT A x) Ker (X)
Therefore,
Ker (XTAX) AX) Ker (IxTAX] )
Hence, X AX is RPN matrix.
Lemma A.16. Given any positive definite matrix A E Raxn and any matrix X E R
Ker (XTXX) Ker (X)
Proof.
Ker
(x C" (XT AX) x 0)
(13)
(x E Cm x AXr = 0}
(14)
(x E C"
Xx = 0}
(15)
Ker (X)
(16)
The step from Equation
to Equation 15 because is positive definite, and by definition
Vx E C
\ {0), R(* Az) > 0.
So x H AXx 0 iff vector Xx 0, so Equation 14 Equation
15) holds. Next, it is easy to see
that
Vr E Ker (X), [XTAX] x=
which means Ker (X) C Ker (xT AX), together with Ker (xT AX) C Ker (X), we can get Ker (X) (TAX)) "AX) Ker (X).
Lemma A.17. A conjugate transpose of positive definite matrix is also a positive definite matrix.
Proof. Given
positive definite matrix A, define the quadratic form of A = Ar bi,
where is real part and b is imaginary part. Then, we have x 4 (a. Ar) = a - bi; therefore R(A) ).
Hence, V' E C", C",R("" Ar) > 0 then Vo E C", R(* (.clAaa Az) > 0, vice versa.
A.1.6 Proof of Property
A.5
Property A.18 (Restatement of Property
A.5 Given any singular RPN matrix A C"xn
Index (A) 1.
Proof. Given an singular RPN matrix A E p by its definition, we have Col (A) Ker (A),
which implies Col (A) Ker (A) 0. By definition of index of singular matrix, we know that
Index (A) 1.
18

---

A.2 MDPs
An MDP classically defined as a tuple, (S.A, R. 7), where S is finite state space, is a finite action space, P: S x A + A(A) is a Markovian transition model defining the conditional distribution over next states given the current state and action, where we denote A(x)) as the set of probability distributions over a finite set X. P(s') s,a), R: S x A + IR is a reward function, and < > S is discount factor. The 7 = case requires special treatment, both algorithmically and theoretically, so we focus on the common 0 < < 1 case. A Q-function QT S x A + IR for given policy : S + A (A) assigns value to every state-action pair (s,a) E x A. This value, called the Q-value, represents the expected cumulative rewards starting from the given state-action pair. Q-functions can also be represented as a vector QT E IR", where = S x A The Q-function satisfies the Bellman equation:
= R = -T
where PT hg is the Markovian, row-stochastic transition matrix induced by policy и. The entries of P- represent the state-action transition probabilities under policy म, defined as (x((s,a), a')) = P(s' s, s,a)=(a' 8'), and E R is the reward function in vector form.
Policy evaluation Policy evaluation refers to the problem of computing the expected discounted value a given policy, such as estimating the Q-value for each state-action pair. on-policy policy evaluation, data (state-action pairs) are sampled following the policy being evaluated. Conversely, In off-policy policy evaluation, the data sampling does not need to follow the policy being evaluated and is often based on different behavior policy. State-action pairs are visited according to distribution ju(s, a). which can be uniform, user-provided, or implicit in a sampling distribution. For example, p1s, a) could be the stationary distribution of an ergodic Markov chain induced by behavior policy. It is worthwhile to mention that in the on on-policy setting, any state-action visited with nonzero probability can be removed from the problem, and in the off off-policy setting, it would be impossible to estimate the values under π if the state-action pairs would be visited under π could never be sampled according to μ and their consequences were never observed. Therefore, that y0s, a) > O for every state-action pair that would be visited under т. This assumption referred to as the assumption of coverage [39]. Accordingly, we define μ as a distribution vector, μ E IR where each entry represents the sampling probability of state-action pair. Subsequently, we define the distribution matrix = diag (1)). which is a nonsingular diagonal matrix with diagonal entries corresponding to the sampling probabilities of each state-action pair. In particular, in on-policy setring. the relationship μPP, = f holds, meaning that the distribution μ aligns with the stationary distribution induced by the target policy т. In contrast, in an off off-policy setting, μP, does not necessarily hold, as the sampling distribution js may be influenced by a behavior policy that differs from π.
assume
Function approximation Although the state and action sets S and are assumed be finite, but the states-action space usually is very large, so it is unrealistic to use a table to represent the value of every state-action (which is known as the tabular setting [4 21), so use function approximation to represent the Q-function is necessary. In such cases, some form of parametric function approximation is frequently used. Linear Function Approximation is the most extensively studied form because is both amenable to analysis and computationally tractable. An additional motivation for studying linear function approximation, despite the growing success and popularity of non-linear methods such neural networks, is that the final layers of such networks are often linear. Thus, understanding linear function approximation, while of interest in own right, can also be viewed as stepping stone towards understanding more complex methods.
When function approximation is used, each state-action pair is featurized with a d-dimensional feature vector, Φ(8, a) + Rd, and corresponding feature matrix:
((ssa))) Φ = )((s,a)2)
E RlSxAIIx
(17)
((ss, T)
Given this feature matrix, for some nimen-dimensional parameter vector 0 E IRd, we can build a linear model of the Q function Qo(s,a) = Φ(s, T 0, for all state-action pairs (s, a). The goal of linear
19

---

function approximation is to find f such that o = Qo 22 Q. In this paper, we focus on a family of commonly used algorithms that can be interpreted as solving for & which satisfies linear fixed point equation known as LSTD 10 9 28 In the following, we introduce several quantities arising from linear function approximation. The state-action covariance matrix, Econs and the cross-covariance matrix, Eer, are defined as:
Exoo
E (s,a)~p
())(s)) Φ DT
Eer ==
E
a') -PPP4
(x.0)-p s s' 1=P((l.))
Additionally, the mean feature-reward vector, fg. is given by:
0
E [d(s,a)(s,aa) DR. (e.atop
A.3
Introduction to algorithms
A.3.1
FQI
Fitted Q-iteration 31 24 is one of the most popular algorithms for policy evaluation in practice. While typically applied in batch setting, the expected or population level behavior of FQI is modeled below. In full generality, in every iteration, FQI uses an arbitrary, parametric function approximator, Qo(s,a), a). and uses some function "Fit" which is arbitrary regressor to choose parameters, 0 to optimize fit to a target function:
8 Fit(yP.Qu, + R).
The more detailed form
0x+1
arg min
E (a ((.aa)))'mmx(
((o((s,)->00 (r,,))-r(s,a))) (18)
When using linear function approximator Qa(s, ((s, (Ts,a))o the update is shown below. For the detailed derivation from Equation (19 to Equation (20) please see Appendix [A.344
( (o(s,a)To- - T00 a') 0x - r(s,
ot+1 arg min
E (,,0)~u s P( (s,a)) (s())
(19)
0
= =1 Eg Or + Elan 6grr.
(20)
FQI in the batch setting Given the datset {(s;, ri approximation, at every iteration, the update FQI involves iterative solving a least squares regression problem. The update equation is:
ri (ss, a:) s/ af) M- with linear function
0k+1 =arg min Σ (8) T r (8i, 76 (s%, 0ee 06)²
(21)
Et + Stor 0s.
(22)
A.3.2 TD
Temporal Difference Learning 36 38 is the progenitor of modern reinforcement learning algorithms. Originally presented as a stochastic approximation algorithm for evaluating state values, it has been extended the evaluate state-action values, and its behavior has been studied in the batch and expected settings as well. When tabular representation is used, TD known to converge the true state values. We review various formulations of TD with linear approximation below.
20

---

Stochastic
TD
TD is known as iterative stochastic approximation method. Its update equation is
Equation 23
When using linear function approximator Qo(s, a) Φ(s, a) 8, the update equation
becomes Equation 25 where E IR+ is the learning rate:
0% - a Vo, Qa. (s, a) (Qo, (s, -Q0 (s', ,') - -
(23)
where ((ta)m)
(24)
=
0₂ - a (0(s a) (Ø(s, () 0g r0(5', (0((s'.')) a') 0g - r(s,
(25)
Batch TD In the batch setting offline policy evaluation setting, TD uses the entire dataset instead of stochastic samples to update:
Mx+1 = 02 a
a (s, (oo -e -(()))r(ss000 r(s.a))
(26)
7
02 a
[db(s, a) (o(s, On 7 r(s,a))]
(27)
02 a [Eeoo - Eer ON 0prr
(28)
Expected TD the behavior of batch TD in expectation. This abstracts away sample complexity considerations, and focuses attention mathematical and algorithmic properties rather than statistical ones. The expected TD update equation is:
This paper largely focuses expected TD, which can be understood as modeling
0x+1 Og a
E (2,0)-p (
[V (Qo, (d, r(s (29)
s'
With a linear function approximator Qo(s,a) = ((s,a)
Ok+1 02
E
(p(s, (ø(s, a) T) ~o(s'' r(s,a))]
(30)
(s,0)1u s' (s((')
= (I - aLenn - --Eerr 03 + a0pr
(31)
= O2 a ( DΦ0 - 7 DP, 20,- - -DDR)
(32)
(33)
A.3.3 PFQI
PFQI differs from FQI (Equation (88) and TD (Equation (9h) by employing two distinct sets of parameters: target parameters 0₂ and learning parameters Ux [6]. The target parameters 0₂ parameterize the TD target [7Q0, (8', - r(,, a)). while the learning parameters Oz., parameterize the learning Q-function Qo While 6R. is updated at every timestep, 0₂ is updated only every t timesteps. In this context, Qo in the TD target is referred as the target value function, and its value Qa, (s, a) is called the target value. Under fixed TD target, the expected update equation at each timestep is:
0..+11 = OR.t - a
E (s,a)=p
[Von, Qo,, (8, a) (Qa,, (8, 2Q,, r(s,
s' (lla)))) (a())
(34)
After timesteps, update the target parameters 0 with the current learning parameters 0k.
02 Ok.
(35)
DQN [27] famously popularized this two-ttoooreee woo-prrmetter approach, using neural networks as function approximators. In this case, the function approximator for the TD target known as the Target Network. This technique of increasing the number of updates under each TD target (or target value function) while using two separate parameter sets stabilize the algorithm is often referred to as the target network approach [16].
21

---

When using linear function approximator Qo(s,a) Ō(s, als, 8, the update equation at each timestep becomes:
0ct111 Ok.t
E (s.a)m
()( ()(ss,) 0z,, ro(o- a') r(s,
(36)
=0k, a DDO
T 1Dx200.- DD
(37)
= - aaI-aEcom)Be al> 0k (g.)).
(38)
Therefore, the update equation for every t timesteps, in other words, the target parameter update equation is the following:
1-1
1
0k+1 =
(ooo)) yoor + (I - aDcoo))
OK + a
Σ (1
accoo)
00.
(39)
i=0
1=0
A.3.4 Derivation of the FQI update equation
0x+1 = arg min
E
[(00(,,))=Q0016 (5' - (
(40)
(s,a)-p
With linear function approximator Q0(s,a) ((ss,))T T.:
(o(ssa) (066,8)00-70(6,61)) 0x - a()
0t+1 arg min
E (s,a)~u
(41)
>' (os-((s,),.a'm (x)
arg min | - pP 10 -R|
(42)
arg min
D D
0 (DD& 20, + D R
(43)
A
There are two common approaches to minimizing Ar b
solving the projection equation and solving the normal equation. As shown in (26) Page 438]. these methods are equivalent for solving this minimization problem. Below, we present the methodology of both approaches.
The projection equation approach
The projection equation is:
Ax PCol(A) (AAi) b,
(44)
where PCol(A) is the orthogonal projector onto Col (A), equal to (AA!). This method involves first computing the orthogonal projection of b onto Col (A), namely (AAt) b, and then finding the coordinates of this projection (i.c., x) in the column space of we use the projection equation approach to solve Equation
we know that the update of 0g is:
0 = {0 E D 1 0 D (DD D8g + D²R)
(45)
= (D P0 + (D: D + (1 (1- (Di (D v RR)
(46)
The minimal norm solution is:
a = >D DDDDDD'DP... P. Tb + D
(47)
= 7 = T DP Φ0 + c DΦ) क DR
(48)
=t + Eon
(49)
22

---

The normal equation approach tosolve the normal equation A Az b directly. Therefore, When using the normal equation approach to solve Equation
The second method for solving this minimization problem is
we know that the update of 0g is:
0 = {0 E R T
D
7 DP, 20 - + D'DRR
(50)
{>( D & T DP, 40 + (Φ D DR+ + (T- (D r (
(51)
+>> P + (D DàR (I- (D. v (VER).
(52)
The minimal norm solution is:
Bk+1 = (o) T D 1 7 T DP,,, 20p + (o T DΦ)² & DR
(53)
720 Us + 2000
(54)
= (D& 'D 00 + (D&t) 'DÀR DÀRR.
(55)
In summary, shown above, without assumptions the chosen features (i.e., on feature matrix +), the update at each iteration is not uniquely determined. From Equation (46) and Equation (52). we know that any vector in the set formed by the sum of the minimum norm solution and any vector from the nullspace of D o can serve valid update. In this paper, choose the minimum norm solution as the update at each iteration. As shown in Equation (49) and Equation (54). this leads to the following FQI update equation:
0x+1 - Ox Boon
(56)
Consequently, we know that when full column rank, the FQI update equation is:
0 E Oz + Deo0 0g.r-
(57)
When & is full row rank in the over wee-parameteriied setting(d d 2 h),, with detailed derivations appearing in Lemma A.19 the update equation becomes:
0k+1 = 7 P, + t R.
(58)
Lemma A.19. When & is full row rank in pver-parameterized setting(d 2 h). the FQI update equation is:
02+1 = - " P00 + + R.
(59)
Proof. In the setting where tb is full row rank, in the over-parameterized setting(d 2 h). we know that [ Di D D and because is full row rank, ΦΦi 1, then
D क D Φ. By Greville 188 Theorem 1], can get that (D&+)) कF DD
Combining this with update equation (Equation (55)) we can rewrite the update equation as:
OK-1 = ( D P.P. v0 + (D. D
(60)
> (D² D 20 + Φ! (Dt)
-1 D
(61)
P 20 + i'R. R.
(62)
B
Unified view: preconditioned iterative method for solving the linear system
B.1
Unified view
One of the key contributions of this work is to show that the three algorithms TD, FQI, and Partial FQI are the same iterative method for solving the same target linear system / fixed point equation (Equation (67)), as they share the same coefficient matrix A = (Eeoo - >E.r) and coefficient vector b = Vo...Their only difference is that they rely on different preconditioners M, a choice which impacts the ensuing algorithm's 's convergence properties. the following will connect to each algorithm's update equation to such perspective.
23

---

TD
0k+1 12+1
1
al (Eco - Foor
0k
al
(63)
We denote the preconditioner M of TD as MTD al and define HTD [I - a (Doon -Err]]
FQI
0k+1 #k+1
E-1
(Ecoc (oorr)
Og
Ogr
(64)
con
26
We denote the preconditioner M of FQI
12 as Mroi Eoo and define HrQI E Eer.
PFQI
t-1
0k+1
I
Econn )' (Ecor FEeor)
Ok
Σ
0g.
(65)
#h++1
M
M
H
We denote the preconditioner M of PFQI as Mrroi a E1=
1-1 ii= (T 2 y and define HyrQu = I
Ei= - Coow) (Eeor Eer
Proposition B. details the transformation of the traditional into this form (Equation (65)).
the PFQI update equation (Equation 39
Preconditioned target linear system (preconditioned fixed point equation): From above we can easily see that the the fixed point equations of TD, PFQI, and FQI are in form of Equation (66). which is a preconditioned linear system, As previously demonstrated, solving this preconditioned linear system is equivalent to solving the original linear system it only multiply nonsingular matrix M on both sides of the original linear system.
M (Eeov - Eer 6*
M fs.
(66)
Target linear system (fixed point equation): Equation 66 presents the original linear system, therefore as well the fixed point equations of TD, PFQI, and FQI. We refer this linear system as the target linear system.
(Eoo - -orr
Ogr
(67)
Non-iterative method to solve fixed point equation (LSTD): From Equation 688 it is evident that if target linear system is consistent, the matrix inversion method used solve is exactly LSTD. therefore, we denote the A matrix and vector of the target linear system as ALSTD = (Dron Eer) and BLSTD = Pg.r. and ÓLSTD as set of solutions of the target linear system, ØLSTD = {0 E Rd (Noon "er) 0 0.
LLTD CEos - /Err 0
(68)
AT
we provide analysis for FQI without this assumption 'here assume (E aEE...' is nonsingular just for clarity of presentation. but doesn't 't lose generality, Emw. is symmetric positive semidefinite, we can easily find a that (aE..w) have no eigenvalue equal I and that case Lemma B.2 show (E!=1( aLico))) nonsingular
Phere we assumed invertibility Ecou, in Scction 3
24

---

Preconditioner transformation From above, we can see that TD, FQI, and PFQI differ only in their choice of preconditioners. while other components in their update equations remain the same-ther all use ALSTD as their A matrix and LLSTD as their b matrix. Looking at the preconditioner matrix (M) of each algorithm, it is evident that these preconditioners are strongly interconnected, as demonstrated in Equation (69) When i 1, the preconditioner of TT equals that of PFQI. However, PFQI converges to the preconditioner
as increases, the preconditioner clearly see that increasing the number of updates toward the target value function (denoted by -)-a technique known as target network -eseesttlaally transforms the algorithm from using a constant preconditioner to using the inverse of the covariance matrix preconditioner, in the context of linear function approximation.
FQI. Therefore, we can
al
1-000
(69)
TD
FQJ
PFQI
B.2 FQI without assuming invertible covariance matrix
We peviously showed that FQI is a iterative method utilizing Dowe as preconditioner to solve the target linear system, but which require + have full column rank. We now study the without assuming is full column rank. From Equation
20 we know general form FQI update equation is:
x 7 Oe 1oo0
Interestingly, which can be seen as
OK+1
{1-
Eeor)
Oc + Et Foso
Z6+1
which is vanilla iterative method solve the linear system:
(1 - -1-22 Mor)
0 Dor
(70)
We call this linear Equaai,Equation 70), the FQI linear system, and denote the solution set of this linear system, Ofor, with matrix: AFQI = (1 1 (2o0 Derr) and bFOI = Do. If we multiply
Eeou on both side of linear system, we get new linear system and this new linear system is our target linear system, and show in Equation (TT) (Detailed calculations in Proposition B.4):
Ecow (I (oo 0 Eeov + (Eeor >Err) 0
(71)
Therefore, we know the target linear system is the projected FQI linear system Naturally, we have the Proposition [.1] which shows that any solution of FQI linear system must also be solution of target linear system and what is necessary and sufficient condition that solution set of FQI linear system exactly equal to solution set of target linear system, and from which we prove that when chosen features are linearly independent( & is full column rank), the solution set of FQI linear system exactly equal solution of target linear system.
B.3 PFQI
Proposition B.1. PFQI update can be expressed as:
OR+1
1- a [1 aCew)
(Ecov - yEer)
Os +
Σ
a
E
(72)
1=0
1=0
Proof. As Eron is symmetric positive semidefinite matrix, it can be diagonalized into:
Moor = Q-1
0
0
Q
0
K
25

---

where Kyxr is full rank diagonal matrix whose diagonal entries are all positive numbers, and r Rank (Ero)), and Q the matrix of eigenvectors. It straightforward to choose a scalar a such that (T aarxx nonsingular, so we will assume (T xxrr as nonsingular matrix for rest of proof. For notational simplicity, we will henceforth denote Krxr as K.
From above, we can derive that
Σ 11 - Q (at) 0
0
(I-(1-ak)))
1=0
By Lemma B.2 we know that Ei=o a is invertible, subsequently its inverse is:
Σ (1-
t-1
aLcov)
-1
= =Q
at ((I-(I-ak))) 1
0
a
0
Therefore, the PFQI update can be rewritten as:
0x+1
07
Σ (1 aliooo) Der (1 aZio))) On + a Σ alico))
0s.
(73)
t-1
)
Σ 11 aCooo)
N2 +
E (11-aSioo))) (
(1 --aooooo'
2x.
(74)
1=
a 3ooo)'00.
(75)
all
0
(I- 10
Q-1 0
(76)
(I
11 0
K - (1- K(-(1-ok))-u-ax" |0) Ox
Porr + Q-1
(77)
0
t
Σ
[I aCco))'
(78)
1=0
atl
Q 8- Q-
+ o
Q-1
0 (79)
0
(I - (I- (I-Ka))KK-
(
Q - (Zerr }
4-1
Q
}.00 .0 + a Σ
- acom))0s
(80)
0 K
1=0
[-1
1-1
-1
a
a ccor)"
a
D
- (Ecor - -oor Ok
(81)
==
1-1
+ t
Σ
Lcou) 10sr
(82)
-=
1-1
1-1
Σ
[I
a a
(Ecor (ier)
Ox + a
Σ (T
Oar
(83)
1=0
M
M
Lemma B.2. Given any symmetric positive semidefinite matrix A and scalar 0, (I aA) invertible and Aa have no eigenvalue equal to 2, then Ei= (I aA) invertible for any positive integer t.
26

---

Proof. Given any symmetric positive semidefinite matrix A and (I - a.)) is invertible, it can be diagonalized into the form:
A= A=
:
0
Krxr
where K' is positive definite diagonal matrix with no eigenvalue equal to 2, and Rank (4), so
Σ
(1 - a.) - Q [
tl 0
-1- -1-(1- (KK))_k)))K-) ]0
0
and by Lemma B.3 we know that (1 - (I - -ak)") is invertible, then elearly
tl (I- (I - (I))
full rank, therefore, Ei (1 aA)" is invertible.
Lemma B.3. Given any positive definite diagonal matrix K and scalar ar O and nonnegative integer t, if (a) K have no eigenvalue equal to 2, - (I-aK)) is invertible.
Proof. Since is positive definite, it has no eigenvalue equal to 0, By Lemma A.1 follows that (I-aK) -KK) has no eigenvalue equal to I, Consequently, (I aK) have no eigenvalue equal to 1. Applying Lemma A.1 once more, we can see that (I [ (I-K) has no eigenvalue equal to therefore, it is full rank and hence invertible.
Proposition B.4. FQI using the minimal norm solution as the update is a vanilla iterative method solving the linear system:
(I- cou Eer) = 0s. and whose projected linear system(multiplying both sides of this equation by Yooo) is target linear gystem:(Ecom
EEer) 8 p..
Proof. When FQI use the minimal norm solution as the update, based on the minimal norm solution in Equation 49 and Equation (54), we knwo that the FQI update is:
a
> Ez + 0g.
(84)
We can rewrite this update
Ox+1
(I (1- Eior
On + Elor
(85)
and thus interpret Equation 84 as vanilla iterative method solve the linear system:
(1 (- Der
coo O Ogr
(86)
Left multiplying both sides of this equation by Enon yields linear system, the projected FQI linear system:
Ecov 7I- Eer = Ecor Et 9
By Lemma
B.5
know that
Col ($ T) -Col (Eco)) ( 2 Col (Eer)
and
( DR) E Col (Φ = Col (Ecov)
so Ecor It Di Eor Egr and Ecor Et 2sr 00rr. Therefore, this linear system be rewritten as:
EEcov F 0 6
which is target linear system.
27

---

Lemma B.5.
Col (Ø D@) Col ( 2 Col ( DP x ④)
(87)
Col (Φ) D4) = Col (+ 2 Col ( D(T )))
(88)
Ker (4 DΦ) Ker (+) C Ker (+ (D'PP, D
(89)
Ker (4 DΦ) Ker (+) C Ker (4 D p)))
(90)
Proof. By Lemma B.6 we know that
Col ( D DD) Col (eDDs
Since D is full rank and Col (ΦT) 2 Col ( T DP naturally holds, we get:
Col ④ T D = Col (4 ) 2 Col (4 D)
Next, by Lemma B.6, we know that Rank (+ DT) Rank ( D = Rank (f), which means
dim (Ker (o ( (Φ)) dim (Ker (+))
Additionally, we know that Ker T DDp) 2 Ker (+) and Ker (Φ) C Ker (Ø DD,, x)) naturally hold, therefore we can conclude that:
Ker ( DT) = Ker (Φ) C Ker DDPP,,))
Since Col (Ø T D 2 Col (o T DP, 3) and Ker (Ø DΦ) C Ker (Φ ToTDe DP,, D)) naturally,
Col (+) 2 Col ( D(I p)) and Ker (Φ D&) S Ker (+ D(T - -P=))
Lemma B.6. Given any matrix x
Col Col(AA)) Col (A)
Proof. Since Col Col(AT) (AT) Row (A) 1 Ker (A) and Rank (A) Rank (AT), by Lemma B.7 know that Rank (AA) Rank (AT) Rank (A), and Col (AAT) S Col (A) naturally holds. Hence,
Col (AAT) Col (A)
Lemma B.7. Given any two matrices A E Raxx andB E RRxx,, Assuming Rank (A) 2 Rank (B), then
Rank (AB) Rank (B)
if and only Ker (A) n Col (B) (0).
Proof. By 26
Page 210], we know that
Rank (AB) Rank (B) -iim (Ker (4) n Col (B))
Therefore, if and only if Ker (A) (Bl((B {0}, Rank (AB) Rank (B)
28

---

B.4 Proof of Proposition 3.1
Proposition B.8 (Restatement of Proposition 3.1
LLSTD 2 +rrr.
if and only if Rank (Eeov - -) - Rank (1 - 2ovr Eer), OLSTD O
when Neoe is full rank(or d is full column rank), OLSTD OF!!
Proof. As we show in 3 the target linear system is projected FQI linear system (multiplying both sides of FQI linear system by Ecor), every solution of FQI linear system must also be solution of target linear system, which means:
LTTD 2 OQQ
By Lemma C.10 we know that OLSTD = Orgi if and only if
Rank (Neve >Drr) = Rank (1 -- 2oo Cor)
Therefore, when Lcov is full rank, we know that
Rank (Eeor - -Drr = Rank (Eeor (T - -to Eer)) = Rank (T - -ISttt Der)
hence OLSTD = OFQI-
C
Singularity and consistency of the linear system
C.1 Rank invariance and linearly independent features are distinet conditions
The commonly assumed condition for algorithms like TD and FQI - that the features are linearly
independent, meaning has full column rank (Condition 4.3) does not necessarily imply rank
invariance (Condition 4.1. which, by Lemma C.I is equivalent to:
Ker (Φ) n Col -P0I--PP>70
{0}
(91)
Conversely, rank invariance (Condition 4.1b does not imply & has full column rank. The intuition behind this distinction lics in the fact that Ker (4²) n Row ( = {0} naturally holds, leading Col (+) does not necessarily hold, regardless of whether has full column rank. Consequently, there is no guarantee that Ker ( ") n Col (D - >P {b) = {O} will hold, irrespective of the rank of 4b Thus, linearly independent features (Condition 4.3) and rank invariance (Condition 4.1) are distinct conditions. with neither necessarily implying the other. Since rank invariance (Condition 4.1 is necessary and sufficient condition for the target linear system to be universally consistent (Proposition 4.2). the existence of solution to the target linear system system cannot be guaranteed solely from the assumption of linearly independent features (Condition 4.3). Consequently, these iterative algorithms such as TD, FQI, and PFQI that are designed to solve the target linear system does not necessarily have fixed point just under the assumption of linearly independent features.
to Ker (Φ n Col (+) = {0}. However, the relationship Col (D( -P=-)
Lemma C.1. These following conditions are equivalent to rank invariance (Condition
Rank (Ecov) Rank (Ercov F
(92)
Col (Ecov) Col (Ecor - -Eerrr
(93)
Ker (Eeav) = Ker (Eon - )..rrr
(94)
Col (ΦT) Col (Zeov 7/ 22orr
(95)
Ker (Ø) = Ker (Zioor - 72200r
(96)
Rank (Ø) = Rank (Eron - -7E
(97)
Ker (Φ
n Col (D(I - -Pp= ) = {0}
(98)
Ker ④ D n Col (P= )Φ) {0)
- ,P,
(99)
Ker ( D(I PP)) n (o) (0)
(100)
29

---

Proof. From Lemma
B.5
we know that
Col ( DΦ) Col (ΦT) 2 Col 1 T D(I - pP
and
Ker ( D$) = Ker ($) C Ker (Φ T D(I ))))
Therefore,
Rank (Ø) Rank (& DDI 7P )())
if and only if the following hold
Col ( DØ) = Col (TT) = Col TDD - -PP,){))
and
Ker ( D Ker (Φ) Ker ( D -P,)
Hence, Equations
93 to 97 are equivalent. Subsequently, together with
Rank (4 Dd) Rank (Φ)
we can obtain that Equation 92 is equivalent to Equation 977.
Next, since D(1 ->P*) is nonsingular matrix,
Rank (+ ) Rank (D(T - -P)))))
and
Rank (D+$) = Rank (D+ - ,P,x
and
Rank ( D(I PP)) = Rank (Φ)
Consequently, by Lemma B.7 we know that Rank ($) Rank (Φ DDI ()) and only if
Ker (TT) n (D(I - )PP)) = (0}
or
Ker ④ D n Col (D
- -P= + (0)
or
Ker (& DDDD(I-PP11) n Col (0) = (0)
So Equations
97 to 100
are equivalent. Hence the proof is complete.
C.2 Rank Invariance is a mild condition and should widely exist
can that the condition of > Eer having eigenvalue equal to is equivalent to rank invariance (Condition 4.1h holding. Even if Eer has an eigenvalue equal to 1, by slightly changing the value of 7, we can ensure that E
From Lemma C.2
cou Eer no longer has as an eigenvalue. In such a case, rank invariance (Condition 4.1 will hold. Therefore, we can conclude that rank invariance (Condition 4.1 can be easily achieved and should widely exist.
Lemma C.2. (r Eer) have no eigenvalue equal to I if and only if rank invariance (Condition 4.1 holds.
Proof. Assuming rank invariance (Condition does not holds, by Lemma C.1
we know that
Ker (Eeov >Eer) o Ker (Ecor)
then together with Lemma B.5 we know
Ker (Eeov - -Errr 3 Ker (Scov)
Ker (Fear - Exerrr n Row (Eeov) * (0) Moreover, since Ecov is symmetric matrix, we know that
Ker (Eeor >orr) n. Col (Ecov) # {0}.
30

---

Therefore, for a nonzero vector v' E Ker (Eeoo - -rrrr) n Col (Ecor), we have:
(Ecov -
which is equal to VooeU V, By multiplying Lovor both sides of equation we can get:
> Lor D Ceo
(101)
Since (Stov Ecov) is orthogonal projector onto Col (ftw and by Lemma C.3 we know
Col (2tww) Col (>
Additionally, Meo is symmetric, so Col (2 Col (Neov), then since Col (Neov) we can obtain that Loo v, therefore, we have:
7 Eor
which means is eigenvector of (y con Der) and whose corresponding eigenvalue is 1. We can conclude that when rank invariance (Condition 4.1 does not hold, matrix (y Der) must have eigenvalue equal to 1.
Next, assuming (oo has eigenvalue equal to 1, then there exist nonzero vector that
22 Zer
and
E Col (2+t
By Lemma C.3 we know Col (Stow) = Col (I and Ecmo is symmetric so
e Col (Eto.) Col (Ecov)
Furthermore, by Lemma B.5 we know that Col DTD) Col (TT) 2 Col (o DP D). which
implies Col (Ecov) 2 Col (Eer). Therefore multiplying by Ecor on both sides of y oo = U. get
? Neov It Eor = 2oo0
which is equal to
(Ecor Eorr v=
Thus, E Ker (Eroe D.r), implying that
Col (Eeor) n Ker (Ecoo - (errr) +
Since Col (Eeov) = Row (Ecor). we conclude that
Ker (Ecov) + Ker (Eoon -EErr
By Lemma this shows that rank invariance (Condition does not hold. Hence the proof is complete.
Lemma C.3. Given matrix A E Raxm, Col (AT) Col (Al)
Proof. Since AAt is orthogonal projector onto Col (A) and AtA is orthogonal projector onto Col (At), by Meyer (26) Page 386, 5.9.11], we know that
Col (AAt) Col (A) and Col (AtA) = Col CAl(
therefore, we have:
Col (AT) Col (AT)) Col (((AT)))TA) A) = Col (A' A) = Col (Ai)
(102)
31

---

C.3
Consistency of the target linear system
C.3.1 Proof of Proposition 4.2
Proposition C.4 (Restatement of Proposition 1.2)
The target linear system:
( D(I -P = DR
consistent for any Rh if and only if
Rank (Ecov) Rank (Ecor - >
Proof. For any R E R2,, the target linear system:
( (DI(II
D(I - DR
consistent if and only if for any R E IR"
( (R) E Col ( ( D(1-~P,),)
which is equivalent to From Lemma
Col (4 TD) Col ( D(1 -P >p)))
B.5 we know that
Col (4 D) Col ( 2 Col (Φ D(I >P;)
Therefore, Col ( D) S Col (i D(T )) holds if and only if
Col ( DD Col ( D(1 - >P
Since Col DD) Col ( )) by Lemma C. we know that
Col 1 D) Col (& DD PP))
holds if and only if Rank (Eom) = Rank (Eron - yEer).
Hence, the target linear system
P DR
is consistent for any R E R if and only if Rank (Eowv) Rank (Eoov (Err.
C.4 Nonsingularity the target linear system
C.4.1 Proof of Proposition 4.5
Proposition C.5 (Restatement of Proposition 4.5g (Eeov >Eer) is nonsingular if and only if Φ is full column rank and Rank (Ero)) = Rank (Eoov -EE
Proof. If 1f T D(I ,,,)) is full rank, by Fact C.6 clear that & must be full column rank.
Next, assuming & is full column rank, we know that Rank (4 (QTDO D - PP(4-7P-. ))) is full rank if and only if
Rank (x TDT -p= Rank (+)
Also, by Lemma B.5 we know that
Rank (Noov) Rank (4). Therefore, Rank ( D(I->Pa)00 is full rank if and only if Rank (Ecov) Rank (Ecov >Eer).
and O is full column rank.
Fact C.6. Let A be K x L matrix and B an L x A matrix. Then, rank(AB) < min(rank( (A), rank(B)).
32

---

is C.5 Nonsingularity of the FQI linear system
Proposition C.7 (Restatement of Proposition 4.6). -- Der nonsingular if and only if rank
invariance (Condition 4.7 holds
Proof. By Lemma C.2
we know that rank invariance (Condition 4.1 holds if and only y
con Der
has no eigenvalue equal to Consequently, by Lemma A.1 this equivalent - 7 Per having no eigenvalue equal to O, which in turn it is equivalent to Lov Eer being nonsingular.
C.6 On-policy setting
C.6.1 Proof of Proposition 4.7
Proposition C.8 (Restatement of Proposition 4.7
In the on-policy setting,
Rank (Eeme) Rank (Eom - -Exr))
Proof. In the on- on-policy setting, from Tsitsiklis and Van Roy 440 we know that D(I -?P,) positive definite matrix, then by Lemma A we know that
Ker D'I PP Ker (4).
Therefore, by Lemma C.I we know that
Rank (Zcov) Rank (Zoov 720or)
C.7 Linear realizability
C.7.1 Proof of Proposition 4.9
Proposition C.9 (Restatement of Proposition 4.9..
When linear realizability holds (Assumption 4.8).
θLSTD 2 + always holds
OLSTD O₂ holds if and only if rank invariance (Condition 4.1 holds.
Proof. Since OLSID is the solution set of the target linear system:
( D PP) 20 & DR
and + is equal to the solution set of linear system:
(P->Pa) = R,
we know that
1LSTT 2 θ
Then, by Lemma C.10 we know that 1LSTD O holds if and only if
Rank (+ D(I 7.,) )) Rank ((I - p)
and since (I 7P,) is full rank matrix and Rank (Φ DΦ) Rank (Ø), from Lemma B.5 know that
Rank ((1 - -(=)),)))) = Rank (Φ).
Therefore, we know that OLSTD O holds if and only if
Rank ( DDI D(1 7P.) = Rank (4 DΦ).
which is Rank (Eeov) Rank (Eovv ).rr).
33

---

Lemma C.10. Given two matrices A E R=xm and B E IRX*" and a vector b E Col (A), we denote the Sa the solution set for linear system: Ar and SBA the solution set for linear system: BAx Bb. the following holds:
SA 2 SBA only holds when SA = -BBA
(103)
and
SA = SBA SBA if and only if Rank (BA) Rank (A).
(104)
Proof. is clear that any x satisfying Ar also satisfies BAx Bb, SA C SBA. Therefore, if SA 2 SBA, SA = SBA.
Next, E Col (A) we know that
SΛ = (A'b (1- A A' Vu }}""),
where ( Vu Rm) Ker (A) and (Atb) & Ker (A). Also,
SBA {BB) Bb + (BA)) BA) Vw E R=')),
where (T--BA) (B)) Ve E RE) Ker (BA) and ((BA) Bb) & Ker (BA). Additionally, Ker (A) S Ker (BA).
First, we will prove that if SA = SBA, then Rank (A) Rank (BA).
Since (Alb) & Ker (A) and ((BA) Bb) & Ker (BA), from above we know SA SBA. dim (Ker (A)) dim (Ker (BA)),
which is equivalent to Ker (A) = Ker (BA) since Ker (A) Ker (BA). From that we can get that Rank (A) Rank (BA) by the Rank-Nullity Theorem.
Now we need to prove that if Rank (A) = Rank (BA), then SA SBA. We know that Ker (A) S Ker (BA),
so when Rank (A) Rank (BA), Ker (A) Ker (BA) and
{(I Al A)E | Ve E RT) {(T - (BA) BA)W Vu R.))
Also, we have that:
Alb - (BA)+ Bb = (Ai (BA)
(105)
=11 - (BA)) BA) Alb
(106)
E {(I (BA)* BAJW Vwu E ET') Ker (BA) Ker (A).
(107)
Therefore,
Atb E ((BA)* Bb + (1 (BA) (BA)]BA) Vi E R?)),
and
((BA) Bb) E {AAi - (1- - A A'Ale ("ER")
which is equal to Then, know that
((BA)BI) E (Atb+ (T At ATA)e V V
{(BA) B6 + (I (BA)tBA)e Vw E RT)} = [Ato b + (1 - AtA)u Vo E }]
Hence we can conclude that Rank (A) = Rank (BA), SBA = SA.
Fact C.11. If X = AX, + B, then if update starts from Xo. we have:
X
ABB + A 44 Xo
34

---

D The convergence of FQI
D.1 Interpretation of convergence condition and fixed point for FQI
First, Theorem 5.1
provides general necessary and sufficient condition for the convergence of FQI without imposing any additional assumptions, such as being full rank. Later, we will demonstrate how the convergence conditions vary under different assumptions.
Theorem D.1 (Restatement of Theorem 5.1. FQI converges for any initial point 8g if and only if (Et (E Bp.r) E Col (I ". Eer) and (7 Ler) ) is semiconvergent. converges to
(1- Peor) Oor + (T- -To For) (T - (oo 0o] 1ISTD-
As previously defined in Section 3 have bFQr Enon Opr AFQI Eoon and HFQI Per. From Theorem 5.1 can see that the necessary and sufficient condition for FQI convergence consists of two conditions:
y Der.
(brou) E
and Hroi being semiconvergent.
First, (bFQr) E Col (Aroi) ensures that the FQI linear system is consistent, which means that a fixed point for FQI exists. Second, HFQI being semiconvergent implies that HFQI converges Ker (Arq)), and acts as identity matrix Ker (Arqi) if Ker (Arqi) * {0}. Since any vector be decomposed into two components one from Ker (Arqi) and one from Ker (Arqı) the above condition ensures that iterations converge to fixed point for the component in Ker (AFqi), while maintaining stability for the component in Ker (AFor) without amplification. This stability is crucial because HFQ I Argr, and if Ker (Aroi) {0], then HFo necessarily has eigenvalue equal to I, whose associated component can easily diverge within Ker (ArQi)- Consequently, preventing amplification of HFQI in Ker (Aroi) during iterations essential.
The fixed point to which FQI converges consists of two components:
(Aroi) broi and (T Aroi (Arqi) 9o-
(108)
The term (T- (ArQi) (Arai) Go represents any vector from
Ker (Arqi)
because (Aroi) (Arqi) is a projector onto
Col ((Aroi))) along Ker ((Arai)*)
while (T (Arri) (Aroi)) the complementary projector onto
Ker ((Arqi))) along (Arq))
where k Index (Arqi). Consequently,
Col - (Aror) (Aroi) = Ker ((Aroi)*)
Since Hroi is semiconvergent, Index HFQi) I 1 and Arqı = I - HFQI, we know that Col (I (I- (Arqi) (Apci)P) Ker (Aroi)
Therefore, (I- (Arqi) (Arqi) P) 8g can be any vector in Ker (Arqr). Additionally, for the term (Aroi) broi in Equation (188). since Index (Arqi) < 1, it follows that
(AFQI) bpot (AFOi)** * bfot-
35

---

In summary, we conclude that any fixed point to which FQI converges is the sum of the group inverse solution of the FQI linear system, denoted by (Aror)* # bFQu, and vector from the null space of ArQu, i.e., Ker (Aroi). Additionally, since Aror = ALSTD and Ecobbru = BLSTD (Section 3) and the FQI linear system is consistent, i.e., (FFO1) E Col (Apo1). it follows that ( (AFQi)* # bFoI is also solution to target linear system Moreover, as Ker (Aroi) S Ker (ALSID), the sum of (Arqi)* * broi and any vector from Ker (ArQi) is also solution to target linear system. In other words, any fixed point to which FQI converges is also a solution to the target linear system. This conclusion aligns with the results presented in Section 3 where it is shown that target linear system represents the projected version of the FQI linear system.
D.2 Proof of Theorem 5.1
Theorem D.2 (Restatement of Theorem 5.Ip. FQI converges for any initial point 8, if and only if (Etoo0.r) E Col (I Lo and (1 Eer) is semiconvergent.
It converges to [1r -1- 7D Ear) Dood (1- Eerr (I ------ co )) oo)
Proof. From Section system
3 we know that FQI is fundamentally a iterative method to solve the FQI linear
(I (I- Eer 1/m
Therefore, without assuming singularity of the linear system, by Berman and Plemmons [5] Pages 198, lemma 6.13 we know that this iterative method converges if and only if the FQI linear system is consistent:
(Dom (p.r) Col (I - -tm
and 7x For is semiconvergent. It converges to
) Oor [[( - Eero D
+ (1- (1- Eer) -1-
7 Ece) 0o)
E OLSTDD
D.3 Linearly independent features
Proposition D.3 examines how linearly independent features affect the convergence of FQL. As shown in Section when is full rank (linearly independent features (Condition (.33l the FQI linear system that FQI solves is exactly equal to the target linear system. Consequently, the consistency condition changes from (brot) E Col (Aroi) to BLSTD E Col (ALSTD). and the covariance matrix Ecow becomes invertible. FQI can then be viewed as an iterative method using E preconditioner to solve target linear system, with MrQi = Ezi. and HFQI = MFQIALSTD. Beyond these adjustments, the convergence conditions for FQI remain largely unchanged compared to the general convergence conditions for FQI (Theorem [5. T). which does not make the linearly independent features assumption. Thus, conclude that the linearly independent features assumption does not play crucial role in FQI's convergence but instead determines the specific linear system that FQI is iteratively solving.
Proposition D.3. Given & is full column rank Condition 4.3 holds), FQI converges for any initial point Og if and only if
0sr Col (Ecor 7Err
and Ferr is semiconvergent. converges to
(1 -1- I=10or (I- (1- Eor) 0o] OLSTD.
MBrief proof: ALsmo (Arq))* begi Apgi(AAg) brgg Dea bLSTD- 1We note that the first printing of this text contained an error in this theorem, by which the contribution of the initial point, Fo. was expressed as (1 - H] - -H) za rather than / (1 - H H)(1 H) D xq. This was corrected by the fourth printing.
36

---

Proof. From Section 3 we know that when d is full column rank (Eeov is full rank), FQI is exactly iterative method to solve target linear system and the FQI linear system equivalent to the target linear system. Therefore, the consistency condition of FQI linear system:
(or)) E Col (I - )
equivalent to the consistency condition of target linear system:
20r E Col (Zeor - 7Lor)),
and we have Eton coe. Then, from Theorem 5.1 we know that in such setting, FQI converges for any initial point 0g if and only if
0 E Col (Ecov (Drr and (z are semiconvergent,
and it converges to
(1 (1-72 -D Dood (1 (1- -I- -I-72 -D Eor) (I -- 0o] @ISTD-
D.4 Rank Invariance
D.4.1 Proof of Lemma 5.2
Lemma D.4 (Restatement of Lemma 5.2 If rank invariance (Condition 4.1 holds, Econ and Eer are a proper splitting of (Ecor - 7Ear).
Proof. When Rank (Ecov) Rank (Ecor Der), by Lemma C.1 we know that
Col (Ecov) Col (Ecor - -Err and Ker (Ecov) Ker (Eeor -Eer)
Then, by definition of a proper splitting (in Appendix A.I. I. Eron and Eer a proper splitting of (Eoo 7Drr
D.4.2 Proof of Corollary 5.3
Corollary D.5 (Restatement of Corollary 5.3
Assuming that rank invariance (Condition 4.1 holds,
FQI converges for any initial point 0g if and only
p p
cop Eer) <1
converges to (I Eer)
Et 2 OLTTD
Proof. From Lemma 5.2 we know when rank invariance (Condition 4.1) holds, Ecow and Eer is proper splitting of (Ecov -Err). By the property proper splitting 14 Theorem 1], know that (I 7 Eor) nonsingular matrix. Then by Lemma A.I we know that 7. Eor has no eigenvalue equal to therefore, > Eer semiconvergent and only if p (rΣt Eerr < 1.
Morever, since FQI linear system nonsingular, 0p.r) Col - -t naturally holds. Additionally,
(I-
cov Eer
Dt
cov Eer)
Hence, by Theorem 5.1 we know that in such setting, FQI converges for any initial point Og if and only if
p P 1.
It converges to [[1 Mn ) - -t 0orl ] E OLSTD.
37

---

D.5
Nonsingular target linear system
Corollary D.6. Assuming Argr is full rank, FQI converges for any initial point t if and only if
p (eor))
converges to
(Ecor - -Eer) 0d.r
OLSTD
Proof. By Proposition 4.6 we know that AFQi is full rank if and only if rank invariance (Condition 4.J holds, therefore, is clear that share the same convergence result with Corollary [.3
E The convergence of TD
Definition F.1. TD is stable if there exists step size > such that for any initial parameter lo IRd, when taking updates according the TD update equation (Equation the sequence (0x ) k= converges, i.e., lim 0₂ exists.
E.1
Interpretation of convergence condition and fixed point for TD
Theorem E.2 (Restatement of Theorem 6.1.. TD converges for any initial point Gg and only if
BISTD E Col (Arsm)) and Hm is semiconvergent. It converges to
(ALSTD) BLSTD +(T (ALSTO) 0o] E OLSTD
(109)
As presented in Section 3 TD an iterative method that uses positive constant as a preconditioner solve the target linear system. Its convergence depends solely the consistency of the target linear system and the properties of HID- In Theorem [.1] we establish the necessary and sufficient condition for TD convergence. Using the notation defined in Section 3 where bTSTDD 0g.r.
ALSTD (Eoor - -eEr),, and HTD (I- AIST)) we know that the necessary and sufficient conditions composed of two conditions:
BLSTD Col (ALSTt) and HTD (1 aALSTD) is semiconvergent.
First, BLSID& E Col (ALSTD) is the necessary and sufficient condition for target linear system being consistent, meaning that a fixed point of TD exists. Second, HID being semiconvergent implies that HyD is convergent Ker (ALSTD) and acts the identity Ker (ALSTD) if Ker (ALSTD) * (0).
This means that the iterations converge fixed point Ker (ALSTD) while remaining stable on Ker (AISTD) without amplification. Since HTD = ALSTTD if Ker (ALSTD) + {0), then HTD will necessarily have eigenvalue equal to 1, and we want prevent amplification of this part through iterations. From Theorem 6. has two components:
we can also see that fixed point which TD converges
(ALSTD)
(eTT))PLsm PLSTTD and (I (1- (ALSTD) (ALSTD)P) Co.
The term (T (T-(ALSTD) (ALSTD))) Og represents any vector from Ker (ALSTD), because
((ALSTD) (ALSTD)" is projector onto Col (AALSTD)*) along Ker (AALSTD)*)
while ( (A((As)))ALISTT)) is the complementary projector onto
Ker ((ALST))* along Col ((ALSTD)*).
where k Index (ALSTD). Consequently, we know
Col (1 (ALSID) (ALSTD) Ker ((ALSTD)*).
38

---

Since HID ALSTD is semiconvergent, we know
Index (ALSTD) S 1,
giving us
Col (1 (1- (ALST)) (AISTD))) - Ker (ALST)).
Therefore, (I - (ALSTD) (ALSTD)") 0o can be any vector in Ker (ALSTD). Additionally, because
Index (ALSTD) I 1, we have
(ALStD) BLSTD = (ALSTD) * BLSTD.
In summary, we conclude that any fixed point which TD converges the sum of the group inverse solution of the target linear system, denoted by (ALSTD) BLSTD, and a vector from the null space of ALSTD, i.e., Ker (ALSTD).
E.2 Proof of Theorem 6.1
Theorem E.3 (Restatement of Theorem 6.1 target linear sytem consistent:
TD converges for any initial point Og if and only if the
2 Col (Ecor 7Derr
and semiconvergent:
p(T - a (Ecoo - -gDer)) <1
or else
p(1 (Eoon - -FDor) =1
where VA E a a (Zcov - () 1) semisimple.
is the only eigenvalue on the unit circle, and X is
converges to (Eeor EErr 0o.r + (Eeov (Ecor DD Bo]
OLSTD-
Proof. As show in Section 3 TD is fundamentally iterative method to solve its target linear system:
(Ecov >Eer) 0 0
When the target linear system is not consistent, this means there is no solution, and naturally TD will not converge. fgr E Col (Noo- - >Eer) is necessary and sufficient condition for the existence of solution to the linear system (Zcov >2ir)) ) 0 fg.r. making a necessary condition for TD convergence.
From Berman and Plemmons chapter 7, lemma 6.13] Hensel 20 know the general necessary and sufficient conditions of convergence of an iterative method for a consistent linear system. We know that given consistent target linear system, TD converges for any initial point 0g if and only (T - a (Eeov 7 EExr )) is semiconvergent.
Therefore, know TD converges for any initial point 0g if and only if (1) the target linear system is consistent:
0+r Col (2cor 720rr)
and (2)
P( - a (Ecov - - 1
or else
p(1 - a (Eeav - -Err) =1
where vA E (I- a (Ecor - E.r)) )), 1, the only eigenvalue on the unit circle, and = semisimple. and when it converges, it will converges to
+ D0.r P0. (Ecov >or)
-Eeov (Eer) () 80] OLSID-
39

---

E.3
Proof of Corollary 6.2
Corollary E.4 (Restatement of Corollary 6.2
TD is stable and only if the following conditions
hold:
Og. E Col (Econ - ?Ler))
(Zeov - (Dier) is positive semi-stable.
Index (Eeon 7rrr 1
Additionally, if (Ecov D is M-matrix, positive semi-stable condition can be relaxed to:
(Ecov -eer) nonnegative stable.
Proof. First, from Lemma E.5 we know that when (Ecov -eer) is full rank, there exists a that
(I a (Ecov - -Er)) semiconvergent
and only if (Econ )Eer)) positive stable
Second, from Lemma E.6 we know that when (Ecoe - -orr) ) is not full rank, there exists a >> 0 that a (Zeov - >Derr) )) is semiconvergent and only if (Ecor - --errr is positive semi-stable and the eigenvalue A(oov--yi = 0 a (Noov - ->2ior) is semisimple. Moreover, from Lemma E.24 we know "the eigenvalue X - (err)) = E o (Eoo >Err is semisimple" is equivalent to Index (Eeov- - --
Combining two above cases where Ecor Mer is full rank and not full rank, we conclude that there exists a > such that (7 a (Erov - Eerr semiconvergent if and only if (Eeov _ is positive semi-stable and Index (Ecor >Ear) 1.
Finally, by Theorem 6.1 know that there exists > 0 such that TD converges for any initial point Oo if and only if
0.r Col (Eeor Eerr
and and
(Dro FDor is positive semi-stable
Index (Ecow - (Ferr S
Additionally, When (Eeon - Eer) is singular M-matrix, by Berman and Plemmons (5] Chapter Page 150, E11,F12), we know that if (Eeov - -Eer) is positive semi-stable, it must be nonnegative stable. Hence, the proof complete.
Lemma E.5. Given square full rank matrix A and positive scalar a, (I -I-aa aA) is semiconvergent if and only if A is positive stable and a E (0,c) where minxea(A) |A
2-R(X)
Proof. Since A is full rank it has no eigenvalue that it is impossible that (I - aA) have eigenvalue equal to for any eligible a.
0 a (A), therefore, by Lemma A. we know
By Proposition A.8 we know that (I aA) is semiconvergent if and only if
p(T aA) < 1.
Additionally, because
(T (1)
and A(a) E a (A), by Lemma E.7 know that
< ()y--a)) E Eo aA) aA),
if and only if
(A), V)(a) E (A), (Acai) >
and a E (0,c) where & (A)
2.((2)) x
40

---

Hence, We can conclude that (I a.A) is semiconvergent if and only if A is positive stable and (0, E), where
2 (A)
min AEA(A) |A/2
Lemma E.6. Given a square, rank deficient matrix A and positive sealar a, (I- aA) semicon- vergent if and only if
is positive semi-stable
the eigenvalue (()) a (A) semisimple or Index (A)
a E (0, c), where c (a)
2-R(A)
[A]2
Proof. Since A is not full rank it must have eigenvalue A(A) - 0 E (A). Then, by Proposition A.8 we know that (7 - a:A) is semiconvergent if and only
p(T aA) =1
where A(r-aA) = 1 is the only eigenvalue on the unit circle, and ((T-aA) = is semisimple.
Next, by Lemma E.7 we know that
VyI-aA) (o
<1
if and only if and a E (0,e) where e mi) 727
(((a) E (A) (A(a)) >
2.R(A))
Thus, Vλ(A) E a (A) V(O).
2 2-R(A)
(A(a)) and (0, where
min \co(A)\())
are necessary and sufficient condition for p aA) where A(r-aA) is the only eigenvalue on the unit circle.
Then by Lemma A.1 we know A(r-aA) is semisimple if and only if ((a 0 is semisimple.
Therefore, we can conclude that (A) is semiconvergent if and only if A is positive semi-stable and its eigenvalue A(A)= = 0 (A) is semisimple and E (0, where min (A)))))
R(A(a))
|A(a)
From Lemma H.24 we know that the eigenvalue
(A) E (A) being semisimple
is equivalent to Index (A) 1. Hence, the poof is complete.
Lemma E.7. Given a positive scalar and matrix A Raxx,
Vλu-aa) ( a.A)
<1
and only ((A) Ea (A) ((O).
22 (2. (2BR((AA)) |A(a))2
R (A(A)) > and a E (0, where ==
min A())o(AA\\10
Proof. Assume that there exists an a > such that VλІT-aA) (I a.) ((1),
< 1.
This means that for every nonzero eigenvalue A(A) # of A, the inequality |1 adcanl < holds. Define any nonzero eigenvalue of matrix A as A(a) + bi, where and are real numbers, and i is the imaginary unit. Using Lemma A.I the condition ad(ail can be rewritten as:
41

---

V(1 aa-aaa (-ab)²
Squaring both sides and simplifying, we get:
a² (a² + +b²) 2aa 1,
which further simplifies
a²(a² + 132) 2ca 0,
(110)
and since (a² + (2) > O, we know that there exists a make Equation 110 hold only quadratic
equation Equation 111 has two roots:
(a² b 201 = O,
(111)
which means the discriminant of Equation 111 (-2a)² > O, so # 0. When a and 2a a²
(they are two roots), the Equation (III) holds. Therefore,
Assuming a < 0, then 462
0, Equation (100) holds if and only if
(
2a
0).
(2
However, this contradicts the fact that > 0, so it cannot hold.
Assuming a 0, then
2a 6
so Equation (110) holds and only if a E
2a
Therefore, we can see that A E Raxa ()(--a)) E (I - aA) (u-aAa)) < if and only ()(A) a (A) ((0) 0 and E (0,c) where
2a
= min (A)
(112)
a² + 62
2 R(((a))))
min (d)
(113)
|Aaa)?
Hence, the proof is complete.
E.4 Proof of Corollary 6.3
Corollary E.8 (Restatement of Corollary learning rate (0,c) where
6.3
When TD stable, TD converges if and only if
2 R(A)
min (E ((0)
|i
Proof. When TD is stable, from Corollary 6.2 we know that
0rr E Col (Eeon yFer)
and
(Eoov Eer) is positive semi-stable
and
Index (Ecov Eer) s 1.
In such a case, by Theorem 6.1 we know that TD converges for any initial point if and only if
(Ecoe - {err) is semiconvergent.
Next, given the above, by Lemma E.S and Lemma semiconvergent and only if
E.6 we know that (I - a (Ecov - 7Err) is
(2-R(A)
(- R(())
E (0,e) ehere
min
XEo(E.. E..
|
Hence, the proof is complete.
42

---

E.5 Encoder-decoder view
To understand the matrix ALSID 4 -()))))))))) we begin by analyzing the matrix D >Pr), referred the system's 's dynamics, which captures the dynamics of the system (state action temporal difference and the importance of each state). As established in Proposition E.9 D(T - -P nonsingular M-matrix. Being positive stable is an important property of nonsingular M- matrix Chapter 6, Theorem 2.3, G20J. Moreover, since & D ) shares the same nonzero eigenvalues as D - ) (Lemma E.18 positive staiiitability of one implies the same for the other. Interestingly, the matrix D - PPP }$ acts as an encoding-decoding process, as shown in Equation (14). This -eceddngg process involves two transformations: First, &b serves as an encoder, mapping the system's 's dynamics into a d-dimensional feature space; then, & acts decoder, transforming it back to the | x Al-dimensional space. The dimensions of these transformations are explicitly marked in Equation (14). Since from Corollary 6.2 we know that T D(I >P,) being positive semi-stable is one of the necessary conditions for convergence of TD. Therefore, whether this encoding- crcodiin-decoddng decoding process can preserve the positive semi-stability of the system's dynamics determines whether this necessary condition for convergence can be satisfied.
1SxAI
|SxA
D(1 P
(114)
Encoder Decoder
Proposition E.9. (I xxx) and D(I >))> are both non-singular M-matrices and strictly
diagonally dominant.
E.6 TD in the over-parameterizzed setting
Over-parameterized orthogonal state-action feature vectors To gain a more concrete understand- ing of the Eicoder-Decoder View, consider an extreme setting where the abstraction and compression effects of the encoding-decoddee imposed. In this scenario, all information from the system's 's dynamics should be fully retained, and if the Encoder-Decoder view is valid, the positive semi-stability of the system's 's dynamics should be preserved. This setting corresponds to S x A IS (overparameterization) and more importantly each state-action pair is represented by a different, orthogonal feature vector mathematically. ((s,,a,) o(s; az) = 0, Vi + j. In this case, we prove that [D(I > )b is also a nonsingu- lar M-matrix") just like D(I - -PP)). ensuring that positive semi semiistability is perfectly preserved during the sicoding-decoding process. Furthermore, show that in this case, the other convergence conditions required by Corollary 66.2 are also satisfied. Thus, TD is stable under this scenario, as formally stated in Proposition E.
process are entirely eliminated, and with no additional constraints
Proposition F. TD is stable when the feature vectors of distinct state-action pairs are orthogonal, i.e,
o(si,a;) (o) a,) = 0, V(s;, a.) + (s), az).
ever-parameterized linearly independent state-action feature vectors Now, consider a similar over-pe over-paramen wer-parameterized setting to the previous one, but without excluding the abstraction and compression effects of the mucoding-decoding process process. This assumes a milder condition, where state-action feature vectors are linearly independent (Condition I.I] rather than orthogonal. In this scenario, feature vectors may still exhibit correlation, potentially leading to abstraction or compression in the encoder-decoder process. The ability of this process preserve the positive semi-stability of system's 's dynamics depends on the choice of features. Not all features guarantee this unless the system's 's dynamics possesses specific struetural properties (for example, in the on-policy setting, any features can preserves positive semi-stability in system's 's dynamics). We provide necessary and sufficient condition of TD convergence for this setting in Corollary E. These results show that both the consistency condition and index condition in Corollary 6..2 are satisfied in this setting. Only the positive cemi-stability condition cannot be guaranteed, which aligns with our previous discussion. Additionally, the star MDP from Baird [2] is a notable example demonstrating that TD can diverge with an over-parameterized linear function approximator, where each state is represented by different,
In this paper, "orthogonal" does not imply "orthonormal," as the latter imposes an additional norm constraint.
The proof is included in proof of Proposition E.10
43

---

linearly independent feature vectors. Xiao et al. 44 Theorems 2] further investigate the necessary and sufficient conditions for the convergence TD with an over-parameterizee linear approximation in the batch setting, assuming that each state's feature vector is linearly independent. However, the proposed conditions for TD are neither sufficient nor necessary. A detailed analysis provided in Appendix [] Che et al. [1] Proposition 3. attempts to refine the TTD convergence results in Xiao et al. [4], providing sufficient conditions for the convergence of TD under the same setting, However, as we explain in Appendix | this condition, presented, cannot hold. The results in this section provide the correct necessary and sufficient condition.
If we take further step and remove the assumption that the feature vectors for each itte-acttion pair are linearly independent, while still operating over- wer-parameterized setting (i.e., A كا d, but is not necessarily full row rank), the consistency of the target linear system (i.e., the existence of fixed point) can no longer be guaranteed, as demonstrated earlier in Section Naturally, this leads to stricter convergence conditions for TD compared to under the previous assumption.
Corollary E.11. Let & be full row rank. Then TD is stable if and only if either [ D(I PP,)
is positive semi-stable or D(1 22 |
is positive stable.
E.7 Proof of Proposition E.
Proof. As P. x is row stochastic matrix, know that 0 S yP,, S L. obtain that (1 - ->pp, is Z-matrix by Definition A.9 As D is positive diagonal matrix then D - p,,) is also an Z-matrix. From below and by Berman and Plemmons [5] page 137, N38] that any prverse-positive Z-matrix is nonsingular M-matrix, we can see that (7 px)) and D(I - yP,) is nonsingular M-matrix:
- (P)) (1 P
Px)** (convergence of matrix power series due p(yP..)
(115)
20 (ppx 2 0 and 2 0),
so (1 - P is nonsingular M-matrix, then since is positive definite diagonal matrix, using Lemma E.12 we know D(I (P) is also nonsingular M-matrix.
Lemma E.12. Given any positive definite diagonal matrix G. if A is an nonsingular M-matrix, then GA and AG are also nonsingular M-matrices.
Proof. If A is nonsingular M-matrix, then for any positive definite diagonal matrix G. off-diagonal entries of matrix GA or AG is also non-positive, means they are also Z-matrix. Furthermore, since by property of nonsingular M M-matrix(5] Chapter 6, Page 137, N38J, A- Z 0, then we can see that (GA) A G-1 2 0 and (AG) G A 2 therefore we know that GA and AG are both 7-matrix and inverse- positivv,, so they are nonsingular M-matrix.
E.8 Linearly independent features, rank invariance, and nonsingularity
While there may be an expectation that if & is full column rank, TD more stable, full column rank does not guarantee any of the conditions of Corollary 6.2 The stability conditions for the full rank case are not relaxed from Corollary 6.2 which is reflected in Proposition [..
Additionally, in
Proposition [.. 14] we see that rank invariance ensures only the consistency of the target linear system but does not relax other stability conditions.
Proposition E.13. When & has full column rank (satisfying Condition 4.3 if the following conditions hold
TD is stable if and only
1. DR) E Col
2. [ T D(I - )P positive semi-stable
3. Index (Ø (DD P))) 1.
{$ DDI p)) is an M-matrix, the positive semi-stable condition be relaxed to:
4 D(1 -()) is nonnegative stable.
44

---

Proposition E.14. Assuming rank invariance (Condition 4.7) holds, TD is stable if and if only the following 2 conditions hold: (1)(Ecne - - positive semi-stable. (2) Index (Zeon - - S 1.
Nonsingular linear system When the target linear system is nonsingular, the solution of target linear system (the fixed point of TD) must exist and be unique. Additionnlly, the necessary and sufficient condition for TD be stable reduces to the condition that Ar STD is positive stable, as concluded in Corollary E.15 Interestingly, if (Φ6 is a Z-matrix, meaning that the feature vectors
of all state-action pairs have non-positive correlation (i.e., Vi + j. (s a,) ((5, az) 0), and its product with another Z-matrix, D - >P,,) is also Z-matrix, then nonsingular M-matrix. In this case, using the encoder-decoder perspective we presented earlier, we easily prove that TD is stable. This result is formalized in Corollary E.
) T) is
Corollary E.15. When (Ecor >Eer) is nonsingular (satisfying Condition 4.4).
TD is stable if and
only if (Eeor - >/er) is positive stable.
Corollary E.16. When (Eron - Eorr is nonsingular (satisfying Condition 4.4 and two matrices:
ΦΦ
- -D(((--7..)000
are Z-matrices, TD is stable.
E.9 Linearly independent features
E.9.1 Proof of Proposition E.13
Proof. Since @ is full column rank does not necessarily imply any of three conditions in Corollary 6.2 therefore, its existence will not alter the condition of TD being stable. When O is full column rank TD is stable if and only if the three conditions in Corollary 6. hold.
E.10
Rank invariance
E.10.1 Proof of Proposition E.14
Proof.
When Rank (Ecov) = Rank (Ecov -Err). from Proposition 4.2
we know that it implies
0 Colo - YEr). Then, Rank (Ecov) Rank (Eeov Eer) does not necessar-
ity imply "(Ecor - - is positive semi-stable" or "Index (Eeor Eerr S 1". By Corol-
lary 6.2 know that when when Rank (Ecor) Rank (Ecov - ). TD is stable if and only if "(ooo <Err is positive semi-stable" and "Index (Eeor Eerr 1"
L
E.11 Nonsingular linear system
E.11.1 Proof of Corollary
E.15
Proof. Assuming that + is full column rank and rank invariance (Condition 4.1 holds, by Proposi- tion 4.5 we know that
(Ecov >Eer)
nonsingular if and only if + is full column rank and rank invariance (Condition 4.1 holds. There- fore, Index (Ere - - = 0 and (E - -.rr) has no eigenvalue equal to 0. Consequently, (Eron ?Eer) is positive semi-stable if and only if it is positive stable. Moreover, by Proposi-
tion 4.2 we know that Rank (Fcov) = Rank (Eeov -E implies 0g.r E Col (E -.r))
Finally, from Corollary 6.2 we know that when & is full column rank and Rank (Noov)
Rank (2ooo - ). TD is stable if and only if (Ceov - 720r)) is positive stable.
E.11.2 Proof of Corollary E.16
Proof. When each feature has nonpositive correlation, the matrix ΦΦ has nonpositive off-diagonal entries and is thus Z-matrix. At the same time, it is clearly symmetric and positive semidefinite.
meaning all of its nonzero eigenvalues are positive. This implies that it is also an M-matrix [5] Chapter 6, Theorem 4.6, El From this property and Proposition E.9 it follows that D(I ?P=) nonsingular M M-matrix. Therefore, when 46 D(1 >P,) is Z-matrix, it is also an M-matrix
45

---

[ Chapter 6, Page 5.2], and hence positive semilstable. Given that Ecor - -Yeer is nonsingular,
Lemma
implies:
( D(I -Pp})) - ($-. D(I - -Px)) MO3.
Thus, Φ D(I - -x is positive stable, and by Corollary E.15 TD is stable.
E.12
Over-paaaaetteiiation
E.12.1 Proof of Corollary E.11
Proof. Assuming & is full row rank, by Proposition J.2 we know that target linear system is universal consistent that 0gr Col (Eeov >eer Then, by Lemma E.17 we know that
Index ( D(I ))) I 1, and by Corollary 6.2 we can conclude that in such setting,
TD is stable if and only if ( D(7 ) is positive semi-stable. Additionally, by Lemma E.17
we see ( T D(I -P singular matrix, so ( D -
{00) = (D(I -D(I--Pa >P=) )) as we know D ([I->P=)(44 is non-
- p is positive semi-stable and only if (D(1 p )
is positive stable. We can conclude that TD is stable if and only if (D(1 - 2 is positive stable.
Lemma E.17. t is full row rank,
Index (px)) S
and
(hb T D(T - - ()
= o - -pp )
Proof. Given that is full row rank, as we know D(7 - 7P is full rank, so when > d. (D(1 - [D(1->Px)00 T) is full rank, then by Lemma E.19 we know that: Index (DJD(L D(1 - pP,)
1.
When h d. & is full rank square matrix, so + D PP,) ) is nonsingular matrix, and Index ( DDT P)) 0. We can conclude that given that $ is full row rank,
Index (Φ DDD P 4)) 1.
Next, & is full row rank, so ΦΦ is also full rank, therefore D(I ) is full rank matrix, and then by Lemma E.18 we know that:
a D(I - -P M0) (D(I - -P PP>)
Lemma E.18. Given any matrix E Cmxx and matrix B E Caxm, suppose n, then the matrices AB and BA share the same non-zero eigenvalues:
o (AB) (1) =1) (BA) Mo),
and every zerozero eigenvalue's 's algebraic multiplicity:
AA E a (AB) (10), alg mult (A) alg multBa (A).
Proof. Given any matrix A E C and matrix B E Cnxm, suppose m 2 n. From 26 Chapter Solution, Page 128, (9b)), we know that it has:
det (AB XI) (-x)m-a det (BA -X),,
where del (AB - X/) is characteristic polynomial of matrix AB and det (BA X7) is characteristic polynomial of matrix B.A. Therefore, they share the same nonzero eigenvalues and every nonzero eigenvalues' algebraic multiplicity.
46

---

Lemma E.19. Given any matrix A E C and matrix B E C suppose > and A is full column rank and B full row rank, if BA is nonsingular matrix, then:
Index (AB) 1.
Proof. Given that m > and A is full column rank and full row rank, and BA is nonsingular matrix. let's define Jordon form of AB as
Jayo 0
P (AB) P
Jx-o
where JAyO is composed by all Jordan blocks of nonzero eigenvalues, and JA-o is composed by all Jordan blocks of eigenvalue O. Next, define Jordon form of B A as:
p-1 (BA) P Juxn-
J is full rank matrix: Rank (J) = n. Since BA is a nonsingular matrix, then by Lemma E.18 we know that AB and BA share the same non-zero eigenvalue and every non-zer eigenvalue's 's algebraic multiplicity, so
(AB) = (BA) (0),
and
YA E (BA), alg mult alg mult (A),
which means have that Ja nonsingular matrix whose size is equal to Jaxns which is an matrix, so Rank (Jx+o) semisimple, means that Rank (J>=o) > 0, then clearly Rank (J) > n. In this case from Fact C.6 we know it violates the maximum rank J can have, which is n, Rank (A) and Rank (B) so it is impossible. Finally, we conclude that the eigenvalue 0 of matrix AB is necessarily semisimple, so by Lemma E.24 we know that Index (AB)
Assume that eigenvalue 0 of matrix & D >P,> ) g is not
E.12.2 Proof of Proposition E. 10
Proposition E.20 (Restatement of Proposition E.10). When the state-action pairss features are orthogonal each other, TD is table.
Proof. When the state-action pairs' feature are orthogonal to each other, we know that the rows of & are orthogonal each other, as well linearly independent, + is full row rank and 4
a positive definite diagonal matrix. Subsequently, by Proposition E. we know D(I - -p is a nonsingular M-matrix. Therefore, by Lemma 12 we can see that D(T >Px)
also
nonsingular M-matrix, and then by the property of nonsingular M-matrix 5 Chapter 6, Page 135.
G20], we know that D -61--1 pp ) 0 is positive stable. Hence, by Corollary E. TD stable. C
E.13
On-policy
E.13.1
Alignment with previous results
In the on-policy setting, it is well-known that if t has full column rank (linearly independent features (Condition 4.3). then ② D(1 >P, x ) is positive definite, which directly supports the proof of
TD's s convergence [40]. This result aligns with our off-policy findings in Corollary 6.2 as explained
below:
First, as demonstrated in Proposition 4.7 the consistency condition inherently satisfied in the on-policy setting. Second, because ① D -P ) is positive definite, all its eigenvalues have positive real parts (as shown in Property A.4). which ensures that positive stable. Additionally, since Φ D (T >P,) ) is nonsingular,
have Index (Φ D(T >P > 0. Thus, both the positive semi-stability condition and the index condition are satisfied, so the necessary and sufficient conditions for TD being stable fully met.
Proposition E.21. In the on-policy setting (pP,, -.p=-))
[ T D - PP is an RPN matrix.
D( 1)] is negative definite, therefore, [D[T - >P))) is positive definite. Hence, by Lemma A.6 we know that T D >P,) is RPN matrix.
Proof. In the n-policy setting, show in 40
47

---

E.13.2 Proof of Theorem 6.4
Theorem E.22 (Restatement of Theorem 6.4 rank, TD is stable.
In the on-policy setting when & is not full column
Proof. First, as shown in Proposition E.21
D(1 - -PP))))
an RPN matrix, and from Lemma E.23 we know that its eigenvalue X (A) is semisimple. Subsequently, by Lemma E.24 we can obtain that
Index (Φ "'T - -P=) =.
Second, because D(I ,)),)) is positive definite, by Lemma A.16 we know that
Ker (Ø D(I - -P Ker (Φ)
Then, by Lemma C.1
know that
Rank (Eem) Rank (Eem Dor)
Moreover, from Proposition 4.2 we know that Psr E Col (Ecov - -22or) As
R (r
Dr D(T >P)))) 0 for all E CC'((0),
so
R Rx D -x, )x)) for all x E C* /er (4)
we know that for [ D(I - ))]) for eigenvector tλ Ker (2), the corresponding eigenvalue
= 0,and for eigenvector U\ & Ker (.), the corresponding eigenvalue R(AA) > 0. Therefore,
$ D(I - PP,) is positive semi-stable.
Finally, by Corollary 6.2 we know TD is stable.
Lemma E.23. For any singular RPN matrix A E Crxn, its eigenvalue = E a (A) is semisimple.
Proof. As A is singular RNP matrix, x = E a (A) and Index (A) 1 by the Property A.5 for singular RNP matrices. Hence, by Lemma E.24 we know that its eigenvalue X = 0 is semisimple. n
Lemma E.24. Given singular matrix A E Cnx", its eigenvalue À = 0 E a (A) is semisimple if and only Index (A) =
Proof. Given a singular matrix A E Ca and À denoting its eigenvalue. from 26 Page 596, 7.8.4.] we know that index (A) if and only if is semisimple eigenvalue. and by definition of index of and eigenvalue:
index (A 0) Index (A - 0z) = Index (A),
so Index (A) = and only if its eigenvalue
is semisimple.
E.14 Expected TD results in this paper can be easily adapted for stochastic TD and batch TD
From the traditional ODE perspective, has been shown that if expected TD converges fixed point, then stochastic TD, with decaying step sizes (as per the Robbins-Monro condition [32] 40] or stricter step size conditions), will also converge to a bounded region within Additionally, if stochastic TD can converge, expected TD special case of stochastic TD must also converge. Therefore, the necessary and sufficient conditions for the convergence of expected TD can be easily extended stochastic TD, forming necessary and sufficient conditions for convergence of stochastic TD to bounded region of the fixed point's solution set. Thus, our previous result in this section automatically extend to for convergence of stochastic TD to a bounded region of the fixed point's solution set. All the convergence condition results presented Section 6 naturally hold as convergence condition results for convergence of stochastic TD to a bounded region of the fixed-point's solution set.
Stochastic TD
the solution of the fixed point 19
13
40
48

---

For instance, as demonstrated in Theorem 6.4, setting of Tsitsiklis and Van Roy 44). even without assuming linearly independent features. This implies that stochastic TD with decaying step sizes, under the same on-policy setting and without assuming linearly independent features, converges set. In other words, the linearly independent features assumption in Tsitsiklis and Van Roy [40] can be removed - a result that, to the best of our knowledge, has not been previously established.
expected TD is guaranteed to converge in the on-policy
bounded region of the fixed point's solution
Batch TD By replacing 4, D, P.P. Yooos Ber and 4 with their empirical counterparts 4. D, P extend the convergence results of expected TD to batch
Der and 0g.r. respectively, For example, Corollary 6.3 which identifies the specific learning rates that make expected TD converge, is particularly useful for batch TD. By replacing each matrix with its empirical counterpart, we can determine which learning rates will ensure batch TD convergence and which will not. This aligns with widely held intuitions in pratical use of batch TD: When a large learning rate doesn't t work, trying smaller one may help. If TD can converge, it must do so with sufficiently small learning rates. In summary, reducing the learning rate can improve stability.
E Seous
TE
F
The convergence of PFQI
F1
Interpretation of convergence condition and fixed point for PFQI
the necessary and sufficient condition for PFQI convergence are established, comprising two primary conditions: 1ISTTD E Col (ALSTD), and the semiconvergence of HPFQI = - -MPQQLALSTD- As demonstrated Section the condition &LSTD E Col (ALSTD) ensures that the target linear system is consistent, which implies the existence of a fixed point for PFQI. The semi- convergence of Hpror indicates that Hyroι converges on Ker (ALSTD) and functions as the identity matrix on Ker (ALSID) if Ker (ALSID) + (0).
In Theorem 7.1
Since any vector can be decomposed into two components - one from Ker (ALSTD) and one from Ker (ALSTD) - the above condition ensures that iterations converge to a fixed point for the component in Ker (ALSiD) while remaining stable for the component in Ker (ALSID), with no amplification. Given that HPFQr = Mr if Ker (ALST) * {0}. then HpFQI necessarily includes an eigenvalue equal to I, necessitating measures to prevent amplification of this component through iterations.
The fixed point to which FQI converges composed of two elements:
(MPFOIALSTD)) MPFQILLSTD and (I (MMrg tg.
The term (1- (M-MMMorAAAssm 0 represents any vector from Ker (ALSTD), because
(Mrrgu (MPra
acts projector onto
Col ((MTDOIALSTO))* along Ker (LMP)))ALSSID*
while
serves as the complementary projector onto
Ker (MSP)) along Col (LSDD))
where k = Index (MPPqqAASSID). Conseuuuu Consequently,
Col (M4
Ker ((MPPQIALSTT)*)
1hhiile the extension the on-policy setting is straightforward in principle, in practice when data sampled from the policy to be evaluated, it is unlikely that üPP, x will hold exactly.
49

---

7.1 PFQI converges for any initial point 9g if and only if Given that HproI is semiconvergent, it indicates that Index ALSTD) & 1 since ALSDIAASTD I Hrqi- Then, we deduce that
Col (1
(MrroiAAssss)))MMrrAA = Ker (ISTD)A
Since Mpror an invertible matrix, it follows that
Ker (MPEQLALSID) Ker (ALSTD).
Thus, (I- ALSTDI (LSTDIAASTDD) 0g can represent any vector Ker (ALSTD). Addition- ally, given that Index (M I 1, obtain
(ISTT)AASTD) MrrQrbASTD (MPTQ MPFQULLSTD
In summary, we can conclude that any fixed point to which PFQI converges is the sum of the group inverse solution of target linear system, (AI.((..)T) BISTD, and vector from the nullspace of ALSTD i.e., Ker (ALSTD).
F.2 Proof of Theorem 7
Theorem F.1 (Restatement of Theorem
Orr E Col (Eeon -
and
t-1
(Eeor - FEcr) is semiconvergent.
1=0
converges to
D 1-1
Σ (Cco)) (Ecor [err
Σ
[I
aCco)
(116)
1- - alcoo) (oocoonioon - VEer))
[-1
))
-
(CCcoo) - )20rr) 0o
(117)
i=0
E OLSTD
(118)
Proof. From Proposition B.1 know that PFQI is fundamentally iterative method solve the target linear system
Eeco >.,rr 0g.--
Therefore, by Berman and Plemmons converges if and only if (Ecov Eerr
5 Pages 198, lemma 6.13] know that this iterative method
2gr consistent:
0 E Col (Ecor EErr
and
a
"cov)" (Ecor - >eer) is semiconvergent.
converges to
1-1
Σ ( (Eeov (For)
Σ
I ('coo)
(119)
aCoo)) ( - -Err))
Σ ) - ))rr)) do (120)
E OLSTD
(121)
50

---

F.3 Linearly independent features
Proposition F.2 studies the convergence of PFQI, showing that linearly independent features does not really relax the convergence conditions compared those without the assumption of lin- early independent features. However, linearly independent features remains important for the preconditioner of PFQI: MPFQI = a E/ (I - aLoo)) because it is upper bounded with in- creasing t, precisely as lim4-+00 a Zizo (1 -a Doo. Without linearly independent fea- tures, MPFOL = a ai=0 (I aCoo)) will diverge with increasing (for a detailed proof, see Mpror ALSTD may also diverge. This will cause divergence of the iteration except some specific cases, like an over-parameterized representation, which will show in Appendix [.3 where the divergent components we know that when the chosen features are not linearly independent, taking a large or increasing number of updates under each target value function will most likely not only f'ail stabilize the convergence of PFQI, but will also make it more divergent. Thus, if the chosen features are a poor representation, the more updates PFQI takes toward the same target value function, the more divergent the iteration becomes. This provides more nuanced understanding of the impact of slowly updated target networks, as commonly used in deep RL. While they are typically viewed as stabilizing the learning process, they can have the opposite effect if the provided or learned feature representation is not good.
Appendix F.3. and consequently, Hpro:
be canceled out. Therefore,
Proposition F.2. Let Condition 4.3 any initial point Og if and only if
be satisfied, i.e., is full column rank. Then PFQI converges for
BLSTD E Col (ALSTD)
and
(I M MISTI semiconvergent.
converges to
(MPrerASSII) MProybESID (I (ArrrAAAssso(MMMrAArrrrr Bu] OLSID-
F.3.1
When & not full column rank, MpFor diverges as t increases
When & is not full column rank, Eeor < D& is symmetric positive semidefinite matrix, and can be diagonalized into:
Ezor = Q-1 Kixr Q,
where Kyxr is a full rank diagonal matrix whose diagonal entries are all positive numbers,r Rank (Ecor), and is the matrix of eigenvectors. We will use K to indicate Kyxr for the rest of the proof. Therefore, we know
t-1 MpPQI = aL-mmo aloo))) Q-1
(at)l 0 [(at) (1-(1-ak)) Jo.
x=0
Clearly, given fixed a, we can see that oo, [(at)T] - oo in the matrix above. Therefore, Myroi will also diverge.
F.3.2 Proof of Proposition F.2
When is full column rank (Condition holds), PFQI converges for any initial point 0g if and only
Proposition E3 (Restatement Proposition
F2
fgrr Col (Ecov EEe Yand
a Et-l(1 (I aoou)' (Ecov -Err)
1 + (I ( 111---11 Eor)] is semiconvergent,
~
51

---

It converges to
1-1
11 - (No - 22ics)
11
a
(122)
==0
1-1
+
I
[T a1 (e - (Ferr)
Σ
(I a aCoo)) (Ecov (Eer)
du
(123)
1=0
E LLTTD
(124)
Proof. As we show in Proposition B.1
when & is full column rank,
1 a-a a ( aCoo)' (Ecov eerr
[ + aLCoo) - --o Eer)
Then, using Theorem 7.1 we know PFQI converges for any initial point 0g if and only if
0zr E Col (Eom - -
and
Eo Dor + (I aL Dcou) Eerl is semiconvergent.
converges to
aConno )'0.r
(125)
[-1
+
1
[ (FEcov) - (Feor)
Σ
(T (Cooo) ( (Eron FEoor)
0o
(126)
OLSID-
(127)
E4 Rank invariance and nonsingularity
First, Proposition shows the necessary and sufficient conditions for convergence of PFQI under rank invariance (Condition 4.1. We see that while the consistency condition can be completely dropped, the other conditions cannot be relaxed, unlike FQI. Second, in Proposition F.4 we provide necessary and sufficient condition for convergence of PFQI under nonsingularity (Condition 4.4). We can see that in such case, the fixed point unique, and requires Hyroı to strictly convergent (p (HPFQi) < 1) instead of being semiconvergent.
Proposition F4.. When rank invariance (Condition 4.1) holds, PFQI converges for any initial point to if and only if HPFQl = (T
is semiconvergent. It converges to
(MPFOLAESTTD) MPFOIbLSTD (I (MProgAALST)
8o] OLSTD.
Corollary F.S. When (Eron Eerr is nonsingular (Condition 4.4 holds) and (I - aE is nonsingular, PFQI converges for any initial point On if and only p (I MrroiAssmn 1. converges to
[Eooo - Eorr Bo.r ALLIDD
F.5
Rank invariance
F.5.1 Proof of Proposition E.4
Proposition F.6 (Restatement of Proposition F.4). If Rank (Eom) = Rank (Eoo - -Eor)) (Condi- tion 4. Tholds), then PFQI converges for any initial point Oo if and only
0
Σ
aCen)) (Ecov - EErr
semiconvergent.
1=0
52

---

It converges to
1-1
1-1
Σ II (Ccoo)"(Eea) - (Eerr)
Σ
(I (.oco)'00.
(128)
1=0
[-1
[-1
+
--
Σ [1 aLicov) aCCoo)((Ecor - (Porr)
E (I aCooo (Eer)
do
(129)
1=0
i=
E LSTTD
(130)
Proof. When Rank (Ecov) = Rank (Feor -err, from Proposition 4.2
we know that it implies
Pør Col (Xcor -rrrr..
Next, Since Rank (Ecov)
= Rank (Neov - (2irr) does not necessarily imply
1
> (T (T-aoooo (oon) (Eron Eaer) being semiconvergent, 1=
by Theorem 7.1 initial point V if and only if
know that when Rank (Scov) Rank (Coou >.err) PFQI converges for any
(1
aooov)' (Ecor (orr is semiconvergent.
t=
It converges to
Σ 11 aCoo) (Ecor (Zier)
Σ
[I (Coo) )'0.r
(131)
1=0
i=0
1-
Σ [I
- (Zerr)
Σ (I (' ?Eer)
Oo
(132)
i=0
i=0
E OLSTD
(133)
F.6
Nonsingular linear system
F.6.1 Proof of Corollary F.5
Corollary F.7 (Restatement of Corollary F.S). When (Eco - is nonsingular (Condition 4.4
holds) and (T (E is nonsingular, PFQI converges for any initial point Og if and only if
1-1
(1-a
1-a
I
E( (I aEco)) (Ecov (Eerr) 1.
p
It converges to (Se.n Zoor)
E 11STD
Proof. Given that (Ecov - Eer) is nonsingular and (I- aCcov) nonsingular, by Lemma B.2 we know that a E1 aoov) is full rank. Therefore.
Σ
II E'ov)' (Ecov EEer) is full rank,
which means it has eigenvalue equal 0. Therefore, by Lemma A.1 we know that I Ei=1(I- aLoov) (Eoov >orr) has eigenvalue equal to 1.
53

---

Subsequently, I --a Ei - aLCovo' (Ecoe - (Ler) is semiconvergent if and only if
(1-0 1-1 (1- aCco)) (Ecov >Leer) <
By Proposition 4.2 we know that Rank (Noov) Rank (Neor 2eer)) implies
0 E Col (Ecor (Err).
Next, using Theorem 7.1 we can conclude that when (Eeor >Err is nonsingular (Condition 4.4
holds) and (I eeor) is also nonsingular, then PFQI converges for any initial point fy and only if
t-1
1
Σ ==0
--Eooo (Eror >ZZor))
< 1.
Additionally, as Ei alCcov)' (Eoow - -Woor) is full rank,
Σ
aCoo) (Econ {Zer)
Σ [1 aCoo)) (Eco - FEerr)
Hence, we know that converges to
D 1-1
1
Σ - (' - 72ier)
Σ
aLiooo) )00.r
(134)
==
(-1
L-1
D
+
I
(<ooo) - -xIer)
Σ (I aCcov) ( (Ecov FEer)
dg
(135)
1=0
aCoo)) (Ecov (Earr)
(I aCoo)) '
(136)
t-1 (1- )oou)
(Ecor
FFirr)
Σ (T aFcon))
(137)
(Ecov >Eerr) - 00.r
(138)
OLSTD-
(139)
G PFQI as transition between TD and FQI
G.1 Relationship between PFQI and TD convergence
G.1.1 Proof of Theorem 8.1
Theorem G.1 (Restatement of Theorem 8. 1. If is stable, fhr any finite N there exists E R that for any a E (0,+g) PFQI converges.
Proof. Assuming TD is stable, then by Corollary 6.2 we know that
Ogr E Col (Ecov - EEr)
(Ecov Eer) is positive semi-stable, and
Index (Doov >orr S 1.
54

---

From Theorem 7.1 we know that for any & E Z+, if PFQI converges from any initial point & if and only if
1 Σ
Econ) (Econ )Eor)
semiconvergent
(140)
and
prr E Col (Deoo - -YEer)
From Lemma E.5 and Lemma
E.6
we know that Equation (140) holds when
E aCco) (Feoo -eer
==0
is positive stable positive semi-stable, where = = (Eizo(1 ) /Borl) is semisimple, and a E (0, E) where
R((A)
min AEo (E ( (Beo-->Ber))) |1
Next, from Lemma G.2
we know
t-1
Σ (1 aCoo)) (Ecov - -EErr) = (Eooe (Der))
(141)
1=0
Σ 1=2
(a) (-Eon)))) (Eear - vErr).
(142)
For fixed, finite & E Z+, define an operator
Ti(a) A + aE
where A (Econ >Eer) and E ()) (1a) (Econ - -EErr), clearly,
i-1 ( -I- aE 1=0
Ti(a)
(Eeoc -Fer)
From Meyer 226 Page 425, 5.12.4.], we know for any sufficiently small perturbation when the 22-norm of perturbation is smaller that the smallest nonzero singular value of unperturbed operator, then the perturbed operator must have greater equal rank than unperturbed operator. Therefore, for any sufficiently small a such that |22 is smaller than the smallest nonzero singular value of A, Rank (a)) > Rank (A). Obviously a Row (A) so Rank (A + aFE) Rank (A). Therefore, for any sufficiently small a, Rank (a)) = Rank (A), so
geo mult (a) (0) geo mult A (0) dim (Ker (A)).
It is easy to see that lima-50 Ti(a) (0) = A, so (a) is continuous at the point a 0. By the theorem of continuity of eigenvalues 22 Theorem 5.1], we know that if the operator T.(a) is continuous at a = 0, then the eigenvalues of T(x) also vary continuously near = 0. This means small changes in a will lead to small changes in the eigenvalues of Tı(a). There- fore, if (,) is positive semi-stable, there must exist small enough e' E IR+ that for any a E (0,''), Ti(a) is positive stmiestable, and the sum of the algebraic multiplicity of every nonzero eigenvalue for Ti(a) is the same as for (0) (no nonzero eigenvalue of (0) changes to 0 by perturbations (aE)), which implies alg multt, (0) = alg multT, (a) Then, when 0 E (A) semisimple, it means alg (u) (0) = geo multT,,() (0). Since we al- ready know alg multt,(o)()) (0) = alg multT, (a) (a)(0) (0) and geo mu) (0) geo mu)lt,(.)(O))) then alg mullir,() = geo (a) (0), semisimple. Thus, if E min(c, c'), the PFQI convergence condition satisfies.
0 a (E D...)''(E...... >Eor) is
Finally, we can conclude that if when (E,m - 7 E.r) is positive semi-stable and À = 0 E a (A) is semisimple, for any finite & N, there must exist R+ that for any a (0, PFQI converges from any initial point 0g-
55

---

Lemma G.2.
Σ - )oo)))) (Fron - -oor)) = (Feo - -Sorr)
(143)
: (a))-
(Ecor - --Ste)
(144)
Proof. As Evou is symmetric positive semidefinite matrix, it can be diagonalized into:
[ [000 1 K Q,
Ecor = QQ11
where Kyxr is full rank diagonal matrix whose diagonal entries are all positive numbers, and
Rank (Ecoe). Thus, it's easy pick a that (1- xxr nonsingular, we will assume
(T - a Kexr) as nonsingular matrix for rest of proof. We will also use to indicate Kyxr for rest of proof. Therefore, know
(al)
Σ II
a )oo =
a (1 - -ok))
Q
(145)
0
(at)
Q-1
Q
(146)
0
(1- (I -1-ool -K))) K-1
(al)
Q-1
0
[ (I- (9(a) K-1
Q
(147)
(at)
Q-1
(9 K-1
(148)
0
(at)l
0
Q-1
(lat) - Eize (-X)--)))
Q
(149)
0
(Eiz ((a)(())))))) ].
(at)) Q-1
?
(150)
(at)l
Σ
(a)
(-Eco))
(151)
= (at)l a Σ (a) ( (-onn()))))
(152)
Moreover,
1-1
Σ (T acoo) (EEoo - -Eerr) = (Ecov EEerr)
(153)
(ax) (-))mm((-E (Eear - >Eer). (154)
2=2
Lemma G.3. Given a matrix: A Raxm if B Raxm and Col (B) S Col (A), then Rank (A + B) < Rank (A).
Proof. Assuming Col Col C Col (A), then we know there exists a matrix C E Rmxx such that
B = AC. Therefore, A A(T + C), and by Fact C.6 we know that Rank (A B) min (Rank (A), Rank (1 + C)) Rank (A).
S
O
56

---

G.2 Relationship Between PFQI and FQI Convergence
Proposition G.4 (Restatement of Proposition 8.2
For a full column rank matrix & and any learning
rate O0 Xmme (Famm)) if there exists integer T E z such that PFQI converges for all t > TT' from any initial point 0o then FQI converges from any initial point 0n-
Proof. From Lemma G.5 we know that when is full column rank, Hproi = - a Ei=0
aLCcoo)' (Eeov ) can be also expressed as
HPFoI = (7>izot Eir + (I a' 22 )er))
and the PFQI update equation can be written as:
8k+1 (1 Fer (I aLcov) - ( 0%.
+ (I- (I- aLcov) )
From Theorem 5.1 we know that PFQI converges from any initial point 0g if and only if 0gr Col (Nooe - yDor)) and HpFor is semiconvergent.
Next, when a is not sufficiently small, its value can be easily adjusted so that a Ei (oow)) )' (Scov - -)Err) has no eigenvalue equal to 1. By Lemma A.I this implies that / " - a ( )' (Eom - has no eigenvalue equal to O, and thus it is nonsingular. There- fore, assuming I Ei=b(T aCoov'' (Ecov EEer) to be nonsingular in such cases does not lose generality.
When a sufficiently small, the entries of a (T= acoo (Ecov - -E are also sufficiently small. From [26] Chapter 4, Page 216], we know that the rank of matrix perturbed by sufficiently small perturbation only increase remain the same, I Ei=o ) (Ecov >EEr)
is nonsingular since is nonsingular.
Overall, we can see that / - a E1 - -oou)) (Eeoo yLoor) is a nonsingular matrix, which has no eigenvalue equal to 0, independent of f.
Therefore, when there exists an integer T - such that for all / T. 0s. E Col (Ecov - -PEer! holds and HPFQI is semiconvergent, by theorem of continuity of eigenvalues [2] Theorem 5.1] we know that:
lim Eor + (I aC -1 1-000
2ird = >in Ear is semiconvergent.
Then, by Theorem 5.1 we know that FQI converges for any initial point 0g.
Lemma G.5. When full column rank, the PFQI update can also be written as:
0x+1
(7 Fer + (T O.Ecovo' )'(())(TTT - > Eor)) Oz.
(155)
+ -FEovo E'
Proof. As know that when d is full column rank, Ecor & D is full rank. Therefore, by Fact...6 we know that
Σ (I- aeon)) (I (I- aD E-1
Then, plug this into the PFQI update:
1-1
a =
[I a.eoo) )' (Ecov - (Crr)
Ox + a Σ a a.Ccoo) )
(156)
= 1- (I - aCoov) 11) D-d (Eoo Worl] 0x+1 + (I - (1 aLcovo D-1 Ss
(157)
= | Eer + (I - aEcov -I------1- Ear) O + (I - (I -aEcov) Eehh Dor
(158)
D
57

---

Fact G.6. For square matrix 7 and positive integer the geometric series of matrices is defined as:
S, :-
(159)
A
Assuming that / T is invertible (where / the identity matrix of the same dimension as T), the sum of the geometric series can be expressed as
S = (I- 1 -1--
(160)
This is implied by Lemma Lemma G.7. Given three square matrices A, B,B.C E RR A commutes with B and C then, A also commutes with B + C.
Proof. If A commutes with B and C. this means AB BA and AC C.A. Therefore A(B+C) AB + AC = BA + CA = (B A.
Lemma G.8. Given square matrix A E Cuxn, (T- A²) and (T A) commute for any E N.
Proof. For any 2 1:
--1
Σ
AI
1=0
80 DE A' -I- (9-A -1 Next, also have:
1-1 (1 A) Σ -'=1-A',
1=0
EE A' -'= (I (7- A²). Therefore, know:
(I AI- A) A)- A²).
Thus, A') and (1 - A) commute.
Theorem G.9 (Restatement of Theorem 8.3
When the target linear system is nonsingular (satisffyngg Condition 4.4) the following statements are equivalent:
1. FQI converges from any initial point tg-
2. For any learning rate E (0, Xmaz (Zcov) there exists integer T E Z+ such that for
2 T, PFQI converges from any initial point 9g-
Proof. First, since Proposition 8.2 has proven that under linearly independent features (Condition 4.3
Item limplies Item[] and Condition 4.44 implies Condition 4.3 therefore, under Condition 4.4] Item implies Item [ Second, from Corollary D.6 we know that FQI converges from any initial point 6g
and only if EzE Ear)
2 1. Next, for any learning rate E (0, Xmax (Dewv) ) P (I a 1,
so
lim [I )'(I E Eer)) O.
1-000
Therefore, by the theorem of continuity of eigenvalues 22 Theorem 5.1] we know that (7220122er)) < 1, then there must exist an integer T E Z such that for all t 2 T:
P -I- E )'( - <
In this case, by Corollary implies Item 2
E.
we know PFQI converges from any initial point tg Therefore, Item
The proof is complete.
58

---

G.3 Convergence of TD and FQI: no mutual implication
TD converges while FQI diverges Consider a system with |S x A| = 3, 2, and y 0.8.
where the feature matrix & the state-action distribution D, and the transition dynamics P= are defined as follows:
0.1
0.1
0.7
0
0
0.8
0.2
D
0
0.1
0 0.2
P
0.5
0
0.5
0.8
0.4
0.7
0.2
0.1/
In this system, the matrix & D - 4 has two distinct, positive eigenvalues, 0.09385551 and 0.01006449, indicating that it nonsingular and positive stable. Therefore, by Corollary F5.15 TD
is stable. On the other hand, y ($TD)) " Φ DΦ = 1.011068 1, and from Corollary D.6 this implies that FQI diverges.
FQI converges while TD diverges Now, consider different system, again with |S x AI 3. = 2, and y 0.8, where the feature matrix & the state-action distribution D, and the transition dynamics P. are defined as follows:
0.1 0.2
0.2
0
0
0.1
0.3
0.0
0.6
0.3
D
0
0.7
0
P
0.1
0.2
0.7
0.7
1.0
0.1
0.1
0.1
0.8
In this case, the matrix T T D(T->P,))) has two complex eigenvalues, -0.00056 0000056++00248A000 0.024445866 and -0.00056 0. 0.02484556i, which shows that it is nonsingular but not positive semi-stable. Therefore,
by Corollary E.15 TD diverges. Meanwhile, y (TDDΦ) dp D x 0.94628 1, and from
D
Corollary D.6 we know that FQI converges.
H TD and FQI in a Z-matrix system
In the previous section, we showed that the convergence of TD and FQI do necessarily imply each other, even when the target linear system is nonsingular. A natural question arises: Under what conditions does the convergence one algorithm imply the convergence of the other? In this section, we investigate the conditions under which such mutual implications hold.
Assumption H.1. IZ-matrix System]
(1) (Eooo - -orr Z-matrix (2)
(3) Eer 20
(161)
First, will introduce Assumption H.T which essentially requires preserving certain properties from the system's dynamics: D(T - PP and its components, D and P Assumption H.1 composed
of two parts: First, ALSID Ecor -orr is Z-matrix; second, Σ-1 2 0 and D Per 2 0. which
means that Ecor and Eer form a weak regular splitting of (Eeoe Eer) Given these matrices' decomposed forms:
Ecor 7EEr = $ D }, Σcor DDP, E D
examining the components between and & each matrix reveals something interesting: First, D(I ,,,,) from (Φ D(I >P)) is Z-matrix (proven in Proposition E.9,, and second, D and (>DP=) form a weak regular splitting of D >Px)), Essentially, Assumption H. requires that these properties be preserved when the matrices are used as coefficient matrices in the matrix quadratic form where & is the variable matrix.
Theorem H.2. Under Assumption are equivalent:
H. and rank invariance (Condition 4.1 1
the following statements
1. TD is stable.
2. FOI converges for any initial point 0g-
Theorem H.2 shows that when Assumption H.T and rank invariance (Condition 4.1 are satisfied, the convergence of either TD or FQI implies the convergence of the other. The intuition behind this
59

---

equivalence in convergence is that when Assumption H.1 H.1 and rank invariance (Condition 4.1) hold, the target linear system a nonsingular Z-matrix system, and the matrix splitting scheme FQI uses to formulate its preconditioner and iterative components is both weak regular splitting and proper splitting. In such cases, from the convergence of either TD or FQI, we can deduce that target linear system is nonsingular M-matrix system (where ALSTD is nonsingular M-matrix), which is naturally positive stable (TD is stable) and whose every weak regular splitting is convergent (FQI converges). Overall, from above see that under the Z-matrix System(Assumpinnn H.I) and rank invariance (Condition 4.1. the convergence of TD and FQI imply each other:
TD is stable + FQI converges
H.1 Feature correlation reversal
First, let us denote each column of the feature matrix & as spi where represents the index of that feature. For a feature matrix with features, the columns are: 91, (2, Pa...., (a. Each yi represents the i-th feature across all state-action pair. We call ii; the feature basis vector, which is distinct from the feature vector ((s, a) that forms a row of Φ
Assumption H.4 presents an interesting scenario where the transition dynamics (P₂) can reverse the correlation between different feature basis vectors, and importantly, it satisfies the Z-matrix System A ssumption H.1) More specifically: First, Emor = + DΦ being a nonsingular Z-matrix means that the feature basis vectors are linearly independent (i.c., & is full column rank). Moreover, after these vectors are reweighted by the sampling distribution, any reweighted feature basis vector has nonpositive correlation with any other original (unreweighted) feature basis vector, i.c., Vi of j. .p Dig; 0. Second, Eer + DP T 0 means that Px reverse these nonpositive correlations nonnegative correlations, i... Vi + j. Pp DP +j 2 O. Under this scenario, as shown in Proposition [H.3] Assumption is satisfied, and consequently, all previously established results apply to this case.
Proposition H.3. If A/ssmpption holds, then Assumption 1.1 also holds.
Assumption H.4. [Feature Correlation Reversal]
(1)Ecov is nonsingular Z-matrix (2)E.r
(162)
H.2 Proof of Theorem H.2
(Ecor - - is Z-matrix, E-1 2 and E Eer 2 Then by definition, Eeov and yEer form a weak regular splitting of (Ecov -EEe)) ), and by Proposition 4.5 (Ecov ->Eer) is a nonsingular matrix.
Proof: Under Assumption H.1 and rank invariance (Condition 4.1
TD stable=FFQI converges: When TD is stable, by Corollary E.
we know that (Eoor - Eer) is positive semi-stable. Since (Eron - -EErr) is also a Z-matrix, by [5] Chapter 6, Theorem 2.3, G20] we know that (Ecor - -.Err) is nonsingular M-matrix. Therefore, since Ecoo and yEer form a weak regular splitting of (Ecov ->Eer), by the property of nonsingular M-matrix Chapter 6,
Theorem 2.3, 047], every weak regular splitting is convergent, so p (1 < 1. Then, by Corollary D.6 we know that FQI converges for any initial point 0n.
FQI converges= TD is stable: Assume FQI converges. By Corollary D.6 we know that pl7E < 1. As Ecor and yEer form weak regular splitting of (Deo - -orr) and (Eron YE.r)) ). is Z-matrix, by [5] Chapter 5, Theorem 2.3, N46), (Eem -,E,r) ) a nonsingular M-matrix. By the property of nonsingular M M-matrix(5] Chapter 6, Theorem 2.3, G20], (Ecov Eer) we know TD is stable.
is positive stable. Then, by Corollary D.6
The proof is complete.
H.3 Proof of Proposition H..
Proof. When Assumption H.4 holds, Eom is a nonsingular Z-matrix, and Σ,, 2 0. Since Enor is also symmetric positive definite, by Berman and Plemmons [5] Chapter 6, Page 156, 4.15), we know that Eoor a nonsingular M-matrix. Moreover, by the property of nonsingular M-matrix Chapter 6, Theorem 2.3, N38], we know that E-1 2 0. Together with Σ., 2 0, this implies:
60

---

First, (Ecov - cer has nonpositive off- off-diagonal entries, which means (Ecov - -E is Z Z-matrix. Second, 2000 Ser 2 0. Therefore, Assumption H. satisfied.
I Corrections to previous results
Section 2.2 of Ghosh and Bellemare [1 The paper claims that in the off-policy setting and assuming linearly independent features when TD has a fixed point, that fixed point is unique, citing Lagoudakis and Parr (23]. This result is used throughout their paper. However, Lagoudakis and Parr [23] does not actually provide such a result, and this claim does not necessarily hold. More specifically,
show in Section 4 the fixed point is unique if and only if both linearly independent features and rank invariance hold, where rank invariance is a stricter condition than target linear system being consistent (which is equivalent to the existence of fixed point). Therefore, when TD has a fixed point (target linear system is consistent) and linearly independent features holds, the fixed point is not necessarily unique since the target linear system being consistent does not imply rank invariance. It is aslo worth mentioning that in the on-policy setting with linearly independent features, when TD has a fixed point, that fixed point is unique, as we demonstrate in Section 4.
Proposition 3.1 of Ghosh and Bellemare [17 It is only sufficient but not necessary condition. Specifically, the proposition states that, assuming & is full column rank, TD is stable if and only if (Φ D(1 7P 2)) is positive stable. As interpreted in this paper, while positive stability of (Φ D( -())= is indeed a sufficient condition, it is not strictly necessary.
In Proposition 13.13 we establish that, under the assumption that & is full column rank, TD is stable if and only if the following three conditions are satisfied:
1. The system consistent, i.e., (Ø T "DR E Col T DD -)())))))))
2. i T D(! - -?P,) is positive semi-stable.
3. Index (Φ DDI PP)) < 1.
If (+ D( is positive stable, then + D(T - 7P,)) is necessarily positive semi-
stable and nonsingular. As shown in Section 4 any nonsingular linear system must be consistent; hence, the nonsingularity of (@TD( D(1 - p ))) ensures that (Φ) DR) E Col (Ø DD1 - >p,)
holds. By definition, this also implies Index D - 7P )b) = 0, satisfying the condition
Index ( D(T->P=)00 < 1. Therefore, the positive stability of ( D PP) guarantees TD stability.
However, the three conditions in Proposition E.13 reveal that TD can still be stable when (Φ D(I ))))) is singular and not strictly positive stable. Therefore, while positive stabil- ity of (+ D(T - PP)) is sufficient condition for TD stability, it is not a necessary one.
Corollary 2 of Asadi et al. [1] It is a only sufficient but not necessary condition. In the context of our paper, their Corollary states that, given & has full column rank, FQI ("Value Function Optimization with Exact Updates" in their paper) converges for any initial point if and only if (+Eal For) < 1. In Proposition D.3] we demonstrate that, given + has full column rank, FQI converges for any initial point if and only if the following two conditions are met: (1) the target linear system must be consistent, i.c., 0 E Col (Voor - -)or)), and (2) (1- Eor) is semiconvergent. is semiconvergent and that (I- (I-7E-1 E..r) is nonsingular, it has no eigenvalue equal 1 (see Lemma Since Eror is full rank, it follows that Zoao( (T 7--1 Eer) Eeor - -eeor is also full rank, ensuring the consistency of the system, ie., for E Col (Ecoe - EEr). Therefore, p (>>eddEer) < 1 is indeed a sufficient condition for convergence. However, as we show, (-E Eer) being semiconvergent, according to Definition A.7 does not necessarily imply that (yI-1 Eerr) < 1. Thus, while (> < 1 is sufficient condition for FQI convergence, is not a necessary condition.
When (7E E < 1, it implies that (yE
Theorem 2 and Theorem 3 of Xiao et al. 44
In Theorem 2, Xiao et al. 44 study the convergence of Temporal Difference (TD) learning with over-parameterizee linear approximation, assuming that the state's feature representations are lincarly independent. The paper proposes condition claimed
61

---

to be both necessary and sufficient for the convergence of TD. However, the proposed condition is flawed and does not hold as either sufficient or necessary due to errors in the proof. Specifically, between equations (51) and (53), it is claimed that for a non-symmetric matrix, |W]| < "Given |W] < 1/7,, all eigenvalues of k ? W are positive." " This claim incorrect, as we can only guarantee that the eigenvalues of I W have positive real parts, not that they are strictly positive.
implies:
Additionally, the matrix 7/ (IR W) MM D2 is not generally symmetric positive definite, as its eigenvalues can be negative or have an imaginary part. Consequently, the condition does not necessarily imply that the matrix power series EL (I In WW) MM D&) MMM
n (Ix W) MMMMM D&
converges, and vice versa.
In Theorem 3, Xiao et al. [44] also attempts to analyze the convergence of Fitted Value Iteration (FVI) in the same setting, providing a condition claimed be both necessary and sufficient. However, the paper does not provide proof for it being a necessary condition, and as we demonstrate, while the condition is sufficient, it necessary for convergence.
Proposition 3.1 of Che et al. [11] In Proposition 3.1, the paper claims that the convergence of TD in their overparameterized setting (d > k) can be guaranteed under two conditions. One of them is p (I - nM ( - yN)) < 1, where M E Rexd and E Rexd Since > k. we know that M (MM -N is a singular matrix. Then, by Lemma A.1
we know that
(I TM (M - -N)) must have an eigenvalue equal to 1, which contradicts the condition - - (M(M- 22)) < <. Therefore, this condition can never hold.
[9
J
Over-parameterized setting
J.1 Consistency and nonsingularity in the wrempaaraeterizzed setting
Consistency Condition J.I describes an over-parameterized setting in which the number of features is greater than equal the number of distinct state-action pairs (h S d),, and each state-action pair is represented by different, linearly independent feature vector (row in ④). It is completely different from linearly independent features, which means full column rank of 4. Condition immplie rank jimplies
invariance. Therefore, it also implies the target linear system is universally consistent. In this case, the existence of fixed point is guaranteed for these iterative algorithms that solve the target linear system. However, in the over-parameterized setting rank invariance does not necessary hold without Condition [.1
For the nonsingularity of the target linear system under the over-parameterized setting, when h d, it can still be guaranteed if linearly independent features (Condition 4.3) holds. however, in the case h < d, the linearly independent features (Condition 4.3) condition can never be satisfied, and thus nonsingularity and consequently the uniqueness of the solution is impossible.
Nonsingularity
Condition J.1 (Linearly Independent State-Action Feature Vectors). 4 is full row rank.
Proposition J.2. If has full row rank (satisfying Condition 4.3). then rank invariance (Condi- tion 4.7 holds and the target linear system is universally consistent.
J.1.1 Proof of Proposition J.2
Proof. Since & is full row rank, know that Rank (Φ) and
Col Rd
therefore, Col (P= S Col (T). By Lemma J.3 we know that Col (P=Φ) S Col (Φ) implies
Rank (Ecov) Rank (Feov Eer)
Hence, the proof is complete.
We expect that this will be corrected in the arXiv version of the paper. (Personal communication with Che al., October 2025)
62

---

Lemma J.3. Col (P, (P, S Col (+), then
Rank (Zcov) Rank (Zeov - -Drr)
However, the converse does not necessarily hold.
Proof. First, assuming Col (P, 4) _ Col (+), by Lemma J.4 we know that
Col ( ( = Col ( x)
holds. Then by Lemma J.5 we know that
Col (Di Col (D -
Subsequently, by Lemma
C.1 we know that Rank (1 DDL - yP, )2) Rank (Φ) if and only if
Ker (DTD=) n Col (D&(1 - ~
Next, since we have
Col ( Col
Col (D+$) Row ( (DTD*) 1 Ker ( (#T
we know Ker
Di nol (D: - -P {0}. therefore.
Rank ( D(1 px)) ))) = Rank (4)
Second, we will show that Rank (Eemr) Col (P S Col (+) by demonstrating that
Rank (Eom Derr does not necessarily imply
Ker ( nCol (T
{0)
does not necessarily imply Col (P, +) C Col (b). This follows from Lemma C.1 which estab- lishes the equivalence between Ker + D n Col (D& - -p)) = {0} and Rank (Ecoo) =
Rank (Ecor - -er).
Assuming that Ker ( D n Col (D (I-
{0} does imply Col (P, C Col (Φ).
When T D doesn't have full column rank:
Ker ② T # {0).
From Lemma J.4 we know Ker DE Col (D - pPx) = {0} implics
Col Col 7P,,
which is equal to Col ( Col (D& - >P=} by Lemma J.5
Since
Row (TTD=) Col (D
we deduce that Ker (D n Col (D& -P,)) = {0} and only
Row ( TD Col (D (I PP)
which means among all subspaces whose dimension equal to dim RRo @ D! TD! )):
Row DD!
is only subspace for which
Ker (DD))) Row ( = (0).
63

---

However, as Ker TD) Therefore, we conclude that
* {0}, we know this is impossible contradicted by Lemma J.6
Ker
D n Col
{0)
does not necessarily imply Col (P [ Col (+).
Lemma J.4. ( = Col ( ,, if and only if Col (, S Co)
Proof. First, assuming Col (o) Col (4p >P know that there must exist matrix C Roxd such that
4C (I >>Pp>>
which is equal to - C). Therefore, the following must hold:
Col (-P bb S Col (
Next, assuming Col (?P, C Col (.), then we know that there must exist a matrix C E Rxx such that &C = >P and therefore,
(I PP=) + +C Φ(T C)2 which implies Col ((T (II~~Pa C Col (.). Subsequently, as (7 - >p=) is full rank and
(163)
Rank ((1 PPP )) = Rank (Ø),
we can get:
Col ((I (P))))))))) Col (+).
From above we know that
Col ( = Col (Φ- PP + Col Col (,P, S CD).
Then, as Col () Col p.) we have
Col (b) Col P) + Col (P, b) S Col (Ø).
Lemma J.5. Given two matrices A E Raxm and B E Raxm and a full rank matrix X E Ruxx if
Col Col (XB),
then
Col (A) Col (B),
and vice versa.
Proof. If Col (XA) Col (XB), then there must exist two matrices V, W E Rmxm such that
XAV XB, XBW = XA.
Since X is invertible, naturally, have:
AV = B, BW A,
which implics respectively: Col S Col (B) and Col (A) 2 Col (B). Therefore, we can conclude that Col (A) Col (B).
Next, Assuming Col (A) Col (B), then there must exist two matrices V, W E mm such that
AV = B, BW = A
then for any full rank matrix X E R
XAV = XB, XBW XA
which implies respectively: Col (XA) C Col (X and Col (X A) 2 Col (XB). therefore, conclude that Col (X A) = Col (XB).
Finally, the proof is complete.
64

---

Lemma J.6. Given any matrix A E Ruxm that Ker (A) + {0), there must exist subspace W that dim (W) Rank (A), W * Row (A) and Ker (A) W = {0).
Proof. Assuming Rank (A) = r and Row (A) = {ui, "0,,... , where in ... or are r linearly inde- pendent vectors which are the basis of Row (A). Since Ker (A) # {0}. define nonzero vector E Ker (A), and subspace
W {(u) + u), , (2, + u)}-
Since Vi {1.... ,r,, 1 Us. we know that vectors (v1 + u) , + u) are also linearly independent and
{(11 + u), .M (v+ + u}} Ker (A) {0)
so dim (W) = dim (A). Subsequently, we know
W + (ui, .. ,r) = Row (A),
e.g. 01 E Row (A) and v1 4 W. Hence, the proof is complete.
J.2 Over-parameterized FQI
Linearly independent state-action representation In the over-parameterized setting (h < d). when each distinct state-action pair is represented by linearly independent features vectors (Con- dition D.I. from Proposition J.2 we know that the target linear system is universally consistent. Furthermore, we can prove that (y (y Eer) < 1 (see Appendix J.2.1 for details). Consequently, by Corollary [5.3] FQI is guaranteed converge from any initial point in this setting. And in such setting, the FQI update equation can be simplified as: 0u41 7 P, P. + Φ R (detailed derivation in Lemma A.19
Linearly dependent state-action representation However, if we relax the assumption of linearly independent state-action feature representation (Condition J.I in the same over-parameterized setting (h d), the previous conclusion longer necessarily holds. In this case, FQI is not guaranteed to retain the favorable properties established above for the case of linearly independent state-action feature representation. Consequently, its convergence
necessarily guaranteed, but all results (e.g., Theorem 5.1 that did not assume any specific parameterization remain valid.
J.2.1 Why (rE Eer) <1
First, as we know when full row rank, ytt Eer >ppP, ,, and by Lemma E.18 we know that (fotP_0) 10)= (7001P, MO). Additionally, .. = >P, full row rank, and p (xPx) < 1. Therefore, p (y Der) = p (y0tP, +) = p (>P 1.
J.3 Over-parameterized PFQI
ever-parameterized PFQI with linearly independent state action feature vectors Corollary J.7 reveals the necessary and sufficient condition for the convergence of PFQI when each state-action pair be represented by distinct linearly independent features vector (Condition [.] is satisfied). In this setting, its preconditioner MPPoQ a Ei= (1 a.cov)* is not upper bounded indicating that MPFoI will diverge with increasing t. However, MPFQL remains upper bounded as increases. This because the divergence MPFQQ caused by the redundancy of features rather than the lack of features, and the divergent components in MproI that grow with & are effectively canceled out when Mproi is multiplied by ALSTD. For more mathematical details on this process, please see Appendix 1.3.1 Leveraging this result, in Proposition [.. we prove that under this setting, updates are performed for a sufficiently large number of iterations toward each target value, the convergence of PFQI is guaranteed. Che et al. [I] Proposition 3.3] previously proved the same result Proposition [.8 using a different proof path. does not guarantee PFQI's 'ss convergence in all practical batch settings, even for sufficiently large I. A detailed explanation is provided in our batch setting Section(Appendit K.
increases,
worth noting, however, that this proposition
Corollary J.7. When t is full row rank (Condition J.7 is satisfied) and a (1 = PFQ converges for any initial point Og and only if p ((Forr = =1 where the X = 1 is only eigenvalue
65

---

the unit circle. It converges to
1-1
1-1
Σ (I - (Ccoo)(( - (Fer)
Σ
(I aCcoo)(0ps
(164)
1m0
1=0
1-1
[-1
+
I
Σ 20000) - ->Eerr)
( - g2 Σ (I
80
(165)
1i-0
1LSTD-
(166)
Proposition J.8. When & is full row rank and d >> h, for any learning rate a E (0, must exist big enough finite T such that for any t T, Partial FQI converges for any initial point 0g.
p( there
Over-parannn parameterieed PFQI without linearly independent state-action feature vectors In this over over-parannn parameettttee setting, our previous results that assumed & be full row rank no longer apply. However, all results (e.g.. Theorem 5.1 that do not rely on any specific parameterization remain valid.
J.3.1
Why the divergent part in Mrror can be canceled out when + is full row rank
As we know from Appendix F.3.1 when t is not full column rank, Myror = a E a Dco ) will diverge increases. However, when & is full row rank (which also includes the case where T not full column rank), (MPFOo-A.STD)) becomes:
Σ [I - aCooo) (Ecov -pEer)
a [T
De)) Φ T - PP))
(167)
1=0
==
a
aDD D(I - ~Px)
(168)
In Equation 167
(I- is singular positive semidefinite matrix. From Appendix F.3.1
we know that Ker (DD) * (0). so / a& T D there are components that cannot be reduced by adjusting (see the mathematical derivation in Appendix F..II. These components will accumulate as increases, causing MpFor to diverge. However, when T is full row rank and MpFQr is multiplied with ALSTD, $ D& can be transformed as (DΦΦT) as shown Equation (168), which a nonsingular matrix. Thus, Ker (D$pTT = (0), meaning that by adjusting a we can always control p (I - aD$4T) < 1. This also indicates that the previously divergent components are canceled out by ALSID-
J.3.2 Proof of Corollary
J.7
Proof. When h > d and Φ is full row rank, we know that Ecor and (Ecov - -Eer are singular matrices and the PFQI update is:
[-1 [u- aEcoo) (Ecoo yEerr A +
1-1 aEooo)
Bx+1
(r-
I
2=0
1=0
From Proposition J.2 we know that PFQI converges for any initial point 0g if and only if
we know the target linear system is universal consistent, then by Theorem 7.1
1
Σ
aDon)) (Ccov 2ier)
1=0
is semiconvergent. Since
1-1
a Σ
a
'Soon Fior)
1=0
66

---

is singular matrix, by Lemma A.1 we know that
1 1- E (1- aZoo) (Ecov - Moor)) 1=0
must have eigenvalue equal to Therefore, by definition of semiconvergent matrix Definition A.7 we know that PFQI converges for any initial point 0g if and only if
(1-a E aEcon) (Ecov >Eer) 1,
p
=
where the À = 1 is only eigenvalue on the unit circle and is semisimple. Next, from Lemma J.9 we
know Index a Ei aCooo)' (Eeor - -gZcr) = 1, so we have
D
t-1
1-1
Σ
I - ccoo) (Ecor - -I =
Σ (I
(Ecov - 3Eorr) acoo)
a
a
1=0
1=0
Then, by Lemma E.24 and Lemma A.
we can get:
t-1
A=leo
1-a
Σ a (Zeor - )2ier) is semisimple.
Therefore, we can conclude that when h > and & is full row rank and (aocov) n {1,2] PFQI converges for any initial point fg if and only if
(1-a
t-1 E aCco))
p
L (Ecov >Dtrr) = 1,
==0
where the À = only eigenvalue on the unit circle. By Theorem 7.1 converges to
Σ
(169)
(--
#
1
a'ooo) 72ier))
Σ (1 aLiov) (LCcoo)(Eooo 720rr)
Go
(170)
E OLSID-
(171)
Lemma J.9. When h > & is full row rank and (alioo) n {1, @ and & is full row rank.
then
Index
Σ (T
-. (Eeov yEer) = 1.
1=0
Proof. First, we have
[-1
a [I
a (Eeov - --ies)
=a
ab
D D - )P (172)
1=0
1=0
[-1 (I I
= aΦb
(I-DD00 D(I - >Px)
(173)
1=0
As we know that a. D& is singular matrix, aDoT is nonsingular matrix and a (a Deb n
{1, 2) 0. By Lemma E. we can obtain that
(a D (0) (aDo4 )
67

---

which implies a (aD04 n [1,2] = 0. By Lemma J.10 we know
Σ - aDob")'
1=0
a full rank matrix, and subsequently,
- (u-aDooTyD(1190
1=0
is a full rank matrix. Together with o being full column rank matrix, we know that
(I ---ald oDo (T((()))(P))))))))) -P=)
is nonsingular matrix. Therefore, by Lemma E.19 know that:
Index
a&
D(I - Px,) p
=1.
==
Hence, Index (a (a aLCoo)) (Ccor - -Zirr) = 1.
Lemma J.10. Given a nonsingular matrix E Raxn, ifa (A) (1,2) 0, Ei=o (T A)) nonsingular for any positive integer I.
Proof. Given nonsingular matrix R"**, assuming (4) n {1,2] by Lemma A.1 we know a (I - A) n (0, 1,2] = 0. Next, we define the Jordan form of A as
QAQ = J,
where J is full rank upper triangular matrix with nonzero diagonal entries. By Lemma A.1 we know the Jordan form of full rank matrix (T A) is:
QT =
where (I - )) is also a full rank upper triangular matrix with no diagonal entries equal to 0, and -1. Therefore, Vi N, (1 - J)' is an full rank upper triangular matrix with no diagonal entries equal to O and 1, so vi E N, [1 - J)') is nonsingular. Moreover, by Fact G.6 we know that:
Σ (1 - = - Lu
(1 J) J'Q
1=0
0=0
Since Q, (1 -I , are all nonsingular, Ei (1 - A)* is nonsingular.
J.3.3 Proof of Proposition J.8
Proposition J.11 (Restatement of Proposition J.8]. When full row rank and > h, for any learning rate (0, p(Dece)) there must exist big enough finite T for any >> T, such that PFQI converges for any initial point 0g.
Proof.
H-1 II acou)) (Ecor - -Errr)
(174)
a D&)' & TDI - )
(175)
1=0
t-1
Σ aD D(1 7Px)
(176)
T (I - [1 aDo T)²) (Do0 T) 1 - )Px))
(177)
T T [I- DD$ y)) (Φ. T) -1 PP
(178)
68

---

By Lemma E.18 we know that:
o ② (T - (I-aD 1/) (++)) )- - )P=) 110)
(179)
a ($4) T ---(I=DD0T]] (00 pP,))
(180)
then by Lemma A.1 we know that
(I ob T (I (I a[-DDo ( -00
(181)
o (I 44 T (I- ( -P u (1),
(182)
and we get that
I- T (I- (--(-- aDD4 )) (0$ 1 -P-
(183)
=, x + 2b (O aDD4 (0 ) )
7Px))
(184)
Since p a 1) < 1im (T oDD ) then
lim 1-00
[yPx + ΦΦ (T aD$$ T
P
As we know that p at) < I, then by the theorem of continuity of cigenvalues (2 Theorem 5.1]. we can know that there must finite positive integer T that for any > T,
p p + ΦT T (T aD ((
)
P=)) <1
In that case, we know that
YA
aDb (0 ( PP ))) ||| <1
Therefore, p (I (I- TT (I- (I- aD )²) (0o -I[ PP }b) = 1, and eigenvalue À = 1 is
only eigenvalue the unit circle. By Lemma 0.9 and Lemma E.24 we know that = 1 is also semisimple. By Definition A.7 we know that
(T (T- (I
aD4. )²) (Φ (TbT)~-((1 -1-)),)) is semiconvergent.
Additionally, Proposition shows that Par Col (Fom ) naturally holds when $ is full row rank. By Theorem 7.1 we know that PFQI converges for any initial point 0g-
J.4 Over-parameteriice TD
The results on TD in peeemeaaeeter setting are presented in Appendix E.6
K
Batch case
Offline policy evaluation is a special but realistic case of the policy evaluation task, where sampling from the environment is not possible. Instead, a collected batch dataset {(s,, a,, r2 (s,,a,) }))); comprising ń samples, is provided. Therefore, this is also referred to batch setting. In this dataset, we define (8i, ai) as the initial state-action, sampled from some arbitrary distribution D. The reward is represented as (8s; 04) = R (si,a;), and the next state is sampled from the transition model, o/ ~ (. 8;, a.). Since the next action is sampled according to π,, aç ~ (sf), we can express the dataset as {(si, di, Ti (st, (e,,a). 8/1 d xm for clarity of presentation. We refer (5/, a) as the next state-action. Here, the sample number n 2 ñ, since usually multiple actions at a single state have nonzero probability of being sampled.
Let m denote the total number of distinct state-action pairs that appear either as initial state-action pairs or next state-action pairs in the dataset. Let na(s, a) > [[; s, a, a) represent the number of times the state-action pair (s, a) appears as the initial state-action pair in the dataset. For a state-action pair (s, a) that appears as initial state-action pair, we define fi(s, a) n(s, a)/n. For state-action pairs (s, a) that appear only as next state-action pairs and not as initial state-action pairs, we set (s, a) 0. Thus, Ā E Rm is the vector of empirical sample distributions for all state-action pairs in the dataset. Next, $ E Remxd is the empirical feature matrix, where each row corresponds to feature vector o(s, a) for state-action pair (s, a) in the dataset.
69

---

The empirical counterparts of the covariance matrix Lcov. cross-variance matrix Eer, and feature- reward vector a. as defined are given by:
Dcoo
e (st, ai) ( (s), = = De,
Σ
Φ ()) = =
(185)
i=1
n
0
Φ (s) a:) = DR. Σ n
Here, we define the empirical distribution matrix D = diag (ā) diagonal matrix whose diagonal
entries correspond to the empirical distribution of the state-action pairs. Similarly, R _ is the vector rewards for all state-action pairs the dataset 20 The empirical transition matrix between state-action pairs, Px E xl is defined as:
(s', (, 1==1 [s 8, a a 8
8 d. d!
n(s a)
for state-action pairs (s, a)) that appear initial state-action pairs, and Pa (5', a' s, 0 for state-action pairs that only appear as next state-action pairs but not as initial state-action pairs. As result, P is a sub-stochastic matrix.
It worth noting that for state-action pairs that appear in the dataset only as next state-action pairs but not as initial state-action pairs, we do remove their corresponding entries from & when defining Ecor. Egr, and o in Equation 185). Including these state-action pairs does not affeet generality, their interactions with other components are effectively canceled out. For example, in E.ev 3 DΦ, their feature vectors in & are nullified by D, since their observed sampling probabilities are zero. However, retaining these entries facilitates analysis. For instance, it ensures that we can model the empirical transition matrix P x as sub-stochastic square matrix, which has desirable properties, such as P
< 1, rather than as rectangular matrix.
FQI in the batch setting Given the datset {(s,, a,, ri (s, o.) s af) with linear function approximation, every iteration, the update of FQI involves iterative solving least squares regression problem. The update equation is:
0x+1 arg min Σ (8). 0 r (82, - (s), 0.)
(186)
Eer + Stt Stow 0s.
(187)
Batch TD In the batch setting/ offline policy evaluation setting, TD uses the entire dataset instead of stochastic samples to update:
Oct1 = 0g -
Vo, (s. (s0,,,) 14 (8,,
(188)
02 a n
Σ
[db(s,a) a) (b(s,a)TT 7 r(s, a))]
(189)
= 0 - a [Eeorr Eer) 8x 8g.r]
(190)
For state-action pairs whose rewards not observed, we set their rewards to 0.
70

---

K.1 Extension of FQI convergence results to the batch setting
By replacing @, D, xx. Leous Ler, and 6 with their empirical counterparts 4 D. P.. Ecov. Eer, and 0s. respectively, we can extend the convergence results of expected FQI to Batch FQL. However, the conclusion in Appendix J.2 holds only when D is full-rank matrix, but D is not necessarily full rank, and FQI in the batch setting does not necessarily converge unless D is full-rank matrix (even in the parameterized setting where T has full row rank). Nevertheless, the batch version of Theorem 5.1 still implies necessary and sufficient condition convergence conditions under these circumstances.
K.2 Extension of TD convergence results to the batch setting
By replacing 4, D, Px. Ecors Eer and 2 with their empirical counterparts T D. P.. Eoons Eer and fg... respectively, we can extend the convergence results of expected TD to Batch 2D For example, Corollary [6.3] which identifies the specific learning rates that make expected TD converge, particularly useful for Batch TD. By replacing each matrix with its empirical counterpart, we can determine which learning rates will ensure Batch TD convergence and which will not.
K.3 Extension of PFQI results to the batch setting
By replacing 4, D, Ps. x. Eoor. Eer and 0 with their empirical counterparts क D. P. Eoors Eor and 0g.r. respectively, we can extend the convergence results expected PFQI to PFQI in the hatch setting, with exception: Proposition J.8 which relies upon D being nonsingular matrix, while D is not necessarily nonsingular anymore However, if D nonsingular, then Proposition J.8 can apply.
While the extension the on-policy setting is straightforward in principle, in practice when data sampled from the policy to be evaluated, is unlikely that üP, x will hold exactly.
71

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract captures most of the key contributions we believe are significant
in this paper. However, due the page limit of the main content, many other interesting results could not be included, for example, content in Appendix H
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We point out the limitations in the Preliminaries and Discussion section and outline potential directions for future.work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
72

---

Answer: [Yes]
Justification: Every theoretical result in the paper clearly states its assumptions and is accompanied by proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: This paper is highly theoretical, addressing questions through mathematical analysis rather than empirical evaluation, and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
73

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This paper is highly theoretical, addressing questions through mathematical analysis rather than empirical evaluation, and does not include data and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/tips.cc/ppbliic wwtppbblcggguiiieecceeeeeeooeeee http:/gddese/eee/ SooodeSummissiooPP...
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This paper highly theoretical, addressing questions through mathematical analysis rather than empirical evaluation, and does not have training and test details to specify.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper highly theoretical, addressing questions through mathematical analysis rather than empirical evaluation, and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
74

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper highly theoretical, addressing questions through mathematical analysis rather than empirical evaluation, and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://eurrppss.ccccm /ttpe///////c/tttttttitiiiiiiia
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on providing mathematical analysis and theoretical ground- ing for existing methods, and does not perform direct societal impact.
Guidelines:
75

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: this paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: this paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
76

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: this paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: this paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
77

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpps////eurpss.... /ctp:////oeeeeeccs///2///////// for what should or should be described.
78


Reviews:
[{"review_id": "NZ9uaacOSu", "reviewer": "Reviewer_iyii", "summary": "This paper studies the off-policy policy evaluation (OPE) problem with linear function approximation. The authors study the TD, FQI, and Partial FQI (PFQI) algorithms and establish that they can be viewed as solving the same \"target\" linear system but with varying choices of splitting schemes and preconditioners. The authors study this \"target\" linear system and establish necessary and sufficient conditions for the existence and uniqueness of a solution. The authors study the convergence of TD, FQI, and PFQI and establish necessary and sufficient conditions for each of these, with connections to each other, and elucidate why convergence of TD and FQI do not necessarily imply convergence of each other.", "questions": "The convergence guarantees can be clarified a bit: e.g. how do the solutions $(A_{FQI})^D b_{FQI} + (I - A_{FQI}(A_{FQI})^D)\\theta_0$ and  $A_{LSTD}^Db_{LSTD} + (I - (A_{LSTD})(A_{LSTD})^D)\\theta_0$ of Theorem 6.1 relate to the desired solution (e.g. assuming realizability, how does it relate to $\\theta^\\star$?)", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This is a very solid paper which in my view should clearly be accepted to the conference. The results are not extremely technical in hindsight (all the proofs boil down to linear algebra) but impactful for understanding these fundamental algorithms and providing definitive convergence conditions and relations between them. Despite their simplicity, many of these results have been previously documented as far as I am aware. \n\nI have some minor complaints:\n- Typos: there are many typos and spacing issues throughout (especially in the appendix but even in the main text). Please review. \n- Clarity: There are some undefined terminology and notation especially when it comes to linear algebra. E.g. in Section 5 and 6: what is a semiconvergent matrix and what is the notation (A)^D? What is a proper splitting, and what are the implications of it (why should I care about Lemma 5.2)? What is the drazin (group) inverse? Bringing some of these concepts which are necessary for interpreting the results out of the appendix and into the main text would improve interpretability.\n- Missing discussion of related work: the condition that $\\rho(\\gamma \\Sigma_{cov}^\\dagger \\Sigma_{cr}) < 1$ is necessary and sufficient for FQI convergence has been noted in Perdomo et al. (reference [30] of this paper), and the condition that nonsingularity of $A_{LSTD}$ is necessary and sufficient for OPE has been noted in Mou, Pananjady, Wainwright (https://arxiv.org/abs/2012.05299), Amortila, Jiang, Xie (https://arxiv.org/abs/2011.01075) and Amortila, Jiang, Szepesvari (https://arxiv.org/abs/2307.13332).", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you so much for taking the time to thoroughly review our paper and for recognizing its contributions—we truly appreciate your thoughtful feedback.**\n\n**In response to your minor concerns:**\n\n**Regarding the typos:**  \nThank you for pointing this out. We will carefully review the manuscript and make sure to correct any such issues.\n\n**Regarding clarity:**  \nThe 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.\n\n**Regarding the missing discussion of related work you kindly pointed out:**  \nThank you very much for bringing these papers to our attention.  \nPerdomo 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\n\n$$\n\\theta_T = \\sum_{k=0}^T \\left(\\gamma \\Sigma_{\\mathrm{cov}}^{-1} \\Sigma_{\\mathrm{cr}}\\right)^k \\Sigma_{\\mathrm{cov}}^{-1} \\theta_{\\phi, r}\n$$\n\nconverges 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.  \n\nAs 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$.\n\nWe 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\n\n$$\nX_{t+1} = \\sum_{i=0}^{t} A^i B + A^{t+1} X_0\n$$\n\nderived 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.\n\n**Regarding your mention of three papers stating that $A_{\\text{LSTD}}$ being nonsingular is necessary and sufficient for OPE:**  \nWe 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.\n\nIf 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.\n\n**To answer your question:**  \nThank 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).\n\nIn 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$.\n\nWe hope this fully addresses your question, and we’d be happy to clarify further if needed!\n\n***We are grateful for your insights and thank you again for your valuable comments.***"}, {"review_id": "7p0w1IABxl", "reviewer": "Reviewer_KHfd", "summary": "This paper offers a unified perspective on reinforcement-learning algorithms, Temporal Difference (TD), Fitted Q-Iteration (FQI), and Partially Fitted Q-Iteration (PFQI), by viewing them as matrix-splitting schemes equipped with preconditioners. In the off-policy evaluation setting, the authors derive a single iterative update based on the state–action covariance and cross-covariance matrices, with TD, FQI, and PFQI emerging as special cases. Within this framework they introduce rank invariance, a condition that is both necessary and sufficient for the consistency of the target linear system. Rank invariance ensures existence and uniqueness of the solution and, in turn, leads to characterization of convergence conditions for the three algorithms.", "questions": "Because linear problems have been widely studied in many contexts, I’m somewhat concerned about the novelty of this paper related to rank invariance condition. In Appendix Section I, the authors discuss the convergence conditions used in earlier work. As I understand it, the linear-independence condition has already been addressed in prior studies, whereas the rank-invariance condition has not been clearly articulated. Is this interpretation correct? If not, could you clarify?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\nThe paper’s main contribution is to clarify the role of rank invariance, a necessary and sufficient condition for the underlying linear system, and to distinguish it from simple linear independence condition. Leveraging this property, this work rigorously analyzes TD, FQI, and PFQI, yielding results that are both necessary and meaningful to the reinforcement learning theory literature.\n\nWeaknesses:\nThe theoretical guarantees do not extend to policy control settings (nonlinear problems), and the paper does not verify its claims with empirical experiments.", "was_revised": true, "final_justification": "I am satisfied with the response and have no unresolved issues. As noted in my original review, since the paper’s strengths slightly outweigh its weaknesses, I will maintain my score.", "rebuttal": "Thank you very much for your thoughtful question.\n\nFirst, 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.\n\nMore 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.\n\n---\n\n### Response regarding the linear independence assumption and rank invariance\n\nWe 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.\nWe 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.\n\nIn 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.\n\nMost 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.\n\nWe 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:\n- Ensuring the **existence of fixed points** (Proposition 4.2), and\n- Influencing the **convergence behavior of TD, PFQI, and FQI**, as elaborated in the respective sections of the paper.\n\n---\n\nIn 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.\n- **Unifying Perspective on TD, PFQI, and FQI:**\n  - 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.\n\n- **Matrix Preconditioning Interpretation:**\n  - Interprets TD as using a constant preconditioner, FQI as using a data-feature adaptive preconditioner (inverse feature covariance), and PFQI as interpolating between them.\n  - Demonstrates that increasing the number of updates under a fixed target value function corresponds to transitioning from a constant to an adaptive preconditioner.\n\n- **Clarification of Convergence Conditions:**\n  - Provides necessary and sufficient convergence conditions for TD, PFQI, and FQI under linear function approximation, without making any assumptions about the chosen features\n  - Identifies limitations of commonly used assumptions in prior literature.\n\n- **Introduction of the *Rank Invariance* Condition:**\n  - 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.\n  - Highlights the distinction between rank invariance and linear independence.\n  - Shows that when rank invariance holds, FQI is an iterative algorithm that uses the proper splitting scheme to formulate its iterative components and preconditioner.\n  - Demonstrates that rank invariance widely exists in practice and is guaranteed to hold in the on-policy setting.\n\n- **Conditions for Uniqueness of Solutions:**\n  - Proves that the target linear system has a unique solution if and only if both rank invariance and linear independence hold.\n\n- **Encoder-Decoder View of TD:**\n  - Introduces an encoder-decoder interpretation of TD's convergence condition, clarifying why TD may diverge even under overparameterization.\n\n- **Analysis of On-Policy and Off-Policy Settings:**\n  - Shows that rank invariance always holds in the on-policy setting, guaranteeing the existence of a fixed point.\n  - Extends on-policy TD convergence guarantees to cases without linearly independent features, showing that this common assumption can be dropped.\n\n- **New Insights into Learning Rates:**\n  - Demonstrates that when a learning rate ensures TD convergence, then all smaller learning rates will also ensure convergence.\n  - Provides guidance where to choose learning rate to make batch TD converge when it can converge\n\n- **Convergence Relationships Among TD, PFQI, and FQI:**\n  - Provides formal implications (and counterexamples) regarding convergence dependencies between TD, PFQI, and FQI.\n  - 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.\n\n- **Relevance to Deep RL and Nonlinear Function Approximation:**\n  - Extends insights to neural networks by noting that final linear layers justify applying results beyond the assumption of feature linear independence.\n\n\n\n---\n\n### Response to the comment on the Weaknesses\nWe 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.\n\nWith respect to the reviewer’s comment on the absence of empirical experiments to support our claims,\nWe 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.\n\n**Thank you again for your thoughtful and constructive feedback—it has been invaluable in improving our work**"}, {"review_id": "WqUhgaBJfY", "reviewer": "Reviewer_Fdq8", "summary": "The paper provides an analysis of the relationship between temporal different (TD), partially fitted Q iteration (PFQI) and fitted Q iteration (FQI) in the linear function approximation setting. The authors formulate the problem as solving a preconditioned linear system, with TD PFQI and FQI all  and uses this to analyse the stability and convergence", "questions": "Before the paper is published ANYWHERE, the authors need to do a better job of CAREFULLY ACKNOWLEDGING related worked instead of presenting their theorems as corrections, clarifications or novelties and claiming existing work is misleading. \n\nEven with this essential correction, I'm not sure the paper contributes enough. A true unified view would have to account for nonlinearity, stochasticity and non-finite MDPs, as these have been tackled before and better represent the reality of where TD algorithms are actually used. I can't raise my score until this is the case. \n\nAnother approach would be to re-write the paper as a review and correction paper. Here previous results and conclusions from existing papers could be carefully collated (acknowledging contribution and similarities between works, corrected if necessary) and expanded upon for certain cases (like in the linear, expected finite case here). I'm not sure this would be a significant enough contribution on its own, but would leave that to the AC to decide.", "limitations": "The authors present many analyses for which identical or similar results have been found before without proper acknowledgement and in a much more restrictive setting. This significantly limits the paper's contribution and claims of a unified framework for analysing off policy RL.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "STRENGTHS:\n\nThe paper is mathematically rigorous and well written. It clearly introduces notation and carefully analyses each algorithm systematically. One of the better parts of the paper is the correction of previous mistakes in SOME of the related work. A main contribution is the formulation of the problem as a preconditioned linear system. The paper then goes through analysing each of TD, PFQI and FQI, providing sufficient and necessary conditions for convergence of each. The discussion around each theoretical result is intuitive and offers nice insights. The paper also generalises analysis for when the Hessian is singular by analysing the Moore-Penrose pseudo-inverse. \n\nWEAKNESSES:\n\nThis paper seems very similar to [1] in terms of its goals and I'm not sure it offers a significant enough contribution beyond this. \n\nNOT AS GENERAL AS OTHER WORKS: The paper is limited to linear function approximation for finite state-action MDPs in the expected TD setting, whereas papers like [1] study general nonlinear smooth stochastic TD methods in general state-action MDPs. This is especially important in TD and related methods where nonlinearity is not only commonplace, but is a major source of instability itself, and so not accounting for this weakens the power of the analysis.\n\nMANY RESULTS ARE RE-FORMULATIONS OF KNOWN RESULTS: \n\nMany results can be recovered from [1] by noting that the following matrices are equivalent under the authors' notation for the special case of a linear function approximator: $ A_\\textrm{LSTD} = J_\\textrm{TD}(\\omega,\\omega^\\star )$,  $ \\Sigma_\\textrm{cov} = H(\\omega,\\omega^\\star;\\omega_l )$  and $\\gamma \\Sigma_\\textrm{cr} = J_\\delta(\\omega,\\omega^\\star;\\omega_l )$.\n\nIn particular: \n\nThe update equation on line 140 is the same as Lemma 3 in [1]\n\nEq. 6 is simply the TD fixed point equation, which has been characterised many times before. \n\nAnalysis of FQI\n\nTheorem  5.1 draws the same conclusions as Theorem 1 from [1] where convergence of FQI is governed by the convergence to zero of $\\prod_{i=0}^{l-1} H(\\omega_{i+1}^\\star,\\omega^\\star;\\omega_i^\\star )^{-1} J_\\delta(\\omega_i,\\omega^\\star;\\omega^\\star ) $, which reduces down EXACTLY to the convergence of  $(H_\\textrm{FQI})^l=(\\gamma \\Sigma_\\textrm{cov}^{-1}\\Sigma_\\textrm{cr})^l $ in the linear case, thereby recovering the same result. The only slight generalisation in the authors' work is the use of the Moore-Penrose Pseudo inverse, however beyond this the result is not as general as [1] as it does not allow for nonlinear function approximation and general state-action spaces. Indeed, this motivated Assumption 5 in [1], which guarantees stability of FQI using the max  2-norm of  $H(\\omega_{i+1}^\\star,\\omega^\\star;\\omega_i^\\star )^{-1} J_\\delta(\\omega_i,\\omega^\\star;\\omega^\\star )$. \n\nAnalysis of TD\n\nIn theorem 6.1, the conclusion that $H_\\textrm{TD}$ must be semiconvergent has been characterised in many ways before [1] [2]. When considering the conditions needed for the spectral norm to be less than 1 (as the authors identify), this recovers the famous deadly triad of TD [1].\n\nAnalysis of PFQI\n\nThe analysis of PFQI and connection to TD and FQI relies on the preconditioning formulation in Eq. 8. This has been characterised in [1] by the condition function in Eq. 7 $C(\\alpha,k)$. The reason for the condition function in [1] is that under the more general nonlinear analysis, an analytic matrix equation does not exist, and so it acts as an upper bound in terms of max eigenvalues to account for the nonlinearity, but plays the same role in analysis and leads the the same conclusions: \n\nTheorem 7.1 draws the conclusion that convergence relies on $H_\\textrm{PFQI}$ being semi-convergent. In the more general nonlinear  stochastic setting of [1], the same conclusions can be drawn from Theorem 3 if $C(\\alpha,k)<1$, showing convergence to a ball due to stochasticity. $C(\\alpha,k)<1$ is a slightly more strict assumption, however this is needed due to the upper bounding because of nonlinearity, but implies $H_\\textrm{PFQI}$ being semi-convergent in the linear case. \n\nResults in Theorem 8.1 have been shown in [1] under an aysmptotic analysis: the authors of [1] show that convergence of PFQI stems from convergence of TD under the diminishing stepsize regime in Theorem 2, implying there exist a sequence of stepsizes such that PFQI always converges if TD converges. \n\nIn Theorem 8.3, the learning rate conditions for convergence given by the authors are the same as those in [1]: observe that the condition function $C(\\alpha,k)$ converges for the same learning rate interval $(0,\\frac{2}{ \\lambda^\\star_H})$ giving convergence of PFQI from FQI (Property 3 of [1]). These results are completely analogous to the convergence of the precondition function converging, albeit for a nonlinear analysis. The proof that convergence of FQI implies convergence of PFQI for large enough $t$ recovers the same result of Theorem 4 of [1] for large enough $k$ using the preconditioning matrix instead of the condition function. \n\nFinally, the apparently novel conclusion that convergence of PFQI implies convergence of FQI, even when TD does not converge, is discussed extensively in Section 5.4 of [1] including a graphical representation of this property in Fig .1 \n\nSTRAWMANNING OF RELATED WORK:  \n\nIn my opinion, it is not acceptable that the authors claim novelty for the many of the main the results of the paper (Theorem 5.1, 6.1, 7.1 8.1 and 8.3) because, as I have shown above, they have been proved before. What is worse though is that the authors seem to suggest that ALL previous work is misleading or incorrect: \n\nLine 32: `The traditional perspective fails to fully capture the convergence connections between these algorithms and may lead to incorrect conclusions. For example, one might erroneously conclude that TD convergence necessarily implies FQI convergence.'\n\nI don't think any rational person would draw this conclusion from [1] as the connections that authors have made in this paper are also made clearly there. \n\nNOT A SIGNIFICANT ENOUGH CONTRIBUTION: \n\nIn light of this, the current paper and introduced unified view does not offer a substantial contribution. The contributions are a slight clarification of necessary and sufficient conditions, a compiling of existing results and a minor technical relaxation of some assumptions (i.e. no need for linearly independent features in the on policy case and relaxation of invertible Hessian) at the expense of introducing additional assumptions that are too restrictive to apply for most practical methods - in particular finite MDPs, linear function approximation and analysis only in the path mean case. \n\nLITTLE PRACTICAL BENEFIT:\n\nIn my opinion, the purported benefits of the introduced unified view and analysis have little practical benefit. Relaxing the assumption of an invertible Hessian makes little difference when a arbitrarily small amount of regularisation can easily satisfy the assumption. As mentioned before, the introduced stricter assumptions DO affect the ability to apply the analysis to real world algorithms.\n\nMinor weaknesses (These don't count towards my score)\n\nTypos: \n\nLine 7: solving same linear system, Line 18: help(for batch TD), Line 139: Target Network.When, Line 184: (Condition 4.1). it can Line 194: features(Condition 4.3)as, Line 196 features(Condition 4.3), Line 198 features(Condition 4.3) Line 236:  invariance(Condition 4.1), Line 238: he impact of of rank invariance, Line 242: the target linear system the solution of the FQI linear system Line 262: The fixed point it converge to Line 327: features(Condition 4.3)do Line 327: invariance(Condition 4.1),\n\nTitles seems to use a mixture of title case and non title case, sometimes in the same title\n\n[1] Fellows et al. Why Target Networks Stabilise Temporal Difference Methods, ICML 2023. https://arxiv.org/pdf/2302.12537v3\n\n[2] Tsitsiklis and Van Roy. An Analysis of Temporal-Difference Learning with Function Approximation, https://www.mit.edu/~jnt/Papers/J063-97-bvr-td.pdf", "was_revised": true, "final_justification": "I think my more major concerns have been addressed by the authors' rebuttal, however I do still believe the linear setting and the contribution  is somewhat limited given the results of prior work. My updated score reflects this.", "rebuttal": "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.\n\n\nOur 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.\n\n[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.\nOur 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.\n\nThe 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.\n\n[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]).\nIt 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).\n\n**Response to RE-FORMULATIONS OF KNOWN RESULTS** \nContrary 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.\n\n**Response to Analysis of FQI** \nThm. 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.\n\nYou 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).\n\n**Response to Analysis of TD** \n\n[2] is noted for its on-policy TD result. Our paper is in the off-policy setting, a much more general case. \nIn 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.\n\n[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.\n\nYour comment about our use of the spectral norm is puzzling because we never use any spectral norm.\n\n**Response to Analysis of  PFQI** \nEq. 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 \n$\\bar{J}_{T D}^{\\star}$ \nis \n\n$I-\\alpha\\left(\\Sigma_{c o v}-\\gamma \\Sigma_{c r}\\right)$\n. 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.\n\nAs 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.\n\nDifference 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.\nOn 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.\n\nFor 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}}$ \nwhere\n\n$$\n\\lambda_H^{\\star} := \\sup_{\\omega, \\omega', \\omega''} \\operatorname{argsup}_{\\lambda' \\in \\lambda\\left(\\bar{H}(\\omega, \\omega'; \\omega'')\\right)}  \\left|1 - \\alpha_l \\lambda'\\right|\n$$\n\n from [1] are obviously also dependent on learning rate $\\alpha_l$.\n\nThm. 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$.\n\nWe 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.\n\nResponse 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.\n\n***Response on NOT A SIGNIFICANT ENOUGH CONTRIBUTION***\nWe 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. \n\n***Response on LITTLE PRACTICAL BENEFIT***\nAs 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.\nWe 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."}, {"review_id": "KGCqEmEBUI", "reviewer": "Reviewer_991y", "summary": "This work analyzes the theoretical properties of policy evaluation algorithms in both the on- and off-policy settings. It characterizes the solutions of (expected) temporal difference update (TD), fitted Q iteration (FQI) and partial FQI (PFQI) using precise conditions (iff). The analysis is based on rank invariance (Condition 4.1). The paper then shows the convergence/stability properties of these methods based on rank invariance (Sec.5-7).", "questions": "For the cases of TD convergence versus FQI convergence, Appendix G.3 shows two counterexamples that one does not imply the other. However, it is not clear how these examples came to light or how they were specifically constructed. Further insights would be helpful. In addition, how likely are we going to see such cases in practice?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The theoretical analysis focuses on a key condition of rank invariance (Condition 4.1), which is complementary to the feature independence condition widely used in the literature. It unifies three algorithms’ updates from a pre-conditioning point of view of solving linear systems. It also theoretically characterizes the singularity and consistency of the LSTD system using the rank invariant condition.\n\n2. This new condition also offers new insights into the sufficient and necessary conditions for the convergence of the three algorithms with proper step sizes.\n\nWeaknesses\n\n1. A main concern is that the content in this work is very dense as a conference paper, and it seems that it would benefit from being a journal paper instead. This causes some problems such as notations not being clearly explained in the main text (e.g., $\\sigma$ and $\\mathfrak{R}$ in Corollary 6.3), and it has to constantly refer to the respective appendix sections for the complete discussion, which hurts the reading flow very much.\n\n2. Some writing can be more precise. For example, L147: \"Its solution is the same as the original linear system\" but this should depend on the choice of $M$ (at least not iff).\n\nMinor comments\n\n- The capitalization of section titles is inconsistent throughout the paper.\n- The space before the left brackets is inconsistent throughout the paper.\n- Matrix bolding is inconsistent throughout the paper (e.g., see Proposition 4.2). It seems that not bolding any matrices would be easier as there are many $A, \\Phi, \\Sigma$, etc.\n- $\\theta_{\\phi,r}$ not sure why we need to emphasize $\\phi$ here. Throughout the paper, it seems that all that matters is to show that this depends on $r$.\n- L106 misses transpose\n- L124 can refer to the equation below it instead of (23) in the appendix\n- L166 can refer to (8) instead of (67)\n- L238 of of, L240 $\\rho$ should be explained. Also, it seems that both $\\rho$ and $\\lambda$ are used in the paper for the same meaning.\n- Eq.(31) is empty, and it makes more sense to switch (30) and (29) since (30) is (28) in matrix form.\n- L736 uses $\\theta_t$, (33) uses $\\theta_k$ and (37) uses $\\theta_{k+1}$. Please make sure the indices are consistent (maybe $k+1$ is the most clear). Also in the main text (L137).", "was_revised": true, "final_justification": "The paper provides a different angle for analyzing temporal difference learning using rank invariance, which is valuable for the RL community. As a result, I tend to accept it.", "rebuttal": "Thank you very much for your thoughtful feedback. \n\n## Regarding the comment on weaknesses\n\nWe 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.\n\nDue 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.\n\n***Regarding the comment on writing precision:***\n\nThank 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.\n\nIn 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.\n\nThat said, we truly appreciate your close reading and will consider clarifying this further to avoid any possible ambiguity for readers.\n\n\n## To answer your question\n\nYou 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.\n\n***Thank you once again for your insightful review and for helping us strengthen the paper.***"}]

Author rebuttal:

Meta-review: Referees (and my own reading) agree that this paper is impactful in linear-approximation RL, and provides a novel understanding of the temporal-difference, fitted Q-iteration, and partially fitted Q-iteration methods. This is despite most of the analysis resulting from "basic" linear algebra -- which may in itself be seen as a strength of the paper.

Concerns on relation to related work already discussed, and to missing related work; as well as to the focus on the linear case whereas nonlinear is more widely used these days; are sufficiently addressed by the authors in the discussion with the referees. A key point here is the relation to [1] in Fdq8, which the authors resolve by stating they newly provide *necessary* and sufficient conditions.

Overall, my recommendation is positive given the paper, reviews, and discussion. Furthermore, since the paper elucidates important technical questions about widely used algorithms in a way that is relatively easy to follow, I further recommend classifying it as spotlight.
Decision: Accept (spotlight)