Year: 2021

Abstract:
The theory of function approximation in reinforcement learning (RL) typically considers low capacity representations that incur a tradeoff between approximation error, stability and generalization. Current deep architectures, however, operate in an overparameterized regime where approximation error is not necessarily a bottleneck. To better understand the utility of deep models in RL we present an analysis of recursive value estimation using overparameterized linear representations that provides useful, transferable findings. First, we show that classical updates such as temporal difference (TD) learning or fitted-value-iteration (FVI) converge to different fixed points than residual minimization (RM) in the overparameterized linear case. We then develop a unified interpretation of overparameterized linear value estimation as minimizing the Euclidean norm of the weights subject to alternative constraints. A practical consequence is that RM can be modified by a simple alteration of the backup targets to obtain the same fixed points as FVI and TD (when they converge), while universally ensuring stability. Further, we provide an analysis of the generalization error of these methods, demonstrating per iterate bounds on the value prediction error of FVI, and fixed point bounds for TD and RM. Given this understanding, we then develop new algorithmic tools for improving recursive value estimation with deep models. In particular, we extract two regularizers that penalize out-of-span top-layer weights and co-linearity in top-layer features respectively. Empirically we find that these regularizers dramatically improve the stability of TD and FVI, while allowing RM to match and even sometimes surpass their generalization performance with assured stability.

text: The theory of function approximation in reinforcement learning (RL) typically considers low capacity representations that incur a tradeoff between approximation error, stability and generalization. Current deep architectures, however, operate in an overparameterized regime where approximation error is not necessarily a bottleneck. To better understand the utility of deep models in RL we present an analysis of recursive value estimation using overparameterized linear representations that provides useful, transferable findings. First, we show that classical updates such as temporal difference (TD) learning or fitted-value-iteration (FVI) converge to different fixed points than residual minimization (RM) in the overparameterized linear case. We then develop a unified interpretation of overparameterized linear value estimation as minimizing the Euclidean norm of the weights subject to alternative constraints. A practical consequence is that RM can be modified by a simple alteration of the backup targets to obtain the same fixed points as FVI and TD (when they converge), while universally ensuring stability. Further, we provide an analysis of the generalization error of these methods, demonstrating per iterate bounds on the value prediction error of FVI, and fixed point bounds for TD and RM. Given this understanding, we then develop new algorithmic tools for improving recursive value estimation with deep models. In particular, we extract two regularizers that penalize out-of-span top-layer weights and co-linearity in top-layer features respectively. Empirically we find that these regularizers dramatically improve the stability of TD and FVI, while allowing RM to match and even sometimes surpass their generalization performance with assured stability.

heading: 1 INTRODUCTION
text: Model-free value estimation remains a core method of reinforcement learning (RL), lying at the heart of some of the most prominent achievements in this area (Mnih et al., 2015; Bellemare et al., 2020). Such success appears paradoxical however, given that value estimation is subject to the deadly triad: any value update that combines off-policy estimation with Bellman-bootstrapping and function approximation diverges in the worst case (Sutton and Barto, 2018). Without additional assumptions it is impossible to ensure the viability of iterative value estimation schemes, yet this remains a dominant method in RL—its popularity supported by empirical success in many applications. Such a sizable gap between theory and practice reflects limited understanding of such methods, how they behave in practice, and what accounts for their empirical success (van Hasselt et al., 2018; Achiam et al., 2019).
Decomposing the deadly triad indicates that off-policy estimation and bootstrapping are difficult to forego: off-policy estimation is supported by the empirical effectiveness of action value maximization and replay buffers, while Bellman-bootstrapping provides significant advantages over Monte Carlo estimation (Sutton, 1988). On the other hand, our understanding of the third factor, the relationship between function representation and generalization, has evolved dramatically in recent years. Although it was once thought that restrictive function approximation—representations that lack capacity to fit all data constraints—might be essential for generalization, we now know that this view is oversimplified (Belkin et al., 2019). The empirical success of deep learning (Krizhevsky et al., 2012), extremely large models (Brown et al., 2020) and associated theoretical advances (Jacot et al., 2018) have made it clear that gradient-based training of overparameterized models embodies implicit biases that encourage generalization even after all data constraints are fit exactly. This success suggests a
new opportunity for breaking the deadly triad: by leveraging overparameterized value representations one can avoid some of the most difficult tradeoffs in value-based RL (Lu et al., 2018).
The use of overparameterized deep models in value-based RL, however, still exhibits mysteries in stability and performance. Although one might expect larger capacity models to improve the stability of Bellman-bootstrapping, in fact the opposite appears to occur (van Hasselt et al., 2018). Our own empirical experience indicates that classical value estimation with deep models always diverges eventually in non-toy problems. It has also been shown that value updating leads to premature rankcollapse in deep models (Kumar et al., 2021), coinciding with instability and degrading generalization. In practice, some form of early-stopping is usually necessary to obtaining successful results, a fact that is not often emphasized in the literature (Agarwal et al., 2021). Meanwhile, there is a long history of convergent methods being proposed in the RL literature—starting from residual gradient (Baird, 1995), to gradient-TD (Sutton et al., 2008; Maei et al., 2009), prox gradient TD (Liu et al., 2015; 2016), and emphatic TD (Yu, 2015; Sutton et al., 2016)—yet none of these has demonstrated sufficient generalization quality to supplant unstable methods. The current state of development leaves an awkward tradeoff between stability and generalization. A stable recursive value estimation method that ensures generalization quality with overparametrization remains elusive.
In this paper we investigate whether overparameterized value representations might allow the stabilitygeneralization tradeoff to be better managed, enabling stable estimation methods that break the deadly triad and generalize well. To this end, we first consider policy evaluation with overparameterized linear value representations, a simplified setting that still imposes the deadly triad (Zhang et al., 2021). Here we first show that alternative updates, such as temporal differencing (TD), fitted value iteration (FVI) and residual minimization (RM) converge to different fixed points in the overparameterized case (when they converge), even though these updates share a common fixed point when the approximation error is zero and there are no extra degrees of freedom (Dann et al., 2014). That is, these algorithms embody certain implicit biases that only become distinguishable in the overparameterized case. From this result, we observe that the fixed points lie in different bases, which we use to develop a unified view of iterative value estimation as minimizing the Euclidean norm of the weights subject to alternative constraint sets. This unification allows us to formulate alternative updates that share common fixed points with TD and FVI but guarantee stability without requiring regularization or prox constraints (Zhang et al., 2021). Next, we analyze the generalization performance of these algorithms and provide a per-iterate bound on the value estimation error of FVI, and fixed point bounds on the value estimation error of TD. From these results, we identify two novel regularizers, one that closes the gap between RM and TD and another that quantifies the effect of the feature representation on the generalization bound. We deploy these regularizers in a realistic study of deep model training for optimal value estimation and observe systematic stability and generalization improvements. We also observe that the performance gap between RM and TD/FVI can be closed and in some cases eliminated.

