Understanding and Leveraging Overparameterization in Recursive Value Estimation
Authors: Chenjun Xiao
Bo Dai
Jincheng Mei
Oscar A Ramirez
Ramki Gummadi
Chris Harris
Dale Schuurmans
Venue: ICLR 2022 Poster (2022)
Keywords: Temporal Difference Learning
Residual Minimization
Value Estimation
Overparameterization

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 \emph{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 \emph{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. 

Published as a conference paper at ICLR 2022
UNDERSTANDING AND LEVERAGING OVERPARAME- TERIZATION IN RECURSIVE VALUE ESTIMATION
Chenjun Xiao .2,-, Bo Dai', Jincheng Mei', Oscar Ramirez', Ramki Gummadi',
Chris Harris' & Dale Schuurmans
'Google 2 *Deparment of Computing Science, University of Alberta
ABSTRACT
The theory of function approximation reinforcement learning (RL) typically considers low capacity representations that incur a tradeoff between approximation error, stability and generalization. Current deep architectures, however, operate in overparameterized regime where approximation error is not necessarily bottle- neck. 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 seeedd-vaue-iteration (FVI) converge different fixed points than residual minimization (RM) in the overparameterized linear case. We then develop a unified interpretation of overparameterized lin- ear value estimation minimizing the Euclidean norm of the weights subject to alternative constraints, A practical consequence 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 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 RMM. Given this understanding, 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 dramati- cally improve the stability of TD and FVI, while allowing RM match and even sometimes surpass their generalization performance with assured stability.
INTRODUCTION
Model-free value estimation remains a method of reinforcement learning (RL), lying 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 subject the deadly triad: any value update that combines off-ppoicy estimation with Bellman-bootstrapp
and function approximation diverges in the worst case (Sutton and Barto, 2018 8). Without additional assumptions 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 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 cellman-bootstrappiin 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. Al- though it was once thought that restrictive function approximation approxinatiinnrepesstttiinn that lack capacity to fit all data constraints- miiht 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),
provides significant advantages over Monte Carlo
Work performed while an intern Google Brain. Email: {chenjun, dues] berta.ca

---

Published as a conference paper at ICLR 2022
extremely large models (Brown et al., 2020) and associated theoretical advances (Jacot al., 2018) have made it clear that gradient-based training of overparameterized models embodies implicit biases that encourage generalization even after all data constraints fit exactly. This success suggests 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- RL, however, still exhibits mysteries in stability and performance. Although one might expect larger capacity models improve the stability of Bellmmn--bottsrappiin empirical experience indicates that classical value estimation with deep models eventually diverges in non-toy problems. It has also been shown that value updating leads to premature rank-collapss 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, fact that 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 awkward tradeoff between stability and generalization. A stable recursive value estimation method that ensures generalization quality with overparametrization remains elusive.
in fact the opposite appears to occur (van Hasselt et al.. 2018). Our own
In this paper investigate whether overparameterized value representations might allow the stability- generalization tradcoff to be better managed, enabling stable estimation methods that break the deadly triad and generalize well. 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 find 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 implicit biases that only become distinguishable in the overparameterized regime. 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 fixed points with TD and FVI but guarantee stability without requiring regularization or prox constraints (Zhang al., 2021). Next, we analyze the generalization performance of these algorithms and provide 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 can be closed and in some cases eliminated.
2 RELATED WORK
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 underparameterizedd 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.a 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
2

---

Published as a conference paper at ICLR 2022
(Maci et al., 2009; Dann et al., 2014) converge to different fixed points given overparameterizztionn, even when they ultimately satisfy the same set of temporal consistency constraints.
It is well known that classical value updates 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 mitigationn proposed, including restricting the function representation (Gordon, 1995; Szepesvári and Smart, 2004) or adjusting the representation to ensure contraction (Kolter, 2011: Ghosh and Bellemare, 2020; Wang et al., 202 2021b), lb), or modifying the updates
to achieve convergent variations, such as LSTD (Bradtke and Barto, 1 1996; Yu, 2010), FVI (Ernst et al., 2005; Munos and Szepesvári. 2005: Szepesvá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., 201 I). Another long running trend has been to consider two time-scale algorithms and analyses, reflected in gradient- TTD 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 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 generaliza- tion 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., 202] 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 al., 2018; Dalal et al., 2018; Prashanth 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 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 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 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.
3 PRELIMINARIES
Notation We let R denote the set of real numbers, I, an n X n identity matrix, and Il the indicator function. For a finite set X, we use A(X') to denote the set of probability distributions over X. For a vector l1 we let [supp(μ)) denote the size of the support of μ (i.c., the number of nonzero entries in μ)) For matrix A E Iaam we let A be the Moore-Penross pseudoinverse of A, ||||| be its spectral norm, and Ammax (A) and A (A) be its maximum and minimum non-zero cigenvalues. We also use A A A to denote the projection matrix to the row space of A. For a vector IRdd let ||>||| be its la norm and æalaA= = Vx T Ax be the associated norm for a positive definite matrix A. We also use diag(z) ) E d to denote a diagonal matrix whose diagonal elements are x.
Markoy reward processes We consider the problem of predicting the value of a given stationary policy in Markov Decision Process (MDP). For stationary policy, this problem can be formulated
3

---

Published as a conference paper at ICLR 2022
in terms of Markov reward process M (S, P.r, such that S is finite set of states, r S IR and P: S + (S) are the reward and transition functions respectively, and y E [o, 1) is the discount factor. Let S |S] be the number of states. For given state s E S, the function r(s) gives the immediate reward incurred at 8, while P(-[s) gives the next-state transition probability of 8. The value function specifies the future discounted total reward obtained from each state, defined
((s) = E
y rr(ss) su
(1)
1=U
To simplify the presentation we identify functions as vectors to allow vector-space operations: the value function and reward function identified vectors v, E RR, the transition P is identified as an S x S transition matrix, where the s-th row P. specifies the transition probability Pl-(s) of state These definitions allow the value function be expressed using Bellman's 's equation
== PPv.
(2)
Linear Function Approximation is usually not possible to consider tabular value representations in practice, since the state set is usually combinatorial 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) x ( 0, where A E R is parameter vector and Φ S - Rd maps given state E S to d-dimensional feature vector ((s) E Rd. We let 4 E R xd denote the feature matrix, with the s-th row corresponding to the feature vector Φ(8), so that the value approximation be written that there is no redundant or irrelevant features in the feature map; that is, & is full rank.
$0. We assume [[][s]] < for any S, and for simplicity also assume
3.1 BATCH VALUE ESTIMATION
We consider batch mode ("offtine") estimation of the value function. Let μa (S8) be an arbitrary probability distribution over states and D,, = diag(1)). The data set consists of {si, ri 8 ) transition tuples, which are generated by s rr = s(, ~ P(-[st). Let n(s) >. 1(s s) be the number of counts of state s. We define the empirical data distribution matrix D diag (ā). where (s)) = n(s)/r n the empirical data distribution over states. The goal is to estimate the value function by finding a weight vector O E Rd that minimizes the value prediction error,
( = 20 vll. = E.es (()))((s)) v(s))²
(3)
Let P be the empirical transition matrix, where the s-th row represents the estimated transition of state s: (s) > (s') Σ I[ss, = s, s = s') /n/n((e ( (s); if ns)) 0, Ps())) = for all s' e e. The empirical mean squared Bellman error the batch data can be defined as
MSBE(() = 1 + + +
(4)
Over vs Underparameterized Features In this paper we are particularly interested in the over- parameterized 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 = |supp( (A)] but the strictly overparameterized case is more interesting, as we will see below.) By contrast, in the underparameterized regime d < (supp(ft), 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
(5) where 0; is the estimated weight at step t, and is the learning rate. As gradient descent method, the convergence of this update is robust, and applies to both linear and nonlinear function approximation.
i 0 0: 17 + 7 PT) D
(r + +PP0))
Temporal Difference (TD) Learning The simplest variant of TD (Sutton, 1988), known as TD(O), also updates weights iteratively using transition data to approximate the value function. Let O be the weight vector at step f. Then the so-called "semi "semi-gradies gradient" of Eq. (4) is used to compute the update,
0 0,77 D(00, (r+ (r+7P
66)
4

---

Published as a conference paper at ICLR 2022
where 1) is the learning rate. From Eq. (6), is clear that in the underparameterrzzed (d [supp((t) regime, if the system converges, must converge to parameters 0 such that
i Dr T ② y P
0 + D - -P)) Dr,
Dr
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:
$ (
(8)
such that 11 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 (dd) compared to (d) of the iterative update algorithm Eq. (6). The value prediction error of TD discussed in (Tsitsiklis and Van Roy, 1997; Kolter, 2011; Dann et al., 2014; Bhandari et al., 2018).
- D a weighted projection matrix. It well-known that TD(0)
Fitted Value Ittration (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 O, iteration the objective Eq. (9) is minimized to obtain 0,+1,
(V) 2 PP00 ~0
A simple calculation shows the TD fixed point matches the fixed point of FVI whenever Og is in the row-span of DΦ. Although convergence of FVI can be established under strong conditions (Szepesvári and Munos, 2008). the algorithm can be quite unstable in the general batch setting (Chen and Jiang, 2019; Wang et al., 2021b).
OVER-PARAMETERIZER LINEAR VALUE FUNCTION APPROXIMATION
In this section, study the convergence properties of the value estimation algorithms introduced in Section 3.1 in the overparameterized regime where d > (u)p( To faciliate analysis, we first introduce additional notation simplify the derivations. Let { 1 denote the states in the support of μ., such that n(x;)) > 0 for all = f1....,A k} and k = (supp(()) Define a mask matrix
H E IR (x|s) and a truncated empirical data distribution matrix D2 E IR k according to
(a(x1)
D&
(10)
A (xxx)
where 1,; E (0.1) 1S is indicator vector such that (bx;)
T 1s,-- 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 D.
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 fixed D. First note that the update Eq. (5) can be re-written as
0++1 = (L. 7M(M - - Dz(M - 7, + (MM T D.R.
(11)
In the overparameterizee regime, one can easily verify that there are infinitely many solutions 0 E Rd satisfying ( M 7 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 unique fixed point.
Theorem 1. With 1j S কमी and starting from Og O, RM converges to ORM = (M - ~NN) R
For simplicity we present the fixed points of RM and TD starting from Og = 0. The fixed points given an arbitrary initial weight vector 0g Rdd are shown in Appendices A. and A.2.
Remark 1.
This result parallels similar findings in the supervised learning literature, that training overparam- eterized deep models with gradient descent (or related algorithms) encodes implicit regularization
5

---

Published as a conference paper at ICLR 2022
22
Figure 1: An illustrative example showing the spectrum of W with k = 2 and d = 3. M [01, Φ2 Without loss of generality,
let Φ1 = (cos T. Tin,,O0 0) and Φ2 = (1,0,0) where of d2 H2
Ø2
N - 10%
(- cOST T, v2 sin v2 sin Then W =
11
2
[[0, I]. 2 -(1 L22 cosT)]]]] Clearly,
2:
M
Φ1
the spectral norm of W increases as the angle T between @1 and 02 decreases.
1 = Φ2
that drives the model solution to partieular 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
0.+1 (Ia nM D&(M 0 + nM D.R.
(12)
Similar to RM, in the overparameterized regime any solutions 0 E Rd that satisfy (M- = R the fixed points of Eq. (12), which implies an infinite set of fixed points. This is quite unlike the underparameterized case where there is 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 = N which has a geometric interpretation that we will exploit later in Section 5. Observe that
N NIl + ( llm) NM M N Il) WM N(I. IM), (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 17- < (1+7) o and starting from 0, = 0, if [| < 2. TD(O) converges to
0pp = M W) R. If W 2 there an initial 0 for which TD(0) does not converge.
A few key observations. First, note that the RM fixed point in Theorem I 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 zero for any that satisfies (M- y N = R. Second, the fixed point of TDD lies in different basis than RM. That is, OTD lies in the row space of the state features M. whereas FRM 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 M, = M D& +++N++ 70.).bu but this system cannot be directly used to compute the solution since M T D M is not invertible. Furthermore, just like RM and TD, any 0 E Idd that satisfies (M 7No6 R. is fixed point of FVI. If one solves the least squares problem Eq. (9) using gradient descent, is known (Bartlett et al., 2021; Soudry et al., 2018) (018) that the optimization converges to the minimum norm solution
+ 0 = 1 ( 7NO))
(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.

---

Published as a conference paper at ICLR 2022
Definition 1. Define the core matrix linear operator Tw by TWV R +- for any R
Similar results for the case with underparameterizee linear model have been discussed in (Parr et al., 2008). Using this operator
characterize the convergence condition of FVI, reaching the conclusion that whenever Tw is non-expansion, FVI converges to the same fixed point as TD.
Theorem 3. Let Oy be the initial weight and 0 E IR be the output of FVI at iteration t. We have
Ozt1 = ( 7No).
(15)
Furthermore, given that || < <1/%, the algorithm converges to OTD MT WW- If [W]] 2 ,/4 there an initial O for which FVI does not converge.
4.1
UNIFIED VIEW OF OVERPARAMETERIZA VALUE ESTIMATORS
We now show that the convergence points above can be characterized as solutions to related con- strained optimization problems, providing a unified perspective on the respective algorithm biases. Theorem 4. RM is the solution of the following constrained optimization, inf
2 0 s.t. MO R R+NNO,
(16)
OER
and GTD is the solution of the following constrained optimization, =0
inf 0112 BER
S.I. MO R + ~N0,
(17)
That is, the convergence points of RM, TD and FVI in the overparameterized case can all be seen as minimizing the Euclidean norm the weights 0 subject to satisfying the Bellman constraints M0 R + NNO, where TD and FVI implicitly add the additional constraint that I 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 iterative procedures for solving particular form of quadratic program, when they converge. Of course, proper constrained optimization techniques would be able stably compute solutions in scenarios where TD FVI diverge (Boyd and Vandenherghe, 2004), but a more direct way to ensure convergence is implied by the following corollary. Corollary 1. OTD also the solution of the following constrained optimization,
inf 2 1110112 OER
MO R + NNIMM
(18)
Note that the right hand side of the constraint simply pre- projectoees next state value predictions onto the row space of M before determining the Bellman backed up value. This allows novel objective to be formulated whose minimizer recovers the same fixed point as TD,
MSCBE(()
+
10
(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 θYD. which is essentially equivalent to applying RM to corrected target values while ensuring stability. Note also that in the linear case the projection matrix I only needs to be precomputed once.
4.2 VALUE PREDICTION ERROR BOUNDS
One can also establish generalization bounds 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. Ler Σ = M D&M be the empirical covariance matrix, and 0, be the output of FVI starting from Ou defined in Theorem 3. Then for any 0 E arg mingeR" E(0). E(O.) E(0")
S (E)
(( + + | [mmwyl]]'+ +|(
| 1100 - 0011²) + 110011 -
(20)
where [ II 10 and HH P)
Intuitively, E measures the length of next-state features along the direction 0-, and or is the expected value prediction error under the empirical transition model, which can be bounded using standard

---

Published as a conference paper at ICLR 2022
concentration inequalities. The proof of this theorem is given in Appendix A.5. Observe that for any step t 2 1, the output of FVI 0, is within the row-span of M. This allows one to decompose the prediction error into component within the row-span, controlled by leveraging the core matrix linear operator Tw, and an orthogonal component that can be bounded by (0=1
Under the convergence conditions of Theorems 2 and 3, we also have the following generalization bound for the value prediction error of OTD.
Corollary 2. Suppose that || < 1, and the value of any s E S is bounded by v(s) E [0, Umax] For any 0r garg sirgmnnges {(),,
E[E(OTD)] - y >log([S16))
Pumin EE Ei [2)[( -) 7) + 47 + d'maxx
(21)
EiAmin (1)(( 7)
where Amin min ((s) 3) 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 Szepesvá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 kAmin Σ) and Rmmin mmin [ 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 when | 2 1/7, 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 0" with respect to M (approximation error).
The smallest eigenvalue of the empirical covariance matrix E[Amin [. well as the length of the orthogonal components =1100"12.--ax] 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 to an algorithm that directly optimizes MSCBE. Although solution of Eq. (18) must exist, its value prediction error can be arbitrarily large given that ||W] 2 1/7. This also connects to a similar result for the TD fixed point that minimizes MSPBE in the underparameterizedd regime (Kolter, 201 l).
REGULARIZERS FOR DEEP REINFORCEMENT LEARNING ALGORITTMS
For tractability, the theory in prior sections assumes fixed representations with a linear parameteriza- tion 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 values with 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, Qu is trained by TD learning that minimizes the objective E.a (r(s, a) au+7Qu a) a)), where (w, a) is known as the target network to increase the learning stability. We view Q. as a two part-approximation with w = (ò.0). 0). where the output of the penultimate layer is referred as the feature mapping 6, the weight of last fully connected layer is referred as 6, and the Q-function is approximated by Qs a) ø(s a) TO 8. Our goal is to define regularizeers on & and that can be effectively applied to practical algorithms.
The first regularizer directly takes inspiration from Theorem 4: by restricting the linear weight 0 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 0,
Rs | 11
(22)
In practice we compute this regularizer for each minibatch of data. The projection step is computed by least squares algorithm with an additional l regularization for numerical stability.
8

---

Published as a conference paper at ICLR 2022
(a) Reacher
(b) Acrobot
(c) Cartpole
(d) Pendulum
We show the results with proposed regularization compared to the baseline algorithms. The algorithms are trained using fixed offline data set collected by random initialized policies. The x-axis shows the training iterations (in thousands) and y y-axis shows the performance. All plots are averaged over 100 runs. The shaded area shows the standard error.
Figure 2:
The second regularizer designed address the effect of the feature representation on convergence and value prediction error. In particular, Theorems 2 and 3 show that TD and FVI converge if the spectral norm W be upper bounded by 1/7, which by Theorem 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 involves differentiation through matrix pseudo inverse. We instead propose alternative regularizer inspired by the geometric interpretation of the core matrix Eq. (13): recall from Fig. that W can be viewed the weights that project N onto the row space of M. To ensure that arbitrary feature vector can be well approximated using W, it would be ideal if M was orthonomral, which would imply an beehave basis represent N. This intuition justifies the following regularization:
R₂ = 3L - M D&M
(23)
where 3 a scale parameter designed to approximate the column norm. That the regularizer forces the neural network to learn an orthogonal feature embedding by normalizing the empirical feature covariance matrix. The gradient of Rs can also approximated using mini-batches. We augment the original learning objectives by adding both R. and R. weighted by hyper-parameters.
5.1 EMPIRICAL JUSTIFICATION OF REGULARIZERS
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. 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 this analysis. For the discrete action environments, we use DQN (Mnih et al., 2015) as the baseline QT-Opt (Kalashnikov
algorithm add regularizers. For continuous control environments, et al., 2018) as the baseline algorithm, which is an actor-critic method that applies the cross-entropy method perform policy optimization. Our modifications add R. and Rg 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 the proposed 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, modification was able fully close the gap between RM and TD. On Cartpole, (where vanilla RM dominates vanilla TD), and on Pendulum, the regularizers also deliver significant improvements to the TD learning bascline and modest improvements to the RM baseline.
CONCLUSION
We have investigated the fixed points of classical updates for value estimation in the overparameterized given data set. We
setting, where there sufficient capacity to fit all the Bellman constraints 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 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 interesting direction for future investigation.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENT
The authors would like to thank Mengjiao Yang, George Tucker, Ofrr Nachum and Aviral Kumar for insightful discussions and providing feedback a draft of this manuscript. Dale Schuurmans gratefully acknowledges funding from the Canada CIFAR Al Chairs Program, Amii and NSERC.
REFERENCES
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards characterizing divergence in deep Q-learning. arXiv preprint arXiv: 1903.088999 2019.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural complex- ity and representation learning of low rank MDPs. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Mare G. Belle- mare. Deep reinforcement learning at the edge of the statistical precipice. arXiv preprint arXiv:2108. 13264, 2021.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In International Conference Machine Learning (ICML), pages 30-37, 1995.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint. arXiv preprint arXiv:2103.09177 2021.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical varianee trade-off. Proceedings the National Academy of Sciences, 116632):15849-1 5854, 2019.
Marc G. Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C. Machado, Subhodeep Moitra, Sameera Ponda, and Ziyu Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588:77-82, 2020.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory (COLTT), pages 1691-1692, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge U Press, 2004.
Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1):33-57, 1996.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scout Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Diogo Carvalho, Francisco S Melo, and Pedro Santos. A new convergent variant of Q-learning with linear function approximation. In Advances Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Jinglin Chen and Nan Jiang. Information-theorede considerations in batch reinforcement learning. In International Conference on Machine Learning (ICML), pages 1042-1051, 2019.
Bo Dai, Niao Hc, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. In Artificial Intelligence and Statistics, pages 1458-1467. PMLR, 2017.
Gal Dalal, Balázs Szöréni, Gugan Thoppe, and Shie Mannor. Finite sample analysis for TD(0) with function approximation. In AAAI Conference on Artificial Intelligence (AAAI), pages 2144-6160 2018.
10

---

Published as a conference paper at ICLR 2022
Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 13:809-8888 883, 2014.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pages 1049- 1058. PMLR, 2017.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off off-policy evaluation with linear function approximation. International Conference on Machine Learning (ICML), pages 2701-2709 2020.
Damien Ernst, P. Guerts, and L. Whenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
Mattheiu Geist, Bilal Piot, and Olivier Pietquin. Is the Bellman residual a bad proxy? In Advances in
Neural Information Processing Systems (NeurIPS), volume 31, pages 3208-3217 2017.
Dibya Ghosh and Mare G. Bellemare. Representations for stable off-policy reinforcement learning. In International Conference on Machine Learning (ICML), pages 3556-3565, 2020.
Geoffrey J. Gordon. Stable function approximation in dynamic programming. In International
Conference on Machine Learning (ICML), pages 261-268, 1995.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference Machine Learning (ICML), 2018.
Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse feature selection makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning (ICML), 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 8571-8580, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Journal of Machine Learning Research, 125:1-7, 2020.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang. Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. QT-Opt: Scalable deep reinforcement learning for vision-based robotic manipulation. arXiv preprint arXiv: 1806. 10293, 2018.
Zico Kolter.
The fixed points of off-policy TD. In Advances in Neural Information Processing Systems (NeurIPS), volume 24, pages 2169-2177, 2011.
George Konidaris, Scott Nickum, and Philip S. Thomas. TD,: Re-evaluating complex backups in temporal difference learning. In Advances in Neural Information Processing Systems (NeurIPS), 2011.
volume 24, pages
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 25, 2012.
Aviral Kumar, Rishabh Agarwal, Dibya Ghosh, and Sergey Levine. Implicit under- parameterizaationn inhibits data-efficient deep reinforcement learning. In International Conference on Learning Representations (ICLR), 2021.
Ilja Kuzborskij. Csaba Szepesvári, Omar Rivasplata, Amal Rannen-Trike and Razvan Pascanu, On the role of optimization double descent: A least squares study. arXiv preprint arXiv:2107.12685, 2021.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In ICLR, 2016.
11

---

Published as a conference paper at ICLR 2022
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient TD. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 504-513, 2015.
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Proximal gradient temporal difference learning algorithms. International Joint Conference on Artificial Intelligence (IJCAI), pages 4195 4199, 2016.
Daniel J. Lizotte. Convergent fitted value iteration with linear function approximation. In Advances in Neural Information Processing Systems (NeurIPS), volume 24, pages 2537-2545, 2011.
Tyler Lu, Dale Schuurmans, and Craig Boutilier. Non-delusional Q-learing and value iteration. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, pages 9971-9981, 2018.
Hamid R. Maei, Csaba Szepesvári. Shalabh Bhatnagar, Doina Precup, and David Silver. Convergent cinporal-difference learning with arbitrary smooth function approximation. In Advances in Neural Information Processing Systems (NeurIPS), volume 22, pages 1 1204-1212, 2009.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-333 2015.
Rémi Munos and Csaba Szepesvári. Finite time bounds for sampling based fitted value iteration. In International Conference on Machine Learning (ICML), pages 880-887,44 2005.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parameterization in generalization of neural networks. International Conference on Learning Representations (ICLR), 2019.
Ronald Parr, Lihong Li, Gavin Taylor, Christopher Painter-Wakefiele and Michael L. Littman. approximation, and feature selction for rein-
An analysis of linear models, linear forcement learning. In International Conference on Machine Learning (ICML), pages 752-759, 2008.
Gandharv Patil, L. A. Prashanth, and Doina Precup. Finite time analysis of temporal difference learning with linear function approximation: the tail averaged case. 2021.
L. A. Prashanth, Nathaniel Korda, and Rémi Munos. Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling. Machine Learning, 10(3):559-618, 2021.
Bruno Scherrer. Should one compute the temporal difference fix point or minimize the Bellman residual? In International Conference on Machine Learning (ICMI), 2010.
John Shawe-Taylor Christopher KI Williams, Nello Cristianini, and Jaz Kandola. On the eigen- spectrum of the Gram matrix and the generalization error of kernel-PCA. IEEE Transactions on Information Theory, 51(7):2510-255 2522, 2005.
Zhao Song, Ronald Parr, Xuejun Liao, and Lawrence Carin. Linear feature encoding for reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 2016.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19:1-57, 2018.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3 (1):9 44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems (NeurIPS), volume 12, 1999.
12

---

Published as a conference paper at ICLR 2022
Richard S Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent O(n) algorithm for off-policy temporal-differeen learning with linear function approximation. In Advances in Neural Information Processing Systems (NeurIPS), volume 21, pages 1609-1616, 2008.
Richard S. Sutton, A. Rupam Mahmood, and Martha White. An emphatic approach to the problem of off-policy temporal-difference learning, Journal of Machine Learning Research, 17:1-29, 2016.
Csaba Szepesvári and Rémi Munos. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Csaba Szepesvári and W. D. Smart. Interpolation- based Q-learning. In International Conference on Machine Learning (ICML), pages 100-107, 2004.
Gavin Taylor and Ronald Parr. Kernelized value function approximation for reinforcement learning. In International Conference on Machine Learning (ICML), pages 4214-4226, 2009.
John N Tsitsiklis and Benjamin Van Roy. Srature-based methods for large scale dynamic program- ming. Machine Learning, 22(1):59-94 1996.
John Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions Automatic Control, 42(5):674-699 1997.
Hado van Hasselt. Double Q-learning In Advances in Neural Information Processing Systems (NeurIPS), volume 23, 2010.
Hado van Hasselt, Yotam Doron, Florian Strub. Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep reinforcement learning and the deadly triad. arXiv preprint 1eXiv:1812.0220 2018.
Ruosong Wang, Dean Foster, and Sham Kakade. What are the statistical limits of offline RL with linear function approximation? In International Conference on Learning Representations (ICLR), 2021a.
Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham M. Kakade. Instabilities of offline RL with pre-trained neural representation. In International Conference Machine Learning (ICML), pages 10948-10960, 2021b.
Wentao Weng. Harsh Gupta, Niao He, and Lei Ying. The mean-squared error of double Q-learning. In Advances Neural Information Processing Systems (NeurIPS), 2020.
Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. On the sample complexity of batch reinforcement learning with policy-induced data. arXiv preprint arXiv:2106.099) 2021.
Lin F. Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning (ICML), 2019.
Zhuoran Yang. Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I. Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Huizhen Yu. Convergence of least squares temporal difference methods under general conditions. In International Conference on Machine Learning (ICML), pages 1207-1214, 2010.
Huizhen Yu. On convergence of emphatic temporal-difference learning. In Conference on Learning Theory (COLT), pages 1-28, 2015.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning. International Conference on Machine Learning (ICML), pages 12287-12297, 2021.
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with target network. International Conference on Machine Learning (ICML), pages 12621-12631, 2021.
13

---

Published as a conference paper at ICLR 2022
Appendix
A PROOFS
A.1 PROOF OF THEOREM 1
Theorem (Restatement of Theorem 1). Let 80 E R the initial weight vector: With 17 S [1+7]*
RM converges to 0RM = (M -7N)² R + (Ia II 11M--NN IM--N)
Proof. Let = M yN for simplicity. First recall the residual minimization update,
8+11 = (Ia n 4x 0, + nA R. Let 6* A'R. It can be verified 0" is of the feasible solution as A R. Then we induction to show that for any On E T2d and 2 0
(24)
1,+1 - 0 = (1 T Dz -7).
(25)
The base case holds by the update rule Eq. (24). Suppose that the statement holds for I, then we have
Det1 0r (Ia T D A) O, + 7 D 0*
(26)
(Ia TA D A) 0, (La - D A)
(27)
(Ia TA D& (8. - -8")
(28)
=(Ia - 7A D&
1+1 (0p -0").
(29)
Thus,
0111 (Ia 7A + 8, + (Ia (Ia nA D
(30)
let VAVT its eigendecomposition of A DzA, which the empirical covariance matrix of residual features. Let V_ be the null space of V. Then
Ia (Ia A DRA)*+
(31)
=I, (VV VVAV V. VT
(32)
=Ia (V(I - DAYV + +V
(33)
=I (V-VT)* V(I. -
(34)
-VVT - -V( -
(35)
=V (I+ - -(Ia - V
(36)
Let Amax the largest eigenvalue of A A.A. We now show that Amax $ 1147.
Xmax (A < Σ (ass) (((s)) - (((s)) ro(())) < (1++))
(37)
1=1
where we use the fact that Amax is convex function and we assume ||((s)] < for all s E S. Thus,
given that 7) < T 71 5 Tamax. Then la (Ia TA" Ax (+1 VV as + oo. Thus
lim 0 = lim (La - 7 D 0. VV 0" lim (Ia 7A D.A) 8- 0o + 0 t-000 to
(38)
+000
where the last equality follows by that 8* is in the row space of A by definition. When 6n = 0, we have the algorithm converges to 0*.
14

---

Published as a conference paper at ICLR 2022
We next show the result for general 0y. Let 8g 0 o.. where 0 = IIM-NOO is the component of Oo that is in the row space of A, 0g = (Ia MM is the perpendicular residual. Then,
lim P1 n D&
(39)
1-000
lim
(V V T + V 7
1 V (00 + 0
(40)
0
+
lim V - - t-000
06 0b.
(41)
where the last step follows by the choice of 1). This finishes the proof.
A.2 PROOF OF THEOREM 2
We will need the matrix binomial theorem in the proof.
Lemma (Matrix Binomial Theorem). For 2 0 and two matrices X, Y
x
(42)
Proof.
(I+ X
12 k
(XX)x
X
11
(YX)* = x(1+Xx))"
(43)
k
k=0
k=0
Theorem 7 (Restatement of Theorem 2). Assuming that M D ~N) is diagonalizable Let On E Rdd be the initial weight vector. With < (I+9)] o/ if | < 2 TD(0) converges to
Omn = M (I= - R + 3, where 3 = QoQ Qo are eigenvectors of M ( NN with zero eigenvalues. If W 2 there an initial f for which TD(0) does not converge.
Proof. We first rewrite the TD update formulate
8+11 = (Ia - nM Dz(M - -N))0 + n D&R
(44)
A simple recursive argument shows that for any On RR.
Oe-11 -Ia- - -1M Da(M - 00 + (1a-nnM DMM D.R.
1=0
(45)
By the matrix binomial theorem (Lemma 1). (Ia TIM Dr (M By writing N as the projection to the row-span of M and the perpendicular component, we have
>N))' M D M T 7(M -NNM T
Dz)².
(46)
(M 7N)M
(47)
-(M 7N M - NN M
(48)
=(T -WWMM
(49)
where the last step follows by ( M = 0. Thus we can rewrite 0 as
O1-1 = (1a= -M DM + + DE
Eu, - - D&Y'R (50)
1=0
= =IIa- D& - + Di. Σ (Ix n - D.)RR
(51)
15

---

Published as a conference paper at ICLR 2022
Given [W| 1/7, we have that all eigenvalues of I wW are positive. Let n (1+7)110:]
1 then
IIn(4x - WW) D&ll nll(Ia -odd=->WWa - DEll < <1,
(52)
otherwise the matrix power series diverges. Thus
nM T D&
Ed n(I WMMM D&) M (W])= R.
(53)
2=0
Therefore, given that 0g = we have the algorithm converge to (1+ - W R.
We now show the convergence point for arbitrary 0o. Let QAQ be the eigen decomposition of M D yN). By the low rank structure of this matrix, it has at most h S h non-zero eigenvalues. Let Qu be the eigenvectors with eigenvalue zero. Then
lim (La nM D& DMMM- - 7 1-000
(54)
lim nA)e (A Q
(55)
QQ 6u.
(56)
where the last step follows by the choice of 1/.
A.2.1 CHARACTERIZATION FOR NON-DIAGONALIZABLE CASE
In the above analysis, we assume that the matrix M D& - >N) is diagonalizable. We now characterize the convergent point for the general case using Jordan normal form of the matrix. Let
Z = M D - >N) and Z QJQ be the jordan normal form of Z. We still denote Qo
eigenvectors with eigenvalue zero. Then there
lim (I Z) lim t-000
(57)
+000
Since J has block diagonal structure, its power can be obtained by first computing the power of each block. Let Jj be the jordan block with eigenvalue X; We write J; = X + L, where L is matrix such that the only non-zero entries of L are on the first dif-diagonal. Then we can write the i-th block of J as (1 n),:) I L,L Using the binomial theorem we get
-
Σ (ii1-n.)"
(58)
Note that L is the matrix with ones the 3-th diagonal away from the main diagonal, and L 0 for larger than the size of L. Therefore, the main diagonal, -1 111;)=11 on the first off-diagonal, and so on. Therefore, the eigenvalues of this matrix are all (1 n),,)" Then given a learning rate that v < 1/Amax. for any jordan block with A O, we have that the matrix power converges. For X; O, the jordan block corresponds to eigenvectors that are in the kernel space of Z. Thus, suppose that all eigenvalues of Z are non-negative, have
(- is a triangular matrix with (1-7)A,) on
lim QI-- 0, Q0Q5 0
(59)
Note that if negative >; exists, the above derivations still be used to characterize the convergent sub-component of Op. The non-convergent sub-component of 0g will diverge with an exponential rate shown above.
A.3 PROOF OF THROREMS 3
Proof. We first prove the update formula. Recall the FVI update,
0: M (R No..1).
16

---

Published as a conference paper at ICLR 2022
Fort t = 1 the result holds by definition. Suppose that
0, M
(60)
We now prove the result for t + 1 by induction.
0++1 = (R
(61)
T- 2
M
R+
(
(62)
1=
M
R+ Σ
(63)
= M
(64)
Clearly the convergence of this algorithm depends on the spectral norm of N M In particular, given that || M'M < 1/7, we have the algorithm converges to
M - W
(65)
as t + co. This finishes the proof.
A.4 PROOF OF THEOREM 4 AND COROLLARY
Proof. We first prove the result for residual minimization fixed point FRM- The proof is adopted from characterizing the minimum norm solution of solving least square (Boyd and Vandenberghe, 2004).
Let A M -N for simplicity. We write the Lagrange of the optimization problem.
1 2
a(0,a) inf sup 1110 + aTaR (RTRRR- A0)
(66)
BE aeRt
sup -
IA all2 +a R a AATa
(67)
OCR
sup a
T R a AATa. a.
(68)
aERt
Solving for and add to 0" A a gives that 0- A'R. We next prove Corollary 1, which characterizes the TD and FVI fixed point OTp. Let W NM
We write the Lagrange of the optimization problem,
1 a() = inf sup |00 + a (( (I+ WW)
(69)
BER" aeRt
2
M (I) aal2 + R (WM -I= (70)
sup
aeRt
sup a R aE
a T (Is WWMMM
(71)
Solving for a' and add it 8" = M (I, - WT a second part of Theorem 4 is immediately followed by this.
a gives that 0" = M -
R. The
A.5 PROOF OF THEOREM 5
Lemma 2. Let O2 be the output of FVI at iteration with 8g as the initial parameter. We have that M MO, O2 for any i. 1.
17

---

Published as a conference paper at ICLR 2022
Proof. The claim is implied by the fact that 0, is in the row space of M. In particular, by Theorem 8, = M for some a E IR.. Thus,
M MMM - 0..
(72)
This finishes the proof.
Lemma 3. E(0) is I-smoothness.
Proof. Recall the prediction error of 0 E IRd
{ 2 20 - -olo- --110 - 0'
(73)
where = -== DD The gradient of is (0) = 200 - )¹ Then
[1)((0)) - (02)) = |=[(0] - 02)1 I Amax (2) (1(0 - 02)1 < 10: 021
(74)
where we use ||o(s)]| - 1 for all S and Xmmax (2) - E, u(s) max (o(s)((s) (m(s)))) T) s
0
Lemma 4. Let Eapp
NII M and stat H(P P) We have
M0 R + (5app + Estor) + MO'
(75)
Proof.
Using the definitions we have,
M0 R + HH PD0
(76)
RR+NNN NN + HP - P)80"
(77)
RR+ (W NTM + +HH(P P)00
(78)
R + (Eapp + Estat + WW*
(79)
Proof. By Theorem 3, - (R NN,) is the output of FVI at iteration By noting that E(0)) = 0 and Lemma 3, for any 0 E Rd.
1
E(O) - ||0 1-1 = 2
|0 1 M + -10 -0 -0-
(80)
We first consider the second term. By Lemma 2.
10 f M = (0. - T (Ia 1--Min
M M) (0, -0") =100"1
-
TT-MMMM MMM
(81)
We now consider the first term. By Lemma 4,
M(0' 02) = M0 T (R+ (R+;NO,)
(82)
W)) (R ((Epp + smm) + (:W)- Σ
(N+7N0)
7No,)
1=0
(83)
=7 W''Yean Sapp Σ (-W) -01 -0)
(84)
Let Let M D& M be the empirical covariance matrix. Note that Amin (M M)/k 2 Amin (E). To
show this, let D diag k 1)) and M USVT be the SVD of M. Then
At DM) min x M DMr ||
(85)
min a T SU DUS ||||==1
(86)
min a T SUT DaUSa ||||=|
(87)
X (M D&M)
(88)
18

---

Published as a conference paper at ICLR 2022
where we replace
Va since V are orthonormal bases, and min [6] Ps S 1/k. Therefore,
| 1/v Atain (MiM) S 1/v
1// k (E))
Combining the results above we have,
1|0, - 0 M
( - 0-)1²
(89)
|| (0, 00) )|(
(90)
Σ (s + Estar) + (2W)--1N(0 (1(0'-0)
-0)
(91)
idmia (
4ry
(6² +22)
Σ (nw))
[-1
+ 11( - 1-1
kdmin (Σ)
1=
(92)
Combine this with Eq. (81) finishes the proof.
A.6 PROOF OF COROLLARY
Proof. Recall that in the proof of Theorem 5 we have
||0, - 1 Admin (Σ)
47
(6² (z))
EGwyy
+ +1 1611//00
0-11
1=0
(93)
Given that W|| < 1, we have for the fixed point 6co.
(E + k:minn ()) 7)2
110, 00 11a I
(94)
We first consider a² HP P)ul12 By Hoeffding's inequality and union bound have with probability at least 1 6, for any E supp(
log([S)/a 2n(s)
(P, - P.) o 1 7
(95)
Thus, 1et Ruin = min (n)) rass,, we have
o²
log((81/0)
(96)
2(1 2
Now we consider e² = | 11. Since NII is perpendicular to M, and all features have norm bounded by one,
82
S 110
10
(97)
h
Combine the above we have,
1 {())= < 0 0'
+ 2
110012 Mi 10-M
(98)
2
24
1og(1S1/6)
1 10'12 MMM
+ 110-11 M
(99)
Amin (E)(1 - 7)
2((1 2
7 [log(
47
110"|17,- MiM
||0'
(100)
Amin (1)(( - 4 Amin
(1
Finally, using the tower rule gives the desired result.
19

---

Published as a conference paper at ICLR 2022
A.7 CONCENTRATION OF EIGENVALUES AND BOUNDING THE ORTHOGONAL COMPLEMENT
We will need the following result (Kuzborskij et al., 2021, Theorem 6), which is concerned with the magnitude of projection (Shawe- Taylor et al., 2005, Theorem 1)
the eigenspace of covariance matrix. The result is based on
Lemma 5. Let E. = E E x. be the covariance malrix iid. data x2 Rd. Denote the h- b-"tail" of eigenvalues of a covariance matrix E = as
A
Σ
A
(101)
i=h+1
Let Uy be the first eigenbasis for E [n)] Then for any R with probability at least 1 - 6,
1 Vh
2 n
18
2n
E
min hE
|
1
In
(102)
n2
vn
n
n
8
The next lemma gives -onasyyptooiic result to understand the behaviour of Xmi (Kuzborskij et al., 2021, Lemma 1).
Lemma 6. Let X (Xi,..., Xa) Ruxx be random matrix with i.i.d columns, such that max; |X ll S K, and let E XXT
T /n, and E E[x, Then, for every 2 0, with
probability at least - aa, we have
x+ min ($) 2 A (E)
II-K²
c1
for n dd,
(103)
and furthemoree,, assuming that |Xills = Vd, for all i [n], we have
(v==
x² (c( ( /=
2
Min (2) min (2)
for d,
(104)
where we have an absolute constant /19
B EXPERIMENT SETUP
In this section, we provide additional details about the experimental setup and parameer used for each of the environments. For all of these environments the regularization weights were considered tunable considered parameter to be tuned in order to approximate the feature matrix norm.
addition, for Rs (see Eq 23), the scale factor B was also
B.1 ACROBOT
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 le-3.
Regularized RM with weight of 2c-2 on Ry and Ic-4 on Rw.
Regularized TD with weight of 0 on Rs and le-4 on R...
B.2 REACHER
Replay buffer with 10k tuples sampled from a random policy across trajectories with maximum steps per episode of length 50.
20

---

Published as a conference paper at ICLR 2022
Learning rate le-4.
A value network for the continuous action inputs with a fc observation layer with params (50,), fe action layer with params (50.) and a joint layer with params (100.).
Batch size 64.
Gradient clipping with norm of 10.0
Regularized RM with weight of 0.15 on Re and 0 on Rig.
Regularized TD with weight of 2c-2 on Ry and 7e-3 on Rg.
B.3 CARTPOLE
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 Re and O R.p.
Regularized TD with weight of 1.5e-3 on Re and 5e-3 on R.g.
B.4 PENDULUM
Replay buffer with Ik tuples obtained by sampling directly from a fixed initial state distribu- tion using random policy.
A value network for the continuous action inputs with a fc observation layer with params (50,), fe action layer with params (50.) and a joint layer with params (100.).
Batch size 64.
Learning rate le-3.
Regularized RM with weight of 1.0 on R., and 5.4e-4 on Rs--
Regularized TD with weight of 0 on Rn and 1.0 on R.s-
B.5 EXTRA EXPERIMENT RESULTS
We provide extra experiment results on four Mujoco control problems to assess the applicability of the proposed regularization Rg: HalfCheetah, Hopper, Ant, and Walker2d. The results are provided Fig. 3. All results are averaged over 100 runs with different random seeds. The hyper-parameters 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 {le 4, 1e - -3, 3e 2, le 1,1]
21

---

Published as a conference paper at ICLR 2022
(a) HalfCheetah
(b) Hopper
(c) Ant
(d) Walker2d
Figure 3: We show the results with proposed regularization compared to the baseline algorithms. The algorithms trained using fixed offline data set collected by random initialized policies. The x-axis shows the training iterations (in thousands) and y axis shows the performance. All plots are averaged over 100 runs. The shaded area shows the standard error.
22


Reviews:
[{"review_id": "cxqmoJNT2ip", "reviewer": "Reviewer_xq3y", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Summary:\nIn this paper, the authors investigate the convergence results of three algorithms (RM, TD, and FVI) in OPE when the model is assumed to be over-parameterized linear function class. Besides, some empirical experiments are also conducted. But as I’m not a fully expert in empirical RL, I would not have any comments on the experiment part. To my opinion, the contribution of this work is not solid enough, even some results might be wrong. Please check the following parts.\n\nQuestions:\n1.\tThis paper is claimed to understand over-parameterized model in OPE. However, after I read this paper, I’m still confused as there is no theoretical comparison between over- and under-parameterization cases. Besides, I also can’t learn from Thm 5 whether the size of model (d in this paper) has an effect on the learning process. Thus, I would be much appreciated if the authors could have a clear explanation of the motivation.\n\nErrors:\n1.\tEquation (38), as t already goes infinity, RHS should be free of t.\n2.\tEquation (42), it should be $\\theta_t$ at RHS. Thus, the recursive expression (43) is also wrong. (no effect on results I guess)\n3.\tAt the bottom of page 15, it mentions that $M^\\top D_k(M-\\gamma N)$ can be eigen decomposed. Please explain why? To my knowledge, it’s not symmetric. And I think this would definitely have an impact on your results.\n4.\tIn the proof of Corollary 2, Hoeffding’s inequality is applied to bound $\\varepsilon$ and $\\sigma$, and then taking an expectation over both sides in (97) without considering the high probability term $1-\\delta$ when applying the Hoeffding’s inequality. I think this is definitely wrong.\n\nRecommendation:\n1.\tTo my opinion, the term ‘over-parameterization’ is confusing in this paper. To my best acknowledgement, the basic structure of an over-parameterized model is assumed a two-layer model, though a linear model is ok but not just enough. \n2.\tAppendix A.7 presents two lemmas to control the expectation term in Corollary 2. Please give readers exact form in your case not just present its original form.\n3.\tI think an improvement on writing is necessary. There are a number of grammatical problems and the language is not precise enough. Please have proofread.\n", "summary_of_the_paper": "See main review.", "summary_of_the_review": "See main review.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TB7XATD_ahr", "reviewer": "Reviewer_PSbG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In the reinforcement learning literature, numerous algorithms exist to learn the value function based on bootstrapping and in presence of function approximation. Chief among these algorithms are (linear) temporal difference learning and the residual gradient. These two differ slightly in terms of the objective functions (MSPBE vs MSBE), but it is known that this small difference can manifest itself significantly in practice. The commonly held intuition is that the TD algorithm has a superior fixed point, so eventhough Maei showed that TD is not following the gradient of any objective, it is preferred to residual gradient in practice. The soundness of residual gradient is also overshadowed by its need for double sampling to combat the bias that would otherwise be present.\n\nOne may intuit that the difference between the fixed point of the two approaches may not carry over to the setting with sufficiently rich feature space, which is the central question of this paper. The paper shows that indeed even in the overparameterized setting, the two approaches may result in different fixed-points. More specifically, each approach can have numerous fixed-points and convergence to a particular fixed point depends upon the initial weight vector, but that crucially these fixed points are different on a per-algorithm basis. This makes sense. After all, the parameter vector is trained to predict different things in each case: value function in TD, and temporal differences in residual gradient.\n\nOverall, reading this paper really excited me, eventhough sometimes it felt like that the paper is purposefully making the math to look more difficult than it needs to be. It is certainly very interesting to study the fixed point of different approaches in settings that more closely resemble the common practice in which people use extremely powerful function approximators.\n\nGetting to the core of the results, I have noticed a few issues worth mentioning:\n\n- The fixed point in theorem 2 is in fact extremely similar to equation (2) from [1]. The newly introduced variables make it less obvious to see, but after plugging in the relevant quantities, one can see that things cancel out and lead to a solution very similar to what i noted, and the paper itself does note in equation (7). This result is still novel and does generalize to the underdetermined case, but I don't feel great about the paper not giving enough credit to [1] in the context of this result.\n\n- The result branded as theorem 4 is really trivial. In particular, this is nothing but the least norm solution for underdetermined equations. See for example: https://see.stanford.edu/materials/lsoeldsee263/08-min-norm.pdf. Again, branding this as a theorem and not giving credit to people who first came up with this result is not a great practice.\n\n- What's even more surprising, the Proof of theorem 4 in the appendix, which is just a copy of the existing result from the convex optimization literature, includes several mistakes. For example, as written $L(\\theta, \\alpha)$ is not a function of $\\theta$ nor $\\alpha$! It is in fact constant with respect to these variables. I think authors meant to compute $\\inf_\\theta \\sup_\\alpha L(\\theta,\\alpha)$ and refer to the objective as $L(\\theta,\\alpha)$. In any case, as written, this gives the wrong impression that this result is first derived in this work, but this is just a trivial result in convex optimization as I mentioned above.\n\n- Less severe issue, but In equation 38 in the Appendix, it seems like that t+1 should actually be $\\infty$?\n\n- While I think the studied setting is very interesting, I don't quite see the connection with deep RL. In deep RL, it is not that the number of features are extremely large, therefore the last layer is solving an underdetermined problem. It is more that all but the last layer are jointly learning a basis function given which it is very easy to fit the value function using linear function approximation. For example, the last layer of DQN is comprised of 256 features, yet on a given game the support of the stationary distribution is vastly larger than 256 in light of the combinatorial nature of most games, how do you square your relating the setting to deep RL with my observation?\n\n- I am also not sure I learned a lot from the experimental sections. Domains are pretty toyish and experiments are not well motivated. Also, the figures and their captions look pretty small. In light of the theory it is OK to not have a significant empirical contribution, but at this point, its debatable if the experiments are adding something or actually degrading the paper.\n\n\n\n[1] Parr and friends, \"An Analysis of Linear Models, Linear Value-Function Approximation, and Feature Selection for Reinforcement Learning\"\n", "summary_of_the_paper": "This paper studies the fixed point solution of standard model-free value-function optimization algorithms in RL (in particular TD, residual gradient, and Fitted Value Iteration) in the over-parameterized setting, meaning that the problem is underdetermined and can generally admit numerous optimal solutions. Importantly the paper shows that the different fixed points of TD and residual gradient in the limited-capacity case carries over to the over-parameterized setting as well.", "summary_of_the_review": "As mentioned above, I am excited about this paper in light of the importance of studying TD and related algorithms in settings other than standard under-parameterized settings. The demonstrated scholarship, or lack thereof, gives me doubts, but overall I like this paper and lean towards the acceptance side.\n--\npost rebuttal: I think this paper makes a respectable contribution to the theory of temporal difference learning. I believe authors will address my concerns, so I like to see this paper accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "E77k2ZiMCeA", "reviewer": "Reviewer_gT5o", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. This paper is concerned with the overparameterized linear representations of TD, FVI, and RM. The paper is easy to follow and digest. The overparameterized representation problem is a crucial problem. On the downside, the linear case is restricted, and technical analysis is not very novel. I have some high-level comments as follows.\n\n2. The paper discusses the unified view of overparameterized linear representation. Does such view also hold for the underparameterized linear representation? If not, is there any intuition that why we would have such difference?\n\n3. For the overparameterized problem, I think non-linear representation like deep neural network is more common and interesting. Although the linear representation result in this paper is new to me, it is too restricted. Usually we would not use linear function approximation with lots of parameters, therefore I feel the result in this paper has limited impact. Is it possible to extend to neural network with Relu activation?\n\n4. Related to the prior point, I suggest the authors to add some discussions about the related work of overparameterized NN theory, e.g., NTK.\n\n5. This paper defines the update equation for the underparameterized form (5,6) and says the equation for the overparameterized case (10,12) can be directly obtained. Can you provide some details of the derivation?\n\n6. Is there any relationship between the solution of TD, FVI, and RM with overparameterized linear representation and the overparameterized linear regression?\n\n7. What is the intuition to define D matrix in proposition 1?\n\n8. Is there any interpretation of operator M, N, and R in the overparameterized regime? It seems that they can be obtained by pre-multiplying H matrix from the original operator for the underparameterized case? If so, why pre-multiplying H would be useful here?\n\n9. For the overparameterized regime (theorem 4), it seems that the difference between TD/FVI and RM is that the convergence points of TD/FVI further constraints that \\theta must lie in the row span of M. This is quite similar as the interpretation that TD/FVI is the solution of MSPBE while RM is the solution of MSBE (see ref) because the objective of MSPBE and MSBE are quite similar and they only differ by a projection operator. This projection operator is similar as the forcing \\theta to lie in the row span of M. Is my understanding correct?\n\nRef: Policy Evaluation with Temporal Differences: A Survey and Comparison\n\n10. In the theorem statement, it is mentioned that the algorithm will not converge if the norm is large. Could you provide more discussions about the implication?\n \n11. The font size in the figure is too small.", "summary_of_the_paper": "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.", "summary_of_the_review": "This is a theoretical paper about the overparameterized linear representations of TD, FVI, and RM. This is an interesting question. On the downside, the linear representation might be too restricted and the technical contribution is not significant.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5adU68CmhsU", "reviewer": "Reviewer_KksW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\nOverall, this paper provides a novel perspective to reveal the implicit bias behind these classical value estimation algorithms, which is something that cannot be observed in under-parameterized case. The proposed regularizers are based on the weaknesses revealed by previous theoretical analysis and show good performance in experiments.\n\n### Weaknesses\nOne of my major concerns is about the setting used in theoretical analysis. In particular, the analysis of this paper relies on an IID dataset $\\left\\lbrace (s_i, r_i, s_i')\\right\\rbrace_{i=1}^n$. However, in real offline policy evaluation problem, the dataset usually consists of sampled trajectories, in which the tuples $(s_i, r_i, s_i')$ are mutually dependent. It is not clear whether this dependency will break the results in this paper.\n\nAnother concern I have is about the experiments. Currently, the proposed regularizers are mainly tested in relatively simple environments. Is that possible to check whether these two regularizers are also effective in more complicated environments?\n\n### Questions\n- What if the dataset consists of many sampled trajectories instead of independent one-step transitions?\n- What is the limit of generalization bound in Theorem 5 when $t\\rightarrow\\infty$ if the convergence criteria $||\\mathbf{W}||\\leq\\frac{1}{\\gamma}$ holds? How should we interpret this limit?\n\n---\n\nMy concerns have been well-addressed and thus I increased my score. Meanwhile, I also decreased my confidence score because I realized that my expertise in this area might still need some improvement.", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper proposes a novel convergence analysis of three classical value estimation algorithms and reveals their implicit bias. However, the validity of its setting is questionable and the experiment results is not very persuasive.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a study of the over parametrization of linear representations in the context of recursive value estimation.

The reviewers could not reach a consensus over the quality of the paper, with a fairly wide range of scores even after the rebuttal.

After considering the paper, the rebuttal, and the discussion, I lean towards accepting the paper. Despite the concerns voiced by some of the reviewers, the topic and analysis of the manuscript are novel and interesting, and it is my expectation that this manuscript will prove a valuable source of inspiration for future work.

I invite the authors to carefully consider the feedback received by all the reviewers (and in particular Reviewers xq3y and gT5o and) and to revisit the manuscript accordingly.
Decision: Accept (Poster)