Assessing Generalization in TD methods for Deep Reinforcement Learning
Authors: Emmanuel Bengio
Doina Precup
Joelle Pineau
Venue:  (2020)
Keywords: reinforcement learning
deep learning
generalization

Abstract: Current Deep Reinforcement Learning (DRL) methods  can exhibit both data inefficiency and brittleness, which seem to indicate that they generalize poorly. In this work, we experimentally analyze this issue through the lens of memorization, and show that it can be observed directly during training. More precisely, we find that Deep Neural Networks (DNNs) trained with supervised tasks on trajectories capture temporal structure well, but DNNs trained with TD(0) methods struggle to do so, while using TD(lambda) targets leads to better generalization.

Under review as a conference paper at ICLR 2020
ASSESSING GENERALIZATION IN TD METHODS FOR DEEP REINFORCEMENT LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Current Deep Reinforcement Learning (DRL) methods can exhibit both data in- efficiency and brittleness, which seem to indicate that they generalize poorly. In this work, we experimentally analyze this issue through the lens of memorization, and show that it can be observed directly during training. More precisely, we find that Deep Neural Networks (DNNs) trained with supervised tasks on trajectories capture temporal structure well, but DNNs trained with TD(0) methods struggle to do so, while using TD(A) targets leads to better generalization.
INTRODUCTION
Deep neural networks (DNNs) trained on supervised learning tasks using i.i.d. data have shown the capacity to learn quickly even from a small amount of samples (Hardt et al.) 2016). Intuitively, this is due each sample also providing information about the estimate corresponding to other samples; research suggests that DNNs first extract structures that are informative of the modes of the data (even if later they can also memorize see /Zhang et al. (2016); AArit al. (2017)) and that they can transfer well (Yosinski et al.) 2014 Li et al.) 2015). even from relatively few samples. In contrast, in Deep Reinforcement Learning (DRL), the number of samples required for an agent to learn successfully is often very high: many modern algorithms struggle to perform well until they acquire tens of millions of samples (Mirowski et al., 2016 Vinyals al. 2017 Hessel et al. 2018). and some even diverge to bad solutions (Anschel et al. (017). While there are many facets to sample complexity and brittleness, we posit that a contributing factor is a lack of what we call gradient update generalization, i.e., whether performing updates at one state provides useful information about the value/policy at other states.
(a) generalization to unseen states-will an agent trained on single MDP pick the optimal action for a state it has never seen before? (b) generalization to unseen tasks-will an agent trained on distribution of MDPs know how to act in an MDP it has never seen before? Both of these facets are actively studied. For example. Farebrother et al. (2018) expose some generalization failures on the Atari domain (Bellemare et al. 2013) and study the impact of regularization, Zhang et al. (2018) study the generalization capabilities of DRL agents on randomized mazes, Packer et al. (2018) study the extrapolation capabilities of DRL agents trained
Generalization in RL is of two types:
distribution of environment parameters (e.g. pole mass in CartPole) outside of the training distribution, [Cobb al. (2018) find that even on procedurally generated environments, DRL agents can easily overfit on their training set unless regularized, Oh et al. (2017) study the embedding regularizations necessary for agents to generalize to new instruction sequences on navigation tasks.
In this study, we are not interested in measuring state generalization (i.e. predictions for unseen states), nor task generalization (i.e. in terms of the quality of the behaviour), but rather generalization within the process of stochastic gradient learning. In other words, since any kind of generalization must arise through the accumulation of parameter updates, it seems useful to measure whether these parameter updates themselves general. To this end, propose the measure of gradient update generalization, best understood as a side-effect neural networks sharing parameters over their entire input space. That is, updating parameters after seeing state will change the prediction for virtually all other states; we are interested in measuring that change.
TD methods
broad class of RL algorithms that form target for an update by utilizing the current estimate of the value function. They include TD(0) and TD(A) methods for estimating the value of fixed policy, well as Sarsa and Q-learning algorithms for control. TD methods have

---

Under review as a conference paper at ICLR 2020
achieved success in some challenging tasks (Tesaur 1995
Mnih et al. 2013 Hessel al. 201 8)
but they are also known to have problems when coupled with function approximation (Sutton 1995
Baird 1995 Titsikkis & Van Roy, [997; Chung et al. 20188) Previous studies explicitly addressed
problems such as leakage propagation in
TD (Penedones et al. 2018). while others aimed to provide
sampling improvements (Schaul et al.
2015 Andrychowicz
al. 2017]] Fu al., (209)), explicit 2018 101 or auxiliary tasks which push the agent to learn more
temporal regularization (Thodoroff et al.
about the temporal structure in the data Jaderberg et al. 2016).
To our knowledge, no study to date has focused on the dynamics of the generalization process itself, within TD-based DRL methods" such as deep Q-Learning (Riedmiller 2005 Mnih et al. 2013). Sarsa (Rummery & Niranjan 1994), and TD(X) (Sutton 1988 Schulman et al. 2015). For this study. we introduce the aforementioned measure of gradient update generalization, which enables us to differentiate the learning behaviours of different methods. Overall, we find that:
when doing a TD(0) update for a single state, parameters change in such a way that the value prediction of other states is generally not affected, surprisingly even for states that are close either temporally or in an annotated "ground truth" state space;
2. DNNs trained with TD(O), in contrast with DNNs trained on memorization task or using supervised objective, do not entirely memorize their state space, yet also do not generalize in the way would expect;
3. both the choice of optimizer and the nature of the objective impact the generalization be- haviours of models; in particular, when increasing the parameter in TD(A), DNNs appear to capture more temporal structure.
2 TECHNICAL BACKGROUND
Markov Decision Process (MDP) (Bellman 1957: Sutton & Barto 2018 M A, consists of state space S, an action space A. reward function R S + IR and a transition probability distribution Pss'|s, a). RL agents aim to optimize the expectation of the long-term return:
G(S)) = R(Ss).
where 7 E [0, 1) is called the discount factor. Policies (a|s) map states to action distributions. Value functions V and Q" map states/states-action pairs expected returns, and can be expressed recursively:
(*(()) = E. [.(.) = [R(S)) (S, E., (R(S.) Σ n )(( ((S)+,,))(
~ T(S)), ~ P(S.,
(2)
P(S., A.)]
While 4 could also be learned via regression to observed values of G, these recursive equations give rise to the Temporal Difference (TD) update rules for policy evaluation, relying on current estimates of V to bootstrap, e.g.:
V(S)) - V(S.) aV - (R(S.) (V(++)))).
where [0, 1) is the step-size. Bootstrapping leads also to algorithms such Q-Learning (Watkins Dayan 1992) and fitted-Q (Ernst et al. 2005 Riedmiller (005):
LQl (Sr, Ar, R₁, S141) [Qe(S,, - (R, + max (o(S)
(5)
Sarsa Rummeer & Niranjan 1994):
Saaraa (St, Ae, Re, S141, A41)) = (S, (Ro+ A++1))2 with A, ~ ((S)) (6)
In contrast, policy-gradient gradient algorithms such as PPO (Schulman et al. 2017) A3C Mnih et al. 2016 and SAC (Haamnjj (0188) are capable of learning good policies without necessarily having learned good value function, and although interesting results have emerged to understand learning behaviours policy-gradien methods (Tlyas al. 2018), these methods build upon TD and analyzing them would add undesired confounders.
2

---

Under review as a conference paper at ICLR 2020
and TD(A), which trades off between the unbiased target G(S)) and the biased TD(0) target (biased due to relying on the estimated V(S++1). using a weighted averaging of future targets called a A-retum (Sutton 1988. Munos et al. 2016):
80
n-1
G*(S)) = (1 X)
Σ x
(V(())))) + Σ n R R(S(+))
j=0
(TD(A)(S)) = (Vo(S.) G (S)))
(8)
(note that the return depends implicitly on the trajectory followed from S.). When À = 0, the loss is
simply (Vo(S,) (R2 + (Vo(S++))) leading to the algorithm called TD(0) (Sutton 1988).
3 UPDATE GENERALIZATION IN DEEP RL
We will now define the measure we propose in order to quantify the speed at which generalization to unseen states occurs, and to characterize the structure under which this generalization occurs. We define gradient update generalization as the expected improvement in the loss function L: ④ x X - IR after updating parameters 0 E O, on sample Xy E X, using update function Uc : O + θ (e.g. SGD or semi-gradient methods like TD(0)):
Ye(Xu; U) = Ex [C(:) 8) - UU(,
If generalization from the samples in Xy to X' is good, this measure of gain should be large, and intuitively fewer other samples should be needed to achieve desired level of performance. On the other hand, if on average the loss only decreases for the samples X used in training, then more data in X' X will have be visited before the model can learn. Hence, this measure is related to both sample complexity and the speed of learning (see Fig. 15 for empirical confirmation of this phenomenon).
As computing the exact expectation is usually intractable, we empirically measure gains on different subsets X X. In particular, when X is chosen to be a slice around Xy in the replay buffer, we write ynear, We also subscript Y with the corresponding loss' subscript, e.g. for (5). CoL. we write YQl. In this study, we are interested in TD-based methods that rely heavily on bootstrapping. Q-Learning, Sarsa, and TD(A), and measure Y using their respective losses,
5 (6) and
Structure in DNNs
common intuition in deep learning (Zhang et al. 2016 Arpit et al. 201 7,
Zhang et a 2018) is that DNNs first learn about the structure of their data, meaning the underlying (usually linear) factors of variation of the data being mapped into the hidden units' space via parameter sharing. These factors of variation are usually conceptualized as a low-dimensional space where each dimension explains part of the data (Bengio et al. 2013). It is commonly assumed that a model which generalizes well will naturally capture these factors in the configuration of its parameters, in which case the gradient of the prediction w.r.t. all examples sharing the same latent factors of variation will be very close; updating with only one sample will change the prediction for all the related examples. Hence, a DNN which captures structure correctly should show high gradient update generalization.
Temporal structure in RL Data used in RL algorithms usually exhibits two additional types of structure: coherence of the inputs in a trajectory over time (e.g. pixel values in adjacent frames are often similar), and smoothness of the value function in time (in the seward case with y close to 1. (S,)) x vV((S++)) which is smooth in time, aside from rare discontinuities upon seeing rewards). Since RL data consists of trajectories which often have strong temporal structure of both types, we hypothesize that the gain ynear of temporally correlated examples should increase closer in time to the sample used in the update.
Parameter sharing Another indirect measure of update generalization related to parameter sharing the difference since last visit, which we denote as A. At each update iteration k, we compute the difference between the value Vo, (s) or Qu, (8, a) predicted from the current parameters, 02, and Ve V (8) or Qetaaees (8, a) i.e. the prediction made the last time state was used for a gradient
update To illustrate, if Vo was lookup table, A would always be 0, while for DNN, when states
In practice. we simply cache the value prediction for all states in replay buffer (as states in a continuous state space are unlikely to be encountered many times), and update the cache after minibatch update (for those states only).
3

---

Under review as a conference paper at ICLR 2020
aliased together, A should accurately reflect the effect of parameter sharing after performing sequences of updates (in contrast, (9) uses only a single update).
3.1 EXPERIMENTAL SETUP
We will now perform series of experiments aimed at assessing the amount of generalization of various bootstrapping algorithms, compared to supervised learning, in combination with DNNs.
First, we test whether DNNs have large gradient update generalization gain when trained under ideal conditions (data generated by expert policies and labelled with correct values, which can be used in supervised learning). Then, we test the policy evaluation case (using the same input data, but bootstrapped targets instead of supervised learning). We then test the usual control case, when no expert trajectories available. Finally, we measure the effect of TD(A) generalization gain in policy evaluation, as well as test Q-Learnin'ss s robustness to withheld data.
We perform our experiments on the Atari environment (Bellemare et al. 2013), with the stochastic setup recommended by Machado et al. (018)) We use a standard DQN architecture (Mnih et al. (013). In order to generate expert trajectories, it al. 2018); we denote D dataset of transitions obtained with this agent, and 6 the parameters after training that agent. For control experiments, we use Mnih et (2013)'s Q-Learning setup. When measuring Ynear we choose the nearest 60 examples in time to a given state-action pair (30
rollouts from policy trained with Rainbow (Hessel
previous and 30 following on the same trajectory).
3.2 ASSESSING TEMPORAL STRUCTURE WITH SUPERVISED LEARNING
In this experiment, we will assess if temporal structure, as described above, exists and can be captured by our architecture. To do so, we train DNNs starting from random parameters but with "ideal" targets coming from the expert parameters 0* and expert trajectories D*; this removes all non-stationarity from the learning. We train Qo with different objectives:
MC:
Lmc(s,a;0) = (Qe(s, a) G(D))(s)2
(10)
Reg:
(reg = (Qo(s,a) (s)
(11)
TD*:
CTD (s, (Qo(s,a) -(r (r+ max Q0 (5', (())
(12)
where by ((P) (s) denote the Monte-Carlo return within the dataset D in Note that since LTD- "bootstraps" to 0" this should be roughly equivalent to Lregs the latter being plain supervised learning (or some sort of distillation, à-la Hinton al. (2012)).
Results are visualized in Fig. [ for experiments ran on MsPacman, Asterix, and Seaquest for 10 runs each. Results are averaged over these three environments (they have similar magnitudes and variance). Learning rates are kept constant, they affect the magnitude but not the shape of these curves.
We draw two conclusions from these results. First, as seen in Fig. Ta & Tbl all curves tend to have large gains around = 0 (the sample used in the update), especially from indices -10 to 10, showing that there is some amount of temporal structure captured by both objectives. Since Q is good approximation, we expect that Q (s, a) Ri (r + max,' Qa- (s', a.)) aa)). so Lreg and LTD- have similar targets and we expect them to have similar behaviours. Indeed, in Fig. [their curves mostly overlap. Second, there is a clear asymmetry between training on expectations (i.e. the learned Q(s, a) or max, Q(s', a')) and high-variance Monte-Carlo returns (red and blue curves in Fig. Lap. We hypothesize that since the returns G are computed from the same state sequence that is used to measure the gain, G truly informative of the expected value of future states. Strangely, this does not seem to be the case for past states, which is surprising On the other hand, while G appears more informative of future expected returns, it is not particularly more informative of future sampled returns than past returns, which explains the symmetric nature of the MC gain shown in Fig. Tb
A possible explanation is that, due to the exponential discounting nature of returns (V(S)) ~ (S++*) aside discontinuities when R 0), the correlation between the current and future returns simply has larger magnitude than with past returns. This might push DNNs to prefer "assign capacity" w.r.t. future returns.
4

---

Under review as a conference paper at ICLR 2020
0.10
MC+adam
0.30
MC+adam
Reg4adam
Rog-ndam
TD' +adam
0.25
TD' tadam
TD gain (1yp)
0.06
MC+mmpprog
MC gain (Kac)
MC+mmspru
0.20
Reg+rmsprop
Reg-runsprop
0.04
TD' +mmspro
0.15
TD' +mmspopp
0.02
0.10
0.00
0.05
30
-20
10
30
30
-20
10
30
Distance minibatch sample in roplay butter
Distance to minibatch sample in replay buffer
(a) Near TD gain, YT
(b) Near Monte-Carlo gain, YMC
Figure 1: Supervised learning on Atari: Gain as a function of distance in the replay buffer from the update sample. We use dotted lines for the point at 0 distance, to emphasize that the corresponding state was used for the update. (a-b) The curve around indicates the temporal structure captured by the TD and regression objectives.
Another striking distinction in these curves appears between the Adam (Kingma & Ba 2015) and RMSProp (Hinton et al. 2012) optimizers [ When moving far away from s, RMSProp tends to induce negative gain, while Adam tends to induce a near-zero gain. This is seen in Fig. la where RMSProp's TD gain is below for states more than 10 steps away from the sample used in update. Note that similar differences appear in virtually all following experiments, which we discuss later.
3.3 POLICY EVALUATION AND TD GAIN
We have seen that DNNs can capture some temporal structure and have good gradient update generalization when given good quality inputs and targets. We will now remove the expert targets generated using the pretrained 0", but we will keep the expert inputs. This corresponds to policy evaluation on expert trajectories, and we would expect to see slightly worse generalization than in the previous case.
We run policy evaluation with 2 objectives, Lor and Lsarsa as defined in (5). and (6 respectively, using a frozen target to bootstrap (Mnih et al. 2013), updated after every 10k minibatches. Experi- ments are run 24 Atari environments (see A.I.1 for 10 runs each. Gain results are visualized in Fig. 2
averaged over the 24 environments.
The main observation from Fig. 2a how narrow the peak around O is, suggesting that whenever a state's s value is updated, the prediction for other states does not change much in expectation, as if the representation were almost tabular, with estimates for encountered states being memorized. The conclusion we draw is that, with fixed data distribution, DNNs bootstrapping network will not proprely capture temporal structure, but will still be able to learn (at least in the sense of correctly approximating the value function).
evolving target
Another worrying observation that RMSProp consistently has negative expected gain for nearby samples (but large, larger than Adam, positive gain on X the minibatch sample), suggesting that parameters trained with this optimizer memorize input-output pairs rather than assign capacity to generalize.
3.4 COMPARING MEMORIZATION BEHAVIOUR IN POLICY EVALUATION
The previous results established that some amount of memorization is done during TD-based policy evaluation. Quantifying memorization still an open problem, but in this experiment offer an
It has been reported that Adam is less sensitive than RMSProp to hyperparameters in value- meth- ads (Hessel al. 2018), although evidence suggests it doesn't help policy gradients (Henderson et al. 2018
5

---

Under review as a conference paper at ICLR 2020
100-
All Games
-1001
All Games
1.00
QL+adam
Sanatadam
Q1+rmsprpp
gain (Fra)
TD gain (fro)
marsa
0.50
0.25
QL+adam
Sarsatadam
0.00
QL+mmsprop
Sarsawrssprop
30
10
20
30
30
20
10
30
Distance to minibatch sample in replay butfer
Distance to minibatch sample in replay butfer
(a) Near TD gain, YTD
(b) Near TD gain, YTD" zoom of (a) excluding Xv, i.c. distance show the lack of temporal structure
Figure 2: Policy evaluation on Atari: Gain as function of distance in the replay buffer of the update sample. (a) We use dotted lines for the point distance emphasize that the corresponding state was used for the update. (a-b) Compared to regression in Fig. [aa] almost no temporal structure is captured, which can seen by how narrow the curve around distance
interesting qualitative inspection confirm that TD-based methods may lie somewhere between pure memorization (acting like a lookup table) and strong generalization (capturing all latent factors).
In Zhang et al. (2016), the authors compare images classifiers trained with true labels classifiers trained with random labels (in which case the model has to simply memorize the labels), finding that, surprisingly, both can reach 0 training error. While this suggests that DNNs may also memorize when given the true labels, further studies showed many behavioural differences between the two setups, notably that DNNs first captured structure, and only afterwards fit random noise (Arpit et al.) 2017).
Taking inspiration from Zhang et al. (2016), we assign random class in [A]] to every state in D', change our Q function be a usual classifier with N outputs, and introduce new objective, Lrand- which is simply the cross-entropy between the random class and the prediction. Experiments are run on MsPacman, Breakout, and Seaquest. We use datasets of sizes 10k, 100k, and 500k, and use N E {2, 10, 50]. Interestingly, the architecture of Mnih et al. (2013) that is reused here struggles to reach 0 errof (for example, a model trained with 10k samples with N reaches 5.7% error, while model trained with 500k and N 50 totally fails at 85% error, see Table ??).
Fig. 3 shows the evolution during training of the distribution of A A) = Q(S, A; ouurrent) Q A; (tast())), where (last(s) represents the value of the parameters when S was last used in minibatch update, and feurrent represents the value of the parameters right before using S for the most recent update. If the parameters were those of a look-up table, A would always be 0. For losses other than Lrand (Q-Learning, Sarsa, and MC) we reuse the results of the previous section (with dataset size of 500k).
The difference between Fig. 3aland and Fig. 33-d is compelling, and somewhat reassuring. In Fig. 3a the ligeliilihood for A 0 is above -2 (white) showing that is very unlikely for the prediction at state to have changed by more than +0.01 when it is updated. In contrast, the distribution of A is more spread out in Fig. 3p- Combined with the fact that the memorization experiment does not reach 0 error, this allows us to confidently claim that DQN is not fully memorizing its state space. Even though the gain curve Fig. 2 is very close to O, except at the update sample (i.e. temporal structure is poorly captured), some structure is captured by DNNs that allow them to learn about state without having to use it explicitly in an update.
'This could be due to the particularly shallow architecture of Mnih et al. (2013). architectures with less parameters but more layers commonly assumed to have more effective capacity. It has indeed been shown that deeper models can distinguish hetween exponentially more linear regions (Montular et al. 2014).

---

Under review as a conference paper at ICLR 2020
0.8
0.8-
0.8
Difterasee (Ansnne lat
0.6
Defterrace (Atntnce last
0.65
0.6
Difference (A) (0per))
0.0
0.0
0.0
40.
-0.2
41.2
40.4
4.88
408-
4888
1,0
10
-10
10
1.0
-10
200
400
0
200
400
200
400
Denniios (thousands)
Dentiios (thousands)
Dentions (thousands)
(a) Lrand
(b) Lou
(c) Ssarsa
1.0
à 0.5
2. 0.95
0.8
1,0
0.8
Diffemece stace last 235i
0.6
0.4
0.2
(1gra Millioy
Diffemne Pirpplat
0.2
(1'm) lid
0.0
0.0
Dilferecce
-0.2-
-0.4
0.6
-0.6
0.8
200
400
2001
Itenioos (thousands)
Iernitons (thousands)
Iteniions (thousands)
(d) LMC
(e) CTDOY,
(l) LT CTD) 0.95
Figure 3: Policy evaluation Atari: evolution of the distribution of A, the difference since last visit, during training. (a) the DNN is forced to memorize, as such the density of A is concentrated around 0 (thin red/white band). In (b-c), Q-Learning and Sarsa, the density is much less peaked at (larger yellow/green bands) as the DNN learns about states without visiting them. In (d) the DNN learns quickly presumably without memorizing (the distribution of A is more spread and not as concentrated around 0, seen by the larger yellow/green band), as it is trained on Monte-Carlo returns, and quickly converges as can be seen by the high density of positive As early. In (e.f) we see the effect of using À returns (see appendix A.6 for all values of A).
3.5 TD GAIN IN CONTROT.
Having removed 0* in section 3.3 we now additionally remove D* and simply perform Q-Learning from scratch on MsPacman, Asterix, and Seaquest for 10M steps.
Results shown in Fig. Interestingly, while Q-Learning does not have strong gain the regressions from Fig. it has larger gain than policy evaluation. This may have several causes, and we investigate two:
Initially, because of the random exploratory policy, the DNN sees little data, and may be able to capture minimal of factors of variation; then, upon seeing new states, the extracted features are forced to be mapped onto those factors of variation, improving them, leading to natural curriculum. By looking the singular values of the last hidden layer's matrix after 100k steps, we do find that there is consistently larger spread in the policy evaluation case than the control case (see appendix AA.3), showing that in the control case fewer factors are initially captured. This effect diminishes as training progresses.
Having run for 10M steps, control models could have been trained on more data and thus be forced to generalize better; this turns not to be the case, measuring the same quantities for only the first 500k steps yields very similar magnitudes (see appendix A.4).
Interestingly, these results consistent with those of Agarwal et al. (2019). who study off off-policy learning. Among many other results, Agarwal et al. (2019) find that model another DQN agent's lifetime set of trajectories yields much worse performance average.
a DQN
7

---

Under review as a conference paper at ICLR 2020
All Games
All Games
adam megd
adam
0.04
0.001
msgd
russprop
rmsprop
grin (1ro)
0.03
(Frn)
sgd
0.000
sgd
0.02
-0.001
0.01
0.002
0.00
20
30
30
20
10
20
30
Distance minibutch sample replay butfer
Distance to minibatch sample replay butter
(a) Near TD gain, Y
(b) Near TD gain, YTD", zoom excluding X i.c. dis- tance 0, to show the magnitude of generalization
Figure 4: Q-Learning on Atari: Gain as function of distance in the replay buffer of the update sample. (a-b) Compared to policy evaluation, gain appears be better, but not as large as for regression. (b) For Adam and RMSProp, we include the corresponding curves for policy evaluation in lighter shades.
While the authors suggest the strongly off- off-polliy aspect of this experiment as the cause, our results still show differences between done "on-policy" in our setup, suggesting there are more factors at play than only off-policyness.
and
which are both
Note that also additionally experiments with SGD and Momentum- Homentum-SGD optimizers to highlight the difference between Adam, that has momentum component, and RMSprop, which only scales per-parameter learning rates. Predictably, Momentum-SGD's behaviour is similar to Adam, and SGD's to RMSprop.
3.6 TD(A) AND RELIANCE BOOTSTRAPPING
TD(A) trades off between the immediate biased estimates of the future values and the true return through its À parameter. To observe the effect of this parameter we perform policy evaluation on D with the D() objective MsPacman.
Results are shown in Fig. 5 where we can observe that (1) increasing increases near gain without overly increasing sample-sample gain (2) as for Lace there is an asymmetry: updating informs us more about the future than about the past, on average. Results for the distribution A are shown in Fig. 3 ef) (and appendix A. where see that the closer À is to the more the TD(A) objective creates updates that affect all states.
These results seem indicate that TD(A) better captures factors of variation. One cause could be that the more one relies on a sequence of DNN predictions (i.e. the sequence of n-step returns of the X-return depend the successive (S++:)) build target, the states and targets (due to DNN smoothness), and the more temporal coherence there is (and thus more opportunities for DNNs capture the temporal dimension's 's correlations). This hard to verify empirically, but we can proxy the correlation measure via the similarity between gradients. We do indeed find that the closer À is 1, the higher the average cosine similarity between gradients (see appendix A.5). This suggests that it may be advantageous to use X-returns in environments where generalization important.
correlation there is between
3.7 TESTING GENERALIZATION WITH AN INTRA-TASK TEST SET
Another way to assess whether agents fail to properly generalize in the sense of statistical inference making predictions about states without visiting them create test set measure generalization enror. We do so on the MsPacman Atari environment, as it contains many opportunities for gener- alization in translational invariances (locally, the optimal action only depends on the surrounding
8

---

Under review as a conference paper at ICLR 2020
x10
MsPacman
MsPacman
==
140
1.50
0.25
0.9
120
0.95
0.75
0.99
100
Avangeepihsuicc
0.75
TD
0.50
0.25
40
0.25
20
0.5
30
30
10
Distance minibatch sample in replay butfer
Iterations (millions)
Figure TD gain for policy evaluation with (D(A) & Adam. Note the larger gain goes to 1, as well as the asymmetry around
Figure 6: Episodic rewards over Q-Learning on Atari. We train agent while witholding states from the training set with probability p.
configuration of the agent, reward pellets, ghosts). We train our agent with the usual DQN setup (Mnih et al. 2013) but prevent the insertion of state into the replay buffer with some probability More specifically, we use the RAM (ground truth) state information to exclude observations from training. We run 5 seeds for each p {0, 0.1, 0.25, 0.5).
Results are shown in Fig. where we see that witholding only 10% states already slightly affects agents. At 50%, performance is significantly reduced. While this is somewhat expected and consistent with the literature (Farebrother et al.] 2018), it again attests that TD-based methods can struggle with generalization, as observed also by Packer al. (2018), who study interpolation and extrapolation failures in deep RL agents.
3.8 ADDITIONAL. OBSERVATIONS
On other structures Our figures mostly show gradient update generalization gain as a function of "time" (temporal distance within trajectory), but there might be structure elsewhere. We measured gain as a function
different metrics: ground truth state distance by reusing the Annotated Atari RAM of Anand et al. (2019), value distance (as DNNs may alias states with the same value), and feature distance. Unfortunately, we were unable to find correlations (see appendix A.2
On convergence Figures I and show values averaged over the course of training. We find that except in the first few iterations, these curves remain constant throughout training (see figures in A.4) and show no sign of convergence. This is also consistent with previous studies, DQN known to not converge on Atari (Anschel et al. (017)).
On variance While V Var(Yc) tends be large, find that the confidence interval of the mean is always small, and would barely appear on most of our plots. Additionally, although generalization gain is typically fraction of the magnitude of the value function,
consistently non-zero.
On optimizers We find that the systematic differences we see between Adam and RMSProp also occur in behaviour, where control agents trained with RMSProp tend get slightly more reward. An interpretation of our results is that RMSProp memorizes faster than Adam: it has much larger on-sample gain, it tends to make the singular values of the weight matrices larger, and it has negative near-sample gain, suggesting that capacity is spent memorizing memorization can be an efficient strategy (although it sensitive to noise, see Machado et al. (2018)). Hence, the better performance of RMSProp Atari is consistent with our claims. This property may not be as desireable in more complex environments requiring generalization.
average. In Atari tasks,
4 DISCUSSION
RL is generally considered harder problem than supervised learning. Hence, the fact that TD-style methods require samples than supervised learning when used with deep nets necessarily

---

Under review as a conference paper at ICLR 2020
surprising. However, with the same data and the same final targets (the "true" value function). it is not clear why TD updates lead to parameters that generalize worse than supervised learning. This could be problem, most RL methods rely the TD mechanism in way another. In particular, results show that both Q-Learning and Sarsa generalize poorly, leading to DNNs that memorize the training data (not unlike table lookup). Our results also suggest that TD(A), although in recent DRL, improves generalization. Finally, we find differences between Adam and RMSProp that we initially did not anticipate. Very little work has been done understand and improve the coupling between optimizers and TD, and our results indicate that this would be an important future work direction.
widely used
Our work suggests that the RL community should pay special attention to the current research on generalization DNNs, because approaching the TD bootstrapping mechanism as supervised learning problem does not seem to leverage the full generalization potential of DNNs.
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. Striving for simplicity in off-policy deep reinforcement learning. arXiv preprint /tt1::/907.044550 2019.
Ankesh Anand, Evan Racah, Sherjil Ozair, Yoshua Bengio, Marc-Alexandre Côté, and R Devon Hjelm. Unsupervised state representation learning in atari. arXiv preprint arXiv:9906.08226. 2019.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, pp. 5048-5058, 2017.
Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pp. 176-185. JMLR. org, 2017.
Devansh Arpit, Stanistaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. closer look at memorization in deep networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 233-242, JMLR. org, 2017.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Mare G Bellemare, Yavar Naddaf. Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Richard Bellman. A markovian decision process. Journal of mathematics and mechanics, pp. 679-684, 1957.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence, 1788),1798 2013.
Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White. Two-timescale networks for nonlinear value function approximation. In 7th International Conference Learning Representations, 2018.
Karl Cobbe, Oleg Klimov, Chris Hesse, Tachoon Kim, and John Schulman. Quantifying generalization in reinforcement learning. arXiv preprint arXiv:1812.02344 2018.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6(Apr):503-556, 2005.
Jesse Farebrother, Marlos C Machado, and Michael Bowling. Generalization and regularization in dqn. arXiv preprint arXiv: /80.000//. 2018.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q-lcarning algorithms. arXiv preprint arXiv: 1902. 10250, 2019.
10

---

Under review as a conference paper at ICLR 2020
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor critrcc Off-policy maxi- mum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXivv1801.0122 2018.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1236 2016.
Peter Henderson, Joshua Romoff, and Joelle Pineau. Where did my optimum go?: An empirical anal- ysis of gradient descent optimization in policy gradient methods. arXiv preprint arXiv: /at::/881..0 180000255. 2018.
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.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. CSC331,2012,
Andrew Ilyas, Logan Engstrom, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Are deep policy gradient algorithms truly policy gradient algorithms? arXiv preprint arXiv:1811.022. 2018.
Max Jaderberg. Volodymyr Mnih, Wojeiech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611. 161.059977 2016.
Diederik Kingma and Jimmy Ba. Adam: a method for stochastic optimization (2014). arXiv preprint arXiv: 6980, 15, 2015.
Yixuan Li, Jason Yosinski, Jeff Clune, Hod Lipson, and John E Hopcroft. Convergent learning: Do different neural networks learn the same representations? In Advances in neural information processing systems, pp. 196-212, 2015.
Andrew L. Maas, Awni Y Hannun, and Andrew Ng. Rectifier nonlinearities improve neural network acoustic models.
Marlos C Machado, Mare G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-566 2018
Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andrew J Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, et al. Learning to navigate in complex environments. arXiv preprint arXiv:1611.03677 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, arXiv preprint 1rXiv:13/2.5602, 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp. 1928- 1937, 2016.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp. 2924-2932, 2014.
Ari S Morcos, David GT Barrett, Neil C Rabinowitz, and Matthew Botvinick. On the importance of single directions for generalization. arXiv preprint 1r31v:1803.06959, 2018
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off- oof-po reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1054-1062, 2016.
11

---

Under review as a conference paper at ICLR 2020
Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli. Zero-shot task generalization with mulliitask deep reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- -Volume 70, pp. 2661-2670. JMLR. org, 2017.
Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. Generalization guaran- lees for neural networks via harnessing the low-rank structure of the jacobian. arXiv preprint MrXiv:/966.0532, 2019.
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Kolun, and Dawn Song. Assessing generalization in deep reinforcement learning. arXiv preprint arXiv: /2282, 201 8.
Hugo Penedones, Damien Vincent, Hartmut Maennel, Sylvain Gelly, Timothy Mann, and Andre Barreto. Temporal difference learning with neural networks-study of the leakage propagation problem. arXiv preprint
2018.
Joelle Pineau. The machine learning reproducibility checklist v1.2. 2019.
Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstein. Sveca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. In Advances in Neural Information Processing Systems, pp. 6076-6085, 2017.
Martin Riedmiller. Neural fitted q iteration-first experiences with a data efficient neural reinforcement learning method. In European Conference Machine Learning, pp. 317-328. Springer, 2005.
Gavin Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems, vol- ume 37, University of Cambridge, Department of Engineering Cambridge, England, 1994.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv: 15I.::15111.09522 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint SeGi:15006.04333 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1eXiiv/707.0665 1707.063477 2017.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3 (1):9-44, 1988.
Richard S Sutton. On the virtues of linear learning and trajectory distribations. In Proceedings of the Workshop on Value Function Approximation, Machine Learming Conference, pp. 85, 1995.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Gerald Tesauro. Temporal difference learning and td-gammon. 1995.
Pierre Thodoroff, Audrey Durand, Joelle Pineau, and Doina Precup. Temporal regularization for markov decision process. In Advances in Neural Information Processing Systems, pp. 1779-1789, 2018.
John N Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffffrenee learning with function approximation. Advances in neural information processing systems, pp. 1075-1081, 1997.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets. Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A
challenge for reinforcement learning. arXiv preprint /708.0077 2017.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep
neural networks? In Advances in neural information processing systems, pp. 3320-3328, 2014.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1rXiv:1611.0335 2016.
Chiyuan Zhang, Oriol Vinyals, Remi Munos, and Samy Bengio. study on overfitting in deep reinforcement learning. arXiv preprint /rrxiv/:044 084906893, 2018.
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 EXTRA EXPERIMENTAL DETAILS
A.1.1 ATARI GAMES
Some sections are only run with 3 Atari games, MsPacman, Asterix and Seaquest. We chose these three games as they exhibit features that seem particularly amenable generalization.
The full 24 games we use for policy evaluation tests are Alien, Amidar, Assault, Asterix, BankHeist, Boxing, Breakout, ChopperCommand, CrazyClimbor DemonAttack, Freeway, Frostbite, Gopher, Hero, Jamesbond, Kangaroo, Krull, KungFuMaster, MsPacman, PrivateEye, Qbert, RoadRunner, Seaquest, and UpNDown.
All our experiments train parameters with the following architecture, as per Mnih et al. (2013): convolutional layers with kernels of shape x 32 8 x 8, 32 64 x 4, and x 3 x and with stride 4, 2, and respectively, followed by two fully-connected layers of shape 9216 x 512 and 512 x [A], A being the legal action set for a given game. All activation are leaky ReLUs (Maas ee al.) except for the last layer which is linear (as it outputs value functions or unnormalized logits for the classification experiment).
D
N
2
10
50
10k
5.7
8.7
8.5
100k
38.8
45.6
56.5
500k
44.7
79.3
85.8
Table 1: Classification error (%) for memorization experiment of Section 3.4. |D] is the dataset size. N is the number of classes. Classes are uniformly randomly assigned to states.
A.1.2 FIGURE HYPERPARAMETER
The experiments of Figures| I and 2 run for 500k steps, measuring gains every 500 updates. A learning rate of 100 is used, with L2 weight regularization of 10 When boostrapping to a frozen network, the frozen network is updated every 10k updates. We use y 0.99, a minibatch size of 32, an of 5% to generate DD, and a buffer size of 500k. Each setting run with 10 random seeds. The random seeds affect the generation of "D", the weight initialization, the minibatch sampling, and the choice of actions in e-greedy rollouts.
The values of A in Figure Jree measured every update. The memorization procedure is also run for 500k steps, which is enough for the model to seemingly converge (albeit to a non 0 error).
The Q-Learning control experiments of Figures 4 and are for 10M steps with the same setup as previously described. Each setting is run with 10 random seeds. For every environment step, one minibatch update done.
The experiments of Figure are run for 500k steps, as previously described. X-targets are computed with the forward view, using the frozen network to compute the target values this allows us to cheaply recompute all X-targets once every 10k steps when we update the frozen network. Each setting is run with 5 random seeds.
Note that we did experiment with various learning rates, momentum settings, DNN regularizations, and other common tricks-our conclusions remained the same, but for simplicity of presentation we stick to commonly used hyperparameters.
A.1.3 MINIBATCHES
All plots are generated from measures taken during training, either during policy evaluation or Q-Learning While learning rates and minibatch sizes do have influence on the results, most of the time results remain mostly the same and for simplicity of presentation only a subset of the experiments we performed we found that results were the same and lower variance for larger minibatch sizes. As such we consistently use 32 examples per minibatch, which reflects current practice in RI.
shown. Ideally, gain should be measured for single example, but
13

---

Under review as a conference paper at ICLR 2020
1.1.4 REPRODUCIBILITY CHECKLIST
We follow the Machine Learning reproducibility checklist (Pineau 2019), and refer to corresponding sections in the text when relevant.
For all models and algorithms presented, check if you include:
A clear description of the mathematical setting, algorithm, and/or model. We modified algorithms, described in the technical background, and only analyse their behaviour.
The measures we propose are straightforward to implement and only require minimal changes An analysis of the complexity (time, space, sample size) of any algorithm. The measures
we propose only add constant instrumentation overhead.
A link to downloadable source code, with specification of all dependencies, includ- ing external libraries. All code is included in supplementary materials, dependencies are documented within.
For any theoretical claim, check you include:
A statement of the result. We make no theoretical claim.
A clear explanation of any assumptions. idem.
A complete proof of the claim. idem.
For all figures and tables that present empirical results, check if you include:
A complete description of the data collection process, including sample size. We collect
data by running standard implementations of common algorithms with repeated runs.
A link to downloadable version of the dataset or simulation environment. Included in code available in supplementary materials.
An explanation of any data that were excluded, description of any pre-processing step. We generally chose hyperparameters that best represent state-of-the-as usage, then necessary that best represent findings. In most cases only minor learning rate adjutments were necessary, although they would not significantly change most plots.
An explanation of how samples were allocated for training validation testing. As are only interested in the training process this is not fully applicable.
The range of syper-parametert considered, method to select the best hyper-parameter
configuration, and specification of all asper-parameters used to generate results. See section
The exact number of evaluation runs. idem. description of how experiments were run. idem.
A clear definition of the specific measure statisties used to report results. See section
Clearly defined error bars. Figures with error bars compute bootstrapped 95% confidence
interval the mean.
A description of results with central tendency(e.g. mean) & variation(e.g. stddev). idem. A description of the computing infrastructure used Almost all experiments were run on P100 GPUs, otherwise they were Intel i7 processors.
A.2 LOOKING FOR OTHER STRUCTURES TD GAIN
On top of measuring Yoeer, i.e. TD gain for nearby examples, we also measure TD gain function of ground truth distance, value distance and feature distance. In all cases we find the expected gain to be close to 0 with only few interesting patterns the gain curves.
Ground fruth distance The Arcade Learning Environment (Bellemare et al. 2013) provides, in addition to pixel observations, the current memory (RAM) state of the game, which consists of 128 bit values. In An/anand et al. (2019), the authors annotate the relevant individual bytes, discarding those not representing anything of value. For example, in MsPacman they identify values consisting of the player's position, the ghosts' positions, etc. In Figure 7a we plot YTD function of the L1 RAM distance (for only the relevant bytes) between X and X (i.e. the update samples and the test samples; minibatch updates, for a total of 1024000 samples). There seems to be no correlation between Yrp and the distance.
2048 test samples each time perform this measure, which is every 1000
14

---

Under review as a conference paper at ICLR 2020
M MMM
McPurran MC
Milhorass GL
McPaerann Sana
Anageni
Suuguue MI
10"1
Scusson Saza
10
3D Pr.
-10"
Molhecna MC
Mullinna
Millicnaa Sacra
MF
-10
120
130
240
700
300
4.03
340
600
000
0.3
0.2
0.4
Dd
0.5
1.0
Dissaton in ground
(a) Policy evaluation, TD gain function of anno- (b) Policy evaluation, TD gain as function of distance tated ground truth distance.
in value predictions.
Figure 7: TD gain as a function of other metrics. Shaded regions are the standard error to the mean.
Value distance DNNs might alias together (blend into single point in latent space) all states that have the same value. This would mean that changing the value prediction for one of those states will change the value prediction for all other aliased states. In Figure 7b we that this effect might occur in the [O, 0.02] bin, where TD gain tends to be positive for TD methods. For Monte-Carie returns in MsPacman, the effect is negative on average in the [0. 0.02] bin, but otherwise positive from [0.02, 0.3). There seems to be no correlation otherwise to TD methods.
16.7
Kdem
Im-30-35
-30
0.20
Figure 8: Policy evaluation with CoL, TD gain as a function of cosine distance in hidden space (second to last layer).
Feature distance We perform again a similar experiment on MsPacman, but using as a distance metric the cosine similarity of activations in the second to last layer. While we do find minor correlation with distance, its magnitude is very small. In addition, this correlation is easily explained by the geometry the shallow neural network we use. Since we use leaky ReLUs and measure distance in the second to last layer, when any two states are close in the hidden space, changing the mapping to the output for one state will change the output for the other state with high probability. Thus what we observe here is closer to how much states are entangled in the hidden space rather than a real measure of how update generalization Interestingly, hidden states trained with SGD seem much more entangled, their cosine distance is often O. This does not seem to be the case with networks trained with Adam and RMSProp.
linked to distance (in true or hidden space).
A.3 SINGULAR VALUES, CONTROL POLICY EVALUATION
Figure shows the spread of singular values after 100k minibatch updates MsPacman for the Q-Learing objective and Adam/RMSProp. The difference between the control case and policy evaluation supports hypothesis that policy evaluation initially captures more factors of variation.
15

---

in case for regression value Under review as a conference paper at ICLR 2020
It remains unclear if the effect of the control case initially having fewer captured factors of variation leads to a form of feature curriculum.
Figure shows the spread of singular values after 500k minibatch updates for TD(A). Interestingly, larger values yield larger singular values and a wider distribution. Presumably, TD(A) having a less biased objective allows the parameters to capture all the factors of variation faster rather than rely on bootstrapping to gradually learn them.
Note that current literature suggests that having fewer large singular values is sign of generalization in classifiers, see in particular Oymak et al. (019),, as well as Morcos et al. (2018) and Raghu al. (2017). It is not clear whether this holds for regression, functions, but interestingly all runs (even for TD())) have a dramatic cutoff in singular values after about the 200th SV, suggesting that there may be in this order of magnitude many underlying factors in MsPacman, and that by changing the objective and the data distribution, DNN may be able to capture them faster or slower.
Control, for RMSProp
10
Control, Lor Adam
Policy evaluation. Lor RMSProp
Policy evaluation, Lor. Adam
100
Singular value (log)
10-1
10
10
10
10
10a
Singular value index (lag)
Figure 9: Spread of singular values after 100k iterations. Despite having seen roughly the same amount of data, the control experiments generally have seen fewer unique states, which may explain the observed difference. Shaded regions show bootstrapped 95% confidence intervals.
A.4 EVOLUTION OF TD GAIN WITH TRAINING
Figure II shows the evolution of TD gain during training; in relation to previous figures like Figure I the y axis now Fig. [ x axis the distance to the update sample in the replay buffer, the axis now training time, and the color now Fig. y axis the magnitude of the TD gain.
Another interesting observation with respect to the evluation of TD gain from Fig. 3 is that the density is asymmetric, predictions tend increase during training. This is consistent with the fact that DNNs are initialized to predict in expectation, while value functions for agents that receive mostly positive rewards will tend be positive. Also note that Fig. Bdiffers very little when using Adam over RMSProp.
A.5
COSINE SIMILARITIES IN TD(A)
Figures 12 and
13
show cosine similarities between gradients after 500k updates.
16

---

Under review as a conference paper at ICLR 2020
10
100
Singular value (log)
Policy evaluation, TD(2), À 0.1
Policy evaluation, TD(2), À = 0.25
Policy evaluation, TD(2), À 0.5
Policy evaluation, TD(2), À 0.75
Policy evaluation, TD(2), à = 0.8
10-1
Policy evaluation, TD(2), A = 0.9
Policy evaluation, TD(2), A 0.95
Policy evaluation, TD(2), 2 = 0.99
Policy ovaluation, for. RMSProp
Control, for RMSProp
2
100
10
102
Singular value index (log)
Figure 10: Spread of singular values after 500k iterations. Shaded regions show bootstrapped 95% confidence intervals.
A.6 DIFFERENCES SINCE LAST VISIT IN TD(A)
See Figure 14 and Figure 3 for reference.
17

---

Under review as a conference paper at ICLR 2020
0.0040
25
0.0035
20
Distance minibatch sample
15
0.0030
10
0.0025
5
0.0020
0.0015
110
-15
0.0010
-20
0.0005
-25
0.0000
-30
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
Iterations (millions)
Figure 11: Evolution of TD gain, Ynper during training. Control experiment with Adam, MsPacman, averaged over 10 runs. Note that index is excluded its magnitude would be too large and dim all other values.
A.7 Is NEAR TD GAIN INDICATIVE OF SPEED OF LEARNING?
In Figure 15 we plot, for an agent trained on MsPacman, the lifetime agent reward (i.e. the AUC of curve as in Figure (6 as function of the lifetime average near TD gain YTT The line is linear regression of the points, with correlation coefficient of r 0.4337. We vary the capacity of the agent by changing the number of hidden units of every layer, between 0.25 x and 4times the original size.
18

---

Under review as a conference paper at ICLR 2020
cosine similariy between Va and (S
1.0
0.9
0.8
0.7
0.6
0.1
0.8
0.25
0.9
0.5 0.95
0.5
0.75 0.99
-30
-20
-10
0
10
20
30
Distance minibatch sample replay buffer
Figure 12: Measuring the cosine similarity in a sequence. The y axis shows the cosine similarity between V VeLa (SE))())Ss) and (Se))())(S++)) for the nearest is E [-30, 30] neighbours in the replay buffer. The larger À is, the more similar gradient updates are for two states when those states are close in time. Shaded regions show bootstrapped 95% confidence intervals.
0.07
==
0.1, ==
0.8, 0.33
0.06
0.25
0.9, E= 0.34
E=022
-0.95 0.35
Density over the replay buffer
0.05
0.75,E 0.32
-0.99,E 0.38
0.04
0.03
0.02
0.01
0.00
1..0
-0.75
0.25
0.00
0.25 0.50
0.75
cosine similarity between V ((C( and Va((S))
Figure 13: Measuring the distribution of cosine similarity. The y axis shows the density of given cosine similarity (r axis) between (eLrp()(S.) and VoLrD(A((S) for 20k (i,j) pairs in the replay buffer. The distributions for positive cosine similarities are similar for all values of X. On the other hand, on the left side of the plot we can see that when gets closer to O, there are more and more gradients "pointing the wrong way". L.c. with negative cosine similarity. The labels show the expected cosine similarity over the replay buffer (E = ...), which show that as increases, gradients more similar. Interestingly there almost pairs of states with cosine similarity of 0.
19

---

Under review as a conference paper at ICLR 2020
A 0.1
À 0.25
03-
0
0.4
02
4.5
00
01g
100
420
300
210
903
baration Uhoeaando
À 0.5
À 0.75
088
0.6
(19-4 (ii
02.
42
402
:00
200
300
409
500
300
300
300
+00
500
Benakin (laxsanb))
Dasikno (komaadd))
0.8
0.9
08-
06-
0.2
402
4.5
4.5
100
200
425
500
300
110
500
- 0.95
À - 0.99
08-
88 06-
034
07-
42-
402
4.4
41
4.5
45
110
200
300
409
500
100
200
300
-00
509
Tecalios (hresind))
Deviiion (llesaadd
Figure 14: Reproducing Fig.
3 but for all values that were tested.
20

---

Under review as a conference paper at ICLR 2020
120
Lifetime Average Reward
115
110
105
100
0..0001
0.00000 0.00001 Lifetime Average Near TD Gain
0.00002
0.00003
Figure 15: The lifetime agent reward (i.e. the AUC of curve as in Figure 6 as function of the lifetime average near TD gain Y-gar, The line is linear regression of the points, with a correlation coefficient of 0.4337. We vary the capacity of agent by changing the number of hidden units of every layer, which is reflected by the size of the circles.
21


Reviews:
[{"review_id": "rklkuYFl5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 studies the generalization property of DRL.  Fundamentally, this is a very interesting problem. The authors experimentally analyze this issue through the lens of memorization, and showed that it can be observed directly during training. This paper presents the measure of gradient update generalization, best understood as a side-effect of neural networks sharing parameters over the entire input space. This paper is very written, and well organized.  The experiments are quite solid. However  I may be not capable in judging the novelties and contributions of this paper, since I did not conduct research on this topic.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "rJx71n4AtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 manuscript is analyzing the \"generalization\" in TD(lambda) methods. It includes supervised learning from trajectories, on-policy imitation learning, and basic RL setting. Moreover, memoization performance has also been measured. Main conclusion is the fact that TD(0) performs very similar to tabular learning failing to transfer inductive biases between states. There are also additional surprising results about optimization.\n\nThe empirical study is rather complete and significant. It raises interesting questions for the community and states some clear open problems. \n\nResults are conclusive and interesting. I believe it is a study which a practitioner using TD-based method should be aware of. Hence, I believe it is impactful.\n\nOn the other hand, the manuscript has some significant issues which need to be resolved as follows:\n\n- One major issue is calling the analyzed metric \"generalization\". Generalization by definition requires something beyond what is seen. I believe the quantity defined in (9) is generalization. However, it can not be computed. Hence, calling its empirical version, \"generalization\" is confusing and a clear misuse of the term. I strongly urge authors to call the observed quantity something else. \"Empirical expected improvement\", \"gradient regularity\", \"expected gain\", etc. are some candidates come to my mind. \n\n- The optimization aspect is very interesting; however, it confuses the exposition significantly. I think it is better to give all results using adam first, and then showing the comparisons between adam and rmsprop later would be much more readable and easier to understand.\n\n- There are some clarity issues in the explanation of the experiments. Figure 3 is very confusing and it requires multiple reading to be understandable. A clearer visualization or a better explanation would improve the paper.\n\n- I am puzzled about why the authors did not use Q_MC in policy evaluation experiments (Section 3.3). I think it can very well be used in a straightforward manner. It would be an interesting addition to the experiments.\n\nMinor Nitpicks:\n- Memorization section is not clear. The discussion on N is very confusing as \"14.4% for N = 2 and of 16.1% for N = 50\" does not match any of \"10.5%, 22.7%, and 34.2%\" Can you give full error table in appendix?\n\nOverall, I like the study and suggest to accept it hoping authors can fix the issues I raise during rebuttal period.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkenPkootB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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:\nThis paper performs an empirical evaluation of generalization by TD methods with neural nets as function approximators. To quantify generalization, the paper considers the change in the loss function at similar states to the one where the update rule is being applied (where “similar” is usually defined as nearby in time). It comes to a variety of conclusions including that TD(0) does not induce much generalization, that TD(0) does not induce as much generalization as supervised learning, and that the choice of optimizer and objective changes the behavior according to their generalization criteria in various ways.\n\n\nDecision:\nThis paper should be rejected because (1) the motivation is unsubstantiated, (2) the main metrics used (“gain” at nearby states and difference since last visit) are of questionable importance, and (3) the conclusions are often vague and not informative.\n\n\nMain argument:\nMotivation:\n- The paper motivates the need for an evaluation of “gradient update generalization” by claiming that it is related to sample complexity and brittleness of RL algorithms. While I agree that this is plausible, there is nothing empirical or theoretical to support this claim in the paper or in the references. This is a significant problem since this assumed connection underlies everything in the paper.\n- Also, it is this sort of generalization that differentiates the function approximation setting (where there are no convergence guarantees for TD without strong assumptions) from the tabular setting (where there are convergence and sample complexity guarantees). \n\nMetrics:\n- The main metric used is TD gain on temporally nearby states. The TD gain is defined as the reduction in the squared TD error at some state s’ when an update is applied at some other state s. Note this metric does not capture all update generalization, but only update generalization as it effects the TD error.\n- It is not evident, nor supported by the paper, that improvements in this metric at nearby states necessarily improve performance of the algorithm. This is especially true when there is a tradeoff between improvement at very nearby vs. somewhat nearby states, it is not clear which behavior is preferable (and this behavior seems to occur in experiments). As a result there is no clear way to use this metric to determine which algorithms are preferable. \n- The other metric used in the paper is the change in value function at a state since the last time that state was sampled from the buffer. It is also not clear whether this measurement is necessarily important for the same reasons as above. \n\nConclusions:\n- In general the results are presented in plots that do not give clear implications and are difficult to read. I understand that we cannot expect completely clean results on such empirical questions, but the results would be potentially much more convincing and clear if the hypotheses were clearly stated and then one plot could summarize the result with respect to each hypothesis. For example, the gain plots are difficult to compare and interpret clearly and the memorization plots do not give such clear results (eg. 3a and 3d look visually fairly similar). Another example is the comparisons between optimizers, which are fine to have as a specific point in one section, but do not need to be in every plot.\n- The main result claimed in the paper is that there is little generalization from TD(0) when compared to supervised learning. This seems to be born out by the difference between figure 1a and 2a, but the difference in scale makes it a bit difficult. It is also not clear how to quantify this result or what the implications are. \n- The plots are averaged across all states over all of training and all environments, while this is somewhat rationalized in figure 11, I am worried that this may be covering some additional complexity/ambiguity in the results. \n- The result about TD(lambda) seems to be born out by figures 3e and f and 5, but is also unsurprising since the objective explicitly averages across temporally nearby states. Again it is not clear how this temporal consistency of updates should be interpreted in terms of the goals of the RL algorithms.\n\nAt a higher level, the paper feels like a solid preliminary set of experiments rather than a paper organized around a clear motivating idea with clear hypotheses to test. The results would become more interesting if the metrics used could be connected back (either empirically or theoretically) to an objective. For example, does generalization in the sense defined in the paper give better performance at value estimation or return maximization? Can these results be quantified in a more direct way than the plots presented in the paper? \n\n\nAdditional feedback:\n- The plots all have different scales which makes them difficult to compare\n- Using “distance” to refer to the relative tilmestep of samples in the replay buffer is confusing (distance cannot be negative)\n- There are strange visual artifacts (horizontal lines) in Figures 3, 5, 10, 12, 13, and 14\n- Sections 3.7 and 3.8 very briefly present results that seem to distract from the main thread of the paper\n- Using one network architecture across all experiments seems like it may have a significant impact on the results. I understand that the architecture chosen is standard and testing different architectures is time consuming, but making broad claims about the algorithms based on only one architecture is potentially dangerous. \n- I assume that the replay buffer is always being sampled uniformly, but I could not find this detail in the paper. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received three reviews. R1 recommends Weak Reject, and identifies a variety of concerns about the motivation, presentation, clarity and soundness of results, and experimental design (e.g. choice of metrics). In a short review, R2 recommends Weak Accept, but indicates they are not an expert in this area. R3 also recommends Weak Accept, but identifies concerns also centering around clarity and completeness of the paper as well as some specific technical questions. In their response, authors address these issues, and have a constructive back-and-forth conversation with R1, who remains unconvinced about significance of the empirical results and thus the conclusion of the overall paper. After the discussion period, R3 indicated that they weakly favored acceptance but agreed that the paper had significant presentation issues and would not strongly advocate for it. R1 advocated for Reject, given the concerns identified in their reviews and followup comments. Given the split decision, the AC also read the paper. While the work clearly has merit, we agree with R1's comment that it is overall a "potentially interesting idea, but the justification and presentation/quantification of results is not good enough in the submitted paper," and feel the paper really needs a revision and another round of peer review before publication. 
Decision: Reject