heading: 2 RELATED WORK
text: Value estimation has a lengthy history throughout RL research. Our main focus is on off-policy value estimation with parametric function representations and iterative (i.e., gradient based) updates. We do not consider exploration nor full planning problems (i.e., approximately solving an entire Markov decision process (MDP)) in the theoretical development, but instead focus on offline value estimation; however, we do apply the findings to policy improvement experiments in the empirical investigation.
Dann et al. (2014) provide a comprehensive survey of value estimation with parametric function representations. Significant attention has been focused on underparameterized representations where backed up values are not necessarily expressible in the function class, however we focus on the overparameterized case where any backed up values can be assumed to be exactly representable with respect to finite data. This change fundamentally alters the conclusions one can draw about algorithm behavior, as we see below. One of the key consequences is that classical distinctions (Scherrer, 2010; Dann et al., 2014) between objectives—e.g., mean squared Bellman error (MSBE), mean squared projected Bellman error (MSPBE), mean squared temporal difference error (MSTDE), and the norm of the expected TD update (NEU)—all collapse when the Bellman errors can all be driven to zero. Despite this collapse, we find that algorithms targetting the different objectives—TD and LSTD for MSPBE (Sutton, 1988; Bradtke and Barto, 1996) and RM without double sampling (DS) for MSTDE (Maei et al., 2009; Dann et al., 2014)—converge to different fixed points given overparameterization, even when they ultimately satisfy the same set of temporal consistency constraints.
It is well known that classical value updates can diverge given off-policy data and parametric function representations (Baird, 1995; Tsitsiklis and Van Roy, 1996; 1997). The stability of these methods has therefore been studied extensively with many mitigations proposed, including restricting the function representation (Gordon, 1995; Szepesvári and Smart, 2004) or adjusting the representation to ensure contraction (Kolter, 2011; Ghosh and Bellemare, 2020; Wang et al., 2021b), or modifying the updates to achieve convergent variations, such as LSTD (Bradtke and Barto, 1996; Yu, 2010), FVI (Ernst et al., 2005; Munos and Szepesvári, 2005; Szepesvári and Munos, 2008; Lizotte, 2011) or the introduction of target networks (Mnih et al., 2015; Lillicrap et al., 2016; Zhang et al., 2021; Carvalho et al., 2020). Others have considered modified the updates to combat various statistical inefficiencies (van Hasselt, 2010; Weng et al., 2020; Konidaris et al., 2011). Another long running trend has been to consider two time-scale algorithms and analyses, reflected in gradient-TD methods (Sutton et al., 2008; Maei et al., 2009), prox gradient TD (Liu et al., 2015; 2016), primal-dual TD (Dai et al., 2017; Du et al., 2017), and emphatic TD (Yu, 2015; Sutton et al., 2016). Beyond mere convergence, however, we discover a greater diversity in fixed points among algorithms in the overparameterized case, which play a critical but previously unacknowledged role in generalization quality.
The fact that minimizing MSPBE via TD methods still dominates practice appears surprising given the theoretical superiority of other objectives. It has been argued, for example, that direct policy gradient methods (Sutton et al., 1999) dominate minimizing Bellman error objectives (Geist et al., 2017). Even among Bellman based approaches, it is known that MSBE can upper bound the value estimation error (MSE) whereas MSPBE cannot (Kolter, 2011; Dann et al., 2014), yet MSPBE minimization (via TD based methods) empirically dominates minimizing MSBE (via residual methods). This dominance has been thought to be due to the double sampling bias of residual methods (Baird, 1995; Dann et al., 2014), but we uncover a more interesting finding that their fixed points lie in different bases in the overparameterized setting, and that reducing this difference closes the performance gap.
We analyze the convergence of classical updates given offline data and provide associated generalization bounds, with the primary goal of understanding the discrepancy between previous theory and the empirical success of TD/FVI versus RM. Although this theory sheds new light in exploitable ways, it cannot overcome theoretical limits on offline value estimation, such as lower bounds on worst case error that are exponential in horizon length (Wang et al., 2021a;b; Zanette, 2021; Xiao et al., 2021). We analyze the convergence of the expected updates, extendible to the stochastic case using known techniques (Yu, 2010; Bhandari et al., 2018; Dalal et al., 2018; Prashanth et al., 2021; Patil et al., 2021). We expand the coverage of these earlier works by including alternative updates and focusing on the overparameterized case, uncovering previously unobserved differences in the fixed points.
There is a growing body of work on linear value estimation and planning that leverages the insight of (Parr et al., 2008; Taylor and Parr, 2009) that linear value estimation is equivalent to linear model approximation. A number of works have strived to obtain provably efficient algorithms for approximating the optimal policy values in this setting, but these generally rely on exploration or strong assumptions about data coverage (Song et al., 2016; Yang and Wang, 2019; Duan et al., 2020; Agarwal et al., 2020; Jin et al., 2020; Yang et al., 2020; Hao et al., 2021) that we do not make. Instead we study linear value estimation to gain insight, but rather than focus on linear planning we leverage the findings to improve the empirical performance of value estimation with deep models.

heading: 3 PRELIMINARIES
text: Notation We let R denote the set of real numbers, In an n× n identity matrix, and I the indicator function. For a finite set X , we use ∆(X ) to denote the set of probability distributions over X . For a vector µ we let |supp(µ)| denote the size of the support of µ (i.e., the number of nonzero entries in µ). For a matrix A ∈ Rn×m, we let A† be the Moore-Penrose pseudoinverse of A, ‖A‖ be its spectral norm, λmax(A) and λmin(A) be its maximum and minimum non-zero eigenvalues. We also use ΠA = A†A to denote the projection matrix to the row space of A. For a vector x ∈ Rd, we let ‖x‖ be its l2 norm and ‖x‖A = √ x>Ax be the associated norm for a positive definite matrix A. We also use diag(x) ∈ Rd×d to denote a diagonal matrix whose diagonal elements are x.
Markov reward processes We consider the problem of predicting the value of a given stationary policy in a Markov Decision Process (MDP). For a stationary policy, this problem can naturally formulated in terms of a Markov reward process M = {S, P, r, γ}, such that S is a finite set of states, r : S → R and P : S → ∆(S) are the reward and transition functions respectively, and γ ∈ [0, 1) is the discount factor. For a given state s ∈ S , the function r(s) gives the immediate reward incurred at
s, while P (·|s) gives the next-state transition probability of s. The value function specifies the future discounted total reward obtained from each state, which is defined as
v(s) = E [ ∞∑ t=0 γtr(st) ∣∣∣s0 = s] . (1)
To simplify the presentation we identify functions as vectors to allow vector-space operations. In particular, the reward function r is identified as a vector r ∈ R|S|, and the transition P is identified as an |S| × |S| transition matrix, where the s-th row Ps specifies the transition probability P (·|s) of state s. These definitions allow the value function to be expressed using Bellman’s equation
v = r + γPv . (2)
Linear Function Approximation It is usually not possible to consider tabular value representations in practice, since the state set is usually combinatorial or infinite. In our theoretical development we focus on linear function approximations, where v is approximated by a linear combination of features describing states; i.e., v(s) ≈ φ(s)>θ, where θ ∈ Rd is a parameter vector and φ : S → Rd maps a given state s ∈ S to a d-dimensional feature vector φ(s) ∈ Rd. We let Φ ∈ R|S|×d denote the feature matrix, with the s-th row corresponding to the feature vector φ(s), so that the value approximation can be written as v ≈ Φθ. We assume ‖φ(s)‖ ≤ 1 for any s ∈ S, and for simplicity we also assume that there is no redundant or irrelevant features in the feature map; that is, Φ is full rank.

