Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning
Authors: Aviral Kumar
Rishabh Agarwal
Dibya Ghosh
Sergey Levine
Venue: ICLR 2021 Poster (2021)
Keywords: deep Q-learning
data-efficient RL
rank-collapse
offline RL

Abstract: We identify an implicit under-parameterization phenomenon in value-based deep RL methods that use bootstrapping: when value functions, approximated using deep neural networks, are trained with gradient descent using iterated regression onto target values generated by previous instances of the value network, more gradient updates decrease the expressivity of the current value network. We char- acterize this loss of expressivity via a drop in the rank of the learned value net- work features, and show that this typically corresponds to a performance drop. We demonstrate this phenomenon on Atari and Gym benchmarks, in both offline and online RL settings. We formally analyze this phenomenon and show that it results from a pathological interaction between bootstrapping and gradient-based optimization. We further show that mitigating implicit under-parameterization by controlling rank collapse can improve performance.

Published as a conference paper at ICLR 2021
IMPLICIT UNDER-PARAMETTRRIAATO INHIBITS
DATA-EFFICHO EFFICIENT DEEP REINFORCEMENT LEARNING
Aviral Kumar*1.2 Rishabh Agarwal* 2,3, Dibya Ghosh', Sergey Levine
UC Berkeley, ?Google Research, 3 MIIA, Université de Montréal
ABSTRACT
We identify an implicit under- pataettrraatttiotoooonnn phenomenon in value-based deep RL methods that use bootstrapping: when value functions, approximated using deep neural networks, are trained with gradient descent using iterated regression onto target values generated by previous instances of the value network, more gradient updates decrease the expressivity of the current value network. We char- acterize this loss of expressivity via drop in the rank of the learned value net- work features, and show that this typically corresponds to a performance drop. We demonstrate this phenomenon Atari and Gym benchmarks, in both offline and online RL. settings. We formally analyze this phenomenon and show that it results from a pathological interaction between bootstrapping and gradient-based optimization. We further show that mitigating implicit under-paramettrization by controlling rank collapse can improve performance.
INTRODUCTION
Many pervasive deep reinforcement learning (RL. algorithms estimate value functions using boot- strapping, that is, by sequentially fitting value functions to target value estimates generated from the value function learned in the previous iteration. Despite high-profile achievements (Silver al., 2017), these algorithms are highly unreliable due to poorly understood optimization issues. Al- though a number of hypotheses have been proposed to explain these issues (Achiam et al., 2019; Bengio et al., 2020; Fu et al., 2019; Igl et al., 2020; Liu et al., 2018; Kumar et al., 2020a), a com- plete understanding remains elusive.
We identify an "implicit parleeerrraameizaattioo" phenomenon that emerges when value networks are trained using gradient descent combined with bootstrapping. This phenomenon manifests as an excessive aliasing of features learned by the value network across states, which is exacer- bated with more gradient updates. While the supervised deep learning literature suggests that some feature aliasing is desirable for generalization (e.g., Gunasekar et al., 2017; Arora et al., 2019), implicit aadde--paramterizzttoon exhibits more pronounced aliasing than in supervised learn- ing. This over-aliasing causes otherwise expressive value network implicitly behave an under-parameterized network, often resulting in poor performance.
Implicit under-pane tatierrrrramttiizzattonn becomes aggravated when the rate of data re-use is increased, stricting the sample efficiency of deep RL methods. In online RL, increasing the number of gradient steps in between data collection steps for data-efficient RL (Fu et al., 2019; Fedus et al., 2020b) causes the problem to emerge more frequently. In the extreme case when no additional data is collected, referred as offline RL (Lange et al., 2012; Agarwal al., 2020; Levine et al., 2020), implicit mnnderparaameterizaton manifests consistently, limiting the viability of offline methods.
We demonstrate the existence of implicit under- pandee-prrametrrizationn in common value-based deep RL. methods, including Q-learning (Mnih et al., 2015; Hessel et al., 2018) and actor-critic (Haarnoja al., 2018), as well as neural fitted-Q iteration (Riedmiller, 2005; Ernst et al., 2005). To isolate the issue, study the effective rank of the features in the penultimate layer of the value network (Sec- tion 3). We observe that after an initial learning period, the rank of the learned features drops steeply. As the rank decreases, the ability of the features to fit subsequent target values and the optimal value function generally deteriorates and results in a sharp decrease in performance (Section 3.1).
'Equal Contribution. Correspondence Aviral Kumar < aviralk@berkeley. @google. com >.
and Rishabh
Agarwal ri whsshaggaaaaae @ggoooggg

---

Published as a conference paper at ICLR 2021
R
P.P. R
7. P.P.R
Minimize TD Error
Minimize TD Error
Minimize TD Error
(
Q
((+,a)
(ss. a
Rank()) decreases
Rank(() decreases
Figure 1: Implicit ander-parameterizztion. Schematic diagram depicting the emergence of effective rank collapse deep Q-leaming. Minimizing TD errors using gradient descent with deep neural network Q-function leads to a collapse the effective rank of the learned features 4, which is exacerbated with further training.
To better understand the emergence of implicit under-pant saterr---aatttrzatioonn
formally study the dy- namics of Q-learning under two distinct models of neural net behavior (Section 4): kernel re- gression (Jacot al., 2018; Mobahi et al., 2020) and deep linear networks (Arora al., 2018). We corroborate the existence of this phenomenon in both models, and show that implicit under- parameterization stems from pathological interaction between bootstrapping and the implicit regu- larization of gradient descent. Since value networks are trained to regress towards targets generated by a previous version of the same model, this leads to sequence of value networks of potentially decreasing expressivity, which can result in degenerate behavior and a drop in performance.
The main contribution of this work is the identification of implicit under-parameterization in deep RL methods that use bootstrapping. Empirically, we demonstrate collapse in the rank of the learned features during training, and show it typically corresponds to a drop in performance in the Atari (Bellemare et al., 2013) and continuous control Gym (Brockman et al., 2016) benchmarks in both the offline and data-efficient online RI. settings. We verify the emergence of this phenomenon theoretically and characterize settings where implieit ander-paramettrrzztion can emerge. We then show that mitigating this phenomenon via a simple penalty on the singular values of the learned features improves performance of value-based RL methods in the offline setting on Atari.
2 PRELIMINARIES
The goal in RL is to maximize long-term discounted reward in Markov decision pro- cess (MDP), defined as a tuple R, (Puterman, 1994). with state space S, ac- tion space A, reward function R(s. transition dynamics P(s'ls, a) and discount fac- tor y [0, 1). The Q-function (s, for a policy T(als), is the expected long-term discounted reward obtained by executing action at state and following T(als) thereafter, (T a) == E |E>n 7² R(ss at)]. (s, a) is the fixed point the Bellman operator T", be written in vector form as: Q" R + + Q The optimal Q-function, (* a), is the fixed point of the Bellman optimality operator T (s, a) == R(s, a) 7Es [max Q(s', a')].
as ("Q a) R(s, a) P(lla)) a' (s))ssss) [Q(s', a')], which
Practical Q-learning methods (e.g., Mnih al., 2015; Hessel et al., 2018; Haarnoja et al., 2018) convert the Bellman equation into an bootstrapping-bart basedd objective for training a Q-network, Qe- via gradient descent. This objective, known mean mean-squared temporal difference (TD) error, is given by: L(0) Es (R(s, a) + Qols'' a') -ss,a))) a))²
where Qo a delayed copy of the Q-function, typically referred to as the target network. These methods train Q-networks via gradient descent and slowly update the target network via Polyak averaging its parameters. We refer the output of the penultimate layer of the deep Q-network as the learned feature matrix Q such that w
Q a)
T ((,, a). where w E dd and & E S|AA///
Algorithm I Fitted Q-tteration (FQI)
For simplicity of analysis, we abstract deep Q-learning methods into a generic fitted Q-iteration (FQI) frame- work (Ernst et al., 2005). We refer to FQI with neural nets as neural FQI (Riedmiller, 2005). In the k-th fitting iteration, FQI trains the Q-function, Qu. to match the tar- get values, Y& = R+ Qx generated using previous Q-function, Q (Algorithm 1). Practical methods can be instantiated as variants of FQI, with different target update styles, different optimizers, etc.
1: Initialize Q-network Qo. buffer p. for fitting iteration in (l..... N) do Compute Qo a) and target values (s,ss, a) = =r + max, Qu-1(s', a') on {(s, a) Minimize TD error for Qo via 1,... , gradient descent updates, ming (s, yx)²
for training
5: end for
2

---

Published as a conference paper at ICLR 2021
GridWorld
Astorix
Seaquest
Ant-v2
Don
200
56C
410
320
dato)
srank C. Lott
150
3.0
60
100
200
20-
Superv and
100
DON
150
10
DON datad
30
0
203
310
500
100
1.0
Tw10
Supervieed
5000
00.0
1000
T-200
Avergee Rature
0000
4000
2000
Average
1000
2000
2000
0.2
1000
-2000
0.0
100
200
300
420
S00
120
200
320
400
500
320
200
200
4.00
500
200
400
Gradient Updittes (A92.99)
Gradiont Updattes (A82.99)
Gradient Updatten (k)
Figure 2: Offline RL. sranks (4)) and performance of neural FQI on gridworld, DQN Atari and SAC on Gym environments in the offline RL setting. Note that low rank (top row) generally corresponds to worse policy performance (bottom row). Rank collapse is worse with more gradient steps per fitting iteration (T= 10 vs. 200 on gridworld). Even when larger. high coverage dataset is used, marked as DQN (4x data), rank collapse occurs (for Asterix also see Figure A.2 for a complete figure with larger number of gradient updates).
3 IMPLICIT UNDER SENDER-PRRAMTTEREE PARAMETERIZATION IN DEEP Q-LEARNING
In this section, we empirically demonstrate the existence of implicit under-parraetteizztion in deep RL methods that use bootstrapping. We characterize implicit under- paader-prrametrizzatonn in terms of the effective rank (Yang et al., 2019) of the features learned by a Q-network. The effective rank of the feature matrix $, for a threshold (we choose 8 0.01), denoted as srank; (.), is given by sranks (D) = min { k: Σ (#)
2 21 18), where {o){ are the singular values of &b in de- od 2 0. Intuitively, srank, ( represents the number of "effective" unique components of the feature matrix & that form the basis for linearly approximating the Q- values. When the network maps different states to orthogonal feature vectors, then sranks ()) has high values close to d. When the network "aliases" statc-action pairs by mapping them to smaller subspace, & has only a few active singular directions, and sranks (.) takes on a small value.
2- (9)
creasing order, i.e., 0i 2
Definition 1. Implicit under- parameterization refers reduction in the effective rank of the fea- tures, srank, (2),, that occurs implicitly as a by-product of learning deep neural network Q-functions.
While rank decrease also occurs in supervised learning, it is usually beneficial for obtaining gener- alizable solutions (Gunasekar et al., 2017; Arora al., 2019). However, we will show that in deep Q-learning, an interaction between bootstrapping and gradient descent can lead to more aggressive rank reduction (or rank collapse), which can hurt performance.
Experimental setup. To study implicit pardeer-raatttiiiaiioon empirically, we compute srank, ( on a minibatch of state-action pairs sampled i.i.d. from the training data (i.e., the dataset in the offline setting, and the replay buffer the online setting). We investigate offline and online RL settings on benchmarks including Atari games (Bellemare et al., 2013) and Gym environments (Brockman et al., 2016). We also utilize gridworlds described by Fu et al. (2019) to compare the Icarned Q-function against the oracle solution computed using tabular value iteration. We evaluate DQN (Mnih et al., 2015) on gridworld and Atari and SAC (Haarnoja et al., 2018) on Gym domains.
Data-efficient offline RL. In offline RL, our goal is to learn effective policies by performing Q- learning on a fixed dataset of transitions. We investigate the presence of rank collapse when deep Q-learning is used with broad state coverage offline datasets from Agarwal et al. (2020). In the top row of Figure/ 2, we show that after an initial learning period, sranks (T) decreases in all do- mains (Atari, Gym and the gridworld). The final value of srank, (+) is often quite small e.g., in Atari, only 20-100 singular components are active for 512-dimensional features, implying signif- is implicitly induced by
icant underutilization of network capacity. Since under-parameterizan the learning process, even high-capacity value networks behave as low-capacity networks as more training is performed with bootstrapped objective (e.g., mean squared TD error).
On the gridworld environment, regressing to Q" using supervised regression results in a much higher sranks (b) (black dashed line in Figure 2(left)) than when using neural FQL. On Atari, even when 4x larger offline dataset with much broader coverage is used (blue line in Figure 2), rank collapse still persists, indicating that implicit under- paramttiittnnnoooioooonnnnn is not due to limited offline dataset size.
3

---

Published as a conference paper at ICLR 2021
Figure 2 (2nd row) illustrates that policy performance generally deteriorates srank( drops, and eventually collapses simultancously with the rank collapse. While we do not claim that implicit mnder-parameteriiattien is the only issue in deep Q-learning, the results in Figure 2 show that the emergence of this mnder--prrmmtterization is strongly associated with poor performance.
To prevent confounding from the distribution mismatch between the learned policy and the offline dataset, which often affects the performance of Q-learning methods, we also study CQL (Kumar et al., 2020b), an offline RL algorithm designed to handle distribution mismatch. We find a sim- ilar degradation in effective rank and performance for CQL (Figure A.3), implying that under- parameterization does not stem from distribution mismatch and arises even when the resulting policy is within the behavior distribution (though the policy may not be exactly pick actions observed in the dataset). We provide more evidence Atari and Gym domains Appendix A.
Gridworld
500
Asterix
505-
Seaquest
200
Antiv2
S0nkk 111
400-
600
180
100
cok (n-d)
200
DON tond
200
300
100
120
1.00
200
300
403
500
100
150
200
50
100
150
200
300
20
40
00
15000
5000-
0.8
Average Ratern
32500
20000-
Buturn
4000
50000
15000
2000
7500
10000
5200
2500
5002
3.0
130 200 300
Envirommnt Stops
400
502
100
200
50
153
200
Ennfronment Steps (xLok)
20 40 00
Figure 3: Data Efficient Online RL. sranks () and performance neural FQI on gridworld, DQN on Atari and SAC on Gym domains in the online RL setting, with varying numbers of gradient steps per environment step (n). Rank collapse happens earlier with more gradient steps, and the corresponding performance is poor.
Data-efficient online RL. Deep Q-learning methods typically use very few gradient updates (n) per environment step (e.g.. DQN takes update every 4 steps on Atari, n 0.25). Improving the sample efficiency of these methods requires increasing n. to utilize the replay data more effectively. However, we find that using larger values of n results in higher levels of rank collapse as well as performance degradation. In the top row of Figure 3, we show that larger values of n lead to a more aggressive drop in sranks (4) (red vs. blue/orange lines), and that rank continues to decrease with more training. Furthermore, the bottom row illustrates that larger values of n result in worse performance, corroborating Fu al. (2019); Fedus et al. (2020b). We find similar results with the Rainbow algorithm (Hessel et al., 201 88 (Appendix A.2). As in the offline setting, directly regressing to Q* via supervised learning does not cause rank collapse (black line in Figure 3).
3.1 UNDERSTANDING IMPLICIT UNDER-PARAMETERRIE
AND ITS IMPLICATIONS
How does implicit under-parameterizatio degrade performance? Having established the pres- ence of rank collapse in data-efficient RL., we now diseuss how it can adversely affect performance. As the effective rank of the network features & decreases, so does the network's 's ability to fit the subsequent target values, and eventually results in inability to fit Q*. In the gridworld domain, we measure this loss of expressivity by measuring the error in fitting oracle-computed Q" values via linear transformation of 4. When rank collapse occurs, the error in fitting Q" steadily increases dur- ing training, and the consequent network is not able to predict Q* at all by the end of training (Fig- ure 4a) - this entails a drop in performance. In Atari domains, we do not have access to Q", and so we instead measure TD error, that is, the error in fitting the target value estimates, R + P* Qa. In SRAQUEST, as rank decreases, the TD error increases (Figure 4b) and the value function is unable to fit the target values, culminating in a performance platcau (Figure 3). This observation is consistent across other environments; we present further supporting evidence in Appendix A.4.
Does bootstrapping cause implicit inder-parameterization We perform number of controlled experiments in the gridworld and Atari environments to isolate the connection between rank collapse and bootstrapping. We first remove confounding issues of poor network initialization (Fedus et al., 2020a) and non-stationarity (Igl et al., 2020) by showing that rank collapse occurs even when the Q-network is re-initialized from scratch at the start of each fitting iteration (Figure 4c). To show that
4

---

Published as a conference paper at ICLR 2021
oridWorld
Seaquest
Gridworld
Seaquest (FQE vs MC)
Sipendient (Dracie)
TD Ertor (log scapscall
100
DON jowd:
DCN Inw5:
60-
n=103
500
nu502
300
20
30
200
10
10a
0
100
230
300
400
500
30
100
150
200
10:
200
300
400
500
103 200
Environment Steps
Environment Steps
Gradient
(a) Q" FITTING ERROR
(b) TD ERROR
(c) Q-REINTTIALIZATION
(d) FQE MC
Figure 4: (a) Fitting error for Q" prediction for 10 vs n 200 steps in Figure (left). Observe that rank collapse inhibits fitting Q" as the fitting error rises over training while rank collapses. (b) TD error for varying values of n for SEAQUEST in Figure 3 (middle). TD error increases with rank degradation. (c) Q-network re i--intiaaiizatinn in each fitting iteration on gridworld. (d) Trend of sranks (+) for policy evaluation based on bootstrapped updates (FQE) Monte-Carlo returns (no bootstrapping). Note that rank-collapse still persists with reinitialization and FQF, but goes away in the absence of bootstrapping.
the problem is not isolated to the control setting, we show evidence of rank collapse in the policy evaluation setting as well. We trained value network using fitted Q-evaluation for fixed policy (Z.e,, using the Bellman operator 7 instead of T)), and found that rank drop still occurs (FQE in Figure 4d). Finally, we show that by removing bootstrapped updates and instead regressing directly to Monte-Carlo (MC) estimates of the value, the effective rank does not collapse (MC Returns in Figure 4d). These results, along with similar findings on other Atari environments (Appendix A.3), our analysis indicates that bootstrapping is at the core of implicit under- paddetraramttriizzaiion.
4 THEORETICAL ANALYSIS OF IMPLICIT
In this section, we formally analyze implicit mader-paramettrrzatte and prove that training neural networks with bootstrapping reduces the effective rank of the Q-network, corroborating the empiri- cal observations in the previous section. We focus on policy evaluation (Figure 4d and Figure A.9), where we aim learn a Q-function that satisfies Q = R +yP Q for a fixed x, for ease of analysis. We also presume a fixed dataset of transitions, D, to learn the Q-function.
4.1 ANALYSIS VIA KERNEL REGRESSION
We first study bootstrapping with neural networks through a mathematical abstraction that treats the Q-network as kernel machine, following the neural tangent kernel (NTK) formalism (Jacot et al., 2018). Building on prior analysis of self-distillation (Mobahi et al., 2020), we assume that each iteration of bootstrapping, the Q-function optimizes the squared TD error to target labels y& with a kernel regularizer. This regularizer captures the inductive bias from gradient-based optimization of TD error and resembles the regularization imposed by gradient descent under NTK (Mobahi et al., 2020). The error is computed on (s;, a:) E 'D whereas the regularization imposed by a universal kernel with a coefficient of e 0 is applied to the Q-values at all state-action pairs shown in Equation 1. We consider a setting c >> 0 for all rounds of bootstrapping. which corresponds to the solution obtained by performing gradient descent on TD error for small number of iterations with early stopping in each round (Suggala et al., 2018) and thus, resembles how the updates in Algorithm are typically implemented in practice.
Q441 + arg min
(Q(s,, a.) - (s,, a²))² + +c Σ Σ u((s, a), (s',a')) a) ('s',a)) (I) A.A.ED
Σ
QEE
(5.a) (s',a')
The solution to Equation 1 can be expressed as Qu+1 (s, a) = 8 (cI + Gy where G is the Gram matrix for a special positive-defimite kernel (Duffy, 2015) and B(s.a) denotes the row of G corresponding to the input a) (Mobahi et al., 2020, Proposition 1). A detailed proof is in Appendix C. When combined with the fitted Q-iteration recursion, setting labels yı RR+ P Q we recover recurrence that relates subsequent value function iterates
Q = G(II+G 'yx = G(d+ R Qul =
((PAA) R: AM,R. (2)
Equation 2 follows from unrolling the recurrence and setting the algorithm-agnostic initial Q-value,
Qu. to be O. We now show that the sparsity of singular values of the matrix M,, generally increases over fitting iterations, implying that the effective rank of M; diminishes with more iterations. For this result, we assume that the matrix S is normal, i.e., the norm of the (complex) eigenvalues of S is equal to its singular values. We will discuss how this assumption can be relaxed in Appendix A.7.
5

---

Published as a conference paper at ICLR 2021
Theorem 4.1. Let S be a shorthand for S = 7, A and assume S is a normal matrix. Then there exists infinite, strictly increasing sequence of fitting iterations. (ka) starting from k1 = O, such that, for any two singular-values (S) and o,(S) of with oi < (S),
(2
(M(M),) 0,
EIEN and I' 11,
(3)
Jj (M
(M
oy(S)
Hence, sranks (MR,) S sranks (M&)). Moreover, if'S is positive semi-definite, then (ka) N, ie., srank continuously decreases in each fitting iteration.
We provide a proof of the theorem above as well as present a stronger variant that shows a gradual decrease in the effective rank for fitting iterations outside this infinite sequence in Appendix C. As increases along the sequence of iterations given by & = (kr) the effective rank of the matrix M& drops, leading to low expressivity of this matrix. Since M; linearly maps rewards to the Q- function (Equation 2), drop in expressivity results of M; in the inability to model the actual Q".
Summary of our analysis. Our analysis of bootstrapping and gradient descent from the view of regularized kernel regression suggests that rank drop happens with more training (i.c., with more rounds of bootstrapping). In contrast self-distillation (Mobahi al., 2020), rank drop may not happen in every iteration (and rank may increase between two consecutive iterations occasionally), but sranks exhibits a generally decreasing trend.
4.2 ANALYSIS WITH DEEP LINEAR NETWORKS UNDER GRADIENT DESCENT
While Section 4.1 demonstrates rank collapse will occur in a kernel-regression model of Q-learning, does not illustrate when the rank collapse occurs. To better specify point in training when rank collapse emerges, we present complementary derivation for the case when the Q-function is represented as a deep linear neural network (Arora et al., 2019), which is a widely-studied setting for analyzing implicit regularization of gradient descent in supervised learning (Gunasekar et al., 2017: 2018; Arora et al., 2018; 2019). Our analysis will show that rank collapse can emerge as the generated target values begin to approach the previous value estimate, in particular, when in the vicinity of the optimal Q-function.
Proof strategy. Our proof consists of two steps: (1) We show that the effective rank of the feature matrix decreases within one fitting iteration (for a given target value) due to the low low-rank affinity, (2) We show that this effective rank drop is "compounded" Proposition 4.1 explains (1) and Proposition 4.2, Theorem 4.2 and Appendix D.2 discuss (2).
we train using bootstrapped objective.
Additional notation and assumptions. We represent the Q-function a deep linear network with at 2 3 layers, such that Q(s,a) a) = W W where N 2 3, WN E IR 1xxdy-1 and W. 6 = WN-IW 2 2 W1 with W; E Rd for i = l,...,,, N 1. Wa maps an input [s; al to corresponding penultimate layer' features 4(s, a). Let W (k, () denotes the weight ma- trix W, at the t-th step of gradient descent during the k-th fitting iteration (Algorithm 1). We define WK.1 k. Wx t) W)W (k, t) and [ (W..) as the TD error objective in the k-th fitting itera- tion. We study sranks W (k,, t)) since the rank of features +- = W o (k, () is equal to rank of (k t) provided the state-action inputs have high rank.
We assume that the evolution of the weights is governed by a continuous time differential equa- tion (Arora et al., 2018) within each fitting iteration k. To simplify analysis, we also assume that all except the last-layer weights follow a "balancedness" property (Equation D.4), which suggests that the weight matrices in the consecutive layers the deep linear network share the same singular values (but with different permutations). However, note that do not assume balancedness for the last layer which trivially leads to rank- I features, making our analysis strictly more general than conventionally studied deep linear networks. In this model, we can characterize the evolution of the singular values of the feature matrix Wo(k, t), using techniques analogous to Arora et al. (2019): Proposition 4.1. The singular values of the feature matrix W Wolk, t) evolve according to:
(Wx(k; t)T ddN.++1 (W k.)). .u, tk,,,,
G,(k, t) = = -N- (o2(k,
(4)
dW
forr=1, min N-1 de where ur (k, t) and v, (k, t) denote the left and right singular vectors of the feature matrix, W (k,,,), t), respectively.

---

Published as a conference paper at ICLR 2021
Solving the differential equation (4) indicates that larger singular val- ues will evolve at a exponentially faster rate than smaller singular values (as we also formally show in Appendix D.I) and the difference in their magnitudes dispropportionatll increase with increasing f. This behavior also occurs empirically, illustrated in the figure the right (also see Fig- ure D.I), 1). where larger singular values are orders of magnitude larger than smaller singular values. Hence, the effective rank, sranks( ( o t)), will decrease with more gradient steps within fitting iteration A.
singsle vatres (og scale)
Seaquest [Singular valums)
2.0
1.00
Gradient Updates Evolution of singular val- ues of Wa on SEAQUEST
Abstract optimization problem for the low-rank solution. Building on Proposition 4.1, we note that the final solution obtained in a bootstrapping round (i.e., fitting iteration) can be equivalently expressed as the solution that minimizes weighted sum of the TD error and a data-dependent implicit regularizer hNd (W o, W x) that encourages disproportionate singular values of W p. and hence, a low effective rank of W.. While the actual form for h is unknown, to facilitate our analysis of bootstrapping, we make simplification and express this solution as the minimum of Equation 5.
min W..WNEM
W W & [s: (s a) + A sranks (W&)
(5)
Note that the entire optimization path may not correspond to the objective in Equation 5, but the Equation 5 represents the final solution of a given fitting iteration. A denotes the set of constraints that W x obtained via gradient optimization of TT error must satisfy, however we do not need to ex- plicitly quantify M in our analysis. d is a constant that denotes the strength of rank regularization. Since srank; is always regularized, our analysis assumes that 0₁ > 0 (see Appendix D.1).
Rank drop within a fitting iteration "compounds" due to bootstrapping. In the RL setting, the target values are given by (s, r(s. a) + -P" a). First note that when r(s. a) 0 and pM = I, i... when the bootstrapping update resembles self-regression, we first note that just "copyying over weights" from iteration k - to iteration & is a feasible point for solving Equation 5, which attains zero TD error with no increase in srankş. A better solution to Equation 5 can thus be obtained by incurring non-zero TD error the benefit of decreased srank, indicating that in this setting, srank;(Wa drops in each fitting iteration, leading to a compounding rank drop effect
We next extend this analysis to the full bootstrapping setting. Unlike the self-training setting, (s, a) is not directly expressible as function of the previous (k T)) due to additional reward and dynamics transformations. Assuming closure of the function class (Assumption D.I) under the Bellman update (Munos & Szepesvári, 2008; Chen & Jiang, 2019), we reason about the compound- ing effect of rank drop across iterations in Proposition 4.2 (proof in Appendix D.2). Specifically, srank, can increase in each fitting iteration due to R and p transformations, but will decrease due to low rank preference of gradient descent. This change in rank then compounds as shown below.
Proposition 4.2. Assume that the Q-function is initialized to W Wo(0) and W (O). Let the O-function class be closed under the backup, i.e., 3 W N W go s.t. (R + xPm -==QQ=="" = ( A"" and assume that the change in srank due to dynamics and reward transformations is bounded: srank, W (k)) S sranks (W a o1 1)) + Ck. Then,
k
Q yyll
sranks (W (k())) S sranks ( (0)) Σ G 1=1 1=1
Σ
X
Proposition 4.2 provides a bound on the value of srank after k rounds of bootstrapping. srank de- creases in each iteration due to non-zero TD errors, but potentially increases due to reward and bootstrapping transformations. To instantiate a concrete case where rank clearly collapses, we in- vestigate Cj as the value function gets closer to the Bellman fixed point, which is a favourable initialization for the Q-function in Theorem 4.2. In this case, the learning dynamics begins to re- semble the self-training regime, as the target values approach the previous value iterate yı R QR-1, and thus, as we show next, the potential increase in srank (Ca in Proposition 4.2) converges to O.
Theorem 4.2. Suppose target values y = R+y P P= QK- are close to the previous value esti- mate Qk-1, L.e. V s, a, yk (s a) Qk (s, a) + a). with (e(s, a) < (Q-1(s,, a)). Then, there is a constant 6g depending upon W N and W such that for all ||e|| < En. Ck = 0. Thus, srank decreases in iteration k: sranks ( (k)) & sranks (W ok 1)) QQ ykll/>r.

---

Published as a conference paper at ICLR 2021
We provide complete form, including the expres- sion for cu and a proof in Appendix D.3. To em- pirically show the consequence of Theorem 4.2 that a decrease in sranks(W) an increase in the distance to the fixed point in
GridWorld
Emer to sosed pateet Eg .10
GridWorld
Superited
OPaNk (2)) (-11/t
values can lead to
a neighborhood around the fixed point, we per- formed controlled experiment on deep linear net shown in Figure 5 that measures the relation- ship between of sranks ( and the error to the pro- jected TD fixed point IQ- Q- Note that drop in srank, (b) corresponds to a increased value of
10
100
700
300
400
100 203
200
000
São
Pitting
Fitting Berratonns
Figure 5: Trend sranks v.s. error on log scale the projected TD fixed point, A drop in srank, (+) (shown as blue and yellow circles) corresponds to a corresponding increase in distance to the fixed point.
QQ Q" indicating that rank drop when Q get close to a fixed point can affect convergence to it.
5
MITIGATING SNDER-PARAMETRIZEE
IMPROVES DEEP Q-LEARNING
We now show that mitigating implicit under- parameterization by preventing rank collapse can im- prove performance. We place special emphasis on the offline RL, setting in this section, since it is particularly vulnerable to the adverse effects of rank collapse.
We devise a penalty (or regularizer) (,( that encourages higher effective rank of the Iearned features, sranks(#)), to prevent rank collapse. The effective rank function sranks ( is non-differentiable, so we choose simple surrogate that be optimized over deep networks. Since effective rank is max- imized when the magnitude of the singular values is roughly balanced. one way to in- crease effective rank to minimize the largest singular value of 4, (@), while simul- taneously maximizing the smallest singular value, O ( We construct a simple penalty (2) derived from this intuition, given by:
Gridworld
500-
Seaquent
400
3.0
Pensaly
02
300 280
Gradient Updaten Breakout
Nomallnd Iuturn
402
ngr will Parally
Supervited
350
Standard Fot
300
250
DQH
BGN Persityy
300
200
300
500
150
200
Gradient Updates
(a)
(b)
(4) = o ()) o (
(6)
Figure 6: (a): sranks (top) and performance (bot- tom) of FQI on gridworld in the offline setting with 200 gradient updates per fitting iteration. Note reduced rank collapse and higher performance with the regular- izer (D).) (b): C,( mitigates the rank collapse in DQN and CQL in the offline RL setting on Atari.
(D) can be computed by invoking the singular value decomposition subroutines in standard automatic differentiation frame- works (Abadi et al., 2016; Paszke et al., 2019).
We estimate the singular values over the feature matrix computed over a minibatch, and add the resulting value of Cp as a penalty to the TD error objective, with a tradeoff factor a = 0.001.
Does (D) address rank collapse? We first verify whether controlling the minimum and maxi- mum singular values using (D) actually prevents rank collapse. When using this penalty on the gridworld problem (Figure 6a), the effective rank does not collapse, instead gradually decreasing at the onset and then platcauing, akin to the evolution of effective rank in supervised learning. In Figure 6b, we plot the evolution of effective rank on two Atari games in the offline setting (all games in Appendix A,5), and observe that using Cp also generally leads to increasing rank values.
Does mitigating rank collapse improve performance? We now evaluate the performance of the penalty using DQN (Mnih et al., 2015) and CQL (Kumar et al., 2020b) on Atari dataset from Agar- wal et al. (2020) (5% replay data), used in Section 3. Figure 7 summarizes the relative improvement from using the penalty for 16 Atari games. Adding the penalty to DQN improves performance on all 16/16 games with median improvement of 74.5% adding it CQL, state-of-the-ant offline algorithm, improves performance on 11/16 games with median improvement of 14.1 %. Prior work has discussed that standard Q-learning methods designed for the online setting, such as DQN, are generally ineffective with small offline datasets (Kumar et al., 2020b; Agarwal et al., 2020). Our results show that mitigating rank collapse makes even such simple methods substantially more ef- fective in this setting, suggesting that rank collapse and the resulting implicit under- parameterizaation may be an crucial piece of the puzzle in explaining the challenges of offline RL.
8

---

Published as a conference paper at ICLR 2021
We also evaluated the reg- ularizer (p( in the data- efficient online RL setting, with results in Appendix A.6.
NOV PoPooaitt
Improveeem
% Immroveeee
This variant achieved median improvement of 20.6% per- formance with Rainbow (Hes- sel et al., 2018). however performed poorly with DQN, where it reduced median per- formance by 11.5%. Thus, while our proposed penalty is effective in many cases in offline and online settings, it does not solve the problem fully, i.c., does not address the root cause of implicit muder-parameterizatinnn and only addresses symptom, and a more sophisticated solution may better prevent the issues with implicit under-paree aadder-parameterzzatoon Nevertheless, our results suggest that mitigation of implicit under-parameterizatiin can improve performance of data-efficient RL.
Figure 7: DQN and CQL with ( penalty vs. their standard counter- parts in the 5% offline setting on Atari from Section 3. Lp improves DQN on 16/16 and CQL on 11/16 games.
RELATED WORK
Prior work has extensively studied the learning dynamics of Q-learning with tabular and linear func- tion approximation, to study error propagation (Munos, 2003; Farahmand et al., 2010) and to prevent divergence (De Farias, 2002; Maei et al., 2009; Sutton et al., 2009; Dai et al., 2018), as opposed to deep Q-learning analyzed in this work. Q-learning has been shown to have favorable optimization properties with certain classes of features (Ghosh & Bellemare, 2020), but our work shows that the features learned by a neural net when minimizing TD error do not enjoy such guarantees, and instead suffer from rank collapse. Recent theoretical analyses of deep Q-learning have shown con- vergence under restrictive assumptions (Yang et al., 2020; Cai et al., 2019; Zhang et al., 2020; Xu & Gu, 2019), but Theorem 4.2 shows that implicit siiier-prrrmtteizattion appears when the estimates of the value function approach the optimum, potentially preventing convergence. Xu et al. (2005; 2007) present variants of LSTD (Boyan, 1999), which model the Q-function but do not take into account the regularization from gradient descent, as done Equation which is essential for implicit under-paramend paraeterizattnnnnnnn Igl et al. (2020); Fedus et al. (2020a) argue that non-stationarity arising from distribution shift hinders generalization and recommend periodic net- work re-initialization. that network re- re-initialization does little to prevent rank collapse (Figure 4c). Luo et al. (2020) pro- poses a regularization similar to ours, but in a different setting, finding that more expressive features increases performance of on-policy RL methods. Finally, Yang et al. (2019) study the effective rank of the -vauuu when expressed as a |S] |A] matrix in online RL and find that low ranks for this Q' -matrix are preferable. We analyze fundamentally different object: the learned features (and illustrate that a collasee of features can hurt), not the Q* -matrix, whose rank is eoper-bounded by the number of actions (e.g.. 24 for Atari).
kernel-machine
pander-prrameteizzationn is not caused by this distribution shift, and find
7 DISCUSSION
We identified an implicit strapping, where gradient-based optimization of a bootstrapped objective can lead reduction in the expressive power of the value network. This effect manifests as a collapse of the rank of the features learned by the value network, causing aliasing across states and often leading to poor per- formance. Our analysis reveals that this phenomenon is caused by the implicit regularization due to gradient descent on bootstrapped objectives. We observed that mitigating this problem by means of simple regularization scheme improves performance of deep Q-learning methods.
phenomenon in deep RL algorithms that use boot-
While our proposed regularization provides some improvement, devising better mitigation strate- gies for implicit under- paddeerrrraetiizzationn remains an exciting direction for future work. Our method explicitly attempts to prevent rank collapse, but relies on the emergence of useful features solely through the bootstrapped signal. An alternative path may be to develop new auxiliary losses (e.g., Jaderberg et al., 2016) that learn useful features while passively preventing underparameterizzatio.. More broadly, understanding the effects of neural nets and associated factors such as initialization, choice of optimizer, etc. on the learning dynamics of deep RL algorithms, using tools from deep learning theory, is likely be key towards developing robust and data-efficient deep RL algorithms.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDDEMENTS
We thank Lihong Li, Aaron Courville, Aurick Zhou, Abhishek Gupta, George Tucker, Ofir Nachum, Wesley Chung, Emmanuel Bengio, Zafarali Ahmed, and Jacob Buckman for feedback on an earlier version of this paper. We thank Hossein Mobahi for insightful discussions about self-distillation and Hanie Sedghi for insightful discussions about implicit regularization and generalization in deep networks. We additionally thank Michael Janner, Aaron Courville, Dale Schuurmans and Marc Bellemare for helpful discussions. AK was partly funded by the DARPA Assured Autonomy pro- gram, and DG was supported by NSF graduate fellowship and compute support from Amazon.
REFERENCES
Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large- scale machine learning. 12th USENIX Symposium on Operating Systems Design and Imple- mentation (OSDI 16), pp. 263, 2016. URL https: osdil 6/ oosoissille 6- abadi. .pdf.
orq/ system/
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards characterizing divergence in deep q- learning. ArXiv, abs/1903.0885 2019.
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. In International Conference Machine Learning (ICML), 2020.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparamcterization. arXiv preprint arXiv:1802.06509 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pp. 7413-7424, 2019.
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning envi- ronment: An evaluation platform for general agents. Artif. Int. Res., 47(1)2253-277, May 2013. ISSN 1076-9757.
Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 449-458. JMLR. org. 2017.
Emmanuel Bengio, Joelle Pineau, and Doina Precup. Interference and generalization in temporal difference learning. arXiv preprint arXiv:2003.063333 2020.
Justin A Boyan. Leaat-squares temporal difference learning. ICML, pp. 49-56. Citeseer, 1999.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Qi Cai, Zhuoran Yang, Jason Lee, and Zhaoran Wang. Neural temporal-differte difference and q-learning provably converge to global optima. arXiv preprint
2019.
Jinglin Chen and Nan Jiang. enformation-theoreet considerations in batch reinforcement learning. ICML, 2019.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Con- ference Machine Learning, pp. 1133-1 142, 2018
Daniela Pucci De Farias. The linear programming approach to approximate dynamic programming: Theory and application. PhD thesis, 2002.
Dean G Duffy. Green's 's functions with applications. CRC Press, 2015.
10

---

Published as a conference paper at ICLR 2021
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Treed batch mode reinforcement learning. Journal of Machine Learning Research, (AAp)):5335550 2005.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems (NIPS), 2010.
William Fedus, Dibya Ghosh, John D Martin, Mare G Bellemare, Yoshua Bengio, and Hugo Larochelle. On catastrophic interference in atari 2600 games. arXiv preprint arXiv:2002.1249,, 2020a.
William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. arXiv preprini arXiv:2007.06700, 2020b.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q- learning algorithms. In Proceedings of the 36th International Conference on Machine Learning- PMLR, 2019.
Dibya Ghosh and Mare G Bellemare. Representations for stable off-policy reinforcement learning. arXiv preprint +XXx:20077005520 2020.
Caglar Gulcehre, Ziyu Wang, Alexander Novikov, Tom Le Paine, Sergio Gómez Colmenarejo, Kon- rad Zolna, Rishabh Agarwal, Josh Merel, Daniel Mankowitz, Cosmin Paduraru, et al. RI un- plugged: Benchmarks for offline reinforcement learning. 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp- 9461-9471, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. CoRR, 0oss/1801.1120 2018. URL http: / /wwwivaiivvvvv.////i//.aa//aiiia org/ 1801001111111 01290.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Edmund Hlawka, Rudolf Taschner, and Johannes SchoiBengeier. The Dirichlet Approximation Theorem, pp. 1-18. Springer Berlin Heidelberg. Berlin, Heidelberg, 1991. ISBN 978-3- 642-75306-0.
doi: 10. 100100777788-3-642-7756-----02 URL pttpss//dcci.org/1..... oor.//0.g//0100/
978-3-642- 001-3-6-27736--00
Maximilian Igl. Gregory Farquhar, Jelena Luketina, Wendelin Boehmer, and Shimon Whiteson.
The impact of son-stationarity generalisation in deep reinforcement learning. arXiv preprint arXiv:2006.0588 055.26.... 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kemnl: Convergence and gen- cralization in neural networks. In Advances in Neural Information Processing Systems 31. 2018.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czamecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint 161 1.05397, 2016.
Robert Johnson. Approximate irrational numbers by rational numbers, 2016. URL https://
math. math. wwwh.ssttceexccangecc.mm cww.aaannn..oooeaaaoooammmomooom http//uesiiiiii 11829743/
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. arXiv preprint arXiv:20033073305, 2020a.

---

Published as a conference paper at ICLR 2021
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint (xXi::2006004779, 2020b.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforce- ment leurning, pp. 45-73. Springer, 2012.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto-
rial, review, and perspectives on open problems. arXiv preprint arXiv:2005..01643 2020.
Vincent Liu, Raksha Kumaraswamy, Lei Le, and Martha White. The utility of sparse representatiioo for control in reinforcement learning. CoRR, abs/1811. 811.66666, 2018. URL http://arxiv.
org/ abs/ ors/abs// 1811. 06626.
Xufang Luo, Qi Meng, Di He, Wei Chen, and Yunhong Wang. 14r: Promoting deep reinforcement learning by the indicator for expressive representations. In Christian Bessiere (ed.), Proceed- ings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. International Joint Conferences on Artificial Intelligence Organization, 7 2020. doi: 2a.24963/jcaii URL htw.h:ttp/////t /oii track.
http://ooooorgg//////// wrg. 24963/ jcaiiiicii...///o 2020/3002 370. Main
Hamid Maei. Csaba Szepesvári, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard S. Sutton. Convergent remporal-difference learning with arbitrary smooth function approximation. In Proceedings of the 22nd International Conference on Neural Information Processing Systems, 2009.
Volodymyr Mnih, Koray Kavukcuoglu, 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 Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 51 51877540)5529-53 feb 2015. ISSN 0028-0836.
Hossein Mobahi, Mehrdad Farajtabar, and Peter L Bartlett. Self-distillation amplifies regularization in hilbert space. arXiv preprint arXiv:2002.05715, 2020.
Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth Inter- national Conference on International Conference on Machine Learning, ICML'03, 00,, pp. 560-567. AAAI Press, 2003. ISBN 3577351894,
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 91 2008
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8026-8033 Curran Associates, Inc., 2019.
Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley Sons, Inc., 1994.
Martin Riedmiller. Neural fitted q iteration-fisst experiences with data efficient neural reinforce- ment learning method. In European Conference on Machine Learning, pp. 317-328. Springer, 2005.
Axel Ruhe. On the closeness of eigenvalues and singular values for almost normal matrices. Linear Algebra and its Applications, 11(1):87-93, 1975.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-355 2017.
12

---

Published as a conference paper at ICLR 2021
Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regulariza- tion paths. Advances in Neural Information Processing Systems. pp. 10608-106111 2018.
Richard S. Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In International Conference on Machine Learning (ICML), 2009.
James Townsend. Differentiating the singular value decomposition. Technical report, Technical Report 2016, https://j-towns, github. io/papers/svd-derivatiie .... 2016.
Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function ap- 2019.
proximation. arXiv preprint
Xin Xu, Tao Xie, Dewen Hu, and Xicheng Lu. Kernel least-squares temporal difference learning. International Journal of Information Technology, 11(9):54-63, 2005.
Xin Xu, Dewen Hu, and Xicheng Lu. Kerne--based least squares policy iteration for reinforcement learning. IEEE Transactions on Neural Nefworks, 18(4)9973-992, 2007.
Yuzhe Yang, Guo Zhang, Zhi Xu, and Dina Katabi. Harnessing structures for value-based planning and reinforcement learning. arXiv preprint arXiv: 2019.
Zhuoran Yang, Yuchen Xie, and Zhaoran Wang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pp. 486-489, PMLR, 2020.
Yufeng Zhang, Qi Cai, Zhuoran Yang, Yongxin Chen, and Zhaoran Wang. Can temporal-diiffrrnce and g-learning learn representation? mean-field theory. arXiv preprint 2rXin:2006.04611, 2020.
13

---

Published as a conference paper at ICLR 2021
Appendices
A ADDITIONAL EVIDENCE FOR IMPLICIT UNDER- PARAMETERIZATION
In this section, we present additional evidence that demonstrates the existence of the implicit under- paramcterization phenomenon from Section 3. In all cases, we plot the values of (T) com- puted on a batch size of 2048 i..d. sampled transitions from the dataset.
A.1
OFFLINE RL
Asteria
Senquest
0'dert
Pong
Breakost
400
20M
001
400
DCM
350
300
363
100
232
D0M
3200
1500
ace
1000
15
-33
210
CrodBret Uaadatee 2402
Oradiest A00
Cradiccn Starlaten EVE2 5k1
Grediont Mardartes DUCO 983
Figure A.I: Offfine DQN on Atari. sranks (1) and performance of DQN on five Atari games the offline RL setting using the 5% DQN Replay dataset (Agarwal et al., 2020) (marked as DQN). Note that low srank (top row) generally corresponds to worse policy performance (bottom row). Also note that rank collapse begins to generally occur close to the position of peak return. Average across runs is showed for each game with individual runs.
410
00X Satt 400
403
00%
250
410
253
300
160
313
200
D25 (Cc 860
252
252
1500
4990
5c0
2500
-20
32
200
-22
10:0
Gradiorn
Figure A.2: Offline DQN on Atari. sranks ④) and performance of DQN on five Atari games the offline RL setting using the 20% DQN Replay dataset (Agarwal et al., 2020) (marked as DQN) trained for 1000 iterations. Note that low srank (top row) generally corresponds to worse policy performance (bottom row). Average across 5 runs is showed for each game with individual runs
Anterte
Seaquest
500
Breakeww
350
300
233
200
230
800
630
166
3200
53
200
406
630
1006
200
466
6.0
300
100.
230
460
600
206
1060
230
400
621
05
1668
2532
2032
1032
3502
2332
2300
25
220 151
X22
270
252 020 620
4T0
233
C2D 230 400 1786
KGD
Figure A.3: Offline CQL on Atari. sranks( and performance of CQL on five Atari games in the offline RL setting using the 5% DQN Replay. Note that low srank (top row) generally corresponds to worse policy performance (bottom row). Average across runs for each game trained for 1000 iterations.
14

---

Published as a conference paper at ICLR 2021
300
54C
200
54C
320
300
100
53
1000
1000
2200
hewere bebm
600
-1000
3300
400
300
233
810
250
311
253
Figure A.4; Offline Control on MuJoCo. sranks () and performance of SAC on three Gym environments the offline RL setting. Implicit Under- parammtrrrattniniiioonnn is conspicuous from the rank reduction, which highly correlates with performance degradation. We use 20% uniformly sampled data from the entire replay experience of an online SAC agent, similar to the 20% setting from Agarwal et al. (2020).
Ant-11
Hoppere2
247
Walker25-2
350
150
325
Reture
2000
2000
1100
Aserge
2000
-200
2007
Gradberd Updittes 890
Figure A.5: Offline Control on MuJoCo. sranks (1) and performance of CQL on three Gym environments the offline RL setting. Implicit Under-parameee parameterization is conspicuous from the rank reduction, which highly correlates with performance degradation. We use 20% uniformly sampled data from the entire replay experience of an online SAC agent, similar to the 20% setting from Agarwal al. (2020).
A.2 DATA EFFICIENT ONLINE RL.
In the data-efficient online RL setting, we verify the presence of implicit under- under-parameten parameterization on both DQN and Rainbow (Hessel et al., 2018) algorithms when larger number of gradient updates made per environment step. In these settings we find that more gradient updates per environment step lead larger decrease in effective rank, whereas effective rank can increase when the amount of data re-use is reduced by taking fewer gradient steps.
Qn
Asterix
Sesquest
Breakout
6.50
mwil DON (vwi)
0 4000
400
6:30-
320
DCk m-d21
Dok ineds
4:00
DON (n-d)
pon (nne)
21
DIO
290
100
D10
130
50
130
15c
230
30
180
15c
200
200
150
200
50
100
150
200
50
260
150
200
15000
15000
2500
-10
5000
-20
50 1.00
183
150
220
120
220
200
200
Stepp
Figure A.6: Online DQN on Atari. srank; (T) and performance of DQN on 5 Atari games in the online RL set- ting, with varying numbers of gradient steps per environment step (1). Rank collapse happens earlier with more gradient steps, and the corresponding performance is poor. This indicates that implicit under-panee parameterization aggravates the rate of data re-use increased.
15

---

Published as a conference paper at ICLR 2021
HalfChhstsh-v22
Hoppar-22
Walker2dez2
2.00
280
.70
140
200
140
120
11
3.0
20
6020
19000
5000
5200
3030
4200
3200
1030
1200
23 60 20 1.0
20
80
65
150
25
43
40)
60
103
20
60 60
100
Mtpp
Steps
Steps
Stops (X305)
Figure A.7: Online SAC on MuJoCo. (Ta and performance of SAC on three Gym environments the online RL setting, with varying numbers of gradient steps per environment step (n). While in the simpler environments, HalfCheetah-v2. Hopper-v2 and Walker2d-v2 we actually observe an increase in the values of effective rank, which also corresponds to good performance with large n values in these cases, the more complex Ant-v2 environment rank decreases with larger n, and the corresponding performance is worse with more gradient updates.
Doubble Dunk
Enduro
400
200
300
300
300
200
200
100
100
40
00
60
Envirunment Steps
Environment
Environment
Ice Hockey
Jamea Bond
Ma. Pac Man
Road Runner
400
400
300
300
300
200
200
200
200
100
100
100
20
10
100
20
40
60
100
40
100
20
40
65
Environmontt Stops
Environment ment Stops
Environment Stops
Environment Steps
Revenge
500
400
300
300
200
200
100
100
40
60
100
60
500
Senqueet
Pong
grBert
Breakout
400
400
300
300
300
200
100
200
100
20
100
20
40
60
1.00
20
1.00
20
40
Environmant Steps
Enviton mont Stops
Environment Steps
Environment Stops
Figure A.8: Online Rainbow on Atari. sranks( (+) Rainbow on 16 Atari games in the data-cfficient online setting, with varying numbers of gradient steps per environment step (n). Rank collapse happens earlier with more gradient steps, and the corresponding performance poor. This plot indicates the multi-step returns, prioritized replay or distributional C51 does not address the implicit under-parameterization issue.
A.3 DOES BOOTSTRAPPING CAUSE IMPLICIT
In this section, we provide additional evidence to support claim from Section 3 that suggests that bootstrapping- based updates are a key component behind the existence of implicit under- parameterization. To do so, empirically demonstrate the following points empirically:
16

---

Published as a conference paper at ICLR 2021
Implicit muder-paramettrizaatinn occurs even when the form of the bootstrapping update is changed from Q-learning that utilizes a max, backup operator to a policy evaluation (fitted Q-evaluation) backup operator, that computes an expectation of the target Q-values under the distributions specified by a different policy. Thus, with different bootstrapped updates, the phenomenon still appears.
Asterii
300
Seaquest
402
Pong
450-
420
Broakout
2:0
420
300
Fibk darei
203
403
303
Barel
350
410
200
310
1:0
303
105
320
126
100
105 203
zic
403
300
200
203
200
400
200
200
200
20
400
500
1201
200
535
400)
500
100
200
535
403
500
Gradient Vpdaetes
Gredient Updates
Grediest Updatees
Gredient Upiiites
Gradient Spdatte
Figure A.9: Offline Policy Evaluation on Atari. (P) and performance of offline policy evalua- tion (FQE) on 5 Atari games in the offline RL setting using the 5% and 20% DQN Replay dataset (Agarwal et al., 2020). The rank degradation shows that under- parameterization is not specific to the Bellman optimal- ity operator but happens even when other bootstrapping baasdd backup operators combined with gradient descent. Furthermore, the rank degradation also happens when increase the dataset size.
does not occur when Monte-Carlo regression targets that compute regression targets for the Q-function by computing a non-parameteric estimate the future trajectory return, i.e., (s, at) = Ee= r'r(s,, ar) and do not use bootstrap- ping. In this setting, we find that the values of effective rank actually increase over time and stabilize. unlike the corresponding case for bootstrapped updates. Thus, other fac- tors kept identically the same, implicit under-parameterriaton happens only when
Implicit
bootstrapped updates are used.
Astorix
Soaquest
O"Bert
500
340
602
400
400
300
200
MCC recurns Jarpel
200
MC returns Jargel
200
250
MCC return Sargel
200
MC recurss (brgel
HC
250
200
MCC reiume (argel
300
210
200
100
220
A00
200
220
200
200
200
200
200
200
50c
Updates
Updates
Updates
Updatas
Updades
Figure 1010: Monte Carlo Offline Policy Evaluation. srank; (D) on 5 Atari games in when using Monte Carlo returns for targets and thus removing bootstrapping updates. Rank collapse does not happen in this We perform the experiments
setting implying that is hootstrapping was essential for ander-parameterizatin using 5% and 20% DQN replay dataset from Agarwal et al. (2020).
For the final point in this section, we verify if the non-stationarity of the policy in the Q- learning (control) setting, i.e., when the Bellman optimality operator is used is not reason behind the emergence of implicit under-parame parameterization The non-stationary policy in a control setting causes the targets to change and, as a consequence, leads to non-zero rors. However, rank drop is primarily caused by bootstrapping rather than non-stationarity of the control objective. To illustrate this, we an experiment in the control setting on Gridworld, regressing to the target computed using the true value function Q' for the current policy π (computed using tabular Q-evaluation) instead of using the bootstrap TD estimate. The results, shown in figure A. la, show that the srank; doesn't tt decrease signif- icantly when regressing to true control values and infact increases with more iterations as compared to Figure 6a where rank drops with bootstrapping, This experiment, alongside with experiments discussed above, ablating bootstrapping in the stationary policy evalua- tion setting shows that rank-deficiency is caused due to bootstrapping.
A.4 How DOES IMPLICIT REGULARIZZTION INHIBIT EFFICIENT RL.
Implicit ander-parameterizatinn
leads to a trade-off between minimizing the TD error vs. encourag- ing low rank features as shown in Figure 4b. This tra often results in decrease in effective rank, at the expense of increase in TD error, resulting in lower performance. Here we present additional evidence to support this.
Figure A. shows a gridworld problem with one-hot features, which naturally leads to reduced state-aliasing. In this setting, we find that the amount of rank drop with respect the supervised
17

---

Published as a conference paper at ICLR 2021
Gridweorld (0 ne-itot Fentures)
Gridworld
60
50
40
Supervised
120
300
400
509
10
100 200
Gradient Updates
300 400 500
12.5
Sugervund (Oroci))
(a) Using oracle access to exact Q for computing the target values does not sig- nificantly decrease in rank, and training for longer can increase feature rank. This experiment uses a policy itcration style setup but the essential trend of rank drop we train more does not occur.
10.0
5.0
2.5
Enviromment Stepo
(b) Q" fitting eтror and srank in one-hot
variant of the gridworld environment.
Figure A.II: Gridword: (a) Effective rank change due to non-stationarity (b) Q" fitting error vs, sranks.
projection of oracle computed Q' values quite small and the regression error to Q' actually decreases unlike the case in Figure 4a, where it remains same to learn policies that attain good performance as well. Hence, this justifies that when there's 's very little rank drop, for example, 5 rank units in the example the right, FQI methods generally able to learn that is able to fit Q" This provides evidence showing that typical Q-networks learn & that can fit the optimal Q-function when rank collapse does not occur.
increases. The method is able
In Atari, we do not have access to Q", and so we instead measure the error in fitting the target value estimates, R +-7P*0 Qi- As rank decreases, the TD error increases (Figure A.12) and the value function is unable to fit the target values, culminating in a performance plateau (Figure A.6).
Seaquest
Pong
O'Bert
Breakout
500
300
pmb)
400
Poll uel
3.0
330
210
200
230
506 (omi)
100
50
250
23a
107
22
53
100
150
330
100 350
200
50
320
350
200
20
200
350
200
200
3.50
200
Figure A.12: TD error Effective rank Atari. We observe that Huber-loss TD error is often higher when there is larger implicit under parameterization, measured in terms of drop in effective rank. The results are shown data-efficient online RL setting.
A.5 TRENDS VALUES OF EFFECTIVE RANK WITH PENALTY.
In this section, we present the trend in the values of the effective rank when the penalty (D) is added. In each plot below, we present the value of (r)) with and without penalty respectively.
18

---

Published as a conference paper at ICLR 2021
A.5.1
OFFLINE RL: DQN
031
240
Do Nanatt
DC6 Nasaly
DOW Haraty
E05 Parssty
250
Qradllent Madittos
Cradieed Syelates
Orudiinnt Updatte
$300
4330
5008
4003
12:00
22.07
300
100
45 CE
126
230
20
43
200
Figure A.13: Effective rank values with the penalty on DQN. Trends in effective rank and performance for offline DQN. Note that the performance DQN with penalty is generally better than DQN and that penalty (blue) is effective in increasing the values of effective rank. We report performance at the end of 100 epochs, per the protocol set by Agarwal et al. (2020) in Figure 7.
200
220
100
100
201
Dobi Aanalt
200
DoN Faray
204 Para
Uptatte
12559
300
4000
2300
1100
100
320
350
330
200 225
200
126
1200 150
230
220 150
300
Figure A.14: Effective rank values with the penalty on DQN on larger dataset. Trends in effective rank and performance for offline DQN with a 4x larger dataset, where distribution shift effects are generally removed. Note that the performance of DQN with penalty is generally better than DQN and that the penalty (blue) is effective in increasing the values of effective rank in most cases. Infact in PONG, where the penalty is effective in increasing rank, observe suboptimal performance (blue red).
% Imorovement (Log scale)
10a
DQN
Penalty
202
COL
Penalty
10a
% Improvveentt (Log
102.
10:
30:
-20
10a
DQN
:20
202
COL
pong
Entura
Zacoo
Obert
hoadhurmer
Iofoction
Specatroaders
Soaquett
budb ank
Demoroltack
booktbukk
Ober
Endiro
nong
Taniherunge
Adte
Squae
Z000n-
Bcambate
Game
Game
(a) Offline DQN with (+))
(b) Offline CQL with (Φ))
Figure A.15: Performance improvement of (a) offline DQN and (b) offline COL with the (x( penalty on
20% Atari dataset, i.c., dataset referred to as 4x large in Figure 2.
19

---

Published as a conference paper at ICLR 2021
A.5.2
OFFLINE RL: CQL WITH (p) PENALTY
Asterix
Seaqueat
Breakout
Perg
452
452
353
202
202
621
200
252
300
1200
$380
19903
7502
100
9302
2000
2382
2500
102
-20
23
40
350
50 23
130
100
20
600
100
Figure A.16: Effective rank values with the penalty (Φ) on CQL. Trends in effective rank and perfor- mance offline DQN, Note that the performance of CQL with penalty is generally better than vanilla CQL and that the penalty (blue) is effective increasing the values of effective rank. We report performance at the end of 100 epochs, as per the protocol set by Agarwal et al. (2020) in Figure 7.
A.6 DATA-EFFICIENT ONLINE RL: RAINBOW
A.6.1 RAINBOW WITH (g( PENALTY: RANK PLOTS
Attack
Dasdile
Irdure
154
050
432
400
400
1.0
352
332
300
3:0
300
2:00
202
200
200
354
23
42
83
100
60
50
100
20
40
20
100
102
20.
41
60
53
100
3.00
020
400
100
352
200
250
300
Saxbze 1o-40
200
Ramboe
252
3asb2e 2004
150
232
65
100
60
100
100
60
Winard Wor
Yart's Rovenge
Zazoon
Antorix
500
500
452
400
355
250
432
100
352
256
2:0
332
Ral (2-4)
DaF 2-41
Failbon (pnd)
250
60
100
160
Livebornent stops
despormenn Staps
sexironnart Stape
destroneent steps
Seaqueat
Pong
QrBort
Breakout
450
4.00
432
312
300
230
332
DON 31 Pardyy
Tambow 2pm42
Ka/15ow 2on Parslyy
252
Tarbar Joe-
Jon Paraary
Eneborment Stapa
Eevirormntt Stape
Gestrormert Stape
Erstronment Stape
Figure A.17: Effective rank values with the penalty Rainbow in the data-efficient online RL setting. Trends in effective rank and performance for online Rainbow, where distribution shift effects are generally removed. Note that the performance DQN with penalty is generally better than DQN and that the penalty (blue) is effective in increasing the values of effective rank in most cases. Infact in PONG, where the penalty is not effective in increasing rank, we observe suboptimal performance (blue vs. red).
20

---

Published as a conference paper at ICLR 2021
A.6.2 RAINBOW WITH Ly( PENALTY: PERFORMANCE
Innrooeemnnt (Log scale)
In this section, we present additional re- sults for supporting the hypothesis that pre-
10a
Rainbow (n=4) w/ Penalty
102
venting rank-collapse leads to better per-
formance. In the first set of experiments, we apply the proposed Lp penalty to Rain-
100
-20
Rainbow (nm4)
bow in the data-efficient online RL setting
-101
(n = 4). In the second set of experiments, present evidence for prevention of rank
10>
Derrn Abwek
seam suam hoder
Yor's Roverges
Forp
Dodble Dura
Vicurd o Wis
Adrer
Nt. Paa Man
22000
Endure
Space treatees
Hucky
Random
collapse by comparing rank values for dif- ferent runs.
Road
Janes
Game
As we will show in the next section, the state-of-the-art Rainbow (Hessel et al., 2018) algorithm also suffers form rank col- lapse in the data-efficient online RL setting when more updates are performed per gradient step. In this section, we applied our penalty Ly to Rainbow with n 4, and obtained a median 20.66% % improvement on top of the base method. This result is summarized below.
Figure 1818 Performance of Rainbow (n = 4) and Rain- bow (n = 4) with the ( penalty (Equation 6. Note that the penalty improves on the base Rainbow in 12/16 games.
Asterix
Beam Rider
Demon Attack
Double Dunk
4000
5000
1200
20
AveragaReuum
3000
4000
1000
10-
3000
800
2000
2000
600
1000
1000
400
-10
200
-20
0
50
Stops
Stops
Environment
Environment
Enduro
Ice Hockey
James Bond
Ms. Pac-Man
5000
2500
Average Return
1000
4000
800
-10
1500
400
1000
-15
1000
-20
0
25
50
75
100
25
50
75
100
50
100
25
50
75
100
Environment Steps
Enuironment Steps
Enviromment Steps
Enwironment Steps
Pong
Q'Bert
Runner
Seaquest
20
20000
40000
2500
Average Return
10
15000
30000
2000
10000
20000
1000
5000
10000
500
0
25
50
75
100
25
50
75
100
25
50
100
25
50
75
100
Ervironment Steps
Enuironment Steps
Environment Steps
Erviranment Steps
Space Invaders
Wilzard OF Wor
Yars's Revenge
Zaxoon
1000
30000
8000
4000
Average Retum
25000
20000
400
2000
15000
200
10000
2000
0
5000
75 Environment Steps
25
50
100
50
100
Enwironment Steps
Environment Steps
Environment
Figure A.19: Learning curves with n 4 gradient updates per environment step for Rainbow(Blur and Rainbow with the (T) penalty (Equation 6) (Red) on 16 games, corresponding to the har plot above. One unit on the x-axis is equivalent to IM environment steps.
21

---

Published as a conference paper at ICLR 2021
A.7 RELAXING THE NORMALITY ASSUMPTION IN THEOREM 4.1
We can relax the normality assumption on S in Theorem 4.1. An analogous statement holds for non-normal matrices for a slightly different notion of effective rank, denoted as sranks, (M+), that utilizes eigenvalue norms instead of singular values. Formally, let x (M+),... ... (2 be the (complex) eigenvalues of Mg arranged in decreasing order of their norms, i.e.. (1 (M+)] (x+(M))] 2 .., then,
(M+) 1= A (M))
x min k
2 21-
A statement essentially analogous Theorem 4.1 suggests that in this general case, sranks, (M&) decreases for all (complex) diagonalizable matrices S, which is the set of almost all matrices of size dim(S). Now, if S is approximately normal, i.e., when (o,(S) - [S)[ is small, then the result in Theorem 4.1 I also holds approximately as we discuss at the end of Appendix C.
We now provide empirical evidence showing that the trend in the values of effective rank computed using singular values, srank; () is almost identical to the trend in the effective rank computed using normalized eigenvalues, sranks,> (.). Since eigenvalues are only defined for square matrix + in practice, we use a batch of d dim(s a)) state-action pairs for computing the eigenvalue rank and compare to the corresponding singular value rank in Figures A.20 and A.21.
Astari:
Brealout
4.1
420
350
412
300
333
332
350
200
237
330
200
350
400
$30
366
203
266
400
306
120
280
3:0
400
560
120
206
300
530
303
200
363
465 56a
Figure A.20: Comparing different measures of effective rank run of offline DQN in the 5% replay setting, previously studied in Figure A.3.
Connection to Theorem 4.1. We computed the effective rank of & instead of S, since S is a theo- retical abstraction that cannot be computed in practice as it depends on the Green's kernel (Duffy, 2015) obtained by assuming that the neural network behaves as a kernel regressor. Instead, we com- pare the different notions of ranks of & since & is the practical counterpart for the matrix, S, when using neural networks (as also indicated by the analysis in Section 4.2). In fact, on the gridworld (Figure A.21), we experiment with a feature & with dimension equal to the number of state-action kernel parameterization
pairs, i... dim(o(s a)) |S,, with the same number of parameters of the Q-function: ((s, a) = Ex'a'' w(s', a') as) a, s', a'). This can also be considered as perform- ing gradient descent on a "wide" linear network, and we measure the feature rank while observing similar rank trends.
Since we do not require the assumption that S is normal in Theorem 4.1 to obtain a decreasing trend in sranks,x()), and we find that in practical scenarios (Figures A.20 and A.21), sranky ( R s A (t) with an extremely similar qualitative trend we believe that Theorem 4.1 still explains the rank-collapse practically observed in deep Q-learning and is not vacuous.
Gridwwerld
Oridworld
GridWorld
GridWorld
1.55
Supevised
275
supervsie
1.5
150
20000
154
200
smank. 20.00000
150
200
200
Superdtred
302
14
smank
37
77
15
Superviedd
1-200
100
350
305 600
560
100
200
360
600
500
300 300
330
403
500
300
203
200
400
500
Fitting
Figure A.21: Comparison of xranks,x(#) and srank,(0) on the gridworld in the offline setting (left) and the online setting (right), when using deep linear network with dim(ø(s, a)) |S|[AA,. Note that both notions of effective rank exhibit similar decreasing trend and are closely related to each other.
22

---

Published as a conference paper at ICLR 2021
A.8 NORMALIZED PLOTS FOR FIGURE 3/ FIGURE A.6
In this section, we provide a set of normalized srank and performance trends for Atari games (the corresponding unnormalized plots are found in Figure A.6). In these plots, each unit on the x-axis is equivalent to one gradient update, and so since n 8 prescribes 8x many updates as compared to n 1, it runs for 8x as long as n 1. These plots are in Figure A.22.
Seaquest
Seaqueett
5.00
500
DON pi-11
D4N ti-11
530
(ood)
DON
(i-4)
300
200
200
200
3:0
FIOK (--11
T10h (n-4
(1
10000
125.0
30000
20093-
50000
10000
15.0
33000
5000
2500
Namsker of www.iieet spiated
Nunsber of gradiient spiliate
Wturbbr of giallinn ugpilidee
Nuurbbrr www.lleeettt.coo.ooooooooooooo.
Numberr graalient upilacee
Figure A.22: Rank collapse in DQN as function of gradient updates on the x-axis for five Atari games in the data-efficient online RL setting. This setting was previously studied in Figure A.6. Note that lesser number of updates per unit amount data, L.e., smaller values of possess larger srank, values.
Note that the trend that effective rank decreases with larger n values also persists when rescaling the x-axis account for the number of gradient steps. all but one game. This expected since it tells us that performing bootstrapping based updates in the data-efficient setting (larger n values) still leads to more aggressive rank drop as updates are being performed on relatively more static dataset for larger values of n.
B HYPERPARAMETERS & EXPERIMENT DETAILS
B. ATARI EXPERIMENTS
We follow the experiment protocol from Agarwal al. (2020) for all our experiments including hyperparameters and agent architectures provided in Dopamine and report them for completeness and ease of reproducibility in Table B.1. We only hyperparameter selection ization experiment a, based on results from 5 Atari games (Asterix, Seaquest, Pong, Breakout and Seaquest). We will also open source our code to further aid in reproducing our results.
the regular-
Evaluation Protocol. Following Agarwal et al. (2020), the Atari environments used in our ex- periments are stochastic due sticky actions, i.e., there is 25% chance every time step that the environment will execute the agent's previous action again, instead of the agent's new action. All agents (online or offline) are compared using the best evaluation score (averaged over 5 runs) achieved during training where the evaluation is done online every training iteration using a r-greedy policy with 0.001. We report offline training results with same hyperparameters over 5 random seeds of the DQN replay data collection, game simulator and network initialization.
Offline Dataset. As suggested by Agarwal et al. (2020), we randomly subsample the DQN Replay dataset containing 50 millions transitions to create smaller offline datasets with the same data distri- bution as the original dataset. We use the 5% DQN replay dataset for most of our experiments. We also report results using the 20% dataset setting (4x larger) to show that our claims are also valid even when we have higher coverage over the state space.
Optimizer related hyperparameters. For existing off-policy agents, step size and optimizer were taken as published. We used the DQN (Adam) algorithm for all our experiments, given its superior performance over the DQN (Nature) which uses RMSProp, as reported by Agarwal et al. (2020).
Atari 2600 games used. For all our experiments in Section 3, we used the same set of 5 games utilized by Agarwal al. (2020); Bellemare al. (2017) present analytical results. For
23

---

Published as a conference paper at ICLR 2021
Table B.1: Hyperparameters used the offline and online RL agents in experiments.
Hyperparameter
Setting (for both variations)
Sticky actions
Yes
Sticky action probability
0.25
Grey-scaling
True
Observation down-sampling
(84, 84)
Frames stacked
Frame skip (Action repetitions)
4
Reward clipping
[-1. 1]
Terminal condition
Game Over
Max frames per episode
108K
Discount factor
0.99
Mini-batch size
32
Target network update period
every 2000 updates
Training environment steps per iteration
250K
Update period every
environment steps
Evaluation e
0.001
Evaluation steps per iteration
125K
network: channels
32, 64, 64
Q network: filter size
8, 4 3 3
Q-network: stride
1
Q-network: hidden units Hardware
512
Tesla P100 GPU
Hyperparameter
Online
Offline
Min replay size for sampling
20,000
Training (for e-greedy exploration)
0.01
e-decay schedule
250K steps No
Fixed Replay Memory
Yes
Replay Memory size (Online)
1,000,000 steps
Fixed Replay size (5%)
2,500,000 steps
Fixed Replay size (20%)
10,000,000 steps
Replay Scheme
Uniform
Uniform
Training Iterations
500
empirical evaluation in Appendix A.5, we use the set of games employed by Fedus et al. (2020b) which are deemed suitable for offline RL by Gulcehre et al. (2020). Similar in spirit Gulcehre et al. (2020), we use the set of 5 games used for analysis for hyperparameter tuning for offline RI. methods.
5 games subset: ASTERIX, QBERT, PONG, SEAQUEST, BREAKOUT
16 game subset:
In addition to 5 games above, the following 11 games: DOUBLE DUNK, JAMES BOND, Ms. PACMAN, SPACE INVADERS, ZAXXON, WIZARD OF WOR, YARS" REVENGE, EN- DURO, ROAD RUNNER, BEAMRIDER, DEMON ATTACK
B.2 GRIDWORLD EXPERIMENTS
We use the gridworld suite from Fu et al. (2019) to obtain gridworlds for our experiments. All of our gridworld results are computed using the 16 16 6SMOTTHOOS environment, which consists of 256-cell grid, with walls arising randomly with probability of 0.2. Each state allows different actions (subject to hitting the boundary the grid): move left, move right, move up, move down and op. The goal in this environment is to minimize the cumulative discounted distance to a fixed goal location where the discount factor is given by y = 0.95. The features for this Q-function given by randomly chosen vectors which are smoothened spatially in local neighborhood of grid cell (xe, v)-
We deep Q-network with two hidden layers of size (64, 64), and train it using soft -elarning with entropy coefficient 0.1, following the code provided by authors of Fu et al. (2019). We use first-in-fisst out replay buffer of size 10000 to store past transitions.
24

---

Published as a conference paper at ICLR 2021
C PROOFS FOR SECTION 4.1
In this section, we provide the technical proofs from Section 4.1. We first derive a solution to optimization problem Equation 1 and show that indeed comes out have the form described in Equation 2. We first introduce some notation, including definition of the kernel G which was used for this proof. This proof closely follows the proof from Mobahi al. (2020).
Definitions. For any universal kernel the Green's function (Duffy, 2015) of the linear kernel operator given by: [I.Q] (s, a) Eisrar) u((s, as)) a') is given by the function that satisfies:
Σ ul(ss,)) g((s' a (5, a)) (((s. a) (s. (5.a)
(C.1)
where å is the Dirac-delta function. Thus, Green's function can be understood as kernel that "inverts" the universal kernel u to the identity (Dirac-delta) matrix. We can then define the matrix G as the matrix of vectors g(s.a) evaluated on the training dataset, D, however note that the functional B(s,a) can be evaluated for other state-action tuples, not present in D.
G( az), (sy, ay)) == g(((, az), ($j, as)) and B(s.a) [ = g[((s a), a:)) v(s;, E D. (C.2)
Lemma C.0.1. The solution to Equation 1 is given by Equation 2.
Proof. This proof closely follows the proof of Proposition from (Mobahi et al., 2020). We revisit key aspects the key parts of this proof here.
We restate the optimization problem below, and solve for the optimum Q₂ to this equation by ap- plying the functional derivative principle.
min ((Q)= = Σ (Q(s., a.) - (s, a:))² + Σ QEE
Σ
ua(s (s' a)ssaa)
(8.a) (s'
The functional derivative principle would say that the optimal Q to this problem would satisfy, for any other function f and for small enough + O.
V aJ(Qu +&f)
==0 = 0.
(C.3)
a=
By setting the gradient of the above expression to 0, we obtain the following stationarity conditions on Qs (also denoting (s;, a;) x;) for brevity:
Σ - (() yx(x)) + Σ u(xx [u(xxx')uuu xxx((x) =. X,E
(C.4)
Now, we invoke the definition of the Green's function discussed above and utilize the fact that the Dirac-delta function can expressed in terms of the Green's function, we obtain a simplified version of the above relation:
Σ
cu(x x') [ - (x(xx))g(x( xx) = -c E u(x (x)))
(C.5)
X
X.ED
Since the kernel u(x,x') x') is universal and positive definite, the optimal solution Qx is given by:
Qu a) =
(Qx a:) (s;, a.)) g((s, a), (s, a.)). (sIDa))ED
Σ
(C.6)
Finally we can replace the expression for residual error, Q (s; a,) y& (s,, a;) using the green's kernel on the training data by solving for it in closed form, which gives us the solution in Equation 2.
1 - B (Q+ yk) = g (cI -yk.
Qu a) -
(C.7)
c
n
25

---

Published as a conference paper at ICLR 2021
Next, now state and prove slightly stronger version of Theorem 4.1 that immediately implies the original theorem.
Theorem C.1. Let S be shorthand for 7P A and assume S is normal matrix. Then there exists an infinite, strictly increasing sequence of firring iterations, (kt) starting from k = 0. such that, for any two singular-values (S)) and (S{S) of with o,(S) S (S(),
T. (Mp)) < (M - 0,
VIEN N. and l' 24,
(C.8)
o,(Mn;
(M(M,)
oy(S)
Therefore, the effective rank of M2 satisfies: sranks (May) I sranks (Mx.)- Furthermore,
(M
(M&)) of (M())
((011)
(2(())
VIEN and t 12 ka.
+o
(C.9)
of (M,
Therefore, the effective rank of M, sranks (M,), outside the chosen subsequence is also controlled above by the effective rank on the subsequence (srankg (M&.))
To prove this theorem, we first show that for any two fitting iterations, t < t', if S and S are positive semi-definite, the ratio of singular values and the effective rank decreases from / to l'. As an immediate consequence, this shows that when S is positive semi-definite, the effective rank decreases at every iteration, i.e., by setting ky (Corollary C.I.I).
To extend the proof to arbitrary normal matrices, we show that for any S, a sequence of fitting iter- ations (kz) ) can be chosen such that S (approximately) positive semi-definite. For this subse- quence of fitting iterations, the ratio of singular values and effective rank also decreases. Finally, to control the ratio and effective rank on fitting iterations outside this subsequence, we construct an upper bound on the ratio f(t): c.(M. (M,) < (t), and relate this bound to the ratio of singular values
on the chosen subsequence.
Lemma C.1.1 (sranks (Mę) decreases when S is PSD.). Let S be a shorthand for S = 7p A and assume is a normal matrix. Choose any 1, E N such that I < If and S are positive semi-definite, then for any two singular-values (S) and (S) of such that (S (S);
T (M)) jj (M,)
T MM,)
< (S)
(C.10)
J. (M.)
(S
Hence, the effective rank of M2 decreases from t to t': sranks (Mr) S sranks (M,).
Proof. First note that Mg given by:
M " Σ sK
(C.11)
From hereon, we omit the leading y term since it is a constant scaling factor that does not affect ratio or effective rank. Almost every matrix admits complex orthogonal eigendecomposition. Thus, we can write S = UX(S)U" And any power of S, i.e., St can be expressed as: S UX(S)'U" and hence, we can express Mş as:
1 1 X(S)*) x(S)
M, = U (SS) UH
U diag
U
(C.12)
Since S is normal, its cigenvalues and singular values are further related as (s(S) = (Sx And this also means that M; is normal, indicating that o, (M+) (M,)) Thus, the singular values of Mj can be expressed as
1 - (S)
(M,) =
(C.13)
1 (S(
When 8 is positive semi-definite, A,(S)* = (S) enabling the following simplification:
| - (8))
(MM)) = || (S]
(C.14)
26

---

Published as a conference paper at ICLR 2021
To show that the ratio of singular values decreases from i to t', we need to show that f(o) = 11-d" an increasing function of when t' It can be seen that this the case, which implies the desired result.
--
To further show that sranks (M) 2 sranks (Mr), we can simply show that Vi [L, n].
hi) == _ (M&)
Σm=1 (M,) increases with k, and this would imply that the sranks (M&) cannot increase
from to h t.. We can decompose hig (i) as:
hz( = E E (M(M)) (M)s) 1 Dimtt (M(M.)
(C.15)
Σj=1 (M,)
Since o, (Ms)/or decreases over time k for all j, o S (S), the ratio in the denomi- nator of (i) decreases with increasing k implying that ht) increases from t to t'.
Corollary C.1.1 (sranks (Mx) decreases for PSD S matrices.). Let S be a shorthand for S = yP A. Assuming that $ is positive semi-definite, for any k,t E N, such that t > k and that for any two singular-values (S) and (s() of S, such that o,(S) < ay()),
(M,))
(M&)) oi(S))
(C.16)
jj (M.) (M,)))
o,(S))
Hence, the effective rank of M2 decreases with more fitting iterations: sranks (M,) S sranks sranks(Ma).
In order to now extend the result to arbitrary normal matrices, must construct a subsequence of fitting iterations (ka) where S is (approximately) positive semi-definite. To do so, we first prove a technical lemma that shows that rational numbers, i.e., numbers that can be expressed as r q² for integers p, Q E are "dense" the space of real numbers.
Lemma C.1.2 (Rational numbers are dense in the real space.). For any real number there exist infinitely many rational numbers y such that a can be approximated by 2 upto 2 accuracy.
p
a
q2
(C.17)
Proof. We first use Dirichlet's approximation theorem (see Hlawka et al. (1991) for a proof of this result using pigeonhole argument and extensions) to obtain that for any real numbers and N > 1, there exist integers p and g such that I I N and,
qq
pl
(C.18)
N +
N
Now, since 2 1> O, we can divide both sides by q. to obtain:
(C.19)
Ng d²
To obtain infinitely many choices for E we observe that Dirichlet's lemma is valid only for all values of N that satisfy N S Iqa-ppl Thus if we choose an N' such that N' Nmax where Nmax defined as:
{
N Imax max
1q'a-p'l E.
(C.20)
Equation C.20 essentially finds new value of N, such that the current choices of and which were valid for the first value of N do not satisfy the approximation error bound. Applying Dirichlet's lemma to this new value of N' hence gives us a new set of p' and g' which satisfy the 7"t approx- imation error bound. Repeating this process gives us countably many choices of (p, 9) pairs that satisfy the approximation error bound. As a result, rational numbers are dense in the space of real numbers, since for any arbitrarily chosen approximation accuracy given by 9², we can obtain atleast
one rational number, 2 which is closer to than +. This proof is based on Johnson (2016).
D
Now utilize Lemmas C.I.1 and C.1.2 to prove Proposition 4.1.
27

---

Published as a conference paper at ICLR 2021
Proof of Proposition 4.1 and Theorem C.1 Recall from the proof of Lemma C.1.1 that the sin- gular values of M2 are given by:
1 - (S)*
0. (M.)
=
(C.21)
1 (S)
Bound on Singular Value Ratio: The ratio between or (M&) and oy (M&) can be expressed
0: (;(M.)
= 1 1 1 (s)
(C.22)
0y [M&)
1 - ())
(S)
For a normal matrix S, (S) = (S(( so this ratio can be bounded above as
(M+) 1 oS) 1- X,())
(C.23)
Jj (M+)
1 11-0 I-
(s)
Defining f(k) be the right hand side of the equation, we can verify that f is a monotonically decreasing function in k when o; < K.. This shows that this ratio of singular values in bounded above and in general, must decrease towards some limit a flk)..
Construction of Subsequence: We now show that there exists subsequence (A:) for which S approximately positive semi-definite. For ease of notation, let's represent the i-th eigenvalue as (S) [A:(S)] e. where 0; > 0 ís the polar angle of the complex value (;(s) and [A:(S)] is its magnitude (norm). Now, using Lemma C.1.2, we can approximate any polar angle, 0, using a
rational approximation, i.e., we apply lemma C.1.2 on 0g
2n
0:
Pi
3 Pr. E N, s.t.
(C.24)
2
q
4
Since the choice of q: is within control we can estimate 9g for all eigenvalues (S) to infinites- imal accuracy. Hence, we can approximate 0g ~ 2n Pi.
2n We will now use this approximation to
construct infinite sequence (kx) shown below: k 1. LCM((1 ...) VjEN.
(C.25)
where LCM is the least-common-muliill of natural numbers -1.--192-
In the absence of any approximation error in 0g, we note that for any and for any E N as defined above, *s) (A) exp (2iTT= Es
kz) = (A)())) since the polar angle for any ky is going to be multiple of 2n, and hence it would fall the real line. As result, Sht will be positive semi definieie since all eigenvalues are positive and real. Now by using the proof for Lemma C.I.I, obtain the ratio of and j singular values Since the approximation error in 0g can be controlled to be infinitesimally small to prevent any increase in the value of srank, due to it (this can be done given the discrete form of srankı), note that the above argument applies even with the approximation, proving the required result on the subsequence.
q.
increasing over the sequence of iterations (2
Controlling All Fitting Iterations using Subsequence:
We now relate the ratio of singular values within this chosen subsequence to the ratio of singular values elsewhere. Choose t, / E N such that t > kt. Earlier in this proof, we showed that the ratio between singular values is bounded above by a monotonically decreasing function f(t), so
O2 (M, < f(t) < f(k).
(C.26)
o3 (M)
Now, we show that that f(k) is in fact very close to the ratio of singular values:
| - (S) k
1 1- (S)
(M,)
(S)
1 1 (S)
f(ki)
(C.27)
|1 (S) (S) kz
(S)
(M.)
1- (S)
1- (S)
The second term goes to zero as ką increases; algebraic manipulation shows that this gap be bounded by
f(k) < (Ma)) +
(S)
(S,(S)
1 1 X
(C.28)
(M.)).) (S(
G (S)
1 (S)
constant
28

---

Published as a conference paper at ICLR 2021
Putting these inequalities together proves the final statement,
((((()))) (c((5) (())())
M.) oj [M) Jj (Ma)
0; (M,)) +
(C.29)
Extension to approximately-normal S. We can extend the result in Theorem C.I (and hence also Theorem 4.1) to approximately- S. Note that the main requirement for normality of (i.c., (S) = [)((s) is because it is straightforward to relate the eigenvalue of S to M as shown below.
(M = 1- (S)* 1 X,
(C.30)
Now, since the matrix S is approximately normal, we can express it using its Schur's triangular form as, S = U +A+ departure from normality of S is defined as: A(S) == infN ||N||, where the infimum is computed over all matrices N that can appear in the Schur triangular form for For normal S only a single value of N 0 satisfies the Schur's triangular form. For approximately normal matrix S, ||N||2 S (S) S E, for small e.
+ N). U where A is a diagonal matrix and N an "offset" matrix. The
Furthermore note that from Equation 6 in Ruhe (1975), we obtain that
o (S) (A)( I A(S) S E,
(C.31)
implying that singular values and norm-eigenvalues close each other for S.
Next, let us evaluate the departure from normality M,. First note that, S = U- UA+ UH, and so, M₁ U. | (A N)²) -HH and if N S c, for small epsilon (i.e., considering only terms that are linear N for (A + NY)), we note that:
1
(M,) - (M. S Σ j. (ASS) S (1 (S)()
(C.32)
Thus, the matrix Mg is also approximately normal provided that the max eigenvalue norm of $ is less than 1. This is true, since S 7P* A (see Theorem 4.1, where both pa and A have eigenvalues less than 1, and 7 < 1.
Given that we have shown that M; is approximately normal, we can show that tranks(Ma, only (M&), differs from x i.e., the effective rank of eigenvalues, in bounded amount. If the value of e then small enough, we still retain the conclusion that srank; (M&) generally decreases with more training by following the proof of Theorem C.I.
D PROOFS FOR SECTION 4.2
In this section, we provide technical proofs from Section 4.2. We start by deriving properties of opti- mization trajectories of the weight matrices of the deep linear network similar to Arora et al. (2018) but customized to our set of assumptions, then prove Proposition 4.1, and finally discuss how to ex- tend these results to the fitted Q-iteration setting and some extensions not discussed in the main pa- per. Similar to Section 1. we assume access to a dataset of transitions, D = {(s., ai, r(s,, at), s in this section, and assume that the same data is used re-train the function.
Notation and Definitions. The Q-function is represented using deep lincar network with at least 3 layers, such that
((s,a) = W WN-1 Wi where N N 3, WN E LIddN-1,
(D.1)
and W; E pddxdd- for = 1.....,. N 1. We index the weight matrices by a tuple (k. t): W, t)
denotes the weight matrix W at the t-th step of gradient descent during the k-th fitting itera- tion (Algorithm 1). Let the end-to-end weight matrix W N w.- W, be denoted shorthand as W NaI, and let the features of the penultimate layer of the network, be denoted W (k; ()
29

---

Published as a conference paper at ICLR 2021
tk) ... Wi(ktt), t). ...,,)....((kk
(klk, t) is the matrix that maps input [s; al to corresponding fea- tures ((s, a). In our analysis, it is sufficient to consider the effective rank of Wkk,, t) since the features & are given by: (kk, t) Wo(k, t)(S; AI, which indicates that:
rank( t)) = rank (W, A]) & min (rank( (a(k, t)), (a::
only concerned about rank V ((k, t)) which justifies our choice for analyzing srank, (Wo (k, (ok,t)) t)).
Assuming the state-action space has full rank,
Let Lx+1 (W N-1 (k, denote the mean squared Bellman error optimization objective in the k-th fitting iteration.
[D]
L (k. t))
Σ
(Ww(k, t) (k)sa) (s)) where Yk = R. + R Qu.
When gradient descent is used to update the weight matrix, the updates to Wi(k, t) are given by:
Wk (k, 0L (W N:1 (k)
aw (k,
If the learning rate 17 is small, we can approximate this discrete time process with a continuous-timg differential equation, which we will use for our analysis. We use W (k, t) to denote the derivative of (K:, 8) with respect to f, for given k.
W, (k, -17 0L (W (a,
(D.2)
OW, (k,t)
In order to quantify the evolution of singular values of the weight matrix, (k; (), we start by quantifying the evolution of the weight matrix W (k,t) t) using more interpretable differential equation. In order to do so, we make an assumption similar to but not identical as Arora et al. (2018), that assumes that all except the last weight matrix are "balanced" at initialization 0, 0. i.c.
ViE [0, , N 2) W (0, O + (0, W. 0)W, O).
(D.3)
Note the distinction from Arora et al. (2018), ) the last layer is not assumed to be balanced. As a result, may not be able comment about the learning dynamics of the end-to-end weight matrix, but we prevent the vacuous case where all the weight matrices are rank 1. Now we are ready to derive the evolution of the feature matrix, W (k,
Lemma D.O.1 (Adaptation of balanced weights (Arora et al., 2018) 1) across FQI iterations). Assume the weight matrices evolve according Equation D.2, with respect to L. for all fitting iterations
k. Assume balanced initialization only for the first N 1 layers, i.e., W Wj+1(0, 0)² S'"W, WWtii(1000 ++1(0,00) 0) (0,0,00 0) W, (0, 0)" V E., 1.... ,N 2. Then the weights remain balanced throughout, i.e.
A k, W Wk+ ((lkk,)"",,a., (K+i(ktt W (k, (t, .N-, 2
(D.4)
Proof. First consider the special case of 1: = O. To beign with, in order to show that weights remain balanced throughout training in l- iteration, will follow the proof technique in Arora et al. (2018), with some modifications. First note that the expression for 0La (W can be expressed as:
8W, (k,4)
aL (W NaI (k,tt) (k,
(L N.). dWNa
1-1
II imj+1
wT
II W?
dL [ N.)
1-1
= =(WT W j+1 J+2
W
II
dW
N:1
Now, since the weight matrices evolve as per Equation D.2, by multiplying the similar differential equation for W, with W (k; t) on the right and multiplying evolution of W with W (k) from the left, and adding the two equations, we obtain:
A j E (0, ... N 2]: W (0, ()W (0, w, (0, (0,4)
(D.5)
30

---

say the Published as a conference paper at ICLR 2021
We can then take transpose of the equation above, and add it to itself, to obtain easily integrable expression:
(0,t) + Wi+ W (0,)) d W (0, 1) W (0,
W, (0,0) + W, (0. (0. d (0, ,0, (D.6)
dt
Since we have assumed the balancedness condition the initial timestep 0, and the derivatives of the two quantities are equal, their integral will also be the same, hence we obtain:
w 1+ (0. 1) WT j+1 (0, = (, (0,,
(D.7)
Now, since the weights after T iterations in fitting iteration k: = 0 are still balanced, the initialization for k 1 is balanced. Note that since the balancedness property does not depend on which objective gradient is used to optimize the weights, as long as W, and W, j+11 utilize the same gradient of the loss function. Formalizing this, we can show inductively that the weights will remain balanced across all fitting iterations h and at all steps t within each fitting iteration. Thus, we have shown the result in Equation D.4.
Our next result aims at deriving the evolution of the feature-matrix that under the balancedness condition. We will show that the feature matrix, W (k. evolves according to similar, but distinct differential equation as the end-to-end weight matrix, WN (k, t), which still allows us to appeal to techniques and results from Arora et al. (2019) study properties of the singular value evolution and hence, discuss properties related to the effective rank of the matrix, W (k,
Lemma D.0.2 ((Exeension of Theorem 1 from Arora et al. (2018)). Under conditions specified in Lemma D.O.I, I, the feature matrix, W a (k:, 1) evolves as per the following continuous- time differential equation, for all fitting iterations k:
W = - (W..k./Wo(k.0777 NEI (K,
(WN.(()))))) dW
(k. o
Proof. In order to prove this statement, we utilize the fact that the weights upto layer N are balanced throughout training. Now consider the singular value decomposition of any weight w, (unless otherwise states, we use W, to refer to (k,k, t) in this section, for ease of notation. W, U VT. The belancedness condition re- we-ttitten using SVD of the weight matrices is equivalent to
V V T E J+1 = -
(D.8)
Thus for all j on which the balancedness condition is valid, it must hold that D Ex+1 M since these are both the eigendecompositions of the same matrix (as they are equal). As result, the weight matrices W, and W j+1 share the same singular value space which can be written as Pi 2 P2 2 ... 2 Pm- The ordering of eigenvalues can be different, and the matrices U and V can also be different (and be rotations of one other) but the unique values that the singular values would take are the same. Note the distinction from Arora et al. (2018), where they apply balancedness on all matrices, and that in case would trivially give rank-1 matrix.
Now this implics, that we can express the feature matrix, also in terms of the common singular values, (PL, ... Pm), for example, tkk,,t D (VPI..... .Pm) Pm V where U) = Vi+1O,. where O, is an orthonormal matrix. Using this relationship, following:
N-1
II w. wi(k 1)
II w.(k,t) = [wo(k:])W?(k..)) N= 11
II t.(k,t (o (kk -
w. 1)
1=1
31

---

Published as a conference paper at ICLR 2021
Now, we can use these expressions to obtain the desired result, by taking the differential equations governing the evolution of Wi(k, t), for E [1,... .N= 1], multiplying the i-th equation by II#+ W5(k; t) from the left, and II; 1--1 Wk(k, t) to the right, and then summing over i.
N-1
N-1
i-
(k) =
Σ
II (K.t)
ti(k,t)
II (k.tt)
1=1
1=++1
N-1
N-1
N (k, O II (K, 2+1
dL W N:))
=-
Σ
II
(k, o7 II w (1
dW Na1
The above equation simplifies to the desired result by taking out W Wrrk,, t) from the first summation. and using the identities above for each of the terms.
Comparing the previous result with Theorem 1 in Arora et al. (2018), we note that the resulting differential equation for weights holds true for arbitrary representations or features in the network provided that the layers from the input to the feature layer are balanced. A direct application of Arora et al. (2018) restricts the model class to only fully balanced networks for convergence analysis and the resulting solutions to the feature matrix will then only have active singular value, leading to less-expressive neural network configurations.
Proof of Proposition 4.1. Finally, are ready to use Lemma D.0.2 to prove the relationship with evolution on singular values. This proof can be shown via a direct application of Theorem 3 in Arora et al. (2019). Given that the feature matrix, W (k, satisfies very similar differential equation as the end-to-end matrix, with the exception that the gradient of the loss with respect to the end-to-end matrix is pre-multiplied by W (N(k,t) t)". As a result, we can directly invoke Arora et al. (2019)'s result and hence, we have Vr E [1,...,,dd)) ,d)]
that:
or(k,t)= (02 1- (Ww(k: 1)7 d.N.A (Wr,)) u. (K,
(D.9)
dWW
Further, as another consequence of the result describing the evolution of weight matrices, we can also obtain a result similar to Arora et al. (2019) that suggests that the goal of the gradient update on the singular vectors U(k,t) t) and V(k, of the features W (kkk, t) U(k, ()k, is to align these spaces with W N (kc t)T dlx, dlx.=(Wx..). JW
D.1 EXPLAINING RANK DECREASE BASED ON SINGULAR VALUE EVOLUTION
302
1.5
10
322
107
103
100
200
403
530
120
200
355
402
500
233
2.00
400
300
1.00
200
300
45c
350
220
360
502
Figure D.I: Evolution of singular values of on Atari. The larger singular values of the feature matrix & grow at disproportionately higher rate than other smaller singular values as described by equation 4.
In this section, we discuss why the evolution of singular values discussed in Equation 4 indi- cates a decrease in the rank of the feature matrix within a fitting iteration k. To see this, let's consider the case when gradient descent has been run long enough (i.e., the data-efficient RL case) for the singular vectors to stabilize, and consider the evolution of singular values post timestep Z to in training. First of all, when the singular vectors stabilize, we obtain that u, (ki, 1)aT W N (k:, ()Tdd)).eeele ddL..eWW.... (k: 1) is diagonal (extending result of Corollary 1 from Arora al. (2019)). Thus, we can assume that
dW
4f (k, () (k, tyr dl
A.N.A C.N.A( W K.)) v, (k,tt) f(k,t) e, dr.
dW
where e, is given by the unit basis vector for the standard orthonormal basis, f is a shorthand for the gradient norm of the loss function pre-multiplied by the transpose of the last layer weight matrix,
32

---

Published as a conference paper at ICLR 2021
and d, denotes the singular values of the state-action input matrix, [S, A]. In this case, we can re- re-write Equation 4 as:
o () (c."(,)))))
t(k,t)-c C, d,.
(D.10)
Note again that unlike Arora et al. (2019), the expression for f(k, t) is different from the gradient of the loss, since the weight matrix Wx Wk(k, t) is multiplied to the expression of the gradient in our case. By using the fact that the expression for f(k: () is shared across all singular values, we can obtain differential equations that are equal across different (k; 1) and ar (ki, l). Integrating, we can show that depending upon the ratio d. and the value of N, the singular values or t) and or (k, t) will take on different magnitude values, in particular, they will grow at disproportionate rates. By then appealing to the result from Proposition 4.1 in Section 4.1 (kernel regression argument), can say that disproportionately growing singular values would imply that the value of sranks ( (W (k(k,tt) decreases within each iteration A as we will discuss next.
e,r-d,7
Interpretation of the abstract rank-regularized objective. We now discuss the form for the ab- stract regularizd objective Equation that we utilize in Section 4.2. Intuitively, the justifica- tion for Equation 5 is that larger singular values grow much faster than small singular values, which dictates how the ratio of singular values evolves through time, thereby reducing effective rank.
(k,, t)) decreases within each fitting iteration (i.e., decreases over the variable 2). Now, we will argue that for a given value of effective rank at f = 0 at fitting iteration & (denoted srank, (k (k),))) the effective rank after steps of gradient descent, srank,( (k,,, T)). constrained to be equal to some constant Ek < srank, ( [ a (k, 0)) due to the implicit regularizaton effect of gradient descent. To see this, note that if (k 0) > (k 0), then o, t)) increases at a much faster rate than oy (k. t) with increasing t (see Equation D.10 and Arora et al. (2019), Equation 11) and hence, the value of hi,) is increasing over l:
The discussion in the previous subsection shows that the effective rank, sranks (Wo(k,
(Wook,
(1) = =E j=1 E (k, 1 Di o (W
O &Wo (D.11) 1+ ++ ( (k.t))
Σ (K,,
as the ratio between larger and smaller singular values increases. Using Equation D.11, we note that the value of (i) approaches 1 as the ratio a /o decreases (in the limit, the ratio is zero). An increase in the value of (1) implies a decrease in sranks, which can be expressed as:
sranks W (k, 1)) = min (hx(t) 21-8
Thus, by rumning gradient descent for To -(Ex) (a function of E&) steps within a fitting iteration, k, the effective rank of the resulting W (k, To) satisfies srank, W (Wakk, To)) = εk- Now, since the solution W (k, To) satisfies the constraint sranks (k. To)) = Ek < srank; a (k, 0)), we express this solution using the solution of a penalized optimization problem (akin to penalty methods) that penalizes sranks (W&) 6) for suitable coefficient λR. which is a function of Eg. We assume A > since when running gradient descent long enough (i.e., for To steps in the above discussion), we can reduce srank; (Wo) from its initial value (note that Ek < sranks (onnk(WWcll (W& 0)), indicating non-zero value of regularization.
(anks(WW))
D.2 PROOF OF PROPOSITION 4.2: COMPOUNDING RANK DROP IN SECTION 4.2
In this section, we illustrate that the rank drop effect compounds due to bootstrapping and prove Proposition 4.2 formally. Our goal demonstrate the compounding effect: a change in the rank at a given iteration gets propagated into the next iteration. We first illustrate this compounding effect and then discuss Theorem 4.2 as a special case of this phenomenon.
Assumptions. We require two assumptions pertaining to closure of the function class and the change in effective rank due to reward and dynamics transformations. be able for this analysis. We assume that the following hold for any fitting iteration i of the algorithm.
Assumption D.1 (Closure). The chosen function class W. W.... WN is closed under the Bellman evaluation backup for policy т. That is, if Q = W (k- 1jw&(ke (k ())s: ATT then there exists an assignment of weights to the deep linear net such that the corresponding target value R+ px Qk can be written as (R + 1ppPPPQQ Qx-1)² = (k W used analyses of approximate dynamic programming with function approximation.
& (k)]SAA)' This assumption is commonly
33

---

Published as a conference paper at ICLR 2021
Assumption D.2 (Change in sranks). For every fitting iteration k. we assume that the the difference between sranks ( W
& (k)), is expressed in the function class, and sranks (W& Wa(k -1) by an iteration specific threshold Cg., i.e.,
(k)), equal to the effective rank to feature matrix obtained when R+ Qx-1
sranks( ( (K)) S sranks (Wo(k - 1)) + ck.
We will characterize the properties of cj in special cases by showing how Theorem 4.2 is a special case of our next argument, where we can analyze the trend in ck.
To first see how change in rank indicated by Cj in Assumption D.2 propagates through bootstrap- ping, note that we can use Assumption D.2 and D.I to observe the following relation:
srank& ( (&(k)) (R:) & sranks (oankaWW"[ [k)) ||Q y&ll
(since we can copy over the weights)
A
||Q yell
sranks( ( (k 1)) + Ck
(using Assumption D.2)
QQ - Yk Yk-ill
|Q y&l
sranks (Wo(k- - 2)) + c
+ Cx
AR-1
-yyll
sranks( (W (k)) sranks (W (0)) +
C/
(D.12)
Aj
Derivation of the steps: The first inequality holds via the weight-copying argument: since the weights for the target value R+ 7P*Qx1 can be directly copied to obtain zero TD error feasible point with equal srank, will obtain better solution at the optimum with a smaller srank in Equation 5. We then use Assumption D.2 to relate srank; (W (k)) to the effective rank of the previous Q-function, srank, o - 1)), which gives us a recursive inequality. Finally, the last two steps follow from a repeated application of the recursive inequality in the second step. This proves the result shown in Proposition 4.2.
Now if the decrease in effective rank due accumulating TD errors is larger than the possible cumulative increase in rank Ck2 then we observe rank drop. Also note that need not be positive, C can be negative, in which case both terms contribute to a drop rank. But in the most general case, Ck2 can also be positive for some iterations. This equation indicates how change in in rank in one iteration gets compounded on the next iteration due to bootstrapping.
What can we comment about the general value of cg² In the general case, Cg can be positive, for example when the ad- dition of the reward and dynamics projection increases srank.
Seaquest
Main
400-
Target
Our current set of assumptions are insufficient to guarantee something about Cj in the general case and more assumptions are needed. For instance, as shown in Thcorem 4.2, under Assumption D.1, we obtain that if we are in small neighbor- hood around the fixed point, we will find that c S O.
srankc
300
Pair
200
Pair
100
Empirical verification:
While our analysis does not dictate the value of Ch. we performed an experiment on Seaquest to approximately visualize srank, (W &e (k:) by computing the effective rank for the feature matrix & obtained when pa Qk-1 is expressed in the Q-function class. We do not in- clude the reward function in this experiment, but believe that a "simple" reward function, ie., it takes only three possi- ble values in Atari, and hence it may not contribute too much to sranks /W" & (I:)). As shown in Figure D.2, the value of the target value feature effective rank decreases, indicating that the coefficient C& is expected to be bounded in practice.
Environment Steps
100
Figure D.2: Two pairs of runs depict- ing the trends of target fcature (approx- imately equal to sranks (W3 (A))) (de- noted "Target") and sranks (Wa(k. 1)) (denoted as "Main") on Seaquest with in the data-efficient online RL set- ting. Note that the contribution of dy- namics transformation in the value of cx generally negative for the Pair and is small/positive for Pair
D.3 PROOF FOR THEOREM 4.2: RANK COLLAPSE NEAR A FIXED POINT
Now, we will prove Theorem 4.2 by showing that when the current Q-function iterate Q₂ is close to fixed point but have not converged yet, i.e.,, when Q2 (R (R+yP" +P.P))))]ll S E, then rank-decrease
34

---

Published as a conference paper at ICLR 2021
happens. We will prove this as special case of the discussion in Section D.2, by showing that for any iteration k when the current Q-function iterate Qx is close to a fixed point, the value of og can be made close to O. While the compounding argument (Equation D. may not directly hold here since we cannot consistently comment on whether making an update on the Q-function pushes it out of the e-ball near the fixed point, so we instead prove "one-step" result here.
To prove Theorem 4.2, we evaluate the (infinitesimal) change in the singular values of the features of W a (k; 1) as result of addition in the value of E. In this case, the change (or differential) in the singular value matrix, (ki, T), (W&(k; 7) U(k, (), (VV T)²) is given by:
dS T) = Ia U(K,TT) dW V(K,T)).
(D.13)
using results on computing the derivative of the singular value decomposition (Townsend, 2016).
Proof strategy: Our high-level strategy in this proof is to design form for e such that the value of effective rank for feature matrix obtained when the resulting target value Yı = Qa-1 + & is expressed in the deep linear network function class, let's say with feature matrix, W (k,,)) and the last layer weights, W (k, T) WN WN T),, then the value of srank; (Wo) (k; T)) can be larger than sranks (W (k: - 1, T)) by only bounded limited amount a that depends on č. More formally, we desire a result of the form
sranks ( (k, T)) I sranks ( (Walk- 1,))) + a, where ||e|| Qu-ill, and (s) 1,TW'', (k; a]]. (D.14)
Once we obtain such a parameterization of yı in the linear network function class, using the argu- ment in Section 4.2 about self-training, we can say that just copying over the weights W (',k, T)) is sufficient obtain bounded increase in srank, W& T)) at the cost of incurring zero TD error (since the targets can be exactly fit). As result, the optimal solution found by Equation 5 will attain lower srank, (W, (k:, T)) value if the TD error non-zero. Specifically,
sranks W sranks(W'dd (k, 1|Qx -vll A
srank, (W (Wakk-1,7) 1,7))= +
(D.15)
As a result we need to examine the factors that affect srank, (W T)) (1) an increase in sranks (W (k,T)) T)) due to an addition of a to the rank, and (2) decrease in sranks (k,, T)) due to the implicit behavior of gradient descent.
Proof: In order to obtain the desired result (Fquation D. D.14), we can express a(s, a) as function of the last layer weight matrix of the current Q-function, W (k 1, and the state-action inputs, [s; a]. Formally, size as W W such that |||| < r = ( & (k: T) a. i.e,, Ç has entries with ignorable magnitude compared the actual feature matrix, W (k, T). This can be computed out of the closure assumption (Assumption D.I) from Section D.2.
assume that es, a) W (k f 1, l, a]. where is matrix of the same
Using this form of e(s, a), we note that the targets yı used for the backup be written
Yk = Qu = Ww - 1,7)W (f -1, 11,, W - 1, T,()s(
Ww 1,T) (W s (k- ()
Using the equation for sensitivity of singular values due to a change in matrix entries. we obtain the maximum change in the singular values of the resulting "effective" feature matrix of the targets in the linear function class, denoted as W (k. T), is bounded:
o
(k: T) = Ia U(k, dW T) v(k,T)²
-
| (ks SC. (D.16)
35

---

Published as a conference paper at ICLR 2021
Now, let's use this inequality to find out the maximum change in the function, h1) used to compute sranks( (W +):
Eisr o,(Wo (R.
(i)
(sranks (W W& (N; T)) min {j hv (j) 63).
Σラ ay( (kkTT))
Σjn (W
3 N
プラ=1 do (W))
[dhx(t)
Σj=1 (W(W)
j== (W,)
プド= (W(W))
j- (Wo))
NÇ
Σド (W
(w(Wo)
o
(i+ Σ (W
The above equation implies that the maximal change in the effective rank of the feature matrix generated by the targets, Y& (denoted W (K: T)) and the effective rank of the features of the current Q-function Qu (denoted as W (k(k, T)) given by:
sranks (W'k (k, 7)) sranks (W (K(k, S
where a can be formally written by the cardinality of the set:
N+NN (1- holl) - (1-6) 81 a -= {s hR( E
(D.17)
Note that by choosing E(s, a) and thus Ç to be small enough, we can obtain W (k. T) such that = O. Now, the self-training argument discussed above applies and gradient descent in the next iteration will give solutions that reduce rank.
Assuming r > 1 and sranks (W& & T)) = we know that (r-1) < 1 ò, while (r) > 1 1-6. 6. Thus, sranks Tranks(W', (k; T)) be equal to it is sufficient to show that hx(r) (dha(r) since both (i) and (i) are increasing for 0, ,,,, r. Thus, sranks (W/ (k) rV, whenever
N 5
[f (Bx(r) - -1-
T+N N
E (1 -6) E3=1
r+N
This implies that [W T) 1oc Ejne( v) - - Σソ E3
T+N
Proof summary: We have thus shown that there exists neighborhood around the optimal fixed point of the Bellman equation, parameterized by e(s, a) where bootstrapping behaves like self- training. In this case, it is possible reduce srank while the TD error non-zero. And of course, this would give rise to rank reduction close to the optimal solution.
36


Reviews:
[{"review_id": "u-bPKtplnDX", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "###Summary:\n\nThis paper identifies a type of implicit under-parameterization phenomenon in deep RL methods that use bootstrapping.  It is found that after an initial learning period, the effective rank of the feature matrix keeps decreasing. This implies that the representational power of the network is not fully utilized. The authors call it a type of implicit under-parameterization.  Moreover, the emergence of this under-parameterization strongly correlates with the poor performance.  Some preliminary theoretical analyses are provided to explain this phenomenon. \n\n###Pros:\n\nThe paper is well written, and I can follow the idea very smoothly. The implicit under-parameterization phenomenon seems very intriguing and useful for designing better bootstrapping-based deep RL methods.  The theoretical analyses are very illustrative though still preliminary. \n\n###Cons:\n\n1. The analysis in Section 4.1 seems not correct to me. For kernel regression,  the implicit bias of gradient descent with an infinite number of iterations is to pick up the solutions with the smallest RKHS norm. This implies  $c=0$ in Eq. (1), which would make the subsequent analysis problematic.  However, if early stopping is applied, the GD solutions will be equal to the one given in Eq. (1) with $c>0$. The value of $c$ depends on how the early stopping is applied. Please refer to [1] for more details. \n\n\n###Other comments:\n\n1. The analysis in Section 4.1  is very illustrative due to the use of the kernel model.  But all the experiments are done for neural networks. It would be much helpful if some extra experiments with kernel models can be added, for which we can directly compare the experimental results and the theoretical analysis. \n\n\n\n\n[1] Suggala, Arun, Adarsh Prasad, and Pradeep K. Ravikumar. \"Connecting optimization and regularization paths.\" Advances in Neural Information Processing Systems. 2018.\n\n\n### Post-rebuttal Comments\nI thank the authors for the response and the efforts to update the drafts. I  think this submission made some original contributions. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "kSYucJUgxJX", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discusses a phenomenon wherein the feature vectors of the learned value function in reinforcement learning (RL) lose their diversity as training progresses. The paper analyzes the rank of the final hidden layer in the model parameterizing the value function and shows experimentally that for offline-RL and online-RL setups on Atari and Gym benchmarks, this rank collapse occurs with a drop in the average return. The paper further develops two models for understanding this phenomenon, (i) where the value function is modeled using the neural tangent kernel, and (ii) where the value function is modeled using a deep linear network. The paper argues that bootstrapping results in reduction of the rank of the feature matrix as training progresses for these models. A regularization term that equalizes the singular values of the feature matrix is used to mitigate this rank collapse and experimental results on Atari benchmarks are shown with this regularizer.\n\nThe main claim of this paper is to identify the phenomenon of rank collapse of the feature matrix. I have concerns about the experimental findings of this paper and correctness of its theoretical claims, which are discussed below. I am willing to increase my score if the authors can convincingly argue otherwise. Broadly, I agree this is an interesting direction but current manuscript does not convince the reader that rank collapse is indeed the cause of degradation of performance.\n\nComments.\n\n1. Figure 1 does not completely validate the claims on page 3. In Asterix, increasing the amount of data does not lead to rank collapse but the returns degrade significantly during training, why? In Seaquest, the returns (blue) have degraded essentially to zero even when the rank (blue) is at its maximum. This suggests that there are other factors which are causing the drop in performance instead of/in addition to the rank. The trends in Appendix A1 are similarly inconsistent, as is Figure 2 (Ant-v2). The implication “if low rank, then low returns” is reasonable to expect due to reduced capacity of the value function approximation. But how do the authors deduce from these experiments that “rank collapses in data-efficient RL” (first sentence of Section 3.1).\n2. I have a similar concern about Fig. 3b (Seaquest). The rank for n=4 gradient steps/transition clearly collapses, yet the TD error remains small, and yet the returns are quite bad. If rank collapse entails that the TD error is not minimized well-enough, and that is the cause of the drop in returns, then how can one explain this figure? I suspect the discrepancy is because the TD error is used in Fig. 3b. Can you perhaps compute a pseudo-optimal policy using a good RL method (say Rainbow) for Seaquest and use its value function as the surrogate for Q*?\n3. The narrative will benefit from being more precise. There is an egregiously large number of sentences where the word “implicit” (the paper uses this word 37 times in the first 8 pages) is used in a vague manner (see for instance Definition 1). Further, “implicit under-parametrization” a bad monicker, should the lottery ticket hypothesis be also called implicit under-parametrization?\n4. Why is Theorem 4.1 here not a direct application of Theorem 5 of Mobahi et al., 2020? Further, the big intellectual gap in the argument is that while we are trying to find the fixed point of the Bellman equation in RL, there is no such fixed point in kernel regression. So while the argument that self-distillation during iterative TD^2-minimization may cause a loss of diversity of the feature space, it does not seem to the only reason, after all some examples in Fig 3 do not show rank collapse.\n5. Perhaps the underlying problem is really that minimizing TD^2 is not an appropriate way to find the fixed point of the Bellman iteration when using function approximation. Indeed, if the TD error is small (Fig. 3b, n=4), there is nothing the network can do to improve the returns. TD error is small in this case in spite of the feature matrix having low rank; it indeed depends on the complexity of the value function.\n6. The development in Sec 4.2 using the work of Arora et a., 2019 around eq. (5) argues that when Q_k(s,a) = Q_{k+1}(s,a) for all pairs (s,a) you get rank collapse; this is a very special situation where the value function at each (s,a) is essentially proportional to the rewards at that state-action pair. I tried to follow the proof of the argument for the botostrapped updates in Theorem 4.2 but to my understanding it hides this same issue, e.g., in eq. (D.15) it is assumed that zeta is small enough which is not true. By this argument simply rescaling all the rewards to have small magnitude should result in rank collapse.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QezxQaeMn4U", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main contributions of the paper are the following ones:\n 1. Identifying feature rank collapse problem in RL algorithms using bootstrapping and gradient descent optimization for value function estimation and pinning down this problem to these two factors.\n 2. Theoretical analysis of rank collapse based on Neural Tangent Kernel framework and ideas from analysis of continuous-time differential equations. In particular, the authors showed that rank collapses near optimal point when fitting resembles self-distillation.\n 3. The regularization term heuristic to prevent rank collapse.\n \nOverall, the paper contains a very extensive experimental part, theoretical part and very-well motivated idea. However, the authors tried to put too much information into one paper, therefore sometimes it is difficult to follow. For example, Preposition 4.1 is difficult to follow, since a lot of interesting and important details are hidden in Appendix.\n \nSome questions and issues.\n 1. There is an assumption that S is a normal matrix in theorem 4.1. How restrictive is this assumption?\n 2. Is it possible to extend theoretical analysis from policy evaluation settings to policy training settings. i.e. when Bellman optimality operator is used instead of Bellman operator?\n 3. I would recommend adding a title to Figure 3 (a).\n 4. Figure 3 (d) contains one red trajectory, for which srank does not collapse. Could you please comment what special properties this trajectory has that srank stays almost the same?\n 5.  \"Similar to Arora et al. (2018; 2019), we assume that all except the last-layer weights share singular values (a.k.a. “balancedness”).\" According to Appendix the stronger assumption W_j*W_j^T = W_{j+1}^T*W_{j+1} is required.\n 6. I assume lambda is missing in equation (C.12).\n 7. The question regarding the equation between D.4 and D.5. I understand how the derivative was computed, but I am not sure that I understand what 0 means in dL_0(W_{N:1})/dW_{N:1}.\n 8. I am a bit puzzled by the fact that Rainbow performance increased, while DQN performance decreased in online settings. What is the key underlying component that leads to different results? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0LxAbLPoK4", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post discussion review\n-----\n-----\n\n# Summary\n\nThe authors present evidence that the approximate rank of the features is correlated with the learned policy's performance and that this rank shrinks when using bootstrapping. They provide empirical evidence in several RL settings and domains and present some theoretical arguments which explain this behavior in the context of kernel regression and deep linear networks. Finally, they propose a simple approach for mitigating the rank collapse and show that this improves the performance of the learned policy in some cases.\n\n# Reason for score\n\nThe authors isolate an interesting phenomenon and present some compelling empirical evidence. This is interesting work and I have have no doubt that it is of sufficient quality for publications.\n\n# Pros\n\n* The main contributions of this work might help us better understand the effects of using bootstrapping with function approximation and gradient descent, a critical aspect of many RL methods. Using neural nets to learn (Q-)value functions on novel domains is still to this day a frustrating experience due to how unstable and unpredictable gradient descent + bootstrapping is. As a result, this subject of this work is quite important and likely of great interest to the field.\n* The experiments are well designed and relevant to the main thesis. The empirical results are well presented and easy to understand.\n\n# Cons\n\n* After a very productive and enlightening discussion with the authors, the only noteworthy issue is that this paper contains too many contributions for the format making some of them hard to appreciate. A more focused in depth dive into a subset of the theoretical contributions might have been preferable and possibly provide more insight.\n\n# Conclusion\n\nI strongly support the acceptance of this submission. After discussion with the authors and resulting updates to the paper, I don't see any reason for rejecting this paper. All of the major concerns from my initial review have been addressed.\n\n\nInitial review\n-----\n-----\n# Summary\n\nThe authors present evidence that the approximate rank of the features is correlated with the learned policy's performance and that this rank shrinks when using bootstrapping. They provide empirical evidence in several RL settings and domains and present some theoretical arguments which explain this behavior in the context of kernel regression and deep linear networks. Finally, they propose a simple approach for mitigating the rank collapse and show that this improves the performance of the learned policy in some cases.\n\n# Reason for score\n\nAlthough the authors isolate an interesting phenomenon and present some compelling empirical evidence, I have a few concerns about the theoretical contributions which, hopefully, the authors can address or clarify any misunderstanding. This is interesting work and I am more than willing to adjust my review if the authors can assuage my concerns.\n\n# Pros\n\n* The main contributions of this work might help us better understand the effects of using bootstrapping with function approximation and gradient descent, a critical aspect of many RL methods. Using neural nets to learn (Q-)value functions on novel domains is still to this day a frustrating experience due to how unstable and unpredictable gradient descent + bootstrapping is. As a result, this subject of this work is quite important and likely of great interest to the field.\n* The experiments are well designed and relevant to the main thesis. The empirical results are well presented and easy to understand.\n\n# Cons\n\n* This did not feel like an 8 page paper. This paper took a long time to review. With 18 pages of appendix, 9 of which are clarifications and proofs, what is left of the theoretical contributions in the main body of the paper doesn't provide much insight into the role/importance of the assumptions or into what makes each claim true.\n* The proof for theorem 4.2 appears to make use of the assumption that $\\varepsilon(s, a) = W_N \\cdot \\zeta [s; a]$ and $y_k = Q_{k-1} + \\varepsilon$. This is not conveyed in the main body of the paper but seems to be a fairly strong assumption on the form of the bootstrapped targets.\n* Similarly, I would argue that the premise that the bootstrapped targets will eventually be close to the previous, i.e., $y_k \\approx Q_{k-1}$, is flawed. There is no guarantee that applying the Bellman operator will return a function that is inside your function class, even in the linear case. Furthermore, we know this phenomenon to be significant and motivated work on the projected Bellman error, a concept heavily used by the various variants of gradient temporal difference learning.\n* In theorem 4.1, the assumption that $S$ is a normal matrix seems impractical and likely makes this result only applicable to very rare cases.\n* In proposition 4.1. it isn't immediately apparent where in the proof the assumption that the loss $L$ is the TD loss is leveraged. If it isn't used, this would suggest that this is a general property of deep linear networks and wouldn't support the authors observations that the rank issues are specific to bootstrapping.\n\n# Questions for the authors\n\n1. Was anything done to \"normalize\" the results in figure 2 to account for the differing number of total updates as a result of different n? Can these observations be explained by the fact that more updates results in the parameters traveling further from their initial values? What happens when plotting the srank vs. # of updates in the setting? (These likely don't need 3 distinct answers)\n2. Could the authors elaborate on why the normal matrix assumption might be reasonable, or, otherwise, explain why this doesn't make it a vacuous result?\n3. What is the purpose of the \"explaining implicit under-parameterization across fitting iterations\" section? I think I am missing the insight this is trying to provide. Why would the parameters change at all if I reuse the results of the previous minimization as targets? What does the Bellman error refer to here and what does it mean to attain zero (or any value) TD error when the targets are just the Q-values?\n4. The balanced assumption used with the deep linear networks seems critical for the proof. Is my assessment correct or could these results possibly hold without it? How does this assumption limit the applicability of the insight gained here to more practical neural networks?\n\n# Misc comments and typos\n* page 2, Yang et al. don't seem to use the term \"effective rank\", but do use the term \"approximate rank\".\n* page 4, \"we first remove the confounding **with** issues [...]\"\n* page 30, proof, it would help to explicit state the dimensions of $\\zeta$. Is the $\\top$ on $\\zeta^\\top$ a typo? Otherwise, why is it not used further down?  (no need to answer either way, just reporting on something that tripped me up)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Knowledgeable R3 found the paper very good (8). He/she found the authors' responses very informative and that edits made the paper much stronger. R2 expressed reservations about rank collapse being the cause of degradation of performance, but also indicated his/her willingness to increase the score if the authors can convincingly respond to his/her concerns. This concerned was shared by other reviewers, and there was an extensive discussion during the discussion period. R3 and R1 found the authors' responses very convincing. Fairly confident R1 found the paper good, appreciated the discussion, and recommends the paper to be accepted. R4 found the paper marginally above the acceptance threshold, however expressing a lower confidence in his/her assessment. In summary, the article contains extensive experiments, theory, and a well motivated idea, elucidating an intriguing phenomenon and useful for designing better bootstrapping-based deep RL methods. Although the reviewers expressed some reservations in their initial reviews, there was a lively discussion with quite positive final feedback. Weighing the ratings by confidence and participation in the discussion, I am recommending the paper for acceptance. I would like to encourage the authors to make efforts in making the presentation as clear as possible, having in mind the discussion and comments from the reviewers. 
Decision: Accept (Poster)