heading: 3.1 BATCH VALUE ESTIMATION
text: We consider batch mode (“offline”) estimation of the value function. Let µ ∈ ∆(S) be an arbitrary probability distribution over states and Dµ = diag(µ). The data set consists of {si, ri, s′i}ni=1 transition tuples, which are generated by s ∼ µ, ri = r(si), s′i ∼ P (·|si). Let n(s) = ∑n i=1 I(si = s) be the number of counts of state s. We define the empirical data distribution matrix D = diag(µ̂), where µ̂(s) = n(s)/n is the empirical data distribution over states. The goal is to estimate the value function by finding a weight vector θ ∈ Rd that minimizes the value prediction error,
E(θ) = ‖Φθ − v‖2Dµ = ∑ s∈S µ(s)(φ(s)>θ − v(s))2 . (3)
Let P̂ be the empirical transition matrix, where the s-th row represents the estimated transition of state s: if n(s) > 0, P̂s(s′) = ∑n i=1 I(si = s, s′i = s′)/n(s); if n(s) = 0, P̂s(s′) = 0 for all s′ ∈ S . The empirical mean squared Bellman error on the batch data can be defined as
MSBE(θ) = 12 ∥∥r + γP̂Φθ − Φθ∥∥2 D . (4)
Over vs Underparameterized Features In this paper we are particularly interested in the overparameterized regime d > |supp(µ̂)| where one can exactly satisfy the temporal consistencies on all transitions in the batch data set, achieving zero Bellman error. (Obviously this would also be possible if d = |supp(µ̂)| but the strictly overparameterized case is more interesting, as we will see below.) By contrast, in the underparameterized regime d < |supp(µ̂)|, one can only expect to find an approximate solution that in general has nonzero Bellman error.
We consider three core algorithms in our analysis, covering major classical approaches.
Residual Minimization (RM) RM directly minimizes the empirical mean squared Bellman error Eq. (4) (MSBE) (Baird, 1995). The gradient update (Dann et al., 2014) can be expressed as
θt+1 = θt − η(Φ− γP̂Φ)>D ( Φθt − (r + γP̂Φθt) ) , (5)
where θt is the estimated weight at step t, and η is the learning rate. As a gradient descent method, the convergence of this update is robust, and applies to both linear and nonlinear function approximation.
Temporal Difference (TD) Learning The simplest variant of TD (Sutton, 1988), known as TD(0), also updates weights iteratively using transition data to approximate the value function. Let θt be the weight vector at step t. Then the so-called “semi-gradient” of Eq. (4) is used to compute the update,
θt+1 = θt − ηΦ>D ( Φθt − ( r + γP̂Φθt )) , (6)
where η is the learning rate. From Eq. (6), it is clear that in the underparameterized (d < |supp(µ̂)|) regime, if the system converges, it must converge to parameters θ∗D such that
Φ>Dr − Φ>D(Φ− γP̂Φ)θ∗D = 0 ⇒ θ∗D = (Φ>D(Φ− γP̂Φ))−1Φ>Dr , (7) where θ∗D is the TD fixed point. That is, given limited representational power, the TD fixed point minimizes the squared projected Bellman error (MSPBE) by solving the projected Bellman equation:
Φθ∗D = Π D Φ ( r + γP̂Φθ∗D ) , (8)
such that ΠDΦ = Φ(Φ >DΦ)−1Φ>D is a weighted projection matrix. It is well-known that TD(0) can diverge if the data sampling distribution µ is not the stationary distribution of the Markov process. One can still compute the TD fixed point directly using batch data, for example using the LSTD algorithm (Bradtke and Barto, 1996), but this requires computation on the order of O(d2) compared to O(d) of the iterative update algorithm Eq. (6). The value prediction error of TD is discussed in (Tsitsiklis and Van Roy, 1997; Kolter, 2011; Dann et al., 2014; Bhandari et al., 2018).
Fitted Value Iteration (FVI) FVI iteratively updates the weight vector by solving a regression problem where the target is constructed from the current estimate (Ernst et al., 2005; Dann et al., 2014), which is also known as approximate dynamic programming (Sutton and Barto, 2018). In particular, given the current weight θt at iteration t, the objective Eq. (9) is minimized to obtain θt+1,
FVIt(θ) = 1 2 ∥∥r + γP̂Φθt − Φθ∥∥2D . (9) A simple calculation shows the TD fixed point matches the fixed point of FVI whenever θ0 is in the row-span of DΦ. Although convergence of FVI can be established under strong conditions (Szepesvári and Munos, 2008), the algorithm can be quite unstable in the general batch setting (Chen and Jiang, 2019; Wang et al., 2021b).

heading: 4 OVER-PARAMETERIZED LINEAR VALUE FUNCTION APPROXIMATION
text: In this section, we study the convergence properties of the value estimation algorithms introduced in Section 3.1 in the overparameterized regime where d > |supp(µ̂)|. To faciliate analysis, we first introduce additional notation to simplify the derivations. Let {xi}ki=1 denote the states in the support of µ̂, such that n(xi) > 0 for all i = {1, . . . , k} and k = |supp(µ̂)|. Define a mask matrix H ∈ Rk×|S| and a truncated empirical data distribution matrix Dk ∈ Rk×k according to
H = 1 > x1 ...
1>xk
 , Dk = µ̂(x1) . . .
µ̂(xk)  , (10) where 1xi ∈ {0, 1}|S| is an indicator vector such that φ(xi) = Φ>1xi . We can then translate between the full distribution and its support via the following. Proposition 1. The empirical data distribution matrix D can be decomposed as D = H>DkH .
Let M = HΦ, N = HP̂Φ and R = Hr denote the state features, the expected next state features under the empirical transitions, and the rewards on the support of the data distribution respectively.
Overparameterized Residual Minimization We first study the convergence of RM given a fixed D. First note that the update Eq. (5) can be re-written as
θt+1 = (Id − η(M − γN)>Dk(M − γN))θt + η(M − γN)>DkR . (11) In the overparameterized regime, one can easily verify that there are infinitely many solutions θ ∈ Rd satisfying (M − γN)θ = R. The gradient of Eq. (11) is zero at any of these solutions, which implies that RM can have infinitely many fixed points. However, given that RM minimizes the MSBE objective via gradient descent, as we show in the following theorem, the RM update initialized from θ0 = 0 will converge to a unique fixed point. Theorem 1. With η ≤ 1(1+γ)2 and starting from θ0 = 0, RM converges to θRM = (M − γN) † R. Remark 1. For simplicity we present the fixed points of RM and TD starting from θ0 = 0. The fixed points given an arbitrary initial weight vector θ0 ∈ Rd are shown in Appendices A.1 and A.2.
This result parallels similar findings in the supervised learning literature, that training overparameterized deep models with gradient descent (or related algorithms) encodes implicit regularization
M τ
φ1
φ2
φ′2
φ′1 = φ2
ΠMφ ′ 2
Figure 1: An illustrative example showing the spectrum of W with k = 2 and d = 3. M = [φ1, φ2] >. Without loss of generality, we let φ1 = (cos τ, sin τ, 0) and φ2 = (1, 0, 0). N = [φ′1, φ ′ 2] >, where φ′1 = φ2, φ′2 = (− cos τ, √ 2 2 sin τ, √ 2 2 sin τ). Then W = [[0, 1]>, [ √ 2 2 ,−(1 + √ 2 2 cos τ)] >]. Clearly, the spectral norm of W increases as the angle τ between φ1 and φ2 decreases.
that drives the model solution to particular outcomes in the overparameterized regime (Soudry et al., 2018; Gunasekar et al., 2018; Neyshabur et al., 2019). Moreover, this implicit regularization is often associated with generalization benefits. However, unlike the case for supervised learning, RM solutions do not often generalize well. Below we uncover a key difference between the RM fixed point and those of TD and FVI that sheds new light on the source of generalization differences.
Overparameterized TD Learning We next consider the convergence properties of the TD(0) update in the overparameterized setting. First, rewrite the TD(0) update formula Eq. (6) as
θt+1 = (Id − ηM>Dk(M − γN))θt + ηM>DkR . (12) Similar to RM, in the overparameterized regime any solutions θ ∈ Rd that satisfy (M − γN)θ = R are the fixed points of Eq. (12), which implies an infinite set of fixed points. This is quite unlike the underparameterized case where there is a unique TD fixed point Eq. (7) given by the solution of projected Bellman equation. However, we now show that in the overparameterized setting, similar to solving RM using gradient descent, TD also encodes an implicit bias toward a particular fixed point.
This of course requires TD to converge, which can be assured by a simple condition. Let W = NM †, which has a geometric interpretation that we will exploit later in Section 5. Observe that
N = NΠM + N(Id −ΠM ) = NM †M + N(Id −ΠM ) = WM + N(Id −ΠM ) , (13) i.e., N can be decomposed into its projection onto the row-span of M plus a perpendicular component. Eq. (13) shows that W projects N onto the row space of M ; see Fig. 1 for an illustration. We refer to W as the core matrix since its norm determines the convergence of TD. Theorem 2. Choosing η < 1(1+γ)‖Φ‖ and starting from θ0 = 0, if ‖W ‖ < 1 γ , TD(0) converges to θTD = M †(Ik − γW )−1R. If ‖W ‖ ≥ 1γ there is an initial θ0 for which TD(0) does not converge.
A few key observations. First, note that the RM fixed point in Theorem 1 and the TD fixed point in Theorem 2 are not identical. That is, the different value estimation algorithms continue to demonstrate different preferences for fixed points, but in the overparameterized setting these differences are implicit in the algorithms and cannot be captured by the MSBE versus MSPBE objectives, since both are zero for any θ that satisfies (M − γN)θ = R. Second, the fixed point of TD lies in different basis than RM. That is, θTD lies in the row space of the state features M , whereas θRM lies in the row space of the residual features M − γN , and these two spaces are not identical in general. We revisit the significance of this difference below, but intuitively, the parameter vector θ is being trained to predict values rather than temporal differences, and the future test states from which value predictions are made will tend to be closer to the space spanned by M than M − γN .
Overparameterized Fitted Value Iteration Finally, we consider the convergence of FVI. Recall that at iteration t, FVI solves the least squares problem Eq. (9) to compute the next weight vector. Using the notation established above, the normal equations for this problem can be expressed as M>DkMθ = M
>Dk(R+γNθt), but this system cannot be directly used to compute the solution since M>DkM is not invertible. Furthermore, just like RM and TD, any θ ∈ Rd that satisfies (M − γN)θ = R is a fixed point of FVI. If one solves the least squares problem Eq. (9) using gradient descent, it is known (Bartlett et al., 2021; Soudry et al., 2018) that the optimization converges to the minimum norm solution
θt+1 = M †(R + γNθt) . (14)
Interestingly, by choosing this solution, each iteration of FVI corresponds to applying a linear backup on the current value estimate, where the backup operator is defined by the core matrix.
Definition 1. Define the core matrix linear operator TW by TW ν = R + γW ν for any ν ∈ R|S|.
Using this operator we can characterize the convergence condition of FVI, reaching the conclusion that whenever TW is a non-expansion, FVI converges to the same fixed point as TD. Theorem 3. Let θ0 be the initial weight and θt ∈ Rd be the output of FVI at iteration t. We have
θt+1 = M †T tW (R + γNθ0) . (15)
Furthermore, given that ‖W ‖ < 1/γ, the algorithm converges to θTD = M †(Ik − γW )−1R. If ‖W ‖ ≥ 1γ there is an initial θ0 for which FVI does not converge.

heading: 4.1 UNIFIED VIEW OF OVERPARAMETERIZED VALUE ESTIMATORS
text: We now show that the convergence points above can be characterized as solutions to related constrained optimization problems, providing a unified perspective on the respective algorithm biases. Theorem 4. θRM is the solution of the following constrained optimization,
inf θ∈Rd
1 2‖θ‖ 2 s.t. Mθ = R + γNθ , (16)
and θTD is the solution of the following constrained optimization,
inf θ∈Rd
1 2‖θ‖ 2 s.t. Mθ = R + γNθ , null(M)θ = 0 . (17)
That is, the convergence points of RM, TD and FVI in the overparameterized case can all be seen as minimizing the Euclidean norm of the weights θ subject to satisfying the Bellman constraints Mθ = R + γNθ, where TD and FVI implicitly add the additional constraint that θ must lie in the row span of M ; moreover, this is the only constraint that differentiates TD from RM. From this perspective, the algorithms can all be seen as iterative procedures for solving a particular form of quadratic program, when they converge. Of course, proper constrained optimization techniques would be able to stably compute solutions in scenarios where TD or FVI diverge (Boyd and Vandenberghe, 2004), but a more direct way to ensure convergence is implied by the following corollary. Corollary 1. θTD is also the solution of the following constrained optimization,
inf θ∈Rd
1 2‖θ‖ 2 s.t. Mθ = R + γNΠMθ . (18)
Note that the right hand side of the constraint simply pre-projects next state value predictions onto the row space of M before determining the Bellman backed up value. This allows a novel objective to be formulated whose minimizer recovers the same fixed point as TD,
MSCBE(θ) = 12 ‖R + γNΠMθ −Mθ‖ 2 D , (19)
which stands for mean squared corrected Bellman error. Note that MSCBE is not identical to MSPBE because the projection is applied before not after the Bellman backup. Gradient descent minimization of MSCBE yields the same fixed point as θTD, which is essentially equivalent to applying RM to corrected target values while ensuring stability. Note also that in the linear case the projection matrix ΠM only needs to be precomputed once.

heading: 4.2 VALUE PREDICTION ERROR BOUNDS
text: One can also establish generalization bounds on the value estimation error of these methods in the overparameterized regime. We first provide a finite time analysis of the value prediction error of FVI.
Theorem 5. Let Σ̂ = M>DkM be the empirical covariance matrix, and θt be the output of FVI starting from θ0 as defined in Theorem 3. Then for any θ∗ ∈ arg minθ∈Rd E(θ), E(θt)− E(θ∗)
≤ 1 kλmin(Σ̂)
(( ε2 + σ2 )∥∥∥ t−1∑ i=0 (γW )i ∥∥∥2 + ∥∥(γW )t−1∥∥2 ‖Φ‖2‖θ0 − θ∗‖2)+ 12 ‖θ∗‖2Id−ΠM , (20)
where ε = ‖N(Id −ΠM )θ∗‖ and σ = ‖H(P̂ − P )v‖.
Intuitively, ε measures the length of next-state features along the direction θ∗, and σ is the expected value prediction error under the empirical transition model, which can be bounded using standard concentration inequalities. The proof of this theorem is given in Appendix A.5. Observe that for
any step t ≥ 1, the output of FVI θt is within the row-span of M . This allows us to decompose the prediction error into a component within the row-span, controlled by leveraging the core matrix linear operator TW , and an orthogonal component that can be bounded by ‖θ∗‖2Id−ΠM . Under the convergence conditions of Theorems 2 and 3, we also have the following generalization bound for the value prediction error of θTD.
Corollary 2. Suppose that ‖W ‖ ≤ 1, and the value prediction for any s ∈ S is bounded by v(s) ∈ [0, vmax]. For any θ∗ ∈ arg minθ∈Rd E(θ),
E[E(θTD)] ≤ γ log(|S|/δ)
nminE[λmin(Σ̂)](1− γ)4 + 4γE[‖θ∗‖2Id−ΠM ] E[λmin(Σ̂)](1− γ)2 + δvmax , (21)
where nmin = mins:n(s)>0 n(s) is the minimum counts given the data set.
This result automatically implies the requirements for ensuring offline generalization, accounting both for distribution shift (Wang et al., 2021b) and policy completeness (Munos and Szepesvári, 2005; Duan et al., 2020) in feature space. In particular, for Eq. (20) and Eq. (21), we characterize the distribution shift using well known concentration bounds in Appendix A.6, which leads to the denominators kλmin(Σ̂) and nminE[λmin(Σ̂)] respectively. In addition, we explicitly characterize the misalignment between the features of current states and next states using the core matrix, which can be used to bound misalignment between values, replacing the feature completeness assumption.
We note that if the convergence condition cannot be satisfied, that is when ‖W ‖ ≥ 1/γ, the estimation error could be arbitrarily large. The sources of value estimation error are explicit in Corollary 2. The first term measures the error due to sampling (statistical error), while the second term considers out-of-span components of the optimal weight vector θ∗ with respect to M (approximation error). The smallest eigenvalue of the empirical covariance matrix E[λmin(Σ̂)], as well as the length of the orthogonal components E[‖θ∗‖2Id−ΠM ], can both be controlled using classical techniques for concentration properties of random matrix. In Appendix A.7 we present the exact approach for bounding these two terms. Furthermore, by Corollary 1, one can also apply Corollary 2 to an algorithm that directly optimizes MSCBE. Although a solution of Eq. (18) must exist, its value prediction error can be arbitrarily large given that ‖W ‖ ≥ 1/γ. This also connects to a similar result for the TD fixed point that minimizes MSPBE in the underparameterized regime (Kolter, 2011).

heading: 5 REGULARIZERS FOR DEEP REINFORCEMENT LEARNING ALGORITHMS
text: For tractability, the theory in prior sections assumes fixed representations with a linear parameterization on only the final layer parameters of the value function. However, in practice, deep RL algorithms also learn the representations in an end-to-end fashion. Inspired by the linear case, we now identify two novel regularizers that are applicable more generally—one that closes the gap between RM and TD inspired by the unified view of different fixed points, and another that quantifies the effect of feature representation on the generalization bound.
Two-Part Approximation Most deep RL algorithms rely on approximating the value function with a deep neural network Qω that predicts the future outcome of given state-action pair (Mnih et al., 2015; Kalashnikov et al., 2018; Lillicrap et al., 2016). In practice, Qω is trained by TD learning that minimizes the objective ∑ s,a(r(s, a) + γQ̄ω(s, a) − Qω(s, a)), where Q̄ω(s, a) is known as the target network to increase the learning stability. We view Qω as a two part-approximation with ω = (φ, θ), where the output of the penultimate layer is referred as the feature mapping φ, the weight of last fully connected layer is referred as θ, and the Q-function is approximated by Qω(s, a) = φ(s, a)
>θ. Our goal is to define regularizers on φ and θ that can be effectively applied to practical algorithms.
The first regularizer directly takes inspiration from Theorem 4: by restricting the linear weight θ within the row space of M (now defined by exited (s, a) pairs in the data), RM finds the same fixed point as TD. We implement this idea by penalizing the norm of the perpendicular component of θ,
Rθ = ‖θ −ΠMθ‖ , (22) In practice we compute this regularizer for each minibatch of data. The projection step is computed by a least squares algorithm with an additional l2 regularization for numerical stability.
The second regularizer is designed to address the effect of the feature representation on convergence and value prediction error. In particular, as shown by Theorems 2 and 3, a sufficient condition that guarantees the convergence of TD and FVI is that the spectral norm of W be upper bounded by 1/γ, which by Theorem 5 will also reduce the bound on generalization error. Hence, it is natural to penalize the norm of this matrix using standard automatic differentiation tools. However, such an approach is prone to numerical difficulty, as it involves differentiation through a matrix pseudo inverse. We instead propose an alternative regularizer inspired by the geometric interpretation of the core matrix Eq. (13): recall from Fig. 1 that W can be viewed as the weights that project N onto the row space of M . To ensure that an arbitrary feature vector can be well approximated using W , it would be ideal if M was orthonomral, which would imply an ideally-behaved basis to represent N . This intuition justifies the following regularization:
Rφ = ∥∥βId −M>DkM∥∥ , (23)
where β is a scale parameter designed to approximate the column norm. That is, the regularizer forces the neural network to learn an orthogonal feature embedding by normalizing the empirical feature covariance matrix. The gradient ofRφ can also approximated using mini-batches. We augment the original learning objectives by adding bothRθ andRφ weighted by hyper-parameters.

heading: 5.1 EMPIRICAL JUSTIFICATION OF REGULARIZERS
text: The goal of our experiments is to assess the applicability of the proposed regularization schemes based on orthogonality and projection operations to practical deep RL algorithms. To avoid the confounding effects of exploration, we restrict our study to learning from a frozen batch of data with a fixed number of transitions collected prior to learning. We use a randomly initialized policy in this initial collection step. We consider both discrete and continuous control benchmarks in this analysis. For the discrete action environments, we use DQN (Mnih et al., 2015) as the baseline algorithm to add our regularizers. For continuous control environments, we use QT-Opt (Kalashnikov et al., 2018) as the baseline algorithm, which is an actor-critic method that applies the cross-entropy method to perform policy optimization. Our modifications addRφ andRθ to the standard MSBE objective on the critic Q-network. Additional details describing the complete experiment setup for each environment are provided in Appendix B. Experimental results contrasting vanilla TD and RM with their regularized variants are summarized in Fig. 2. These findings demonstrate that our regularization schemes can be used to improve the performance of both vanilla TD learning and RM. Note that RM is typically less popular than TD due to its worse empirical performance. On Acrobot and Reacher, our method was able to fully close the gap between RM and TD. On Cartpole, (where vanilla RM dominates vanilla TD), and on Pendulum, our regularizers also deliver significant improvements to the TD learning baseline and modest improvements to the RM baseline.

heading: 6 CONCLUSION
text: We have investigated the fixed points of classical updates for value estimation in the overparameterized setting, where there is sufficient capacity to fit all the Bellman constraints in a given data set. We find that TD and FVI have different fixed points than RM, but in the linear case the difference can be entirely attributed to a constraint missing from RM that the solution lie in the row space of the predecessor state features. We devised two novel regularizers based on these findings, which stabilized the performance of TD without sacrificing generalization, while improving the generalization of RM, in the setting of estimating optimal values with a deep model. Characterizing the implicit bias of other
algorithms, such as gradient or emphatic TD variants remains open. Identifying other regularizers that further close the gap between TD and RM is also an interesting direction for future investigation.

heading: A PROOFS

heading: A.1 PROOF OF THEOREM 1
text: Theorem 6 (Restatement of Theorem 1). Let θ0 ∈ Rd be the initial weight vector. With η ≤ 1(1+γ)2 , RM converges to θRM = (M − γN)†R + (Id −ΠM−γN )θ0.
Proof. Let A = M − γN for simplicity. First recall the residual minimization update, θt+1 = ( Id − ηA>DkA ) θt + ηA >DkR . (24)
Let θ∗ = A†R. It can be verified θ∗ is one of the feasible solution as Aθ∗ = R. Then a simple recursive argument shows that for any θ0 ∈ Rd,
θt+1 − θ∗ = ( Id − ηA>DkA ) θt + ηA >DkR− θ∗ (25)
= ( Id − ηA>DkA ) θt + ηA >DkAθ ∗ − θ∗ (26)
= (Id − ηA>DkA)(θt − θ∗) (27) = . . . (28)
= (Id − ηA>DkA)t+1(θ0 − θ∗) (29) Thus,
θt+1 = (Id − ηA>DkA)t+1θ0 + (Id − (Id − ηA>DkA)t+1)θ∗ . (30) We let V ΛV > be its eigendecomposition of A>DkA, which is the empirical covariance matrix of residual features. Let V− be the null space of V . Then
Id − (Id − ηA>DkA)t+1 (31)
=Id − (V V > − ηV ΛV > + V−V >− )t+1 (32)
=Id − (V (Ik − ηΛ)V > + V−V >− )t+1 (33)
=Id − (V−V >− )t+1 − V (Ik − ηΛ)t+1V > (34)
=V V > − V (Ik − ηΛ)t+1V > (35) =V ( Ik − (Ik − ηΛ)t+1 ) V > (36)
Let λmax be the largest eigenvalue of A>DkA. We now show that λmax ≤ 1 + γ.
λmax ( A>DkA ) ≤ k∑ i=1 µ̂(si)λmax ( (φ(si)− γφ̄(s′i))(φ(si)− γφ̄(s′i))> ) ≤ (1 + γ)2 , (37)
where we use the fact that λmax is a convex function and we assume ‖φ(s)‖ ≤ 1 for all s ∈ S . Thus, given that η ≤ 11+γ , η ≤ 1 λmax . Then Id − (Id − ηA>DkA)t+1 = V V > as t→∞. Thus
lim t→∞ θt = lim t→∞ (Id − ηA>DkA)t+1θ0 + V V >θ∗ = lim t→∞ (Id − ηA>DkA)t+1θ0 + θ∗ , (38) where the last equality follows by that θ∗ is in the row space of A by definition. When θ0 = 0, we have the algorithm converges to θ∗.
We next show the result for general θ0. Let θ0 = θ10 + θ 2 0 , where θ 1 0 = ΠM−γNθ0 is the component of θ0 that is in the row space of A, θ20 = (Id −ΠM−γN )θ0 is the perpendicular residual. Then, lim t→∞ (Id − ηA>DkA)t+1θ0 (39)
= lim t→∞
(V−V > − + V (Ik − ηΛ)t+1V >)(θ10 + θ20) (40)
=θ20 + lim t→∞ V (Ik − ηΛ)t+1V >θ10 = θ20 , (41)
where the last step follows by the choice of η. This finishes the proof.

heading: A.2 PROOF OF THEOREM 2
text: Theorem 7 (Restatement of Theorem 2). Let θ0 ∈ Rd be the initial weight vector. Assuming that M>Dk(M − γN) is diagonalizable, with η < 1(1+γ)‖Φ‖ , if ‖W ‖ < 1 γ , TD(0) converges to θTD = M †(Ik − γW )−1R+ β, where β = Q0Q−10 θ0, Q0 are eigenvectors of M>Dk(M − γN) with zero eigenvalues. If ‖W ‖ ≥ 1γ there is an initial θ0 for which TD(0) does not converge.
Proof. We first rewrite the TD update formulate as
θt+1 = (Id − ηM>Dk(M − γN))θt + ηM>DkR (42) A simple recursive argument shows that for any θ0 ∈ Rd,
θt+1 = (Id − ηM>Dk(M − γN))t−1θ0 + η t∑ i=0 (Id − ηM>Dk(M − γN))iM>DkR .
(43)
Then note that (Id − ηM>Dk(M − γN))iM>Dk (44)
=(Id − ηM>Dk(M − γN))i−1(Id − ηM>Dk(M − γN))M>Dk (45)
=(Id − ηM>Dk(M − γN))i−1(M>Dk − ηM>Dk(M − γN)M>Dk) (46)
=(Id − ηM>Dk(M − γN))i−1M>Dk(Ik − η(M − γN)M>Dk) (47) = . . . (48)
=M>Dk(Ik − η(M − γN)M>Dk)i (49) By writing N as the projection to the row-span of M and the perpendicular component, we have
(M − γN)M> (50)
=(M − γNM †M − γN(Id −M †M))M> (51)
=(Ik − γW )MM> , (52) where the last step follows by (Id −M †M)M> = 0. Thus we can rewrite θt+1 as
θt+1 = (Id − ηM>Dk(M − γN))t−1θ0 + ηM>Dk t∑ i=0 (Ik − η(M − γN)M>Dk)iR (53)
= (Id − ηM>Dk(M − γN))t−1θ0 + ηM>Dk t∑ i=0 (Ik − η(Ik − γW )MM>Dk)iR ,
(54)
Given ‖W ‖ < 1/γ, we have that all eigenvalues of Ik − γW are positive. Let η < 1(1+γ)‖Φ‖ , then
‖η(Ik − γW )MM>Dk‖ < η‖(Ik − γW )‖‖MM>Dk‖ < 1 , (55) otherwise the matrix power series diverges. Thus
ηM>Dk t∑ i=0 (Ik − η(Ik − γW )MM>Dk)iR = M †(Ik − γW )−1R . (56)
Therefore, given that θ0 = 0, we have the algorithm converge to M †(Ik − γW )−1R. We now show the convergence point for an arbitrary θ0. Let QΛQ−1 be the eigen decomposition of M>Dk(M − γN). By the low rank structure of this matrix, it has at most h ≤ k non-zero
eigenvalues. Let Q0 be the eigenvectors with eigenvalue zero. Then
lim t→∞
(Id − ηM>Dk(M − γN))tθ0 (57)
= lim t→∞
Q(Id − ηΛ)tQ−1θ0 (58)
=Q0Q −1 0 θ0 , (59)
where the last step follows by the choice of η.
Characterization for non-diagonalizable M>Dk(M − γN) Let Z = M>Dk(M − γN) and Z = QJQ−1 be the jordan normal form of Z. We still denote Q0 the eigenvectors with eigenvalue zero. Then there is
lim t→∞ (I − ηZ)t = lim t→∞ Q(I − ηJ)tQ−1 (60)
Since I − ηJ has a block diagonal structure, its power can be obtained by first computing the power of each block. Let Ji be the jordan block with eigenvalue λi. We write Ji = λiI + L, where L is a matrix such that the only non-zero entries of L are on the first off-diagonal. Then we can write the i-th block of J as (1− ηλi)I − ηL. Using the binomial theorem we get
((1− ηλi)I − ηL)t = t∑
s=0
( t s ) (1− ηλi)t−s(−ηL)s . (61)
Note that Ls is the matrix with ones on the s-th diagonal away from the main diagonal, and Ls = 0 for s larger than the size of L. Therefore, ((1−ηλi)I−ηL)t is a triangular matrix with (1−ηλi)t on the main diagonal, −ηt(1− ηλi)t−1 on the first off-diagonal, and so on. Therefore, the eigenvalues of this matrix are all (1− ηλi)t. Then given a learning rate that η < 1/λmax, for any jordan block with λi > 0, we have that the matrix power converges. For λi = 0, the jordan block corresponds to eigenvectors that are in the kernel space of Z. Thus, suppose that all eigenvalues of Z are non-negative, we have
lim t→∞
Q(I − ηJ)tQ−1θ0 = Q0Q−10 θ0 . (62)
Note that if a negative λi exists, the above derivations can still be used to characterize the convergent sub-component of θ0. The non-convergent sub-component of θ0 will diverge with an exponential rate as shown above.

heading: A.3 PROOF OF THEOREM 3
text: Proof. We first prove the update formula. Recall the FVI update,
θ = M †(R + γNθt−1) .
For t = 1 the result holds by definition. For t ≥ 2, a simple recursive argument reveals that for every θ0 ∈ Rd,
θt = M †(R + γNθt−1) (63)
= M †(R + γN(M †(R + γNθt−2))) (64)
= M †(R + γNM †R + γ2NM †Nθt−2) (65)
= M †(R + γNM †R + γ2NM †NM †(R + γNθt−3)) (66)
= M †(R + γNM †R + γ2(NM †)2R + γ2(NM †)2Nθt−3) (67) = . . . . . . (68)
= M † ( t−2∑ i=0 (γNM)iR + (γNM †)t−1(R + γNθ0) ) (69)
Clearly the convergence of this algorithm depends on the spectral norm of NM †. In particular, given that ‖NM †‖ < 1/γ, we have the algorithm converges to
M †(Ik − γW )−1R (70) as t→∞. This finishes the proof.

heading: A.4 PROOF OF THEOREM 4 AND COROLLARY 1
text: Proof. We first prove the result for residual minimization fixed point θRM. Let A = M − γN for simplicity. We write the Lagrange of the optimization problem,
L(θ, α) = inf θ∈Rd sup α∈Rk
1 2 ‖θ‖2 + α>(R−Aθ) (71)
= sup α∈Rk
1 2 ‖A>α‖2 + α>R− α>AA>α (72)
= sup α∈Rk α>R− 1 2 α>AA>α . (73)
Solving for α∗ and add it to θ∗ = A>α∗ gives that θ∗ = A†R.
We next prove Corollary 1, which characterizes the TD and FVI fixed point θTD. Let W = NM †. We write the Lagrange of the optimization problem,
L(θ, α) = inf θ∈Rd sup α∈Rk
1 2 ‖θ‖2 + α>(R− (Ik − γW )Mθ) (74)
= sup α∈Rk
1 2 ‖M>(Ik − γW )>α‖2 + α>R− α>(Ik − γW )MM>(Ik − γW )>α (75)
= sup α∈Rk α>R− 1 2 α>(Ik − γW )MM>(Ik − γW )>α . (76)
Solving for α∗ and add it to θ∗ = M>(Ik − γW )>α∗ gives that θ∗ = M †(Ik − γW )−1R. The second part of Theorem 4 is immediately followed by this.

heading: A.5 PROOF OF THEOREM 5
text: Lemma 1. Let θt be the output of FVI at iteration t with θ0 as the initial parameter. We have that M †Mθt = θt for any t ≥ 1.
Proof. The claim is implied by the fact that θt is in the row space of M . In particular, by Theorem 3, θt = M
†α for some α ∈ Rn. Thus, M †Mθt = M
†MM †α = M †α = θt . (77) This finishes the proof.
Lemma 2. E(θ) is 1-smoothness.
Proof. Recall the prediction error of θ ∈ Rd
E(θ) = 1 2 ‖Φθ − v‖2Dµ = 1 2 ‖θ − θ∗‖2Σ , (78)
where Σ = Φ>DµΦ. The gradient of θ is E ′(θ) = Σ(θ − θ∗). Then ‖E ′(θ1)− E ′(θ2)‖ = ‖Σ(θ1 − θ2)‖ ≤ λmax(Σ) ‖(θ1 − θ2)‖ ≤ ‖θ1 − θ2‖ , (79)
where we use ‖φ(s)‖ ≤ 1 for all s ∈ S and λmax(Σ) ≤ ∑ s µ(s)λmax(φ(s)φ(s) >) ≤ 1.
Lemma 3. Let εapp = NΠ⊥Mθ∗ and σstat = H(P − P̂ )Φθ∗. We have
Hv = Mθ∗ = T−1∑ i=0 (γW )i (R + γ(ε+ σ)) + (γW )T (Mθ∗) .
for any T ≥ 1.
Proof. A simple recursive argument shows that, Mθ∗ = R + γHPΦθ∗
= R + γNθ∗ + γH(P − P̂ )Φθ∗
= R + γ(WM + NΠ⊥M )θ ∗ + γH(P − P̂ )Φθ∗ = R + γ(εapp + εstat) + γWMθ ∗
= . . .
= T−1∑ i=0 (γW )i (R + γ(εapp + εstat)) + (γW ) T (Mθ∗) .
Proof. By Theorem 3, θt = M †T t−1(R + γNθ0) is the output of FVI at iteration t. By noting that E(θ∗) = 0 and Lemma 2, for any θ ∈ Rd.
E(θ) ≤ 1 2 ‖θ − θ∗‖2 = 1 2
( ‖θ − θ∗‖2M†M + ‖θ − θ ∗‖2Id−M†M ) . (80)
We first consider the second term. By Lemma 1,
‖θt − θ∗‖2Id−M†M = (θt − θ ∗)> ( Id −M †M ) (θt − θ∗) = ‖θ∗‖2Id−M†M . (81)
We now consider the first term. By Lemma 3, M(θ∗ − θt) = Mθ∗ − T t−1(R + γNθ0) (82)
= t−2∑ i=0 (γW )i (R + γ(εapp + εstat)) + (γW ) t−1(Mθ∗)− t−2∑ i=0 (γW )iR− (γW )t−1(R + γNθ0)
(83)
=γ ( t−2∑ i=0 (γW )iεapp + t−1∑ i=0 (γW )iεstat + (γW ) t−1N(θ∗ − θ) ) (84)
Let Σ̂ = M>DkM be the empirical covariance matrix. Note that λmin(M>M)/k ≥ λmin(Σ̂). To show this, let D̄ = diag( 1k , . . . , 1 k ), and M = USV > be the SVD of M . Then
λ+min(M >D̄M) = min ‖x‖=1 x>M>D̄Mx (85)
= min ‖α‖=1
α>SU>D̄USα (86)
≥ min ‖α‖=1 α>SU>DkUSα (87)
= λ+min(M >DkM) (88)
where we replace x = V α since V are orthonormal bases, and mini∈[k] µ̂i ≤ 1/k. Therefore, ‖M †‖ = 1/ √ λ+min(M †M) ≤ 1/ √ kλ+min(Σ̂).
Combining the results above we have, ‖θt − θ∗‖2M†M = ∥∥M †M(θt − θ∗)∥∥2 (89)
≤ ‖M †‖2 ‖M(θt − θ∗)‖2 (90)
≤ γ kλmin(Σ̂) ∥∥∥∥∥ t−1∑ i=0 (γW )i(εapp + εstat) + (γW ) t−1N(θ∗ − θ) ∥∥∥∥∥ 2
(91)
≤ 4γ kλmin(Σ̂) (ε2 + σ2)∥∥∥∥∥ t−1∑ i=0 (γW )i ∥∥∥∥∥ 2 + ∥∥(γW )t−1∥∥2 ‖Φ‖2‖θ0 − θ∗‖2  . (92)
Combine this with Eq. (81) finishes the proof.

heading: A.6 PROOF OF COROLLARY 2
text: Proof. Recall that in the proof of Theorem 5 we have
‖θt − θ∗‖2M†M ≤ 4γ
kλmin(Σ̂) (ε2 + σ2)∥∥∥∥∥ t−1∑ i=0 (γW )i ∥∥∥∥∥ 2 + ∥∥(γW )t−1∥∥2 ‖Φ‖2‖θ0 − θ∗‖2  . (93)
Given that ‖W ‖ < 1, we have for the fixed point θ∞,
‖θt − θ∗‖2M†M ≤ 4γ(ε2 + σ2)
kλmin(Σ̂)(1− γ)2 (94)
We first consider σ2 = ‖H(P − P̂ )v‖2. By Hoeffding’s inequality and a union bound we have with probability at least 1− δ, for any s ∈ supp(D),∣∣∣(P̂s − Ps)>v∣∣∣ ≤ 1
1− γ
√ log(|S|/δ)
2n(s) . (95)
Thus, let nmin = mins:n(s)>0 n(s), we have
σ2 k ≤ log(|S|/δ) 2(1− γ)2nmin . (96)
Now we consider ε2 = ‖NΠ⊥Mθ∗‖2. Since NΠ⊥M is perpendicular to M , and all features have norm bounded by one,
ε2 k ≤ ‖θ∗‖2Id−M†M . (97)
Combine the above we have,
E(θ) ≤ 1 2 ‖θ − θ∗‖2M†M + 1 2 ‖θ∗‖2Id−M†M (98)
≤ 2γ λmin(Σ̂)(1− γ)2
( log(|S|/δ)
2(1− γ)2nmin + ‖θ∗‖2Id−M†M
) + 1
2 ‖θ∗‖2Id−M†M (99)
= γ log(|S|/δ)
λmin(Σ̂)(1− γ)4nmin +
4γ
λmin(Σ̂)(1− γ)2 ‖θ∗‖2Id−M†M (100)
Finally, using the tower rule gives the desired result.

heading: A.7 CONCENTRATION OF EIGENVALUES AND BOUNDING THE ORTHOGONAL COMPLEMENT
text: We will need the following result (Kuzborskij et al., 2021, Theorem 6), which is concerned with the magnitude of projection onto the eigenspace of a covariance matrix. The result is based on (Shawe-Taylor et al., 2005, Theorem 1)
Lemma 4. Let Σ̂ = 1n ∑ i xix > i be the covariance matrix of i.i.d. data xi ∈ Rd. Denote the h-“tail” of eigenvalues of a covariance matrix Σ̂ = as
λ>h = n∑ i=h+1 λi . (101)
Let Ur be the first r eigenbasis for r ∈ [n]. Then for any z ∈ Rd, with probability at least 1− δ,
E [ ‖Π⊥Urz‖ 2 2 ] ≤ min h∈[r]  1nλ>h + 1 + √ h√ n √√√√ 2 n n∑ i=1 ‖xi‖2 + ‖z‖22 √ 18 n ln ( 2n δ ) . (102)
The next lemma gives a non-asymptotic result to understand the behaviour of λ̂min (Kuzborskij et al., 2021, Lemma 1).
Lemma 5. Let X = [X1, . . . ,Xn] ∈ Rd×n be a random matrix with i.i.d. columns, such that maxi ‖Xi‖2 ≤ K, and let Σ̂ = XX>/n, and Σ = E[X1X>1 ]. Then, for every α ≥ 0, with probability at least 1− 2e−α, we have
λ+min(Σ̂) ≥ λ + min(Σ)
( 1−K2 ( c √ d
n +
√ α
n ))2 + for n ≥ d , (103)
and furthermore, assuming that ‖Xi‖Σ† = √ d, for all i ∈ [n], we have
λ+min(Σ̂) ≥ λ + min(Σ)
(√ d
n −K2
( c+ 6 √ α
n ))2 + for n < d , (104)
where we have an absolute constant c = 23.5 √ ln 9.

heading: A.8 NEURAL TANGENT KERNEL EXTENSION
text: We show how to extend the results of Theorem 3 using neural tangent kernel. Let v(s, ω) be the value function approximated by a neural network, where ω is all the parameters of the neural network. The neural tangent kernel is defined as
ker(s, s′) = Eω∼Ω 〈 ∂v(s, ω)
∂ω , ∂v(s′, ω) ∂ω
〉 (105)
where s, s′ are two states, Ω is an initialization distribution over ω. Let ω0 be random initial parameters sampled from Ω, there is
ker0(s, s′) = 〈 ∂v(s, ω0)
∂ω0 , ∂v(s′, ω0) ∂ω0
〉 ≈ ker(s, s′) . (106)
See (Arora et al., 2019, Theorem 3.1) for the proof. Note that in this kernel, an input s is mapped to a feature vector φ(s) = ∂v(s,ω0)∂ω0 .
Consider a least square problem: given a training dataset {xi, yi}ki=1, consider training the neural network by minimizing the squared loss over training data: 12 ∑k i=1(v(xi, ω)− yi)2. The following result shows that a properly randomly initialized sufficiently wide deep neural network trained by gradient descent is equivalent to a kernel regression predictor with neural tangent kernel (Arora et al., 2019, Theorem 3.2),
v(x, ω) ≈ vNTK(x) = ker(x,X)>ker(X,X)−1y , (107) where ker(x,X) = (ker(x, x1), . . . , ker(x, xk))>, ker(X,X) ∈ Rk×k whose (i, j)-th element is ker(x, xi), and y ∈ Rk whose i-th element is yi.
Recall that {xi, ri, x′i}ki=1 is the batch dataset on the support of the µ̂. Let ker(X ′,X) be a n× n matrix where the (i, j)-th element is ker(x′i, xj). For simplicity, we assume that FVI uses zero value prediction initially. We now prove that for any s ∈ S , the value prediction at the t-th iteration of FVI is given by
vt(s) = ker(s,X)>ker(X,X)−1 ( t−1∑ i=1 ( γker(X ′,X)ker(X,X)−1 )i R ) . (108)
We prove this result by induction. For the base case i = 1, the result directly follows by Eq. (107),
v1(s) = ker(s,X)>ker(X,X)−1R . (109) Now suppose the induction hypothesis holds for i = t− 1, then by Eq. (107) vt(s) = ker(s,X)>ker(X,X)−1 (110)(
R + γker(X ′,X)>ker(X,X)−1 ( t−2∑ i=1 ( γker(X ′,X)ker(X,X)−1 )i R )) (111)
= ker(s,X)>ker(X,X)−1 ( t−1∑ i=1 ( γker(X ′,X)ker(X,X)−1 )i R ) . (112)
Then, given that the following matrix is a contractor γker(X ′,X)ker(X,X)−1 , (113)
we have that at the convergence, the value prediction of FVI for any s ∈ S is given by vFVI(s) = ker(s,X)>ker(X,X)−1 ( I − γker(X ′,X)ker(X,X)−1 ) R . (114)
Note that ker(X ′,X)ker(X,X)−1 corresponds to the core matrix W in the linear setting.

heading: B EXPERIMENT SETUP
text: In this section, we provide additional details about the experimental setup and hyper-parameters used for each of the environments. For all of these environments the regularization weights were considered as tunable hyper-parameters. In addition, for Rφ (see Eq 23), the scale factor β was also considered as a parameter to be tuned in order to approximate the feature matrix norm.

heading: B.1 ACROBOT
text: • Replay buffer with 10k tuples sampled using a random policy across trajectories with maximum episode length of 64.
• A DQN with hidden units consisting of fully connected layers with (100, 100) units. • Batch size 64. • Learning rate of 1e-3. • Regularized RM with weight of 2e-2 onRφ and 1e-4 onRw. • Regularized TD with weight of 0 onRφ and 1e-4 onRw.

heading: B.2 REACHER
text: • Replay buffer with 10k tuples sampled from a random policy across trajectories with maximum steps per episode of length 50.
• Learning rate 1e-4. • A value network for the continuous action inputs with a fc observation layer with params
(50,), a fc action layer with params (50,) and a joint fc layer with params (100,). • Batch size 64. • Gradient clipping with a norm of 10.0 • Regularized RM with weight of 0.15 onRw and 0 onRφ. • Regularized TD with weight of 2e-2 onRw and 7e-3 onRφ.

heading: B.3 CARTPOLE
text: • Replay buffer with 10k tuples sampled using a random policy across trajectories with maximum steps per episode of length 50.
• A DQN with hidden units consisting of fully connected layers with (100, 100) units. • Batch size 64. • Learning rate 1e-3. • Regularized RM with weight of 0.29 onRw and 0 onRφ. • Regularized TD with weight of 1.5e-3 onRw and 5e-3 onRφ.

heading: B.4 PENDULUM
text: • Replay buffer with 1k tuples obtained by sampling directly from a fixed initial state distribution using a random policy.
• A value network for the continuous action inputs with a fc observation layer with params (50,), a fc action layer with params (50,) and a joint fc layer with params (100,).
• Batch size 64. • Learning rate 1e-3. • Regularized RM with weight of 1.0 onRw and 5.4e-4 onRφ. • Regularized TD with weight of 0 onRw and 1.0 onRφ.

heading: B.5 EXTRA EXPERIMENT RESULTS
text: We provide extra experiment results on four mujoco control problems to assess the applicability of the proposed regularization Rφ: HalfCheetah, Hopper, Ant, and Walker2d. The results are provided in Fig. 3. All results are averaged over 100 runs with different random seeds. The hyper-parameters are provided below.
• The Q-function is approximated by two hidden layer fully neural networks, where the hidden layer size is 256.
• Batch size 256. • Learning rate 3e-4. • Regularized TD weight are tuned from {1e− 4, 1e− 3, 1e− 2, 1e− 1, 1}

Review summaries:
This paper studies the convergence properties of three classical value estimation algorithms (TD, FVI and RM) under over-parameterized linear case. The difference among convergence results are interpreted unifiedly through different constraints in an optimization problem. It also proposes an generalization bound for FVI. Furthermore, based on the results mentioned before, it proposes two regularizers to help convergence in deep reinforcement learning and experimentally evaluates their performance.

In this paper, the authors consider the overparameterized linear representations of TD, FVI, and RM. A unified interpretation of these algorithms of minimizing the Euclidean norm of the weights subject to alternative constraints is proposed. The paper is also supported by the empirical results.